Newtonin menetelmä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 25. tammikuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Newtonin menetelmä, Newtonin algoritmi ( tunnetaan myös tangenttimenetelmänä ) on iteratiivinen numeerinen menetelmä tietyn funktion juuren ( nolla ) löytämiseksi . Menetelmän ehdotti ensimmäisenä englantilainen fyysikko , matemaatikko ja tähtitieteilijä Isaac Newton ( 1643-1727 ) . Ratkaisun etsintä tehdään peräkkäisten approksimaatioiden muodostamalla ja se perustuu yksinkertaisen iteroinnin periaatteisiin . Menetelmällä on neliöllinen konvergenssi . Menetelmän muunnos on sointujen ja tangenttien menetelmä . Newtonin menetelmällä voidaan myös ratkaista optimointiongelmia , joissa moniulotteisen avaruuden tapauksessa on määritettävä ensimmäisen derivaatan tai gradientin nolla.

Menetelmän kuvaus

Perustelut

Yhtälön ratkaisemiseksi numeerisesti yksinkertaisella iteraatiomenetelmällä se on pelkistettävä vastaavaan yhtälöön: , missä on supistumiskuvaus . $f(x) = 0$ $x=\varphi(x)$ $\varphi$

Jotta menetelmän konvergenssi olisi paras seuraavan approksimoinnin pisteessä , ehdon on täytyttävä . Tämän yhtälön ratkaisua etsitään muodossa , jolloin: $x^{*}$ $\varphi '(x^{*})=0$ $\varphi (x)=x+\alpha (x)f(x)$

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

Olettaen, että approksimaatiopiste on "riittävän lähellä" juuria ja annettu funktio on jatkuva , lopullinen kaava on: ${\tilde {x}}$ ${\näyttötyyli (f(x^{*})\approx f({\tilde {x)))=0)}$ $\alpha(x)$

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

Tätä silmällä pitäen funktio määritellään: $\varphi(x)$

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

Tietyissä olosuhteissa tämä toiminto suorittaa supistuksen kartoituksen juuren läheisyydessä.

Todiste

Olkoon annettu reaalimuuttujan funktio , joka on kahdesti jatkuvasti differentioituva määritelmäalueellaan ja jonka derivaatta ei koskaan katoa:

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

