×   HOME PREDAVANJA

SADRŽAJ INTEGRAL ODREĐENI INTEGRAL FUNKCIJE VIŠE VARIJABLA VIŠESTRUKI INTEGRALI DIFERENCIJALNE JEDNADŽBE METODA NAJMANJIH KVADRATA INDEKS

VJEŽBE

SADRŽAJ INTEGRAL ODREĐENI INTEGRAL FUNKCIJE VIŠE VARIJABLA VIŠESTRUKI INTEGRALI DIFERENCIJALNE JEDNADŽBE METODA NAJMANJIH KVADRATA

PODSJETNIK

SADRŽAJ NEODREĐENI INTEGRAL ODREĐENI INTEGRAL FUNKCIJE VIŠE VARIJABLA VIŠESTRUKI INTEGRALI DIFERENCIJALNE JEDNADŽBE METODA NAJMANJIH KVADRATA

JAVA NETPLOT OCTAVE Traži ...

☰   matematika2 Linearna regresija     Problem najmanjih kvadrata     Problem najmanjih kvadrata s

Metoda najmanjih kvadrata

Postupak iz prethodnog poglavlja primjenjiv je i na višedimenzionalne probleme. U ovom poglavlju pokazat ćemo da je postupak primjenjiv uvijek kada matrica sustava $A$ ima linearno nezavisne stupce te je u tom slučaju rješenje problema najmanjih kvadrata jedinstveno.

Neka je zadan preodređeni sustav $Ax=b$ od $m$ jednadžbi s $n$ nepoznanica, pri čemu je $m>n$ . Kako za normu vektora $x$ vrijedi $\Vert x\Vert^2=x^Tx$ , problem najmanjih kvadrata

$$% \begin{equation}\label{ls1} \Vert A\mathbf{x} - \mathbf{b}\Vert^2\to \min$$

možemo zapisati kao

$$% \begin{equation}\label{ls2} (A\mathbf{x} - \mathbf{b})^T(A\mathbf{x} - \mathbf{b}) \to \min.$$

Uvedimo oznaku

$$Q(\mathbf{x}) =\Vert A\mathbf{x} - \mathbf{b}\Vert^2=(A\mathbf{x} - \mathbf{b})^T(A\mathbf{x} - \mathbf{b})$$

$$=\mathbf{x}^TA^TA\mathbf{x} - \mathbf{b}^TA\mathbf{x}-\mathbf{x}^TA^T\mathbf{b}+\mathbf{b}^T\mathbf{b}$$ (6.1)

$$=\mathbf{x}^T B \mathbf{x}-2\mathbf{x}^T\mathbf{c}+\beta$$

gdje je

$$B=A^TA,\qquad \mathbf{c}=A^T\mathbf{b},\qquad \beta=\Vert\mathbf{b}\Vert^2.$$

Ideju za postupak rješavanja daje nam jednodimenzionalni slučaj: ako su $x$ , $B$ , $c$ i $\beta$ realni brojevi, onda je $Q(x)=Bx^2-2xc+\beta$ kvadratna parabola čiji se minimum nalazi u točki

$$x=\frac{c}{B}.$$

U višedimenzionalnom slučaju tome odgovara

$$x=B^{-1}c$$

pa je $x$ rješenje sustava

$$Bx=c,$$

odnosno

$$A^TAx=A^Tb.$$

Ova jednadžba zove se normalna jednadžba. Dokažimo sada da ovaj intuitivni postupak zaista daje rješenje.

Teorem 6.1   Neka su stupci matrice $A$ linearno nezavisni, odnosno $\mathop{\mathrm{rang}}\nolimits (A)=n$ . Tada je rješenje $x$ problema najmanjih kvadrata $Q(\mathbf{x})\to \min$ ujedno i jedinstveno rješenje normalne jednadžbe $A^TA\mathbf{x}=A^T\mathbf{b}$ .

Dokaz.

Neka je $\mathbf{y}$ bilo koji $n$ -dimenzionalni vektor i neka je $\mathbf{h}=\mathbf{y}-\mathbf{x}$ . Tada je prema (6.1)

$$Q(\mathbf{y}) =\mathbf{y}^TB\mathbf{y}-2\mathbf{y}^T\mathbf{c}+\beta$$

$$=(\mathbf{x}+\mathbf{h})^TB(\mathbf{x}+\mathbf{h})-2(\mathbf{x}+\mathbf{h})^T \mathbf{c}+\beta$$

