Differentiaali- ja integraalilaskenta 2, kevät 2022 (Aalto MOOC)

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}<\sqrt{5}<\sqrt{9}=3\), 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.