Головна
1. Метод характеристичного рівння матриці
2. QR-алгоритм
3. Способи прискорення QR-алгоритму
4. Обчислення окремих власних значень
Розділ 5. Методи розв'язування матричних проблем на власні значення

5.1. Метод характеристичного рівння матриці
У загальному випадку результатом множення матриці A на довільній ненульовий вектор x є новий вектор y = Ax, який відрізняється від початкового вектора x за довжиною (модулем) і напрямком (орієнтацією) у багатовимірному просторі. Але в деяких випадках після такої операції множення новий вектор y не змінює свою орієнтацію, а змінює тільки довжину, тобто окремі його компоненти стають пропорційними відповідним компонентам вектора x. Такі вектори x називають власними векторами матриці A, а коефіцієнти пропорційності - власними значеннями (або числами) матриці A. Ця властивість лежить в основі обчислення власних значень і власних векторів матриці. Квадратна матриця розмірності nxn має n власних значень і власних векторів.
Власними значеннями матриці називають такі скалярні величини, які є ккоренями рівняння


або
     (5.1)

Звідси, якщо x не дорівнює 0, перепишему цю тотожність у такому вигляді:
     (5.2)

Якщо визначник (5.2) розкрити відносно значень , то отримаємо так зване характеристичне рівняння матриці A у вигляді полінома n-степеня P() відносно власних значень. Розв'язок цього рівняння визначає множину всіх власних значень матриці, яка називається її спектром. Кожному власному значенню матриці відповідає свій власний вектор.

5.2. QR-алгоритм
QR-алгоритм базується на перетворенні подібності матриці A таким чином, щоб власні значення матриці, отриманої внаслідок перетворення, обчислювалися простіше, ніж для початкової матриці. найзручніше знайти власні значення трикутної матриці, для якої:


при цьому власні значення дорівнюють діагональним елементам матриці i = 1, 2, ..., n.
Дещо складніше знаходити власні значення для блочно-діагональної матриці

оскільки

Але якщо блочні матриці, які розташовані на діагоналі, мають крім розмірності 1х1 ще розмірність 2х2, власні значення матриці розмірності 2х2 обчислюються у такий спосіб:

     (5.3)

QR-алгоритм дозволяє створити на базі матриці A матрицю B, подібну до A, яка має блочно-діагональну форму.
Приклад 5.1


Знайдемо власні значення матриці з блочно-діагональною формою:

на діагоналі матриці розташовані чотири блоки, два з яких мають розмірність 2х2. Тому, користуючись формулою (5.3) обчислюємо для діагональних блоків:

Нехай A - довільна матриця з дійсними елементами, власні значення якої необхідно визначити. Її можна завжди зобразити у вигляді добутку двох матариць:
A= Q1R1,     (5.4)

де Q1 - ортогональна матриця, а R1 - верхня трикутна матриця.
Із виразу (5.4) знаходимо R1 = Q1-1A і пересвідчуємося, що матриця
A1 = R1Q1 = Q1-1AQ1,     (5.5)

яка є результатом перестановки множників у (5.4), буде подібна до матриці A.
Тепер розкладемо матрицю A1 на добуток ортогональної і правої трикутної матриць A1 = Q2R2 і сформуємо нову матрицю A2 = Q2R2, яка подібна до A.
Дотримуючись єдиних правил побудови, можна сформувати послідовність матриць Am, де m = 1, 2, ... . Наприклад, матрицю Am можна розкласти на добуток ортогональної та правої трикутної матриць Am = Qm+1Rm+1 і записати нову матрицю
Am+1 = Rm+1Qm+1.

Оскільки Am+1 = Qm+1-1AmQm+1, то всі матриці Am подібні між собою до початкової матриці A. При цьому матриця Am обчислюється за формулою
Am = (Q1, Q2, ..., Qm)-1A(Q1, Q2, ..., Qm) = Pm-1APm.     (5.6)

