Kleinste kwadratenoplossingen van lineaire vergelijkingen

Orthogonale en symmetrische afbeeldingen: Toepassingen van symmetrische matrices

Kleinste kwadratenoplossingen van lineaire vergelijkingen

We zagen dat een stelsel vergelijkingen geschreven kan worden als een matrixvergelijking $A\vec{x}=\vec{b}$ . Als de rang van de coëfficiëntenmatrix $A$ gelijk is aan de rang van de aangevulde matrix $(A\mid\vec{b})$ , dan heeft het stelsel een oplossing $\vec{x}$ .

Het enige alternatief is dat de rang van de coëfficiëntenmatrix kleiner is dan de rang van de aangevulde matrix. In dat geval bestaat er geen oplossing. We gaan nu na hoe we de best mogelijke benadering voor een oplossing kunnen vinden. Met andere woorden, we gaan op zoek naar een vector $\vec{\hat{x}}$ waarvoor de afstand $\norm{A\vec{\hat{x}}-\vec{b}}$ tussen $\vec{b}$ en het beeld onder $A$ van de benaderende oplossing $\vec{\hat{x}}$ geminimaliseerd wordt.

Laat $A$ een $(m\times n)$ -matrix zijn en $\vec{b}$ een vector in $\mathbb{R}^m$ .

De vergelijking $A^{\top}A\vec{x}=A^{\top}\vec{b}$ met onbekende $\vec{x}$ heeft een oplossing.
Elke oplossing $\vec{\hat{x}}$ van deze vergelijking geeft een beste benadering voor de vergelijking $A\vec{x}=\vec{b}$ in de zin dat $\norm{A\vec{x}-\vec{b}}$ minimaal is voor $\vec{x} = \vec{\hat{x}}$ onder alle vectoren $\vec{x}$ van $\mathbb{R}^m$ .

Als de $(m\times n)$ -matrix $A$ rang $n$ heeft, kunnen we deze beste benadering eenvoudig vinden. Dan is de matrix $A^{\top}A$ namelijk inverteerbaar, zodat we de volgende procedure kunnen uitvoeren:

Bereken $A^\top A$ en $A^{\top}\vec{b}$ .
Bereken de inverse van $A^\top A$ .
Nu wordt $\vec{\hat{x}}$ gegeven door $(A^{\top} A)^{-1}\,(A^\top\vec{b})$ .
Nu wordt $\vec{\hat{b}}$ gegeven door $A\vec{\hat{x}}$ .

Dat de eis van de rang essentieel is, wordt duidelijk als we kijken naar het volgende voorbeeld $\matrix{1&1\\1&1}\, \cv{x\\y} = \cv{1\\0}$ De matrix $A^{\top}A$ wordt gegeven door $\matrix{2&2\\2&2}$ Deze matrix is niet inverteerbaar want zijn determinant is gelijk aan $0$ .

Deze stelling is vooral nuttig wanneer het stelsel $A\,\vec{x}=\vec{b}$ geen oplossing heeft. Als dit stelsel wel een oplossing heeft, is deze oplossing dezelfde als die van $A^{\top}A\vec{x}=A^{\top}\vec{b}$ , dus in dit geval zou de kleinste kwadratenmethode onnodige moeite opleveren.

Bekijk het strijdige stelsel
$\eqs{x+y&=&1\\ 2x+3y&=&4\\ x-y&=&0}$ Dat dit stelsel geen oplossing heeft, is snel duidelijk. De laatste vergelijking geeft $x=y$ , in combinatie met de eerste geeft dit $x=y=\frac{1}{2}$ . Als we dit invullen in de tweede vergelijking krijgen we echter $\frac{5}{2}=4$ . We kunnen dus geen oplossing vinden, en gaan op zoek naar de beste benadering. Hiervoor schrijven we het stelsel eerst om naar de matrixvergelijking $A\vec{x} = \vec{b}$ met
$A = \matrix{1 & 1\\ 2&3\\1 & -1}\quad \text{ en } \quad \vec{b} = \matrix{1\\4\\0}$ We berekenen $A^{\top}A$ en $A^{\top}\vec{b}$ .
$\begin{array}{rcl} A^{\top}A&=&\displaystyle\matrix{1&3&-1\\1&2&1}\matrix{1&1\\2&3\\1&-1}=\matrix{6&11\\6&6} \\ A^{\top} \vec{b}&=&\displaystyle\matrix{1&3&-1\\1&2&1}\matrix{1\\4\\0}=\matrix{13\\9}\end{array}$ De inverse van de matrix $A^{\top}A$ wordt gegeven door
$(A^{\top} A)^{-1}=\matrix{-\frac{1}{5}&\frac{11}{30}\\\frac{1}{5}&-\frac{1}{5}}$ We kunnen nu de vector $\vec{\hat{x}}$ berekenen:
$\vec{\hat{x}}=(A^{\top} A)^{-1}A^\top\vec{b}=\matrix{-\frac{1}{5}&\frac{11}{30}\\\frac{1}{5}&-\frac{1}{5}}\matrix{13\\9}=\matrix{\frac{7}{10}\\\frac{4}{5}}$ Deze vector wordt door de matrix $A$ afgebeeld op de vector $\vec{\hat{b}}$ , die gegeven wordt door
$\vec{\hat{b}}=A\vec{\hat{x}}=\matrix{1 & 1\\ 2&3\\1 & -1}\matrix{\frac{7}{10}\\\frac{4}{5}}=\matrix{\frac{2}{3}\\\frac{19}{5}\\-\frac{1}{10}}$

