Newtonova metóda (Newton‑Raphson): ako nájsť nuly funkcie
Newtonova metóda (Newton‑Raphson): rýchle nájdenie reálnych núl funkcií pomocou derivácií a iterácií. Praktický návod, vzorce a vizuálne vysvetlenie krok za krokom.
Newtonova metóda umožňuje nájsť reálne nuly funkcie. Tento algoritmus sa niekedy nazýva Newtonova-Raphsonova metóda, pomenovaná podľa sira Isaaca Newtona a Josepha Raphsona.
Metóda využíva deriváciu funkcie na nájdenie jej koreňov. Je potrebné odhadnúť počiatočnú pozičnú hodnotu nuly (tzv. počiatočný odhad). Z tejto hodnoty sa vypočíta nový odhad podľa tohto vzorca:
x n + 1 = x n - f ( x n ) f ′ ( x n ) {\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}} 
Tu xn je aktuálny odhad a xn+1 je ďalší odhad. Funkcia f (ktorej nula sa rieši) má deriváciu f'.
Základný princíp
Opakovaným použitím tohto vzorca na vygenerované odhady (t. j. nastavením hodnoty xn na výstup vzorca a opätovným výpočtom) sa hodnota odhadov často rýchlo priblíži k reálnej nule funkcie. Geometricky sa to dá vysvetliť pomocou priesečníkov dotyčnice s osou x: v bode xn sa sestrojí dotyčnica grafu funkcie, nájde sa jej priesečník s osou x a jeho x-ová súradnica je xn+1.
Algoritmus (krok za krokom)
- Zvoľte počiatočný odhad x0.
- Opakujte krok: xn+1 = xn − f(xn)/f'(xn).
- Skontrolujte kritérium zastavenia, napr. |f(xn+1)| < tol alebo |xn+1 − xn| < tol alebo dosiahnutie maximálneho počtu iterácií.
Podmienky konvergencie a vlastnosti
- Lokálna kvadratická konvergencia: Ak je koreň r jednoduchý (t.j. f(r) = 0 a f'(r) ≠ 0) a počiatočný odhad je dostatočne blízko k r, Newtonova metóda konverguje kvadraticky — počet správnych číslic sa približne zdvojnásobí pri každej iterácii.
- Citlivosť na počiatočný odhad: Ak je počiatočný odhad príliš vzdialený, metóda nemusí konvergovať alebo sa môže dostať k inému koreňu. Oblasť bodov, z ktorých sa metóda konverguje k danému koreňu, sa nazýva basin of attraction a môže byť zložitá.
- Problém s nulovou deriváciou: Ak pre nejaké xn platí f'(xn) = 0 (alebo je veľmi malá), iterácia nie je definovaná alebo môže viesť k veľkým krokom a nestabilite.
- Opakované koreňe: Ak koreň má násobnosť m > 1, konvergencia je len lineárna (pomalšia). Existuje modifikovaná Newtonova metóda: xn+1 = xn − m·f(xn)/f'(xn) na zlepšenie rýchlosti, ak je m známa.
Praktické úpravy a alternatívy
- Damping (preriedenie) kroku: Použitie parametra 0 < λ ≤ 1 a náhrada kroku xn+1 = xn − λ·f(xn)/f'(xn) pomáha predísť preskočeniu a zlepšiť globálnu stabilitu.
- Secant metóda: Ak nie je k dispozícii derivácia, secant metóda aproximuje deriváciu a vyžaduje len hodnoty f; má superlineárnu (ale nie kvadratickú) konvergenciu.
- Hybridné metódy: Kombinácie bisekcie (garantovaná konvergencia) a Newtona (rýchlosť) sú bežné v knižniciach numerických metód.
- Kontrola krokov a obmedzenia: V praxi sa zväčša kontroluje veľkosť kroku a ak je príliš veľký, zmenší sa alebo zvolí alternatívna stratégia.
Kritériá zastavenia
- |f(xn)| < tolerance — zodpovednosť funkcie blízko nule.
- |xn+1 − xn| < tolerance — zmena medzi iteráciami je malá.
- Dosiahnutie maximálneho počtu iterácií — bezpečnostné opatrenie.
Príklad
Riešime f(x) = x² − 2 (hľadáme sqrt(2)). Zvoľme x0 = 1.
- f'(x) = 2x
- x1 = 1 − (1² − 2)/(2·1) = 1.5
- x2 = 1.5 − (1.5² − 2)/(2·1.5) ≈ 1.4166667
- x3 ≈ 1.4142157, atď. — približne po niekoľkých iteráciách získame hodnotu 1.41421356…
Výhody a nevýhody
- Výhody: veľmi rýchla lokálna konvergencia (kvadratická), jednoduchá implementácia ak je k dispozícii derivácia.
- Nevýhody: potreba derivácie, citlivosť na počiatočný odhad, problémy pri nulových alebo malých deriváciách, menej spoľahlivá bez doplnkových opatrení.
Newtonova metóda je v numerickom výpočte veľmi užitočná vďaka svojej rýchlosti pri dobrom počiatočnom odhade, avšak pri praktickej implementácii je dôležité doplniť ju o kontrolné mechanizmy (damping, overenie derivácie, heuristiky pre zmenu stratégie), aby bola robustná aj pre náročnejšie prípady.
Funkcia (modrá) sa používa na výpočet sklonu dotyčnice (červená) v bode xn.
Problémy s Newtonovou metódou
Newtonova metóda dokáže nájsť riešenie rýchlo, ak odhadovaná hodnota začína dostatočne blízko požadovaného koreňa. Ak však počiatočná odhadovaná hodnota nie je blízko a v závislosti od funkcie, Newtonova metóda môže nájsť riešenie pomaly alebo vôbec.
Ďalšie čítanie
- Fernández, J. A. E., & Verón, M. Á. H. (2017). Newtonova metóda: Aktualizovaný prístup ku Kantorovichovej teórii. Birkhäuser.
- Peter Deuflhard, Newtonove metódy pre nelineárne problémy. Affine Invariance and Adaptive Algorithms, druhé tlačené vydanie. Séria Computational Mathematics 35, Springer (2006)
- Yamamoto, T. (2001). "Historický vývoj v analýze konvergencie Newtonových a Newtonových metód". In Brezinski, C.; Wuytack, L. (eds.). Numerical Analysis : Historical Developments in the 20th Century (Numerická analýza : historický vývoj v 20. storočí). North-Holland. s. 241-263.
Pozri tiež
- Kantorovičova veta (tvrdenie o konvergencii Newtonovej metódy, ktoré objavil Leonid Kantorovič)
| Kontrola úradu |
|
Otázky a odpovede
Otázka: Čo je Newtonova metóda?
Odpoveď: Newtonova metóda je algoritmus na hľadanie reálnych núl funkcie. Na výpočet koreňov funkcie používa deriváciu funkcie a vyžaduje počiatočnú odhadovanú hodnotu polohy nuly.
Otázka: Kto vytvoril túto metódu?
Odpoveď: Metódu vyvinuli sir Isaac Newton a Joseph Raphson, preto sa niekedy nazýva Newtonova-Raphsonova metóda.
Otázka: Ako tento algoritmus funguje?
Odpoveď: Tento algoritmus funguje tak, že sa opakovane použije vzorec, ktorý prijíma počiatočnú odhadovanú hodnotu (xn) a vypočíta nový odhad (xn+1). Opakovaním tohto procesu sa odhad priblíži k nule funkcie.
Otázka: Čo je potrebné na použitie tohto algoritmu?
Odpoveď: Na použitie tohto algoritmu musíte mať počiatočnú "odhadovanú hodnotu" polohy nuly, ako aj vedomosti o derivácii danej funkcie.
Otázka: Ako môžeme Newtonovu metódu vysvetliť graficky?
Odpoveď: Newtonovu metódu môžeme graficky vysvetliť tak, že sa pozrieme na priesečníky dotyčnice s osou x. Najprv sa vypočíta priamka dotyčnice k f v bode xn. Potom nájdeme priesečník tejto dotyčnice s osou x a jeho polohu x zapíšeme ako náš ďalší odhad - xn+1.
Otázka: Existuje nejaké obmedzenie pri použití Newtonovej metódy?
Odpoveď: Áno, ak je vaša počiatočná odhadovaná hodnota príliš vzdialená od skutočného koreňa, potom môže trvať dlhšie alebo sa dokonca nepodarí konvergovať ku koreňu v dôsledku oscilácií okolo neho alebo divergencie od neho.
Prehľadať