Newtons metod

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 25 januari 2022; kontroller kräver 3 redigeringar .

Newtons metod, Newtons algoritm ( även känd som tangentmetoden ) är en iterativ numerisk metod för att hitta roten ( noll ) av en given funktion . Metoden föreslogs först av den engelske fysikern , matematikern och astronomen Isaac Newton ( 1643-1727 ) . Sökandet efter en lösning utförs genom att konstruera successiva approximationer och bygger på principerna för enkel iteration . Metoden har kvadratisk konvergens . En modifiering av metoden är metoden för ackord och tangenter . Dessutom kan Newtons metod användas för att lösa optimeringsproblem där det krävs att bestämma nollpunkten för den första derivatan eller gradienten i fallet med ett flerdimensionellt utrymme.

Beskrivning av metoden

Motivering

För att numeriskt lösa ekvationen med den enkla iterationsmetoden måste den reduceras till en ekvivalent ekvation: , där är sammandragningsavbildningen . $f(x)=0$ $x=\varphi(x)$ $\varphi$

För bästa konvergens av metoden vid punkten för nästa approximation måste villkoret vara uppfyllt . Lösningen av denna ekvation söks i formen , då: $x^{*}$ $\varphi '(x^{*})=0$ $\varphi (x)=x+\alpha (x)f(x)$

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

Om man antar att approximationspunkten är "tillräckligt nära" roten och att den givna funktionen är kontinuerlig , är den slutliga formeln för : ${\tilde {x}}$ $(f(x^{*})\approx f({\tilde {x)))=0)$ $\alfa(x)$

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

Med detta i åtanke är funktionen definierad: $\varphi(x)$

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

Under vissa förhållanden utför denna funktion en sammandragningsmappning i ett område av roten.

Bevis

Låt en funktion av en reell variabel ges som är två gånger kontinuerligt differentierbar i sin definitionsdomän och vars derivata aldrig försvinner:

\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.}

Och det är nödvändigt att bevisa att funktionen utför en sammandragningsmappning nära roten av ekvationen . $\scriptstyle {\varphi (x)=x-{\frac {f(x)}{f'(x)))}$ $\scriptstyle {f(x)=0}$

På grund av funktionens kontinuerliga differentiabilitet och olikheten noll är dess första derivata kontinuerlig . $\scriptstyle {f(x)}$ $\scriptstyle {\varphi (x)}$

Derivaten är: $\scriptstyle {\varphi '(x)}$

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

Under de villkor som ställs på är den också kontinuerlig. Låt vara den önskade roten till ekvationen: , därför i dess grannskap : $\scriptstyle {f(x)}$ $\scriptstyle {{\tilde {x}}}$ $\scriptstyle {f({\tilde {x)))=0}$ $\scriptstyle {\varphi '(x)\approx 0}$

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

Sedan enligt Lagranges sats :

\scriptstyle {\forall x_{1},\;x_{2}\in {\mathrm {U}}_{\delta }({\tilde {x)))\;\exists \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 av det faktum att i samma deltakvarter är följande sant: $\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ålunda erhållna funktionen i närheten av roten implementerar en sammandragningsmappning . ■ $\scriptstyle {\varphi (x)}$ $\scriptstyle {U_{\delta }({\tilde {x)))}$

I detta fall reduceras algoritmen för att hitta en numerisk lösning till ekvationen till en iterativ beräkningsprocedur : $f(x)=0$

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

Enligt Banachs teorem tenderar sekvensen av approximationer till roten av ekvationen . $f(x)=0$

Geometrisk tolkning

Huvudidén med metoden är följande: den initiala approximationen sätts nära den hypotetiska roten, varefter en tangent till grafen för funktionen som studeras plottas vid approximationspunkten, för vilken skärningspunkten med abskissaxeln är hittades. Denna punkt tas som nästa approximation. Och så vidare, tills den erforderliga noggrannheten uppnås.

Låt 1) en verkligt värderad funktion vara kontinuerligt differentierbar på intervallet ; 2) det finns en nödvändig punkt : ; 3) det finns också sådana att för och för ; 4) poängen är sådan att . Sedan kan formeln för iterativ approximation till k härledas från tangentens geometriska betydelse enligt följande: $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}}},

var är lutningsvinkeln för tangentlinjen till grafen vid punkten . $\alpha _{n}$ ${\displaystyle y(x)=f(x_{n})+(x-x_{n})\cdot \mathrm {tg} \,\alpha _{n))$ $f$ $(x_{n};f(x_{n}))$