Ja on tarpeen todistaa, että funktio suorittaa supistumiskartoituksen lähellä yhtälön juurta . $\scriptstyle {\varphi (x)=x-{\frac {f(x)}{f'(x)))}$ $\scriptstyle {f(x)=0}$

Johtuen funktion jatkuvasta differentiatiivisuudesta ja nollan epäyhtälöstä, sen ensimmäinen derivaatta on jatkuva . $\scriptstyle {f(x)}$ $\scriptstyle {\varphi (x)}$

Johdannainen on: $\scriptstyle {\varphi '(x)}$

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

Se on myös jatkuvaa :lle asetettujen ehtojen mukaisesti . Olkoon yhtälön haluttu juuri: , siis sen läheisyydessä : $\scriptstyle {f(x)}$ $\scriptstyle {{\tilde {x}}}$ $\scriptstyle {f({\tilde {x)))=0}$ $\scriptstyle {\varphi '(x)\noin 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 .}

Sitten Lagrangen lauseen mukaan :

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

Johtuen siitä, että samassa delta-alueella, seuraava pitää paikkansa: $\scriptstyle {\varphi ({\tilde {x)))={\tilde {x}}}$

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

Näin saatu funktio juuren naapurissa toteuttaa supistumismappauksen . ■ $\scriptstyle {\varphi (x)}$ $\scriptstyle {U_{\delta }({\tilde {x)))}$

Tässä tapauksessa yhtälön numeerisen ratkaisun löytämisalgoritmi pelkistetään iteratiiviseksi laskentamenettelyksi : $f(x) = 0$

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

Banachin lauseen mukaan approksimaatioiden sarja pyrkii yhtälön juureen . $f(x) = 0$

Geometrinen tulkinta

Menetelmän pääidea on seuraava: alkuperäinen approksimaatio asetetaan hypoteettisen juuren lähelle, minkä jälkeen piirretään tarkasteltavan funktion kaavion tangentti approksimaatiopisteeseen, jonka leikkaus abskissa-akselin kanssa on löytyi. Tämä piste on otettu seuraavaksi approksimaatioksi. Ja niin edelleen, kunnes vaadittu tarkkuus on saavutettu.

Olkoon 1) reaaliarvoinen funktio jatkuvasti differentioituva välillä ; 2) on pakollinen kohta : ; 3) on myös sellaisia, että for ja for ; 4) kohta on sellainen, että . Sitten kaava iteratiiviselle approksimaatiolle k :lle voidaan johtaa tangentin geometrisestä merkityksestä seuraavasti: $f(x)\colon (a,\,b)\to \mathbb {R}$ ${\näyttötyyli (a,\,b)}$
$x^{*}\in (a,\,b)$ $f(x^{*})=0$
$C > 0$ $\delta>0$
$\vert f'(x)\vert \geqslant C$ $x\in (a,\,x^{*}-\delta ]\kuppi [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}}},

missä on kaavion tangenttiviivan kaltevuus pisteessä . $\alpha _{n}$ ${\displaystyle y(x)=f(x_{n})+(x-x_{n})\cdot \mathrm {tg} \,\alpha _{n))$ $f$ $(x_{n};f(x_{n}))$

Siksi (oletetaan tangenttiviivan yhtälössä ) halutulla lausekkeella on muoto: $y(x_{n+1})=0$ $x_{{n+1}}$

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

Jos , tätä arvoa voidaan käyttää seuraavana likiarvona . $x_{n+1}\in (a,\,b)$ $x^{{*}}$

Jos , niin siellä on "lento" (juuri on lähellä rajaa ). Tässä tapauksessa on välttämätöntä (käyttäen puolitusmenetelmän ideaa ) korvata pisteellä, kunnes piste "palaa" hakualueelle . $x_{n+1}\notin (a,\,b)$ $x^{{*}}$ ${\näyttötyyli (a,\,b)}$ $x_{{n+1}}$ ${\frac {x_{n}+x_{n+1}}{2}}$ ${\näyttötyyli (a,\,b)}$

Huomautukset. 1) Jatkuvan derivaatan läsnäolo mahdollistaa jatkuvasti muuttuvan tangentin rakentamisen koko ratkaisun etsintäalueelle . 2) Tapauksia, joissa halutun ratkaisun raja (pisteessä tai pisteessä ) on, tarkastellaan samalla tavalla. 3) Geometrialta katsottuna yhtäläisyys tarkoittaa, että kaavion tangentti pisteessä - on yhdensuuntainen akselin kanssa eikä leikkaa sen kanssa lopussa. 4) Mitä suurempi vakio ja pienempi vakio ehtojen kappaleesta 3, sitä lähempänä kaavion tangentin ja pisteen akselin leikkauspiste on, eli sitä lähempänä arvo on haluttua . ${\näyttötyyli (a,\,b)\;}$
$a$ $b$ $x^{{*}}$
$f'(x_{n})=0$ $f$ $(x_{n};f(x_{n}))$ $HÄRKÄ$ $f(x_{n})\neq 0$
$C > 0$ $\delta>0$ $x_{n}\in (a,\,x^{*}-\delta ]\cup [x^{*}+\delta ,\,b)$ $f$ $HÄRKÄ$ $(x^{*};\;0)$ $x_{{n+1}}$ $x^{*}\in (a,\,b)$

Iteratiivinen prosessi alkaa jollain aloituslikiarvolla ja halutun pisteen välissä ei saa olla muita funktion nollia, eli "mitä lähempänä haluttua juuria , sen parempi." Jos etsinnässä ei ole oletuksia , yritys ja erehdys voi kaventaa mahdollisten arvojen aluetta soveltamalla väliarvolausetta . $x_{0}\in (a,\,b)$ $x_{0}\in (a,\,b)$ $x^{*}\in (a,\,b)$ $f$ $x_{0}$ $x^{{*}}$ $x^{{*}}$

Ennalta määritetyille , iteratiivinen prosessi päättyy , jos ja . Erityisesti näyttömatriisille ja voidaan laskea kaavion näyttöasteikon perusteella, eli jos ja putoavat yhteen pystysuoraan ja yhteen vaakariviin. $\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})$

Algoritmi

Alkuperäinen likiarvo on asetettu . $x_{0}$
Kunnes pysäytysehto täyttyy, joka voidaan katsoa tai (eli virhe on vaadituissa rajoissa), lasketaan uusi approksimaatio: . $|x_{n+1}-x_{n}|<\varepsilon$ $|f(x_{n+1})|<\varepsilon$ $x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n))}}$

Esimerkki