Een klassieke toepassing van de kleinste kwadratenmethode heeft een statistisch karakter. Stel dat een aantal punten $\rv{x_i,y_i}$ , met $i=1,\ldots,n$ , een stel punten in het $x,y$ -vlak is. Het lineaire regressie probleem vraagt naar een lijn die deze verzameling punten in het geheel het best benadert. De lijn die de beste benadering zal gaan vormen, beschrijven we door $y=a+b\cdot x$ voor nader te bepalen reële getallen $a$ en $b$ . We zijn dus op zoek naar de oplossing voor $a$ en $b$ van het stelsel
$\begin{array}{rcl} a+bx_1&=&y_1\\ a+bx_2&=&y_2\\ \vdots &\quad& \vdots\\ a+bx_n&=&y_n \end {array}$ Dit geeft ons dus in matrixvorm
$\matrix{1&x_1\\1&x_2\\\vdots&\vdots\\1&x_n}\matrix{a\\b}=\matrix{y_1\\y_2\\\vdots\\y_n}$ De kleinste kwadratenmethode geeft een antwoord hierop.

We kunnen voor dit stelsel net als in het andere voorbeeld gewoon eenvoudig de beste benadering berekenen. Dezelfde methode werkt voor het vinden van de beste hogeregraadse benadering, die de vorm $y:c_1+c_2x+\cdots+c_mx^m$ heeft. De matrixvergelijking wordt dan
$\matrix{1&x_1&x_1^2&\ldots &x_1^m\\1&x_2&x_2^2&\ldots& x_2^m\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&x_n&x_n^2&\cdots&x_n^m}\matrix{c_1\\\vdots\\c_m}=\matrix{y_1\\y_2\\\vdots\\y_n}$ Deze methode beperkt zich niet tot veeltermen. Ook exponentiële functies kunnen geconstrueerd worden aan de hand van een dergelijke methode. Dit kan bijvoorbeeld zijn toepassingen vinden binnen het modelleren van de groei van populaties.

Het vinden van een functie, zij het een veelterm of een andere functie, die het best een dergelijke puntenwolk benadert, heet ook wel het vinden van de kleinste kwadratenfit.

Dezelfde methode als lineaire regressie werkt ook voor het vinden van de beste benadering van een stel punten $\rv{x_i,y_i}$ voor $i=1,\ldots,n$ in het $x,y$ -vlak door middel van de grafiek van een veeltermfunctie van hogere graad. Als we $y:c_1+c_2x+\ldots+c_mx^m$ nemen, dan wordt de overeenkomstige matrixvergelijking $\matrix{1&x_1&x_1^2&\ldots &x_1^m\\1&x_2&x_2^2&\ldots& x_2^m\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&x_n&x_n^2&\ldots&x_n^m}\matrix{c_1\\\vdots\\c_m}=\matrix{y_1\\y_2\\\vdots\\y_n}$ In feite werkt deze methode voor andere functies dan veeltermen. Exponentiële functies worden bijvoorbeeld vaak gebruikt bij het modelleren van de groei van een bevolking.

De vergelijking $A^{\top}A\vec{x}=A^{\top}\vec{b}$ noemen we ook wel de normaalvergelijking van de matrixvergelijking $A\vec{x}=\vec{b}$ .

We zullen beide onderdelen bewijzen, beginnend met de eerste.

