Lineaire Algebra – Orthogonaliteit en kleinste kwadraten – Kleinste-kwadratenproblemen

Een stelsel vergelijkingen \(A\mathbf{x}=\mathbf{b}\) is alleen oplosbaar als \(\mathbf{b}\in\text{Col}(A)\). In de praktijk komt het vaak voor dat zo'n stelsel vergelijkingen niet oplosbaar is, bijvoorbeeld door meetfouten en/of afrondfouten. Dit is vaak erg onbevredigend. Om het stelsel oplosbaar te maken vervangt men dan de vector \(\mathbf{b}\) door een vector die wel in \(\text{Col}(A)\) zit. Om de 'fout' daarbij zo klein mogelijk te houden wordt díe vector in \(\text{Col}(A)\) gekozen die het dichtst bij \(\mathbf{b}\) ligt: de (orthogonale) projectie van \(\mathbf{b}\) op \(\text{Col}(A)\). Een oplossing van een op deze manier verkregen stelsel vergelijkingen heet een kleinste-kwadratenoplossing van \(A\mathbf{x}=\mathbf{b}\):

Definitie: Stel dat \(A\) een \(m\times n\) matrix is en \(\mathbf{b}\in\mathbb{R}^n\). Dan heet \(\hat{\mathbf{x}}\in\mathbb{R}^n\) een kleinste-kwadratenoplossing van \(A\mathbf{x}=\mathbf{b}\) als \(||\mathbf{b}-A\hat{\mathbf{x}}||\leq||\mathbf{b}-A\mathbf{x}||\) voor alle \(\mathbf{x}\in\mathbb{R}^n\).

Het vinden van zo'n kleinste-kwadratenoplossing komt dus neer op het minimaliseren van de afstand \(||\mathbf{b}−A\mathbf{x}||\) oftewel van \(||\mathbf{b}−A\mathbf{x}||^2\), een som van kwadraten. Dat verklaart de term "kleinste-kwadratenoplossing".

We gaan nu op zoek naar zo'n kleinste-kwadratenoplossing. Stel dat \(\hat{\mathbf{b}}=\text{proj}_{\text{Col}(A)}\mathbf{b}\), dan geldt dat \(A\mathbf{x}=\hat{\mathbf{b}}\) oplosbaar is. Stel dat \(\hat{\mathbf{x}}\) een oplossing is, dan geldt dus: \(A\hat{\mathbf{x}}=\hat{\mathbf{b}}\). Dan geldt dat \(\mathbf{b}-\hat{\mathbf{b}}\) loodrecht staat op \(\text{Col}(A)\). Dus: \(\mathbf{b}−A\hat{\mathbf{x}}\) staat loodrecht op elke kolom van \(A\). Als \(\mathbf{a}_j\) zo'n kolom van \(A\) is, dan geldt dus: \(\mathbf{a}_j\cdot(\mathbf{b}-A\hat{\mathbf{x}})=0\) oftewel \(\mathbf{a}_j^T(\mathbf{b}-A\hat{\mathbf{x}})=0\). Dit geldt voor iedere \(j=1,2,\ldots,n\), dus:

\[A^T(\mathbf{b}-A\hat{\mathbf{x}})=\mathbf{0}\quad\Longleftrightarrow\quad A^T\mathbf{b}-A^TA\hat{\mathbf{x}}=\mathbf{0} \quad\Longleftrightarrow\quad A^T\hat{\mathbf{x}}=A^T\mathbf{b}.\]

Dit laatste stelsel vergelijkingen wordt aangeduid met de term normale vergelijkingen:

Stelling: De verzameling van kleinste-kwadratenoplossingen \(\hat{\mathbf{x}}\) van \(A\mathbf{x}=\mathbf{b}\) komt overeen met de niet-lege verzameling van oplossingen van de normale vergelijkingen: \(A^T\hat{\mathbf{x}}=A^T\mathbf{b}\).

