Newtonova metoda

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 25. ledna 2022; kontroly vyžadují 3 úpravy .

Newtonova metoda, Newtonův algoritmus ( také známý jako metoda tečny ) je iterativní numerická metoda pro nalezení kořene ( nuly ) dané funkce . Tuto metodu poprvé navrhl anglický fyzik , matematik a astronom Isaac Newton ( 1643-1727 ) . Hledání řešení se provádí konstrukcí postupných aproximací a je založeno na principech jednoduché iterace . Metoda má kvadratickou konvergenci . Modifikací metody je metoda tětiv a tečen . Newtonovu metodu lze také použít k řešení optimalizačních problémů , ve kterých je potřeba určit nulu první derivace nebo gradientu v případě vícerozměrného prostoru.

Popis metody

Odůvodnění

Abychom rovnici numericky vyřešili metodou jednoduché iterace , musíme ji zredukovat na ekvivalentní rovnici: , kde je mapování kontrakce . $f(x)=0$ $x=\varphi(x)$ $\varphi$

Pro nejlepší konvergenci metody v bodě další aproximace musí být splněna podmínka . Řešení této rovnice se hledá ve tvaru , pak: $x^{*}$ $\varphi '(x^{*})=0$ $\varphi (x)=x+\alpha (x)f(x)$

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

Za předpokladu, že bod aproximace je „dostatečně blízko“ kořenu a že daná funkce je spojitá , konečný vzorec pro je: ${\tilda {x}}$ $(f(x^{*})\approx f({\tilde {x)))=0)$ $\alpha(x)$

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

S ohledem na to je funkce definována: $\varphi(x)$

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

Za určitých podmínek tato funkce provádí mapování kontrakce v okolí kořene.

Důkaz

Nechť je dána funkce reálné proměnné , která je ve svém oboru definice dvakrát spojitě diferencovatelná a jejíž derivace nikdy nezmizí:

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

A je nutné dokázat, že funkce provádí kontrakční zobrazení blízko kořene rovnice . $\scriptstyle {\varphi (x)=x-{\frac {f(x)}{f'(x)))}$ $\scriptstyle {f(x)=0}$

Kvůli spojité diferencovatelnosti funkce a nerovnosti nuly je její první derivace spojitá . $\scriptstyle {f(x)}$ $\scriptstyle {\varphi (x)}$

Derivát je: $\scriptstyle {\varphi '(x)}$

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

Za podmínek uložených na , je také nepřetržitý. Nechť je požadovaný kořen rovnice: , tedy v jejím okolí : $\scriptstyle {f(x)}$ $\scriptstyle {{\tilde {x}}}$ $\scriptstyle {f({\tilde {x)))=0}$ $\scriptstyle {\varphi '(x)\cca 0}$

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

Pak podle Lagrangeovy věty :

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

Vzhledem k tomu, že ve stejném sousedství delty platí následující: $\scriptstyle {\varphi ({\tilde {x)))={\tilde {x}}}$

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

Takto získaná funkce v okolí kořene implementuje mapování kontrakce . ■ $\scriptstyle {\varphi (x)}$ $\scriptstyle {U_{\delta }({\tilde {x)))}$

V tomto případě je algoritmus pro nalezení numerického řešení rovnice redukován na postup iterativního výpočtu : $f(x)=0$

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

Podle Banachovy věty má posloupnost aproximací sklon ke kořeni rovnice . $f(x)=0$

Geometrická interpretace

Hlavní myšlenka metody je následující: počáteční aproximace je nastavena blízko hypotetického kořene, poté je v aproximačním bodě vykreslena tečna ke grafu studované funkce, pro kterou je průsečík s osou úsečky nalezeno. Tento bod je brán jako další aproximace. A tak dále, dokud není dosaženo požadované přesnosti.

Nechť 1) reálná funkce je spojitě derivovatelná na intervalu ; 2) existuje požadovaný bod : ; 3) existují i takové, že pro a pro ; 4) pointa je taková, že . Potom vzorec pro iterační aproximaci ke k lze odvodit z geometrického významu tečny takto: $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}}},

kde je úhel sklonu tečny ke grafu v bodě . $\alpha _{n}$ ${\displaystyle y(x)=f(x_{n})+(x-x_{n})\cdot \mathrm {tg} \,\alpha _{n))$ $F$ $(x_{n};f(x_{n}))$

