69324

LR-та QR-алгоритми обчислення власних значень

Лекция

Математика и математический анализ

Цей метод базується на перетворенні подібності матриці А таким чином щоб власні значення матриці отриманої внаслідок перетворення знаходилися простіше чим для початкової матриці. Найбільш просто обчислювати власні значення трикутної матриці для якої...

Украинкский

2014-10-03

325.5 KB

8 чел.

Лекція 9. LR-та QR-алгоритми обчислення власних значень

Цей метод базується на перетворенні подібності матриці А таким чином, щоб власні значення матриці, отриманої внаслідок перетворення, знаходилися простіше, чим для початкової матриці. Найбільш просто обчислювати власні значення трикутної матриці, для якої:

при цьому λi(A) = aii, i = .

Дещо складніше знаходити власні значення для блочно–діагональної матриці

А = ,

оскільки det(λE - A) = det(λE11 - A11)∙det(λE22 - A22)∙…∙det(λEnn - Ann) .

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

 (4.11)

QRалгоритм дозволяє створити на базі матриці А матрицю В, подібну А, яка має блочно–діагональний вигляд.

Приклад 4.3.

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

А =

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

для А1 ,

для А22 та А33 ,

для А44  

Нехай А  довільна дійсна матриця, власні значення якої необхідно визначити. Її можна завжди представити у вигляді добутку двох матриць:

A = Q1R1, (4.12)

де Q1 ортогональна, R1  верхня трикутна матриці.

З виразу (4.12) знаходимо R1 = Q1 - 1 A і пересвідчуваємося, що матриця

А1 = R1 Q1 = Q1 - 1 А Q1, (4.13)

отримана переставлянням множників в (4.12), буде подібною матриці А.

Тепер розкладемо матрицю А1 на добуток ортогональної і правої трикутної матриць у вигляді A1 = Q2R2 і сформуємо нову подібну матрицю А2 = R2Q2.

Дотримуючись єдиних правил побудови, можна сформувати послідовність матриць Аn. Наприклад, матрицю Аn можна розкласти на добуток ортогональної і правої трикутної матриць у вигляді Аn = Qn + 1 Rn + 1 і записати нову матрицю Аn + 1 = R n + 1 Q n + 1. Оскільки А n + 1 = = Q n + 1 - 1 Аn Qn + 1, то всі матриці Аn подібні між собою і подібні до початкової матриці А. При цьому

An = (Q1 Q2..... Qn) - 1 A (Q1 Q2....... Qn) = Pn - 1APn. (4.14)

Якщо А матриця з комплексними елементами, то матриці Qі повинні бути унітарними матрицями U, при цьому UU* = E, де U* отримують з U заміною елементів на комплексно–спряжені і наступним транспонуванням.

Було доведено, що якщо в розкладі матриці А всі діагональні мінори матриці Q не вироджені, то послідовність матриць Аn при n→∞ збігається і набуває блочно–діагонального вигляду.

Розлад матриці на ортогональну і верхню трикутну матриці здійснюється послідовною дією на матрицю А ортогональних матриць обертання Гівенса. Для отримання верхньої трикутної матриці R = Q - 1, A = Q - 1A елементи початкової матриці aij, які стоять нижче головної діагоналі, обнулюються по стовпцям. Для цього використовується послідовність ортогональних матриць обертання виду:

 (4.15)

Перемножимо матрицю Гівенса на матрицю А і в отриманої матриці виділимо змінені елементи:

де aij  елемент, який обнулюється; ajj  діагональний елемент.

Елемент буде рівний нулю, якщо вибрати

 (4.16)

При всіх наступних використаннях матриць типу Гівенса елемент  залишається нульовим, тому що в наступних матрицях Гівенса більше не використовується одночасно індекси рядків i і стовпця j.

Можна показати, що для QR–розкладу повної матриці А необхідно 4n3/3 операцій, а також можна провести певну аналогію між методом QR–розкладу і матричним LU–розкладом, описаним в параграфі 2.4. Як матриця L формується через окремі матриці Li, які використовуються для обнулення елементів стовпців при формуванні матриці U, так і окремі матриці обертання Гівенса дозволяють побудувати матрицю R, але без необхідності перестановки рядків. Таким чином, ці розклади не співпадають, і в процесі LU–розкладу власні значення матриці не зберігаються.

Коли QR–розклад збігся, обчислення власних векторів xi по відомим власним значенням λi значно спрощується порівняно з прямим розв’язком рівняння (4.1), тому що вже виконано перехід від матриці А до матриці R. В результаті власні вектори верхньої трикутної матриці R знаходяться з розв’язку лінійної системи з верхньою трикутною матрицею:


(
4.17)

Приклад 4.4.

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

А =

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

 

Тоді

 

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

 

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

 

Приклад 4.5.

Знайти власні значення несиметричної матриці, розглянутої в Прикладі 4.4:

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

;

Розкладаємо її на складові множники:

 

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

;

 

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

;

 

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

;

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

;

 

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

;

 

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

Якщо знехтувати елементами a21, a31, a41, a42, a43, то можна вважати, що мету досягнуто і матриця  має блочно–діагональну форму. При цьому два власних значення дорівнюють λ1 = 8,1142, λ2 = - 2,2363, два інших визначаються блоком другого порядку:

.

Відповідь: λ1 = 8,1142, λ2 = - 2,2363, λ3 = 4,2635, λ4 = - 4,1413

Точні значення: λ = [8,1077, - 2,2209, 4,2594, - 4,1461]t.

Приклад 4.6.

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

.

Розкладаємо її на складові множники:

 

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

;

Розкладаємо її на складові множники:

 

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

;

 

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

;

Якщо знехтувати елементом a32, то можна вважати, що мету досягнено і матриця  має блочно–діагональну форму. При цьому одне власне значення дорівнює λ1 = 1,0448 два інших визначаються блоком другого порядку:

.

Відповідь: λ1 = 1,0448, λ2 = 3,5528, λ3 = 6,0701.

Точні значення: λ = [1,0448, 3,5528, 6,0701]t.

4.3. Засоби прискорення QR–алгоритму

Як було показано, процедура розкладу матриці А на множники Q і R досить витратна, тому бажано зменшити розмір послідовності подібних матриць An перед тим, як буде отримана їх блочно–діагональна структура.

На практиці матрицю А спочатку приводять до матриці Хессенберга, яка буде подібною матриці А. Матриця А має верхню форму Хессенберга, якщо аij = 0, при i > j + 1. Наприклад, верхня форма Хессенберга для матриці [6x6] має вигляд:

А =

Можна сподіватися, що при генерації з допомогою QR–алгоритму послідовності подібних матриць An через обнулення елементів нижньої діагоналі скоріше сформуються діагональні блоки розмірності 2х2.

При приведенні матриці А до верхньої форми Хессенберга обнулення елементів aij по стовпцям виконується шляхом еквівалентних перетворень типу А n + 1 = Q n + 1 - 1 А n Q n + 1, де Q n + 1 — матриця обертання Гівенса:

для якої

 та  (4.18)

Формули (4.18) і (4.16) відрізняються застосуванням ведучого елемента.

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

Приклад 4.6.

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

А = .

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

Q1 =

де .

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

A2 = Q - 1AQ1 = Q1tAQ1 = .

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

Q2 =

де .

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

A3 = Q2 - 1A2Q2 = Q2tA2Q2 = ,

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

Q3 =

де.

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

H = Q3 - 1A3Q3 = .

Для прискорення збіжності використовується також варіант QRалгоритму зі зсувом. Будується послідовність ортогональних матриць Qk і правих трикутних матриць Rk у відповідності з наступними рекурентними формулами:

Ak - PkI = QkRk, Ak + 1 = RkQk + рk I, k = 1,2,... (4.18)

де рk  константа.

Покажемо, що при цьому власні числа зберігаються, тобто це перетворення подібності. Дійсно,

Ak + 1 = Rk Qk + PkI = Qk - 1(Ak - Pk I) Qk + PkI = Qk - 1Ak Qk - Pk I + Pk I = Qk - 1Ak Qk.

4.4. Метод відбиття Хаусхолдера

Існує також різновид QR–алгоритму, в якому для отримання трикутної матриці R використовується не матриці обертання Гівенса, а метод відбиття Хаусхолдера (4.15), сутність якого полягає в наступному.

Матриця А приводиться до трикутної форми з допомогою матриці перетворення

(4.19)

де вектор W задовольняє умові W2W = ||W||2 = 1 Оскільки

p1 tp1 = (I - 2W W t)(I - 2WWt) = I - 4WW t + 4WWt WW t = I,

то p1 ортогональна матриця.

Застосовуючи перетворення подібності, отримуємо:

(4.20)

Нехай вектор W1 вибрано так, що

(4.21)

де

S =

Тоді подібна матриця набуде виду:

(4.22)

Впевнимося, що обраний вектор W відповідає нашим умовам. Дійсно,

