Учебное пособие по курсу «Нейроинформатика» | страница 28

1 .Запишем матрицу размерности m×2m следующего вида: (G_>m|E_>m).

2. Используя операции сложения строк и умножения строки на ненулевое число преобразуем левую квадратную подматрицу к единичной. В результате получим (E_>m|G_>m^>-1). Пусть известна G_>m^>-1 — обратная к матрице Грама для множества из m векторов x^>i. Добавим к этому множеству вектор x^>m>+1. Тогда матрица для обращения матрицы G_>m+1 методом Гауса будет иметь вид:

После приведения к единичной матрице главного минора ранга m получится следующая матрица:

где b_>i — неизвестные величины, полученные в ходе приведения главного минора к единичной матрице. Для завершения обращения матрицы G_>m+1 необходимо привести к нулевому виду первые m элементов последней строки и (m +1)-го столбца. Для обращения в ноль i-го элемента последней строки необходимо умножить i-ю строку на (x, x^>m>+1) и вычесть из последней строки. После проведения этого преобразования получим

где , .

b_>0 = 0 только если новый эталон является линейной комбинацией первых m эталонов. Следовательно b_>0 ≠ 0. Для завершения обращения необходимо разделить последнюю строку на b_>0 и затем вычесть из всех предыдущих строк последнюю, умноженную на соответствующее номеру строки b_>i. В результате получим следующую матрицу

где F_>ij = G_>mij^>-1-b_>ic_>j/b_>0. Поскольку матрица, обратная к симметричной, всегда симметрична получаем c_>i/b_>0 = -b_>i/b_>0 при всех i. Так как b_>0 ≠ 0 следовательно b_>i = -c_>i.

Обозначим через d вектор ((x^>1, x^>m>+1), …, (x^>m, x^>m>+1)), через b — вектор (b_>1, …, b_>m). Используя эти обозначения можно записать b = G_>m^>-1d, b_>0 = (x^>m>+1,x^>m>+1)-(d,b), b_>0 = (x^>m>+1,x^>m>+1)-(d,b). Матрица G_>m+1^>-1 записывается в виде

Таким образом, при добавлении нового эталона требуется произвести следующие операции:

1. Вычислить вектор d (m скалярных произведений — mn операций, mn≤n²).

2. Вычислить вектор b (умножение вектора на матрицу — m² операций).

3. Вычислить b^>0 (два скалярных произведения — m+n операций).

4. Умножить матрицу на число и добавить тензорное произведение вектора b на себя (2m² операций).

5. Записать G_>m+1^>-1.

Таким образом эта процедура требует m+n+mn+3m² операций. Тогда как стандартная схема полного пересчета потребует:

1. Вычислить всю матрицу Грама (nm(m+1)/2 операций).

2. Методом Гаусса привести левую квадратную матрицу к единичному виду (2m³+m²-m