Harkitse positiivisen löytämisen ongelmaa , jolle . Tämä tehtävä voidaan esittää tehtävänä löytää funktion nollakohta . Meillä on lauseke johdannaiselle . Koska kaikille ja for , on selvää , että ratkaisu on välillä 0 ja 1. Otetaan arvo alkuperäiseksi approksimaatioksi , niin: $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})))&=&\alleviivaus 0 {,}}909\;672\;693\;736,\\x_{3}&=&x_{2}-{\dfrac {f(x_{2})}{f'(x_{2})} }&=&\alleviivaus {0{,}86}7\;263\;818\;209,\\x_{4}&=&x_{3}-{\dfrac {f(x_{3})}{ f'(x_{3})}}&=&\alleviivaus {0{,}865\;47}7\;135\;298,\\x_{5}&=&x_{4}-{\dfrac { f(x_{4})}{f'(x_{4})}}&=&\alleviivaus {0{,}865\;474\;033\;1}11,\\x_{6}&= &x_{5}-{\dfrac {f(x_{5})}{f'(x_{5})}}&=&\alleviivaus {0{,}865\;474\;033\;102}. \end{matrix}}

Kelvolliset merkitsevät numerot on alleviivattu . Voidaan nähdä, että niiden lukumäärä kasvaa askeleelta askeleelta (noin kaksinkertaistuu jokaisessa vaiheessa): 1 - 2, 2 - 5, 5 - 10, mikä kuvaa neliöllistä lähentymisnopeutta .

Käyttöehdot

Tarkastellaanpa useita esimerkkejä, jotka osoittavat menetelmän puutteita.

Vastaesimerkkejä

Jos alkuperäinen approksimaatio ei ole tarpeeksi lähellä ratkaisua, menetelmä ei välttämättä konvergoi.

Päästää

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

Sitten

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

Otetaan nolla alkuperäiseksi approksimaatioksi. Ensimmäinen iteraatio antaa yksikön likimääräisenä. Toinen puolestaan antaa jälleen nollan. Menetelmä kiertää, eikä ratkaisua löydy. Yleisesti ottaen approksimaatiosarjan rakentaminen voi olla hyvin hämmentävää .

Jos derivaatta ei ole jatkuva juuripisteessä, menetelmä voi poiketa missä tahansa juuren ympäristössä .

Harkitse toimintoa:

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

Silloin ja kaikkialla paitsi 0. $f'(0)=1$ $f'(x)=1+2x\sin(2/x)-2\cos(2/x)$

Juuren läheisyydessä derivaatta vaihtaa merkkiä lähestyessään nollaa oikealta tai vasemmalta. Vaikka . _ $x$ $f(x)\geqslant xx^{2}>0$ $0<x<1$

Siten se ei ole rajattu lähellä juurta, ja menetelmä hajoaa, vaikka funktio on kaikkialla differentioituva, sen derivaatta on ei-nolla juuressa, äärettömästi differentioituva kaikkialla paitsi juuresta ja sen derivaatta on rajattu juuren ympärille. . $f(x)/f'(x)$ $f$

Jos juuripisteessä ei ole toista derivaattia , menetelmän konvergenssinopeutta voidaan vähentää huomattavasti.

Harkitse esimerkkiä:

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

Sitten ja paitsi silloin, kun sitä ei ole määritelty. ${\displaystyle f'(x)=1+(4/3)x^{1/3))$ ${\displaystyle f''(x)=(4/9)x^{-2/3))$ $x=0$

Seuraavassa vaiheessa meillä on : $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})}}.

Tuloksena olevan sekvenssin konvergenssinopeus on noin 4/3. Tämä on huomattavasti pienempi kuin 2, mikä on välttämätöntä neliöllisen konvergenssin kannalta, joten tässä tapauksessa voidaan puhua vain lineaarisesta konvergenssista, vaikka funktio on jatkuvasti differentioituva kaikkialla , derivaatta juuressa ei ole nolla ja on äärettömästi differentioituva kaikkialla paitsi juurella. $f$

Jos derivaatta juuripisteessä on nolla, konvergenssin nopeus ei ole neliöllinen, ja itse menetelmä voi lopettaa haun ennenaikaisesti ja antaa annetulla tarkkuudella väärän likiarvon.

Päästää

f(x)=x^{2}.

Silloin ja sieltä . Siten menetelmän konvergenssi ei ole neliöllinen, vaan lineaarinen, vaikka funktio on äärettömästi differentioituva kaikkialla. $f'(x)=2x$ $xf(x)/f'(x)=x/2$

Rajoitukset

Olkoon yhtälö , missä ja sen ratkaisu on löydettävä. $f(x) = 0$ $f(x)\colon \mathbb {X} \to \mathbb {R}$

Alla on päälauseen muotoilu, jonka avulla voimme antaa selkeät sovellettavuuden ehdot. Se kantaa Neuvostoliiton matemaatikon ja taloustieteilijän Leonid Vitalievich Kantorovich ( 1912-1986 ) nimeä .