Proto (v rovnici tečné přímky předpokládáme ) požadovaný výraz pro má tvar: $y(x_{n+1})=0$ $x_{{n+1}}$

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

Pokud , pak lze tuto hodnotu použít jako další aproximaci k . $x_{n+1}\in (a,\,b)$ $x^{{*}}$

Jestliže , pak existuje „úlet“ (kořen leží blízko hranice ). V tomto případě je nutné (pomocí myšlenky metody bisekce ) nahrazovat , dokud se bod „nevrátí“ do oblasti hledání . $x_{n+1}\notin (a,\,b)$ $x^{{*}}$ $(a,\,b)$ $x_{{n+1}}$ ${\frac {x_{n}+x_{n+1}}{2}}$ $(a,\,b)$

Poznámky. 1) Přítomnost spojité derivace umožňuje vybudovat plynule se měnící tečnu na celé ploše hledání řešení . 2) Případy hraničního (v bodě nebo v bodě ) umístění požadovaného řešení jsou uvažovány obdobným způsobem. 3) Z geometrického hlediska rovnost znamená, že tečna ke grafu v bodě - je rovnoběžná s osou a na konci se s ní neprotíná. 4) Čím větší je konstanta a čím menší je konstanta z odstavce 3 podmínek, tím blíže je průsečík tečny ke grafu a osa k bodu , to znamená, že se hodnota blíží požadované hodnotě . $(a,\,b)\;$
$A$ $b$ $x^{{*}}$
$f'(x_{n})=0$ $F$ $(x_{n};f(x_{n}))$ $VŮL$ $f(x_{n})\neq 0$
$C > 0$ $\delta>0$ $x_{n}\in (a,\,x^{*}-\delta ]\cup [x^{*}+\delta ,\,b)$ $F$ $VŮL$ $(x^{*};\;0)$ $x_{{n+1}}$ $x^{*}\in (a,\,b)$

Iterační proces začíná nějakou počáteční aproximací a mezi požadovaným bodem by neměly být další nuly funkce , tedy "čím blíže k požadovanému kořeni , tím lépe." Pokud neexistují žádné předpoklady o nalezení , pokus a omyl mohou zúžit rozsah možných hodnot použitím teorému střední hodnoty . $x_{0}\in (a,\,b)$ $x_{0}\in (a,\,b)$ $x^{*}\in (a,\,b)$ $F$ $x_{0}$ $x^{{*}}$ $x^{{*}}$

U předdefinovaných se iterační proces ukončí , pokud a . Zejména pro zobrazovací matici a lze vypočítat na základě měřítka zobrazení grafu , to znamená, pokud a spadají do jedné vertikální a do jedné horizontální řady. $\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})$

Algoritmus

Je nastavena počáteční aproximace . $x_{0}$
Dokud není splněna podmínka zastavení, kterou lze brát jako nebo (to znamená, že chyba je v požadovaných mezích), vypočítá se nová aproximace: . $|x_{n+1}-x_{n}|<\varepsilon$ $|f(x_{n+1})|<\varepsilon$ $x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n))}}$

Příklad

Zvažte problém hledání pozitivních , pro které . Tato úloha může být reprezentována jako úloha najít nulu funkce . Máme výraz pro derivaci . Protože pro všechny a pro je zřejmé , že řešení leží mezi 0 a 1. Vezměme hodnotu jako počáteční aproximaci , pak: $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})))&=&\podtržítko {0 {,}}909\;672\;693\;736,\\x_{3}&=&x_{2}-{\dfrac {f(x_{2})}{f'(x_{2})} }&=&\podtržítko {0{,}86}7\;263\;818\;209,\\x_{4}&=&x_{3}-{\dfrac {f(x_{3})}{ f'(x_{3})}}&=&\podtržítko {0{,}865\;47}7\;135\;298,\\x_{5}&=&x_{4}-{\dfrac { f(x_{4})}{f'(x_{4})}}&=&\podtržítko {0{,}865\;474\;033\;1}11,\\x_{6}&= &x_{5}-{\dfrac {f(x_{5})}{f'(x_{5})}}&=&\podtržítko {0{,}865\;474\;033\;102}. \end{matrix}}