Якщо A - матриця, яка містить комплексні елементи, то матриця Qi повинні бути унітарними матрицями U, при цьому UU* = E, де U отримують з U заміною елементів на комплексно-спряжені й наступним транспонуванням.
Було доведено, що коли в розкладі матриці A всі діагоналі мінори матриці Q не вироджені, то послідовність матриць Am, якщо m прямує до нескінченності, збігається до матриці блочно-діагональної форми.
Розкладання матриці на ортогональну і верхню трикутну матриці здійснюється послідовною дією на матрицю A ортогональних матриць обертання Гівенса. Для отримання верхньої трикутної матриці R = Q-1A елементи початкової матриці aij, які стоять нижче головної діагоналі, обнулюються по стовпцях. Для цього використовується послідовність ортогональних матриць обертання:

Помножимо транспоновану матрицю Гівенса на матрицю A, і в отриманій матриці виділимо елементи:

де - елемент, який стане рівний нулю; - діагональний модифікований елементи.
Елемент буде рівний нулю, якщо

В усіх подальших обчисленнях із матрицями Гівенса елемент залишається нульовим, тому що в цих матрицях більше не використовуються одночасно елементи, що розташовані в рядку i та стовпці j. Можна показати, що для QR-розкладання повної матриці A необхідно виконати 4n3/3 операцій.
Існує певна аналогія між методами QR-розкладання і матричногго LU-розкладання. Так само, як матриця L формується як добуток матриць Li, що використовуються для обнулювання елементів стовпців під час формування матриці U, окремі матриці обертання Гівенса дозволяють побудувати матрицю R, але перестановка рядків при цьому не потрібна. Таким чином, дані методи не збігаються, і в процесі LU-розкладання власні значення матриці не зберігаються.
У разі збіжності процесу QR-розкладання матриці обчислення власних векторів xi за відомими власними значеннями , істотно спрощується, якщо порівняти його з прямим розв'язанням рівняння (5.1), тому що вже виконано перехід від матриці A до матриці R. Як наслідок власні вектори верхньої трикутної матриці R знаходять із розв'язку лінійної системи з верхньою трикутною матрицею:
     (5.7)

Приклад 5.2


Знайдемо матриці Q і R для матриці

Починаємо з елемента a12: a12 = 3, i = 2, j = 1 і відповідна матриця Гівенса має вигляд:

Тоді

Тепер обнулюємо елемент a13 матриці A1: a31 = 4, i = 3, j = 1, і відповідна матриця Гівенса має вигляд:

Продовжуючи далі, на шостій ітерації отримаємо:


Приклад 5.3



Знайдемо власні значення симетричної матриці

Розкладемо її на множники Q1 і R1:

Скориставшись значеннями матриць Q1 і R1, будуємо подібну матрицю:

Розкладемо її на множники:

Знаходимо нову подібну матрицю та її множники:

Далі будується така подібна матриця:

Якщо знехтувати елементом a32, то можна вважати, що мету досягнуто, і матриця A3 має блочно-діагональну форму. При цьому одне власне значення дорівнює два інших обчислюються як розв'язок характеристичного рівняння матриці


5.3. Способи прискорення QR-алгоритму
Процедура розкладання матриці A на множники Q і R досить громіздка, тому в процесі роботи QR-алгоритму бажано спрощувати структуру подібних матриць Am перед тим, як буде отримана їх блочно-діагональна структура.
З цією метою на практиці матрицю A спочатку перетворюють на матрицю Хессенберга, яка подібна матриці A. Матриця A має верхню форму Хессенберга, якщо aij = 0, коли i > j + 1. Наприклад, верхня форма Хессенберга для матриці 6х6 має вигляд:


Можна сподіватися, що у разі генерування за допомогою QR-алгоритму послідовність подібних матриць Am через обнулення елементів нижньої діагоналі скоріше сформуються діагональні блоки розмірності 2х2.
У разі зведення матриці A до верхньої форми Хессенберга обнулення елементів aij по сповпцях виконується перетвореннями подібності виду Am+1 = Qm+1-1AmQm+1, де Qm+1 - матриця обертання Гівенса:

для якої
     (5.8)

Якщо матриця A зведена до форми Хессенберга, яка зберігається під час наступних QR-ітерацій, то складність одного QR-розкладання зменшується до 4n2 операцій для несиметричних матриць, де n - розмірність матриці A.
Приклад 5.4


Зведемо до форми хессенберга матрицю

