6 Newton-Raphson Metodu
İkiye Bölme Metodu her durumda yakınsar ama yavaştır; Sabit Nokta İterasyonu ise iyi bir \(g\) seçimine bağlıdır. Newton-Raphson Metodu (kısaca Newton metodu), fonksiyonun türevini de kullanarak kök bulma problemleri için bilinen en etkili yöntemlerden biri olur: köke yeterince yakın bir başlangıçtan sonra her adımda doğru basamak sayısı hızla artar.
Newton yöntemini 1669’da yazdı, ama çalışma ancak 1711’de basıldı; Joseph Raphson 1690’da daha sade bir biçimini yayımladı. Bugün kullandığımız türevli yazım Thomas Simpson’a (1740) dayanır.
6.1 Taylor polinomundan türetme
Yöntem, \(f\) fonksiyonunu başlangıç yaklaşımı civarında birinci dereceden Taylor polinomuyla değiştirmekten doğar.
\(f \in C^2[a, b]\) olsun ve \(p\) kökü için \(p_0 \in [a, b]\) öyle bir başlangıç yaklaşımı olsun ki \(f'(p_0) \neq 0\) ve \(|p - p_0|\) yeterince küçük olsun. Taylor Teoremine (Teorem 1.9) göre her \(x \in [a, b]\) için \(x\) ile \(p_0\) arasında bir \(\xi(x)\) sayısı vardır ve
\[ f(x) = f(p_0) + (x - p_0) f'(p_0) + \frac{(x - p_0)^2}{2} f''(\xi(x)) \]
yazılabilir. Burada \(x = p\) alalım. \(f(p) = 0\) olduğundan, \(p\) ile \(p_0\) arasındaki \(\xi(p)\) için
\[ 0 = f(p_0) + (p - p_0) f'(p_0) + \frac{(p - p_0)^2}{2} f''(\xi(p)) \]
elde edilir. \(|p - p_0|\) küçük olduğundan \((p - p_0)^2\) çok daha küçüktür; son terimi ihmal edersek
\[ 0 \approx f(p_0) + (p - p_0) f'(p_0) \quad\Longrightarrow\quad p \approx p_0 - \frac{f(p_0)}{f'(p_0)} \]
bulunur (son adımda \(f'(p_0) \neq 0\) ile bölündü). Sağdaki sayıyı \(p_1\) diye adlandırıp aynı işlemi \(p_1\)’den başlayarak tekrarlarsak \(p_2\), sonra \(p_3\), … elde edilir.
Tanım 6.1 (Newton-Raphson Metodu) \(f \in C^2[a, b]\) ve \(p_0 \in [a, b]\) verilsin.
\[ p_n = p_{n-1} - \frac{f(p_{n-1})}{f'(p_{n-1})}, \qquad n \geq 1 \tag{1} \]
indirgeme bağıntısıyla \((p_n)_{n=0}^{\infty}\) dizisini üreten yönteme Newton-Raphson Metodu, \(p_0\) sayısına da başlangıç yaklaşımı denir. Her adımda \(f'(p_{n-1}) \neq 0\) olması gerekir.
Yani her adımda \(f\) yerine onun \(p_{n-1}\)’deki doğrusal yaklaşımı konur ve bu doğrunun kökü bir sonraki yaklaşım olarak alınır.
Bu doğrusal yaklaşım, \(f\)’nin grafiğine \((p_{n-1}, f(p_{n-1}))\) noktasında çizilen teğettir:
\[ y = f(p_{n-1}) + f'(p_{n-1})\,(x - p_{n-1}). \]
\(y = 0\) konursa \(x = p_n\) çıkar. Demek ki \(p_n\), grafiğe \((p_{n-1}, f(p_{n-1}))\) noktasında çizilen teğetin \(x\) eksenini kestiği noktadır. Aşağıdaki şekil ilk iki adımı gösteriyor; somut bir denklemdeki teğetler Örnek 6.1 çözümündedir.
İterasyon, İkiye Bölme Metodu bölümündeki durma kriterlerinden biriyle durdurulur; bu bölümde çoğunlukla verilen bir \(\varepsilon > 0\) için
\[ |p_n - p_{n-1}| < \varepsilon \tag{2} \]
kriteri kullanılır.
6.2 Yakınsama
Newton-Raphson Metodu, \(g(x) = x - f(x)/f'(x)\) fonksiyonuyla yapılan bir sabit nokta iterasyonudur. Bu gözlem, yakınsamayı Sabit Nokta Teoreminden elde etmemizi sağlar.
Teorem 6.1 (Newton-Raphson Metodunun yakınsaması) \(f \in C^2[a, b]\) olsun. Bir \(p \in (a, b)\) için \(f(p) = 0\) ve \(f'(p) \neq 0\) ise öyle bir \(\delta > 0\) vardır ki her \(p_0 \in [p - \delta, p + \delta]\) başlangıç yaklaşımı için (1) ile üretilen \((p_n)_{n=0}^{\infty}\) dizisi \(p\) köküne yakınsar.
İspat
\(g(x) = x - \dfrac{f(x)}{f'(x)}\) diyelim. O zaman (1) bağıntısı \(p_n = g(p_{n-1})\), \(n \geq 1\) fonksiyonel iterasyonudur ve \(f(p) = 0\) olduğundan \(g(p) = p\) sağlanır. \(0 < k < 1\) sabitlensin. Amacımız
- \(g([p - \delta, p + \delta]) \subseteq [p - \delta, p + \delta]\) ve
- her \(x \in (p - \delta, p + \delta)\) için \(|g'(x)| \leq k\)
olacak biçimde bir \(\delta > 0\) bulmak; bu durumda Sabit Nokta Teoreminin (Teorem 5.2) koşulları \([p - \delta, p + \delta]\) aralığında sağlanmış olur.
\(g\)’nin tanımlı ve türevlenebilir olduğu bir aralık. \(f'\) sürekli ve \(f'(p) \neq 0\) olduğundan, ayrıca \(p\) iç nokta olduğundan, öyle bir \(\delta_1 > 0\) vardır ki \([p - \delta_1, p + \delta_1] \subseteq [a, b]\) ve bu aralıktaki her \(x\) için \(f'(x) \neq 0\) olur. Böylece \(g\), \([p - \delta_1, p + \delta_1]\) üzerinde tanımlı ve süreklidir. Bölüm kuralıyla bu aralıkta
\[ \begin{aligned} g'(x) &= 1 - \frac{f'(x)\,f'(x) - f(x)\,f''(x)}{[f'(x)]^2} \\[1mm] &= \frac{f(x)\,f''(x)}{[f'(x)]^2} \end{aligned} \]
bulunur. \(f\), \(f'\), \(f''\) sürekli ve payda sıfırdan farklı olduğundan \(g \in C^1[p - \delta_1, p + \delta_1]\) olur.
\(|g'| \leq k\) olan daha küçük bir aralık. \(f(p) = 0\) olduğundan
\[ g'(p) = \frac{f(p)\,f''(p)}{[f'(p)]^2} = 0 \]
dır. \(g'\) fonksiyonu \(p\) noktasında sürekli olduğundan öyle bir \(0 < \delta < \delta_1\) vardır ki her \(x \in [p - \delta, p + \delta]\) için \(|g'(x)| \leq k\) olur.
\(g\) aralığı kendi içine gönderir. \(x \in [p - \delta, p + \delta]\) alalım. \(x = p\) ise \(g(x) = p\) aralıktadır. \(x \neq p\) ise Ortalama Değer Teoremine (Teorem 1.4) göre \(x\) ile \(p\) arasında bir \(\xi\) vardır ve \(|g(x) - g(p)| = |g'(\xi)|\,|x - p|\) olur. \(\xi\) de \([p - \delta, p + \delta]\) içinde olduğundan \(|g'(\xi)| \leq k\) dır; dolayısıyla
\[ |g(x) - p| = |g(x) - g(p)| = |g'(\xi)|\,|x - p| \leq k\,|x - p| \leq k\delta < \delta \]
ve \(g(x) \in [p - \delta, p + \delta]\) elde edilir.
Sonuç. \(g\), \([p - \delta, p + \delta]\) üzerinde Sabit Nokta Teoreminin bütün koşullarını sağlar. Bu aralıktaki tek sabit nokta \(p\) olduğundan, her \(p_0 \in [p - \delta, p + \delta]\) için
\[ p_n = g(p_{n-1}) = p_{n-1} - \frac{f(p_{n-1})}{f'(p_{n-1})}, \qquad n \geq 1 \]
dizisi \(p\)’ye yakınsar. \(\blacksquare\)
Yani \(f'(p) \neq 0\) olan basit bir kökte, \(p_0\) köke yeterince yakın seçilirse Newton-Raphson Metodu yakınsar. Teorem yalnız böyle bir \(\delta\)’nın var olduğunu söyler, büyüklüğünü vermez; bu yüzden uygulamada önce kökü içeren dar bir aralık belirlenir ve \(p_0\) bu aralıktan seçilir.
\(f'(p_{n-1})\) küçükse teğet neredeyse yataydır ve \(x\) eksenini çok uzakta keser. \(f(x) = x^3 + 3x^2 - 1\) için \(f'(x) = 3x(x + 2)\) türevi \(x = -2\) ve \(x = 0\)’da sıfırdır. \([-3; -2]\) aralığındaki kökü ararken \(p_0 = -1{,}8\) seçilirse \(f(p_0) = 2{,}888\), \(f'(p_0) = -1{,}08\) ve \(p_1 = 0{,}87407\) olur; dizi bundan sonra aranan kök yerine \(0{,}53209\) köküne yakınsar. \(p_0 = -2{,}5\) seçilince de \(p_1 = -3{,}06667\) aralığın dışına düşer, ama dizi geri dönüp aranan köke yakınsar (Alıştırma 6.2).
6.3 Yöntemin uygulanması
Yöntemi bir tabloyla yürütmek, hem hesabı düzenli tutar hem de durma kriterini her satırda okumayı sağlar.
- \(f\) ve \(f'\) fonksiyonlarını yaz; kökü içeren bir \([a, b]\) aralığı belirle (uç noktalarda işaret değişimi) ve \(f \in C^2[a, b]\) olduğunu gör.
- Bu aralıktan bir \(p_0\) seç; \(f'(p_0) \neq 0\) olduğunu, mümkünse aralık boyunca \(f' \neq 0\) olduğunu kontrol et.
- bağıntısını uygula; her satıra \(n\), \(p_n\), \(f(p_n)\), \(f'(p_n)\), \(f(p_n)/f'(p_n)\) ve \(|p_n - p_{n-1}|\) değerlerini yaz. Bir sonraki yaklaşım \(p_{n+1} = p_n - f(p_n)/f'(p_n)\) dir.
- numaralı durma kriteri sağlanınca (ya da istenen \(p_n\)’ye ulaşınca) dur ve \(p \approx p_n\) al.
Örnek 6.1 (cos x − x = 0 denkleminin kökü) \(\cos x - x = 0\) denkleminin \(p\) köküne, \(p_0 = \pi/4\) başlangıç yaklaşımı ve \(|p_n - p_{n-1}| < 10^{-8}\) durma kriteriyle Newton-Raphson Metodu kullanarak bir yaklaşımda bulunun. İşlemleri yuvarlama yapmadan bir tabloda gösterin.
Çözüm
Aralık ve koşullar. \(f(x) = \cos x - x\) olsun. \(f(0) = 1 > 0\) ve \(f(\pi/2) = -\pi/2 < 0\) olduğundan Ara Değer Teoremine (Teorem 1.7) göre \(p \in [0, \pi/2]\) dir. Türev
\[ f'(x) = -\sin x - 1 \]
\([0, \pi/2]\) üzerinde \(-1\) ile \(-2\) arasındadır, yani sıfırdan farklıdır; özellikle \(f'(p) \neq 0\). \(f \in C^2[0, \pi/2]\) olduğundan Teorem 6.1 koşulları sağlanır; dolayısıyla köke yeterince yakın başlangıçlar için yöntem yakınsar. \(p_0 = \pi/4\)’ün bu komşulukta olduğunu tablo gösterir.
İterasyon. \(p_0 = \pi/4 \approx 0{,}785398163\) ve \(n \geq 1\) için
\[ p_n = p_{n-1} - \frac{\cos(p_{n-1}) - p_{n-1}}{-\sin(p_{n-1}) - 1} \]
dir. İlk adımda \(f(p_0) = -0{,}078291382\), \(f'(p_0) = -1{,}707106781\) ve
\[ p_1 = 0{,}785398163 - 0{,}045862030 = 0{,}739536134 \]
bulunur (gösterilen değerler 9 basamağa yuvarlanmıştır). Hesap tam duyarlıkla sürdürülür; tabloda yalnız gösterim 9 ondalık basamağa yuvarlandığı için son basamakta \(1\) birimlik farklar görünebilir. \(10^{-9}\)’dan küçük değerler bilimsel yazımla verilmiştir.
| \(n\) | \(p_n\) | \(f(p_n)\) | \(f'(p_n)\) | \(f(p_n)/f'(p_n)\) | \(\lvert p_n - p_{n-1}\rvert\) |
|---|---|---|---|---|---|
| \(0\) | \(0{,}785398163\) | \(-0{,}078291382\) | \(-1{,}707106781\) | \(0{,}045862030\) | |
| \(1\) | \(0{,}739536134\) | \(-0{,}000754875\) | \(-1{,}673945288\) | \(0{,}000450955\) | \(0{,}045862030\) |
| \(2\) | \(0{,}739085178\) | \(-0{,}000000075\) | \(-1{,}673612062\) | \(0{,}000000045\) | \(0{,}000450955\) |
| \(3\) | \(0{,}739085133\) | \(-0{,}745 \cdot 10^{-15}\) | \(-1{,}673612029\) | \(0{,}445 \cdot 10^{-15}\) | \(0{,}000000045\) |
| \(4\) | \(0{,}739085133\) | \(0{,}445 \cdot 10^{-15}\) |
\(n = 3\) satırında \(|p_3 - p_2| = 0{,}000000045 > 10^{-8}\) olduğundan bir adım daha atılır; \(n = 4\) satırında \(|p_4 - p_3| < 10^{-8}\) olur ve iterasyon durur:
\[ p \approx p_4 = 0{,}739085133. \]
Teğetlerin yaklaşımları nasıl ürettiği aşağıda görülüyor. \(p_0\)’daki teğet \(x\) eksenini \(p_1\)’de keser; \(p_1\)’deki teğet ise \(p_2\)’de keser ve \(p_2\) kökten ancak \(4{,}5 \cdot 10^{-8}\) kadar uzaktadır.
\(|p_n - p_{n-1}|\) sütunu \(10^{-2}\), \(10^{-4}\), \(10^{-8}\), \(10^{-16}\) mertebelerinden geçer: her adımda doğru basamak sayısı kabaca iki katına çıkar. \(\blacksquare\)
6.4 Alıştırmalar
Aşağıdaki alıştırmalarda her adımda virgülden sonra 5. basamağa yuvarlanır ve hesaba yuvarlanmış değerle devam edilir.
Alıştırma 6.1 (x² − 6 = 0 denkleminin pozitif kökü) \(x^2 - 6 = 0\) denkleminin pozitif köküne, Newton-Raphson Metodu ile \(p_0 = 2\) alarak \(p_3\) yaklaşımında bulunun. İşlemlerde virgülden sonra 5. basamağa yuvarlama yaparak bir tablo oluşturun.
Çözüm
Aralık ve koşullar. \(f(x) = x^2 - 6\) olsun. Pozitif kök \(\sqrt{6}\) dır ve \(2 = \sqrt{4} < \sqrt{6} < \sqrt{9} = 3\) olduğundan \([2, 3]\) aralığında çalışırız. \(f \in C^2[2, 3]\) ve \(f'(x) = 2x \geq 4\) olduğundan türev bu aralıkta sıfırdan farklıdır.
İterasyon. \(p_0 = 2{,}00000\) ve \(n \geq 1\) için
\[ p_n = p_{n-1} - \frac{p_{n-1}^2 - 6}{2 p_{n-1}} \]
dir. İlk satırda \(f(2) = -2\), \(f'(2) = 4\), \(f(p_0)/f'(p_0) = -0{,}5\) ve \(p_1 = 2 - (-0{,}5) = 2{,}5\) olur. İkinci satırda \(f(2{,}5) = 0{,}25\), \(f'(2{,}5) = 5\), oran \(0{,}05\) ve \(p_2 = 2{,}45\) bulunur. Üçüncü satırda \(0{,}0025/4{,}9 = 0{,}000510\ldots\) değeri \(0{,}00051\)’e yuvarlanır ve \(p_3 = 2{,}45 - 0{,}00051 = 2{,}44949\) elde edilir.
| \(n\) | \(p_n\) | \(f(p_n)\) | \(f'(p_n)\) | \(f(p_n)/f'(p_n)\) |
|---|---|---|---|---|
| \(0\) | \(2{,}00000\) | \(-2{,}00000\) | \(4{,}00000\) | \(-0{,}50000\) |
| \(1\) | \(2{,}50000\) | \(0{,}25000\) | \(5{,}00000\) | \(0{,}05000\) |
| \(2\) | \(2{,}45000\) | \(0{,}00250\) | \(4{,}90000\) | \(0{,}00051\) |
| \(3\) | \(2{,}44949\) |
Sonuç \(p_3 = 2{,}44949\) dur. \(\sqrt{6} = 2{,}4494897\ldots\) olduğundan \(p_3\) beş basamağa kadar doğrudur.
Bağıntı sadeleştirilirse \(p_n = \frac{1}{2}\left(p_{n-1} + \frac{6}{p_{n-1}}\right)\) olur: Sabit Nokta İterasyonu bölümünde \(\sqrt{3}\) için kullanılan \(g(x) = 0{,}5\left(x + \frac{3}{x}\right)\) fonksiyonu, \(f(x) = x^2 - 3\)’e uygulanan Newton-Raphson Metodundan başka bir şey değildir. \(\blacksquare\)
Alıştırma 6.2 (Kübik denklemin −3 ile −2 arasındaki kökü) \(x^3 + 3x^2 - 1 = 0\) denkleminin \([-3; -2]\) aralığındaki köküne Newton-Raphson Metodu ile \(p_0 = -2{,}5\) alarak \(|p_n - p_{n-1}| < 10^{-4}\) durma kriteriyle bir \(p_n\) yaklaşımında bulunun. Hesapları her adımda virgülden sonra 5. basamağa yuvarlayarak bir tabloda gösterin.
Çözüm
Aralık ve koşullar. \(f(x) = x^3 + 3x^2 - 1\) olsun. \(f(-3) = -1 < 0\) ve \(f(-2) = 3 > 0\) olduğundan Ara Değer Teoremine göre \((-3, -2)\) aralığında bir kök vardır. \(f \in C^2[-3; -2]\) ve
\[ f'(x) = 3x^2 + 6x = 3x(x + 2) \]
türevi \([-3; -2)\) üzerinde sıfırdan farklıdır (yalnız uç nokta \(x = -2\)’de sıfırdır). Kök \(-2\)’den uzakta olduğundan \(f'(p) \neq 0\) dır.
İterasyon. \(p_0 = -2{,}5\) ve \(n \geq 1\) için
\[ p_n = p_{n-1} - \frac{p_{n-1}^3 + 3p_{n-1}^2 - 1}{3p_{n-1}^2 + 6p_{n-1}} \]
dir. İlk satırın hesabı şöyledir:
\[ \begin{aligned} f(-2{,}5) &= -15{,}625 + 18{,}75 - 1 = 2{,}125, \\[1mm] f'(-2{,}5) &= 18{,}75 - 15 = 3{,}75, \\[1mm] \frac{f(p_0)}{f'(p_0)} &= \frac{2{,}125}{3{,}75} = 0{,}566666\ldots \approx 0{,}56667, \\[1mm] p_1 &= -2{,}5 - 0{,}56667 = -3{,}06667. \end{aligned} \]
\(p_1\) aralığın biraz dışına düşer, ama sonraki adımlar köke geri döner.
| \(n\) | \(p_n\) | \(f(p_n)\) | \(f'(p_n)\) | \(f(p_n)/f'(p_n)\) | \(\lvert p_n - p_{n-1}\rvert\) |
|---|---|---|---|---|---|
| \(0\) | \(-2{,}50000\) | \(2{,}12500\) | \(3{,}75000\) | \(0{,}56667\) | |
| \(1\) | \(-3{,}06667\) | \(-1{,}62700\) | \(9{,}81337\) | \(-0{,}16579\) | \(0{,}56667\) |
| \(2\) | \(-2{,}90088\) | \(-0{,}16589\) | \(7{,}84003\) | \(-0{,}02116\) | \(0{,}16579\) |
| \(3\) | \(-2{,}87972\) | \(-0{,}00254\) | \(7{,}60004\) | \(-0{,}00033\) | \(0{,}02116\) |
| \(4\) | \(-2{,}87939\) | \(-0{,}00004\) | \(7{,}59632\) | \(-0{,}00001\) | \(0{,}00033\) |
| \(5\) | \(-2{,}87938\) | \(0{,}00001\) |
\(|p_4 - p_3| = 0{,}00033\) henüz \(10^{-4}\)’ten büyüktür; \(|p_5 - p_4| = 0{,}00001 < 10^{-4}\) olduğundan iterasyon durur:
\[ p \approx p_5 = -2{,}87938. \]
Gerçek kök \(p = -2{,}8793852\ldots\) olduğundan \(|p_5 - p| \approx 0{,}52 \cdot 10^{-5}\) tir. Beş basamaklı yuvarlamayla yaklaşımlar artık \(-2{,}87939\) ile \(-2{,}87938\) arasında gidip gelir; bu duyarlıkla daha iyisi elde edilemez. \(\blacksquare\)
Newton-Raphson Metodu her adımda \(f'\) türevini hesaplamayı gerektirir. Türev yerine iki yaklaşımdan geçen kesenin eğimini kullanan yöntemler bir sonraki bölümün konusu: Secant ve Regula Falsi Metodları.