Lineaire Algebra – Orthogonaliteit en kleinste kwadraten – Het Gram-Schmidt proces

Voor het berekenen van een orthogonale projectie van een vector \(\mathbf{y}\) op een deelruimte \(W\) van \(\mathbb{R}^n\) is een orthogonale basis \(\{\mathbf{v}_1,\ldots,\mathbf{v}_p\}\) zeer gewenst. De orthogonale projectie is dan gelijk aan de som van de orthogonale projecties langs de (orthogonale) basisvectoren:

\[\text{proj}_W\mathbf{y}=\left(\frac{\mathbf{y}\cdot\mathbf{v}_1}{\mathbf{v}_1\cdot\mathbf{v}_1}\right)\mathbf{v}_1+\cdots+ \left(\frac{\mathbf{y}\cdot\mathbf{v}_p}{\mathbf{v}_p\cdot\mathbf{v}_p}\right)\mathbf{v}_p.\]

Een interessante vraag is nu: hoe kunnen we een orthogonale basis construeren als we een willekeurige (niet-orthogonale) basis van \(W\) kennen? Hiervoor dient het orthogonaliseringsproces van Gram-Schmidt:

Stelling: Stel dat \(\{\mathbf{x}_1,\ldots,\mathbf{x}_p\}\) een willekeurige basis van een deelruimte \(W\) van \(\mathbb{R}^n\) is. Definieer dan:

\begin{align*} \mathbf{v}_1&=\mathbf{x}_1\\[2.5mm] \mathbf{v}_2&=\mathbf{x}_2-\left(\frac{\mathbf{x}_2\cdot\mathbf{v}_1}{\mathbf{v}_1\cdot\mathbf{v}_1}\right)\mathbf{v}_1\\[2.5mm] \mathbf{v}_3&=\mathbf{x}_3-\left(\frac{\mathbf{x}_3\cdot\mathbf{v}_1}{\mathbf{v}_1\cdot\mathbf{v}_1}\right)\mathbf{v}_1 -\left(\frac{\mathbf{x}_3\cdot\mathbf{v}_2}{\mathbf{v}_2\cdot\mathbf{v}_2}\right)\mathbf{v}_2\\[2.5mm] &\;\;\vdots\\[2.5mm] \mathbf{v}_p&=\mathbf{x}_p-\left(\frac{\mathbf{x}_p\cdot\mathbf{v}_1}{\mathbf{v}_1\cdot\mathbf{v}_1}\right)\mathbf{v}_1 -\left(\frac{\mathbf{x}_p\cdot\mathbf{v}_2}{\mathbf{v}_2\cdot\mathbf{v}_2}\right)\mathbf{v}_2 -\cdots-\left(\frac{\mathbf{x}_p\cdot\mathbf{v}_{p-1}}{\mathbf{v}_{p-1}\cdot\mathbf{v}_{p-1}}\right)\mathbf{v}_{p-1}. \end{align*}

Dan geldt: \(\{\mathbf{v}_1,\ldots,\mathbf{v}_p\}\) is een orthogonale basis van \(W\).

Opmerking: In elke stap worden van iedere basisvector \(\mathbf{x}_k\) de orthogonale projecties langs de nieuwe (orthogonale) basisvectoren \(\mathbf{v}_1,\ldots,\mathbf{v}_{k-1}\) afgetrokken. De resulterende vector \(\mathbf{v}_k\) staat dan loodrecht op alle vectoren \(\mathbf{v}_1,\ldots,\mathbf{v}_{k-1}\) die al (onderling) orthogonaal zijn. Bovendien geldt dan steeds: \(\text{Span}\{\mathbf{v}_1,\ldots,\mathbf{v}_k\}=\text{Span}\{\mathbf{x}_1,\ldots,\mathbf{x}_k\}\).

Een orthogonale basis kan eenvoudig worden omgezet in een orthonormale basis door elke basisvector te normeren (of: te schalen): als \(\{\mathbf{v}_1,\ldots,\mathbf{v}_p\}\) een orthogonale basis van \(W\) is, dan is \(\{\mathbf{u}_1,\ldots,\mathbf{u}_p\}\) met \(\mathbf{u}_i=\displaystyle\frac{1}{||\mathbf{v}_i||}\mathbf{v}_i\) voor \(i=1,2,\ldots,p\) een orthonormale basis van \(W\).