Kantorovichin lause.

Jos on vakioita , kuten: $A,\;B,\;C$

${\frac {1}{|f'(x)|}}<A$ on , eli se on olemassa eikä ole yhtä suuri kuin nolla; $[a,\;b]$ $f'(x)$
$\left|{\frac {f(x)}{f'(x)}}\right|<B$ on , eli rajoitettu; $[a,\;b]$ $f(x)$
${\näyttötyyli \exists f''(x)}$ päällä ja ; $[a,\;b]$ $|f''(x)|\leqslant C\leqslant {\frac {1}{2AB))$

Lisäksi tarkasteltavan segmentin pituus . Sitten seuraavat väitteet pitävät paikkansa: $|ab|<{\frac {1}{AB}}\left(1-{\sqrt {1-2ABC}}\right)$

yhtälöllä on juuri ; $[a,\;b]$ $x^{*}$ $f(x)=0\colon \exists x^{*}\in [a,\;b]\colon f(x^{*})=0$
jos , niin iteratiivinen sekvenssi konvergoi tähän juureen: ; $x_{0}={\frac {a+b}{2))$ $\left\{x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})))\right\}\to x^ {*}$
virhe voidaan arvioida kaavalla . $|x^{*}-x_{n}|\leqslant {\frac {B}{2^{n-1}}}(2ABC)^{2^{n-1}}$

Erityisesti lauseen viimeisestä lauseesta menetelmän neliöllinen konvergenssi seuraa:

|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}}\oikea)^{2}=\alpha | x^{*}-x_{n-1}|^{2}.

Sitten alkuperäisen funktion rajoitukset näyttävät tältä: $f(x)$

toimintoa on rajoitettava;
funktion on oltava tasainen , kahdesti differentioituva ;
sen ensimmäinen derivaatta erotetaan tasaisesti nollasta; $f'(x)$
sen toisen derivaatan on oltava tasaisesti rajattu. $f''(x)$

Historiallinen tausta

Isaac Newton kuvasi menetelmän Barrowille vuonna 1669 osoittamassaan käsikirjoituksessa On the Analysis by Equations of Infinite Series ( latinaksi De analysi per aequationes numero terminorum infinitas ) ja teoksessa The Method of Fluxions and Infinite Series ( latinaksi: De metodis fluxionum ) et serierum infinitarum" ) tai " Analyyttinen geometria " ( lat. "Geometria analytica" ) Newtonin teosten kokoelmissa, joka kirjoitettiin vuonna 1671 . Kirjoituksissaan Newton esittelee käsitteitä, kuten funktion laajentaminen sarjaksi , infinitesimaalit ja fluxions ( johdannaiset nykyisessä merkityksessä). Nämä teokset julkaistiin paljon myöhemmin: ensimmäinen julkaistiin vuonna 1711 William Johnsonin ansiosta, toisen julkaisi John Colzon vuonna 1736 luojan kuoleman jälkeen. Menetelmän kuvaus poikkesi kuitenkin merkittävästi hänen nykyisestä esityksestään: Newton sovelsi menetelmäään yksinomaan polynomeihin . Hän ei laskenut peräkkäisiä approksimaatioita , vaan polynomien sarjaa ja sai tuloksena likimääräisen ratkaisun . $x_{n}$ $x$

Menetelmä julkaistiin ensimmäisen kerran John Wallisin tutkielmassa "Algebra" vuonna 1685, jonka pyynnöstä Newton itse kuvaili sitä lyhyesti. Vuonna 1690 Joseph Raphson julkaisi yksinkertaistetun kuvauksen kirjassaan "Analysis aequationum universalis" ( latinaksi: "Analysis aequationum universalis" ). Raphson piti Newtonin menetelmää puhtaasti algebrallisena ja rajoitti sen soveltamisen polynomeihin, mutta hän kuvaili menetelmää peräkkäisillä approksimaatioilla eikä Newtonin käyttämän vaikeammin ymmärrettävän polynomisarjan avulla. Lopuksi, vuonna 1740 Thomas Simpson kuvasi Newtonin menetelmän ensimmäisen kertaluvun iteratiiviseksi menetelmäksi epälineaaristen yhtälöiden ratkaisemiseksi derivaatta käyttäen, kuten tässä esitetään. Samassa julkaisussa Simpson yleisti menetelmän kahden yhtälöjärjestelmän tapaukseen ja totesi, että Newtonin menetelmää voidaan soveltaa myös optimointiongelmiin etsimällä derivaatan tai gradientin nolla . $x_{n}$