1. Laat $A$ een $(m\times n)$ -matrix zijn en $\vec{b}$ een vector uit $\mathbb{R}^m$ . We beweren dat $\ker{A} = \ker{A^\top A}$ . Het is duidelijk dat $\ker{A} \subseteq \ker{A^\top A}$ , zodat we om de bewering te bewijzen alleen hoeven na te gaan dat $\ker{A^\top A} \subseteq\ker{A}$ . Stel daartoe dat $\vec{x}$ behoort tot $\ker{A^\top A}$ . Dan geldt $\dotprod{(A\vec{x})}{(A\vec{x})} = \dotprod{\vec{x}}{(A^\top A\vec{x})}= \dotprod{\vec{x}}{\vec{0}}=0$ Omdat het inproduct positief-definiet is, volgt hieruit $A\vec{x} = \vec{0}$ , dat wil zeggen: $\vec{x}$ behoort tot $\ker{A}$ . Hiermee is de bewering $\ker{A} = \ker{A^\top A}$ vastgesteld.

We zullen nu bewijzen dat $\im{A^\top \, A} = \im{A^\top}$ . Omdat $\im{A^\top \, A} \subseteq \im{A^\top}$ duidelijk is, volstaat het om de inclusie $\im{A^\top}\subseteq\im{A^\top \, A}$ te bewijzen. Dit volgt uit de volgende afleiding: $\begin{array}{rcl}\text{Stel }& \vec{x}\in \im{A^\top A}^\perp\\ \text{Dan geldt }&\dotprod{\vec{x}}{(A^\top A\vec{v})}=0&\text{voor alle }\vec{v}\in \mathbb{R}^n\\ \text{Dus ook }&\dotprod{(A\vec{x})}{( A\vec{v})}=0&\text{voor alle }\vec{v}\in \mathbb{R}^n\\ \text{En ook }&\dotprod{(A^\top A\vec{x})}{\vec{v}}=0&\text{voor alle }\vec{v}\in \mathbb{R}^n\\\text{Dit betekent dat }&A^\top A\vec{x}=\vec{0}&\\ \text{Volgens bovenstaande uitspraak volgt hieruit }& A\vec{x}=\vec{0}&\\\text{Voor het inproduct geeft dit }&\dotprod{(A\vec{x})}{\vec{v}}=0&\text{voor alle }\vec{v}\in \mathbb{R}^n\\ \text{Bijgevolg }&\dotprod{\vec{x}}{(A^\top \vec{v})}=0&\text{voor alle }\vec{v}\in \mathbb{R}^n\\ \text{Met andere woorden: }&\vec{x}\in\im{ A^\top}^{\perp}&\end{array}$ Hiermee hebben we de inclusie $\im{A^\top A}^\perp\subseteq\im{ A^\top}^\perp$ afgeleid. Volgens de eigenschappen van de loodrechte ruimte geldt dan ook $\im{ A^\top}={\im{ A^\top}^\perp}^\perp\subseteq {\im{A^\top A} ^\perp}^\perp = \im{A^\top A}$ De vector $A^{\top}\vec{b}$ behoort tot $\im{A^\top}$ . Er is dus een vector $\vec{x}$ , zodat $A^{\top}A\vec{x}=A^{\top}\vec{b}$ . Dit bewijst de eerste uitspraak.

2. Stel dat $\vec{x} = \vec{\hat{x}}$ een oplossing is van de vergelijking $A^{\top}A\vec{x}=A^{\top}\vec{b}$ . We beweren dat dan $\vec{\hat{b}} =A\vec{\hat{x}}$ de orthogonale projectie van $\vec{b}$ op $\im{A}$ is. Om dit in te zien, berekenen we $\begin{array}{rcl}\dotprod{(\vec{\hat{b}}-\vec{b})}{(A\vec{y})}&=&\dotprod{(A\vec{\hat{x}}-\vec{b})}{(A\vec{y})}\\&=&\dotprod{(A\vec{\hat{x}})}{(A\vec{y})}-\dotprod{\vec{b}}{(A\vec{y})}\\&=&\dotprod{(A^\top A\vec{\hat{x}})}{\vec{y}}-\dotprod{(A^\top\vec{b})}{\vec{y}}\\&=&\dotprod{(A^\top A\vec{\hat{x}}-A^\top\vec{b})}{\vec{y}}\\&=&\dotprod{\vec{0}}{\vec{y}}\\&=&0\end{array}$ Dit laat zien dat $\vec{\hat{b}}-\vec{b}$ loodrecht staat op het beeld van $A$ . De vector $\vec{\hat{b}} =A\vec{\hat{x}}$ behoort tot $\im{A}$ en is dus de loodrechte projectie van $\vec{b}$ op $\im{A}$ . Dit betekent dat $\vec{\hat{b}}$ van alle beelden van vectoren onder $A$ het dichtst bij de vector $\vec{b}$ ligt. Daarom levert $\vec{x}=\vec{\hat{x}}$ de beste benadering voor een oplossing van de vergelijking $A\vec{x}=\vec{b}$ .