Platné platné číslice jsou podtržené . Je vidět, že jejich počet roste krok od kroku (přibližně se zdvojnásobuje s každým krokem): od 1 do 2, od 2 do 5, od 5 do 10, což ilustruje kvadratickou rychlost konvergence .

Podmínky použití

Podívejme se na několik příkladů poukazujících na nedostatky metody.

Protipříklady

Pokud počáteční aproximace není dostatečně blízko k řešení, pak metoda nemusí konvergovat.

Nechat

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

Pak

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

Vezměme nulu jako počáteční aproximaci. První iterace dá jednotku jako aproximaci. Druhý zase dá nulu. Metoda se zacyklí a nebude nalezeno žádné řešení. Obecně může být konstrukce posloupnosti aproximací velmi matoucí .

Pokud derivace není spojitá v bodě kořene, pak se metoda může rozcházet v libovolném okolí kořene.

Zvažte funkci:

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

Tehdy a všude kromě 0. $f'(0)=1$ $f'(x)=1+2x\sin(2/x)-2\cos(2/x)$

V blízkosti kořene derivace mění znaménko při přiblížení k nule zprava nebo zleva. Zatímco pro . $X$ $f(x)\geqslant xx^{2}>0$ $0<x<1$

Není tedy omezena blízko kořene a metoda bude divergovat, i když je funkce všude diferencovatelná, její derivace je nenulová v kořenu, nekonečně diferencovatelná všude kromě kořene a její derivace je ohraničena kolem kořene. . $f(x)/f'(x)$ $F$

Pokud v kořenovém bodě neexistuje žádná druhá derivace , pak lze rychlost konvergence metody znatelně snížit.

Zvažte příklad:

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

Potom a kromě případů , kdy to není definováno. ${\displaystyle f'(x)=1+(4/3)x^{1/3))$ ${\displaystyle f''(x)=(4/9)x^{-2/3))$ $x=0$

V dalším kroku máme : $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})}}.

Rychlost konvergence výsledné sekvence je přibližně 4/3. To je výrazně méně než 2, což je nutné pro kvadratickou konvergenci, takže v tomto případě můžeme mluvit pouze o lineární konvergenci, ačkoli funkce je všude spojitě diferencovatelná , derivace v kořeni není rovna nule a je všude nekonečně diferencovatelná . kromě kořene. $F$

Pokud je derivace v kořenovém bodě rovna nule, pak rychlost konvergence nebude kvadratická a metoda sama může ukončit vyhledávání předčasně a poskytnout aproximaci, která je pro danou přesnost nesprávná.

Nechat

f(x)=x^{2}.

Pak a odtud . Konvergence metody tedy není kvadratická, ale lineární, ačkoli funkce je všude nekonečně diferencovatelná. $f'(x)=2x$ $xf(x)/f'(x)=x/2$

Omezení

Nechť je rovnice dána , kde a je třeba najít její řešení. $f(x)=0$ $f(x)\colon \mathbb {X} \to \mathbb {R}$

Níže je uvedena formulace hlavní věty, která nám umožňuje dát jasné podmínky použitelnosti. Nese jméno sovětského matematika a ekonoma Leonida Vitalieviče Kantoroviče ( 1912-1986 ) .

Kantorovičova věta.

Pokud existují takové konstanty , že: $A,\;B,\;C$

${\frac {1}{|f'(x)|}}<A$ na , to znamená, že existuje a nerovná se nule; $[a,\;b]$ $f'(x)$
$\left|{\frac {f(x)}{f'(x)}}\right|<B$ na , tedy omezeně; $[a,\;b]$ $f(x)$
$\exists f''(x)$ na , a ; $[a,\;b]$ $|f''(x)|\leqslant C\leqslant {\frac {1}{2AB))$

Navíc délka uvažovaného segmentu . Pak jsou pravdivá následující tvrzení: $|ab|<{\frac {1}{AB}}\left(1-{\sqrt {1-2ABC}}\right)$

existuje kořen rovnice ; $[a,\;b]$ $x^{*}$ $f(x)=0\colon \exists x^{*}\in [a,\;b]\colon f(x^{*})=0$
if , pak iterační posloupnost konverguje k tomuto kořenu: ; $x_{0}={\frac {a+b}{2))$ $\left\{x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})))\right\}\to x^ {*}$
chybu lze odhadnout podle vzorce . $|x^{*}-x_{n}|\leqslant {\frac {B}{2^{n-1}}}(2ABC)^{2^{n-1}}$

