Približné riešenie - metóda najmenších štvorcov

[Martin Sleziak]

Vráťme sa ešte k tomuto typu úloh, ktorý sme robili na cvičení.

Vyskúšajme takýto problém.

Úloha. Nájdite približné riešenie $X=\begin{pmatrix} x_1\\ x_2 \end{pmatrix}$ sústavy $Ax=B$ pre
$$A= \begin{pmatrix} 1 &-2 \\ -1 & 2 \\ 0 & 3 \\ 2 & 5 \\ \end{pmatrix} \qquad b=\begin{pmatrix}3\\1\\-4\\2\end{pmatrix}.$$

Je to Exercise 6.5.3 z Lay: Linear Algebra and Its Applications (4th Edition).

[Martin Sleziak]

Najbližší bod

Pre ľubovoľné $X$ je výraz tvaru $AX$ stĺpcový vektor, ktorý je lineárnou kombináciou stĺpcov matice $A$. Ak nevieme nijakou lineárnou kombináciou dostať vektor $b$, chceli by sme aspoň nájsť nejaký bod $\widehat b$, ktorý je k nemu najbližší. To je vlastne kolmý priemet vektora $\vec b=(3,1,-4,2)$ do podpriestoru $[(1,-1,0,2),(-2,2,3,5)]$.

To vieme urobiť viacerými spôsobmi.
Napríklad ak by sa nám podarilo nájsť ortogonálnu bázu $\vec v_1=(1,-1,0,2)$, $\vec v_2=(1,-1,-1,-1)$ a z nej ortonormálnu bázu $\vec u_1=\frac1{\sqrt6}(1,-1,0,2)$, $\vec u_2=\frac12(1,-1,-1,-1)$, tak vieme vypočítať maticu projekcie
$$P=\frac1{12}\begin{pmatrix} 5 &-5 &-3 & 1 \\ -5 & 5 & 3 &-1 \\ -3 & 3 & 3 & 3 \\ 1 &-1 & 3 &11 \\ \end{pmatrix}$$

Spoiler:

$$P= \frac16\begin{pmatrix} 1 &-1 & 0 & 2 \\ -1 & 1 & 0 &-2 \\ 0 & 0 & 0 & 0 \\ 2 &-2 & 0 & 4 \\ \end{pmatrix}+ \frac14\begin{pmatrix} 1 &-1 &-1 &-1 \\ -1 & 1 & 1 & 1 \\ -1 & 1 & 1 & 1 \\ -1 & 1 & 1 & 1 \\ \end{pmatrix}= \frac1{12}\begin{pmatrix} 5 &-5 &-3 & 1 \\ -5 & 5 & 3 &-1 \\ -3 & 3 & 3 & 3 \\ 1 &-1 & 3 &11 \\ \end{pmatrix}$$

Kolmý priemet potom môžeme vypočítať ako $\vec bP=(2,-2,-1,1)$.

Spoiler:

$\frac1{12}(3,1,-4,2) \begin{pmatrix} 5 &-5 &-3 & 1 \\ -5 & 5 & 3 &-1 \\ -3 & 3 & 3 & 3 \\ 1 &-1 & 3 &11 \\ \end{pmatrix}= \frac1{12}(24,-24,-12,12)=(2,-2,-1,1)$

Ešte treba vyriešiť príslušnú sústavu
$\left(\begin{array}{cc|c} 1 &-2 & 2\\ -1 & 2 &-2\\ 0 & 3 &-1\\ 2 & 5 & 1\\ \end{array}\right)\sim\dots\sim \left(\begin{array}{cc|c} 1 & 0 & \frac43\\ 0 & 1 &-\frac13\\ 0 & 0 & 0\\ 0 & 0 & 0\\ \end{array}\right)$

Spoiler:

