Matematyka.pl

Dla danego wektora \(\displaystyle{ \vec{w} \in \RR^{m} }\) o normie \(\displaystyle{ \parallel \vec{w}\parallel_{2} = \sqrt{\vec{w}^{T}\vec{w}} }\), odbicie (macierz) Hauseholdera zdefiniowane jest jako

\(\displaystyle{ H = I - 2\vec{w}\vec{w}^{T}. }\)

Zauważmy, że

\(\displaystyle{ H\vec{x} = (I - 2\vec{w}\vec{w}^{T})\vec{x} = \vec{x}- 2(\vec{w^{T}}\vec{x})\vec{w}.}\)

Stąd wynika, że \(\displaystyle{ (\vec{w}^{T}\vec{x})\vec{w} = \langle \vec{x}, \vec{w}\rangle _{2}\vec{w} }\) jest rzutem prostopadłym \(\displaystyle{ \vec{x}}\) na kierunek wektora \(\displaystyle{ \vec{w}. }\)

\(\displaystyle{ H\vec{x} }\) jest odbiciem lustrzanym wektora \(\displaystyle{ \vec{x} }\) względem płaszczyzny wymiaru \(\displaystyle{ m-1 - }\) prostopadłej do \(\displaystyle{ \vec{w}. }\)

Odbicia Hauseholdera są przekształceniami nieosobliwymi, spełniającymi:

\(\displaystyle{ H^{-1} = H = H^{T}, }\)

\(\displaystyle{ H^2 = (I - 2\vec{w}\vec{w}^{T})^2 = I -4\vec{w}\vec{w}^{T} + 4\vec{w}(\vec{w}^{T}\vec{w})\vec{w}^{T} = I }\)

i

\(\displaystyle{ H^{T} = (I - 2\vec{w}\vec{w}^{T})^{T} = I - 2(\vec{w} ^{T})^{T} \vec{w}^{T} = H.}\)

W szczególności \(\displaystyle{ H }\) jest więc przekształceniem ortogonalnym \(\displaystyle{ H^{-1}=H^{T} }\)- nie zmienia długości wektora.

Odbić Hauseholdera można użyć dla rozkładu macierzy \(\displaystyle{ A\in \RR^{m\times n} }\) na iloczyn ortogonalno - trójkątny.

Idea algorytmu jest następująca:

Wybieramy pierwsze odbicie Hauseholdera \(\displaystyle{ H_{1} }\) tak aby przekształcało pierwszy wektor-kolumnę macierzy \(\displaystyle{ A }\) na kierunek \(\displaystyle{ \vec{e}_{1}. }\).

Efektem pomnożenia macierzy \(\displaystyle{ A }\) z lewej strony macierzy \(\displaystyle{ A }\) przez \(\displaystyle{ H_{1} }\) będzie macierz

\(\displaystyle{ A^{(1)} = (\vec{a}^{(1)}_{1}, \ \ ... \ \ \vec{a}^{(n)}_{n} ) = (H_{1}\vec{a}^{(1)}_{1}, \ \ ...,\ \ H_{1}\vec{a}^{(n)}_{n}),}\)

w której pierwsza kolumna \(\displaystyle{ \vec{a}^{(1)}_{1} }\) ma niezerową tylko pierwszą wspóółrzędną.

W następnym kroku wybieramy drugie przekształcenie Hausoholdera \(\displaystyle{ H_{2} }\) wymiaru \(\displaystyle{ m-1 }\) tak, aby przeprowadzało

wektor \(\displaystyle{ (a^{(1)}_{1,2})_{m=2}^{m} }\) na kierunek pierwszego wersora w \(\displaystyle{ \RR^{m-1}}\)

Pomnożenie macierzy \(\displaystyle{ A^{1}}\) z lewej strony przez \(\displaystyle{ H_{2} }\) spowoduje teraz wyzerowanie drugiej kolumny macierzy pod elementem \(\displaystyle{ a^{(1)}_{2,2} }\) , przy czym pierwszy wiersz i pierwsza kolumna pozostaną niezmienione.

Postępując tak dalej \(\displaystyle{ n - }\) razy ( albo \(\displaystyle{ n-1 }\) razy, gdy \(\displaystyle{ m=n, }\)) otrzymujemy

\(\displaystyle{ H_{n}H_{n-1}\ \ ... \ \ H_{2}H_{1} A = R, }\)

gdzie \(\displaystyle{ R }\) jest uogólnioną macierzą trójkątną górną, tzn \(\displaystyle{ r_{i,j} = 0 }\) dla \(\displaystyle{ i>j. }\)

Podstawiając \(\displaystyle{ Q = H_{1}H_{2} \ \ ...\ \ H_{n} }\) dostajemy rozkład macierzy na iloczyn ortogonalno-trójkątny.

\(\displaystyle{ A = Q\cdot R.}\)

Rzeczywiście, macierz \(\displaystyle{ Q^{\times m} }\) jest ortogonalna, bo

