Newtons metode

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 25. januar 2022; checks kræver 3 redigeringer .

Newtons metode, Newtons algoritme ( også kendt som tangentmetoden ) er en iterativ numerisk metode til at finde roden ( nul ) af en given funktion . Metoden blev først foreslået af den engelske fysiker , matematiker og astronom Isaac Newton ( 1643-1727 ) . Søgningen efter en løsning udføres ved at konstruere successive tilnærmelser og er baseret på principperne om simpel iteration . Metoden har kvadratisk konvergens . En modifikation af metoden er metoden med akkorder og tangenter . Newtons metode kan også bruges til at løse optimeringsproblemer, hvor det er nødvendigt at bestemme nulpunktet for den første afledte eller gradient i tilfælde af et flerdimensionalt rum.

Beskrivelse af metoden

Begrundelse

For numerisk at løse ligningen ved den simple iterationsmetode , skal den reduceres til en ækvivalent ligning: , hvor er sammentrækningsafbildningen . $f(x)=0$ $x=\varphi(x)$ $\varphi$

For den bedste konvergens af metoden på punktet for den næste tilnærmelse skal betingelsen være opfyldt . Løsningen af denne ligning søges i formen , så: $x^{*}$ $\varphi '(x^{*})=0$ $\varphi (x)=x+\alpha (x)f(x)$

\varphi '(x^{*})=1+\alpha '(x^{*})f(x^{*})+\alpha (x^{*})f'(x^{ *})=0.

Hvis vi antager, at tilnærmelsespunktet er "tæt nok" på roden , og at den givne funktion er kontinuert , er den endelige formel for : ${\tilde {x}}$ $(f(x^{*})\approx f({\tilde {x)))=0)$ $\alfa(x)$

\alpha (x)=-{\frac {1}{f'(x))).

Med dette i tankerne er funktionen defineret: $\varphi(x)$

\varphi (x)=x-{\frac {f(x)}{f'(x))).

Under visse forhold udfører denne funktion en sammentrækningskortlægning i et nabolag af roden.

Bevis

Lad en funktion af en reel variabel gives, der er to gange kontinuerligt differentierbar i sit definitionsdomæne , og hvis afledte aldrig forsvinder:

\scriptstyle {f(x)\colon {\mathbb {X}}\to \mathbb{R} ,\;f(x)\in {\mathrm {C}}^{2}({\mathbb {X} });\quad \forall x\in {\mathbb {X}}\;f'(x)\neq 0.}

Og det er nødvendigt at bevise, at funktionen udfører en sammentrækningskortlægning nær roden af ligningen . $\scriptstyle {\varphi (x)=x-{\frac {f(x)}{f'(x)))}$ $\scriptstyle {f(x)=0}$

På grund af den kontinuerlige differentiabilitet af funktionen og uligheden af nul, er dens første afledede kontinuert . $\scriptstyle {f(x)}$ $\scriptstyle {\varphi (x)}$

Den afledte er: $\scriptstyle {\varphi '(x)}$

\scriptstyle {\varphi '(x)={\frac {f(x)f''(x)}{\left(f'(x)\right)^{2))}.}

Under de betingelser, der er pålagt , er den også kontinuerlig. Lad være den ønskede rod af ligningen: , derfor i dens nabolag : $\scriptstyle {f(x)}$ $\scriptstyle {{\tilde {x}}}$ $\scriptstyle {f({\tilde {x)))=0}$ $\scriptstyle {\varphi '(x)\ca. 0}$

\scriptstyle {\forall \varepsilon \colon 0<\varepsilon <1,\;\eksisterer \delta >0\;\forall x\in {\mathbb {X}}\;|x-{\tilde {x}} |<\delta \colon |\varphi '(x)-0|<\varepsilon .}

Så ifølge Lagranges sætning :

\scriptstyle {\forall x_{1},\;x_{2}\i {\mathrm {U}}_{\delta }({\tilde {x)))\;\eksisterer \xi \i {\mathrm {U}}_{\delta }({\tilde {x}})\colon |\varphi (x_{1})-\varphi (x_{2})|=|\varphi '(\xi)|| x_{1}-x_{2}|<\varepsilon |x_{1}-x_{2}|.}

På grund af det faktum, at i det samme deltakvarter er følgende sandt: $\scriptstyle {\varphi ({\tilde {x)))={\tilde {x}}}$

\scriptstyle {\forall x\in U_{{\delta }}({\tilde {x}})\colon \;|\varphi (x)-{\tilde {x}}|<\varepsilon |x-{ \tilde{x}}|.}

Den således opnåede funktion i nærheden af roden implementerer en sammentrækningsmapping . ■ $\scriptstyle {\varphi (x)}$ $\scriptstyle {U_{\delta}({\tilde {x)))}$

I dette tilfælde reduceres algoritmen til at finde en numerisk løsning til ligningen til en iterativ beregningsprocedure : $f(x)=0$

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n)))))

Ifølge Banachs sætning tenderer sekvensen af tilnærmelser til roden af ligningen . $f(x)=0$

Geometrisk fortolkning

Hovedideen med metoden er som følger: den indledende tilnærmelse er sat nær den hypotetiske rod, hvorefter en tangent til grafen for den undersøgte funktion plottes ved tilnærmelsespunktet, for hvilket skæringspunktet med abscisseaksen er fundet. Dette punkt tages som den næste tilnærmelse. Og så videre, indtil den nødvendige nøjagtighed er nået.

Lad 1) en funktion med reel værdi være kontinuerligt differentierbar på intervallet ; 2) der er et påkrævet punkt : ; 3) der er også sådanne, at for og for ; 4) pointen er sådan, at . Så kan formlen for iterativ tilnærmelse til k udledes af den geometriske betydning af tangenten som følger: $f(x)\colon (a,\,b)\to \mathbb {R}$ $(a,\,b)$
$x^{*}\in (a,\,b)$ $f(x^{*})=0$
$C > 0$ $\delta>0$
$\vert f'(x)\vert \geqslant C$ $x\in (a,\,x^{*}-\delta ]\cup [x^{*}+\delta ,\,b)$
$f'(x)\neq 0$ $x\in (x^{*}-\delta ,\,x^{*})\cup (x^{*},\,x^{*}+\delta )$
$x_{n}\in (a,\,b)$ $f(x_{n})\neq 0$
$x_{n}$ $x^{{*}}$