$\left(\begin{array}{cc|c} 1 &-2 & 2\\ -1 & 2 &-2\\ 0 & 3 &-1\\ 2 & 5 & 1\\ \end{array}\right)\sim$ $\left(\begin{array}{cc|c} 1 &-2 & 2\\ 0 & 0 & 0\\ 0 & 1 &-\frac13\\ 2 & 5 & 1\\ \end{array}\right)\sim$ $\left(\begin{array}{cc|c} 1 & 0 & \frac43\\ 0 & 1 &-\frac13\\ 0 & 0 & 0\\ 2 & 5 & 1\\ \end{array}\right)\sim$ $\left(\begin{array}{cc|c} 1 & 0 & \frac43\\ 0 & 1 &-\frac13\\ 0 & 0 & 0\\ 0 & 0 & 0\\ \end{array}\right)$

Dostali sme približné riešenie $(\frac43,-\frac13)$.

[Martin Sleziak]

Násobenie transponovanou maticou

Približné riešenie môžeme hľadať tak, že riešime sústavu $A^TAx=A^Tb$.

Prečo to funguje?
Dôkaz môžete nájsť v Lay: Linear Algebra and Its Applications. (Vo Fourth Edition je to Theorem 6.5.13, v iných vydaniach sa možno môže číslovanie trochu líšiť.)
Skúsim k tomu ale stručne niečo povedať aj tu.
My chceme nájsť riešenie $Ax=\widehat b$, kde $\widehat b$ je ortogonálny priemet do priestoru generovaného stĺpcami matice $A$.
To špeciálne znamená, že $b-\widehat b$ má byť kolmé na stĺpce matice $A$. Túto podmienku môžeme ekvivalentne prepísať ako $A^T(b-\widehat b)=0$.
Teda dostávame $A^T\widehat b=A^Tb$.
Ak teda pre nejaké $x$ má platiť $Ax=\widehat b$, tak skutočne musí platiť aj rovnosť
$$A^TAx=A^T\widehat b=A^Tb.$$
Vidíme, že hľadané $x$ skutočne vyhovuje sústave, ktorú sme uviedli vyššie. Na dokončenie dôkazu by sme mali ukázať aj obrátenú implikáciu - ak $x$ vyhovuje tejto sústave, tak je to naozaj približné riešenie. (Zdôvodniť sa to dá do istej miery podobne - treba si uvedomiť čo nám táto rovnica hovorí o kolmosti vektora $Ax-b$ na stĺpcový priestor matice $A$.)

Riešenie

V našom prípade dostaneme
$$A^TA= \begin{pmatrix} 1 &-1 & 0 & 2 \\ -2 & 2 & 3 & 5 \\ \end{pmatrix} \begin{pmatrix} 1 &-2 \\ -1 & 2 \\ 0 & 3 \\ 2 & 5 \\ \end{pmatrix}= \begin{pmatrix} 6 & 6 \\ 6 & 42 \\ \end{pmatrix} \qquad A^Tb= \begin{pmatrix} 1 &-1 & 0 & 2 \\ -2 & 2 & 3 & 5 \\ \end{pmatrix} \begin{pmatrix}3\\1\\-4\\2\end{pmatrix}= \begin{pmatrix} 6\\-6 \end{pmatrix}$$

Riešením sústavy, ktorú sme takto získali, dostaneme
$\left(\begin{array}{cc|c} 6 & 6 & 6 \\ 6 &42 &-6 \end{array}\right)\sim \left(\begin{array}{cc|c} 1 & 1 & 1 \\ 1 & 7 &-1 \end{array}\right)\sim \left(\begin{array}{cc|c} 1 & 1 & 1 \\ 0 & 6 &-2 \end{array}\right)\sim \left(\begin{array}{cc|c} 1 & 1 & 1 \\ 0 & 1 &-\frac13 \end{array}\right)\sim \left(\begin{array}{cc|c} 1 & 0 & \frac43 \\ 0 & 1 &-\frac13 \end{array}\right)$
Približné riešenie sústavy je teda $x_1=\frac43$, $x_2=-\frac13$.

[Martin Sleziak]

Derivácie

Skúsme sa pozrieť na túto úlohu ako na minimalizáciu vhodnej funkcie a využiť to, že aby sa niekde nadobudlo minimum, tak nutne musia byť nulové parciálne derivácie: viewtopic.php?t=1428