Därför (i tangentlinjens ekvation antar vi ) har det önskade uttrycket för formen: $y(x_{n+1})=0$ $x_{{n+1}}$

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

Om , då kan detta värde användas som nästa approximation till . $x_{n+1}\in (a,\,b)$ $x^{{*}}$

Om , så finns det en "flykt" (roten ligger nära gränsen ). I det här fallet är det nödvändigt (med hjälp av idén om halveringsmetoden ) att ersätta med tills punkten "återgår" till sökområdet . $x_{n+1}\notin (a,\,b)$ $x^{{*}}$ $(a,\,b)$ $x_{{n+1}}$ ${\frac {x_{n}+x_{n+1}}{2}}$ $(a,\,b)$

Anmärkningar. 1) Närvaron av en kontinuerlig derivata gör det möjligt att bygga en kontinuerligt föränderlig tangent på hela området för sökningen efter en lösning . 2) Fall av gräns (vid en punkt eller vid en punkt ) placering av den önskade lösningen betraktas på liknande sätt. 3) Ur geometrisk synvinkel betyder likhet att tangentlinjen till grafen i punkten - är parallell med axeln och inte skär den i slutet. 4) Ju större konstant och ju mindre konstant från punkt 3 av villkoren, desto närmare skärningspunkten för tangenten till grafen och axeln till punkten , det vill säga desto närmare värdet till det önskade . $(a,\,b)\;$
$a$ $b$ $x^{{*}}$
$f'(x_{n})=0$ $f$ $(x_{n};f(x_{n}))$ $OXE$ $f(x_{n})\neq 0$
$C > 0$ $\delta>0$ $x_{n}\in (a,\,x^{*}-\delta ]\cup [x^{*}+\delta ,\,b)$ $f$ $OXE$ $(x^{*};\;0)$ $x_{{n+1}}$ $x^{*}\in (a,\,b)$

Den iterativa processen börjar med en viss initial approximation , och mellan och den önskade punkten bör det inte finnas andra nollor i funktionen , det vill säga "ju närmare den önskade roten , desto bättre." Om det inte finns några antaganden om att hitta , kan trial and error begränsa intervallet av möjliga värden genom att tillämpa mellanvärdessatsen . $x_{0}\in (a,\,b)$ $x_{0}\in (a,\,b)$ $x^{*}\in (a,\,b)$ $f$ $x_{0}$ $x^{{*}}$ $x^{{*}}$

För fördefinierade slutar den iterativa processen om och . I synnerhet för visningsmatrisen och kan beräknas baserat på grafens displayskala , det vill säga om och faller i en vertikal och i en horisontell rad. $\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})$

Algoritm

Den initiala approximationen är inställd . $x_{0}$
Tills stoppvillkoret är uppfyllt, vilket kan tas som eller (det vill säga felet ligger inom de erforderliga gränserna), beräknas en ny approximation: . $|x_{n+1}-x_{n}|<\varepsilon$ $|f(x_{n+1})|<\varepsilon$ $x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n))}}$

Exempel

Tänk på problemet med att hitta positivt , för vilket . Denna uppgift kan representeras som uppgiften att hitta nollpunkten för funktionen . Vi har ett uttryck för derivatan . Eftersom för alla och för , är det uppenbart att lösningen ligger mellan 0 och 1. Låt oss ta värdet som en initial approximation , då: $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})))&=&\understryka {0 {,}}909\;672\;693\;736,\\x_{3}&=&x_{2}-{\dfrac {f(x_{2})}{f'(x_{2})} }&=&\understryka {0{,}86}7\;263\;818\;209,\\x_{4}&=&x_{3}-{\dfrac {f(x_{3})}{ f'(x_{3})}}&=&\understryka {0{,}865\;47}7\;135\;298,\\x_{5}&=&x_{4}-{\dfrac { f(x_{4})}{f'(x_{4})}}&=&\understryka {0{,}865\;474\;033\;1}11,\\x_{6}&= &x_{5}-{\dfrac {f(x_{5})}{f'(x_{5})}}&=&\understrecka {0{,}865\;474\;033\;102}. \end{matris}}

Giltiga signifikanta siffror är understrukna . Det kan ses att deras antal ökar från steg till steg (ungefär fördubblas med varje steg): från 1 till 2, från 2 till 5, från 5 till 10, vilket illustrerar den kvadratiska konvergenshastigheten .