.

Далі, позначаючи перший стовпець матриці А через а, знаходимо :

так що

(4.23)
 (4.24)

що підтверджує справедливість виразу (4.20).

Обираємо замість (4.21) наступний вектор

, (4.25)

де  і знаком ”^” помічено елементи матриці А2 (4.20), і аналогічно обчислюємо співвідношення для a22 і a12.

На основі формул типу (4.24) переконуємося, що елементи двох перших стовпців матриці (I - 2W2W2t)A2, які лежать нижче головної діагоналі, перетворюються в нуль. Продовжуючи цей процес з допомогою векторів Wi, які мають нулі в перших i - 1 позиціях, знаходимо :

(I - 2Wn - 1Wn - 1t)...(I - 2W1W1t)A = R, (4.26)
Q = (I - 2W1W1t)(I - 2W2W2t)... (I - Wn - 1Wn - 1t). (4.27)

Оскільки кожна окрема матриця I - 2WiWit ортогональна, то матриця Q буде також ортогональною матрицею. На відміну від перетворення Гівенса, яке обнулює один обраний елемент стовпця матриці на кроці обчислень, перетворення Хаусхолдера на кожному кроці перетворення обнулює всі необхідні елементи обраного стовпця матриці.

По отриманим R і Q будується із застосуванням процедури (4.13) нова подібна матриця і вся процедура повторюється. Як і раніше, якщо власні значення початкової матриці А різні, то генерована послідовність подібних матриць має границею верхню трикутну матрицю R, діагональні елементи якої уявляють собою власні значення матриці А, розташовані в порядку зростання їх модулів. Якщо матриця А має комплексні власні значення, то гранична матриця не є трикутною, а має діагональні блоки другого порядку, які відповідають комплексним власним значенням.

Слід зазначити, що структура формованої подібної матриці Ai визначається вибором вектора W. Для окремого випадку симетричних матриць перетворення Хаусхолдера використовується для приведення таких матриць до трьохдіагональної (а не трикутної) форми. Тоді відпадає необхідність генерації послідовності подібних матриць, як в QR–алгоритмі, оскільки власні значення трьохдіагональної матриці визначаються безпосередньо, наприклад, знаходженням коренів поліномів Штурма, які мають наступний вигляд:

,

де f0(λ) = 1, f1(λ) = a11 - λ; aii і bi = bi,i - 1 = bi - 1,i — діагональні і недіагональні елементи матриці.


 

А также другие работы, которые могут Вас заинтересовать

51366. Экономический анализ финансово-хозяйственной деятельности ООО «Адидас» 329 KB
  Организационная характеристика предприятия Экономический анализ финансово-хозяйственной деятельности предприятия Основные цели преддипломной практики: закрепление расширение углубление и систематизацию знаний полученных при изучении общепрофессиональных и специальных дисциплин на основе изучения деятельности предприятия отрасли; проведение системного анализа организации с целью выявления проблем управления и разработки мероприятий по их устранению; более глубоко освоить методы и приемы системного анализа; сбор и...
51368. Исследование начальной остойчивости плавучей полупогружной буровой установки 155 KB
  Ознакомление студентов с особенностями остойчивости плавучих полупогружных буровых установок (ППБУ) и их поведения на взволнованной поверхности моря, изучение основных положений теории и расчета, а также ознакомление с методикой постановки эксперимента по определению параметров начальной остойчивости плавучих технических средств для освоения шельфа.
51369. Двухфазная СМО с отказами 95.5 KB
  Для упрощения расчёта представим данную СМО как совокупность 2ух одноканальных. Т.к. в данной системе очередь не бесконечной длинны, то все расчёты будут не очень точны. Но главная цель проведения данных расчётов – это сравнение их результатов с результатами имитационной модели (программой). Для оценки соответствия результатов такой точности будет достаточно.
51371. РАБОТА С ОДНОМЕРНЫМИ МАССИВАМИ В ЯЗЫКЕ C 487.8 KB
  Варианты для задания 1 Array1. Дано целое число N (>0). Сформировать и вывести целочисленный массив размера N, содержащий N первых положительных нечетных чисел:
51372. РАБОТА С МАТРИЦАМИ В ЯЗЫКЕ C 120.29 KB
  В соответствии со своим вариантом для задачи 1 составить: Алгоритм решения задачи, в котором предусмотреть использование следующих функций: 1) функция формирования матрицы, предусмотреть формирование матрицы с клавиатуры и с помощью генератора псевдослучайных чисел;