NaamDe methode heet kleinste kwadratenmethode naar aanleiding van lineaire regressie in het vlak, waarbij het probleem is om bij een gegeven stel punten een lijn te vinden die het stel punten zo goed mogelijk beschrijft als onderdeel van de grafiek van een lineaire functie. De oplossing is de lijn waarvoor de som over de kwadraten van alle verticale afstanden van de gegeven punten tot de lijn minimaal is.

Vind de kleinste kwadratenoplossing van de volgende vergelijking:
$\matrix{3 & 4 \\ -2 & -5 \\ 1 & -2} \, \vec{x} = \cv{-5\\-1\\4}$

$\vec{x}={}$ $\cv{\frac{11}{46}\\-\frac{71}{115}}$

Om de kleinste kwadratenbenadering $\vec{x}$ voor dit probleem te vinden, lossen we $A^{\top}A\vec{x}=A^{\top}\,\vec{b}$ op, met:
$A=\matrix{3 & 4 \\ -2 & -5 \\ 1 & -2} \quad \text{en}\quad \vec{b}= \cv{-5\\-1\\4}$ We berekenen $A^{\top}A$ en $A^{\top}\,\vec{b}$ : $\begin{aligned} A^{\top}A &= \matrix{3 & -2 & 1 \\ 4 & -5 & -2}\matrix{3 & 4 \\ -2 & -5 \\ 1 & -2}\\ &= \matrix{3\cdot3-2\cdot-2+1\cdot1 & 3\cdot4-2\cdot-5+1\cdot-2 \\ 3\cdot4-2\cdot-5+1\cdot-2 & 4\cdot4-5\cdot-5-2\cdot-2}\\ &= \matrix{14 & 20 \\ 20 & 45} \end{aligned}$ en
$\begin{aligned} A^{\top}\,\vec{b} &= \matrix{3 & -2 & 1 \\ 4 & -5 & -2} \cv{-5\\-1\\4}\\ &= \matrix{3\cdot-5-2\cdot-1+4\cdot1 \\ 4\cdot-5-5\cdot-1-2\cdot4}\\ &= \matrix{-9 \\ -23} \end{aligned}$ De coëfficiëntenmatrix die correspondeert met $A^{\top}A \vec{x}=A^{\top}\,\vec{b}$ is:
$\left(\begin{array}{cc|c} 14 & 20 & -9 \\ 20 & 45 & -23 \end{array}\right)$ Rijreductie geeft:
$\begin{array}[t]{ll} \left(\begin{array}{cc|c} 14 & 20 & -9 \\ 20 & 45 & -23 \\ \end{array}\right) & \begin{array}[t]{ll} \sim\left(\begin{array}{rr|r} 20 & 45 & -23 \\ 14 & 20 & -9 \end{array}\right) & \\\\ \sim\left(\begin{array}{rr|r} 1 & {{9 }\over{4}} & -{{23}\over{20}} \\ 14 & 20 & -9 \end{array}\right) & \\\\ \sim\left(\begin{array}{rr|r} 1 & {{9 }\over{4}} & -{{23}\over{20}} \\ 0 & -{{23}\over{2}} & {{71}\over{10 }} \end{array}\right) & \\\\ \sim\left(\begin{array}{rr|r} 1 & {{9}\over{4}} & -{{23}\over{20}} \\ 0 & 1 & - {{71}\over{115}} \end{array}\right) & \\\\ \sim\left(\begin{array}{rr|r} 1 & 0 & {{11}\over{46}} \\ 0 & 1 & - {{71}\over{115}} \end{array}\right) \end{array} \end{array}$ Dus, $\vec{x}=\cv{\frac{11}{46}\\-\frac{71}{115}}$

Omdat de matrix $A^{\top}A$ inverteerbaar is, hadden we ook de kleinste kwadratenoplossing kunnen berekenen door $A^{\top}A$ te inverteren en de bekende berekeningen uit te voeren zoals deze in de theorie zijn gegeven.

Nieuw voorbeeld