Användarvillkor

Låt oss överväga ett antal exempel som pekar på bristerna i metoden.

Motexempel

Om den initiala approximationen inte är tillräckligt nära lösningen, kanske metoden inte konvergerar.

Låta

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

Sedan

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

Låt oss ta noll som en första gissning. Den första iterationen ger enheten som en approximation. I sin tur kommer tvåan återigen att ge noll. Metoden kommer att loopa och ingen lösning kommer att hittas. Generellt sett kan konstruktionen av en sekvens av approximationer vara mycket förvirrande .

Om derivatan inte är kontinuerlig vid rotens punkt, kan metoden divergera i vilket område som helst av roten.

Tänk på en funktion:

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

Då och överallt utom 0. $f'(0)=1$ $f'(x)=1+2x\sin(2/x)-2\cos(2/x)$

I närheten av roten ändrar derivatan tecken när den närmar sig noll från höger eller vänster. Medan för . $x$ $f(x)\geqslant xx^{2}>0$ $0<x<1$

Således är den inte begränsad nära roten, och metoden kommer att divergera, även om funktionen är differentierbar överallt, dess derivata är icke-noll vid roten, oändligt differentierbar överallt utom vid roten, och dess derivata är avgränsad runt roten . $f(x)/f'(x)$ $f$

Om det inte finns någon andraderivata vid rotpunkten kan metodens konvergenshastighet minskas märkbart.

Tänk på ett exempel:

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

Då och utom där det inte är definierat. ${\displaystyle f'(x)=1+(4/3)x^{1/3))$ ${\displaystyle f''(x)=(4/9)x^{-2/3))$ $x=0$

I nästa steg 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})}}.

Konvergenshastigheten för den resulterande sekvensen är ungefär 4/3. Detta är betydligt mindre än 2, vilket är nödvändigt för kvadratisk konvergens, så i detta fall kan vi bara tala om linjär konvergens, även om funktionen är kontinuerligt differentierbar överallt , är derivatan vid roten inte lika med noll, och är oändligt differentierbar överallt utom vid roten. $f$

Om derivatan vid rotpunkten är lika med noll, kommer konvergenshastigheten inte att vara kvadratisk, och själva metoden kan avsluta sökningen i förtid och ge en approximation som är felaktig för en given noggrannhet.

Låta

f(x)=x^{2}.

Då och därav . Metodens konvergens är alltså inte kvadratisk, utan linjär, även om funktionen är oändligt differentierbar överallt. $f'(x)=2x$ $xf(x)/f'(x)=x/2$

Begränsningar

Låt ekvationen ges , var och det är nödvändigt att hitta sin lösning. $f(x)=0$ $f(x)\colon \mathbb {X} \to \mathbb {R}$

Nedan följer formuleringen av huvudsatsen, som gör att vi kan ge tydliga förutsättningar för tillämpbarhet. Den bär namnet på den sovjetiske matematikern och ekonomen Leonid Vitalievich Kantorovich ( 1912-1986 ) .

Kantorovichs teorem.

Om det finns konstanter så att: $A,\;B,\;C$

${\frac {1}{|f'(x)|}}<A$ på , det vill säga den existerar och är inte lika med noll; $[a,\;b]$ $f'(x)$
$\left|{\frac {f(x)}{f'(x)}}\right|<B$ på , det vill säga begränsad; $[a,\;b]$ $f(x)$
$\exists f''(x)$ på , och ; $[a,\;b]$ $|f''(x)|\leqslant C\leqslant {\frac {1}{2AB))$

Dessutom längden på det betraktade segmentet . Då är följande påståenden sanna: $|ab|<{\frac {1}{AB}}\left(1-{\sqrt {1-2ABC}}\right)$

det finns en rot av ekvationen ; $[a,\;b]$ $x^{*}$ $f(x)=0\colon \exists x^{*}\in [a,\;b]\colon f(x^{*})=0$
om , då konvergerar den iterativa sekvensen till denna rot: ; $x_{0}={\frac {a+b}{2))$ $\left\{x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})))\right\}\to x^ {*}$
felet kan uppskattas med formeln . $|x^{*}-x_{n}|\leqslant {\frac {B}{2^{n-1}}}(2ABC)^{2^{n-1}}$

Från det sista påståendet i satsen, i synnerhet, följer metodens kvadratiska 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}.

