1.Максимизация первого столбца

Рассмотрим матрицу B=AU_p=(b_ij).

В ней: b₁ = ca₁+sa_p, b_p = -sa₁+ca_p. Остальные столбцы совпадают со столбцами А.

Свойство 1

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

Действительно:

.

Отсюда .

Что и требовалось доказать.

Выберем угол α в матрице U_p так, чтобы | b₁ | был максимален.

Рассмотрим функцию

Тогда .

Обозначим α=α_p: f ’(α)=0. Будем выбирать α_p по правилу:

а) если , то

б) иначе α_p находится из равенства

в) заметим, что α_p=0 тогда и только тогда, когда .

Свойство 2 Если | a₁|≥| a_p|, то | b₁|≥| a₁|≥| a_p|≥| b_p| и | b₁|>| a₁| при .

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

Действительно:

1) Пусть . Тогда и .

Следовательно, из определения f(α): .

Отсюда:

и | b₁|>| a₁| при .

2) Пусть .

Рассмотрим функцию .

Т.к. , , a , то

f ’’(α_p)≤0, т.е. α_p – локальный максимум ( ) и общий максимум функции на .

Следовательно, .

Что и требовалось доказать.

Свойство 3 Если | a₁|≥| a_p|, то , т.е. новые столбцы ортогональны.

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

Действительно:

Что и требовалось доказать.

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

Пусть дана матрица 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-разложение.