Також можливі представлення QL, RQ, та LQ (де L — нижня трикутна матриця).
Для m×n матриці A, з m ≥ n нижні (m−n) рядків m×n верхньої трикутної матриці усі нульові, тому часто буває корисно розбити R, або R і Q:
де R1 — це n×n верхня трикутна матриця, 0 — це (m − n)×n нульова матриця, Q1 — це m×n, Q2 — це m×(m − n) і Q1 та Q2 обидві мають ортогональні стовпчики.
Зміст
1Обчислення
1.1Використовуючи процес Грама — Шмідта
1.1.1Приклад
1.2Використовуючи перетворення Хаусхолдера
1.2.1Приклад
2Див. також
3Джерела
Обчислення
Розклад матриці може отримуватись за допомогою різних методів:
Розглянемо процес Грама — Шмідта застосований до стовпчиків матриці з повним стовпчиковим рангом, де (або у комплексному випадку).
Визначимо проєкцію вектора як:
тоді:
Тепер ми можемо виразити через ново обчислений ортонормальний базис:
де . Це можна записати у матричній формі:
де:
Приклад
Розглянемо декомпозицію
Згадаймо, що ортонормальна матриця має таку властивість
Тоді, ми можемо обчислити із застосувавши процес Грама — Шмідта так:
Отже, ми маємо
Використовуючи перетворення Хаусхолдера
Відбиття Хаусхалдера для QR-розкладу: Ціллю є знаходження лінійного перетворення, що переводить вектор у вектор такої ж довжини колінеарний з . Ми могли б використати ортогональну проєкцію (Грам-Шмідт), але це було б чисельно нестабільно якщо вектори і майже ортогональні. Натомість, відбиття Хаусхолдера віддзеркалює щодо пунктирної лінії (обраної так, щоб розсікати навпіл кут між і ). Найбільший можливий кут у такій трансформації становить 45 градусів.
Перетворення Хаусхолдера — це трансформація, яка приймає вектор і відбиває його від певної площини або гіперплощини. Ми можемо використати цю операцію для обчислення QR-розкладу m-на-n матриці з m ≥ n.
Q можна використати, щоб відбивати вектор таким чином, щоб всі координати окрім однієї зникали.
Нехай буде довільним дійсним m-вимірним вектором стовпчиком таким, що для скаляра α. Якщо алгоритм втілюється із використанням арифметики з рухомою комою, тоді потрібно надати α знак протилежний до знаку k-ї координати , де є опорною координатою після якої усі елементи дорівнюють нулю в кінцевій верхній трикутній формі матриці A, задля уникнення втрати розрядів. У комплексному випадку, встановіть
і замініть транспонування на спряжене транспонування під час побудови Q далі.
Тоді, є вектором (1,0,...,0)T, ||·|| є Евклідовою нормою і є m-by-m одиничною матрицею, встановимо
Це можна використати, щоб поступово трансформувати m-на-n матрицю A у верхню трикутну форму. Спершу ми множимо A на матрицю Хаусхолдера Q1 яку ми отримали для першого стовпчика. Це нам дає матрицю Q1A з нулями в першому стовпчику окрім першого рядка.
Це можна повторити для A′ (Q1A без першого рядка і першого стовпчика), в результаті маємо матрицю Хаусхолдера Q′2. Зауважте, що Q′2 менше ніж Q1. Оскільки ми бажаємо, щоб вона діяла на Q1A, а не на A′ нам потрібно розширити її додавши у верхній лівий кут 1, узагальнюючи:
Наступна таблиця наводить кількість операцій на k-му кроці QR-розкладення із використанням перетворення Хаусхолдера, припускаючи квадратну матрицю розміру n.
Операція
Кількість на k-му кроці
множення
додавання
ділення
взяття кореня
Додаючи ці числа для усіх n − 1 кроків (для квадратної матриці розміру n), складність алгоритму (кількість множень з рухомою комою) задається
Приклад
Обчислимо розклад для
Перше, нам потрібно знайти відбиття, що перетворює перший стовпчик матриці A, вектор , у
Тепер,
і
Тут,
and
Отже
and , and then
Спостережемо що:
Отже, ми вже маємо майже трикутну матрицю. Нам лише потрібен нуль у чарунці (3, 2).
Візьмемо мінор (1, 1) і знову застосуємо процес до
Таким саме методом як і вище, отримуємо матрицю перетворення Хаусхолдера
після розширення.
Тепер, знайдемо
Тоді
Матриця Q є ортогональною і R є верхньою трикутною, отже A = QR і є шуканим QR-розкладом.