Då kommer begränsningarna för den ursprungliga funktionen att se ut så här: $f(x)$

funktionen måste begränsas;
funktionen måste vara jämn , två gånger differentierbar ;
dess första derivata är enhetligt separerad från noll; $f'(x)$
dess andra derivata måste vara enhetligt begränsad. $f''(x)$

Historisk bakgrund

Metoden beskrevs av Isaac Newton i manuskriptet On the Analysis by Equations of Infinite Series ( latin: De analysi per aequationes numero terminorum infinitas ) adresserat till Barrow 1669 , och i The Method of Fluxions and Infinite Series ( latin: De metodis fluxionum et serierum infinitarum" ) eller " Analytisk geometri " ( lat. "Geometria analytica" ) i samlingarna av Newtons verk, som skrevs 1671 . I sina skrifter introducerar Newton begrepp som expansionen av en funktion till en serie , infinitesimals och fluxioner ( derivator i nuvarande mening). Dessa verk publicerades mycket senare: det första publicerades 1711 tack vare William Johnson, det andra publicerades av John Colzon 1736 efter skaparens död. Men beskrivningen av metoden skilde sig väsentligt från hans nuvarande utläggning: Newton tillämpade sin metod uteslutande på polynom . Han beräknade inte successiva approximationer , utan en sekvens av polynom och som ett resultat fick en ungefärlig lösning . $x_{n}$ $x$

Metoden publicerades först i avhandlingen "Algebra" av John Wallis 1685, på vars begäran den kortfattat beskrevs av Newton själv. År 1690 publicerade Joseph Raphson en förenklad beskrivning i sin "Analysis aequationum universalis" ( latin: "Analysis aequationum universalis" ). Raphson såg Newtons metod som rent algebraisk och begränsade dess tillämpning till polynom, men han beskrev metoden i termer av successiva approximationer istället för den svårare att förstå sekvensen av polynom som används av Newton. Slutligen, 1740, beskrevs Newtons metod av Thomas Simpson som en första ordningens iterativ metod för att lösa icke-linjära ekvationer med hjälp av en derivata, som presenteras här. I samma publikation generaliserade Simpson metoden till fallet med ett system med två ekvationer och noterade att Newtons metod också kan tillämpas på optimeringsproblem genom att hitta nollpunkten för derivatan eller gradienten . $x_{n}$

År 1879 var Arthur Cayley , i The Newton-Fourier imaginary problem, den förste som påpekade svårigheterna med att generalisera Newtons metod till fallet med imaginära rötter av polynom av högre grad än de andra och komplexa initiala approximationerna. Detta arbete banade väg för studier av fraktal teori .

Generaliseringar och ändringar

Sekantmetoden

Den relaterade sekantmetoden är Newtons "ungefärliga" metod och undviker att beräkna derivatan. Värdet på derivatan i den iterativa formeln ersätts av dess uppskattning för de två föregående iterationspunkterna:

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

Således har huvudformeln formen

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

Denna metod liknar Newtons, men har en något långsammare konvergenshastighet. Metodens konvergensordning är lika med det gyllene snittet - 1,618 ...

Anmärkningar. 1) För att starta den iterativa processen krävs två olika värden av och . 2) I motsats till den "riktiga Newtonmetoden" (tangensmetoden), som endast kräver lagring (och tillfälligt under beräkningar och ), kräver sekantmetoden att spara , , , . 3) Den används om beräkningen är svår (till exempel kräver den en stor mängd maskinresurser: tid och/eller minne). $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)$

One tangent-metod

För att minska antalet anrop till värdena för derivatan av en funktion används den så kallade entangentmetoden.

Iterationsformeln för denna metod är:

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

Kärnan i metoden är att beräkna derivatan endast en gång, vid den initiala approximationspunkten , och sedan använda detta värde vid varje efterföljande iteration: $x_{0}$

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

Med detta val gäller följande jämlikhet vid punkten : $\alpha _{0}$ $x_{0}$

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

och om segmentet på vilket närvaron av en rot antas och den initiala approximationen väljs är tillräckligt liten, och derivatan är kontinuerlig, kommer värdet inte att skilja sig mycket från och därför kommer grafen att passera nästan horisontellt och skära rak linje , vilket i sin tur kommer att säkerställa snabb konvergens av sekvensen av approximationspunkter till roten. $x^{*}$ $x_{0}$ $\varphi '(x)$ $\varphi '(x^{*})$ $\varphi '(x_{0})=0$ $y=\varphi (x)$ $y=x$

