Metoda nejmenších čtverců

Z Wikipedie, otevřené encyklopedie

 Graf, na kterém byla experimentální data zjištěna s obrovskou chybou, přičemž daná závislost (nalezená metodou nejmenších čtverců) proměnné y na x je kvadratická.
Graf, na kterém byla experimentální data zjištěna s obrovskou chybou, přičemž daná závislost (nalezená metodou nejmenších čtverců) proměnné y na x je kvadratická.

Metoda nejmenších čtverců je matematická metoda, určená ke statistickému zpracování dat. Jejím úkolem je nalézt vhodnou aproximační funkci pro dané empiricky zjištěné hodnoty. Algebraický tvar takové funkce nám ale musí být znám již před aplikováním metody nejmenších čtverců.

Obecně řečeno, metoda nejmenších čtverců slouží k nalezení takového řešení, aby součet druhých mocnin chyb nalezeného řešení byl minimální. (Lidově, „aby součet čtverců odchylek byl nejmenší“.)

Obsah

[editovat] Jak přesně funguje metoda nejmenších čtverců?

Pro první přiblížení uvažujme závislost jisté proměnné y na proměnné x, danou nějakým předpisem y = f(x). Pokud námi uvažovaná závislost má očekávaný tvar, např. f(x) = ax + b (lineární závislost), mohlo by se zdát, že postačí pouze vybrat dvě dvojice [x,y] naměřených hodnot a řešením soustavy dvou rovnic (dosazením dané dvojice hodnot) získat jednoduše koeficienty a, b, které hledáme. Není tomu tak, a to z důvodu chyby měření. V kostce řečeno:

Metoda nejmenších čtverců hledá takové hodnoty koeficientů, aby součet čtverců „odchylek“ (správně reziduí, definice pojmu je mimo rozsah článku) jejích funkčních hodnot od daných naměřených hodnot byl nejmenší možný.

[editovat] Příklad: aplikace metody nejmenších čtverců na lineární závislost (metoda lineární regrese)

Uvažujme funkční závislost: f(x) = ax + b

Součet čtverců pak bude vypadat takto:

S(a, b) = \sum_{i=1}^{n} {[f(x_i)-y_i]^2} = \sum_{i=1}^{n} {(a x_i + b - y_i)^2 }

Abychom našli minimum součtu (našli koeficienty a, b tak, aby nalezená závislost vhodně aproximovala daná data), položíme obě parciální derivace součtu čtverců rovny nule:

0 = { \partial S \over \partial a} = 2 \sum_{i=1}^{n} (ax_i + b - y_i)x_i
0 = { \partial S \over \partial b} = 2 \sum_{i=1}^{n} (ax_i + b - y_i)

Úpravami obdržíme soustavu:

a\sum_{i=1}^{n} {x_i^2} + b\sum_{i=1}^{n} {x_i} = \sum_{i=1}^{n} x_i y_i
a\sum_{i=1}^{n} {x_i} + bn = \sum_{i=1}^{n} y_i

Jejím řešením pro konkrétní hodnoty xi a yi dostaneme konečně hledané hodnoty parametrů a a b.

a = \frac{n \sum{x_i y_i} - \sum{x_i} \sum{y_i}}{n \sum{x_i^2} - \left( \sum{x_i} \right)^2}
b = \frac{\sum{x_i^2}\sum{y_i} - \sum{x_i}\sum{x_i y_i}}{n \sum{x_i^2} - \left(\sum{x_i}\right)^2}

Dá se ukázat, že matice této soustavy je regulární pro všechna n \geq 2, a má tedy právě jedno řešení. Obecně se dá také ukázat, že v tomto bodě má součet čtverců minimum.

Podobný postup lze aplikovat na jakýkoliv druh závislosti i více proměnných.

[editovat] Příklad: Aproximace bodů parabolou

Cílem příkladu je proložit skupinu n bodů [xi;yi] parabolou, tedy polynomem druhého řádu f(x) = ax2 + bx + c. Tento příklad je velmi podobný předchozímu (přímka v předchozím příkladu je vlastně polynom prvního řádu) a jeho ukázka je na obrázku v úvodu článku.

Ukázka aproximace zadaných bodů polynomem libovolného řádu.
Ukázka aproximace zadaných bodů polynomem libovolného řádu.

Součet čtverců odchylek S závisí na parametrech a, b, c.

S(a,b,c) = \sum_{i=1}^{n}{\left(a x_i^2 + b x_i + c - y_i\right)^2}

Aby byl tento součet minimální, musí být jeho parciální derivace rovny nule.

\frac{\partial S}{\partial a} = \frac{\partial S}{\partial b} = \frac{\partial S}{\partial c} = 0

Uvedeným postupem lze odvodit soustavu lineárních rovnic, ze které již není problém vypočítat koeficienty a, b, c.

\begin{matrix} a \sum{x_i^4} & + & b \sum{x_i^3} & + & c \sum{x_i^2} & = & \sum{y_i x_i^2} \\ a \sum{x_i^3} & + & b \sum{x_i^2} & + & c \sum{x_i} & = & \sum{y_i x_i} \\ a \sum{x_i^2} & + & b \sum{x_i} & + & c \cdot n & = & \sum{y_i} \end{matrix}

Porovnáním se soustavou rovnic odvozenou pro aproximaci přímkou f(x) = ax + b je zřejmé, jak by vypadala soustava rovnic pro aproximaci polynomem libovolného řádu.

[editovat] Metoda nejmenších čtverců a soustava lineárních rovnic