f'(x_{n})=\mathrm {tg} \,\alpha _{n}={\frac {\Delta y}{\Delta x))={\frac {f(x_{n })-0}{x_{n}-x_{n+1}}}={\frac {0-f(x_{n})}{x_{n+1}-x_{n}}},

hvor er hældningsvinklen for tangentlinjen til grafen i punktet . $\alpha _{n}$ ${\displaystyle y(x)=f(x_{n})+(x-x_{n})\cdot \mathrm {tg} \,\alpha _{n))$ $f$ $(x_{n};f(x_{n}))$

Derfor (i ligningen for tangentlinjen antager vi ) har det ønskede udtryk for formen: $y(x_{n+1})=0$ $x_{{n+1}}$

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n)))))

Hvis , så kan denne værdi bruges som den næste tilnærmelse til . $x_{n+1}\in (a,\,b)$ $x^{{*}}$

Hvis , så er der en "flugt" (roden ligger nær grænsen ). I dette tilfælde er det nødvendigt (ved at bruge ideen om halveringsmetoden ) at erstatte med indtil punktet "vender tilbage" til søgeområdet . $x_{n+1}\notin (a,\,b)$ $x^{{*}}$ $(a,\,b)$ $x_{{n+1}}$ ${\frac {x_{n}+x_{n+1}}{2}}$ $(a,\,b)$

Bemærkninger. 1) Tilstedeværelsen af en kontinuerlig afledt gør det muligt at bygge en kontinuerligt skiftende tangent på hele området for søgningen efter en løsning . 2) Tilfælde af grænse (ved et punkt eller ved et punkt ) placering af den ønskede løsning betragtes på lignende måde. 3) Set fra et geometrisk synspunkt betyder lighed , at tangentlinjen til grafen i punktet - er parallel med aksen og ikke skærer med denne i enden. 4) Jo større konstanten er og jo mindre konstanten fra afsnit 3 af betingelserne, jo tættere er skæringspunktet mellem tangenten til grafen og aksen til punktet , det vil sige jo tættere er værdien på den ønskede . $(a,\,b)\;$
$-en$ $b$ $x^{{*}}$
$f'(x_{n})=0$ $f$ $(x_{n};f(x_{n}))$ $OKSE$ $f(x_{n})\neq 0$
$C > 0$ $\delta>0$ $x_{n}\in (a,\,x^{*}-\delta ]\cup [x^{*}+\delta ,\,b)$ $f$ $OKSE$ $(x^{*};\;0)$ $x_{{n+1}}$ $x^{*}\in (a,\,b)$

Den iterative proces begynder med en indledende tilnærmelse , og mellem og det ønskede punkt bør der ikke være andre nuller i funktionen , det vil sige "jo tættere på den ønskede rod , jo bedre." Hvis der ikke er nogen antagelser om at finde , kan trial and error indsnævre rækken af mulige værdier ved at anvende mellemværdisætningen . $x_{0}\in (a,\,b)$ $x_{0}\in (a,\,b)$ $x^{*}\in (a,\,b)$ $f$ $x_{0}$ $x^{{*}}$ $x^{{*}}$

For foruddefinerede afslutter den iterative proces hvis og . Især for displayet matrix og kan beregnes baseret på grafen display skala , det vil sige, hvis og falder i én lodret, og i én vandret række. $\varepsilon _{x}>0$ $\varepsilon _{f}>0$ $\left\vert {\frac {f(x_{n})}{f'(x_{n))}}\right\vert \approx \vert x_{n+1}-x_{n}\ vert<\varepsilon_{x}$ ${\displaystyle \vert f(x_{n+1})\vert </varepsilon _{f))$
$\varepsilon _{x}$ ${\displaystyle \varepsilon _{f))$ $f$ $x_{n}$ $x_{{n+1}}$ $f(x_{n})$ $f(x_{n+1})$

Algoritme

Den indledende tilnærmelse er indstillet . $x_{0}$
Indtil stopbetingelsen er opfyldt, som kan tages som eller (det vil sige fejlen er inden for de krævede grænser), beregnes en ny tilnærmelse: . $|x_{n+1}-x_{n}|<\varepsilon$ $|f(x_{n+1})|<\varepsilon$ $x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n))}}$

