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


 

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

25585. Основные направления в отечественной психологии дореволюционного периода 28 KB
  основные направления в отечественной психологии дореволюционного периода. рассмотрение исторических и социальных изменений с точки зрения человека его практической пользы а также преобладание нравственных этических проблем в российской психологии. Главными её выразителями были университетские профессора психологии и философии отстаивающие идею субстанциональности психики её независимости от материального мира и проповедующие схоластические описательные методы её постижения. Бурное развитие естествознания в России подготовило почву для...
25586. Развитие прикладных отраслей в отечественной психологии в довоенные период 28 KB
  развитие прикладных отраслей в отечественной психологии в довоенные период. Одним из направлений прикладной психологии переживавшим в 2030е гг. Очевидно что государство диктатуры пролетариата каким изначально являлась послереволюционная Россия не могло не уделять серьезного внимания проблемам руководства управления человеческими ресурсами различным формам воздействия на человека включая и психологическое воздействие Таким образом в результате развития психотехнического движения был накоплен разнообразный и богатый опыт...
25587. Становление понятийного аппарата психологии как предмет истории психологии 27.5 KB
  Его нельзя смешивать с предметом самой психологии как науки. История же психологии описывает и объясняет как эти факты и законы открывались порой в мучительных поисках истины человеческому уму. Задача истории психологии: Задачей истории психологии является анализ возникновения и дальнейшего развития научных знаний о психике.
25588. Основные категории психологии в их исторической перспективе 30.5 KB
  Субъект личность индивид Это к Рубинштейну или куда Человека как субъект деятельности. Человек субъект 3х видов деятельности по Рубинштейну: работа игра учеба. Ананьев выделяет общение как вид деятельности. Игру рассматривал как производную от ведущего типа деятельности.
25589. Принципы отечественной психологии в их истории и развитии 36 KB
  Принцип отражения. Принцип развития. Выявлен принцип гетерохронности психики.
25590. Основные проблемы психологии и способы их решения в истории психологии 41 KB
  Значение и актуальные задачи психологической историографии Зачем мы изучаем историю психологии и действительно Идеологическая функция Некоторые работы служат основой для материалистических и идеологических школ мыслей Гносеологическая функция Нам важна роль психологии и ее истории в становление научной картины мира Функция междисциплинарной связи История психологии развивалась в тесной связи с другими науками вспомните астрономию Кумулятивная функция Накопительная функция. Память науки – это сбережение преумножение информации и...
25591. Основные способы изложения истории психологии 32 KB
  Основные способы изложения истории психологии Выделяют несколько подходов к изучению истории психологии. Хронологический подход – для каждого конкретного момента существует характерная атмосфера мнений которая воздействует на исследователя. Персонологический подход через характеристику научных взглядов мыслителей прошлого. В основе этого подхода лежит идея о том что история делается великими людьми Карлейль.
25592. Значение и актуальные задачи психологической историографии 27 KB
  Память науки – это сбережение преумножение информации и знаний Прогностическая функция Прогноз основан на предыдущем опыте Прагматическая функция В какой мере психология имеет потенцию для решения прикладных задач в области бизнеса медицины образования начало в 70е годы сейчас активно развивается Мировоззренческая функция Представление об окружающем мире и отношение к нему Аксиологическая Изучение истории психологии помогает психологам формировать оценочные суждения строить шкалу оценки новых фактов и теорий знание прошлого –...
25593. Возникновение эволюционных идей в древности 28 KB
  своими взглядами на возникновение и развитие животных в наивной и фантастической форме высказывает идею эволюции. По мнению этого древнегреческого мыслителя путь развития животных представлен четырьмя периодами. В последний период происходит дифференциация полов и возникновение животных и людей путем размножения. Развитие животных возникает по необходимости.