Vuonna 1879 Arthur Cayley Newton - Fourierin imaginaarisessa ongelmassa huomautti ensimmäisenä vaikeudet yleistää Newtonin menetelmää tapaukseen , jossa polynomien imaginaariset juuret ovat korkeampia kuin toinen ja monimutkaiset alkuperäiset approksimaatiot. Tämä työ tasoitti tietä fraktaaliteorian tutkimukselle .

Yleistykset ja muutokset

Sekanttimenetelmä

Asiaan liittyvä sekanttimenetelmä on Newtonin "likimääräinen" menetelmä ja välttää derivaatan laskemisen . Johdannan arvo iteratiivisessa kaavassa korvataan sen estimaatilla kahdelle edelliselle iteraatiopisteelle:

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

Siten pääkaavalla on muoto

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

Tämä menetelmä on samanlainen kuin Newtonin menetelmä, mutta sen konvergenssinopeus on hieman hitaampi. Menetelmän konvergenssijärjestys on yhtä suuri kuin kultainen suhde - 1,618 ...

Huomautukset. 1) Iteratiivisen prosessin aloittamiseksi tarvitaan kaksi eri arvoa ja . 2) Toisin kuin "todellisessa Newton-menetelmässä" (tangenttimenetelmä), joka vaatii vain tallentamisen (ja tilapäisesti laskelmien aikana ja ), sekanttimenetelmä vaatii tallentamisen , , , . 3) Sitä käytetään, jos laskenta on vaikeaa (esimerkiksi se vaatii paljon koneresursseja: aikaa ja/tai muistia). $x_{0}$ $x_{1}$
${\näyttötyyli x_{n))$ $f(x_{n})$ $f'(x_{n})$ ${\näyttötyyli x_{n-1))$ ${\näyttötyyli x_{n))$ $f(x_{n-1})$ $f(x_{n})$
$f'(x)$

Yksi tangenttimenetelmä

Kutsujen määrän vähentämiseksi funktion derivaatan arvoihin käytetään niin sanottua yhden tangentin menetelmää.

Tämän menetelmän iteraatiokaava on:

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

Menetelmän ydin on laskea derivaatta vain kerran, alkuperäisessä approksimaatiopisteessä ja käyttää sitten tätä arvoa jokaisessa seuraavassa iteraatiossa: $x_{0}$

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

Tällä valinnalla seuraava yhtäläisyys pätee pisteessä : $\alpha _{0}$ $x_{0}$

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

ja jos segmentti, jossa oletetaan juuren olemassaoloa ja valitaan alkuperäinen approksimaatio , on riittävän pieni ja derivaatta on jatkuva, niin arvo ei poikkea paljoakaan ja siksi kuvaaja kulkee melkein vaakasuoraan leikkaaen suora viiva , joka puolestaan varmistaa approksimaatiopisteiden sarjan nopean lähentymisen juureen. $x^{*}$ $x_{0}$ $\varphi '(x)$ $\varphi '(x^{*})$ $\varphi '(x_{0})=0$ $y=\varphi (x)$ $y=x$

Tämä menetelmä on yksinkertaisen iterointimenetelmän erikoistapaus . Sillä on lineaarinen konvergenssijärjestys.

Moniulotteinen tapaus

Yleistetään saatu tulos moniulotteiseksi tapaukseksi.

On tarpeen löytää ratkaisu järjestelmään:

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

Kun valitaan jokin alkuarvo , peräkkäiset approksimaatiot löydetään ratkaisemalla yhtälöjärjestelmiä : ${\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,

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

Sovelletaan optimointiongelmiin

Olkoon tarpeen löytää usean muuttujan funktion minimi . Tämä tehtävä vastaa gradientin nollakohdan löytämisen ongelmaa . Sovelletaan yllä olevaa Newtonin menetelmää: $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,

missä on funktion Hessiankielinen . $H({\vec {x)))$ $f({\vec {x)))$

Kätevämmässä iteratiivisessa muodossa tämä lauseke näyttää tältä:

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

On huomattava, että neliöfunktion tapauksessa Newtonin menetelmä löytää ääripään yhdessä iteraatiossa.

Hessenin matriisin löytäminen on laskennallisesti kallista eikä useinkaan mahdollista. Tällaisissa tapauksissa vaihtoehtona voivat toimia kvasi-newtonilaiset menetelmät , joissa Hessenin matriisin approksimaatio rakennetaan funktion kaarevuuden tiedon keräämiseen.

Newton-Raphsonin menetelmä

Newton-Raphsonin menetelmä on parannus edellä kuvattuun Newtonin ääripäämenetelmään. Suurin ero on, että seuraavassa iteraatiossa yksi yksiulotteisen optimoinnin menetelmistä valitsee optimaalisen vaiheen:

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

jossa Laskelmien optimoimiseksi käytetään seuraavaa parannusta: sen sijaan, että laskemme uudelleen tavoitefunktion Hessenin jokaisessa iteraatiossa , rajoitamme alkuperäiseen approksimaatioon ja päivitämme sen vain kerran vaiheittain tai emme päivitä sitä ollenkaan. $\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$

Sovelletaan pienimmän neliösumman tehtävissä

Käytännössä on usein tehtäviä, joissa joudutaan säätämään kohteen vapaita parametreja tai sovittamaan matemaattinen malli todelliseen dataan. Näissä tapauksissa esiintyy pienimmän neliösumman ongelmia :

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

Näille ongelmille on ominaista erityinen gradientti ja Hessenin matriisi :

\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}}) ,