Denna metod är ett specialfall av den enkla iterationsmetoden . Den har en linjär konvergensordning.

Flerdimensionellt fall

Låt oss generalisera det erhållna resultatet till det flerdimensionella fallet.

Låt det vara nödvändigt att hitta 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.

Genom att välja ett initialt värde , hittas successiva approximationer genom att lösa ekvationssystem : ${\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,

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

Som tillämpat på optimeringsproblem

Låt det vara nödvändigt att hitta minimum av en funktion av flera variabler . Denna uppgift är likvärdig med problemet att hitta nollpunkten för gradienten . Låt oss tillämpa ovanstående Newtons metod: $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,

var är hessian för funktionen . $H({\vec {x)))$ $f({\vec {x)))$

I en mer bekväm iterativ form ser detta uttryck ut så här:

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

Det bör noteras att i fallet med en kvadratisk funktion hittar Newtons metod ett extremum i en iteration.

Att hitta den hessiska matrisen är beräkningsmässigt dyrt och ofta omöjligt. I sådana fall kan kvasi-newtonska metoder fungera som ett alternativ , där en approximation av den hessiska matrisen byggs i processen att ackumulera information om funktionens krökning.

Newton-Raphson-metoden

Newton-Raphson-metoden är en förbättring av Newtons extremummetod som beskrivs ovan. Den största skillnaden är att vid nästa iteration väljer en av metoderna för endimensionell optimering det optimala steget:

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

där För att optimera beräkningarna används följande förbättring: istället för att räkna om hessian för objektivfunktionen vid varje iteration begränsar vi oss till den initiala approximationen och uppdaterar den bara en gång i steg, eller uppdaterar den inte alls. $\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$

Tillämpas på problem med minsta kvadrater

I praktiken finns det ofta uppgifter där det krävs att justera de fria parametrarna för ett objekt eller justera den matematiska modellen till verkliga data. I dessa fall visas minsta kvadratproblem :

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

Dessa problem kännetecknas av en speciell sorts gradient och hessisk matris :

\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)))=\summa _{{i=1}}^{m}f_{i}({\vec {x}})H_{i}({\vec {x}}) ,

där är Jacobi-matrisen för vektorfunktionen , är den hessiska matrisen för dess komponent . $J({\vec {x)))$ ${\vec {f))({\vec {x)))$ $H_{i}({\vec {x)))$ $f_{i}({\vec {x)))$

Sedan bestäms nästa steg från systemet: ${\vec {p}}$

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

Gauss-Newton-metoden

Gauss-Newton-metoden bygger på antagandet att termen dominerar över . Detta krav uppfylls inte om minimiresterna är stora, det vill säga om normen är jämförbar med matrisens maximala egenvärde . Annars kan du skriva: $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}}).

Således, när normen är nära noll, och matrisen har full kolumnrankning , skiljer sig steget lite från det Newtonska (med hänsyn till ), och metoden kan uppnå en kvadratisk konvergenshastighet, även om andraderivatorna inte tas med i konto. En förbättring av metoden är Levenberg-Marquardt-algoritmen baserad på heuristiska överväganden. $\|Q({\vec {x)))\|$ $J({\vec {x)))$ ${\vec {p}}$ $Q({\vec {x)))$

Generalisering till det komplexa planet

Fram till nu, i beskrivningen av metoden, användes funktioner som utför mappningar inom uppsättningen av verkliga värden . Metoden kan dock också användas för att hitta nollpunkten för en funktion av en komplex variabel . Proceduren förblir dock densamma:

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

Av särskilt intresse är valet av den initiala uppskattningen . Med tanke på att en funktion kan ha flera nollor kan metoden i olika fall konvergera till olika värden, och det är ganska naturligt att vilja ta reda på vilka områden som säkerställer konvergens till en viss rot. Denna fråga intresserade Arthur Cayley redan 1879 , men det var bara möjligt att lösa den på 70 -talet av 1900-talet med tillkomsten av datorteknik. Det visade sig att i skärningspunkterna mellan dessa regioner (de kallas vanligtvis attraktionsregioner ) bildas så kallade fraktaler - oändliga självliknande geometriska figurer. $z_{0}$

På grund av det faktum att Newton tillämpade sin metod uteslutande på polynom , blev fraktalerna som bildades som ett resultat av en sådan ansökan kända som Newtons fraktaler eller Newtons pooler .

