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

Рассмотрим матрицу 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|, то , т.е. новые столбцы ортогональны.

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

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

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

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

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

 

Главное собственное число

 

Пусть А=(a_ij) – симметричная матрица. Метод максимизации столбцов дает следующее:

Перемножим равенства:

максимальное собственное число матрицы A² (из метода максимизации).

λ=±b – главное собственное число симметричной матрицы А.

 

 

Метод вращения

Рассмотрим симметричную матрицу А=(а_ij). Обозначим ортогональную матрицу вращения U_pq(α):

u_qq = u_pp= c =cosα, -u_pq = u_qp= -s = - sinα, остальные диагональные элементы равны 1, а недиагональные – нулю.

Рассморим вращение матрицы в плоскости O_pq:

Матрица В=AU_pq отличается от А столбцами b_p и b_q:

b_p=c·a_p+s·a_q

b_q= -s·a_p+c·a_q

b_j=a_j, j≠p,q

Матрица отличается от В р-ой и q-ой строками:

d_pj=c·b_pj+s·b_qj

d_qj= -s·b_pj+c·b_qj

Остальные строки не изменяют.

Тогда,

Разобьем S на диагональную и недиагональную части:

Заметим:

При элементарном вращении D недиагональные элементы а_pi, a_qi и а_ip, a_iq (i≠p,q) меняются так, что попарные суммы квадратов их модулей сохраняются.

Кроме этих элементов вне диагонали меняется элемент а_pq.

Т.е. величина S₂ меняется при элементарном вращении настолько, насколько изменится |a_pq|².

Будем подбирать вращения так, чтобы S₂ максимально уменьшалась.

Положим d_pq=0:

d_pq=c·b_pq+s·b_qq=c(-s·a_pp+c·a_pq)+s(-s·a_{q p}+c·a_qq)=

α выберем следующим образом:

1) при а_pp cos2α=0 => α=π/4

2) иначе