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 — діагональні і недіагональні елементи матриці.


 

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

11610. Работа с таблицами в MS Word’2000/2003 116.5 KB
  Лабораторная работа № 5 Тема: Работа с таблицами в MS Word’2000/2003. Цель работы: Освоить основные приемы создания редактирования и форматирования таблиц в документах текстового процессора MS Word’2000/2003. Содержание работы: Создать таблицу Отчетная ведомость по компью
11611. Графические возможности MS Word’2000/2003 139 KB
  Лабораторная работа № 6 Тема: Графические возможности MS Word’2000/2003.. Цель работы: Освоить основные приемы создания редактирования и форматирования графических объектов в документах текстового процессора MS Word’2000/2003. Содержание работы: Задание: Создать бланк фирмы п...
11612. Оформление математических формул в документах MS Word’2000/2003 99 KB
  Лабораторная работа № 7 Тема: Оформление математических формул в документах MS Word’2000/2003. Цель работы: Освоить основные приемы создания и форматирования математических формул в текстовых документах MS Word’2000/2003. Содержание работы: Освоение...
11613. Работа с большим (структурированным) документом MS Word’2000/2003 138.5 KB
  Лабораторная работа № 8 Тема: Работа с большим структурированным документом MS Word’2000/2003 Цель работы: Освоить основные приемы оформления структурированного документа в MS Word’2000/2003. Содержание работы: Создание структурированного документа. Оформление структ
11614. Решение задач в MatLab 324.86 KB
  Лабораторная работа №2. Решение задач в MatLab Цель лабораторной работы – закрепление практических навыков решения задач в среде математического пакета MatLab необходимых для выполнения лабораторных работ по дисциплине ТИПиС. Этап I. Решение уравнений в пакете MatLa...
11615. Создание собственных функций на MatLa 147.39 KB
  Создание собственных функций Необходимо создать программу на MatLab. При этом все операции с матрицами должны производиться без использования стандартных функций. Создание функции сложения матриц: function C=addmAB d1=sizeA; d2=sizeB; if d11==d21||d12==d22 n=d11; m=d12; ...
11616. ПЕРЕХОДНЫЕ ПРОЦЕССЫ В ЛИНЕЙНЫХ ЭЛЕКТРИЧЕСКИХ ЦЕПЯХ С СОСРЕДОТОЧЕННЫМИ ПАРАМЕТРАМИ 2.14 MB
  Лабораторная работа №7 ПЕРЕХОДНЫЕ ПРОЦЕССЫ В ЛИНЕЙНЫХ ЭЛЕКТРИЧЕСКИХ ЦЕПЯХ С СОСРЕДОТОЧЕННЫМИ ПАРАМЕТРАМИ Целью работы является исследование переходных процессов в линейных электрических цепях содержащих сопротивления индуктивность и емкость при действии и...
11617. Изучение рентгеновских трубок и аппаратов 629.5 KB
  ЛАБОРАТОРНАЯ РАБОТА №1. Изучение рентгеновских трубок и аппаратов. РЕНТГЕНОВЧСКИЕ ТРУБКИ. Рентгеновская трубка является источником рентгеновских лучей возникающих в ней в результате взаимодействия быстро летящих электронов с атомами анода установленного...
11618. Мерология. Лабораторный практикум 1.36 MB
  Мерология. Лабораторный практикум Учебнометодическое пособие для студентов приборостроительного факультета Лабораторный практикум предназначен для использования в высших учебных заведениях при подготовке инженеров по специальности Метрология стандартизация и...