$$=\mathbf{x}^TB\mathbf{x}+ \mathbf{h}^TB\mathbf{x}+\mathbf{x}^TB\m... ...\mathbf{h}^TB\mathbf{h} -2\mathbf{x}^T\mathbf{c}-2\mathbf{h}^T\mathbf{c}+\beta.$$

Kako je $B\mathbf{x}=\mathbf{c}$ , to je

$$\mathbf{h}^TB\mathbf{x}=\mathbf{h}^T\mathbf{c},$$

a kako se radi o matricama dimenzije $1$ , to je zbog $B ^T=(A^TA)^T=B$ i

$$\mathbf{x}^TB\mathbf{h}=(\mathbf{x}^TB\mathbf{h})^T= \mathbf{h}^T B^T \mathbf{x}=\mathbf{h}^TB\mathbf{x}=\mathbf{h}^T\mathbf{c}.$$

Uvrštavanje u $Q(\mathbf{y})$ daje

$$Q(\mathbf{y})=\mathbf{x}^TB\mathbf{x}+\mathbf{h}^TB\mathbf{h}-2\mathbf{x}^T\mathbf{c}+\beta=Q(\mathbf{x})+\mathbf{h}^TB\mathbf{h}.$$

Izraz $\mathbf{h}^TB\mathbf{h}$ je veći ili jednak od nule:

$$\mathbf{h}^TB\mathbf{h}=\mathbf{h}^TA^TA\mathbf{h}=(A\mathbf{h})^TA\mathbf{h}=\Vert A\mathbf{h}\Vert^2.$$

Dakle, uvijek je

$$Q(\mathbf{y})\geq Q(\mathbf{x}),$$

odnosno vrijednost $Q(\mathbf{x})$ je zaista najmanja moguća.

Dokažimo sada da je rješenje $\mathbf{x}$ jedinstveno. Ako je

$$Q(\mathbf{y})=Q(\mathbf{x}),\qquad \mathbf{x}\neq \mathbf{y},$$

onda je $\Vert A\mathbf{h}\Vert=0$ . No, onda je i $A\mathbf{h}=0$ (samo nul-vektor ima normu jednaku nula), što zajedno s $\mathbf{h}=\mathbf{y}-\mathbf{x}\neq \mathbf{0}$ znači da su stupci matrice $A$ linearno zavisni. To je kontradikcija pa je teorem dokazan.

Q.E.D.

Primijetimo da su vektori $A\mathbf{x}$ i $A\mathbf{x} - \mathbf{b}$ međusobno okomiti:

$$(A\mathbf{x})\cdot (A\mathbf{x} - \mathbf{b})=(A\mathbf{x})^T(A\mathbf{x} - \mathbf{b})=\mathbf{x}^T A^T(A\mathbf{x} - \mathbf{b})=0.$$

Geometrijski to znači da je vektor $A\mathbf{x}$ ortogonalna projekcija vektora $\mathbf{b}$ na skup $\{A\mathbf{y}: \mathbf{y} \textrm{ proizvoljan}\}$ . Nadalje, vektori $A\mathbf{x}$ , $\mathbf{b}$ i $A\mathbf{x} - \mathbf{b}$ tvore pravokutni trokut s hipotenuzom $\mathbf{b}$ .

Rješenje problema najmanjih kvadrata $\mathbf{x}$ zove se još i kvadratična prilagodba sustavu $A\mathbf{x}=\mathbf{b}$ u smislu najmanjih kvadrata. Kvalitetu prilagodbe mjerimo s

$$q=\sqrt{\frac{Q(\mathbf{x})}{(Q(\mathbf{0})}}=\frac{\Vert A\mathbf{x} - \mathbf{b}\Vert}{\Vert\mathbf{b}\Vert }.$$

Iz činjenice da je $\mathbf{b}$ hipotenuza pravokutnog trokuta sa stranicama $A\mathbf{x}$ , $A\mathbf{x} - \mathbf{b}$ i $\mathbf{b}$ slijedi da je $\mathbf{q}$ uvijek između 0 i 1. Ako je $q=0$ , onda je prilagodba najbolja moguća, odnosno $\mathbf{x}$ je točno rješenje sustava $A\mathbf{x}=\mathbf{b}$ . Ukoliko je $q$ mali, prilagodba je dobra, a ukoliko je $q$ blizu jedan, prilagodba je loša.

Primjer 6.1   Riješimo sustav

$$x+y =0$$

$$y+z =1$$

$$x+z =0$$

$$-x+y+z =1$$

$$-x-z =0$$

u smislu najmanjih kvadrata. U matričnom obliku sustav glasi

$$\begin{bmatrix}1& 1 &0\\ 0 & 1 & 1\\ 1 & 0 & 1\\ -1 & 1 & 1... ...matrix}x y z \end{bmatrix}=\begin{bmatrix}0 1 0 1 0 \end{bmatrix}.$$

