ТОП 10:

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



Рассмотрим матрицу B=AUp=(bij).

В ней: b1 = ca1+sap, bp = -sa1+cap. Остальные столбцы совпадают со столбцами А.

 

Свойство 1

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

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

.

Отсюда .

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

 

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

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

Тогда .

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

а)если , то

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

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

 

Свойство 2Если | a1|≥| ap|, то | b1|≥| a1|≥| ap|≥| bp| и | b1|>| a1| при .

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

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

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

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

Отсюда:

и | b1|>| a1| при .

2) Пусть .

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

Т.к. , , a , то

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

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

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

 

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

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

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

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

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

Пусть дана матрица A=(aij). Рассмотрим матрицу A1=AU1, где U1 – ортогональная матрица перестановки столбцов: первый столбец матрицы А1 максимален.

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

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

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

u11 = up(k)p(k)= c =cosα, -up(k)1 = u1p(k)= -s = - sinα,

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

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

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

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

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

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

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

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

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

 

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

 

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

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

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

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

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

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

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

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

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

3.И т.д.

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

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

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

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

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

 

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

 

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

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

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

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

 

 

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

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

uqq = upp= c =cosα, -upq = uqp= -s = - sinα, остальные диагональные элементы равны 1, а недиагональные – нулю.

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

Матрица В=AUpq отличается от А столбцами bp и bq:

bp=c·ap+s·aq

bq= -s·ap+c·aq

bj=aj, j≠p,q

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

dpj=c·bpj+s·bqj

dqj= -s·bpj+c·bqj

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

Тогда,

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

Заметим:

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

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

Т.е. величина S2 меняется при элементарном вращении настолько, насколько изменится |apq|2.

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

Положим dpq=0:

dpq=c·bpq+s·bqq=c(-s·app+c·apq)+s(-s·aq p+c·aqq)=

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

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

2) иначе

 

 







Последнее изменение этой страницы: 2016-04-26; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.234.245.125 (0.008 с.)