Z posledního tvrzení věty zejména vyplývá kvadratická konvergence metody:

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

Pak budou omezení původní funkce vypadat takto: $f(x)$

funkce musí být omezena;
funkce musí být hladká , dvakrát diferencovatelná ;
jeho první derivace je rovnoměrně oddělena od nuly; $f'(x)$
jeho druhá derivace musí být rovnoměrně ohraničená. $f''(x)$

Historické pozadí

Metodu popsal Isaac Newton v rukopise O analýze rovnicemi nekonečných řad ( latinsky De analysi per aequationes numero terminorum infinitas ) adresovaném Barrowovi v roce 1669 a v The Method of Fluxions and Infinite Series ( latinsky: De metodis fluxionum et serierum infinitarum" ) nebo " Analytická geometrie " ( lat. "Geometria analytica" ) ve sbírkách Newtonových děl, která byla napsána v roce 1671 . Ve svých spisech Newton zavádí pojmy, jako je expanze funkce do řady , infinitesimals a fluxions ( deriváty v současném smyslu). Tato díla vyšla mnohem později: první vyšla v roce 1711 zásluhou Williama Johnsona, druhá vyšla Johnem Colzonem v roce 1736 po smrti tvůrce. Popis metody se však výrazně lišil od jeho současného výkladu: Newton aplikoval svou metodu výhradně na polynomy . Počítal ne po sobě jdoucí aproximace , ale posloupnost polynomů a jako výsledek obdržel přibližné řešení . $x_{n}$ $X$

Metoda byla poprvé publikována v pojednání „Algebra“ od Johna Wallise v roce 1685, na jehož žádost ji stručně popsal sám Newton. V roce 1690 Joseph Raphson publikoval zjednodušený popis ve svém „Analysis aequationum universalis“ ( latinsky: „Analysis aequationum universalis“ ). Raphson si prohlížel Newtonovu metodu jako čistě algebraickou a omezil její použití na polynomy, ale popsal metodu v podmínkách postupných aproximací namísto obtížněji pochopitelné sekvence polynomů používané Newtonem. Konečně v roce 1740 byla Newtonova metoda popsána Thomasem Simpsonem jako iterační metoda prvního řádu pro řešení nelineárních rovnic pomocí derivace, jak je zde uvedeno. Ve stejné publikaci Simpson zobecnil metodu na případ systému dvou rovnic a poznamenal, že Newtonova metoda může být také aplikována na optimalizační problémy nalezením nuly derivace nebo gradientu . $x_{n}$

V 1879, Arthur Cayley , v Newton-Fourier imaginární problém, byl první poukázat na potíže v zobecnění Newtonovy metody k případu imaginárních kořenů polynomials stupně vyšší než sekunda a komplexní počáteční aproximace. Tato práce připravila cestu pro studium teorie fraktálů .

Zobecnění a modifikace

Metoda secantu

Související metoda sečny je Newtonova „přibližná“ metoda a vyhýbá se výpočtu derivace. Hodnota derivátu v iteračním vzorci je nahrazena jeho odhadem pro dva předchozí body iterace:

${\displaystyle f'(x_{n})\přibližně {\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1))))$ .

Hlavní vzorec má tedy tvar

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

Tato metoda je podobná Newtonově metodě, ale má o něco pomalejší rychlost konvergence. Pořadí konvergence metody se rovná zlatému řezu - 1,618 ...

Poznámky. 1) Pro zahájení iteračního procesu jsou vyžadovány dvě různé hodnoty a . 2) Na rozdíl od „reálné Newtonovy metody“ (metoda tečny), která vyžaduje pouze ukládání (a dočasně během výpočtů a ), metoda sečny vyžaduje uložení , , , . 3) Používá se, pokud je výpočet obtížný (například vyžaduje velké množství strojových zdrojů: čas a / nebo paměť). $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)$

Metoda jedné tečny

Aby se snížil počet volání na hodnoty derivace funkce, používá se takzvaná metoda jedné tečny.

Iterační vzorec pro tuto metodu je:

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

Podstatou metody je vypočítat derivaci pouze jednou, v počátečním aproximačním bodě , a tuto hodnotu pak použít v každé následující iteraci: $x_{0}$

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

S touto volbou platí v bodě následující rovnost : $\alpha _{0}$ $x_{0}$

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

