Newton-Raphson-metode

Die Newton-Raphson metode (ook bekend as Newton se metode) is 'n iteratiewe metode wat gebruik word om vergelykings op te los wat andersins baie moeilik of onmoontlik is om algebraïs op te los. Dit is waarskynlik een van die beste en gewildste metodes om opeenvolgend beter benaderings tot die wortels van 'n reëlwaardige funksie te vind. Dié metode konvergeer dikwels verbasend vinnig, veral as die iterasie naby aan die verlangde wortel begin. Ongelukkig is dit ook waar dat dié metode vinnig kan wegbeweeg vanaf die verlangde wortel as die eerste iterasie ver van die wortel af begin het. Goeie algoritmes wat die metode insluit bevat daarom gewoonlik 'n metode om konvergensieprobleme op te spoor.

Probleemstelling

Vir 'n gegewe funksie $f(x)$ wil ons die waarde van $x$ bereken waarvoor $f(x)=0$. Ons wil dus die wortel van die funksie bereken. Mens kan enige vergelyking in hierdie formaat skryf deur al die terme aan die regterkant na die linkerkant toe te skuif. As voorbeeld, veronderstel ${\textstyle g(x)=x}$ is gegewe, dan kan ons hierdie uitdrukking herskryf as $f(x):=g(x)-x=0$ waaruit volg dat $x$ 'n oplossing van die vergelyking $g(x)-x=0$ is.

Beskrywing

Gegewe 'n funksie $f(x)$ en sy afgeleide $f'(x)\!$, dan word daar begin met 'n eerste raaiskoot $x_{0}.$ 'n Beter benadering $x_{1}$ van die wortel word dan verkry deur die formule

$$x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}.$$

Ons gebruik dan $x_{1}$as die volgende raaiskoot en bereken dan 'n volgende raaiskoot $x_{2}$deur gebruik te maak van die vorige formule, dit wil sê

$$x_{2}=x_{1}-{\frac {f(x_{1})}{f'(x_{1})}}.$$

Hierdie proses word dan oor en oor toegepas om 'n ry opeenvolgend beter benaderings $\left\{x_{0},\;x_{1},\;x_{2},\;\dotsc ,\;x_{j},\;x_{j+1},\;\dotsc ,\;x_{n}\right\}$ te verkry. Die proses word beëindig indien óf $|x_{j+1}-x_{j}|<\varepsilon$ (waar $\varepsilon$ 'n klein, reële getal is) óf $|f(x_{j})|<\varepsilon .$Die voorgenoemde voorwaarde dui aan dat die raaiskote naby mekaar is en die laasgenoemde voorwaarde dui aan dat die funksiewaarde klein genoeg is vir die waardeskatting. Die getal $\varepsilon$ word die fout (van die benadering) genoem.

Bespreking

'n Illustrasie van een iterasie van die metode (die funksie ƒ word in blou vertoon en die raaklyn is in rooi). Ons kan sien dat x_n+1 'n beter benadering is as x_n vir die wortel x van die funksie f.

Die gedagte agter die metode is as volg: 'n mens begin met 'n aanvanklike raaiskoot wat redelik naby is aan die ware wortel, die funksie word dan benader deur sy raaklyn (wat bereken kan word deur van differensiasie gebruik te maak) wat mens dan in staat stel om die $x\!$-snypunt van die raaklyn te bereken (met behulp van gewone algebra). Hierdie $x\!$-snypunt sal tipies 'n beter benadering wees vir die funksie se wortel as die oorspronklike raaiskoot en die metode kan dan van daar herhaal word deur verder iterasies uit te voer.

Gestel $f:[a,b]\to \mathbb {R}$ is 'n differensieërbare funksie gedefinieer op die interval $[a,b]$ met waardes in die reële getalle $\mathbb {R} \!$. Die vergelyking vir die konvergensie na die wortel kan dan maklik afgelei word. Gestel ons het 'n benadering x_n. Die vergelyking vir 'n beter benadering, x_n+1 kan dan afgelei word deur te verwys na die diagram na regs. Ons weet uit die definisie van die afgeleide by 'n gegewe punt dat dit die helling van die raaklyn by 'n gegewe punt op die grafiek is.

Dit wil sê

$f'(x_{n})\approx {\frac {\mathrm {styging} }{\mathrm {interval} }}={\frac {\mathrm {\Delta y} }{\mathrm {\Delta x} }}={\frac {f(x_{n})-0}{x_{n}-x_{n+1}}}.\,\!$

f ' stel die afgeleide van die funksie f voor. 'n Mens kan dan algebraïes aflei dat

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.\,\!$

Die proses word begin met 'n arbitrêre aanvangswaarde x₀. (Hoe nader dit aan die wortel is des te beter. Die metode sal gewoonlik kwadraties konvergeer in die gebied van die wortel, wat beteken dat die aantal korrekte desimale van die benadering met elke raaiskoot rofweg verdubbel. In die afwesigheid van enige kennis van waar die wortel mag lê, kan die biseksie metode gebruik word om die moontlike ligging van die wortel oor 'n redelik klein interval te bepaal deur na die tussenwaarde stelling te verwys.

Toepassing op minimering en maksimering

Newton se metode kan ook gebruik word om die minimum of maksimum van 'n funksie te bepaal. Die afgeleide is nul by 'n minimum of 'n maksimum, dus kan minima en maksima gevind word deur Newton se metode op die afgeleide toe te pas. Die iterasie word dan:

$x_{n+1}=x_{n}-{\frac {f'(x_{n})}{f''(x_{n})}}.\,\!$

Meetkundige interpretasie

Die metode kan baie maklik verstaan word as dit meetkundig beskou word:

1. Kies 'n punt x₁ op die x-as naby die nulpunt;
2. Konstrueer 'n loodregte lyn op die x-as, deur x₁;
3. Konstrueer die raaklyn deur f(x₁) aan die kromme f(x);
4. Die nuwe benadering x₂ word deur die snypunt van die raaklyn met die x-as gegee;
5. Herhaal bogenoemde proses deur by x₂ te begin.

Verdere gebruike

'n Belangrike, maar ietwat verrassende, toepassing is Newton-Raphson deling, wat gebruik kan word om vinnig die omgekeerde van 'n getal te verkry deur slegs van vermenigvuldiging en aftrekking gebruik te maak.