Edellisessä blogikirjoituksessani yleistin Newtonin menetelmän usean yhtälön muodostaman yhtälöryhmän ratkaisemiseen. Yleistämisen tie taitaa kuitenkin olla loputon. Katsotaanpa onnistuisiko neliömatriisin käänteismatriisin hakeminen Newtonin menetelmällä. Tarvittaessa näkökulmaa hieman vaihtaen.
Joitakin pohjatietoja tarvitaan. Tiettyä kokoa olevien neliömatriisien — esimerkiksi \[ A = \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} \] — yhteenlasku ja matriisikertolasku (sellaisena kuin se matriisialgebrassa määritellään, ks. esim. https://en.wikipedia.org/wiki/Matrix_multiplication) noudattavat melkein samoja laskusääntöjä kuin reaaliluvut. Poikkeuksena on kertolaskun vaihdannaisuus: matriiseille tulot $AB$ ja $BA$ eivät yleensä ole samoja.
Matriisi $B$ on matriisin $A$ käänteismatriisi, jos $AB = BA = I$, missä $I$ on yksikkömatriisi. Tämän vasemmasta ylänurkasta alkavalla ja oikeaan alanurkkaan päättyvällä laskevalla lävistäjällä on ykkösiä, muualla nollia, esimerkiksi \[ I = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}. \] Tällöin merkitään $B = A^{-1}$. Kaikilla matriiseilla ei ole käänteismatriisia.
Matriisien jakolaskua on aina ajateltava käänteismatriisilla kertomisena, kuten reaalilukujen jakolaskukin voidaan ajatella: $c/d = cd^{-1} = d^{-1}c$. Matriiseilla oikealta puolelta ja vasemmalta puolelta jakaminen antavat kuitenkin yleensä eri suuren tuloksen: $CD^{-1} \neq D^{-1}C$, joten jakolaskuja on kaksi erilaista.
Olkoon seuraavassa $A$ neliömatriisi, jolle etsitään käänteismatriisia. Kaikille samankokoisille neliömatriiseille $X$, joilla on käänteismatriisi, voidaan määritellä funktio $F(X) = X^{-1} - A$. Tämän nollakohta, ts. yhtälön $F(X) = O$ ratkaisu on $X = A^{-1}$, ts. $A$:n käänteismatriisi. (Tässä $O$ tarkoittaa pelkistä nollista muodostuvaa neliömatriisia.)
Jotta Newtonin menetelmää voitaisiin soveltaa, on löydettävä funktion $F$ differentiaali, kuten edellisestä blogiartikkelista ilmenee. Tällä kertaa ei kuitenkaan derivointi auta, vaan on vaihdettava näkökulmaa ja pyrittävä esittämään funktion muutos summana lineaarisesta termistä ja korjaustermistä edellisen artikkelin yhtälön \[ f(x) = f(x_0) + f'(x_0)(x - x_0) + \varepsilon(x,x_0)(x - x_0) \] tapaan. Tällöin saadaan seuraavaa: \begin{align*} F(X) &= X^{-1} - A \\ &= (X_0^{-1} - A) - (X_0^{-1}X X_0^{-1} - X_0^{-1}) + (X_0^{-1}X X_0^{-1} - 2X_0^{-1} + X^{-1}) \\ &= (X_0^{-1} - A) - X_0^{-1}(X - X_0)X_0^{-1} + (X_0^{-1} - X^{-1})(X - X_0)X_0^{-1}. \end{align*} (Algebran taidot ovat tässä tarpeen. Kyseessähän ei ole lausekkeen sievennys vaan sen monimutkaistaminen haluttuun muotoon pääsemiseksi. Lausekkeeseen on lisätty joitakin termejä ja tasapainon säilyttämiseksi vähennetty nämä pois. Täten monimutkaistettua lauseketta on muokattu matriisialgebran säännöillä. Tuloksen tarkistaminen on ehkä helpointa sieventämällä lopputulosta ja päätymällä lähtökohtaan.)
Kolmesta termistä ensimmäinen on funktion arvo pisteessä $X_0$, toinen on lineaarinen termi, ts. $X - X_0$ kerrottuna vakiomatriisilla $X_0^{-1}$ sekä oikealta että vasemmalta. Kolmannessa kaksi ensimmäistä tekijää lähestyvät nollaa, kun $X \to X_0$, ts. se kelpaa korjaustermiksi.
Tällöin kahta ensimmäistä termiä voidaan käyttää funktion $F$ approksimaationa ja yhtälöä $F(X) = O$ likimäärin vastaa yhtälö \[ (X_0^{-1} - A) - X_0^{-1}(X - X_0)X_0^{-1} = O. \] Kun tämä kerrotaan oikealta ja vasemmalta matriisilla $X_0$, saadaan yhtälö: \[ X_0 - X_0AX_0 = X - X_0. \] Tästä voidaan ratkaista $X$, jolloin Newtonin menetelmän iteraatiokaavaksi saadaan \[ X_{n+1} = 2X_n - X_nAX_n. \]
Kovin käyttökelpoinen menettely käänteismatriisin määräämiseen tämä ei kuitenkaan ole, sillä riittävän lähellä olevan aloitusmatriisin löytäminen ei useinkaan ole helppoa. Jos tämä ei ole riittävän lähellä, ei syntyvä iteraatio suppene. Jos matriisi $A$ kuitenkin on lävistäjävaltainen, ts. päälävistäjän alkiot ovat itseisarvoltaan muita riittävästi suurempia, voidaan aloittaa matriisista, jossa lävistäjällä on matriisin $A$ lävistäjäalkioiden käänteisarvot ja muut alkiot ovat nollia. Esimerkiksi matriisin \[ A = \begin{pmatrix} 2 & 1 & 1 \\ 1 & 3 & 1 \\ 1 & 1 & 4 \end{pmatrix} \] tapauksessa alkuarvoksi voidaan ottaa \[ X_0 = \begin{pmatrix} 0.5 & 0 & 0 \\ 0 & 0.33 & 0 \\ 0 & 0 & 0.25 \end{pmatrix}, \] jolloin perättäisiksi käänteismatriisin approksimaatioiksi saadaan \begin{align*} &\left( \begin{array}{ccc} 0.5 & 0 & 0 \\ 0 & 0.33 & 0 \\ 0 & 0 & 0.25 \\ \end{array} \right) \\[3pt] &\left( \begin{array}{ccc} 0.5 & -0.165 & -0.125 \\ -0.165 & 0.3333 & -0.0825 \\ -0.125 & -0.0825 & 0.25 \\ \end{array} \right) \\[3pt] &\left( \begin{array}{ccc} 0.604575 & -0.186467 & -0.1299 \\ -0.186467 & 0.389417 & -0.072402 \\ -0.1299 & -0.072402 & 0.281456 \\ \end{array} \right) \\[3pt] &\left( \begin{array}{ccc} 0.640413 & -0.180814 & -0.121396 \\ -0.180814 & 0.408004 & -0.0618364 \\ -0.121396 & -0.0618364 & 0.291636 \\ \end{array} \right) \\[3pt] &\left( \begin{array}{ccc} 0.646718 & -0.17673 & -0.117862 \\ -0.17673 & 0.411567 & -0.0589877 \\ -0.117862 & -0.0589877 & 0.293982 \\ \end{array} \right) \\[3pt] &\left( \begin{array}{ccc} 0.647058 & -0.176471 & -0.117648 \\ -0.176471 & 0.411764 & -0.058824 \\ -0.117648 & -0.058824 & 0.294117 \\ \end{array} \right) \\[3pt] &\left( \begin{array}{ccc} 0.647059 & -0.176471 & -0.117647 \\ -0.176471 & 0.411765 & -0.0588235 \\ -0.117647 & -0.0588235 & 0.294118 \\ \end{array} \right) \\[3pt] &\left( \begin{array}{ccc} 0.647059 & -0.176471 & -0.117647 \\ -0.176471 & 0.411765 & -0.0588235 \\ -0.117647 & -0.0588235 & 0.294118 \\ \end{array} \right) \end{align*}
Ei kommentteja:
Lähetä kommentti