\(\displaystyle{ Q^{-1} = (H_{1}H_{2} \ \ ... \ \ H_{n})^{-1} = H^{-1}_{n} \ \ ... \ \ H^{-1}_{2}H^{-1}_{1} = H^{T}_{n} \ \ ... \ \ H^{T}_{2}H^{T}_{1} = (H_{1}H_{2} \ \ ... \ \ H_{n} )^{T} = Q^{T}. }\)

Programy MATLAB i OCTAVE mają wbudowany program rozkładu macierzy \(\displaystyle{ A }\) na iloczyn ortogonalno-trójkątny.

Wywołanie programu:

\(\displaystyle{ [Q \ \ R ] = qr(A). }\)

Implementacji w języku MATLAB tego ekonomicznego programu dokonał Gilbert W. Stewart przy wspólpracy Cleve Barry Molera.

Przykład
Sprawdzenie

Wg mnie nie pokazałeś tutaj najważniejszego czyli jak efektywnie mnożyć macierz \(\displaystyle{ A}\) przez macierze odbić \(\displaystyle{ H}\)
W przypadku rozkładu \(\displaystyle{ A=QR}\) wystarczą lewostronne mnożenia
Te mnożenia da się wykonać tańszym kosztem niż standardowe mnożenie i to tańszym zarówno czasowo jak i pamięciowo
Złożoność czasowa mnożenia przez macierz odbicia będzie chyba wynosić \(\displaystyle{ O\left( m \cdot n\right) }\)
a pamięciowa chyba \(\displaystyle{ O\left( n\right) }\) bo nie trzeba pamiętać całej macierzy H a co najwyżej jedną z jej kolumn

Uwzględniając obecność zerowych elementów w wektorze \(\displaystyle{ \vec{u}_{k} }\) - przejście od macierzy \(\displaystyle{ A^{(k-1)} }\) do \(\displaystyle{

A^{(k)} }\) kosztuje rzędu \(\displaystyle{ 4(m-k+1)(n-k) }\) operacji arytmetycznych i obliczenia jednego pierwiastka kwadratowego.

Cały rozkład \(\displaystyle{ A=Q\cdot R }\) kosztuje (dla dużych \(\displaystyle{ m, n }\))

\(\displaystyle{ \sum_{k=1}^{n} 4(m-k+1)(n-k) \approx \frac{4}{3}n^3 + 2n^2(m- n) = 2n^2\left( m- \frac{n}{3}\right) }\)

operacji arytmetycznych i \(\displaystyle{ n }\) pierwiastków kwadratowych.

Zauważmy, że w przypadku \(\displaystyle{ m=n }\) - dla kwadratowego układu równań koszt ten wynosi \(\displaystyle{ \frac{4}{3}n^3 }\) i jest dwa razy większy od kosztu eliminacji Gaussa.

Chciałem pokazać w jaki sposób odbicia Householdera można stosować do rozkładu ortogonalno- trójkątnego \(\displaystyle{ QR.}\)

Nie miałem na celu popisywania się algorytmem bardziej oszczędnym, szybszym i jego opisem, który stosowany jest na przykład w programach MATLAB I OCTAVE. Wspomniałem tylko, że ekonomiczne jego implementacje zostały opracowane między innymi przez dwóch amerykańskich matematyków - numeryków.

Mogę służyć tymi implementacjami.

Zatem twoje wypociny niczym nie różnią się od tego co można znaleźć w sieci

Ale kto powiedział, że powinny się różnić?

JK

Tak tylko że takie mnożenie nie dość że jest nieefektywne gdybym chciał je zaprogramować to i zajmuje zbyt dużo czasu
oraz marnuje dużo papieru gdybym chciał samemu na kartce zapisać ten rozkład QR
On nie napisał niczego nowego bo to co tutaj napisał łatwo w sieci znaleźć
Podał jakie programy matematyczne mają gotowce ale do samego rozkładu QR nie będę ściągał kilkugigabajtowego Octave
ani kupował Matlaba

Poza tym jaki jest sens kopiować wiadomości z sieci nie dodając nic od siebie

Odbicia Hausoldera i opis algorytmu, \(\displaystyle{ Q R }\), który przedstawiłem nie znajdziemy w internecie. Są częścią moich "wypocin" wchodzących w zakres wykładów i zajęć laboratoryjnych z Metod Numerycznych, które prowadziłem ze studentami Politechniki Wrocławskiej i w Kolegium Karkonoskim w Jeleniej Górze.
Tak jak i pozostałe zagadnienia numeryczne, które miałem przyjemność przedstawić na tym forum.

No dobra nie wczytałem się dobrze w treść tego wpisu i trochę zbyt negatywnie byłem do niego nastawiony
Nadal jednak nie widzę jakie składowe posiada wektor w
w mnożeniach przez kolejne macierze odbić \(\displaystyle{ H_{1},H_{2},\cdots}\)

Możliwe że oczekiwałem czegoś podobnego do tego co Janusz napisał w tym wątku
algebra-liniowa-f32/rozklad-qr-t443576.html#p5596899