Pokud máme soustavu lineárních rovnic ve tvaru Ax = b (A je matice, kterou známe, b je vektor a také jej známe, x je neznámý vektor), mohou nastat tři situace:

  • Matice A je čtvercová, vektor b má stejný rozměr jako vektor x a máme tak k dispozici stejný počet rovnic jako neznámých. V tomto případě lze vypočítat x například pomocí inverzní matice x = A-1b.
  • Matice A má větší počet sloupců než řádků, vektor b má menší rozměr než vektor x. Jedná se o nedourčenou soustavu rovnic, která má více neznámých než rovnic.
  • Matice A má větší počet řádků než sloupců, vektor b má větší rozměr než vektor x. Jedná se o přeurčenou soustavu rovnic, která má více rovnic než neznámých. V tomto případě je teoreticky možné některé rovnice zanedbat, ale předpokládejme, že rovnice jsou získány z experimentálních dat, u kterých si ceníme každého měření a nejsme schopni rozhodnout, kterou pracně získanou rovnici zanedbat.

V případech s nedourčenou (respektive přeurčenou) soustavou lineárních rovnic platí, že taková soustava má nekonečně mnoho (respektive žádné) řešení. Řekněme, že nás taková skutečnost neuspokojuje a definujeme chybu řešení.

\bold e = \bold A \bold x - \bold b

Chceme najít takové řešení x, aby tato chyba (respektive velikost vektoru e) byla minimální. V následujících dvou podkapitolách jsou uvedeny dva různé způsoby odvození řešení x. Následující matematické úpravy nejsou úplne korektní, ale v běžné praxi je možné je použít.

[editovat] Derivace matic a vektorů

Protože e je vektor, upravme tento požadavek tak, aby „součet čtverců jednotlivých odchylek (tedy složek vektoru e) byl minimální“. Při takovém způsobu formulace kritéria se vlastně jedná minimalizaci skalárního součinu, který můžeme napsat pomocí transpozice.

\bold e \cdot \bold e = \bold e^T \bold e \to min

Součin bude minimální tehdy, když jeho derivace podle proměnné x bude rovna nule.

\left( \bold e^T \bold e \right)' = \left[ \left(\bold{Ax-b}\right)^T\left(\bold{Ax-b}\right) \right]' = 0

Pomocí pravidel pro transpozici součinu a derivaci součinu matic a vektorů můžeme vztah dále upravovat.

\left[ \bold x^T \bold A^T \bold{Ax} - \bold x^T \bold A^T \bold b - \bold b^T \bold{Ax} + \bold b^T \bold b\right]' = 2 \bold A^T \bold{Ax} - 2 \bold A^T \bold b = 0

Z výše uvedeného vztahu lze již vyjádřit výsledný vzorec pro x.

\bold x = \left( \bold A^T \bold A \right)^{-1} \bold A^T \bold b

[editovat] Kolmé vektory

Stejný vzorec lze odvodit pomocí jiné úvahy bez derivování. Je zřejmé, že výsledkem součinu Ax je vektor o stejném rozměru jako vektor b, přičemž v ideálním případě jsou tyto dva vektory totožné. Bohužel, v našem neideálním případě vektory totožné nejsou a odchylka je dána vektorem e = Ax – b, jehož velikost chceme minimalizovat.

Při nákresu dané situace v dvourozměrné rovině lze vypozorovat, že vektor e bude nejkratší, pokud bude kolmý na vektor Ax. V takovém případě bude skalární součin těchto dvou vektorů nulový.

\bold e \cdot \bold {Ax} = \bold e^T \bold{Ax} = 0

Tento vztah lze dále upravit.

\left(\bold x^T \bold A^T - \bold b^T\right) \bold{Ax} = \bold x^T \bold A^T \bold{Ax} - \bold b^T \bold{Ax} = \left( \bold x^T \bold A^T \bold A - \bold b^T \bold A \right) \bold x = 0

Poslední součin bude roven nule ve dvou případech.

  • x = 0, to obvykle není řešení, které nás zajímá
  • \bold x^T \bold A^T \bold A = \bold b^T \bold A

Druhou variantu je možné transponovat a pomocí inverzní matice vyjádřit x.

\bold x = \left( \bold A^T \bold A \right)^{-1} \bold A^T \bold b

[editovat] Příklad: Přeurčená soustava lineárních rovnic

Následující přeurčená soustava tří lineárních rovnic pro dvě neznámé nemá řešení.

 x + y = 0      (1)
2x - y = 4      (2)
 x - y = 2      (3)

V případě, že bysme řešili pouze soustavu rovnic (1) a (2), získali bysme řešení [1.333; -1.333]. Řešení rovnic (2) a (3) je [2; 0]. Řešení rovnic (1) a (3) je [1; -1].

Řešení přeurčené soustavy lineárních rovnic metodou nejmenších čtverců
Řešení přeurčené soustavy lineárních rovnic metodou nejmenších čtverců

Soustavu rovnic můžeme modifikovat.

 x + y - 0 = e1
2x - y - 4 = e2
 x - y - 2 = e3

A můžeme se alespoň pokusit najít takový bod [x; y], aby součet druhých mocnin odchylek e_1^2 + e_2^2 + e_3^2 byl minimální.

V maticovém tvaru bude soustava vypadat následovně.

\bold A \bold x - \bold b = \bold e
\left[ \begin{matrix} 1 & 1 \\ 2 & -1 \\ 1 & -1 \end{matrix} \right] \cdot \left[ \begin{matrix} x \\ y \end{matrix} \right] - \left[ \begin{matrix} 0 \\ 4 \\ 2 \end{matrix} \right] = \left[ \begin{matrix} e_1 \\ e_2 \\ e_3 \end{matrix} \right]
\bold x = \left( \bold A^T \bold A \right)^{-1} \bold A^T \bold b \doteq \left[ \begin{matrix} 1.286 \\ -1.143 \end{matrix} \right]

[editovat] Externí odkazy