De behandelde Gram-Schmidt procedure, en de bijhorende relatie tussen een stelsel vectoren en een orthonormaal stelsel vectoren, kan ook worden gevangen in een matrixontbinding. We zullen deze ontbinding eerst als een stelling formuleren, en daarna laten zien hoe de bijbehorende matrices gevonden kunnen worden.
Als #A# een #(m \times n)#-matrix is met lineair onafhankelijke kolomvectoren, dan is deze matrix te schrijven als het product
\[A=Q\,R\]
waarbij #R# een #(m\times n)#-bovendriehoeksmatrix is en de kolommen van de #(m\times m)#-matrix #Q# een orthonormaal stelsel vormen. Deze schrijfwijze heet een QR-ontbinding van #A#.
De matrix #A = \matrix{3\\4}# heeft als QR-ontbinding
\[A =\left( \frac{1}{5}\matrix{3&4\\ 4&-3}\right)\, \matrix{5\\ 0}\]
Hierbij vormen de kolommen van #Q = \frac{1}{5}\matrix{3&4\\ 4&-3}# een orthonormaal stelsel en is de matrix #R = \matrix{5\\ 0}# bovendriehoeks.
De aanname dat de kolommen van \(A\) onafhankelijk zijn, heeft tot gevolg dat #m\ge n#. De kolommen zijn immers vectoren van de #m#-dimensionale vectorruimte #\mathbb{R}^m#.
Laat #A# een #(m\times n)#-matrix zijn met #n# onafhankelijke kolomvectoren. We geven de kolomvectoren van #A# aan met #\vec{a}_1,\ldots, \vec{a}_n#. Dit zijn vectoren uit #\mathbb{R}^m#. Met de Gram-Schmidt procedure kunnen we hieruit een orthonormale basis #\vec{q}_1,\ldots,\vec{q}_n# construeren voor het opspansel van #\vec{a}_1,\ldots, \vec{a}_n#.
We zullen nu deze orthonormale basis construeren en de gemaakte stappen vangen in elementaire matrices. Hierbij gebruiken we de volgende notatie:
- #D_{i,\lambda}# is de #(n\times n)#-diagonaalmatrix met #\lambda# op plaats #(i,i)# en verder enen op de diagonaal
- #E_{jk,\lambda}# (met #j\ne k#) is de #(n\times n)#-matrix die op de plaats #(j,k)# het getal #\lambda# heeft, op de diagonaal enen en verder overal nullen
Begin met de matrices #P_0 = A# en #S_0=I_n# (de identieke #(n\times n)#-matrix). Er geldt #A = P_0\, S_0#. We zullen nu iteratief matrices #P_i# en #S_i# uit #P_{i-1}# en #S_{i-1}# van dezelfde omvang construeren zodanig dat
- de kolommen van #P_i# steeds een tussenresultaat van de Gram-Schmidt procedure vormen en
- #S_i# steeds een bovendriehoeksmatrix is die vastlegt wat er gebeurd is met de kolommen van #P_0# om tot #P_i# te komen,
- #A = P_i\, S_i#.
De eerste stap van de procedure is het normaliseren van de kolomvector #\vec{a}_1# om #\vec{q}_1# te krijgen. Hier is #\vec{a}_1# niet de nulvector omdat het tot een stel lineair onafhankelijke vectoren behoort. Door de eerste vector #\vec{q}_1# met de norm van #\vec{a}_1# te vermenigvuldigen krijgen we de vector #\vec{a}_1# terug. In termen van matrices geeft dit \[ \begin{array}{rcl} A&=&\matrix{&&&\\\vec{a}_1&\vec{a}_2& \cdots &\vec{a}_n\\&&&}\\&&\phantom{xx}\color{blue}{\vec{a}_1,\ldots,\vec{a}_n\text{ zijn de kolommen van }A}\\&=&\matrix{&&&\\\vec{q}_1&\vec{a}_2&\cdots&\vec{a}_n\\&&&}\,\matrix{\norm{ \vec{a}_1}&0&\ldots&\ldots\\0&1&&\\\vdots&&\ddots&\\\vdots&&&1}\\&&\phantom{xx}\color{blue}{\vec{a}_1=\norm{\vec{a}_1}\cdot \vec{q}_1}\\&=&P_1\,S_1\\&&\phantom{xx}\color{blue}{P_1\text{ is de eerste factor, }S_1\text{ is de diagonaalmatrix }D_{1,\norm{\vec{a}_1}}}\end{array}\]
In de volgende stap van de Gram-Schmidt procedure krijgen we de vector #\vec{q}^*_2# door de vector #(\dotprod{\vec{a}_2}{\vec{q}_1})\,\vec{q}_1# af te trekken van de vector #\vec{a}_2#. Dit geeft \( \vec{a}_2 =\vec{q}^*_2+(\dotprod{\vec{a}_2}{\vec{q}_1})\vec{q}_1\). Voor de matrix met als kolommen \(\vec{q}_1,\vec{q}^*_2,\vec{a}_3, \ldots ,\vec{a}_n\) geeft dit de matrixontbinding\[\begin{array}{rcl}P_1&=&\matrix{&&&\\\vec{q}_1&\vec{q}^*_2&\vec{a}_3& \cdots &\vec{a}_n\\&&&}\, \matrix{1&(\dotprod{\vec{a}_2}{\vec{q}_1})&0&\cdots\\0&1&&\\\vdots&&\ddots&\\\vdots&&&1}\end{array}\] We zien dat de eerste matrix #P_2# van deze ontbinding al wat meer lijkt op de gewenste matrix #P#. De tweede matrix van de ontbinding is de elementaire matrix #E_{1,2,(\dotprod{\vec{a}_2}{\vec{q}_1})}#. Deze is bovendriehoeks en dus (zie LUP decompositie) is het product #S_2 = E_{1,2,(\dotprod{\vec{a}_2}{\vec{q}_1})}\, S_1# ook weer bovendriehoeks. We hebben nu de ontbinding\[A = P_1\,S_1 = P_2\, E_{1,2,(\dotprod{\vec{a}_2}{\vec{q}_1})}\,S_1 = P_2\,S_2\]
Zo gaan we door. We normaliseren de tweede vector zoals we de eerste vector genormaliseerd hebben. Dan krijgen we \[ P_2=\matrix{&&&\\\vec{q}_1&\vec{q}_2&\vec{a}_3& \cdots &\vec{a}_n\\&&&}\,D_{2,\norm{ \vec{a}_2}}\]
We laten #P_3# de eerste factor van deze ontbinding zijn en schrijven #S_3 = D_{2,\norm{\vec{a}_2}}\, S_2#, zodat de eerste twee kolommen van #P_3# een orthonormaal stelsel vormen, #S_3# bovendriehoeks is, en \[ A = P_3\,S_3\]Dit zetten we voort, en krijgen zo in het algemeen \[P_{i-1}=P_{i}\,E_{i}\phantom{x}\text{, }\phantom{xxx}S_i = E_i\, S_{i-1}\phantom{xxx}\text{ en }\phantom{xxx}A = P_i\, S_i \] waarbij de matrix #E_{i}# voor iedere #i# ofwel de diagonaalmatrix \( D_{k,\norm{\vec{a}_k}}\) voor een index #k\le n# is, ofwel een elementaire matrix van de vorm #E_{j,k,(\dotprod{\vec{a}_k}{\vec{q}_j})}# voor een tweetal indices #j,k# met #1\le j\lt k\le n# is. In elk geval is #E_i# dus een bovendriehoeksmatrix, zodat het product #S_i = E_i\, S_{i-1}# weer een bovendriehoeksmatrix is. We kunnen de vectoren #\vec{a}_k# immers altijd uitdrukken in lineaire combinaties van #\vec{q}_1,\ldots,\vec{q}_k#.
Omdat de kolommen #\vec{a}_1,\vec{a}_2, \cdots ,\vec{a}_n# van #A# lineair onafhankelijk zijn, eindigt het proces voor #k=n# met
- een #(m\times n)#-matrix #P_k# waarvan de kolommen een orthonormaal stelsel van #n# vectoren vormen in #\mathbb{R}^m#,
- een bovendriehoeksmatrix #S_k#,
- \(A = P_k\, S_k\).
We laten nu #Q# gelijk zijn aan de #(m\times n)#-matrix #P_n# aangevuld met #m-n# kolommen die een orthonormale basis vormen voor het orthogonale complement van het opspansel van de #n# kolommen van #P_n#. Met andere woorden, als we #B# de #(n\times (n-m))#-matrix laten zijn met als kolommen de basis van dit orthogonale complement, dan is #Q=\matrix{P&B}#.
Verder nemen we #R# gelijk aan de matrix #S_k# aangevuld met #m-n# nulrijen tot een #(m\times n)#-matrix, zodat #R = \matrix{S\\ 0}#, waarbij #0# de #((n-m)\times n)#-nulmatrix is. Dan is #Q# een #(m\times m)#-matrix waarvan de kolommen een orthonormale basis vormen van #\mathbb{R}^m#. Bovendien is #R# een #(m\times n)#-bovendriehoeksmatrix met de eigenschap dat \[A = P\, S = \matrix{P&B}\,\matrix{S\\ 0} = Q\, R\]
Hiermee is de stelling bewezen.
Later zullen we een vierkante matrix waarvan de kolommen een orthonormaal stelsel vormen orthogonaal noemen. Van zo'n matrix vormen ook de rijen een orthonormaal stelsel.
Vaak zijn de kolommen van #Q# precies de vectoren zoals deze door het Gram-Schmidt algoritme gevormd worden. Je kan echter ook andere orthonormale stelsels krijgen door de tekens van de vectoren te veranderen. De matrix #A = \matrix{3\\4}# heeft bijvoorbeeld twee QR-ontbindingen:
\[A =\left( \frac{1}{5}\matrix{3&4\\ 4&-3}\right)\, \matrix{5\\ 0}= \left(\frac{1}{5}\matrix{-3&4\\ -4&-3}\right)\, \matrix{-5\\ 0}\]
Met zulke tekenveranderingen kunnen we er voor zorgen dat de diagonaal van de matrix #R# uit positieve elementen bestaat. Als #m=n#, dan is, onder deze extra voorwaarde op de diagonaalelementen van #R#, de QR-ontbinding uniek.
Voor het bewijs hiervan hebben we enkele feiten nodig die we later zullen bewijzen als we meer weten over orthogonale matrices.
Stel dat #m=n#, zodat #A# een vierkante matrix is. Laat #P# de permutatiematrix bij de permutatie #[n,n-1,n-2,\ldots,1]# zijn. Dan voldoet #P# aan #P^2 = I_n# en #P^\top = P=P^{-1}#. Voer de QR-ontbinding op #PA^\top P# uit. Dit geeft de ontbinding #PA^\top P = Q_1\, R_1#, waarbij de kolommen van #Q_1# een orthonormaal stelsel vormen en #R_1# een bovendriehoeksmatrix is. Dan volgt #A = (P\,R_1^\top P)\, ( P\, Q_1^\top P )#. De matrix #R = P\,R_1^\top P# is een bovendriehoeksmatrix en de kolommen van de matrix #Q =P \, Q_1^\top P # vormen een orthonormaal stelsel. Daarom kunnen we #A = R\, Q# een RQ-ontbinding noemen.
Zoals we later zullen zien, is het maximale aantal onafhankelijke kolomvectoren van #A# gelijk aan de rang van #A#. De onafhankelijkheidsvoorwaarde van de stelling kan dus ook geformuleerd worden als: de rang van #A# is gelijk aan #n#.
Alle diagonaalelementen van #R# zijn ongelijk aan nul. Dit volgt uit de constructie van #R# als gegeven in het bewijs, waardoor alle diagonaalelementen van #R# lengtes van vectoren ongelijk aan #0# zijn. (Het is ook een consequentie van de eigenschappen van de rang van een matrix die we nog zullen bewijzen.)
Er zijn verschillende manieren om de QR-ontbinding van een matrix te vinden. We geven hieronder de methode die het bewijs van bovenstaande stelling volgt.
Voor een gegeven #(m\times n)#-matrix #A# waarvan de kolommen lineair onafhankelijk zijn, is een QR-decompositie te bepalen door de volgende uitbreiding van de Gram-Schmidt procedure:
Start met de matrices #P = A# en #S=I_n# (de identieke #(n\times n)#-matrix). Voer voor #k=1,\ldots,n# de volgende veranderingen uit:
- Bereken #\vec{q}^*_k= \vec{a}_k - \sum_{j=1}^{k-1}\vec(\dotprod{\vec{a}_k}{\vec{q}_j})\,\vec{q}_j#.
- Bereken de lengte #\norm{\vec{q}^*_k}#.
- Bereken #\vec{q}_k=\frac{1}{\norm{\vec{q}^*_k}}\vec{q}^*_k#.
- Vervang de #k#-de kolom van #P# door #\vec{q}_k#.
- Vervang #S# door #D_{k,\norm{\vec{q}_k^*}}\,E_{1,k,(\dotprod{\vec{a}_k}{\vec{q}_1})}\,E_{2,k,(\dotprod{\vec{a}_k}{\vec{q}_2})}\,\cdots\,E_{k-1,k,(\dotprod{\vec{a}_k}{\vec{q}_{k-1}})}\,S#.
Bepaal een #(m\times (m-n))#-matrix #B# waarvan de #m-n# kolommen een orthonormale basis vormen voor het orthogonale complement van het opspansel van de #n# kolommen van #P#.
Schrijf #Q = \matrix{P&B}# en #R = \matrix{S\\ 0}#, waarbij #0# de nulmatrix is met afmetingen #{(m-n)\times n}#.
Dan is #A = Q\, R# een QR-ontbinding van #A#.
Er is een alternatieve manier om de QR-ontbinding te berekenen waarbij we vermijden om de matrix #R# tijdens de Gram-Schmidt procedure op te bouwen. Vanwege de orthonormaliteit van de kolommen van #Q# die als in bovenstaande procedure tot stand komt, geldt dat #Q^{\top}Q=I_m#, waarbij #Q^\top# de getransponeerde van #Q# is. Dan is de bijbehorende matrix #R# te vinden dankzij de vergelijking #A=Q\, R#: \[R=I_m\, R=Q^{\top}\,Q\,R=Q^{\top}\,A\] We kunnen dus de matrix #R# vinden door #Q^{\top}\, A# uit te rekenen.
De beschreven stappen volgen de stappen in het bewijs van bovenstaande stelling QR-ontbinding. De stappen die voor #k=1,\ldots,n# beschreven worden, volgen de Gram-Schmidt procedure.
Voor vaste #k# commuteren de elementaire matrices #E_{j,k,(\dotprod{\vec{a}_k}{\vec{q}_j})}# voor #{j=1,\ldots,k-1}# onderling. Dit geeft de mogelijkheid in de Gram-Schmidt procedure om het aftrekken van scalaire veelvouden van #\vec{q}_j# van #\vec{a}_k# voor verschillende #j# in willekeurige volgorde uit te voeren.
Als #m=n#, dan zijn de matrices #Q# en #R# gelijk aan respectievelijk #P# en #S#. Het algoritme houdt dan al op na het doorlopen van de stappen voor #k=1,\ldots,n#, in de zin dat #A = P\, S# al een QR-ontbinding is.
Bepaal een QR-ontbinding van de #(3\times 3)#-matrix \[A= {{{1}\over{15}}\,\matrix{-15 & 0 & -10 \\ -42 & 33 & 11 \\ -6 & -6 & -52 \\ }} \]
#A=# #\left({{1}\over{15}}\,\matrix{-5 & -10 & 10 \\ -14 & 5 & -2 \\ -2 & -10 & -11 \\ } \right) \, \matrix{3 & -2 & 0 \\ 0 & 1 & 3 \\ 0 & 0 & 2 \\ }#
We beschrijven de stappen van de
uitgebreide Gram-Schmidt procedure in onderstaande tabel. De linker kolom bevat de veranderingen aan de kolommen van de matrix #A# om via Gram-Schmidt tot een matrix #Q# te komen waarvan de kolommen een orthonormaal stelsel vormen. De tweede kolom bevat de elementaire bewerking die nodig is om de vorige matrix uit de linker kolom terug te krijgen in termen van de matrix waarmee van rechts vermenigvuldigd moet worden.
De eerste regel laat zien hoe de eerste kolom van #A# genormaliseerd wordt. De tweede regel laat zien hoe bij de tweede kolom een veelvoud van de eerste wordt opgeteld om deze kolom loodrecht op de eerste te laten zijn. De bijbehorende bijdrage aan #R# is een matrix die alleen op de #(1,2)#-plaats van de identiteitsmatrix #I_3# afwijkt. En zo voorts.
\[ \begin{array}{rclcl}\text{van } A\text{ op weg naar }Q&\phantom{xx}&\text{bijdrage aan }R&\phantom{xx}&\text{opbouw van }R\\
\hline
\matrix{-{{1}\over{3}} & 0 & -{{2}\over{3}} \\ -{{14}\over{15}} & {{11}\over{5}} & {{11}\over{15}} \\ -{{2}\over{15}} & -{{2}\over{5}} & -{{52}\over{15}} \\ } && \matrix{3 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ } && \matrix{3 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ } \\ \matrix{-{{1}\over{3}} & -{{2}\over{3}} & -{{2}\over{3}} \\ -{{14}\over{15}} & {{1}\over{3}} & {{11}\over{15}} \\ -{{2}\over{15}} & -{{2}\over{3}} & -{{52}\over{15}} \\ } && \matrix{1 & -2 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ } && \matrix{3 & -2 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ } \\ \matrix{-{{1}\over{3}} & -{{2}\over{3}} & -{{2}\over{3}} \\ -{{14}\over{15}} & {{1}\over{3}} & {{11}\over{15}} \\ -{{2}\over{15}} & -{{2}\over{3}} & -{{52}\over{15}} \\ } && \matrix{1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ } && \matrix{3 & -2 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ } \\ \matrix{-{{1}\over{3}} & -{{2}\over{3}} & -{{2}\over{3}} \\ -{{14}\over{15}} & {{1}\over{3}} & {{11}\over{15}} \\ -{{2}\over{15}} & -{{2}\over{3}} & -{{52}\over{15}} \\ } && \matrix{1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ } && \matrix{3 & -2 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ } \\ \matrix{-{{1}\over{3}} & -{{2}\over{3}} & {{4}\over{3}} \\ -{{14}\over{15}} & {{1}\over{3}} & -{{4}\over{15}} \\ -{{2}\over{15}} & -{{2}\over{3}} & -{{22}\over{15}} \\ } && \matrix{1 & 0 & 0 \\ 0 & 1 & 3 \\ 0 & 0 & 1 \\ } && \matrix{3 & -2 & 0 \\ 0 & 1 & 3 \\ 0 & 0 & 1 \\ } \\ \matrix{-{{1}\over{3}} & -{{2}\over{3}} & {{2}\over{3}} \\ -{{14}\over{15}} & {{1}\over{3}} & -{{2}\over{15}} \\ -{{2}\over{15}} & -{{2}\over{3}} & -{{11}\over{15}} \\ } && \matrix{1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 2 \\ } && \matrix{3 & -2 & 0 \\ 0 & 1 & 3 \\ 0 & 0 & 2 \\ } \end{array}\] De matrix #Q# staat onderaan de linker kolom: \[Q = {{1}\over{15}}\,\matrix{-5 & -10 & 10 \\ -14 & 5 & -2 \\ -2 & -10 & -11 \\ }\] De matrix #R# is het product van de matrices in de middenkolom in de omgekeerde volgorde; de eerste regel bevat de meest rechtse factor en de laatste regel de meest linkse factor. De rechter kolom bevat de producten van de bijdragen aan #R# tot en met de betreffende regel. Het resultaat staat rechtsonder: \[R = \matrix{3 & -2 & 0 \\ 0 & 1 & 3 \\ 0 & 0 & 2 \\ }\] Zo vinden we \[ A = {{1}\over{15}}\,\matrix{-5 & -10 & 10 \\ -14 & 5 & -2 \\ -2 & -10 & -11 \\ }\, \matrix{3 & -2 & 0 \\ 0 & 1 & 3 \\ 0 & 0 & 2 \\ } \]
Gram-Schmidt in matrixvorm