Починаємо з елемента a31, для якого i = 3, j = 1, і будуємо відповідну матрицю Гівенса:

де

Перше еквівалентне перетворення формує матрицю, яка подібна до матриці A:

Далі обнулюємо елемент a41 матриці A2, для якого i = 4, j = 1, і відповідна матриця Гівенса:

де

Друге еквівалентне перетворення формує нову матрицю, яка подібна до матриці A:

Нарешті обнулюємо елемент a42 матриці A2, для якого i = 4, j = 2, використовуючи відповідну матрицю Гівенса:

де

Таким чином, отримуємо:

Для прискорення збіжності використовують QR-алгоритм із зсувом. Будують послідновність ортогональних матриць Qk і правих трикутних матриць Rk у відповідності з рекурентними формулами
Ak - ckE = QkRkAk+1 = RkQk + ckE,
k = 1, 2, ... ,

де ck - константа.
Покажемо, що при цьому власні значення зберігаються, тобто ми маємо справу з перетворенням подібності. Дійсно,
Ak+1 = RkQk + ckE = Qk-1(Ak - ckE)Qk + ckE = Qk-1AkQk - ckE + ckE = Qk-1AkQk.


5.4. Обчислення окремих власних значень
Якщо необхідно оцінити лише деякі з власних значень, то простіше використовувати степеневий метод для формування послідовності векторів

zk+1 = Azk = Ak+1z0, k = 1, 2, 3, ... .      (5.9)
Припустимо, що матриця A має n лінійно незалежних власних векторів xi і максимальне за величиною власне значення

Якщо розкласти деякий ненульовий вектор z0 у базисі власних векторів матриці
z0 = a1x1 + a2x2 + ... + anxn,

то

Оскільки для j > 2, то напрямок вектора zk прямує до напрямку власного вектора x1, якщо тільки a1 не дорівнює 0.
Для підвищення стійкості обчислень проводять масштабування послідовності векторів zk, яке найпростіше здійснити, якщо перейти до послідовності yk нормуванням векторів zk за значеннями їх найбільших елементів zki, тобто замість виразу (5.9) використовують співвідношення:
     (5.10)

при цьому
     (5.11)

і похибка визначення найбільшого власного значення прямує до нуля як
   Коли степеневий метод застосовувати до оберненої матриці A-1, то аналогічно можна оцінити величину найменшого власного значення якщо виконуєтья умова

Приклад 5.5

Знайдемо найменше власне значення матриці:

Для цього нам необхідна обернена матриця:

Виконаємо послідовність ітерацій, користуючись співвідношеннями (5.10) і обравши початковий вектор z0 = [1, 1, 1, 0]T:

Враховуючи, що ми отримали оцінку оберненої величини найменшого власного значення матриці, знаходимо

або



Степеневий метод можна поширити і на обчислення інших власних значень матриці, які за абсолютною величиною менші, ніж або більші, ніж . Для цього необхідно провести редукцію матриці, замінивши початкову матрицю іншою матрицею, яка не матиме вже знайдених значень або . Якщо матриці симетричні, така редукція здійснюється методом Хотелінга, який базується на використанні властивості ортогональності власних векторів матриці:
     (5.12)

де компоненти векторів нормуються за значенням

Нова матриця A2 будується на основі початкової матриці A1, яка має найбільше власне значення , так:
     (5.13)

Якщо застосувати степеневий метод до матриці A2, ітераційний процес буде сходитися до наступного за абсолютною величиною власного значення
Дійно, якщо рівність (5.13) помножити справа на вектор x1, отримаємо вираз:

який з огляду на ортогональність власних векторів матриці спрощується і має такий вигляд:

Отже, значення і x = x1 також є розв'язком рівння або, інакше кажучи, матриця A2 має такий набір власних значень: . Тобто найбільше власне значення замінюється значенням 0 й ітерації степеневого методу будуть збігатися до наступного найбільшого власного значння . Теоретично можна побудувати потім матрицю A3 і так далі для перебору всіх власних значень. Однак у цьому разі через накопичення похибки результати поступатимуться за точністю і швидкодією результатам, які можна отримати за допомогою QR-алгоритму.