missä on vektorifunktion Jacobi-matriisi , on sen komponentin Hessen-matriisi . $J({\vec {x)))$ ${\vec {f))({\vec {x)))$ $H_{i}({\vec {x)))$ $f_{i}({\vec {x)))$

Sitten seuraava vaihe määritetään järjestelmästä: ${\vec {p}}$

\left[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-Newtonin menetelmä

Gauss-Newtonin menetelmä perustuu oletukseen, että termi hallitsee . Tämä vaatimus ei täyty, jos minimijäännökset ovat suuria, eli jos normi on verrattavissa matriisin maksimiominaisarvoon . Muuten voit kirjoittaa: $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}}).

Siten, kun normi on lähellä nollaa ja matriisilla on täysi sarakejärjestys , askel poikkeaa vain vähän newtonilaisesta (ottaen huomioon ), ja menetelmällä voidaan saavuttaa neliöllinen konvergenssinopeus, vaikka toisia derivaattoja ei oteta huomioon. tili. Menetelmän parannus on heuristisiin näkökohtiin perustuva Levenberg-Marquardt-algoritmi . $\|Q({\vec {x)))\|$ $J({\vec {x)))$ ${\vec {p}}$ $Q({\vec {x)))$

Yleistys kompleksitasoon

Tähän asti menetelmän kuvauksessa on käytetty funktioita, jotka suorittavat kartoituksia todellisten arvojen joukossa . Menetelmää voidaan kuitenkin soveltaa myös kompleksisen muuttujan funktion nollakohdan löytämiseen . Menettelytapa pysyy kuitenkin samana:

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

Erityisen kiinnostavaa on alkuperäisen approksimation valinta . Ottaen huomioon, että funktiossa voi olla useita nollia, menetelmä voi eri tapauksissa konvergoida eri arvoihin, ja on aivan luonnollista haluta selvittää, mitkä alueet varmistavat konvergenssin tiettyyn juuriin. Tämä kysymys kiinnosti Arthur Cayleyä jo vuonna 1879 , mutta se oli mahdollista ratkaista vasta 1900-luvun 70 - luvulla tietokonetekniikan myötä. Kävi ilmi, että näiden alueiden risteyskohdissa (niitä kutsutaan yleensä vetovoimaalueiksi ) muodostuu niin sanottuja fraktaaleja - äärettömiä itsekaltaisia geometrisia kuvioita. $z_{0}$

Koska Newton sovelsi menetelmäään yksinomaan polynomeihin , tällaisen sovelluksen tuloksena muodostuneet fraktaalit tunnettiin Newtonin fraktaaleina tai Newtonin pooleina .

Toteutus

scala

objekti NewtonMethod { val tarkkuus = 1e-6 @tailrec def -metodi ( x0 : Double , f : Double => Double , dfdx : Double => Double , e : Double ): Double = { val x1 = x0 - f ( x0 ) / dfdx ( x0 ) if ( abs ( x1 ) - x0 ) < e ) x1 else - metodi ( x1 , f , dfdx , e ) } def g ( C : Double ) = ( x : Double ) => x * x - C def dgdx ( x : Double ) = 2 * x def sqrt ( x : Double ) = x match { case 0 => 0 case x if ( x < 0 ) => Double . NaN tapaus x if ( x > 0 ) => menetelmä ( x / 2 , g ( x ), dgdx , tarkkuus ) } }

Python

