QR-розклад матриці — представлення матриці у вигляді добутку унітарної та правої трикутної матриці.
Матриця A розміру m×n може бути представлена у вигляді
де Q — унітарна матриця розміру m×m, R — верхня трикутна матриця розміру m×n.
Також можливі представлення 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 обидві мають ортогональні стовпчики.
Обчислення
Розклад матриці може отримуватись за допомогою різних методів:
Використовуючи процес Грама — Шмідта
Розглянемо процес Грама — Шмідта застосований до стовпчиків матриці з повним стовпчиковим рангом, де (або у комплексному випадку).
Визначимо проєкцію вектора як:
тоді:
Тепер ми можемо виразити через ново обчислений ортонормальний базис:
де . Це можна записати у матричній формі:
де:
Приклад
Розглянемо декомпозицію
Згадаймо, що ортонормальна матриця має таку властивість
Тоді, ми можемо обчислити із застосувавши процес Грама — Шмідта так:
Отже, ми маємо
Використовуючи перетворення Хаусхолдера
Перетворення Хаусхолдера — це трансформація, яка приймає вектор і відбиває його від певної площини або гіперплощини. Ми можемо використати цю операцію для обчислення 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 без першого рядка і першого стовпчика), в результаті маємо матрицю Хаусхолдера Q′2. Зауважте, що Q′2 менше ніж 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-розкладом.
Див. також
Джерела
- Гантмахер Ф. Р. Теория матриц. — 5-е. — М: : Физматлит, 2010. — 559 с. — .(рос.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
QR rozklad matrici predstavlennya matrici u viglyadi dobutku unitarnoyi ta pravoyi trikutnoyi matrici Matricya A rozmiru m n mozhe buti predstavlena u viglyadi A Q R displaystyle A QR de Q unitarna matricya rozmiru m m R verhnya trikutna matricya rozmiru m n Takozh mozhlivi predstavlennya QL RQ ta LQ de L nizhnya trikutna matricya Dlya m n matrici A z m n nizhni m n ryadkiv m n verhnoyi trikutnoyi matrici usi nulovi tomu chasto buvaye korisno rozbiti R abo R i Q A Q R Q R 1 0 Q 1 Q 2 R 1 0 Q 1 R 1 displaystyle A QR Q begin bmatrix R 1 0 end bmatrix begin bmatrix Q 1 Q 2 end bmatrix begin bmatrix R 1 0 end bmatrix Q 1 R 1 de R1 ce n n verhnya trikutna matricya 0 ce m n n nulova matricya Q1 ce m n Q2 ce m m n i Q1 ta Q2 obidvi mayut ortogonalni stovpchiki ObchislennyaRozklad matrici mozhe otrimuvatis za dopomogoyu riznih metodiv Proces Grama Shmidta Peretvorennya Hausholdera Povorot Givensa Vikoristovuyuchi proces Grama Shmidta Rozglyanemo proces Grama Shmidta zastosovanij do stovpchikiv matrici A a 1 a n displaystyle A mathbf a 1 cdots mathbf a n z povnim stovpchikovim rangom de v w v w displaystyle langle mathbf v mathbf w rangle mathbf v top mathbf w abo v w v w displaystyle langle mathbf v mathbf w rangle mathbf v mathbf w u kompleksnomu vipadku Viznachimo proyekciyu vektora yak p r o j e a e a e e e displaystyle mathrm proj mathbf e mathbf a frac left langle mathbf e mathbf a right rangle left langle mathbf e mathbf e right rangle mathbf e todi u 1 a 1 e 1 u 1 u 1 u 2 a 2 p r o j u 1 a 2 e 2 u 2 u 2 u 3 a 3 p r o j u 1 a 3 p r o j u 2 a 3 e 3 u 3 u 3 u k a k j 1 k 1 p r o j u j a k e k u k u k displaystyle begin aligned mathbf u 1 amp mathbf a 1 amp mathbf e 1 amp mathbf u 1 over mathbf u 1 mathbf u 2 amp mathbf a 2 mathrm proj mathbf u 1 mathbf a 2 amp mathbf e 2 amp mathbf u 2 over mathbf u 2 mathbf u 3 amp mathbf a 3 mathrm proj mathbf u 1 mathbf a 3 mathrm proj mathbf u 2 mathbf a 3 amp mathbf e 3 amp mathbf u 3 over mathbf u 3 amp vdots amp amp vdots mathbf u k amp mathbf a k sum j 1 k 1 mathrm proj mathbf u j mathbf a k amp mathbf e k amp mathbf u k over mathbf u k end aligned Teper mi mozhemo viraziti a i displaystyle mathbf a i cherez novo obchislenij ortonormalnij bazis a 1 e 1 a 1 e 1 a 2 e 1 a 2 e 1 e 2 a 2 e 2 a 3 e 1 a 3 e 1 e 2 a 3 e 2 e 3 a 3 e 3 a k j 1 k e j a k e j displaystyle begin aligned mathbf a 1 amp langle mathbf e 1 mathbf a 1 rangle mathbf e 1 mathbf a 2 amp langle mathbf e 1 mathbf a 2 rangle mathbf e 1 langle mathbf e 2 mathbf a 2 rangle mathbf e 2 mathbf a 3 amp langle mathbf e 1 mathbf a 3 rangle mathbf e 1 langle mathbf e 2 mathbf a 3 rangle mathbf e 2 langle mathbf e 3 mathbf a 3 rangle mathbf e 3 amp vdots mathbf a k amp sum j 1 k langle mathbf e j mathbf a k rangle mathbf e j end aligned de e i a i u i displaystyle langle mathbf e i mathbf a i rangle mathbf u i Ce mozhna zapisati u matrichnij formi A Q R displaystyle A QR de Q e 1 e n and R e 1 a 1 e 1 a 2 e 1 a 3 0 e 2 a 2 e 2 a 3 0 0 e 3 a 3 displaystyle Q left mathbf e 1 cdots mathbf e n right qquad text and qquad R begin pmatrix langle mathbf e 1 mathbf a 1 rangle amp langle mathbf e 1 mathbf a 2 rangle amp langle mathbf e 1 mathbf a 3 rangle amp ldots 0 amp langle mathbf e 2 mathbf a 2 rangle amp langle mathbf e 2 mathbf a 3 rangle amp ldots 0 amp 0 amp langle mathbf e 3 mathbf a 3 rangle amp ldots vdots amp vdots amp vdots amp ddots end pmatrix Priklad Rozglyanemo dekompoziciyu A 12 51 4 6 167 68 4 24 41 displaystyle A begin pmatrix 12 amp 51 amp 4 6 amp 167 amp 68 4 amp 24 amp 41 end pmatrix Zgadajmo sho ortonormalna matricya Q displaystyle Q maye taku vlastivist Q T Q I displaystyle begin matrix Q T Q I end matrix Todi mi mozhemo obchisliti Q displaystyle Q iz zastosuvavshi proces Grama Shmidta tak U u 1 u 2 u 3 12 69 58 5 6 158 6 5 4 30 33 displaystyle U begin pmatrix mathbf u 1 amp mathbf u 2 amp mathbf u 3 end pmatrix begin pmatrix 12 amp 69 amp 58 5 6 amp 158 amp 6 5 4 amp 30 amp 33 end pmatrix Q u 1 u 1 u 2 u 2 u 3 u 3 6 7 69 175 58 175 3 7 158 175 6 175 2 7 6 35 33 35 displaystyle Q begin pmatrix frac mathbf u 1 mathbf u 1 amp frac mathbf u 2 mathbf u 2 amp frac mathbf u 3 mathbf u 3 end pmatrix begin pmatrix 6 7 amp 69 175 amp 58 175 3 7 amp 158 175 amp 6 175 2 7 amp 6 35 amp 33 35 end pmatrix Otzhe mi mayemo Q T A Q T Q R R displaystyle begin matrix Q T A Q T Q R R end matrix R Q T A 14 21 14 0 175 70 0 0 35 displaystyle begin matrix R Q T A end matrix begin pmatrix 14 amp 21 amp 14 0 amp 175 amp 70 0 amp 0 amp 35 end pmatrix Vikoristovuyuchi peretvorennya Hausholdera Vidbittya Haushaldera dlya QR rozkladu Cillyu ye znahodzhennya linijnogo peretvorennya sho perevodit vektor x displaystyle x u vektor takoyi zh dovzhini kolinearnij z e 1 displaystyle e 1 Mi mogli b vikoristati ortogonalnu proyekciyu Gram Shmidt ale ce bulo b chiselno nestabilno yaksho vektori x displaystyle x i e 1 displaystyle e 1 majzhe ortogonalni Natomist vidbittya Hausholdera viddzerkalyuye shodo punktirnoyi liniyi obranoyi tak shob rozsikati navpil kut mizh x displaystyle x i e 1 displaystyle e 1 Najbilshij mozhlivij kut u takij transformaciyi stanovit 45 gradusiv Peretvorennya Hausholdera ce transformaciya yaka prijmaye vektor i vidbivaye jogo vid pevnoyi ploshini abo giperploshini Mi mozhemo vikoristati cyu operaciyu dlya obchislennya QR rozkladu m na n matrici A displaystyle A z m n Q mozhna vikoristati shob vidbivati vektor takim chinom shob vsi koordinati okrim odniyeyi znikali Nehaj x displaystyle mathbf x bude dovilnim dijsnim m vimirnim vektorom stovpchikom A displaystyle A takim sho x a displaystyle mathbf x alpha dlya skalyara a Yaksho algoritm vtilyuyetsya iz vikoristannyam arifmetiki z ruhomoyu komoyu todi potribno nadati a znak protilezhnij do znaku k yi koordinati x displaystyle mathbf x de x k displaystyle x k ye opornoyu koordinatoyu pislya yakoyi usi elementi dorivnyuyut nulyu v kincevij verhnij trikutnij formi matrici A zadlya uniknennya vtrati rozryadiv U kompleksnomu vipadku vstanovit a e i arg x k x displaystyle alpha mathrm e mathrm i arg x k mathbf x i zaminit transponuvannya na spryazhene transponuvannya pid chas pobudovi Q dali Todi e 1 displaystyle mathbf e 1 ye vektorom 1 0 0 T ye Evklidovoyu normoyu i I displaystyle I ye m by m odinichnoyu matriceyu vstanovimo u x a e 1 displaystyle mathbf u mathbf x alpha mathbf e 1 v u u displaystyle mathbf v mathbf u over mathbf u Q I 2 v v T displaystyle Q I 2 mathbf v mathbf v T Abo yaksho A displaystyle A kompleksna Q I 1 w v v H displaystyle Q I 1 w mathbf v mathbf v H de w x H v v H x displaystyle w mathbf x H mathbf v mathbf mathbf v H mathbf x de x H displaystyle mathbf x H ce ermitovo spryazhenij x displaystyle mathbf x Q displaystyle Q ye m na m matricya Hausholdera i Q x a 0 0 T displaystyle Q mathbf x alpha 0 cdots 0 T Ce mozhna vikoristati shob postupovo transformuvati m na n matricyu A u verhnyu trikutnu formu Spershu mi mnozhimo A na matricyu Hausholdera Q1 yaku mi otrimali dlya pershogo stovpchika Ce nam daye matricyu Q1A z nulyami v pershomu stovpchiku okrim pershogo ryadka Q 1 A a 1 0 A 0 displaystyle Q 1 A begin bmatrix alpha 1 amp star amp dots amp star 0 amp amp amp vdots amp amp A amp 0 amp amp amp end bmatrix Ce mozhna povtoriti dlya A Q1A bez pershogo ryadka i pershogo stovpchika v rezultati mayemo matricyu Hausholdera Q 2 Zauvazhte sho Q 2 menshe nizh Q1 Oskilki mi bazhayemo shob vona diyala na Q1A a ne na A nam potribno rozshiriti yiyi dodavshi u verhnij livij kut 1 uzagalnyuyuchi Q k I k 1 0 0 Q k displaystyle Q k begin pmatrix I k 1 amp 0 0 amp Q k end pmatrix Pislya t displaystyle t iteracij cogo procesu t min m 1 n displaystyle t min m 1 n R Q t Q 2 Q 1 A displaystyle R Q t cdots Q 2 Q 1 A ye verhnoyu trikutnoyu matriceyu Otzhe z Q Q 1 T Q 2 T Q t T displaystyle Q Q 1 T Q 2 T cdots Q t T A Q R displaystyle A QR ye QR rozkladom A displaystyle A Cej metod maye bilshu chislovu stijkist nizh metod Grama Shmidta Nastupna tablicya navodit kilkist operacij na k mu kroci QR rozkladennya iz vikoristannyam peretvorennya Hausholdera pripuskayuchi kvadratnu matricyu rozmiru n Operaciya Kilkist na k mu kroci mnozhennya 2 n k 1 2 displaystyle 2 n k 1 2 dodavannya n k 1 2 n k 1 n k 2 displaystyle n k 1 2 n k 1 n k 2 dilennya 1 displaystyle 1 vzyattya korenya 1 displaystyle 1 Dodayuchi ci chisla dlya usih n 1 krokiv dlya kvadratnoyi matrici rozmiru n skladnist algoritmu kilkist mnozhen z ruhomoyu komoyu zadayetsya 2 3 n 3 n 2 1 3 n 2 O n 3 displaystyle frac 2 3 n 3 n 2 frac 1 3 n 2 O n 3 Priklad Obchislimo rozklad dlya A 12 51 4 6 167 68 4 24 41 displaystyle A begin pmatrix 12 amp 51 amp 4 6 amp 167 amp 68 4 amp 24 amp 41 end pmatrix Pershe nam potribno znajti vidbittya sho peretvoryuye pershij stovpchik matrici A vektor a 1 12 6 4 T displaystyle mathbf a 1 12 6 4 T u a 1 e 1 14 0 0 T displaystyle mathbf a 1 mathrm e 1 14 0 0 T Teper u x a e 1 displaystyle mathbf u mathbf x alpha mathbf e 1 i v u u displaystyle mathbf v mathbf u over mathbf u Tut a 14 displaystyle alpha 14 and x a 1 12 6 4 T displaystyle mathbf x mathbf a 1 12 6 4 T Otzhe u 2 6 4 T 2 1 3 2 T displaystyle mathbf u 2 6 4 T 2 1 3 2 T and v 1 14 1 3 2 T displaystyle mathbf v 1 over sqrt 14 1 3 2 T and then Q 1 I 2 14 14 1 3 2 1 3 2 displaystyle Q 1 I 2 over sqrt 14 sqrt 14 begin pmatrix 1 3 2 end pmatrix begin pmatrix 1 amp 3 amp 2 end pmatrix I 1 7 1 3 2 3 9 6 2 6 4 displaystyle I 1 over 7 begin pmatrix 1 amp 3 amp 2 3 amp 9 amp 6 2 amp 6 amp 4 end pmatrix 6 7 3 7 2 7 3 7 2 7 6 7 2 7 6 7 3 7 displaystyle begin pmatrix 6 7 amp 3 7 amp 2 7 3 7 amp 2 7 amp 6 7 2 7 amp 6 7 amp 3 7 end pmatrix Sposterezhemo sho Q 1 A 14 21 14 0 49 14 0 168 77 displaystyle Q 1 A begin pmatrix 14 amp 21 amp 14 0 amp 49 amp 14 0 amp 168 amp 77 end pmatrix Otzhe mi vzhe mayemo majzhe trikutnu matricyu Nam lishe potriben nul u charunci 3 2 Vizmemo minor 1 1 i znovu zastosuyemo proces do A M 11 49 14 168 77 displaystyle A M 11 begin pmatrix 49 amp 14 168 amp 77 end pmatrix Takim same metodom yak i vishe otrimuyemo matricyu peretvorennya Hausholdera Q 2 1 0 0 0 7 25 24 25 0 24 25 7 25 displaystyle Q 2 begin pmatrix 1 amp 0 amp 0 0 amp 7 25 amp 24 25 0 amp 24 25 amp 7 25 end pmatrix pislya rozshirennya Teper znajdemo Q Q 1 T Q 2 T 6 7 69 175 58 175 3 7 158 175 6 175 2 7 6 35 33 35 displaystyle Q Q 1 T Q 2 T begin pmatrix 6 7 amp 69 175 amp 58 175 3 7 amp 158 175 amp 6 175 2 7 amp 6 35 amp 33 35 end pmatrix Todi Q Q 1 T Q 2 T 0 8571 0 3943 0 3314 0 4286 0 9029 0 0343 0 2857 0 1714 0 9429 displaystyle Q Q 1 T Q 2 T begin pmatrix 0 8571 amp 0 3943 amp 0 3314 0 4286 amp 0 9029 amp 0 0343 0 2857 amp 0 1714 amp 0 9429 end pmatrix R Q 2 Q 1 A Q T A 14 21 14 0 175 70 0 0 35 displaystyle R Q 2 Q 1 A Q T A begin pmatrix 14 amp 21 amp 14 0 amp 175 amp 70 0 amp 0 amp 35 end pmatrix Matricya Q ye ortogonalnoyu i R ye verhnoyu trikutnoyu otzhe A QR i ye shukanim QR rozkladom Div takozhQR algoritmDzherelaGantmaher F R Teoriya matric 5 e M Fizmatlit 2010 559 s ISBN 5 9221 0524 8 ros