Voorbeeld: Stel \(W=\text{Span}\{\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3\mathbf{x}_4\}\) met \(\mathbf{x}_1=\begin{pmatrix}1\\-1\\0\\1\end{pmatrix}\), \(\mathbf{x}_2=\begin{pmatrix}0\\1\\2\\-1\end{pmatrix}\), \(\mathbf{x}_3=\begin{pmatrix}1\\1\\1\\1\end{pmatrix}\) en \(\mathbf{x}_4=\begin{pmatrix}2\\1\\3\\1\end{pmatrix}\). Dan is \(W\) dus een deelruimte van \(\mathbb{R}^4\). We bepalen eerst een basis van \(W\):

\[\begin{pmatrix}1&0&1&2\\-1&1&1&1\\0&2&1&3\\1&-1&1&1\end{pmatrix}\sim\begin{pmatrix}1&0&1&2\\0&1&2&3\\0&2&1&3\\0&-1&0&-1\end{pmatrix} \sim\begin{pmatrix}1&0&1&2\\0&1&2&3\\0&0&-3&-3\\0&0&2&2\end{pmatrix}\sim\begin{pmatrix}1&0&1&2\\0&1&2&3\\0&0&1&1\\0&0&0&0\end{pmatrix}.\]

Hieruit volgt dat \(\{\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3\}\) een basis van \(W\) is. Nu passen we het orthogonaliseringsproces van Gram-Schmidt toe:

\begin{align*} \mathbf{v}_1&=\mathbf{x}_1=\begin{pmatrix}1\\-1\\0\\1\end{pmatrix}\\[2.5mm] \mathbf{v}_2&=\mathbf{x}_2-\left(\frac{\mathbf{x}_2\cdot\mathbf{v}_1}{\mathbf{v}_1\cdot\mathbf{v}_1}\right)\mathbf{v}_1 =\begin{pmatrix}0\\1\\2\\-1\end{pmatrix}-\frac{\begin{pmatrix}0&1&2&-1\end{pmatrix}\begin{pmatrix}1\\-1\\0\\1\end{pmatrix}}{\begin{pmatrix}1&-1&0&1\end{pmatrix}\begin{pmatrix}1\\-1\\0\\1\end{pmatrix}}\begin{pmatrix}1\\-1\\0\\1\end{pmatrix}\\[2.5mm] &=\begin{pmatrix}0\\1\\2\\-1\end{pmatrix}-\frac{0-1+0-1}{1+1+0+1}\begin{pmatrix}1\\-1\\0\\1\end{pmatrix} =\begin{pmatrix}0\\1\\2\\-1\end{pmatrix}+\frac{2}{3}\begin{pmatrix}1\\-1\\0\\1\end{pmatrix} =\frac{1}{3}\begin{pmatrix}2\\1\\6\\-1\end{pmatrix}\\[2.5mm] \mathbf{v}_3&=\mathbf{x}_3-\left(\frac{\mathbf{x}_3\cdot\mathbf{v}_1}{\mathbf{v}_1\cdot\mathbf{v}_1}\right)\mathbf{v}_1 -\left(\frac{\mathbf{x}_3\cdot\mathbf{v}_2}{\mathbf{v}_2\cdot\mathbf{v}_2}\right)\mathbf{v}_2=\begin{pmatrix}1\\1\\1\\1\end{pmatrix} -\frac{\begin{pmatrix}1&1&1&1\end{pmatrix}\begin{pmatrix}1\\-1\\0\\1\end{pmatrix}}{\begin{pmatrix}1&-1&0&1\end{pmatrix}\begin{pmatrix}1\\-1\\0\\1\end{pmatrix}}\begin{pmatrix}1\\-1\\0\\1\end{pmatrix} -\frac{\begin{pmatrix}1&1&1&1\end{pmatrix}\begin{pmatrix}2\\1\\6\\-1\end{pmatrix}}{\begin{pmatrix}2&1&6&-1\end{pmatrix}\begin{pmatrix}2\\1\\6\\-1\end{pmatrix}}\begin{pmatrix}2\\1\\6\\-1\end{pmatrix}\\[2.5mm] &=\begin{pmatrix}1\\1\\1\\1\end{pmatrix}-\frac{1-1+0+1}{1+1+0+1}\begin{pmatrix}1\\-1\\0\\1\end{pmatrix}-\frac{2+1+6-1}{4+1+36+1}\begin{pmatrix}2\\1\\6\\-1\end{pmatrix} =\begin{pmatrix}1\\1\\1\\1\end{pmatrix}-\frac{1}{3}\begin{pmatrix}1\\-1\\0\\1\end{pmatrix}-\frac{8}{42}\begin{pmatrix}2\\1\\6\\-1\end{pmatrix} =\frac{1}{21}\begin{pmatrix}6\\24\\-3\\18\end{pmatrix}=\frac{1}{7}\begin{pmatrix}2\\8\\-1\\6\end{pmatrix}. \end{align*}

