Алгоритм сингулярного разложения

Пусть дана матрица A=(a_ij). Рассмотрим матрицу A₁=AU₁, где U₁ – ортогональная матрица перестановки столбцов: первый столбец матрицы А₁ максимален.

Рассмотрим последовательность матриц: A_k+1=A_kU_p(k) , k=1,2…,

где p(k) – номер столбца (= 2,3..n; 2,3..);

U_p(k) – матрица простейшего поворота:

u₁₁ = u_p(k)p(k)= c =cosα, -u_p(k)1 = u_1p(k)= -s = - sinα,

остальные диагональные элементы равны 1,

а недиагональные – нулю.

Т.е. у всех A_k первый столбец максимальный, у всех A_k+1 первый столбец ортогонален p(k+1). При этом сумма квадратов сохраняется.

Обозначим . Действительно, тогда .

Отсюда следует лемма:

Лемма 1 Последовательность норм первых столбцов матриц сходится.

Доказательство

По Свойству 2 предыдущего пункта последовательность не убывает.

А из сохранения суммы квадратов она ограничена, а значит сходится.

ЗамечаниеОтсюда не следует сходимость векторов .

Лемма 2Последовательность матриц {A_k} сходится поэлементно при k→∞ (без доказательства).

Т.е. . Эта матрица обладает следующими свойствами:

1)первый столбец наибольший по модулю

2)первый столбец ортогонален всем остальным.

Действительно, предположим противное . Умножим на U_p1, получим требуемое.

Таким образом, получен алгоритм сингулярного разложения.

Пусть матрица А nого порядка. Построим последовательность A_k→A_∞.

1.Обозначим как в процессе максимализации первого столбца. Т.о. первый столбец макимален и ортогонален всем остальлным.

2.Максимизируем второй столбец матрицы с помощью последующих, не изменяя первый. Полученная последовательность матриц сходится к некоторой матрице .

3.И т.д.

n-1. Максимизируем (n-1)ый столбец у матрицы . Получим матрицу с монотонными нормами и взаимоортогональными столбцами.

Запишем полученную матрицу в виде: , где ортогональная матрица V есть произведение ортогональных матриц.

Обозначим нормы столбцов матрицы как S_k.

Получим , где W – ортогональная матрица.

Таким образом, AV = WS, т.е. A = WSV^T – SVD-разложение.