Eksempel

Overvej problemet med at finde positive , for hvilket . Denne opgave kan repræsenteres som opgaven med at finde funktionens nulpunkt . Vi har et udtryk for den afledede . Da for alle og for , er det indlysende , at løsningen ligger mellem 0 og 1. Lad os tage værdien som en indledende tilnærmelse , så: $x$ $\cos x=x^{3}$ $f(x)=\cos xx^{3}$ $f'(x)=-\sin x-3x^{2}$ $\cos x\leqslant 1$ $x$ $x^{3}>1$ $x>1$ $x_{0}=0{,}5$

{\begin{matrix}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})))&=&1{,}112\;141 \;637\;097,\\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})))&=&\understreget {0 {,}}909\;672\;693\;736,\\x_{3}&=&x_{2}-{\dfrac {f(x_{2})}{f'(x_{2})} }&=&\understreget {0{,}86}7\;263\;818\;209,\\x_{4}&=&x_{3}-{\dfrac {f(x_{3})}{ f'(x_{3})}}&=&\understreget {0{,}865\;47}7\;135\;298,\\x_{5}&=&x_{4}-{\dfrac { f(x_{4})}{f'(x_{4})}}&=&\understreget {0{,}865\;474\;033\;1}11,\\x_{6}&= &x_{5}-{\dfrac {f(x_{5})}{f'(x_{5})}}&=&\understreget {0{,}865\;474\;033\;102}. \end{matrix}}

Gyldige signifikante cifre er understreget . Det kan ses, at deres antal stiger fra trin til trin (ca. fordobles med hvert trin): fra 1 til 2, fra 2 til 5, fra 5 til 10, hvilket illustrerer den kvadratiske konvergenshastighed .

Vilkår for brug

Lad os overveje en række eksempler, der peger på manglerne ved metoden.

Modeksempler

Hvis den indledende tilnærmelse ikke er tæt nok på løsningen, konvergerer metoden muligvis ikke.

Lade

f(x)=x^{3}-2x+2.

Derefter

x_{{n+1}}=x_{{n}}-{\frac {x_{n}^{3}-2x_{n}+2}{3x_{n}^{2}-2}}.

Lad os tage nul som en indledende tilnærmelse. Den første iteration vil give enhed som en tilnærmelse. Til gengæld vil den anden igen give nul. Metoden vil loope, og der vil ikke blive fundet nogen løsning. Generelt kan konstruktionen af en sekvens af tilnærmelser være meget forvirrende .

Hvis den afledede ikke er kontinuert ved rodens punkt, kan metoden divergere i et hvilket som helst område af roden.

Overvej en funktion:

f(x)={\begin{cases}0,&x=0,\\x+x^{2}\sin \left({\dfrac {2}{x}}\right),&x\ neq 0.\end{cases}}

Dengang og overalt undtagen 0. $f'(0)=1$ $f'(x)=1+2x\sin(2/x)-2\cos(2/x)$

I nærheden af roden skifter den afledede fortegn, når den nærmer sig nul fra højre eller venstre. Mens for . $x$ $f(x)\geqslant xx^{2}>0$ $0<x<1$

Den er således ikke afgrænset nær roden, og metoden vil divergere, selvom funktionen er differentierbar overalt, dens afledte er ikke-nul ved roden, uendeligt differentierbar overalt undtagen ved roden, og dens afledte er afgrænset omkring roden . $f(x)/f'(x)$ $f$

Hvis der ikke er nogen anden afledet ved rodpunktet, kan metodens konvergenshastighed reduceres mærkbart.

Overvej et eksempel:

f(x)=x+x^{4/3}.

Så og undtagen hvor det ikke er defineret. ${\displaystyle f'(x)=1+(4/3)x^{1/3))$ ${\displaystyle f''(x)=(4/9)x^{-2/3))$ $x=0$

På næste trin har vi : $x_{n}$

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n))}}={\frac {(1/3)x_{ n}^{4/3}}{(1+(4/3)x_{n}^{1/3})}}.

Hastigheden af konvergens af den resulterende sekvens er ca. 4/3. Dette er væsentligt mindre end 2, hvilket er nødvendigt for kvadratisk konvergens, så i dette tilfælde kan vi kun tale om lineær konvergens, selvom funktionen er kontinuerligt differentierbar overalt , er den afledede ved roden ikke lig med nul, og er uendeligt differentierbar overalt undtagen ved roden. $f$

Hvis den afledede ved rodpunktet er lig med nul, vil konvergenshastigheden ikke være kvadratisk, og selve metoden kan afslutte søgningen for tidligt og give en tilnærmelse, der er forkert for en given nøjagtighed.