Implementering

scala

objekt NewtonMethod { valnoggrannhet = 1e -6 @tailrec def method ( x0 : Double , f : Double => Double , dfdx : Double => Double , e : Double ): Double = { val x1 = x0 - f ( x0 ) / dfdx ( x0 ) if ( abs ( x1 ) - x0 ) < e ) x1 annan metod ( x1 , f , dfdx , e ) } def g ( C : Double ) = ( x : Double ) => x * x - C def dgdx ( x : Dubbel ) = 2 * x def sqrt ( x : Double ) = x match { case 0 => 0 case x if ( x < 0 ) => Double . NaN fall x if ( x > 0 ) => metod ( x / 2 , g ( x ), dgdx , noggrannhet ) } }

Python

från matte import sin , cos från att skriva import Callable 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 med Newtons metod med precision eps :param f: f :param f_prime: f' :param x0: startpunkt :param eps: precision önskad :return: roten av f(x) = 0 """ x , x_prev , i = x0 , x0 + 2 * eps , 0 medan abs ( x - x_prev ) >= eps och i < kmax : x , x_prev , i = x - f ( x ) / f_prime ( x ), x , i + 1 tillbaka x klass TestNewton ( unittest . TestCase ): def test_0 ( self ) : def f ( x : float ) -> float : return x ** 2 - 20 * sin ( x ) def f_prime ( x : float ) -> float : return 2 * x - 20 * cos ( x ) x0 , x_star = 2 , 2,7529466338187049383 själv . assertAlmostEqual ( newton ( f , f_prime , x0 ), x_star ) if __name__ == '__main__' : unittest . huvud ()

PHP

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

Octave

funktion res = nt () eps = 1e-7 ; x0_1 = [ -0,5 , 0,5 ] ; max_iter = 500 ; xopt = new (@ resh , eps , max_iter ); xopt slutfunktionsfunktion a = ny ( f, eps, max_iter ) x = -1 ; _ p0 = 1 ; i = 0 _ while ( abs ( p0 ) > = eps ) [ p1 , q1 ]= f ( x ); x = x - pl / ql ; p0 = pl ; i = i + 1 ; slut 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 ; slutfunktion

Delphi

// beräknad funktion funktion fx ( x : Dubbel ) : Dubbel ; börja Resultat := x * x - 17 ; slut ; // härledd funktion av f(x) funktion dfx ( x : Double ) : Double ; börja Resultat := 2 * x ; slut ; function solve ( fx , dfx : TFunc < Double , Double > ; x0 : Double ) : Double ; const eps = 0,000001 ; var x1 : Dubbel ; börja x1 := x0 - fx ( x0 ) / dfx ( x0 ) ; // första approximationen medan ( Abs ( x1 - x0 ) > eps ) börjar // tills precision 0,000001 uppnås x0 := x1 ; x1 := x1 - fx ( x1 ) / dfx ( x1 ) ; // efterföljande uppskattningar slutar ; Resultat := x1 ; slut ; // Call solve ( fx , dfx , 4 ) ;

C++

#include <iostream> #inkludera <math.h> double fx ( double x ) { return x * x - 17 ;} // beräknad funktion double dfx ( double x ) { return 2 * x ;} // funktionsderivata typedef dubbel ( * funktion ) ( dubbel x ); // tilldelning av typfunktion dubbel lösa ( funktion fx , funktion dfx , dubbel x0 , dubbel eps = 1e-8 ) { dubbel xi = x0 ; //Aktuell punkt vid i-te iterationen while ( fabs ( fx ( xi )) >= eps ) // tills precision 0,00000001 uppnås xi = xi - fx ( xi ) / dfx ( xi ); // efterföljande approximationer returnerar xi ; } int main () { std :: cout << solve ( fx , dfx , 4 ) << std :: endl ; returnera 0 ; }

C

typedef dubbel ( * funktion ) ( dubbel x ); double TangentsMethod ( funktion f , funktion df , dubbel xn , dubbel eps ) { dubbel xl = xn - f ( xn ) / df ( xn ); dubbel x0 = xn ; while ( abs ( x0 - x1 ) > eps ) { x0 = xl ; xl = xl - f ( xl ) / df ( xl ); } returnera x1 ; } //Välj initial gissning xn = MyFunction ( A ) * My2Derivative ( A ) > 0 ? B : A ; double MyFunction ( double x ) { return ( pow ( x , 5 ) - x - 0,2 ); } //Din funktion dubbel MyDerivative ( double x ) { return ( 5 * pow ( x , 4 ) - 1 ); } //Första derivatan dubbel My2Derivative ( double x ) { return ( 20 * pow ( x , 3 )); } //Andra derivata //Exempel på att anropa en funktion dubbel x = TangentsMethod ( MyFunction , MyDerivative , xn , 0.1 )