Bewijs: We hebben al gezien dat een kleinste-kwadratenoplossing \(\hat{\mathbf{x}}\) van \(A\mathbf{x}=\mathbf{b}\) moet voldoen aan de normale vergelijkingen \(A^TA\hat{\mathbf{x}}=A^T\mathbf{b}\). Omgekeerd, als \(\hat{\mathbf{x}}\) een oplossing is van \(A^TA\hat{\mathbf{x}}=A^T\mathbf{b}\), dan staat \(\mathbf{b}-A\hat{\mathbf{x}}\) dus loodrecht op alle rijen van \(A^T\) en dus op alle kolommen van \(A\). Dus: \(\mathbf{b}−A\hat{\mathbf{x}}\) staat loodrecht op \(\text{Col}(A)\). Dit betekent dat \(\mathbf{b}=A\hat{\mathbf{x}}+(\mathbf{b}-A\hat{\mathbf{x}})\) een ontbinding van \(\mathbf{b}\) is met \(A\hat{\mathbf{x}}\in\text{Col}(A)\) en \(\mathbf{b}-A\hat{\mathbf{x}}\perp\text{Col}(A)\). Aangezien zo'n ontbinding uniek is, geldt dus dat \(A\hat{\mathbf{x}}\) de orthogonale projectie van \(\mathbf{b}\) op \(\text{Col}(A)\) moet zijn. Dus: \(A\hat{\mathbf{x}}=\hat{\mathbf{b}}\) en dat betekent dat \(\hat{\mathbf{x}}\) een kleinste-kwadratenoplossing van \(A\mathbf{x}=\mathbf{b}\) is.

Opmerking: een kleinste-kwadratenoplossing is uniek als de matrix \(A^TA\) inverteerbaar is. Dit is het geval als de kolommen van \(A\) lineair onafhankelijk zijn. We zullen dit niet bewijzen.

De afstand \(||\mathbf{b}-\hat{\mathbf{b}}||=||\mathbf{b}-A\hat{\mathbf{x}}||\) wordt wel de kleinste-kwadratenfout genoemd.

Voorbeelden:

1) Als \(A=\begin{pmatrix}1&0\\1&1\\0&1\end{pmatrix}\) en \(\mathbf{b}=\begin{pmatrix}1\\2\\2\end{pmatrix}\), dan is \(A\mathbf{x}=\mathbf{b}\) niet oplosbaar.

Nu geldt:

\[A^TA=\begin{pmatrix}1&1&0\\0&1&1\end{pmatrix}\begin{pmatrix}1&0\\1&1\\0&1\end{pmatrix}=\begin{pmatrix}2&1\\1&2\end{pmatrix} \quad\text{en}\quad A^T\mathbf{b}=\begin{pmatrix}1&1&0\\0&1&1\end{pmatrix}\begin{pmatrix}1\\2\\2\end{pmatrix}=\begin{pmatrix}3\\4\end{pmatrix}.\]

Dus:

\[A^TA\mathbf{x}=A^T\mathbf{b}:\quad\left(\left.\begin{matrix}2&1\\1&2\end{matrix}\,\right|\,\begin{matrix}3\\4\end{matrix}\right) \sim\left(\left.\begin{matrix}1&2\\0&-3\end{matrix}\,\right|\,\begin{matrix}4\\-5\end{matrix}\right) \sim\left(\left.\begin{matrix}3&0\\0&3\end{matrix}\,\right|\,\begin{matrix}2\\5\end{matrix}\right)\quad\Longrightarrow\quad \hat{\mathbf{x}}=\frac{1}{2}\begin{pmatrix}2\\5\end{pmatrix}.\]

Er geldt dus dat \(\displaystyle\hat{\mathbf{b}}=A\hat{\mathbf{x}}=\frac{1}{3}\begin{pmatrix}1&0\\1&1\\0&1\end{pmatrix} \begin{pmatrix}2\\5\end{pmatrix}=\frac{1}{3}\begin{pmatrix}2\\7\\5\end{pmatrix}\) de orthogonale projectie van \(\mathbf{b}\) op \(\text{Col}(A)\) is. De kleinste-kwadratenfout is dan

\[||\mathbf{b}-\hat{\mathbf{b}}||=||\mathbf{b}-A\hat{\mathbf{x}}||=||\begin{pmatrix}1\\2\\2\end{pmatrix} -\frac{1}{3}\begin{pmatrix}2\\7\\5\end{pmatrix}||=||\frac{1}{3}\begin{pmatrix}1\\-1\\1\end{pmatrix}||=\frac{1}{3}\sqrt{3}.\]

2) Stel dat \(A=\begin{pmatrix}1&0&1\\1&0&1\\0&1&1\\0&1&1\end{pmatrix}\) en \(\mathbf{b}=\begin{pmatrix}1\\3\\1\\3\end{pmatrix}\). Dan zijn de kolommen van \(A\) lineair afhankelijk, want de derde kolom is de som van de eerste en de tweede kolom. Bovendien is het stelsel \(A\mathbf{x}=\mathbf{b}\) niet oplosbaar.