matematiikasta tuonti sin , cos kirjoittamasta tuonti Soitava tuonti unittest _ _ def newton ( f : Kutsuttava [[ float ], float ], f_prime : Kutsuttava [[ float ], float ], x0 : float , eps : float = 1e-7 , kmax : int = 1e3 ) -> float : """ ratkaisee f(x) = 0 Newtonin menetelmällä tarkkuudella eps :param f: f :param f_prime: f' :param x0: aloituspiste :param eps: haluttu tarkkuus :return: f(x) = 0:n juuri """ x , x_edellinen , i = x0 , x0 + 2 * eps , 0 kun taas abs ( x - x_edellinen ) >= eps ja i < kmax : x , x_edellinen , i = x - f ( x ) / f_alkuluku ( x ), x , i + 1 palauta x luokka TestNewton ( yksikkötesti . TestCase ): def testi_0 ( itse ): def f ( x : float ) -> float : paluu x ** 2 - 20 * sin ( x ) def f_prime ( x : float ) -> float : return 2 * x - 20 * cos ( x ) x0 , x_tähti = 2 , 2,7529466338187049383 itse . assertAlmostEqual ( newton ( f , f_prime , x0 ), x_star ) if __name__ == '__main__' : yksikkötesti . tärkein ()

PHP

<?php // PHP 5.4 function newtons_method ( $a = - 1 , $b = 1 , $f = function ( $x ) { paluupow ( $ x , 4 ) - 1 ; }, $johdannainen_f = funktio ( $x ) { paluu 4 * pow ( $x , 3 ); }, $eps = 1E-3 ) { $xa = $a ; $xb = $b ; $iteraatio = 0 ; while ( abs ( $xb ) > $eps ) { $p1 = $f ( $xa ); $q1 = $johdannainen_f ( $xa ); $xa - = $p1 / $q1 ; $xb = $p1 ; ++ $iteraatio ; } palauttaa $xa ; }

Oktaavi