Haskell

importera Data.List ( iterate ' ) main :: IO () main = print $ solve ( \ x -> x * x - 17 ) ( * 2 ) 4 -- Lösningsfunktionen är universell för alla verkliga typer vars värden kan jämföras. lösa = esolve 0,000001 esolve epsilon func deriv x0 = fst . head $ dropWhile pred- par där pred ( xn , xn1 ) = ( abs $ xn - xn1 ) > epsilon -- Pred-funktionen avgör om den erforderliga precisionen har uppnåtts. nästa xn = xn - func xn / deriv xn -- Nästa funktion beräknar en ny approximation. iters = iterate' next x0 -- En oändlig lista med iterationer. par = zip iters ( tail iters ) -- En oändlig lista med par av iterationer av formen: [(x0, x1), (x1, x2) ..].

Litteratur

Akulich I. L. Matematisk programmering i exempel och uppgifter: Proc. bidrag för studenters ekonomi. specialist. universitet. - M . : Högre skola, 1986. - 319 sid. : sjuk. - BBK 22.1 A44 . - UDC 517,8 .
Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Beräkningsmetoder för ingenjörer: Proc. ersättning. - M . : Högre skola, 1994. - 544 sid. : sjuk. - BBK 32,97 A62 . - UDC 683.1 . — ISBN 5-06-000625-5 .
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Numeriska metoder. - 8:e uppl. - M . : Laboratory of Basic Knowledge, 2000.
Vavilov S. I. Isaac Newton . - M. : Ed. USSR:s vetenskapsakademi, 1945.
Volkov E. A. Numeriska metoder. — M .: Fizmatlit, 2003.
Gill F., Murray W., Wright M. Praktisk optimering. Per. från engelska. — M .: Mir, 1985.
Korn G., Korn T. Handbok i matematik för vetenskapsmän och ingenjörer. - M . : Nauka, 1970. - S. 575-576.
Korshunov Yu. M., Korshunov Yu. M. Matematiska grunder för cybernetik. - Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmer för att lösa problem med olinjär programmering. — M .: MEPhI, 1982.
Morozov AD Introduktion till teorin om fraktaler. — MEPhI, 2002.

Se även

Länkar

"Newtons pooler" på fractalworld.xaoc.ru
"Isaac Newton" på www.scottish-wetlands.org
"Kantorovichs matematiska verk" på webbplatsen för Institute of Mathematics of SB RAS
Hazewinkel, Michiel, red. (2001), Newton method , Encyclopedia of Mathematics , Springer , ISBN 978-1-55608-010-4
Weisstein, Eric W. Newtons metod (engelska) på Wolfram MathWorld- webbplatsen .
Newtons metod, Citizendium.
Mathews, J., The Accelerated and Modified Newton Methods, Kursanteckningar.
Wu, X., Roots of Equations, Kursanteckningar.

Optimeringsmetoder _
En-dimensionell	gyllene snittmetoden Dikotomi Parabolmetoden Rutnätssökning Enhetlig blocksökningsmetod Fibonacci-metoden Ternär sökning Piyavsky-metoden Strongin metod
Noll ordning	Gauss metod Nelder-Mead metod Hook-Jeeves metod Rosenbrock-metoden Powell metod
Första beställning	lutning nedstigning Zeutendijk-metoden Koordinera nedstigning Konjugerad gradientmetod Kvasi-newtonska metoder Levenberg-Marquardts algoritm
andra beställning	Newtons metod Newton-Raphson-metoden Broyden-Fletcher-Goldfarb-Shanno-algoritm (BFGS)
Stokastisk	Monte Carlo metoden Simulerad glödgning Evolutionära algoritmer differentiell evolution Myralgoritm Partikelsvärmmetod Algoritm för bikoloni Random walk-metod
Linjära programmeringsmetoder _	Enkel metod Gomoris algoritm Ellipsoid metod Potentiell metod
Icke -linjära programmeringsmetoder	Sekventiell kvadratisk programmering