8. Newtonin iteraatio

Newtonin menetelmä

Newtonin menetelmällä voidaan löytää (vähintäänkin derivoituvan) funktion f\colon \mathbb{R} \to \mathbb{R} nollakohta eli yhtälön f(x)=0 ratkaisu. Silloin kun menetelmä toimii, se suppenee hyvin nopeasti. Silloin kun ei, niin...

Lähdetään liikkeelle jostakin pisteestä x_0, joka on alkuarvaus yhtälön ratkaisulle. Arvioidaan funktiota f sen tangenttisuoralla pisteessä, eli funktiolla l(x)=f(x_0)+f'(x_0)(x-x_0). Ratkaistaan yhtälö l(x_1)=0. Toistetaan edellinen käyttäen alkuarvauksena lukua x_1 luvun x_0 sijasta jne. Tämä menettely johtaa algoritmiin, jossa iteraatioaskeleet saadaan kaavasta x_{n+1}= x_n-\frac{f(x_n)}{f'(x_n)}\,\qquad n=0,1,2,\ldots. Suppeneminen ja löytyvä nollakohta riippuvat alkuarvauksesta x_0.

Esimerkki

Etsitään likiarvo luvulle \sqrt{5}.
Koska 2=\sqrt{4}, niin valitaan x_0=2 läheltä ratkaisua. Tässä f(x)=x^2-5, joten f'(x)=2x. Saadaan x_1 = x_0 - \frac{f(2)}{f'(2)} = 2- \frac{4-5}{2\cdot 2}= \frac{9}{4}. x_2 = x_1 - \frac{f(9/4)}{f'(9/4)} = \frac{9}{4} - \frac{27/16-5}{2\cdot 9/4} = \frac{161}{72} \approx 2.2361.

Huomaa, että \sqrt{5}\approx 2.236068, eli jo kahdella iteraatiolla saatiin varsin hyvä likiarvo.

Esimerkki

Etsitään funktion f(x)=x^3-x+1 nollakohdat.

Piirtämällä kuvaaja nähdään, että funktiolla on vain yksi nollakohta jossain pisteiden -2 ja -1 välissä. Asetetaan x_0=-1.

Koska f'(x)=3x^2-1 iteratioksi saadaan x_{n+1} = x_n - \frac{x_n^3-x_n+1}{3x_n^2-1}. Saadaan x_0=-1,\quad x_1= -1.5, \quad x_2 = -1.347826, \quad x_3=-1.325200. x_4= -1.324718, \quad x_5=-1.324717, \quad \ldots

Newtonin menetelmä monen muuttujan tapauksessa

Newtonin menetelmä toimii myös funktion \mathbf{f} \colon \mathbb{R}^n\to\mathbb{R}^n tapauksessa. Tällöin iteraatiokaavassa oleva derivaatta pitää korvata Jacobin matriisilla D\mathbf{f}(\mathbf{x}) = \begin{bmatrix} \frac{\partial f_1}{\partial x_1} & \frac{\partial f_1}{\partial x_2} & \cdots & \frac{\partial f_1}{\partial x_n}\\ \frac{\partial f_2}{\partial x_1} & \frac{\partial f_2}{\partial x_2} & \cdots & \frac{\partial f_2}{\partial x_n}\\ \vdots & \vdots & & \vdots \\ \frac{\partial f_m}{\partial x_1} & \frac{\partial f_m}{\partial x_2} & \cdots & \frac{\partial f_m}{\partial x_n} \end{bmatrix}. Iteraatioaskeleeksi saadaan \mathbf{x}_{n+1} = \mathbf{x}_n- D\mathbf{f} (\mathbf{x}_n)^{-1}\mathbf{f}(\mathbf{x}_n), \quad n=0,1,2,\ldots, missä D\mathbf{f} (\mathbf{x}_n)^{-1} on D\mathbf{f} (\mathbf{x}_n):n käänteismatriisi.

Esimerkki

Etsitään \mathbf{f}(\mathbf{x})=\mathbf{0}, kun \mathbf{x}_0=(1,0,1) ja \mathbf{f}(x,y,z)=(x^2+y^2+z^2-3)\mathbf{i} + (x^2+y^2-z-1)\mathbf{j} +(x+y+z-3)\mathbf{k}.
Saadaan D \mathbf{f} (x,y,z)=\begin{bmatrix}2x &2y & 2z\\ 2x&2y&-1\\ 1&1&1\end{bmatrix} ja voidaan laskea \mathbf{x}_1 = (3/2,1/2,1),\quad \mathbf{x}_2 = (5/4,3/4,1)\quad \text{ ja }\quad \mathbf{x}_2 = (9/8,7/8,1), mikä on terveellisintä tehdä tietokoneella.

Nähdään, että iteraatiot konvergoivat kohti pistettä (1,1,1), joka on tehtävän tarkka (ja kaikesta päätellen ainoa) ratkaisu.