QR-розклад матриці

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з QR розклад матриці)
Перейти до: навігація, пошук

QR-розклад матриці — представлення матриці у вигляді добутку унітарної та правої трикутної матриці.

Матриця A розміру m×n може бути представлена у вигляді

де Q — унітарна матриця розміру m×m, R — верхня трикутна матриця розміру m×n.

Також можливі представлення QL, RQ, та LQ (де L — нижня трикутна матриця).

Для m×n матриці A, з m ≥ n нижні (mn) рядків m×n верхньої трикутної матриці усі нульові, тому часто буває корисно розбити R, або R і Q:

де R1 — це n×n верхня трикутна матриця, 0 — це (m − nn нульова матриця, Q1 — це m×n, Q2 — це m×(m − n) і Q1 та Q2 обидві мають ортогональні стовпчики.

Обчислення[ред.ред. код]

Розклад матриці може отримуватись за допомогою різних методів:

Використовуючи процес Грама — Шмідта[ред.ред. код]

Розглянемо процес Грама — Шмідта застосований до стовпчиків матриці з повним стовпчиковим рангом, де (або у комплексному випадку).

Визначимо проекцію вектора як:

тоді:

Тепер ми можемо виразити через ново обчислений ортонормальний базис:

де . Це можна записати у матричній формі:

де:

Приклад[ред.ред. код]

Розглянемо декомпозицію

Згадаймо, що ортонормальна матриця має таку властивість

Тоді, ми можемо обчислити із застосувавши процес Грама — Шмідта так:

Отже, ми маємо

Використовуючи перетворення Хаусхолдера[ред.ред. код]

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

Перетворення Хаусхолдера — це трансформація, яка приймає вектор і відбиває його від певної площини або гіперплощини. Ми можемо використати цю операцію для обчислення QR-розкладу m-на-n матриці з m ≥ n.

Q можна використати, щоб відбивати вектор таким чином, щоб всі координати окрім однієї зникали.

Нехай буде довільним дійсним m-вимірним вектором стовпчиком таким, що для скаляра α. Якщо алгоритм втілюється із використанням арифметики з рухомою комою, тоді потрібно надати α знак протилежний до знаку k-ї координати , де є опорною координатою після якої усі елементи дорівнюють нулю в кінцевій верхній трикутній формі матриці A, задля уникнення втрати розрядів. У комплексному випадку, встановіть

і замініть транспонування на спряжене транспонування під час побудови Q далі.

Тоді, є вектором (1,0,...,0)T, ||·|| є Евклідовою нормою і є m-by-m одиничною матрицею, встановимо

Або, якщо комплексна

, де
де  — це ермітово-спряжений

є m-на-m матриця Хаусхолдера і

Це можна використати, щоб поступово трансформувати m-на-n матрицю A у верхню трикутну форму. Спершу ми множимо A на матрицю Хаусхолдера Q1 яку ми отримали для першого стовпчика. Це нам дає матрицю Q1A з нулями в першому стовпчику окрім першого рядка.

Це можна повторити для A′ (Q1A без першого рядка і першого стовпчика), в результаті маємо матрицю Хаусхолдера Q2. Зауважте, що Q2 менше ніж Q1. Оскільки ми бажаємо, щоб вона діяла на Q1A, а не на A′ нам потрібно розширити її додавши у верхній лівий кут 1, узагальнюючи:

Після ітерацій цього процесу, ,

є верхньою трикутною матрицею. Отже, з

є QR-розкладом .

Цей метод має більшу числову стійкість ніж метод Грама-Шмідта.

Наступна таблиця наводить кількість операцій на k-му кроці QR-розкладення із використанням перетворення Хаусхолдера, припускаючи квадратну матрицю розміру n.

Операція Кількість на k-му кроці
множення
додавання
ділення
взяття кореня

Додаючи ці числа для усіх n − 1 кроків (для квадратної матриці розміру n), складність алгоритму (кількість множень з рухомою комою) задається

Приклад[ред.ред. код]

Обчислимо розклад для

Перше, нам потрібно знайти відбиття, що перетворює перший стовпчик матриці A, вектор , у

Тепер,

і

Тут,

and

Отже

and , and then

Спостережемо що:

Отже, ми вже маємо майже трикутну матрицю. Нам лише потрібен нуль у чарунці (3, 2).

Візьмемо мінор (1, 1) і знову застосуємо процес до

Таким саме методом як і вище, отримуємо матрицю перетворення Хаусхолдера

після розширення.

Тепер, знайдемо

Тоді

Матриця Q є ортогональною і R є верхньою трикутною, отже A = QR і є шуканим QR-розкладом.

Джерела[ред.ред. код]