Newton yöntemi

Newton yöntemi, $f(r) = 0$ koşulunu sağlayan bir r sayısına, yani f fonksiyonunun bir köküne, aynı adımı tekrarlayarak yaklaşır. Şimdiki tahmin $x_n$ iken grafiğin $(x_n, f(x_n))$ noktasındaki teğetini alın; bu teğet $L(x) = f(x_n) + f'(x_n)(x - x_n)$ ile verilir. $x_n$ yakınında teğet eğriye yakın kalır; dolayısıyla x eksenini kestiği yer, eğrinin kesişimi için daha iyi bir tahmindir. $L(x) = 0$ denklemini çözmek sonraki tahmini verir. Grafikte her adım, $x_n$ noktasından eğriye soluk kesikli çizgi boyunca, sonra da teğet boyunca eksene gider.

Hatayı $e_n = x_n - r$ ile gösterelim. r basit bir kökse ($f'(r) \ne 0$) ve f sürekli ikinci türeve sahipse, adımın Taylor açılımı $x_n$ değeri r’ye yaklaştığında $e_{n+1} \approx \frac{f''(r)}{2f'(r)}\,e_n^2$ sonucunu verir. Hatanın karesini almak doğru basamak sayısını yaklaşık ikiye katlar. x² − 2 için x₀ = 1’den hatalar 0.086, 0.0025, 2.1 × 10⁻⁶ ve 1.6 × 10⁻¹² olur; gösterge, $e_n/e_{n-1}^2$ değerinin $1/(2\sqrt2) \approx 0.354$ yakınına yerleştiğini gösterir. Kökten uzakta böyle bir güvence yoktur. $f''(r) = 0$ olduğunda karesel terim kaybolur ve yöntem daha da hızlanır: arctan x için hata yaklaşık $-\tfrac23 e_n^3$ olur, her adımda küp alınır.

Adım için $f'(x_n) \ne 0$ gerekir. Yatay teğet eksenle hiç buluşmaz, neredeyse yatay teğet ise çok uzakta buluşur: x² − 2 için 0.1’den ilk adım 10.05’e gider. Yöntem uzaklaşmadan da başarısız olabilir. x³ − 2x + 2 için 0’daki teğet 1’e, 1’deki teğet 0’a gider; 0’a yakın başlangıçlar da bu döngüye çekilir. Dizi sınırlı kalır, fakat limiti yoktur. arctan x için α ≈ 1.3917 sınırı vardır; bu sayı $2\alpha = (1 + \alpha^2)\arctan\alpha$ koşulunu sağlar. |x₀| < α olan başlangıçlar yakınsar, sınırın ötesindekiler her seferinde karşı tarafta daha uzağa gider. «Her başlangıç» seçeneği x eksenini her başlangıcın ulaştığı sonuca göre renklendirir. x³ − 2x + 2 için [−3, 3] aralığının yaklaşık beşte biri döngüye girer; buna $\pm\sqrt{2/3}$ yatay teğet noktalarına doğru sıklaşan dar şeritler de dahildir. Karmaşık sayılardan başlamak bu şeritleri Newton fraktalına dönüştürür.

Katlı bir kökte $f'(r) = 0$ da geçerlidir ve karesel yakınsama kaybolur. $(x - 1)^2$ için adım tam olarak $x_{n+1} = (x_n + 1)/2$ olduğundan hata her adımda yarıya iner. Bu doğrusal yakınsamadır: her yeni ondalık basamak için yaklaşık 3.3 adım. Katı m olan bir kökün yakınında $e_{n+1}/e_n$ oranı $(m - 1)/m$ değerine yaklaşır.