QR-алгоритм

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

QR-алгоритм — це чисельний метод у лінійній алгебрі, призначений для розв'язування повної задачі власних значень, тобто відшукання всіх власних значень і власних векторів матриці. Розробили в кінці 1950-х років незалежно В. М. Кублановська і Джон Френсіс[en].

Алгоритм

[ред. | ред. код]

Нехай A — дійсна матриця, для якої ми хочемо знайти власні числа і вектори. Поклавши A0=A. на k-му кроці (починаючи від k = 0) обчислимо QR-розклад Ak=QkRk, де Qk — ортогональна матриця (тобто QkT = Qk−1), а Rk — верхня трикутна матриця. Потім ми визначаємо Ak+1 = RkQk.

Зауважимо, що

тобто всі матриці Ak є подібними, тобто їхні власні значення рівні.

Нехай усі діагональні мінори матриці A не вироджені. Тоді послідовність матриць Ak при збігається за формою до клітинного правого трикутного вигляду, відповідного клітинам з однаковими за модулем власними значеннями.[1]

Для того, щоб отримати власні вектори матриці, потрібно перемножити всі матриці Qk.

Алгоритм вважається обчислювально стійким, оскільки проводиться ортогональними перетвореннями подібності.

Доказ для симетричної додатноозначеної матриці

[ред. | ред. код]

Будемо вважати, що власні числа додатноозначеної матриці A впорядковано за спаданням:

Нехай

а S — матриця, складена зі власних векторів матриці A. Тоді, матрицю A можна записати у вигляді спектрального розкладу

Знайдемо вираз для степенів початкової матриці через матриці Qk і Rk. З одного боку, за визначенням QR-алгоритму:

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

Увівши такі позначення:

маємо

З іншого боку:

Прирівнявши праві частини останніх двох формул, отримаємо:

Припустимо, що існує LU-розклад матриці ST:

тоді

Помножимо праворуч на обернену до U матрицю, а потім — на обернену до Λk:

Можна показати, що

При без обмеження загальності можна вважати, що на діагоналі матриці L стоять одиниці, тому

Позначимо

причому матриця Pk є верхньотрикутною, як добуток верхньотрикутних і діагональних матриць.

Таким чином, ми довели, що

.

З єдиності QR-розкладу випливає, що якщо добуток ортогональної і трикутної матриці збігається до ортогональної матриці, то трикутна матриця збігається до одиничної матриці. Зі сказаного випливає, що

Тобто матриці Sk збігаються до матриці власних векторів матриці A.

Оскільки

то

Переходячи до границі, отримаємо:

Отже, ми довели, що QR-алгоритм дозволяє розв'язати повну проблему власних значень для симетричної додатноозначеної матриці.

Реалізація QR-алгоритму

[ред. | ред. код]

За певних умов послідовність матриць збігається до трикутної матриці, розкладу Шура матриці . В цьому випадку власні числа трикутної матриці розташовуються на її діагоналі, і задача знаходження власних чисел вважається розв'язаною. У тестах на збіжність не практично вимагати точних нулів у нульовій частині матриці, але можна скористатися теоремою Гершгоріна про кола[en], що задає межі помилок.

У початковому стані матриці (без додаткових перетворень) вартість ітерацій відносно висока. Вартість алгоритму можна зменшити, спочатку звівши матрицю до форми верхньої матриці Гессенберга (вартість отримання якої методом, заснованим на перетворенні Хаусхолдера, оцінюється як арифметичних операцій), і потім скориставшись скінченною послідовністю ортогональних перетворень подібності. Цей алгоритм нагадує двобічну QR-декомпозицію. (У звичайній QR-декомпозиції матриця відображень Хаусхолдера множиться на початкову тільки зліва, тоді як у разі використання форми Хессенберга матриця відображень множиться на початкову і зліва, і справа.) Знаходження QR-декомпозиції верхньої матриці Хессенберга оцінюється як арифметичних операцій. Оскільки форма матриці Хессенберга майже верхньотрикутна (у ній тільки один піддіагональний елемент не дорівнює нулю), вдається зразу знизити число ітерацій необхідних для збігання QR-алгоритму.

У випадку, якщо початкова матриця симетрична, верхня матриця Хессенберга також симетрична і тому є тридіагональною. Цю ж властивість має вся послідовність матриць . У цьому випадку вартість процедури оцінюється як арифметичних операцій з використанням методу, заснованого на перетворенні Хаусхолдера. Знаходження QR-розкладу симетричної тридіагональної матриці оцінюється як операцій.

Швидкість збіжності залежить від ступеня розділення власних чисел, і в практичній реалізації в явному або неявному вигляді використовуються «зсуви» для посилення розділення власних чисел і для прискорення збіжності. У типовому вигляді для симетричних матриць QR-алгоритм точно знаходить одне власне число (зменшуючи розмірність матриці) за одну або дві ітерації, що робить цей підхід як ефективним, так і надійним.

Реалізація QR-алгоритму в неявному вигляді

[ред. | ред. код]

У сучасній обчислювальній практиці QR-алгоритм реалізують із використанням його неявної версії, що спрощує додавання множинних «зсувів». Початково матриця зводиться до форми верхньої матриці Хессенберга , так само як і в явній версії. Потім, на кожному кроці перша колонка перетворюється через малорозмірне перетворення подоби Хаусхолдера до першої колонки (або ), де  — це поліном степеня , який визначає стратегію «зсувів» (зазвичай , де і  — це два власних числа залишкової підматриці розміру 2х2, це так званий неявний подвійний зсув). Потім виконують послідовні перетворення Хаусхолдера розмірності з метою повернути робочу матрицю до форми верхньої матриці Хессенберга.

Примітки

[ред. | ред. код]
  1. Численные методы / Н. С. Бахвалов, Н. П. Жидков, Г. М. Кобельков. — 3-е изд. — М : БИНОМ, Лаборатория знаний, 2004. — С. 321. — ISBN 5-94774-175-X.

Посилання

[ред. | ред. код]