Nu geldt:

\[A^TA=\begin{pmatrix}1&1&0&0\\0&0&1&1\\1&1&1&1\end{pmatrix}\begin{pmatrix}1&0&1\\1&0&1\\0&1&1\\0&1&1\end{pmatrix} =\begin{pmatrix}2&0&2\\0&2&2\\2&2&4\end{pmatrix}\quad\text{en}\quad A^T\mathbf{b}=\begin{pmatrix}1&1&0&0\\0&0&1&1\\1&1&1&1\end{pmatrix} \begin{pmatrix}1\\3\\1\\3\end{pmatrix}=\begin{pmatrix}4\\4\\8\end{pmatrix}.\]

Dus:

\[A^TA\mathbf{x}=A^T\mathbf{b}:\quad\left(\left.\begin{matrix}2&0&2\\0&2&2\\2&2&4\end{matrix}\,\right|\,\begin{matrix}4\\4\\8\end{matrix}\right) \sim\left(\left.\begin{matrix}2&0&2\\0&2&2\\0&2&2\end{matrix}\,\right|\,\begin{matrix}4\\4\\4\end{matrix}\right) \sim\left(\left.\begin{matrix}1&0&1\\0&1&1\\0&0&0\end{matrix}\,\right|\,\begin{matrix}2\\2\\0\end{matrix}\right).\]

In dit geval zijn er dus oneindig veel oplossingen:

\[\left\{\begin{array}{l}x_1=2-x_3\\x_2=2-x_3\\x_3\;\text{is vrij}\end{array}\right.\quad\Longrightarrow\quad \hat{\mathbf{x}}=\begin{pmatrix}2-x_3\\2-x_3\\x_3\end{pmatrix}=\begin{pmatrix}2\\2\\0\end{pmatrix}+x_3\begin{pmatrix}-1\\-1\\1\end{pmatrix}.\]

De orthogonale projectie van \(\mathbf{b}\) op \(\text{Col}(A)\) is uiteraard wel uniek:

\[\hat{\mathbf{b}}=A\hat{\mathbf{x}}=\begin{pmatrix}1&0&1\\1&0&1\\0&1&1\\0&1&1\end{pmatrix} \begin{pmatrix}2-x_3\\2-x_3\\x_3\end{pmatrix}=\begin{pmatrix}2\\2\\2\\2\end{pmatrix}.\]

De \(QR\)-ontbinding van een matrix kan helpen om het rekenwerk te bekorten:

Stelling: Als \(A\) een \(m\times n\) matrix is met lineair onafhankelijke kolommen en \(A=QR\) is de \(QR\)-ontbinding van \(A\), dan geldt: \(A\mathbf{x}=\mathbf{b}\) heeft voor iedere \(\mathbf{b}\in\mathbb{R}^m\) een unieke kleinste-kwadratenoplossing \(\hat{\mathbf{x}}\) gegeven door \(R\hat{\mathbf{x}}=Q^T\mathbf{b}\).

Opmerking: de kleinste-kwadratenoplossing \(\hat{\mathbf{x}}\) is uniek omdat de kolommen van \(A\) lineair onafhankelijk zijn. Omdat \(R\) een bovendriehoeksmatrix is, kan \(R\hat{\mathbf{x}}=Q^T\mathbf{b}\) (eenvoudig) worden opgelost door middel van terugsubstitutie.

Bewijs: Voor een \(QR\)-ontbinding van \(A\) geldt dat \(Q^TQ=I\) (want \(Q\) heeft orthonormale kolommen) en dat \(R\) inverteerbaar is. Dus:

\[A^TA=(QR)^TQR=R^TQ^TQR=R^TIR=R^TR\quad\text{en}\quad A^T\mathbf{b}=(QR)^T\mathbf{b}=R^TQ^T\mathbf{b}.\]

Omdat \(R\) inverteerbaar is (\(\text{det}(R)\neq0\)), is \(R^T\) ook inverteerbaar (want: \(\det(R^T)=\det(R)\neq0\)). Dus:

\[A^TA\hat{\mathbf{x}}=A^T\mathbf{b}\quad\Longleftrightarrow\quad R^TR\hat{\mathbf{x}}=R^TQ^T\mathbf{b} \quad\Longleftrightarrow\quad R\hat{\mathbf{x}}=Q^T\mathbf{b}.\]

---

Laatst gewijzigd op 2 mei 2021