a pokud je segment, na kterém se předpokládá přítomnost kořene a je zvolena počáteční aproximace , dostatečně malý a derivace je spojitá, pak se hodnota nebude příliš lišit , a proto bude graf procházet téměř vodorovně a protínat přímka , což zase zajistí rychlou konvergenci posloupnosti aproximačních bodů ke kořenu. $x^{*}$ $x_{0}$ $\varphi '(x)$ $\varphi '(x^{*})$ $\varphi '(x_{0})=0$ $y=\varphi (x)$ $y=x$

Tato metoda je speciálním případem metody jednoduché iterace . Má lineární řád konvergence.

Vícerozměrné pouzdro

Zobecněme získaný výsledek na vícerozměrný případ.

Nechť je nutné najít řešení systému:

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

Vybereme-li si nějakou počáteční hodnotu , nalezneme postupné aproximace řešením soustav rovnic : ${\vec {x}}^{[0]}$ ${\vec {x}}^{[j+1]}$

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

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

Aplikované na optimalizační problémy

Nechť je třeba najít minimum funkce několika proměnných . Tato úloha je ekvivalentní problému nalezení nuly gradientu . Aplikujme výše uvedenou Newtonovu metodu: $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,

kde je hesián funkce . $H({\vec {x)))$ $f({\vec {x)))$

V pohodlnější iterační formě tento výraz vypadá takto:

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

Je třeba poznamenat, že v případě kvadratické funkce najde Newtonova metoda extrém v jedné iteraci.

Nalezení hessovské matice je výpočetně nákladné a často nemožné. V takových případech mohou jako alternativa sloužit kvazi-newtonské metody , ve kterých je v procesu akumulace informací o zakřivení funkce zabudována aproximace Hessovy matice.

Newton-Raphsonova metoda

Newton-Raphsonova metoda je vylepšením Newtonovy extrémní metody popsané výše. Hlavní rozdíl je v tom, že při další iteraci jedna z metod jednorozměrné optimalizace vybere optimální krok:

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

kde K optimalizaci výpočtů se používá následující vylepšení: místo přepočítávání Hessianu účelové funkce při každé iteraci se omezíme na počáteční aproximaci a aktualizujeme ji pouze jednou v krocích, nebo ji neaktualizujeme vůbec. $\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$

Aplikováno na problémy nejmenších čtverců

V praxi se často vyskytují úlohy, ve kterých je potřeba upravit volné parametry objektu nebo upravit matematický model na reálná data. V těchto případech se objevují problémy nejmenších čtverců :

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 .

Tyto problémy se vyznačují speciálním druhem gradientu a hessovské matice :

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

kde je Jacobiho matice vektorové funkce , je Hessova matice pro její složku . $J({\vec {x)))$ ${\vec {f))({\vec {x)))$ $H_{i}({\vec {x)))$ $f_{i}({\vec {x)))$

Poté se ze systému určí další krok: ${\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-Newtonova metoda

Gauss-Newtonova metoda je založena na předpokladu, že člen dominuje nad . Tento požadavek není splněn, pokud jsou minimální rezidua velká, tedy pokud je norma srovnatelná s maximální vlastní hodnotou matice . Jinak můžete napsat: $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}}).

Když je tedy norma blízká nule a matice má plnou hodnost sloupce , krok se od newtonovského kroku liší jen málo (s přihlédnutím k ), a metoda může dosáhnout kvadratické míry konvergence, i když se druhé derivace neberou v úvahu. účet. Vylepšením metody je Levenberg-Marquardtův algoritmus založený na heuristických úvahách. $\|Q({\vec {x)))\|$ $J({\vec {x)))$ ${\vec {p}}$ $Q({\vec {x)))$

Zobecnění na komplexní rovinu

Doposud se v popisu metody používaly funkce, které provádějí mapování v rámci množiny reálných hodnot . Metodu však lze také použít k nalezení nuly funkce komplexní proměnné . Postup však zůstává stejný:

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

Zvláště zajímavá je volba počáteční aproximace . Vzhledem k tomu, že funkce může mít několik nul, může metoda v různých případech konvergovat k různým hodnotám a je zcela přirozené chtít zjistit, které oblasti zajistí konvergenci ke konkrétnímu kořenu. Tato otázka zajímala Arthura Cayleyho již v roce 1879 , ale bylo možné ji vyřešit až v 70. letech dvacátého století s příchodem výpočetní techniky. Ukázalo se, že na průsečíkech těchto oblastí (obvykle se jim říká oblasti přitažlivosti ) vznikají takzvané fraktály - nekonečné sobě podobné geometrické obrazce. $z_{0}$

