Newtons metode

Newtons metode i kalkulus, òg kjend som Newton-Raphson-metoden, er ein iterativ metode for å finna nullpunkta til ein gjeven funksjon $f$, altså løysinga av $f(x)=0$.

Han må ikkje blandast saman med newtons metode i optimering, som baserer seg på å finna stasjonære punkt for ein gjeven funksjon $f$.

Definisjon

Gjeve eit startpunkt $x_n$ som den iterative metoden startar frå og ein funksjon $f$ ein ønskjer å finna nullpunkta til, så er newtons algoritme i kalkulus gjeven som

$x_{n+1}=x_n-\frac{f(x_n)}{\Delta f(x_n)}$

Her er $\Delta f(x_n)$ den deriverte av $f(x_n)$. Under særskilde føresetnadar bundne av valet av startpunkt $x_k$, så vil følgja $x_{n+1}$ konvergera mot løysinga $f(x_{x+1})=0$.

I det høvet der $f$ er ein vektorvaluert funksjon, så vert dette:

$x_{n+1}=x_n-J_f(x_n{)}^{-1}f(x_n)$

$J_f$ er her kjend som jakobimatrisa for funksjonen $f$.

Utleiing av definisjon

Ein ønskjer å finna nullpunkta for ein funksjon $f$, altså løysinga av $f(x)=0$ ved ein iterativ algoritme på forma:

$x_{k+1}=x_k+h$

som vil konvergera mot løysinga $f(x_{x+1})=0$ gjeve eit særskilt startpunkt $x_k$ og eit steg $h$. Me ønskjer i denne seksjonen å motivera steget $h$. For eit gjeve punkt $x_k$ så ønskjer me å tilnærma funksjonen $f$ i punktet og analysera kva for ein $h$ for eit punkt $x_k+h$ som fører til at ein går mot eit minimum,

altså ei løysing av $f(x)=0$. Newtons metode går ut på å gjera dette og å tilnærma funksjonen i punktet ved hjelp av taylorpolynom.

For ein fleirvariabels funksjon $f$ så er taylorpolynomtilnærminga av funksjonen $f$ gjeven som:

$f(x_k+h)=f(x_k)+\Delta f(x_k{)}^{T}h+(1/2)h^T{\Delta }^{2}f(x_k)h+\dots$

Det vert då nytta ei førsteordens taylorpolynomtilnærming av funksjonen i punktet, som er ei rett linje og er tangent til punktet $x_k$:

$f(x_k+h)\approx f(x_k)+\Delta f(x_k{)}^{T}h$

Me finn den $h$-en sånn at denne tilnærminga (tangentfunksjonen) er 0. Løyser ein dette ($f(x_k+h)=0$ med omsyn på $h$), så får ein newtonsteget:

$h=-\frac{f(x_k)}{\Delta f(x_k{)}^T}$

Newtonsteget i Newtons metode i kalkulus er altså utleitt frå ei førsteordens taylorpolynomtilnærming for funksjonen. For denne tilnærminga løyser ein $f(x_k+h)=0$ med omsyn på $h$. Ein får då punktet $x_k+h$ som minimerer tangentfunksjonen i punktet $x_k$.

Ut i frå $h$, så får me då:

$x_{n+1}=x_k+h=x_n-\frac{f(x_n)}{\Delta f(x_n{)}^T}$