Lade

f(x)=x^{2}.

Så og deraf . Metodens konvergens er således ikke kvadratisk, men lineær, selvom funktionen er uendelig differentierbar overalt. $f'(x)=2x$ $xf(x)/f'(x)=x/2$

Begrænsninger

Lad ligningen være givet , hvor og det er nødvendigt at finde dens løsning. $f(x)=0$ $f(x)\colon \mathbb {X} \to \mathbb {R}$

Nedenfor er formuleringen af hovedsætningen, som giver os mulighed for at give klare betingelser for anvendelighed. Den bærer navnet på den sovjetiske matematiker og økonom Leonid Vitalievich Kantorovich ( 1912-1986 ) .

Kantorovichs teorem.

Hvis der er konstanter , sådan at: $A,\;B,\;C$

${\frac {1}{|f'(x)|}}<A$ på , det vil sige, den eksisterer og er ikke lig med nul; $[a,\;b]$ $f'(x)$
$\left|{\frac {f(x)}{f'(x)}}\right|<B$ på , altså begrænset; $[a,\;b]$ $f(x)$
$\exists f''(x)$ på , og ; $[a,\;b]$ $|f''(x)|\leqslant C\leqslant {\frac {1}{2AB))$

Desuden er længden af det betragtede segment . Så er følgende udsagn sande: $|ab|<{\frac {1}{AB}}\left(1-{\sqrt {1-2ABC}}\right)$

der findes en rod af ligningen ; $[a,\;b]$ $x^{*}$ $f(x)=0\colon \exists x^{*}\in [a,\;b]\colon f(x^{*})=0$
hvis , så konvergerer den iterative sekvens til denne rod: ; $x_{0}={\frac {a+b}{2))$ $\left\{x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})))\right\}\to x^ {*}$
fejlen kan estimeres med formlen . $|x^{*}-x_{n}|\leqslant {\frac {B}{2^{n-1}}}(2ABC)^{2^{n-1}}$

Fra den sidste sætning i sætningen følger især metodens kvadratiske konvergens :

|x^{*}-x_{n}|\leqslant {\frac {B}{2^{n-1}}}(2ABC)^{2^{n-1}}={\frac {1}{2}}{\frac {B}{2^{n-2}}}\left((2ABC)^{2^{n-2}}\right)^{2}=\alpha | x^{*}-x_{n-1}|^{2}.

Så vil begrænsningerne på den oprindelige funktion se således ud: $f(x)$

funktionen skal være begrænset;
funktionen skal være jævn , dobbelt differentierbar ;
dens første afledte er ensartet adskilt fra nul; $f'(x)$
dens anden afledte skal være ensartet afgrænset. $f''(x)$

Historisk baggrund

Metoden blev beskrevet af Isaac Newton i manuskriptet On the Analysis by Equations of Infinite Series ( latin: De analysi per aequationes numero terminorum infinitas ) adresseret til Barrow i 1669 , og i The Method of Fluxions and Infinite Series ( latin: De metodis fluxionum et serierum infinitarum" ) eller " Analytisk Geometri " ( lat. "Geometria analytica" ) i samlingerne af Newtons værker, som blev skrevet i 1671 . I sine skrifter introducerer Newton begreber som udvidelsen af en funktion til en serie , infinitesimals og fluxioner ( afledte i den nuværende betydning). Disse værker blev udgivet meget senere: den første blev udgivet i 1711 takket være William Johnson, den anden blev udgivet af John Colzon i 1736 efter skaberens død. Imidlertid afveg beskrivelsen af metoden væsentligt fra hans nuværende udlægning: Newton anvendte sin metode udelukkende på polynomier . Han beregnede ikke successive tilnærmelser , men en sekvens af polynomier og som et resultat fik en omtrentlig løsning . $x_{n}$ $x$

Metoden blev først offentliggjort i afhandlingen "Algebra" af John Wallis i 1685, på hvis anmodning den kort blev beskrevet af Newton selv. I 1690 udgav Joseph Raphson en forenklet beskrivelse i sin "Analysis aequationum universalis" ( latin: "Analysis aequationum universalis" ). Raphson betragtede Newtons metode som rent algebraisk og begrænsede dens anvendelse til polynomier, men han beskrev metoden i form af successive tilnærmelser i stedet for den mere vanskelige at forstå sekvens af polynomier brugt af Newton. Endelig, i 1740, blev Newtons metode beskrevet af Thomas Simpson som en førsteordens iterativ metode til løsning af ikke-lineære ligninger ved hjælp af en afledt, som præsenteret her. I samme publikation generaliserede Simpson metoden til tilfældet med et system af to ligninger og bemærkede, at Newtons metode også kan anvendes til optimeringsproblemer ved at finde nulpunktet for den afledte eller gradient . $x_{n}$

I 1879 var Arthur Cayley , i The Newton-Fourier imaginary problem, den første til at påpege vanskelighederne ved at generalisere Newtons metode til tilfældet med imaginære rødder af polynomier af højere grad end den anden og komplekse indledende tilnærmelse. Dette arbejde banede vejen for studiet af fraktal teori .

Generaliseringer og ændringer

Sekantmetoden

Den relaterede sekantmetode er Newtons "tilnærmede" metode og undgår at beregne den afledte. Værdien af den afledte i den iterative formel erstattes af dens estimat for de to foregående iterationspunkter:

${\displaystyle f'(x_{n})\ca. {\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1))))$ .

Således har hovedformlen formen

x_{n+1}=x_{n}-f(x_{n})\cdot {\frac {x_{n}-x_{n-1}}{f(x_{n})-f (x_{n-1})}}.

Denne metode ligner Newtons, men har en lidt langsommere konvergenshastighed. Metodens konvergensrækkefølge er lig med det gyldne snit - 1.618 ...

Bemærkninger. 1) For at starte den iterative proces kræves to forskellige værdier af og . 2) I modsætning til den "ægte Newton-metode" (tangensmetoden), som kun kræver lagring (og midlertidigt under beregninger og ), kræver sekantmetoden lagring , , , . 3) Det bruges, hvis beregningen er svær (for eksempel kræver den en stor mængde maskinressourcer: tid og/eller hukommelse). $x_{0}$ $x_{1}$
${\displaystyle x_{n))$ $f(x_{n})$ $f'(x_{n})$ ${\displaystyle x_{n-1))$ ${\displaystyle x_{n))$ $f(x_{n-1})$ $f(x_{n})$
$f'(x)$