Merk op dat \(\displaystyle\left(\frac{\mathbf{x}_3\cdot\mathbf{v}_2}{\mathbf{v}_2\cdot\mathbf{v}_2}\right)\mathbf{v}_2 =\left(\frac{\mathbf{x}_3\cdot3\mathbf{v}_2}{3\mathbf{v}_2\cdot3\mathbf{v}_2}\right)3\mathbf{v}_2\). Omdat de lengte of norm van de vectoren niet belangrijk is voor de orthogonaliteit, concluderen we dat

\[\{\mathbf{v}_1,3\mathbf{v}_2,7\mathbf{v}_3\}=\left\{\begin{pmatrix}1\\-1\\0\\1\end{pmatrix},\begin{pmatrix}2\\1\\6\\-1\end{pmatrix}, \begin{pmatrix}2\\8\\-1\\6\end{pmatrix}\right\}\]

een orthogonale basis van \(W\) is.

Opmerking: we hadden eerst geconstateerd dat \(\mathbf{x}_4\in\text{Span}\{\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3\}\) zodat we \(\mathbf{x}_4\) niet hoeven mee te nemen in het orthogonaliseringsproces. Als we dat echter toch zouden doen, dan vinden we

\[\mathbf{v}_4=\mathbf{x}_4-\left(\frac{\mathbf{x}_4\cdot\mathbf{v}_1}{\mathbf{v}_1\cdot\mathbf{v}_1}\right)\mathbf{v}_1 -\left(\frac{\mathbf{x}_4\cdot\mathbf{v}_2}{\mathbf{v}_2\cdot\mathbf{v}_2}\right)\mathbf{v}_2 -\left(\frac{\mathbf{x}_4\cdot\mathbf{v}_3}{\mathbf{v}_3\cdot\mathbf{v}_3}\right)\mathbf{v}_3 =\begin{pmatrix}2\\1\\3\\1\end{pmatrix}-\frac{2}{3}\begin{pmatrix}1\\-1\\0\\1\end{pmatrix} -\frac{11}{21}\begin{pmatrix}2\\1\\6\\-1\end{pmatrix}-\frac{1}{7}\begin{pmatrix}2\\8\\-1\\6\end{pmatrix}=\mathbf{0}.\]

Hieruit volgt (eventueel) ook dat \(\mathbf{x}_4\) een lineaire combinatie van \(\mathbf{v}_1\), \(\mathbf{v}_2\) en \(\mathbf{v}_3\) is.

Door de vectoren te normeren of te schalen kunnen we ook een orthonormale basis van \(W\) bepalen:

\[\{\mathbf{u}_1,\mathbf{u}_2,\mathbf{u}_3\}=\left\{\frac{1}{||\mathbf{v}_1||}\mathbf{v}_1,\frac{1}{||\mathbf{v}_2||}\mathbf{v}_2,\frac{1}{||\mathbf{v}_3||}\mathbf{v}_3\right\} =\left\{\frac{1}{\sqrt{3}}\begin{pmatrix}1\\-1\\0\\1\end{pmatrix},\frac{1}{\sqrt{42}}\begin{pmatrix}2\\1\\6\\-1\end{pmatrix}, \frac{1}{\sqrt{105}}\begin{pmatrix}2\\8\\-1\\6\end{pmatrix}\right\}.\]

Het orthogonaliseringsproces van Gram-Schmidt kan worden gebruikt om een \(QR\)-ontbinding van een matrix te vinden:

Stelling: Als \(A\) een \(m\times n\) matrix is met lineair onafhankelijke kolommen, dan kan \(A\) worden geschreven als \(A=QR\), waarbij \(Q\) een \(m\times n\) matrix is waarvan de kolommen een orthonormale basis van \(\text{Col}(A)\) vormen en \(R\) een inverteerbare \(n\times n\) bovendriehoeksmatrix is.

