$\newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\R}{\mathbb R} \newcommand{\C}{\mathbb C} \newcommand{\ba}{\mathbf{a}} \newcommand{\bb}{\mathbf{b}} \newcommand{\bc}{\mathbf{c}} \newcommand{\bd}{\mathbf{d}} \newcommand{\be}{\mathbf{e}} \newcommand{\bff}{\mathbf{f}} \newcommand{\bh}{\mathbf{h}} \newcommand{\bi}{\mathbf{i}} \newcommand{\bj}{\mathbf{j}} \newcommand{\bk}{\mathbf{k}} \newcommand{\bN}{\mathbf{N}} \newcommand{\bn}{\mathbf{n}} \newcommand{\bo}{\mathbf{0}} \newcommand{\bp}{\mathbf{p}} \newcommand{\bq}{\mathbf{q}} \newcommand{\br}{\mathbf{r}} \newcommand{\bs}{\mathbf{s}} \newcommand{\bT}{\mathbf{T}} \newcommand{\bu}{\mathbf{u}} \newcommand{\bv}{\mathbf{v}} \newcommand{\bw}{\mathbf{w}} \newcommand{\bx}{\mathbf{x}} \newcommand{\by}{\mathbf{y}} \newcommand{\bz}{\mathbf{z}} \newcommand{\bzero}{\mathbf{0}} \newcommand{\nv}{\mathbf{0}} \newcommand{\cA}{\mathcal{A}} \newcommand{\cB}{\mathcal{B}} \newcommand{\cC}{\mathcal{C}} \newcommand{\cD}{\mathcal{D}} \newcommand{\cE}{\mathcal{E}} \newcommand{\cF}{\mathcal{F}} \newcommand{\cG}{\mathcal{G}} \newcommand{\cH}{\mathcal{H}} \newcommand{\cI}{\mathcal{I}} \newcommand{\cJ}{\mathcal{J}} \newcommand{\cK}{\mathcal{K}} \newcommand{\cL}{\mathcal{L}} \newcommand{\cM}{\mathcal{M}} \newcommand{\cN}{\mathcal{N}} \newcommand{\cO}{\mathcal{O}} \newcommand{\cP}{\mathcal{P}} \newcommand{\cQ}{\mathcal{Q}} \newcommand{\cR}{\mathcal{R}} \newcommand{\cS}{\mathcal{S}} \newcommand{\cT}{\mathcal{T}} \newcommand{\cU}{\mathcal{U}} \newcommand{\cV}{\mathcal{V}} \newcommand{\cW}{\mathcal{W}} \newcommand{\cX}{\mathcal{X}} \newcommand{\cY}{\mathcal{Y}} \newcommand{\cZ}{\mathcal{Z}} \newcommand{\pv}{\overline} \newcommand{\re}{\operatorname{Re}} \newcommand{\im}{\operatorname{Im}} \newcommand{\arsinh}{\operatorname{ar\,sinh}} \newcommand{\arcosh}{\operatorname{ar\,cosh}} \newcommand{\artanh}{\operatorname{ar\,tanh}} \newcommand{\diag}{\operatorname{diag}} \newcommand{\proj}{\operatorname{proj}} \newcommand{\rref}{\operatorname{rref}} \newcommand{\rank}{\operatorname{rank}} \newcommand{\Span}{\operatorname{span}} \newcommand{\vir}{\operatorname{span}} \renewcommand{\dim}{\operatorname{dim}} \newcommand{\alg}{\operatorname{alg}} \newcommand{\geom}{\operatorname{geom}} \newcommand{\id}{\operatorname{id}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\tp}[1]{#1^{\top}} \renewcommand{\d}{\mathrm{d}} \newcommand{\sij}[2]{\bigg/_{\mspace{-15mu}#1}^{\,#2}} \newcommand{\qedhere}{} \newcommand{\taumatrix}[1]{\left[\!\!#1\!\!\right]} \newenvironment{augmatrix}[1]{\left[\begin{array}{#1}}{\end{array}\right]} \newenvironment{vaugmatrix}[1]{\left|\begin{array}{#1}}{\end{array}\right|}$

# Pienimmän neliösumman menetelmä¶

Määritelmä 7.2.1

Olkoon $$A$$ jokin $$m\times n$$-matriisi ja $$\bb$$ avaruuden $$\R^m$$ vektori. Tällöin yhtälöryhmän $$A\bx=\bb$$ pienimmän neliösumman ratkaisu (least squares solution) on avaruuden $$\R^n$$ vektori $$\overline{\bx}$$, joka toteuttaa epäyhtälön

$\|\bb-A\overline{\bx}\|\le \|\bb-A\bx\|$

aina, kun $$\bx\in\R^n$$.

Jos yhtälöryhmällä $$A\bx=\bb$$ ei ole ratkaisua, niin $$\bb\not\in \cR(A)$$. Pienimmän neliösumman ratkaisu on sellainen vektori $$\overline{\bx}$$, että vektori $$A\overline{\bx}\in \cR(A)$$ on ikään kuin lähimpänä vektoria $$\bb$$. Nyt kun periaate on selvä, tarvitsee enää tietää, miten $$\overline{\bx}$$ lasketaan.

Aloitetaan pohtimalla, miten voitaisiin laskea pisteen $$\bb$$ kohtisuora etäisyys tasosta $$S$$. Ongelman ratkaisemiseksi tarvitaan jokin vektori $$\bv$$ tasolta $$S$$ pisteeseen $$\bb$$, joka tämän jälkeen projisoidaan tason normaalille $$\bn$$. Haluttu etäisyys on vektorin $$\proj_{\bn}(\bv)$$ normi. Toisin muotoiltuna tehtävän ratkaisu on tasolta $$S$$ kohtisuorasti pisteeseen $$\bb$$ kulkevan vektorin $$\bb - \proj_{S}(\bb)$$ pituus. Tämä tarkoittaa edelleen, että $$\bb - (\bb - \proj_{S}(\bb)) = \proj_{S}(\bb)$$ on vektoria $$\bb$$ lähimmäksi sijoittuva tason $$S$$ vektori.

Huomautus 7.2.2

Merkinnällä $$\proj_{S}(\bb)$$ tarkoitetaan vektorin $$\bb$$ projektiota aliavaruudelle $$S$$. Se voitaisiin laskea kirjoittamalla aliavaruuden yleinen vektori kantavektorien lineaarikombinaationa, ja käyttämällä sitten tavallisen vektoriprojektion kaavaa.

Korvaamalla edellisessä pohdinnassa tason $$S$$ matriisin $$A$$ sarakeavaruudella $$\cR(A)$$ nähdään, että $$\proj_{\cR(A)}(\bb)$$ on lähimmäksi vektoria $$\bb$$ sijoittuva aliavaruuden $$\cR(A)$$ vektori. Normi $$\|\bb - \proj_{\cR(A)}(\bb)\|$$ on siis pienin mahdollinen, eli $$A\overline{\bx} = \proj_{\cR(A)}(\bb)$$, kun $$\overline{\bx}$$ on yhtälöryhmän $$A\bx = \bb$$ pienimmän neliösumman ratkaisu. Nyt projektion laskemiseksi havaitaan, että $$\bb - A\overline{\bx}$$ on ortogonaalinen mielivaltaista aliavaruuden $$\cR(A)$$ vektoria vasten. Erityisesti siis $$\ba_j \cdot (\bb - A\overline{\bx}) = \tp{\ba_j}(\bb - A\overline{\bx}) = 0$$, kun $$\ba_j$$ on $$m \times n$$-matriisin $$A$$ sarake. Keräämällä kaikki $$n$$ tällaista yhtälöä yhteen nähdään, että

$\begin{split}\bzero = \begin{augmatrix}{c} 0 \\ 0 \\ \vdots \\ 0 \end{augmatrix} = \begin{augmatrix}{c} \tp{\ba_1}(\bb - A\overline{\bx}) \\ \tp{\ba_2}(\bb - A\overline{\bx}) \\ \vdots \\ \tp{\ba_n}(\bb - A\overline{\bx}) \end{augmatrix} = \begin{augmatrix}{c} \tp{\ba_1} \\ \tp{\ba_2} \\ \vdots \\ \tp{\ba_n} \end{augmatrix}(\bb - A\overline{\bx}) = \tp{\begin{augmatrix}{cccc} \ba_1 & \ba_2 & \cdots & \ba_n \end{augmatrix}}(\bb - A\overline{\bx}) = \tp{A}(\bb - A\overline{\bx}).\end{split}$

Pienimmän neliösumman ratkaisu $$\overline{\bx}$$ siis toteuttaa aina yhtälöryhmän $$\tp{A}A\bx = \tp{A}\bb$$.

Määritelmä 7.2.3

Yhtälöryhmän $$A\bx = \bb$$ normaaliryhmä on $$\tp{A}A\bx = \tp{A}\bb$$.

Oletetaan, että $$A \in \R^{m \times n}$$ ja $$\bb \in \R^m$$. Valitse paikkansa seuraavista pitävät väittämät. Jos yhtälöryhmällä $$A\bx = \bb$$ ei ole ratkaisuja ja $$\hat{\bx}$$ on pienimmän neliösumman ratkaisu, niin

Käy ilmi, että normaaliryhmällä on aina ratkaisuja, ja jokainen näistä on myös pienimmän neliösumman ratkaisu. Tämän osoittamiseksi lähestytään ongelmaa teoreettisemmin seuraavasta näkökulmasta. Jos matriisiyhtälössä $$A\bx = \bb$$ matriisi $$A$$ ei ole kääntyvä, voidaan silti yrittää löytää mahdollisimman hyvin käänteismatriisin käyttäytymistä imitoiva matriisi. Tällaista matriisia kutsutaan pseudoinverssiksi. Seuraava tulos otetaan käyttöön todistamatta.

Jos $$A$$ on $$m \times n$$-matriisi, niin on olemassa yksikäsitteinen $$n \times m$$-matriisi $$A^+$$, joka toteuttaa ehdot

1. $$AA^+A = A$$,
2. $$A^+AA^+ = A^+$$,
3. $$\tp{(AA^+)} = AA^+$$
4. $$\tp{(A^+A)} = A^+A$$.

Matriisia $$A^+$$ sanotaan matriisin $$A$$ Moore-Penrosen pseudoinverssiksi.

Lemma 7.2.5

Jos $$A$$ on $$m \times n$$-matriisi, niin $$\cR(\tp{A}A) = \cR(\tp{A})$$.

Todistus

Oletetaan, että $$\by \in \cR(\tp{A}A)$$. Tällöin $$\by = \tp{A}A\bx$$ jollekin avaruuden $$\R^n$$ vektorille $$\bx$$ ja $$A\bx = \bz$$ on avaruuden $$\R^m$$ vektori. Täten $$\by = \tp{A}\bz$$ jollekin avaruuden $$\R^m$$ vektorille $$\bz$$, eli $$\by \in \cR(\tp{A})$$.

Oletetaan sitten, että $$\by \in \cR(\tp{A})$$, eli $$\by = \tp{A}\bx$$ jollekin avaruuden $$\R^m$$ vektorille $$\bx$$. Sijoitetaan matriisin $$A$$ paikalle Moore-Penrosen pseudoinverssin $$A^+$$ sisältävä matriisitulo edellisen lauseen ensimmäisen ehdon mukaisesti ja sovelletaan muitakin pseudoinverssin ominaisuuksia.

$\by = \tp{(AA^+A)}\bx = \tp{A}\tp{(AA^+)}\bx = \tp{A}(AA^+)\bx = (\tp{A}A)A^+\bx$

Tässä $$A^+\bx = \bz$$ on avaruuden $$\R^n$$ vektori, jolle $$\by = \tp{A}A\bz$$, ja täten $$\by \in \cR(\tp{A}A)$$.

Edellä olevista päättelyistä seuraa, että $$\cR(\tp{A}A) \subseteq \cR(\tp{A})$$ ja $$\cR(\tp{A}) \subseteq \cR(\tp{A}A)$$, joten $$\cR(\tp{A}A) = \cR(\tp{A})$$.

Nyt voidaan lopulta osoittaa, että yhtälöryhmän $$A\bx = \bb$$ normaaliryhmällä $$\tp{A}A\bx = \tp{A}\bb$$ on aina vähintään yksi ratkaisu.

Lause 7.2.6

Olkoon $$A$$ $$m\times n$$-matriisi ja $$\bb\in\R^m$$. Tällöin normaaliryhmällä $$\tp{A}A\bx = \tp{A}\bb$$ on ratkaisu $$\overline{\bx}$$, joka on myös yhtälöryhmän $$A\bx = \bb$$ pienimmän neliösumman ratkaisu.

Todistus

Vektori $$\tp{A}\bb$$ kuuluu luonnollisesti matriisin $$\tp{A}$$ sarakeavaruuteen $$\cR(\tp{A})$$. Edellisen lemman nojalla siis $$\tp{A}\bb \in \cR(\tp{A}A)$$, ja täten normaaliryhmällä $$\tp{A}A\bx = \tp{A}\bb$$ on ratkaisu $$\overline{\bx}$$. Olkoon nyt $$\bx$$ avaruuden $$\R^n$$ vektori ja tarkastellaan normin neliötä

$\|\bb - A\bx\|^2 = \|\bb - A\overline{\bx} + A\overline{\bx} - A\bx\|^2 = \|\bb - A\overline{\bx}\|^2 + \|A(\overline{\bx} - \bx)\|^2 + 2A(\overline{\bx} - \bx) \cdot (\bb - A\overline{\bx}).$

Pistetulo voidaan kirjoittaa matriisitulona, jolloin

$\|\bb - A\bx\|^2 = \|\bb - A\overline{\bx}\|^2 + \|A(\overline{\bx} - \bx)\|^2 + 2\tp{(\overline{\bx} - \bx)}(\tp{A}\bb - \tp{A}A\overline{\bx}) = \|\bb - A\overline{\bx}\|^2 + \|A(\overline{\bx} - \bx)\|^2,$

sillä $$\overline{\bx}$$ on normaaliryhmän ratkaisu. Täten

$\|\bb - A\bx\|^2 \geq \|\bb - A\overline{\bx}\|^2,$

eli $$\|\bb - A\overline{\bx}\| \leq \|\bb - A\bx\|$$, mielivaltaista vektoria $$\bx$$ kohti, ja näin $$\overline{\bx}$$ on yhtälöryhmän $$A\bx = \bb$$ pienimmän neliösumman ratkaisu.

Pienimmän neliösumman ratkaisu on siis aina olemassa, ja edellinen lause tarjoaa keinon löytää sen. Ratkaisun residuaaliksi, eli virhevektoriksi kutsutaan vektoria $$\br = \bb - A\overline{\bx}$$, ja ratkaisun virhe on tämän normi $$\|\br\| = \|\bb - A\overline{\bx}\|$$. Jos alkuperäisellä yhtälöryhmällä on ratkaisuja, niin pienimmän neliösumman ratkaisun virhe on $$0$$.

Huomautus 7.2.7

Pienimmän neliösumman ratkaisun olemassaolo ei tarkoita sitä, että se olisi yksikäsitteinen. On hyvinkin mahdollista, että matriisi normaaliryhmän kerroinmatriisi $$\tp{A}A$$ ei ole kääntyvä, ja tällöin normaaliryhmällä on ääretön määrä ratkaisuja.

Varmistetaan vielä, että pienimmän neliösumman ratkaisu toimii kuten yhtälön $$A\bx = \bb$$ tarkkakin ratkaisu ainakin seuraavan lauseen mielessä.

Lause 7.2.8

Olkoon $$\overline{\bx}$$ yhtälöryhmän $$A\bx = \bb$$ pienimmän neliösumman ratkaisu. Jos yhtälöryhmällä $$A\bx=\bb$$ on ratkaisuja, niin tällöin myös $$\overline{\bx}$$ on sen ratkaisu.

Todistus
Koska yhtälöryhmällä on ratkaisuja, löydetään vektori $$\bx$$, jolle $$\|\bb - A\bx\| = 0$$. Koska pienimmän neliösumman ratkaisu minimoi yhtälön vasemman puolen lausekkeen, on oltava $$\|\bb - A\overline{\bx}\| = 0$$. Ainoastaan nollavektorin normi on nolla, joten $$\bb - A\overline{\bx} = \bzero$$ ja edelleen $$A\overline{\bx} = \bb$$.
Oletetaan, että $$A \in \R^{m \times n}$$, $$\bb \in \R^m$$ ja $$\bx \in \R^n$$. Valitse paikkansa pitävät väittämät yhtälön $$A\bx = \bb$$ pienimmän neliösumman ratkaisuille $$\hat{\bx}$$.

Normaaliryhmä $$\tp{A}A\bx=\tp{A}\bb$$ voidaan ratkaista Gaussin–Jordanin menetelmällä, kuten mikä tahansa muukin yhtälöryhmä. Erityisen kiintoisa tapaus syntyy silloin, kun ratkaisu on yksikäsitteinen, eli kerroinmatriisi $$\tp{A}A$$ on kääntyvä. Tällöin pienimmän neliösumman ratkaisuksi tulee

$\overline{\bx}=(\tp{A}A)^{-1}\tp{A}\bb.$

Moore-Penrosen pseudoinverssi sattuu tässä tapauksessa olemaan täsmälleen se matriisi, joka “kääntää” matriisin $$A$$: jos $$\tp{A}A$$ on kääntyvä, niin $$A^+ = (\tp{A}A)^{-1}\tp{A}$$ ja pienimmän neliösumman ratkaisu on $$\overline{\bx} = A^+\bb$$.

Lause 7.2.9

Olkoon $$A$$ $$m \times n$$-matriisi. Tällöin seuraavat väitteet ovat voimassa.

1. Jos $$\tp{A}A$$ on kääntyvä, niin $$A^+A = I_n$$.
2. Jos $$A$$ on kääntyvä, niin $$A^+ = A^{-1}$$.
Todistus
Jätetään harjoitustehtäväksi.

Käänteismatriisia $$(\tp{A}A)^{-1}$$ kutsutaan yhtälöryhmän $$A\bx = \bb$$ normalisoivaksi kertoimeksi, ja sen olemassaololle löydetään riittävä ja välttämätön ehto.

Lause 7.2.10

Normalisoiva kerroin $$(\tp{A}A)^{-1}$$ on olemassa täsmälleen silloin, kun matriisin $$A$$ sarakkeet ovat lineaarisesti riippumattomat.

Todistus

Tiedetään, että $$m \times n$$-matriisin $$A$$ sarakkeet ovat lineaarisesti riippumattomat täsmälleen silloin, kun $$\rank(A) = n$$. Vastaavasti $$n \times n$$-matriisi $$\tp{A}A$$ on kääntyvä jos ja vain jos $$\rank(\tp{A}A)=n$$. Mutta lemman 7.2.5 nojalla $$\cR(\tp{A}A) = \cR(\tp{A})$$, joten

$\rank(\tp{A}A) = \rank(\tp{A}) = \rank(A) = n,$

ja väite on todistettu.

Tarkastellaan seuraavaa väitettä: pienimmän neliösumman mielessä mille tahansa matriisille $$A$$ yhtälöryhmän $$A\bx = \bb$$ paras ratkaisu on $$\hat{\bx} = (\tp{A}A)^{-1}\tp{A}\bb$$. Milloin väite on tosi?

Olkoon $$A$$ mikä tahansa matriisi, jonka sarakkeet ovat lineaarisesti riippumattomia. Tarkastellaan matriisia $$A^{+} = (\tp{A}A)^{-1}\tp{A}$$. Onko laskussa

$AA^{+} = A(\tp{A}A)^{-1}\tp{A} = AA^{-1}(\tp{A})^{-1}\tp{A} = II = I$

kaikki välivaiheet oikein?

Esimerkki 7.2.11

Tutki yhtälöryhmän

$\begin{split}\begin{cases} x+5y = 3\\ 2x-2y = 2\\ -x+y =5 \end{cases}\end{split}$

ratkaisujen olemassaoloa. Jos ratkaisuja ei ole, etsi residuaalin normin minimoiva approksimaatio ryhmän ratkaisulle. Jos tämä arvio on yksikäsitteinen, etsi yhtälöryhmän kerroinmatriisille Moore-Penrosen pseudoinverssi.

Ratkaisu

Viedään yhtälöryhmän kokonaismatriisi redusoituun riviporrasmuotoon.

$\begin{split}[A\mid\bb]= \begin{augmatrix}{rr|c} 1 & 5& 3\\ 2 & -2 & 2\\ -1 & 1 &5 \end{augmatrix}\longrightarrow \rref[A\mid\bb]= \begin{augmatrix}{cc|c} 1 & 0& 0\\ 0 & 1 & 0\\ 0 & 0 &1 \end{augmatrix}\end{split}$

Tästä nähdään, että yhtälöryhmällä ei ole tarkkaa ratkaisua, joten etsitään pienimmän neliösumman ratkaisu. Normaaliryhmän kerroinmatriisi ja vakiovektori

$\begin{split}\tp{A}A= \begin{augmatrix}{cc} 6 & 0\\ 0 & 30 \end{augmatrix} \qquad\text{ja}\qquad \tp{A}\bb= \begin{augmatrix}{c} 2\\16 \end{augmatrix}.\end{split}$

Matriisi $$\tp{A}A$$ on selvästi kääntyvä, sillä se on kolmiomatriisi, jolla ei ole nolla-alkiota diagonaalillaan. Täten normaaliryhmällä $$\tp{A}A\bx=\tp{A}\bb$$ on yksikäsitteinen pienimmän neliösumman ratkaisu

$\begin{split}\overline{\bx}=(\tp{A}A)^{-1}\tp{A}\bb=\frac{1}{180} \begin{augmatrix}{cc} 30 & 0 \\ 0 & 6 \end{augmatrix} \begin{augmatrix}{c} 2 \\ 16 \end{augmatrix}= \begin{augmatrix}{c} \frac{1}{3}\\\frac{8}{15} \end{augmatrix}.\end{split}$

Ratkaisun virhe on $$\|\bb - A\overline{\bx}\| = \sqrt{(3 - 3)^2 + \left(2 + \frac{2}{5}\right)^2 + \left(5 - \frac{1}{5}\right)^2} = \frac{12}{\sqrt{5}}$$ ja kerroinmatriisin $$A$$ pseudoinverssiksi saadaan

$\begin{split}A^+=(\tp{A}A)^{-1}\tp{A}=\frac{1}{180} \begin{augmatrix}{cc} 30 & 0\\ 0 & 6 \end{augmatrix} \begin{augmatrix}{crr} 1 & 2 & -1\\ 5 & -2 & 1 \end{augmatrix}= \begin{augmatrix}{crr} \frac{1}{6} & \frac{1}{3} & -\frac{1}{6}\\ \frac{1}{6} & -\frac{1}{15} & \frac{1}{30} \end{augmatrix}.\qedhere\end{split}$
Palautusta lähetetään...