Vzhledem k tomu, že Newton aplikoval svou metodu výhradně na polynomy , fraktály vzniklé v důsledku takové aplikace se staly známými jako Newtonovy fraktály nebo Newtonovy bazény .

Implementace

scala

objekt NewtonMethod { val přesnost = 1e-6 @tailrec def metoda ( x0 : Double , f : Double => Double , dfdx : Double => Double , e : Double ): Double = { val x1 = x0 - f ( x0 ) / dfdx ( x0 ) if ( abs ( x1 - x0 ) < e ) metoda x1 else ( 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 případ x if ( x > 0 ) => metoda ( x / 2 , g ( x ), dgdx , přesnost ) } }

Python

z matematiky import sin , cos z psaní 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 : """ řeší f(x) = 0 Newtonovou metodou s přesností eps :param f: f :param f_prime: f' :param x0: počáteční bod :param eps: požadovaná přesnost :return: kořen z f(x) = 0 """ x , x_prev , i = x0 , x0 + 2 * eps , 0 zatímco abs ( x - x_prev ) >= eps a i < kmax : x , x_prev , i = x - f ( x ) / f_prime ( x ), x , i + 1 vrátit x class 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 sebe . claimAlmostEqual ( newton ( f , f_prime , x0 ), x_star ) if __name__ == '__main__' : unittest . hlavní ()

PHP

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

Oktáva

funkce res = nt () eps = 1e-7 ; x0_1 = [ -0,5 , 0,5 ] ; max_iter = 500 ; xopt = new (@ resh , eps , max_iter ); xopt endfunction function a = new ( f, eps, max_iter ) x = -1 ; _ p0 = 1 ; i = 0 _ while ( abs ( p0 ) > = eps ) [ p1 , q1 ]= f ( x ); x = x - pl / ql ; p0 = p1 ; i = i + 1 ; konec i a = x ; endfunction function [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 ; koncová funkce

Delphi

// vypočítaná funkce function fx ( x : Double ) : Double ; begin Vysledek := x * x - 17 ; konec ; // odvozená funkce funkce f(x) dfx ( x : Double ) : Double ; begin Vysledek := 2 * x ; konec ; funkce řešit ( fx , dfx : TFunc < Double , Double > ; x0 : Double ) : Double ; const eps = 0,000001 ; var x1 : Double ; begin x1 := x0 - fx ( x0 ) / dfx ( x0 ) ; // první aproximace while ( Abs ( x1 - x0 ) > eps ) do begin // dokud není dosaženo přesnosti 0,000001 x0 := x1 ; x1 := x1 - fx ( x1 ) / dfx ( x1 ) ; // následné aproximace end ; Vysledek := x1 ; konec ; // Volání řešit ( fx , dfx , 4 ) ;

C++

#include <iostream> #include <math.h> double fx ( double x ) { return x * x - 17 ;} // vypočítaná funkce double dfx ( double x ) { return 2 * x ;} // derivace funkce typedef double ( * funkce )( double x ); // přiřazení funkce typu double solve ( funkce fx , funkce dfx , double x0 , double eps = 1e-8 ) { double xi = x0 ; //Aktuální bod v i-té iteraci while ( fabs ( fx ( xi )) >= eps ) // dokud není dosaženo přesnosti 0,00000001 xi = xi - fx ( xi ) / dfx ( xi ); // následné aproximace return xi ; } int main () { std :: cout << řešit ( fx , dfx , 4 ) << std :: endl ; návrat 0 ; }

C

typedef double ( * funkce )( double x ); double TangentsMethod ( funkce f , funkce df , double xn , double eps ) { double x1 = xn - f ( xn ) / df ( xn ); double x0 = xn ; while ( abs ( x0 - x1 ) > eps ) { x0 = x1 ; xl = xl - f ( xl ) / df ( xl ); } návrat x1 ; } //Vyberte počáteční odhad xn = MyFunction ( A ) * My2Derivative ( A ) > 0 ? B : A ; double MyFunction ( double x ) { return ( pow ( x , 5 ) - x - 0,2 ); } //Vaše funkce double MyDerivative ( double x ) { return ( 5 * pow ( x , 4 ) - 1 ); } //První derivace double My2Derivative ( double x ) { return ( 20 * pow ( x , 3 )); } //Druhá derivace //Příklad volání funkce double x = TangentsMethod ( MyFunction , MyDerivative , xn , 0.1 )

Haskell

import Data.List ( iterate' ) main :: IO () main = tisk $ vyřešit ( \ x -> x * x - 17 ) ( * 2 ) 4 -- Funkce řešit je univerzální pro všechny reálné typy, jejichž hodnoty lze porovnávat. vyřešit = vyřešit 0,000001 esolve epsilon func deriv x0 = fst . head $ dropWhile pred pairs kde pred ( xn , xn1 ) = ( abs $ xn - xn1 ) > epsilon -- Funkce pred určuje, zda bylo dosaženo požadované přesnosti. next xn = xn - func xn / deriv xn -- Další funkce vypočítá novou aproximaci. iters = iterate' next x0 -- Nekonečný seznam iterací. pairs = zip iters ( tail iters ) -- Nekonečný seznam dvojic iterací formuláře: [(x0, x1), (x1, x2) ..].

Literatura

Akulich I. L. Matematické programování v příkladech a úlohách: Proc. příspěvek na studentské hospodářství. specialista. vysoké školy. - M . : Vyšší škola, 1986. - 319 s. : nemocný. - BBK 22.1 A44 . - MDT 517,8 .
Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Výpočtové metody pro inženýry: Proc. příspěvek. - M . : Vyšší škola, 1994. - 544 s. : nemocný. - BBK 32,97 A62 . - UDC 683.1 . — ISBN 5-06-000625-5 .
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Numerické metody. - 8. vyd. - M . : Laboratoř základních znalostí, 2000.
Vavilov S. I. Isaac Newton . - M .: Ed. Akademie věd SSSR, 1945.
Volkov E. A. Numerické metody. — M .: Fizmatlit, 2003.
Gill F., Murray W., Wright M. Praktická optimalizace. Za. z angličtiny. — M .: Mir, 1985.
Korn G., Korn T. Příručka matematiky pro vědce a inženýry. - M .: Nauka, 1970. - S. 575-576.
Korshunov Yu.M., Korshunov Yu.M. Matematické základy kybernetiky. - Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmy pro řešení problémů nelineárního programování. — M. : MEPhI, 1982.
Morozov AD Úvod do teorie fraktálů. — MEPhI, 2002.

Viz také

Odkazy

"Newtonovy bazény" na fractalworld.xaoc.ru
"Isaac Newton" na www.scottish-wetlands.org
"Matematické práce Kantoroviče" na stránkách Matematického ústavu SB RAS
Hazewinkel, Michiel, ed. (2001), Newtonova metoda , Encyklopedie matematiky , Springer , ISBN 978-1-55608-010-4
Weisstein, Eric W. Newton's Method (anglicky) na webu Wolfram MathWorld .
Newtonova metoda, Citizendium.
Mathews, J., Zrychlené a upravené Newtonovy metody, Poznámky ke kurzu.
Wu, X., Kořeny rovnic, Poznámky ke kurzu.

Optimalizační metody
Jednorozměrný	metoda zlatého řezu Dichotomie Parabolová metoda Vyhledávání v mřížce Jednotná metoda vyhledávání bloků Fibonacciho metoda Ternární hledání Piyavského metoda Stronginovou metodou
Nulové pořadí	Gaussova metoda Metoda Nelder-Mead Hook-Jeevesova metoda Rosenbrockova metoda Powellova metoda
První objednávka	gradientní sestup Zeutendijkova metoda Souřadnicový sestup Metoda konjugovaného gradientu Kvazi-newtonské metody Levenberg-Marquardtův algoritmus
druhá objednávka	Newtonova metoda Newton-Raphsonova metoda Algoritmus Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastické	Metoda Monte Carlo Simulované žíhání Evoluční algoritmy diferenciální evoluce Algoritmus mravenců Metoda roje částic Algoritmus včelstva Metoda náhodné chůze
Metody lineárního programování	Simplexní metoda Gomoriho algoritmus Elipsoidní metoda Potenciální metoda
Metody nelineárního programování	Sekvenční kvadratické programování