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-розкладом.

ДжерелаРедагувати