funktio res = nt () eps = 1e-7 ; x0_1 = [ -0,5 , 0,5 ] ; max_iter = 500 ; xopt = uusi (@ resh , eps , max_iter ); xopt-päätefunktio a = uusi ( 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 ; loppu i a = x ; päätefunktiofunktio [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 * × - 2 ; q = -100 * x .^ 3 + 48 * x . ^ 2 - 72 * x + 22 ; lopputoiminto

Delphi

// laskettu funktiofunktio fx ( x : Double ) : Double ; alkaa Tulos := x * x - 17 ; loppu ; // f(x)-funktion johdettu funktio dfx ( x : Double ) : Double ; aloita Tulos := 2 * x ; loppu ; funktio ratkaista ( fx , dfx : TFunc < Double , Double >; x0 : Double ) : Double ; const eps = 0,000001 ; var x1 : Double ; alkaa x1 := x0 - fx ( x0 ) / dfx ( x0 ) ; // ensimmäinen approksimaatio while ( Abs ( x1 - x0 ) > eps ) alkaa // kunnes saavutetaan tarkkuus 0.000001 x0 : = x1 ; x1 := x1 - fx ( x1 ) / dfx ( x1 ) ; // myöhemmät approksimaatiot loppuvat ; Tulos := x1 ; loppu ; // Kutsu ratkaista ( fx , dfx , 4 ) ;

C++

#include <iostream> #include <math.h> double fx ( double x ) { return x * x - 17 ;} // laskettu funktio double dfx ( double x ) { return 2 * x ;} // funktion derivaatta typedef double ( * funktio )( double x ); // tyyppifunktion määrittäminen double solve ( function fx , function dfx , double x0 , double eps = 1e-8 ) { kaksinkertainen xi = x0 ; //Nykyinen piste i. iteraatiossa while ( fabs ( fx ( xi )) >= eps ) // kunnes saavutetaan tarkkuus 0,00000001 xi = xi - fx ( xi ) / dfx ( xi ); // myöhemmät approksimaatiot return xi ; } int main () { std :: cout << ratkaista ( fx , dfx , 4 ) << std :: endl ; paluu 0 ; }

C

typedef double ( * funktio )( double x ); double TangentsMethod ( function f , function df , double xn , double eps ) { kaksinkertainen x1 = xn - f ( xn ) / df ( xn ); kaksinkertainen x0 = xn ; while ( abs ( x0 - x1 ) > eps ) { x0 = x1 ; x1 = x1 - f ( x1 ) / df ( x1 ); } paluu x1 ; } //Valitse alkuperäinen arvaus xn = OmaFunktio ( A ) * Oma2Johdannainen ( A ) > 0 ? B : A ; double MyFunction ( double x ) { return ( pow ( x , 5 ) - x - 0.2 ); } //Funktioni double MyDivative ( double x ) { return ( 5 * pow ( x , 4 ) - 1 ); } //Ensimmäinen derivaatta double My2Divatiivi ( double x ) { return ( 20 * pow ( x , 3 )); } //Toinen derivaatta //Esimerkki funktion kutsumisesta double x = TangentsMethod ( MyFunction , MyDivative , xn , 0.1 )

Haskell

tuonti Data.List ( iterate ' ) main :: IO () main = tulosta $ ratkaista ( \ x -> x * x - 17 ) ( * 2 ) 4 -- Ratkaisutoiminto on universaali kaikille todellisille tyypeille, joiden arvoja voidaan verrata. ratkaise = ratkaise 0,000001 esolve epsilon func deriv x0 = fst . head $ dropWhile pred parit missä pred ( xn , xn1 ) = ( abs $ xn - xn1 ) > epsilon -- Pred-funktio määrittää, onko vaadittu tarkkuus saavutettu. seuraava xn = xn - funktio xn / deriv xn -- Seuraava funktio laskee uuden approksimaation. iters = iterate ' next x0 -- Loputon iteraatioiden luettelo. parit = zip iters ( tail iters ) -- Loputon luettelo iteraatiopareista muodossa: [(x0, x1), (x1, x2) ..].

Kirjallisuus

Akulich I. L. Matemaattinen ohjelmointi esimerkeissä ja tehtävissä: Proc. opiskelijatalouden tuki. asiantuntija. yliopistot. - M . : Higher School, 1986. - 319 s. : sairas. - BBK 22.1 A44 . - UDC 517,8 .
Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Laskennalliset menetelmät insinööreille: Proc. korvaus. - M . : Korkeakoulu, 1994. - 544 s. : sairas. - BBK 32,97 A62 . - UDC 683.1 . — ISBN 5-06-000625-5 .
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Numeeriset menetelmät. - 8. painos - M . : Perustiedon laboratorio, 2000.
Vavilov S. I. Isaac Newton . - M .: Toim. Neuvostoliiton tiedeakatemia, 1945.
Volkov E. A. Numeeriset menetelmät. - M .: Fizmatlit, 2003.
Gill F., Murray W., Wright M. Käytännön optimointi. Per. englannista. - M .: Mir, 1985.
Korn G., Korn T. Matematiikan käsikirja tutkijoille ja insinööreille. - M .: Nauka, 1970. - S. 575-576.
Korshunov Yu. M., Korshunov Yu. M. Kybernetiikan matemaattiset perusteet. - Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmit epälineaarisen ohjelmoinnin ongelmien ratkaisemiseen. - M .: MEPhI, 1982.
Morozov AD Johdatus fraktaalien teoriaan. - MEPhI, 2002.

Katso myös

Linkit

"Newtonin altaat" osoitteessa fractalworld.xaoc.ru
"Isaac Newton" osoitteessa www.scottish-wetlands.org
"Kantorovitšin matemaattiset teokset" SB RAS:n matematiikan instituutin verkkosivuilla
Hazewinkel, Michiel, toim. (2001), Newtonin menetelmä , Encyclopedia of Mathematics , Springer , ISBN 978-1-55608-010-4
Weisstein, Eric W. Newton's Method (englanniksi) Wolfram MathWorld -verkkosivustolla .
Newtonin menetelmä, Citizendium.
Mathews, J., The Accelerated and Modified Newton Methods, Kurssin muistiinpanot.
Wu, X., Roots of Equations, Course Notes.

Optimointimenetelmät _
Yksiulotteinen	kultaisen leikkauksen menetelmä Dikotomia Paraabeli menetelmä Verkkohaku Yhtenäinen lohkohakumenetelmä Fibonaccin menetelmä Kolminkertainen haku Piyavsky menetelmä Vahva menetelmä
Nolla järjestys	Gaussin menetelmä Nelder-Meadin menetelmä Hook-Jeeves -menetelmä Rosenbrockin menetelmä Powellin menetelmä
Ensimmäinen tilaus	gradienttilasku Zeutendijkin menetelmä Koordinaattilasku Konjugaattigradienttimenetelmä Kvasi-Newtonilaiset menetelmät Levenberg-Marquardt-algoritmi
toinen tilaus	Newtonin menetelmä Newton-Raphsonin menetelmä Broyden-Fletcher-Goldfarb-Shanno-algoritmi (BFGS)
Stokastinen	Monte Carlon menetelmä Simuloitu hehkutus Evoluutioalgoritmit differentiaalinen evoluutio Ant algoritmi Hiukkasparvimenetelmä Mehiläisyhdyskunnan algoritmi Satunnainen kävelymenetelmä
Lineaariset ohjelmointimenetelmät _	Yksinkertainen menetelmä Gomorin algoritmi Ellipsoidi menetelmä Potentiaalinen menetelmä
Epälineaariset ohjelmointimenetelmät	Jaksottainen neliöllinen ohjelmointi