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).
Približné riešenie - metóda najmenších štvorcov
Moderators: Martin Sleziak, Ludovit_Balko, Martin Niepel, Tibor Macko
-
Martin Sleziak
- Posts: 5689
- Joined: Mon Jan 02, 2012 5:25 pm
-
Martin Sleziak
- Posts: 5689
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Približné riešenie - metóda najmenších štvorcov
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}$$
Kolmý priemet potom môžeme vypočítať ako $\vec bP=(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)
$
Dostali sme približné riešenie $(\frac43,-\frac13)$.
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:
Spoiler:
$\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:
-
Martin Sleziak
- Posts: 5689
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Približné riešenie - metóda najmenších štvorcov
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$.
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
- Posts: 5689
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Približné riešenie - metóda najmenších štvorcov
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)$$
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)$$