Differentiaali- ja integraalilaskenta 2

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.