Newtonmetoder

Newtonmetoder er en gruppe iterativ metoder som brukes til å finne røtter til ikke-lineære funksjoner eller løsninger av ikke-lineære likningssystemer. Hovedideen er å erstatte funksjonen med tangentlinjen ved hver prøveverdi og bruke røttene til tangentlikningen som nye anslag.

Metoden er vanligvis kalt Newton-Raphson-metoden og har navn etter Isaac Newton og Joseph Raphson. Den ble utviklet uavhengig av dem i senere arbeid, og den har blitt en av de mest brukte metodene i numerisk analyse på grunn av sin ofte raske konvergens og brede anvendelsesområde. Det finnes varianter som er tilpasset én variabel eller flere variabler, og som også brukes i ulike problemstillinger som optimering og systemløsning.

For en enkel variabel f vie funksjon f, starter man med et initialt gjettet tall x0 og itererer på formelen x_{n+1} = x_n - f(x_n)/f'(x_n), forutsatt at f' ikke er null i nærheten av roten. Ved riktig forhold mellom funksjonens glatthet og en god begynnelsesverdi konvergerer metoden ofte raskt mot roten, med kvadratisk konvergens nær simple røtter. Hvis f'(x) blir null eller initialverdien er for dårlig, kan konvergensen avta eller feile, og man bruker ofte varianter som demping eller secant-metoden når deriverten ikke er tilgjengelig.

For flervariable problemer løser man F(x) = 0 der F: R^n -> R^n. Her brukes Jacobian-matrisen J(x) i stedet for den enkle deriverten, og oppdateringen blir x_{k+1} = x_k - J(x_k)^{-1} F(x_k) eller ved å løse J(x_k) p = F(x_k) og sette x_{k+1} = x_k - p. Lokalt gir dette ofte kvadratisk konvergens når Jacobian er invertibel i nærheten av løsningen. Kostnaden ligger i evaluering og invertering av Jacobian, og i praksis brukes ofte demping eller line search for å oppnå bedre global konvergens.

Newtonmetoder har brede anvendelser i vitenskap og ingeniørfag, blant annet til å løse ikke-lineære ligningssystemer som oppstår i fluiddynamikk, kjemi, mekanikk, elektronikk og optimering. Begrensningene inkluderer avhengighet av en god startverdi, risiko for divergens hvis jacobiansvingen er nær singular eller hvis funksjonen er dårlig oppført, samt høy kostnad ved høyere dimensjoner. Som følge av dette bruker man ofte kombinasjoner av Newtonmetoden med andre teknikker for å sikre robust konvergens i komplekse problemer.