Bewijs: Omdat de kolommen van \(A=\Bigg(\mathbf{a}_1\;\ldots\;\mathbf{a}_n\Bigg)\) lineair onafhankelijk zijn, is \(\{\mathbf{a}_1,\ldots,\mathbf{a}_n\}\) een basis van \(\text{Col}(A)\). Met behulp van het orthogonaliseringsproces van Gram-Schmidt kunnen we hieruit een orthonormale basis \(\{\mathbf{u}_1,\ldots,\mathbf{u}_n\}\) van \(\text{Col}(A)\) construeren. Dan geldt voor iedere \(k=1,2,\ldots,n\) dat \(\text{Span}\{\mathbf{a}_1,\ldots,\mathbf{a}_k\}=\text{Span}\{\mathbf{u}_1,\ldots,\mathbf{u}_k\}\). Er bestaan dus getallen \(r_{1k},\ldots,r_{kk}\) zodat

\[\mathbf{a}_k=r_{1k}\mathbf{u}_1+\cdots+r_{kk}\mathbf{u}_k+0\mathbf{u}_{k+1}+\cdots+0\mathbf{u}_n,\quad k=1,2,\ldots,n.\]

Stel nu dat \(Q=\Bigg(\mathbf{u}_1\;\ldots\;\mathbf{u}_n\Bigg)\), dan volgt dat \(\mathbf{a}_k=Q\mathbf{r}_k\) met \(\mathbf{r}_k=\begin{pmatrix}r_{1k}\\\vdots\\r_{kk}\\0\\\vdots\\0\end{pmatrix}\) voor \(k=1,2,\ldots,n\). Stel nu \(R=\Bigg(\mathbf{r}_1\;\ldots\;\mathbf{r}_n\Bigg)\), dan volgt:

\[A=\Bigg(\mathbf{a}_1\;\ldots\;\mathbf{a}_n\Bigg)=\Bigg(Q\mathbf{r}_1\;\ldots\;Q\mathbf{r}_n\Bigg)=QR.\]

Stel dat \(R\mathbf{x}=\mathbf{0}\), dan volgt dat \(A\mathbf{x}=QR\mathbf{x}=Q\mathbf{0}=\mathbf{0}\). Omdat de kolommen van \(A\) lineair onafhankelijk zijn, volgt hieruit dat \(\mathbf{x}=\mathbf{0}\) en dat bewijst dat \(R\) inverteerbaar is.

Voorbeeld: Stel dat \(A=\begin{pmatrix}1&0&1\\-1&1&1\\0&2&1\\1&-1&1\end{pmatrix}\). Hierboven hebben we gezien dat de kolommen lineair onafhankelijk zijn en dat

\[\left\{\frac{1}{\sqrt{3}}\begin{pmatrix}1\\-1\\0\\1\end{pmatrix},\frac{1}{\sqrt{42}}\begin{pmatrix}2\\1\\6\\-1\end{pmatrix}, \frac{1}{\sqrt{105}}\begin{pmatrix}2\\8\\-1\\6\end{pmatrix}\right\}\]

een orthonormale basis van \(\text{Col}(A)\) is. Dus:

\[Q=\begin{pmatrix}\frac{1}{\sqrt{3}}&\frac{2}{\sqrt{42}}&\frac{2}{\sqrt{105}}\\-\frac{1}{\sqrt{3}}&\frac{1}{\sqrt{42}}&\frac{8}{\sqrt{105}}\\ 0&\frac{6}{\sqrt{42}}&-\frac{1}{\sqrt{105}}\\\frac{1}{\sqrt{3}}&-\frac{1}{\sqrt{42}}&\frac{6}{\sqrt{105}}\end{pmatrix} =\frac{1}{\sqrt{210}}\begin{pmatrix}\sqrt{70}&2\sqrt{5}&2\sqrt{2}\\-\sqrt{70}&\sqrt{5}&8\sqrt{2}\\ 0&6\sqrt{5}&-\sqrt{2}\\\sqrt{70}&-\sqrt{5}&6\sqrt{2}\end{pmatrix}.\]

Aangezien \(Q^TQ=I\) volgt nu dat

\[R=Q^TA=\frac{1}{\sqrt{210}}\begin{pmatrix}\sqrt{70}&-\sqrt{70}&0&\sqrt{70}\\2\sqrt{5}&\sqrt{5}&6\sqrt{5}&-\sqrt{5}\\ 2\sqrt{2}&8\sqrt{2}&-\sqrt{2}&6\sqrt{2}\end{pmatrix}\begin{pmatrix}1&0&1\\-1&1&1\\0&2&1\\1&-1&1\end{pmatrix}=\frac{1}{\sqrt{210}} \begin{pmatrix}3\sqrt{70}&-2\sqrt{70}&\sqrt{70}\\0&14\sqrt{5}&8\sqrt{5}\\0&0&15\sqrt{2}\end{pmatrix}.\]

---

Laatst gewijzigd op 2 mei 2021