Normalna jednadžba glasi

$$\begin{bmatrix} 4 & 0 & 1\\ 0 & 3 & 2\\ 1 & 2 & 4 \end{bmatrix}\begin{bmatrix}x y z \end{bmatrix}=\begin{bmatrix}-1 2 2 \end{bmatrix}$$

pa je rješenje dano s

$$x=-\frac{10}{29},\qquad y=\frac{12}{29}, \qquad z=\frac{11}{29}.$$

Kvaliteta prilagodbe je

$$q=0.1857$$

Odgovarajući Matlab program glasi

Octave On-line

A = [1 1 0; 0 1 1; 1 0 1; -1 1 1; -1 0 -1] b=[0 1 0 1 0]' B=A'*A c=A'*b x=B\c % ili krace x=A\b q=norm(A*x-b)/norm(b)

     

[Octave On-line Home]    [Octave User's Guide]

Primjer 6.2   Kroz točke

$$\begin{tabular}{r\vert lllll} x& 1 & 2 & 4 & 5 & 6 \hline y& 0 & 1 & 4 & 8 & 14 \end{tabular}$$

provucimo kvadratnu parabolu

$$y=ax^2+bx+c$$

koja ima najbolju kvadratičnu prilagodbu. Dakle, moramo naći koeficijente parabole tako da je

$$\sum_{i=1}^5 (y_i-axi^2-bx_i-c)^2 \to \min.$$

Ovaj problem možemo zapisati kao problem najmanjih kvadrata

$$\begin{bmatrix}1 & 1 & 1 \\ 4 & 2 & 1 16 & 4 & 1 25 & 5 & 1\... ...x}a b c \end{bmatrix}=\begin{bmatrix}0 1 4 8 14 \end{bmatrix}.$$

Rješavanje normalne jednadžbe daje

$$\begin{bmatrix}a b c \end{bmatrix} \approx \begin{bmatrix} 0.68994\\ -2.16071\\ 1.86364 \end{bmatrix},$$

a kvaliteta prilagodbe iznosi $q=0.0562$ . Zadane točke i dobivena parabola prikazane su na slici 6.3.

Slika 6.3: Parabola s najboljom prilagodbom

Parabola i slike mogu se dobiti sljedećim Matlab programom

Octave On-line

A = [1 1 1 4 2 1 16 4 1 25 5 1 36 6 1] y = [0 1 4 8 14]' % rjesenje xLS=A\y % kvaliteta prilagodbe q=norm(A*xLS-y)/norm(y) % slike x=[1 2 4 5 6]' plot(x,y,'r*') hold % gusca mreza radi bolje slike parabole x1=1:0.1:6 y1=xLS(1)*x1.^2+xLS(2)*x1+xLS(3) plot(x1,y1,'b')

     

[Octave On-line Home]    [Octave User's Guide]

Napomena 6.2   Vidimo da je puni stupčani rang matrice $A$ nužan za funkcioniranje metode normalnih jednadžbi, jer bi u protivnom matrica $B=A^TA$ bila singularna. Ako matrica $A$ nema puni stupčani rang, onda rješenje problema najmanjih kvadrata nije jedinstveno i za rješavanje problema ne može se koristiti normalna jednadžba. U tom slučaju od svih mogućih (beskonačno) rješenja, zanima nas ono koje samo po sebi ima najmanju normu. Za rješavanje takvih problema koristimo ili QR rastav s pivotiranjem po stupcima ili rastav singularnih vrijednosti (SVD ili singular value decomposition). Nadalje, ove dvije metode je zbog njihovih svojstava (numeričke stabilnosti) poželjno koristiti i kada su stupci matrice $A$ gotovo linearno zavisni. Detaljna analiza ovih slučajeva izlazi izvan okvira kolegija, pa je izostavljamo.

Zadatak 6.3   Za rast svjetske populacije prema podacima iz tablice 5.1 u primjeru 5.3 odredite parametre $C$ i $k$ za koje funkcija $P(t)=C e^{k(t-1950)}$ najbolje aproksimira podatke od 1950.-2050. godine u smislu najmanjih kvadrata. Nacrtajte sliku i usporedite sa slikom 5.5. Predvidite populaciju 2050. godine.

Linearna regresija     Problem najmanjih kvadrata     Problem najmanjih kvadrata s