En tangentmetode

For at reducere antallet af opkald til værdierne af den afledte funktion af en funktion, bruges den såkaldte en-tangens metode.

Iterationsformlen for denne metode er:

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

Essensen af metoden er kun at beregne den afledte én gang, ved det indledende tilnærmelsespunkt , og derefter bruge denne værdi ved hver efterfølgende iteration: $x_{0}$

\alpha (x)=\alpha _{0}=-{\dfrac {1}{f'(x_{0})))

Med dette valg gælder følgende lighed på punktet : $\alpha _{0}$ $x_{0}$

\varphi '(x_{0})=1+\alpha _{0}f'(x_{0})=0,

og hvis det segment, hvorpå tilstedeværelsen af en rod antages, og den indledende tilnærmelse er valgt, er lille nok, og den afledede er kontinuert, så vil værdien ikke afvige meget fra , og derfor vil grafen passere næsten vandret og skære lige linje , som igen vil sikre hurtig konvergens af sekvensen af tilnærmelsespunkter til roden. $x^{*}$ $x_{0}$ $\varphi '(x)$ $\varphi '(x^{*})$ $\varphi '(x_{0})=0$ $y=\varphi (x)$ $y=x$

Denne metode er et specialtilfælde af den simple iterationsmetode . Det har en lineær rækkefølge af konvergens.

Multidimensional sag

Lad os generalisere det opnåede resultat til det multidimensionelle tilfælde.

Lad det være nødvendigt at finde en løsning på systemet:

\left\{{\begin{array}{lcr}f_{1}(x_{1},\;x_{2},\;\ldots ,\;x_{n})&=&0,\ \\ldots &&\\f_{m}(x_{1},\;x_{2},\;\ldots,\;x_{n})&=&0.\end{array}}\right.

Ved at vælge en begyndelsesværdi , findes successive tilnærmelser ved at løse ligningssystemer : ${\vec {x}}^{[0]}$ ${\vec {x}}^{[j+1]}$

f_{i}+\sum _{k=1}^{n}{\frac {\partial f_{i}}{\partial x_{k}}}(x_{k}^{[j+ 1 ]}-x_{k}^{[j]})=0,\qquad i=1,\;2,\;\ldots ,\;m,

hvor . ${\vec {x}}^{[j]}=(x_{1}^{[j]},\;x_{2}^{[j]},\;\ldots ,\;x_ {n}^{[j]}),\quad j=0,\;1,\;2,\;\ldots$

Som anvendt på optimeringsproblemer

Lad det være nødvendigt at finde minimum af en funktion af flere variable . Denne opgave svarer til problemet med at finde nulpunktet for gradienten . Lad os anvende ovenstående Newtons metode: $f({\vec {x}})\colon \mathbb {R} ^{n}\to \mathbb {R}$ $\nabla f({\vec {x)))$

\nabla f({\vec {x}}^{[j]})+H({\vec {x}}^{[j]})({\vec {x}}^{[j +1]}-{\vec {x}}^{[j]})=0,\quad j=1,\;2,\;\ldots ,\;n,

hvor er hessian for funktionen . $H({\vec {x)))$ $f({\vec {x)))$

I en mere bekvem iterativ form ser dette udtryk således ud:

{\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-H^{-1}({\vec {x}}^{[ j]})\nabla f({\vec {x}}^{[j]}).

Det skal bemærkes, at i tilfælde af en kvadratisk funktion, finder Newtons metode et ekstremum i én iteration.

At finde den hessiske matrix er beregningsmæssigt dyrt og ofte ikke muligt. I sådanne tilfælde kan kvasi-newtonske metoder tjene som et alternativ , hvor en tilnærmelse af den hessiske matrix bygges i processen med at akkumulere information om funktionens krumning.

Newton-Raphson metode

Newton-Raphson metoden er en forbedring af Newtons ekstremum metode beskrevet ovenfor. Den største forskel er, at ved den næste iteration vælger en af metoderne til endimensionel optimering det optimale trin:

{\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda _{j}H^{-1}({\vec { x}}^{[j]})\nabla f({\vec {x}}^{[j]}),

hvor For at optimere beregningerne bruges følgende forbedring: i stedet for at genberegne hessian for objektivfunktionen ved hver iteration begrænser vi os til den indledende tilnærmelse og opdaterer den kun én gang i trin, eller opdaterer den slet ikke. $\lambda _{j}=\arg \min _{\lambda }f({\vec {x}}^{[j]}-\lambda H^{-1}({\vec {x} }^{[j]})\nabla f({\vec {x}}^{[j]})).$ $H(f({\vec {x))^{[0]}))$ $m$

Anvendt på opgaver med mindste kvadrater

I praksis er der ofte opgaver, hvor det er nødvendigt at justere de frie parametre for et objekt eller justere den matematiske model til reelle data. I disse tilfælde opstår problemer med mindste kvadrater :

F({\vec {x)))=\|{\vec {f}}({\vec {x}})\|=\sum _{{i=1}}^{m}f_{i} ^{2}({\vec {x}})=\sum _{{i=1}}^{m}(\varphi _{i}({\vec {x}})-{\mathcal {F }}_{i})^{2}\til \min .

Disse problemer er kendetegnet ved en særlig form for gradient og hessisk matrix :

\nabla F({\vec {x)))=2J^{T}({\vec {x))){\vec {f}}({\vec {x}}),

H({\vec {x)))=2J^{T}({\vec {x)))J({\vec {x)))+2Q({\vec {x))),\qquad Q ({\vec {x)))=\sum _{{i=1}}^{m}f_{i}({\vec {x}})H_{i}({\vec {x}}) ,

hvor er Jacobi-matrixen for vektorfunktionen , er den hessiske matrix for dens komponent . $J({\vec {x)))$ ${\vec {f))({\vec {x)))$ $H_{i}({\vec {x)))$ $f_{i}({\vec {x)))$

Derefter bestemmes det næste trin fra systemet: ${\vec {p}}$

\venstre[J^{T}({\vec {x}})J({\vec {x}})+\sum _{{i=1}}^{m}f_{i}({\vec {x)))H_{i}({\vec {x)))\right]{\vec {p}}=-J^{T}({\vec {x}}){\vec {f} }({\vec {x}}).

Gauss-Newton metode

Gauss-Newton-metoden er baseret på den antagelse, at begrebet dominerer over . Dette krav er ikke opfyldt, hvis minimumsresterne er store, det vil sige, hvis normen er sammenlignelig med matrixens maksimale egenværdi . Ellers kan du skrive: $J^{T}({\vec {x)))J({\vec {x)))$ $Q({\vec {x)))$ $\|{\vec {f}}({\vec {x}})\|$ $J^{T}({\vec {x)))J({\vec {x)))$

J^{T}({\vec {x}})J({\vec {x}}){\vec {p}}=-J^{T}({\vec {x}}){\vec {f}}({\vec {x}}).

Når normen er tæt på nul, og matricen har fuld kolonnerangering , adskiller trinnet sig således lidt fra det newtonske (under hensyntagen til ), og metoden kan opnå en kvadratisk konvergenshastighed, selvom de anden afledede ikke tages i betragtning konto. En forbedring af metoden er Levenberg-Marquardt-algoritmen baseret på heuristiske overvejelser. $\|Q({\vec {x)))\|$ $J({\vec {x)))$ ${\vec {p}}$ $Q({\vec {x)))$

Generalisering til det komplekse plan

Indtil nu er der i beskrivelsen af metoden brugt funktioner, der udfører mappings inden for sættet af reelle værdier . Metoden kan dog også anvendes til at finde nulpunktet for en funktion af en kompleks variabel . Proceduren forbliver dog den samme:

z_{n+1}=z_{n}-{\frac {f(z_{n})}{f'(z_{n)))))

Af særlig interesse er valget af den oprindelige tilnærmelse . I lyset af at en funktion kan have flere nuller, kan metoden i forskellige tilfælde konvergere til forskellige værdier, og det er helt naturligt at ville finde ud af, hvilke områder der vil sikre konvergens til en bestemt rod. Dette spørgsmål interesserede Arthur Cayley tilbage i 1879 , men det var først muligt at løse det i 70'erne af det tyvende århundrede med fremkomsten af computerteknologi. Det viste sig, at i skæringspunkterne mellem disse regioner (de kaldes normalt tiltrækningsområder ) dannes såkaldte fraktaler - uendelige selvlignende geometriske figurer. $z_{0}$

På grund af det faktum, at Newton udelukkende anvendte sin metode til polynomier , blev fraktalerne dannet som følge af en sådan anvendelse kendt som Newtons fraktaler eller Newtons puljer .

Implementering

scala

objekt NewtonMethod { valnøjagtighed = 1e -6 @tailrec def metode ( x0 : Double , f : Double => Double , dfdx : Double => Double , e : Double ): Double = { val x1 = x0 - f ( x0 ) / dfdx ( x0 ) if ( abs ( x1 ) - x0 ) < e ) x1 anden metode ( x1 , f , dfdx , e ) } def g ( C : Dobbelt ) = ( x : Dobbelt ) => x * x - C def dgdx ( x : Dobbelt ) = 2 * x def sqrt ( x : Dobbelt ) = x match { case 0 => 0 case x if ( x < 0 ) => Double . NaN tilfælde x if ( x > 0 ) => metode ( x / 2 , g ( x ), dgdx , nøjagtighed ) } }

Python

fra matematik import sin , cos fra at skrive import Kaldbar import unittest def newton ( f : Callable [[ float ], float ], f_prime : Callable [[ float ], float ], x0 : float , eps : float = 1e-7 , kmax : int = 1e3 ) -> float : """ løser f(x) = 0 ved Newtons metode med præcision eps :param f: f :param f_prime: f' :param x0: startpunkt :param eps: præcision ønsket :return: roden af f(x) = 0 """ x , x_prev , i = x0 , x0 + 2 * eps , 0 mens abs ( x - x_prev ) >= eps og i < kmax : x , x_prev , i = x - f ( x ) / f_prime ( x ), x , i + 1 returnere x klasse TestNewton ( unittest . TestCase ): def test_0 ( self ) : def f ( x : float ) -> float : return x ** 2 - 20 * sin ( x ) def f_prime ( x : float ) -> float : returner 2 * x - 20 * cos ( x ) x0 , x_star = 2 , 2,7529466338187049383 selv . assertAlmostEqual ( newton ( f , f_prime , x0 ), x_star ) hvis __navn__ == '__main__' : enhedstest . vigtigste ()

PHP

<?php // PHP 5.4 function newtons_method ( $a = - 1 , $b = 1 , $f = function ( $x ) { returner pow ( $x , 4 ) - 1 ; }, $derivat_f = funktion ( $x ) { returner 4 * pow ( $x , 3 ); }, $eps = 1E-3 ) { $xa = $a ; $xb = $b ; $iteration = 0 ; while ( abs ( $xb ) > $eps ) { $p1 = $f ( $xa ); $q1 = $derivat_f ( $xa ); $xa -= $p1 / $q1 ; $xb = $p1 ; ++ $iteration ; } returnere $xa ; }

Oktav

funktion res = nt () eps = 1e-7 ; x0_1 = [ -0,5 , 0,5 ] ; max_iter = 500 ; xopt = ny (@ resh , eps , max_iter ); xopt slutfunktion funktion a = ny ( f, eps, max_iter ) x = -1 ; _ p0 = 1 ; i = 0 _ while ( abs ( p0 ) > = eps ) [ p1 , q1 ]= f ( x ); x = x - p1 / q1 ; p0 = p1 ; i = i + 1 ; ende i a = x ; slutfunktionsfunktion [p , q] = resh ( x ) % p= -5*x.^5+4*x.^4-12*x.^3+11*x.^2-2*x+1; p = - 25 * x .^ 4 + 16 * x .^ 3 - 36 * x .^ 2 + 22 * x - 2 ; q = - 100 * x .^ 3 + 48 * x .^ 2 - 72 * x + 22 ; afslutte funktion

Delphi

// beregnet funktion funktion fx ( x : Dobbelt ) : Dobbelt ; begynde Resultat := x * x - 17 ; ende ; // afledt funktion af f(x) funktion dfx ( x : Dobbelt ) : Dobbelt ; begynde Resultat := 2 * x ; ende ; function solve ( fx , dfx : TFunc < Double , Double >; x0 : Double ) : Double ; const eps = 0,000001 ; var x1 : Dobbelt ; begynde x1 := x0 - fx ( x0 ) / dfx ( x0 ) ; // første tilnærmelse mens ( Abs ( x1 - x0 ) > eps ) begynder // indtil præcision 0,000001 er nået x0 : = x1 ; x1 := x1 - fx ( x1 ) / dfx ( x1 ) ; // efterfølgende tilnærmelser slutter ; Resultat := x1 ; ende ; // Kald løse ( fx , dfx , 4 ) ;

C++

#include <iostream> #include <math.h> double fx ( double x ) { return x * x - 17 ;} // beregnet funktion double dfx ( double x ) { return 2 * x ;} // funktionsafledt typedef double ( * funktion ) ( dobbelt x ); // tildeling af type funktion double solve ( funktion fx , funktion dfx , double x0 , double eps = 1e-8 ) { dobbelt xi = x0 ; //Aktuelt punkt ved i-te iteration while ( fabs ( fx ( xi )) >= eps ) // indtil præcision 0,00000001 er nået xi = xi - fx ( xi ) / dfx ( xi ); // efterfølgende tilnærmelser returnerer xi ; } int main () { std :: cout << solve ( fx , dfx , 4 ) << std :: endl ; returnere 0 ; }

C

typedef double ( * funktion ) ( dobbelt x ); double TangentsMethod ( funktion f , funktion df , dobbelt xn , dobbelt eps ) { dobbelt x1 = xn - f ( xn ) / df ( xn ); dobbelt x0 = xn ; while ( abs ( x0 - x1 ) > eps ) { x0 = x1 ; xl = xl - f ( xl ) / df ( xl ); } returnere x1 ; } //Vælg indledende gæt xn = MyFunction ( A ) * My2Derivative ( A ) > 0 ? B : A ; double MyFunction ( double x ) { return ( pow ( x , 5 ) - x - 0,2 ); } //Din funktion double MyDerivative ( double x ) { return ( 5 * pow ( x , 4 ) - 1 ); } //First derivative double My2Derivative ( double x ) { return ( 20 * pow ( x , 3 )); } //Anden afledet //Eksempel på at kalde en funktion dobbelt x = TangentsMethod ( MyFunction , MyDerivative , xn , 0.1 )

Haskell

importer Data.List ( iterate ' ) main :: IO () main = print $ solve ( \ x -> x * x - 17 ) ( * 2 ) 4 - Løsningsfunktionen er universel for alle rigtige typer, hvis værdier kan sammenlignes. solve = esolve 0,000001 esolve epsilon func deriv x0 = fst . head $ dropWhile pred - par hvor pred ( xn , xn1 ) = ( abs $ xn - xn1 ) > epsilon -- Pred-funktionen bestemmer om den nødvendige præcision er nået. næste xn = xn - func xn / deriv xn -- Den næste funktion beregner en ny tilnærmelse. iters = iterate' næste x0 -- En uendelig liste over iterationer. par = zip iters ( tail iters ) -- En uendelig liste over par af iterationer af formen: [(x0, x1), (x1, x2) ..].

Litteratur

Akulich I. L. Matematisk programmering i eksempler og opgaver: Proc. godtgørelse for studerendes økonomi. specialist. universiteter. - M . : Højere skole, 1986. - 319 s. : syg. - BBK 22.1 A44 . - UDC 517,8 .
Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Beregningsmetoder for ingeniører: Proc. godtgørelse. - M . : Højere skole, 1994. - 544 s. : syg. - BBK 32,97 A62 . - UDC 683.1 . — ISBN 5-06-000625-5 .
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Numeriske metoder. - 8. udg. - M . : Laboratoriet for grundlæggende viden, 2000.
Vavilov S. I. Isaac Newton . - M. : Red. USSR's Videnskabsakademi, 1945.
Volkov E. A. Numeriske metoder. — M .: Fizmatlit, 2003.
Gill F., Murray W., Wright M. Praktisk optimering. Om. fra engelsk. — M .: Mir, 1985.
Korn G., Korn T. Håndbog i matematik for videnskabsmænd og ingeniører. - M . : Nauka, 1970. - S. 575-576.
Korshunov Yu. M., Korshunov Yu. M. Matematiske grundlag for kybernetik. - Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmer til løsning af problemer med ikke-lineær programmering. - M .: MEPhI, 1982.
Morozov AD Introduktion til teorien om fraktaler. - MEPhI, 2002.

Se også

Links

"Newtons puljer" på fractalworld.xaoc.ru
"Isaac Newton" på www.scottish-wetlands.org
"Kantorovichs matematiske værker" på webstedet for Institut for Matematik ved SB RAS
Hazewinkel, Michiel, red. (2001), Newton-metoden , Encyclopedia of Mathematics , Springer , ISBN 978-1-55608-010-4
Weisstein, Eric W. Newtons metode (engelsk) på Wolfram MathWorld -webstedet .
Newtons metode, Citizendium.
Mathews, J., The Accelerated and Modified Newton Methods, Kursusnotater.
Wu, X., Roots of Equations, Course notes.

Optimeringsmetoder _
Endimensionel	gyldne snit metode Modsætning Parabel metode Netsøgning Ensartet bloksøgningsmetode Fibonacci metode Ternær søgning Piyavsky metode Strongin metode
Nul orden	Gauss metode Nelder-Mead metode Hook-Jeeves metode Rosenbrock metode Powell metode
Første ordre	gradient nedstigning Zeutendijk metode Koordinat nedstigning Konjugeret gradientmetode Kvasi-newtonske metoder Levenberg-Marquardt algoritme
anden orden	Newtons metode Newton-Raphson metode Broyden-Fletcher-Goldfarb-Shanno-algoritme (BFGS)
Stokastisk	Monte Carlo metode Simuleret udglødning Evolutionære algoritmer differentiel evolution Myre-algoritme Partikelsværmmetode Algorithme for bikoloni Tilfældig gå-metode
Lineære programmeringsmetoder _	Enkel metode Gomoris algoritme Ellipsoid metode Potentielle metode
Ikke-lineære programmeringsmetoder	Sekventiel kvadratisk programmering