Newtonova metoda - Newton's method

V numerické analýze , Newtonova metoda , známá také jako Newton-Raphsonova metoda , pojmenoval Isaac Newton a Joseph Raphsonova , je kořen zjišťovací algoritmus , který vytváří postupně lepší přiblížení ke kořenům (nebo nul) o skutečné cenil funkce . Nejzákladnější verze začíná s jedinou variabilní funkce f definovaná pro reálné proměnné x , funkce se derivát f ' , a počáteční odhad x ₀ pro kořen z f . Pokud funkce splňuje dostatečné předpoklady a počáteční odhad je blízký, pak

${\ displaystyle x_ {1} = x_ {0}-{\ frac {f (x_ {0})} {f '(x_ {0})}}}$

je lepší aproximace kořene než x ₀ . Geometricky, ( x ₁ , 0) je průsečík x aretačním kroužkem a tečna v grafu o f u ( x ₀ , f  ( x ₀ )) : to je, zlepšený odhad je jedinečný kořen lineární aproximace v počátečním bodě. Proces se opakuje jako

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

dokud není dosaženo dostatečně přesné hodnoty. Tento algoritmus je první ve třídě domácích metod , následovaný Halleyovou metodou . Metodu lze také rozšířit na komplexní funkce a soustavy rovnic .

Popis

Funkce f je zobrazena modře a tečná čára je červeně. Vidíme, že x _{n + 1} je lepší aproximace než x _n pro kořen x funkce f .

Myšlenkou je začít s počátečním odhadem, který je přiměřeně blízký skutečnému kořenu, pak aproximovat funkci jeho tečnou čarou pomocí kalkulu a nakonec vypočítat x -intercept této tečné přímky pomocí elementární algebry . To x -intercept typicky být lepší přiblížení ke kořeni původní funkci je než první odhad, a tato metoda může být opakována .

Formálněji předpokládejme, že f  : ( a , b ) → ℝ je diferencovatelná funkce definovaná na intervalu ( a , b ) s hodnotami v reálných číslech  ℝ a máme nějakou aktuální aproximaci x _n . Potom můžeme odvodit vzorec pro lepší aproximaci, x _{n + 1} podle diagramu vpravo. Rovnice tečné přímky ke křivce y = f  ( x ) při x = x _n je

${\ Displaystyle y = f '(x_ {n}) \, (x-x_ {n})+f (x_ {n}),}$

kde f ' označuje derivát . X -intercept této linie (hodnota x , která je y = 0 ), je brána jako další aproximace, x _{n + 1} , na kořen, takže rovnice tečny je splněn, pokud : ${\ Displaystyle (x, y) = (x_ {n+1}, 0)}$

${\ Displaystyle 0 = f '(x_ {n}) \, (x_ {n+1} -x_ {n})+f (x_ {n}).}$

Řešení pro x _{n + 1} dává

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

Proces spustíme s libovolnou počáteční hodnotou x ₀ . (Čím blíže k nule, tím lépe. Ale při absenci jakékoli intuice, kde by mohla ležet nula, by metoda „hádat a kontrolovat“ mohla zúžit možnosti na přiměřeně malý interval odvoláním se na teorém o středních hodnotách .) Metoda se obvykle sbíhá za předpokladu, že je tento počáteční odhad dostatečně blízko neznámé nule a že f ′ ( x ₀ ) ≠ 0 . Navíc pro nulu multiplicity  1 je konvergence přinejmenším kvadratická (viz rychlost konvergence ) v sousedství nuly, což intuitivně znamená, že počet správných číslic se v každém kroku zhruba zdvojnásobí. Další podrobnosti naleznete v níže uvedené části analýzy .

Metody majitele domu jsou podobné, ale mají vyšší řád pro ještě rychlejší konvergenci. Extra výpočty požadované pro každý krok však mohou zpomalit celkový výkon ve srovnání s Newtonovou metodou, zvláště pokud je f nebo jeho deriváty výpočetně nákladné na vyhodnocení.

Dějiny

Název „Newtonova metoda“ je odvozen z popisu zvláštního případu Isaaca Newtona v De analysi per aequationes numero terminorum infinitas (napsáno v roce 1669, publikováno v roce 1711 Williamem Jonesem ) a v De metodis fluxionum et serierum infinitarum ( napsáno v roce 1671, přeloženo a publikováno jako Metoda toků v roce 1736 Johnem Colsonem ). Jeho metoda se však podstatně liší od moderní metody uvedené výše. Newton použil metodu pouze na polynomy, počínaje počátečním kořenovým odhadem a extrahováním posloupnosti oprav chyb. Každou opravu použil k přepsání polynomu ve smyslu zbývající chyby a poté vyřešil novou opravu zanedbáním termínů vyššího stupně. Metodu výslovně nespojoval s deriváty ani nepředložil obecný vzorec. Newton aplikoval tuto metodu na numerické i algebraické problémy, přičemž v druhém případě vytvořil Taylorovu řadu .

Newton možná odvodil svou metodu z podobné, ale méně přesné metody Viety . Podstatu Vietovy metody lze nalézt v díle perského matematika Sharafa al-Din al-Tusiho , zatímco jeho nástupce Jamshīd al-Kashi použil formu Newtonovy metody k řešení x ^P - N = 0 k nalezení kořenů N ( Ypma 1995). Zvláštní případ Newtonovy metody pro výpočet odmocnin byl znám již od starověku a často se mu říká babylonská metoda .

Newtonovu metodu použil japonský matematik Seki Kōwa ze 17. století k řešení rovnic s jednou proměnnou, ačkoli spojení s kalkulem chybělo.

Newtonova metoda byla poprvé publikována v roce 1685 v A Treatise of Algebra Historical and Practical od Johna Wallise . V roce 1690 publikoval Joseph Raphson zjednodušený popis v Analysis aequationum universalis . Raphson také použil metodu pouze na polynomy, ale vyhnul se únavnému Newtonovu procesu přepisování extrahováním každé následné opravy z původního polynomu. To mu umožnilo odvodit opakovaně iterativní výraz pro každý problém. Nakonec, v roce 1740, Thomas Simpson popsal Newtonovu metodu jako iterační metodu pro řešení obecných nelineárních rovnic pomocí kalkulu, přičemž v podstatě uvedl výše uvedený popis. Ve stejné publikaci Simpson také uvádí zobecnění systémů dvou rovnic a poznamenává, že Newtonovu metodu lze použít k řešení problémů s optimalizací nastavením přechodu na nulu.

Arthur Cayley v roce 1879 v The Newton – Fourierův imaginární problém byl první, kdo si všiml obtíží při generalizaci Newtonovy metody na komplexní kořeny polynomů se stupněm vyšším než 2 a komplexními počátečními hodnotami. To otevřelo cestu ke studiu teorie iterací racionálních funkcí.

Praktické úvahy

Newtonova metoda je silná technika - konvergence je obecně kvadratická: jak metoda konverguje ke kořenu, rozdíl mezi kořenem a aproximací je v každém kroku na druhou (počet přesných číslic se zhruba zdvojnásobuje). S touto metodou však existují určité potíže.

Obtížnost při výpočtu derivace funkce

Newtonova metoda vyžaduje, aby derivát mohl být vypočítán přímo. Analytický výraz pro derivát nemusí být snadno dosažitelný nebo jeho vyhodnocení může být nákladné. V těchto situacích může být vhodné aproximovat derivaci pomocí sklonu čáry přes dva blízké body funkce. Použití této aproximace by vedlo k něčemu podobnému sekové metodě, jejíž konvergence je pomalejší než u Newtonovy metody.

Selhání metody v konvergenci ke kořenu

Před implementací Newtonovy metody je důležité zkontrolovat důkaz kvadratické konvergence . Konkrétně by měl člověk zkontrolovat předpoklady uvedené v důkazu. V situacích, kdy se metodě nepodaří sblížit , je to proto, že nejsou splněny předpoklady provedené v tomto důkazu.

Přestřelení

Pokud se první derivace nechová dobře v sousedství konkrétního kořene, metoda může přestřelit a odchýlit se od tohoto kořene. Příklad funkce s jedním kořenem, pro kterou se derivát v okolí kořene nechová dobře, je

${\ Displaystyle f (x) = | x |^{a}, \ quad 0 <a <{\ tfrac {1} {2}}}$

u nichž bude kořen přestřelen a posloupnost x se bude rozcházet. Pro a = 1/2, kořen bude stále přestřelen, ale posloupnost bude oscilovat mezi dvěma hodnotami. Pro1/2< <1 , kořen bude stále Přestřelené ale sekvence se sbíhají, a pro ≥ 1 kořen nebude předkus vůbec.

V některých případech lze Newtonovu metodu stabilizovat pomocí postupné nadměrné relaxace nebo lze rychlost konvergence zvýšit použitím stejné metody.

Stacionární bod

Pokud dojde ke stacionárnímu bodu funkce, je derivace nulová a metoda bude ukončena z důvodu dělení nulou .

Špatný počáteční odhad

Velká chyba v počátečním odhadu může přispět ke nekonvergenci algoritmu. K překonání tohoto problému lze často linearizovat funkci, která je optimalizována pomocí počtu, protokolů, diferenciálů nebo dokonce pomocí evolučních algoritmů, jako je stochastické tunelování . Dobré počáteční odhady se blíží konečnému globálně optimálnímu odhadu parametrů. V nelineární regresi je součet čtvercových chyb (SSE) v oblasti odhadů konečných parametrů pouze „blízký“ parabolickému. Počáteční odhady zde nalezené umožní Newtonově -Raphsonově metodě rychle se sblížit. Pouze zde je hesenská matice SSE kladná a první derivace SSE se blíží nule.

Zmírnění nekonvergence

V robustní implementaci Newtonovy metody je běžné omezit počet iterací, navázat řešení na interval, o kterém je známo, že obsahuje kořen, a kombinovat metodu s robustnější metodou hledání kořenů.

Pomalá konvergence pro kořeny multiplicity větší než 1

Pokud má hledaný kořen multiplicitu větší než jedna, je míra konvergence pouze lineární (chyby snížené o konstantní faktor v každém kroku), pokud nejsou podniknuty zvláštní kroky. Pokud existují dva nebo více kořenů, které jsou blízko sebe, může trvat mnoho iterací, než se iterace dostanou dostatečně blízko k jednomu z nich, aby byla patrná kvadratická konvergence. Pokud je však znát multiplicita kořene, následující upravený algoritmus zachovává kvadratickou míru konvergence: ${\ displaystyle m}$

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

To je ekvivalentní použití postupné nadměrné relaxace . Na druhou stranu, pokud není známa multiplicita m kořene, je možné odhadnout po provedení jedné nebo dvou iterací a poté tuto hodnotu použít ke zvýšení rychlosti konvergence. ${\ displaystyle m}$

Pokud je multiplicita m kořene konečná, pak g ( x ) = f ( x ) / f ′ ( x ) bude mít kořen na stejném místě s multiplicitou 1. Použití Newtonovy metody k nalezení kořene g ( x ) se obnoví kvadratická konvergence v mnoha případech, ačkoli obecně zahrnuje druhou derivaci f ( x ) . Ve zvláště jednoduchém případě, pokud f ( x ) = x ^m, pak g ( x ) = x / m a Newtonova metoda najde kořen v jedné iteraci s

${\ Displaystyle x_ {n+1} = x_ {n}-{\ frac {g (x_ {n})} {g '(x_ {n})}} = x_ {n}-{\ frac {x_ { n}/m} {1/m}} = 0 \ ,.}$

Analýza

Předpokládejme, že funkce f má nulu v alfa , tj f  ( alfa ) = 0 , a f je diferencovatelná v sousedství z alfa .

Pokud f je spojitě diferencovatelná a jeho derivát je nenulová v  alfa , pak existuje sousedství z α taková, že pro všechny výchozí hodnoty x ₀ v této čtvrti, sekvenci ( x _n ) bude setkají na alfa .

Pokud je funkce spojitě diferencovatelná a její derivace není 0 na α a má druhou derivaci na α, pak je konvergence kvadratická nebo rychlejší. Pokud druhá derivace není 0 v α, pak je konvergence pouze kvadratická. Pokud třetí derivace existuje a je ohraničena v sousedství α , pak:

${\ Displaystyle \ Delta x_ {i+1} = {\ frac {f '' (\ alpha)} {2f '(\ alpha)}} (\ Delta x_ {i})^{2}+O (\ Delta x_ {i})^{3} \ ,,}$

kde

${\ Displaystyle \ Delta x_ {i} \ triangleq x_ {i}-\ alpha \ ,.}$

Pokud je derivace 0 na α , pak je konvergence obvykle pouze lineární. Konkrétně, pokud f je dvakrát spojitě diferencovatelný, f ′ ( α ) = 0 a f ″ ( α ) ≠ 0 , pak existuje okolí α takové, že pro všechny počáteční hodnoty x ₀ v tomto sousedství se posloupnost iterací sbíhá lineárně s rychlostí 1/2 Alternativně, je-li f ' ( α ) = 0 a f' ( x ) ≠ 0 pro x ≠ α , x  v okolí u z alfa , α být nulu multiplicity r , a, pokud f ∈ C ^r ( U ) , pak existuje sousedství α takové, že pro všechny počáteční hodnoty x ₀ v tomto sousedství se posloupnost iterací lineárně sbíhá.

Ani lineární konvergence však není v patologických situacích zaručena.

V praxi jsou tyto výsledky lokální a okolí konvergence není předem známé. Ale jsou tu i některé výsledky na globální konvergence: například, vzhledem k tomu, že právo sousedství U ₊ of alfa , pokud f je dvakrát diferencovatelná v U ₊ a je-li f ' ? 0 , f · f " > 0 v U ₊ , pak pro každá x ₀ v U ₊ sekvence x _k monotónně klesá na α .

Důkaz kvadratické konvergence pro Newtonovu iterační metodu

Podle Taylorovy věty může být jakákoli funkce f  ( x ), která má spojitou druhou derivaci, reprezentována expanzí kolem bodu, který je blízko kořene f  ( x ) . Předpokládejme, že tento kořen je α . Pak expanze f  ( α ) o x _n je:

${\ Displaystyle f (\ alpha) = f (x_ {n})+f '(x_ {n}) (\ alpha -x_ {n})+R_ {1} \,}$

( 1 )

kde Lagrangeova forma Taylorův rozvoj série zbytek je

${\ Displaystyle R_ {1} = {\ frac {1} {2!}} f '' (\ xi _ {n}) (\ alpha -x_ {n})^{2} \ ,,}$

kde ξ _n je mezi x _n a α .

Protože α je kořen, ( 1 ) se stává:

${\ Displaystyle 0 = f (\ alpha) = f (x_ {n})+f '(x_ {n}) (\ alpha -x_ {n})+{\ tfrac {1} {2}} f' ' (\ xi _ {n}) (\ alpha -x_ {n})^{2} \,}$

( 2 )

Dělení rovnice ( 2 ) f ' ( x _n ) a přeskupení dává

${\ Displaystyle {\ frac {f (x_ {n})} {f '(x_ {n})}}+\ left (\ alpha -x_ {n} \ right) = {\ frac {-f' '( \ xi _ {n})} {2f '(x_ {n})}} \ left (\ alpha -x_ {n} \ right)^{2}}$

( 3 )

Pamatujte, že x _{n + 1} je definováno

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

( 4 )

člověk to zjistí

${\ Displaystyle \ underbrace {\ alpha -x_ {n+1}} _ {\ varepsilon _ {n+1}} = {\ frac {-f '' (\ xi _ {n})} {2f '(x_ {n})}} (\, \ underbrace {\ alpha -x_ {n}} _ {\ varepsilon _ {n}} \,)^{2} \ ,.}$

To znamená,

${\ Displaystyle \ varepsilon _ {n+1} = {\ frac {-f '' (\ xi _ {n})} {2f '(x_ {n})}}} \ cdot {\ varepsilon _ {n}} ^{2} \ ,.}$

( 5 )

Užívání absolutní hodnoty obou stran dává

${\ Displaystyle \ left | {\ varepsilon _ {n+1}} \ right | = {\ frac {\ left | f '' (\ xi _ {n}) \ right |} {2 \ left | f '( x_ {n}) \ vpravo |}} \ cdot {\ varepsilon _ {n}}^{2} \ ,.}$

( 6 )

Rovnice ( 6 ) ukazuje, že míra konvergence je přinejmenším kvadratická, pokud jsou splněny následující podmínky:

1. f ' ( x ) ≠ 0 ; pro všechna x ∈ I , kde I je interval [ α - r , α + r ] pro některé r ≥ | α - x ₀ | ;
2. f ″ ( x ) je spojitý, pro všechna x ∈ I ;
3. x ₀ je dostatečně blízko kořenu α .

Termín dostatečně blízký v tomto kontextu znamená následující:

Nakonec ( 6 ) lze vyjádřit následujícím způsobem:

${\ Displaystyle \ left | {\ varepsilon _ {n+1}} \ right | \ leq M {\ varepsilon _ {n}}^{2} \,}$

kde M je supremum variabilního koeficientu ε _n ² v intervalu I definovaném v podmínce 1, tj.

${\ Displaystyle M = \ sup _ {x \ in I} {\ frac {1} {2}} \ left | {\ frac {f '' (x)} {f '(x)}} \ right |. \,}$

Počáteční bod x ₀ musí být vybrán tak, aby byly splněny podmínky 1 až 3, kde třetí podmínka vyžaduje, aby M | ε ₀ | <1 .

Povodí přitažlivosti

Nespojité podmnožiny povodí přitažlivosti - oblasti skutečné číselné řady tak, že v každé oblasti iterace z jakéhokoli bodu vede k jednomu konkrétnímu kořenu - mohou být nekonečné a libovolně malé. Například pro funkci f  ( x ) = x ³ - 2 x ² - 11 x + 12 = ( x - 4) ( x - 1) ( x + 3) jsou v postupných povodí přitažlivosti následující počáteční podmínky:

2. 352 875 27	konverguje k	4;
2,352 841 72	konverguje k	−3;
2,352 837 35	konverguje k	4;
2,352 836 327	konverguje k	−3;
2,352 836 323	konverguje k	1.

Analýza selhání

Newtonova metoda se zaručeně sbíhá, pouze pokud jsou splněny určité podmínky. Pokud jsou splněny předpoklady učiněné v důkazu kvadratické konvergence, metoda bude konvergovat. U následujících podsekcí selhání metody konvergence znamená, že předpoklady uvedené v důkazu nebyly splněny.

Špatné výchozí body

V některých případech jsou splněny podmínky na funkci, které jsou nezbytné pro konvergenci, ale bod zvolený jako počáteční bod není v intervalu, kde se metoda sbíhá. K tomu může dojít například v případě, že funkce, jejíž kořen je hledán, se blíží nule asymptoticky, když x přechází na ∞ nebo −∞ . V takových případech by měla být použita jiná metoda, jako je půlení , k získání lepšího odhadu nuly, která se použije jako počáteční bod.

Iterační bod je nehybný

Zvažte funkci:

${\ Displaystyle f (x) = 1-x^{2}.}$

Má maximum při x = 0 a řešení f  ( x ) = 0 při x = ± 1 . Pokud začneme iterovat ze stacionárního bodu x ₀ = 0 (kde je derivace nulová), x ₁ bude nedefinováno, protože tangenta v (0,1) je rovnoběžná s osou x :

${\ Displaystyle x_ {1} = x_ {0}-{\ frac {f (x_ {0})} {f '(x_ {0})}}} = 0-{\ frac {1} {0}} }$

Ke stejnému problému dochází, pokud je místo počátečního bodu jakýkoli iterační bod nehybný. I když je derivace malá, ale není nulová, další iterace bude mnohem horší aproximace.

Počáteční bod vstupuje do cyklu

Tečné čáry x ³ -2 x + 2 v 0 a 1 protínají osu x na 1 a 0, v tomto pořadí, což ukazuje, proč Newtonova metoda osciluje mezi těmito hodnotami pro některé počáteční body.

U některých funkcí mohou některé výchozí body vstoupit do nekonečného cyklu, což brání konvergenci. Nechat

${\ Displaystyle f (x) = x^{3} -2x+2 \!}$

a vezměte 0 jako výchozí bod. První iterace vytvoří 1 a druhá iterace se vrátí na 0, takže se sekvence bude střídat mezi těmito dvěma bez konvergence do kořene. Ve skutečnosti je tento 2-cyklus stabilní: existují sousedství kolem 0 a kolem 1, ze kterých všechny body iterují asymptoticky k 2-cyklu (a tedy ne ke kořenu funkce). Chování sekvence může být obecně velmi složité (viz Newtonův fraktál ). Skutečné řešení této rovnice je-1,769 292 35 ...

Derivační problémy

Pokud funkce není spojitě diferencovatelná v sousedství kořene, pak je možné, že se Newtonova metoda vždy rozchází a selže, pokud řešení neuhodnete na první pokus.

Derivát neexistuje v kořenovém adresáři

Jednoduchý příklad funkce, kde se Newtonova metoda rozchází, se snaží najít kořen krychle nula. Kořen krychle je spojitý a nekonečně diferencovatelný, s výjimkou x = 0 , kde jeho derivace není definována:

${\ Displaystyle f (x) = {\ sqrt [{3}] {x}}.}$

Pro jakýkoli iterační bod x _n bude další iterační bod:

${\ Displaystyle x_ {n+1} = x_ {n}-{\ frac {f (x_ {n})} {f '(x_ {n})}} = x_ {n}-{\ frac {{x_ {n}}^{\ frac {1} {3}}} {{\ frac {1} {3}} {x_ {n}}^{{\ frac {1} {3}}-1}}} = x_ {n} -3x_ {n} =-2x_ {n}.}$

Algoritmus přestřelí řešení a přistane na druhé straně osy y , dále, než původně byl; použití Newtonovy metody ve skutečnosti zdvojnásobuje vzdálenosti od roztoku při každé iteraci.

Ve skutečnosti se iterace rozcházejí do nekonečna pro každé f  ( x ) = | x | ^α , kde 0 < α <1/2. V omezujícím případě α =1/2(odmocnina), iterace se budou neomezeně střídat mezi body x ₀ a - x ₀ , takže ani v tomto případě nekonvergují.

Nespojitá derivace

Pokud derivát není v kořeni spojitý, pak konvergence nemusí nastat v žádném sousedství kořene. Zvažte funkci

${\ Displaystyle f (x) = {\ begin {cases} 0 & {\ text {if}} x = 0, \\ x+x^{2} \ sin {\ frac {2} {x}} & {\ text {if}} x \ neq 0. \ end {cases}}}$

Jeho derivát je:

${\ Displaystyle f '(x) = {\ begin {cases} 1 & {\ text {if}} x = 0, \\ 1+2x \ sin {\ frac {2} {x}}-2 \ cos {\ frac {2} {x}} & {\ text {if}} x \ neq 0. \ end {cases}}}$

V libovolném sousedství kořene tato derivace stále mění znaménko, když se x blíží 0 zprava (nebo zleva), zatímco f  ( x ) ≥ x - x ² > 0 pro 0 < x <1 .

Tak f  ( x )/f ' ( x ) je neomezený blízko kořene a Newtonova metoda se bude lišit téměř všude v jakémkoli sousedství, přestože:

• funkce je diferencovatelná (a tedy spojitá) všude;
• derivát v kořenu je nenulový;
• f je nekonečně diferencovatelný kromě kořene; a
• derivát je ohraničen v sousedství kořene (na rozdíl od f  ( x )/f ' ( x )).

Nekvadratická konvergence

V některých případech se iterace sbíhají, ale nekonvergují tak rychle, jak bylo slíbeno. V těchto případech se jednodušší metody sbližují stejně rychle jako Newtonova metoda.

Nulový derivát

Pokud je první derivace v kořenu nula, pak konvergence nebude kvadratická. Nechat

${\ Displaystyle f (x) = x^{2} \!}$

pak f ' ( x ) = 2 x a následně

${\ Displaystyle x-{\ frac {f (x)} {f '(x)}} = {\ frac {x} {2}}.}$

Konvergence tedy není kvadratická, i když je funkce všude nekonečně odlišitelná.

K podobným problémům dochází, i když je kořen pouze "téměř" dvojnásobný. Nechte například

${\ Displaystyle f (x) = x^{2} (x-1000) +1.}$

Pak několik prvních iterací počínaje x ₀ = 1 jsou

x ₀ = 1

x ₁ =0,500 250 376 …

x ₂ =0,251 062 828 …

x ₃ =0,127 507 934 …

x ₄ =0,067 671 976 …

x ₅ =0,041 224 176 …

x ₆ =0,032 741 218 …

x ₇ =0,031 642 362 …

trvá šest iterací, než se dosáhne bodu, kde se zdá, že konvergence je kvadratická.

Žádný druhý derivát

Pokud v kořeni není druhá derivace, pak konvergence nemusí být kvadratická. Nechat

${\ Displaystyle f (x) = x+x^{\ frac {4} {3}}.}$

Pak

${\ Displaystyle f '(x) = 1+{\ tfrac {4} {3}} x^{\ frac {1} {3}}.}$

A

${\ displaystyle f '' (x) = {\ tfrac {4} {9}} x^{-{\ frac {2} {3}}}}$

kromě případů, kdy x = 0, kde není definováno. Vzhledem k x _n ,

${\ displaystyle x_ {n+1} = x_ {n}-{\ frac {f (x_ {n})} {f '(x_ {n})}}} = {\ frac {{\ frac {1} { 3}} {x_ {n}}^{\ frac {4} {3}}} {1+{\ tfrac {4} {3}} {x_ {n}}^{\ frac {1} {3} }}}}$

který má přibližně 4/3krát tolik bitů přesnosti, kolik má x _n . To je méně než 2krát tolik, kolik by bylo zapotřebí pro kvadratickou konvergenci. Konvergence Newtonovy metody (v tomto případě) není kvadratická, i když: funkce je všude spojitě diferencovatelná; derivát není v kořenu nula; a f je nekonečně diferencovatelné s výjimkou požadovaného kořene.

Zobecnění

Komplexní funkce

Povodí přitažlivosti pro x ⁵ - 1 = 0 ; tmavší znamená více iterací ke konvergování.

Při řešení složitých funkcí lze Newtonovu metodu přímo použít k nalezení jejich nul. Každá nula má v komplexní rovině přitažlivost , množinu všech počátečních hodnot, které způsobují, že metoda konverguje k této konkrétní nule. Tyto sady lze mapovat jako na obrázku. Pro mnoho složitých funkcí jsou hranice povodí přitažlivosti fraktály .

V některých případech existují oblasti v komplexní rovině, které nejsou v žádném z těchto povodí přitažlivosti, což znamená, že iterace nekonvergují. Pokud například někdo použije skutečnou počáteční podmínku k vyhledání kořene x ² + 1 , všechny následující iterace budou reálná čísla, a proto se iterace nemohou sbíhat do žádného kořene, protože oba kořeny jsou nereálné. V tomto případě téměř všechny skutečné počáteční podmínky vedou k chaotickému chování , zatímco některé počáteční podmínky iterují buď do nekonečna, nebo do opakujících se cyklů libovolné konečné délky.

Curt McMullen ukázal, že u jakéhokoli možného čistě iterativního algoritmu podobného Newtonově metodě se algoritmus rozchází v některých otevřených oblastech komplexní roviny, když je aplikován na nějaký polynom stupně 4 nebo vyšší. McMullen však poskytl obecně konvergentní algoritmus pro polynomy stupně 3.

Chebyshevova metoda třetího řádu

Nash -Moserova iterace

Soustavy rovnic

k proměnné, k funkce

Lze také použít Newtonovu metodu k řešení soustav rovnic, což znamená nalezení (simultánních) nul spojitě diferencovatelných funkcí . To je ekvivalentní nalezení nuly jedné funkce s vektorovou hodnotou . Ve výše uvedené formulaci jsou skaláry nahrazeny vektory a místo dělení funkce derivací musí místo toho funkci vynásobit inverzí její jakobijské matice . Výsledkem je výraz ${\ displaystyle k}$${\ displaystyle k}$${\ Displaystyle f: \ mathbb {R} \ to \ mathbb {R}}$${\ Displaystyle F: \ mathbb {R} ^{k} \ to \ mathbb {R} ^{k}}$${\ displaystyle x_ {n}}$${\ displaystyle \ mathbf {x} _ {n}}$${\ displaystyle f (x_ {n})}$${\ displaystyle f '(x_ {n})}$${\ displaystyle F (\ mathbf {x} _ {n})}$${\ displaystyle k \ times k}$ ${\ displaystyle J_ {F} (\ mathbf {x} _ {n})}$

${\ Displaystyle \ mathbf {x} _ {n+1} = \ mathbf {x} _ {n} -J_ {F} (\ mathbf {x} _ {n})^{-1} F (\ mathbf { x} _ {n})}$.

Spíše než ve skutečnosti počítat inverzi jakobiánské matice lze ušetřit čas a zvýšit numerickou stabilitu řešením soustavy lineárních rovnic

${\ Displaystyle J_ {F} (\ mathbf {x} _ {n}) (\ mathbf {x} _ {n+1}-\ mathbf {x} _ {n}) =-F (\ mathbf {x} _ {n})}$

pro neznámé . ${\ Displaystyle \ mathbf {x} _ {n+1}-\ mathbf {x} _ {n}}$

k proměnné, m rovnice, s m > k

K -dimenzionální varianta Newtonovy metody mohou být použity k řešení systémů je větší než k (nelineárních) rovnic také v případě, že algoritmus používá celkový inverzní z non-čtvercové Jacobian matice J ⁺ = ( J ^T J ) ^-1 J ^T místo inverze J. Pokud nelineární systém nemá řešení, pokusí se metoda najít řešení ve smyslu nelineárních nejmenších čtverců . Další informace najdete v Gauss -Newtonově algoritmu .

V Banachově prostoru

Další generalizace je Newtonova metoda k nalezení kořene funkčního F definovaného v Banachově prostoru . V tomto případě je formulace

${\ Displaystyle X_ {n+1} = X_ {n}-{\ bigl (} F '(X_ {n}) {\ bigr)}^{-1} F (X_ {n}), \,}$

kde F ' ( X _n ) je Fréchetův derivát vypočítaný na X _n . Aby byla metoda použitelná, je třeba, aby derivát Fréchet byl neomezeně invertovatelný v každém X _n . Podmínka existence a konvergence ke kořenu je dána Newtonovou -Kantorovichovou větou .

Přes p -adická čísla

V p -adické analýze má standardní metoda pro zobrazení polynomické rovnice v jedné proměnné p -adický kořen Henselův lemma , který na p -adická čísla používá rekurzi z Newtonovy metody . Vzhledem ke stabilnějšímu chování sčítání a násobení v p -adických číslech ve srovnání se skutečnými čísly (konkrétně jednotková koule v p -adics je prsten), konvergence v Henselově lemmatu může být zaručena za mnohem jednodušších hypotéz než v klasická Newtonova metoda na skutečné linii.

Newton – Fourierova metoda

Newton – Fourierova metoda je rozšířením Newtonovy metody Josepha Fouriera o poskytnutí hranic absolutní chyby aproximace kořenů, přičemž stále poskytuje kvadratickou konvergenci.

Předpokládejme, že f  ( x ) je dvakrát spojitě diferencovatelné na [ a , b ] a že f obsahuje v tomto intervalu kořen. Předpokládejme, že f ′ ( x ), f ″ (x) ≠ 0 v tomto intervalu (to platí například pro f  ( a ) <0 , f  ( b )> 0 a f ′ ( x )> 0 , a f ″ ( x )> 0 v tomto intervalu). To zaručuje, že v tomto intervalu je jedinečný kořen, říkejte tomu α . Pokud je konkávní dolů místo konkávního nahoru, vyměňte f  ( x ) za - f  ( x ), protože mají stejné kořeny.

Nechť x ₀ = b je pravý koncový bod intervalu a nechť z ₀ = a je levý koncový bod intervalu. Vzhledem k tomu, že x _n , definujte

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

což je jen Newtonova metoda jako dříve. Poté definujte

${\ Displaystyle z_ {n+1} = z_ {n}-{\ frac {f (z_ {n})} {f '(x_ {n})}},}$

kde jmenovatel je f ' ( x _n ) a ne f' ( z _n ) . Iterace x _n budou striktně klesat ke kořenu, zatímco iterace z _n se budou striktně zvyšovat ke kořenu. Taky,

${\ Displaystyle \ lim _ {n \ to \ infty} {\ frac {x_ {n+1} -z_ {n+1}} {(x_ {n} -z_ {n})^{2}}} = {\ frac {f '' (\ alpha)} {2f '(\ alpha)}}}$

takže vzdálenost mezi x _n a z _n se kvadraticky zmenšuje.

Kvazi-newtonské metody

Když je Jacobian nedostupný nebo příliš drahý na výpočet při každé iteraci, lze použít kvazi-Newtonovu metodu .

q-analog

Newtonovu metodu lze zobecnit pomocí q-analogu obvyklé derivace.

Upravené Newtonovy metody

Maehlyho postup

Nelineární rovnice má obecně více řešení. Pokud však počáteční hodnota není vhodná, Newtonova metoda nemusí konvergovat k požadovanému řešení nebo může konvergovat ke stejnému řešení, které bylo nalezeno dříve. Když jsme již našli N řešení pro , pak další kořen lze nalézt použitím Newtonovy metody na další rovnici: ${\ displaystyle f (x) = 0}$

${\ Displaystyle F (x) = {\ frac {f (x)} {\ prod _ {i = 1}^{N} (x-x_ {i})}}} = 0.}$

Tato metoda se používá k získání nul Besselovy funkce druhého druhu.

Hiranova modifikovaná Newtonova metoda

Hiranova modifikovaná Newtonova metoda je modifikací, která zachovává konvergenci Newtonovy metody a vyhýbá se nestabilitě. Je vyvinut pro řešení složitých polynomů.

Intervalová Newtonova metoda

Kombinace Newtonovy metody s intervalovou aritmetikou je v některých kontextech velmi užitečná. To poskytuje kritérium zastavení, které je spolehlivější než obvyklá (což jsou malá hodnota funkce nebo malá variabilita proměnné mezi po sobě jdoucími iteracemi). Také to může detekovat případy, kdy Newtonova metoda teoreticky konverguje, ale numericky se liší kvůli nedostatečné přesnosti s plovoucí desetinnou čárkou (to je typický případ polynomů velkého stupně, kde velmi malá změna proměnné může dramaticky změnit hodnotu funkce ; viz Wilkinsonův polynom ).

Zvážit , kde je skutečný interval, a předpokládejme, že máme interval prodloužení o , což znamená, že bere jako vstup interval a předává interval tak, že: ${\ displaystyle f \ v {\ mathcal {C}}^{1} (X)}$${\ displaystyle X}$${\ displaystyle F '}$${\ displaystyle f '}$${\ displaystyle F '}$${\ Displaystyle Y \ subseteq X}$${\ displaystyle F '(Y)}$

${\ Displaystyle {\ begin {aligned} F '([y, y]) & = \ {f' (y) \} \\ [5pt] F '(Y) & \ supseteq \ {f' (y) \ střední y \ v Y \}. \ end {aligned}}}$

Předpokládáme to také , takže zejména má nejvýše jeden root in . Poté definujeme interval Newtonova operátoru: ${\ Displaystyle 0 \ notin F '(X)}$${\ displaystyle f}$${\ displaystyle X}$

${\ Displaystyle N (Y) = m-{\ frac {f (m)} {F '(Y)}} = \ left \ {\ left.m-{\ frac {f (m)} {z}} ~ \ right | ~ z \ in F '(Y) \ right \}}$

kde . Všimněte si, že hypotéza o znamená, že je dobře definovaná a je to interval ( další podrobnosti o intervalových operacích viz aritmetika intervalu). To přirozeně vede k následující sekvenci: ${\ Displaystyle m \ v Y}$${\ displaystyle F '}$${\ displaystyle N (Y)}$

${\ displaystyle {\ begin {aligned} X_ {0} & = X \\ X_ {k+1} & = N (X_ {k}) \ cap X_ {k}. \ end {aligned}}}$

Tyto střední hodnoty teorém , zajišťuje, že v případě, že je kořenem v , pak je také . Navíc hypotéza o zajišťuje, že je to nejvýše poloviční velikost, než kdy je střed , takže se tato posloupnost sbíhá směrem , kde je kořen in . ${\ displaystyle f}$${\ displaystyle X_ {k}}$${\ displaystyle X_ {k+1}}$${\ displaystyle F '}$${\ displaystyle X_ {k+1}}$${\ displaystyle X_ {k}}$${\ displaystyle m}$${\ displaystyle Y}$${\ Displaystyle [x^{*}, x^{*}]}$${\ displaystyle x^{*}}$${\ displaystyle f}$${\ displaystyle X}$

Pokud to striktně obsahuje , použití dělení s prodlouženým intervalem vytvoří spojení dvou intervalů pro  ; více kořenů je proto automaticky odděleno a ohraničeno. ${\ displaystyle F '(X)}$${\ displaystyle 0}$${\ displaystyle N (X)}$

Aplikace

Minimalizace a maximalizace problémů

Newtonovu metodu lze použít k nalezení minima nebo maxima funkce . Derivát je nula na minimu nebo maximu, takže lokální minima a maxima lze nalézt aplikací Newtonovy metody na derivát. Iterace se stává: ${\ displaystyle f (x)}$

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

Multiplikativní inverze čísel a mocninných řad

Důležitou aplikací je rozdělení Newton – Raphson , které lze použít k rychlému nalezení převráceného čísla a , pouze pomocí násobení a odčítání, tedy čísla x takového, že1/X= a . Můžeme to přeformulovat jako nalezení nuly f ( x ) =1/X- a . Máme f '( x ) = -1/x ².

Newtonova iterace je

${\ Displaystyle x_ {n+1} = x_ {n}-{\ frac {f (x_ {n})} {f '(x_ {n})}} = x_ {n}+{\ frac {{\ frac {1} {x_ {n}}}-a} {\ frac {1} {x_ {n}^{2}}}} = x_ {n} (2-ax_ {n}).}$

Newtonova iterace proto potřebuje pouze dvě násobení a jedno odečtení.

Tato metoda je také velmi účinná pro výpočet multiplikativní inverze výkonové řady .

Řešení transcendentálních rovnic

Mnoho transcendentálních rovnic lze vyřešit pomocí Newtonovy metody. Vzhledem k rovnici

${\ Displaystyle g (x) = h (x),}$

s g ( x ), a / nebo h ( x ) a transcendentní funkce , jeden píše

${\ Displaystyle f (x) = g (x) -h (x).}$

Hodnoty x, které řeší původní rovnici, jsou potom kořeny f  ( x ) , které lze zjistit Newtonovou metodou.

Získání nuly speciálních funkcí

Newtonova metoda se aplikuje na poměr Besselových funkcí, aby se získal její kořen.

Numerické ověření řešení nelineárních rovnic

Numerické ověření pro řešení nelineárních rovnic bylo stanoveno použitím Newtonovy metody vícekrát a vytvořením sady kandidátů řešení.

CFD modelování

K zavedení stabilní Dirichletovy okrajové podmínky v CFD byl použit iterativní Newton-Raphsonův postup jako celkem obecná strategie modelování distribuce proudu a potenciálu pro elektrochemické komíny.

Příklady

Odmocnina

Zvažte problém nalezení odmocniny čísla a , tj. Kladného čísla x takového, že x ² = a . Newtonova metoda je jednou z mnoha metod výpočtu odmocnin . Můžeme to přeformulovat jako nalezení nuly f ( x ) = x ² - a . Máme f '( x ) = 2 x .

Například pro nalezení odmocniny 612 s počátečním odhadem x ₀ = 10 je posloupnost daná Newtonovou metodou:

${\ displaystyle {\ begin {matrix} x_ {1} & = & x_ {0}-{\ dfrac {f (x_ {0})} {f '(x_ {0})}} & = & 10-{\ dfrac {10^{2} -612} {2 \ times 10}} & = & 35,6 \ qquad \ qquad \ qquad \ quad \; \, {} \\ x_ {2} & = & x_ {1}-{\ dfrac {f (x_ {1})} {f '(x_ {1})}} & = & 35,6-{\ dfrac {35,6^{2} -612} {2 \ times 35,6}} & = & { \ podtržení {2}} 6,395 \, 505 \, 617 \, 978 \ bodů \\ x_ {3} & = & \ vdots & = & \ vdots & = & {\ podtržení {24,7}} 90 \, 635 \, 492 \, 455 \ dots \\ x_ {4} & = & \ vdots & = & \ vdots & = & {\ podtržení {24.738 \, 6}} 88 \, 294 \, 075 \ dots \\ x_ {5} & = & \ vdots & = & \ vdots & = & {\ podtrhnout {24.738 \, 633 \, 753 \, 7}} 67 \ dots \ end {matrix}}}$

kde jsou podtrženy správné číslice. Pouze s několika iteracemi lze získat řešení přesné na mnoho desetinných míst.

Přeskupením vzorce následujícím způsobem získáte babylonskou metodu hledání odmocnin :

${\ displaystyle x_ {n+1} = x_ {n}-{\ frac {f (x_ {n})} {f '(x_ {n})}} = x_ {n}-{\ frac {x_ { n}^{2} -a} {2x_ {n}}} = {\ frac {1} {2}} {\ biggl (} 2x_ {n}-{\ Bigl (} x_ {n}-{\ frac {a} {x_ {n}}} {\ Bigr)} {\ biggr)} = {\ frac {1} {2}} {\ Bigl (} x_ {n}+{\ frac {a} {x_ { n}}} {\ Bigr)}}$

tj. aritmetický průměr odhadu, x _n aA/x _n.

Řešení cos ( x ) = x ³

Zvažte problém nalezení kladného čísla x s cos ( x ) = x ³ . Můžeme to přeformulovat jako nalezení nuly f ( x ) = cos ( x ) - x ³ . Máme f ′ ( x ) = −sin ( x ) - 3 x ² . Protože cos ( x ) ≤ 1 pro všechna x a x ³ > 1 pro x > 1 , víme, že naše řešení leží mezi 0 a 1.

Například s počátečním odhadem x ₀ = 0,5 je posloupnost daná Newtonovou metodou (všimněte si, že počáteční hodnota 0 povede k nedefinovanému výsledku, což ukazuje důležitost použití počátečního bodu, který je blízko řešení):

${\ displaystyle {\ begin {matrix} x_ {1} & = & x_ {0}-{\ dfrac {f (x_ {0})} {f '(x_ {0})}} & = & 0,5- { \ dfrac {\ cos 0,5-0,5^{3}} {-\ sin 0,5-3 \ times 0,5^{2}}} & = & 1,112 \, 141 \, 637 \, 097 \ dots \\ x_ {2 } & = & x_ {1}-{\ dfrac {f (x_ {1})} {f '(x_ {1})}} & = & \ vdots & = & {\ podtržení {0.}} 909 \, 672 \, 693 \, 736 \ bodů \\ x_ {3} & = & \ vdots & = & \ vdots & = & {\ podtržení {0,86}} 7 \, 263 \, 818 \, 209 \ bodů \\ x_ {4} & = & \ vdots & = & \ vdots & = & {\ podtržení {0,865 \, 47}} 7 \, 135 \, 298 \ dots \\ x_ {5} & = & \ vdots & = & \ vdots & = & {\ podtržení {0,865 \, 474 \, 033 \, 1}} 11 \ teček \\ x_ {6} & = & \ vdots & = & \ vdots & = & {\ podtržení {0,865 \, 474 \, 033 \, 102}} \ tečky \ end {matrix}}}$

Správné číslice jsou ve výše uvedeném příkladu podtrženy. Zejména x ₆ je správné na 12 desetinných míst. Vidíme, že počet správných číslic za desetinnou čárkou se zvyšuje z 2 (pro x ₃ ) na 5 a 10, což ilustruje kvadratickou konvergenci.

Kód

Následuje příklad implementace Newtonovy metody v programovacím jazyce Julia pro nalezení kořene funkce, fkterá má derivát fprime.

Počáteční odhad bude x ₀ = 1 a funkce bude f ( x ) = x ² - 2, takže f ′ ( x ) = 2 x .

Každá nová iterace Newtonovy metody bude označena x1. Během výpočtu zkontrolujeme, zda se jmenovatel ( yprime) stane příliš malým (menším než epsilon), což by byl případ, kdyby f ′ ( x _n ) ≈ 0 , protože jinak by bylo možné zavést velké množství chyb.

x0            = 1         # The initial guess
f(x)          = x^2 - 2   # The function whose root we are trying to find
fprime(x)     = 2x        # The derivative of the function
tolerance     = 1e-7      # 7 digit accuracy is desired
epsilon       = 1e-14     # Do not divide by a number smaller than this
maxIterations = 20        # Do not allow the iterations to continue indefinitely
solutionFound = false     # Have not converged to a solution yet

for i = 1:maxIterations
  y      = f(x0)
  yprime = fprime(x0)

  if abs(yprime) < epsilon            # Stop if the denominator is too small
    break
  end

  global x1 = x0 - y/yprime           # Do Newton's computation

  if abs(x1 - x0) <= tolerance        # Stop when the result is within the desired tolerance
    global solutionFound = true
    break
  end

  global x0 = x1                      # Update x0 to start the process again
end

if solutionFound
  println("Solution: ", x1)           # x1 is a solution within tolerance and maximum number of iterations
else
  println("Did not converge")         # Newton's method did not converge
end

Viz také

Poznámky

Reference

• Gil, A .; Segura, J .; Temme, NM (2007). Numerické metody pro speciální funkce . Společnost pro průmyslovou a aplikovanou matematiku. ISBN 978-0-89871-634-4.
• Süli, Endre ; Mayers, David (2003). Úvod do numerické analýzy . Cambridge University Press. ISBN 0-521-00794-1.

Další čtení

• Kendall E. Atkinson, An Introduction to Numerical Analysis , (1989) John Wiley & Sons, Inc, ISBN  0-471-62489-6
• Tjalling J. Ypma, Historický vývoj metody Newton – Raphson, SIAM Review 37 (4), 531–551, 1995. doi : 10,1137/1037125 .
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Numerická optimalizace: Teoretické a praktické aspekty . Universitext (druhé přepracované vydání překladu francouzského vydání z roku 1997). Berlín: Springer-Verlag. s. xiv+490. doi : 10,1007/978-3-540-35447-5 . ISBN 3-540-35445-X. MR  2265882 .
• P. Deuflhard, Newtonovy metody pro nelineární problémy. Afinní invariance a adaptivní algoritmy. Springer Series in Computational Mathematics, sv. 35. Springer, Berlin, 2004. ISBN  3-540-21099-7 .
• CT Kelley, Řešení nelineárních rovnic Newtonovou metodou , č. 1 v Fundamentals of Algorithms, SIAM, 2003. ISBN  0-89871-546-6 .
• JM Ortega, WC Rheinboldt, Iterační řešení nelineárních rovnic v několika proměnných. Classics in Applied Mathematics, SIAM, 2000. ISBN  0-89871-461-3 .
• Stiskněte, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). „Kapitola 9. Vyhledávání kořenů a nelineární sady rovnic Vzorkování důležitosti“ . Numerical Recipes: The Art of Scientific Computing (3. vyd.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.. Viz zejména oddíly 9.4 , 9.6 a 9.7 .
• Avriel, Mordecai (1976). Nelineární programování: Analýza a metody . Sál Prentice. s. 216–221. ISBN 0-13-623603-0.

externí odkazy

• „Newtonova metoda“ , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Weisstein, Eric W. „Newtonova metoda“ . MathWorld .
• Newtonova metoda, Citizendium.
• Mathews, J., The Accelerated and Modified Newton Methods, Course notes.
• Wu, X., Kořeny rovnic, Poznámky k kurzu.