Chceme minimalizovať funkciu$\newcommand{\abs}[1]{|{#1}|} \newcommand{\vek}[1]{\vec{#1}} \newcommand{\skal}[2]{\langle{\vek{#1}},{\vek{#2}}\rangle} \newcommand{\skl}[2]{\langle{#1},{#2}\rangle}$ $g(x_1,x_2)=\abs{AX-B}^2$.
$$\begin{align*} g(x_1,x_2)&=(a_{11}x_1+a_{12}x_2-b_1)^2+(a_{21}x_1+a_{22}x_2-b_2)^2+(a_{31}x_1+a_{32}x_2-b_3)^2\\ \frac{\partial g(x_1,x_2)}{\partial x_1}&=2a_{11}(a_{11}x_1+a_{12}x_2-b_1)+2a_{21}(a_{21}x_1+a_{22}x_2-b_2)+2a_{31}(a_{31}x_1+a_{32}x_2-b_3)\\ \frac{\partial g(x_1,x_2)}{\partial x_2}&=2a_{12}(a_{11}x_1+a_{12}x_2-b_1)+2a_{22}(a_{21}x_1+a_{22}x_2-b_2)+2a_{32}(a_{31}x_1+a_{32}x_2-b_3)\\ \end{align*}$$
Po úprave dostaneme
$$\begin{align*} (a_{11}^2+a_{21}^2+a_{31}^2)x_1+(a_{11}a_{12}+a_{21}a_{22}+a_{31}a_{32})x_2&=a_{11}b_1+a_{21}b_2+a_{31}b_3\\ (a_{11}a_{12}+a_{21}a_{22}+a_{31}a_{32})x_1+(a_{21}^2+a_{22}^2+a_{32}^2)x_2&=a_{12}b_1+a_{22}b_2+a_{32}b_3\\ \end{align*}$$

To isté zapísané inak - označme si $\vek a_1=(a_{11},a_{21})$ a $\vek a_2=(a_{12},a_{22})$. (T.j. zobrali sme stĺpce matice $A$.) Potom dostaneme:
$$\begin{align*} g(x_1,x_2) &= \skl{x_1\vek a_1+x_2\vek a_2 - \vek b}{x_1\vek a_1+x_2\vek a_2 - \vek b} \\ &= x_1^2 \abs{\vek a_1}^2 + 2x_1x_2\skal{a_1}{a_2} + x_2^2 \abs{\vek a_1}^2 - x_1 \skal{a_1}b - x_2\skal{a_2}b + \abs{\vek b}^2 \end{align*}$$
Pre parciálne derivácie potom dostaneme:
$$\begin{align*} \frac{\partial g(x_1,x_2)}{\partial x_1}&= 2(\abs{\vek a_1}^2x_1+\skal{a_1}{a_2}x_2-\skal{a_1}b)\\ \frac{\partial g(x_1,x_2)}{\partial x_2}&= 2(\skal{a_1}{a_2}x_1+\abs{\vek a_2}^2x_2-\skal{a_2}b) \end{align*}$$
čo nám dá sústavu
$$\begin{align*} \abs{\vek a_1}^2x_1+\skal{a_1}{a_2}x_2&=\skal{a_1}b\\ \skal{a_1}{a_2}x_1+\abs{\vek a_2}^2x_2&=\skal{a_2}b \end{align*}$$
Je to presne tá istá sústava, ktorú sme dostali pri predošlom postupe. (Stačí si uvedomiť že v $A^TA$ a v $A^Tb$ skutočne vycházajú práve takéto skalárne súčiny.)

Konkrétne pre zadanú maticu máte $\vek a_1=(1,-1,0,2)$, $\vek a_2=(-2,2,3,5)$ a $\vek b=(3,1,-4,2)$, čiže dostanete:
$\skal{a_1}{a_1}=6$
$\skal{a_1}{a_2}=6$
$\skal{a_2}{a_2}=42$
$\skal{a_1}{b}=6$
$\skal{a_2}{b}=6$
Z toho vyjde sústava:
$$\left(\begin{array}{cc|c} 6 & 6 & 6 \\ 6 &42 &-6 \end{array}\right)$$