5 Sabit Nokta İterasyonu
İkiye Bölme Metodu her adımda kökü içeren aralığı yarıya indirir ve \(|p_n - p| \le (b - a)/2^n\) güvencesini verir (Teorem 4.1). Bu güvence sağlamdır ama yavaştır: yöntem fonksiyonun yalnız işaretine bakar, değerlerinin ne kadar büyük ya da küçük olduğunu hiç kullanmaz. Bu bölümde kök bulma problemine başka bir açıdan bakıyoruz. \(f(x) = 0\) denklemini \(x = g(x)\) biçimine getirir, bir \(p_0\) başlangıç değerinden \(p_1 = g(p_0)\), \(p_2 = g(p_1)\), … dizisini kurarız. Dizi yakınsarsa limiti \(g\)’nin bir sabit noktası, dolayısıyla \(f\)’nin bir köküdür.
Böyle bir dizinin hangi koşulda yakınsadığını genel biçimde Stefan Banach 1922’de büzülme dönüşümleri için ispatladı. Biz aynı sonucu bir aralık üzerinde, türev ve Ortalama Değer Teoremi yardımıyla kuracağız. Bu yöntemin bir sonraki bölümdeki Newton-Raphson Metodu’nun da temeli olduğunu göreceğiz.
5.1 Sabit Nokta ve Kök Bulma Problemi
Önce sabit noktayı tanımlayıp kök bulma problemine nasıl bağlandığını görelim.
Tanım 5.1 (Sabit Nokta) Bir \(g\) fonksiyonu verilsin. \(g(p) = p\) eşitliğini sağlayan bir \(p\) noktasına \(g\) fonksiyonunun sabit noktası denir.
Yani \(g\), sabit noktasını yerinden oynatmaz. Geometrik olarak sabit noktalar, \(y = g(x)\) grafiğinin \(y = x\) doğrusunu kestiği noktaların apsisleridir.
Sabit nokta problemi ile kök bulma problemi birbirine dönüştürülebilir:
- \(f(p) = 0\) kök bulma problemi verilsin. \(g(x) = x - f(x)\) ya da \(g(x) = x + 3f(x)\) gibi pek çok farklı biçimde, \(p\)’yi sabit nokta kabul eden \(g\) fonksiyonları kurulabilir. Örneğin ilki için \(g(p) = p - f(p) = p - 0 = p\) olur.
- Tersine, \(g(p) = p\) ise \(f(x) = x - g(x)\) tanımlanırsa \(f(p) = p - g(p) = p - p = 0\) olur, yani \(p\), \(f\)’nin bir köküdür.
Bu yüzden bir sabit noktayı bulmak için geliştirilen her yöntem bir kök bulma yöntemi olarak da kullanılabilir.
Örnek 5.1 (Bir Polinomun Sabit Noktaları) \(g(x) = x^2 - 2\) fonksiyonunun sabit noktalarını bulunuz.
Çözüm
Sabit nokta tanımından
\[ g(p) = p \iff p^2 - 2 = p \iff p^2 - p - 2 = 0 \iff (p - 2)(p + 1) = 0 \]
olur. Buradan \(p = -1\) ve \(p = 2\) bulunur. Gerçekten
\[ g(-1) = (-1)^2 - 2 = -1, \qquad g(2) = 2^2 - 2 = 2 \]
sağlanır. Bu iki nokta, \(y = x^2 - 2\) parabolünün \(y = x\) doğrusunu kestiği \((-1, -1)\) ve \((2, 2)\) noktalarının apsisleridir.
\(\blacksquare\)
5.2 Sabit Noktanın Varlığı ve Tekliği
Bir fonksiyonun sabit noktası olup olmadığını, varsa tek olup olmadığını denklemi çözmeden nasıl anlarız? Aşağıdaki teorem bunun için iki yeter koşul verir.
Teorem 5.1 (Sabit Noktanın Varlığı ve Tekliği) (i) \(g \in C[a, b]\) ve her \(x \in [a, b]\) için \(g(x) \in [a, b]\), yani \(a \le g(x) \le b\) ise \(g\) fonksiyonunun \([a, b]\) aralığında en az bir sabit noktası vardır.
(ii) \(g \in C[a, b]\) ve her \(x \in [a, b]\) için \(g(x) \in [a, b]\) olsun. Ayrıca \(g'\) türevi \((a, b)\) aralığında mevcut olsun ve her \(x \in (a, b)\) için
\[|g'(x)| \le k\]
eşitsizliğini sağlayan bir \(k < 1\) sabiti bulunsun. Bu durumda \(g\) fonksiyonunun \([a, b]\) aralığında tek türlü belirli bir sabit noktası vardır.
İspat
(i) \(g(a) = a\) ya da \(g(b) = b\) ise uç noktalardan biri sabit noktadır ve söylenecek bir şey kalmaz. Aksi hâlde \(g(a) \ne a\) ve \(g(b) \ne b\)’dir. \(g(a) \in [a, b]\) olduğundan \(g(a) \ge a\)’dır ve eşitlik olmadığına göre \(a < g(a)\) olur. Aynı biçimde \(g(b) \le b\) ve \(g(b) \ne b\) olduğundan \(g(b) < b\) olur.
\(h(x) = g(x) - x\) fonksiyonunu tanımlayalım. \(h\), \([a, b]\) aralığında süreklidir ve
\[h(a) = g(a) - a > 0, \qquad h(b) = g(b) - b < 0\]
olduğundan \(h(a) \cdot h(b) < 0\)’dır. Ara Değer Teoremi’ne (Teorem 1.7) göre \(h(p) = 0\) olan bir \(p \in (a, b)\) vardır. Bu, \(g(p) - p = 0\), yani \(g(p) = p\) demektir.
(ii) Varlık (i)’den gelir. Teklik için \(g\)’nin \([a, b]\) aralığında \(p \ne q\) olan iki sabit noktası olduğunu varsayalım. \(g\), \(p\) ile \(q\) arasındaki kapalı aralıkta sürekli, açık aralıkta türevlidir. Ortalama Değer Teoremi’ne (Teorem 1.4) göre \(p\) ile \(q\) arasında bir \(\xi\) için
\[g'(\xi) = \frac{g(p) - g(q)}{p - q}\]
olur. Buradan
\[|p - q| = |g(p) - g(q)| = |g'(\xi)|\,|p - q| \le k\,|p - q| < |p - q|\]
elde edilir. \(|p - q| < |p - q|\) bir çelişkidir. Dolayısıyla \(p = q\)’dur ve sabit nokta tek türlü belirlidir. \(\blacksquare\)
Örnek 5.2 (Bir Parabolün Tek Sabit Noktası) \(g(x) = \dfrac{x^2 - 1}{3}\) fonksiyonunun \([-1, 1]\) aralığında tek türlü belirli bir sabit noktası olduğunu gösteriniz.
Çözüm
\(g\) bir polinom olduğundan \(g \in C[-1, 1]\)’dir ve \(g'(x) = \dfrac{2x}{3}\) türevi \((-1, 1)\) üzerinde vardır.
Değerlerin aralıkta kalması. Ekstremum Değer Teoremi’ne (Teorem 1.5) göre \(g\), \([-1, 1]\) aralığında mutlak en küçük ve en büyük değerlerini ya uç noktalarda ya da \(g'(x) = 0\) olan noktalarda alır.
\[g(-1) = g(1) = 0, \qquad g'(x) = \frac{2x}{3} = 0 \Rightarrow x = 0, \qquad g(0) = -\frac{1}{3}\]
olduğundan
\[g : [-1, 1] \to \left[-\frac{1}{3}, 0\right] \subset [-1, 1]\]
olur. Teorem 5.1 (i)’ye göre \(g\)’nin \([-1, 1]\) aralığında, hatta \(\left[-\frac{1}{3}, 0\right]\) aralığında en az bir sabit noktası vardır.
Teklik. Her \(x \in (-1, 1)\) için
\[|g'(x)| = \left|\frac{2x}{3}\right| = \frac{2}{3}|x| \le \frac{2}{3} = k < 1\]
olduğundan Teorem 5.1 (ii)’ye göre bu sabit nokta tek türlü belirlidir.
Bu örnekte sabit nokta açıkça da bulunabilir: \(\dfrac{p^2 - 1}{3} = p \iff p^2 - 3p - 1 = 0\) denkleminin \([-1, 1]\)’deki kökü \(p = \dfrac{3 - \sqrt{13}}{2} \approx -0{,}30278\)’dir. Diğer kök \(\dfrac{3 + \sqrt{13}}{2} \approx 3{,}30278\) aralığın dışındadır. \(\blacksquare\)
Teorem 5.1 sabit noktanın varlığı ve tekliği için yeter koşullar verir, ama sabit noktanın nasıl bulunacağını söylemez. Şimdi sabit noktaya istenen hassasiyette nasıl yaklaşılacağını ele alıyoruz.
5.3 İterasyon ve İterasyon Fonksiyonu
Sabit noktaya yaklaşmanın en doğal yolu \(g\)’yi art arda uygulamaktır.
Tanım 5.2 (Sabit Nokta İterasyonu ve İterasyon Fonksiyonu) Bir \(g\) fonksiyonu ve bir \(p_0\) ilk yaklaşım değeri verilsin. Her \(n \ge 1\) için
\[p_n = g(p_{n-1}) \tag{1}\]
kuralıyla \((p_n)_{n=0}^{\infty}\) dizisini üretme tekniğine sabit nokta iterasyonu, \(g\) fonksiyonuna da iterasyon fonksiyonu denir.
Yani \(p_0\)’dan başlayıp her terimi bir öncekinin \(g\) altındaki görüntüsü olarak hesaplarız: \(p_1 = g(p_0)\), \(p_2 = g(p_1)\), … Bu dizi bir \(p\)’ye yakınsar ve \(g\) sürekli ise
\[p = \lim_{n \to \infty} p_n = \lim_{n \to \infty} g(p_{n-1}) = g\left(\lim_{n \to \infty} p_{n-1}\right) = g(p)\]
olur, yani limit \(x = g(x)\) denkleminin bir çözümüdür.
\(f(x) = 0\) denkleminin bir kökünü sabit nokta iterasyonuyla bulmak için önce bir iterasyon fonksiyonu seçilir; seçilen \(g\)’nin sabit noktası \(f(x) = 0\) denkleminin gerçek köküdür. Bu seçim tek türlü değildir.
Örnek 5.3 (Aynı Denklem İçin Farklı İterasyon Fonksiyonları) \(f(x) = x^2 - x - 2\) fonksiyonu için \(g(x)\) iterasyon fonksiyonlarını belirleyiniz.
Çözüm
\(f(x) = 0\) denklemini \(x = g(x)\) biçimine getirmek istiyoruz. Bunun birçok yolu vardır.
Birinci seçenek. \(x\) terimini yalnız bırakalım:
\[x^2 - x - 2 = 0 \Rightarrow x = x^2 - 2 \Rightarrow g(x) = x^2 - 2.\]
İkinci seçenek. \(x^2\) terimini yalnız bırakıp \(x \ge 0\) için karekök alalım:
\[x^2 = x + 2 \Rightarrow x = \sqrt{x + 2} \Rightarrow g(x) = \sqrt{x + 2}.\]
Karekök negatif olmadığından bu \(g\) yalnız pozitif kökü (\(p = 2\)) sabit nokta olarak taşır: \(g(-1) = 1 \ne -1\).
Üçüncü seçenek. \(x^2 = x + 2\) eşitliğini \(x \ne 0\) için \(x\)’e bölelim:
\[x = 1 + \frac{2}{x} \Rightarrow g(x) = 1 + \frac{2}{x}.\]
Dördüncü seçenek. \(m \ne 0\) bir sabit olmak üzere
\[x = x + m(x^2 - x - 2) \Rightarrow g(x) = x + m(x^2 - x - 2).\]
Bu ailedeki her \(g\)’nin sabit noktaları tam olarak \(f\)’nin kökleridir. \(m\) serbest bir parametre olduğundan, \(m\) uygun seçilerek kök civarında \(|g'(x)|\) küçültülebilir.
Dört fonksiyonun da \(2\)’de sabit noktası vardır: \(g(2) = 2\). \(\blacksquare\)
Hangi seçimin iyi olduğunu, yani iterasyonun yakınsayıp yakınsamadığını ve ne hızla yakınsadığını bir sonraki teorem belirler.
5.4 Sabit Nokta Teoremi
Teorem 5.1’in (ii) koşulları yalnız sabit noktanın tekliğini değil, iterasyonun her başlangıç noktasından ona yakınsadığını da güvenceye alır.
Teorem 5.2 (Sabit Nokta Teoremi) \(g \in C[a, b]\) ve her \(x \in [a, b]\) için \(g(x) \in [a, b]\) olsun. Ayrıca \(g'\) türevi \((a, b)\) aralığında mevcut olsun ve her \(x \in (a, b)\) için
\[|g'(x)| \le k\]
eşitsizliğini sağlayan bir \(0 < k < 1\) sayısı bulunsun. Bu durumda \([a, b]\) aralığındaki her \(p_0\) için, \(n \ge 1\) olmak üzere \(p_n = g(p_{n-1})\) ile tanımlanan \((p_n)_{n=0}^{\infty}\) dizisi, \([a, b]\) aralığındaki tek türlü belirli \(p\) sabit noktasına yakınsar.
İspat
Teorem 5.1’e göre \(g\)’nin \([a, b]\) aralığında tek bir \(p\) sabit noktası vardır. \(p_0 \in [a, b]\) ve \(g\), \([a, b]\)’yi kendi içine gönderdiğinden tümevarımla her \(n \ge 0\) için \(p_n \in [a, b]\) olur.
\(n \ge 1\) olsun. \(p_{n-1} = p\) ise \(p_n = g(p) = p\) olur. Aksi hâlde Ortalama Değer Teoremi’ne (Teorem 1.4) göre \(p_{n-1}\) ile \(p\) arasında, dolayısıyla \((a, b)\) içinde bir \(\xi_n\) için
\[|p_n - p| = |g(p_{n-1}) - g(p)| = |g'(\xi_n)|\,|p_{n-1} - p| \le k\,|p_{n-1} - p|\]
olur. İki durumda da \(|p_n - p| \le k\,|p_{n-1} - p|\)’dir. Bu eşitsizliği art arda uygularsak
\[|p_n - p| \le k\,|p_{n-1} - p| \le k^2\,|p_{n-2} - p| \le \dots \le k^n\,|p_0 - p| \tag{2}\]
elde ederiz. \(0 < k < 1\) olduğundan \(n \to \infty\) iken \(k^n \to 0\)’dır. Böylece
\[0 \le \lim_{n \to \infty} |p_n - p| \le \lim_{n \to \infty} k^n\,|p_0 - p| = 0\]
olur, yani \(p_n \to p\)’dir. \(\blacksquare\)
Teorem yakınsamayı güvenceye alır. Pratikte ise kaç adım atılacağını bilmek isteriz; bunun için hatayı sınırlamamız gerekir.
Sonuç 5.1 (Sabit Nokta İterasyonunda Hata Sınırları) \(g\) fonksiyonu Sabit Nokta Teoremi’nin (Teorem 5.2) koşullarını sağlasın. \(p\) sabit noktasına yapılan \(p_n\) yaklaşımının mutlak hatası, \(n \ge 1\) olmak üzere
(i) \(|p_n - p| \le k^n \max\{p_0 - a,\ b - p_0\}\),
(ii) \(|p_n - p| \le \dfrac{k^n}{1 - k}\,|p_1 - p_0|\)
eşitsizlikleriyle sınırlanır.
İspat
(i) \(p, p_0 \in [a, b]\) olduğundan \(p_0\) ile \(p\) arasındaki uzaklık, \(p_0\)’ın uç noktalara uzaklıklarının büyüğünü aşamaz: \(|p_0 - p| \le \max\{p_0 - a,\ b - p_0\}\). Bunu (2) eşitsizliğinde yerine koyarsak
\[|p_n - p| \le k^n\,|p_0 - p| \le k^n \max\{p_0 - a,\ b - p_0\}\]
elde ederiz.
(ii) Teoremin ispatındaki gibi Ortalama Değer Teoremi’ni ardışık terimlere uygularsak her \(n \ge 1\) için
\[ \begin{aligned} |p_{n+1} - p_n| &= |g(p_n) - g(p_{n-1})| \le k\,|p_n - p_{n-1}| \\[1mm] &\le k^2\,|p_{n-1} - p_{n-2}| \le \dots \le k^n\,|p_1 - p_0| \end{aligned} \]
olur. \(m > n \ge 1\) için \(p_m - p_n\) farkını ardışık farkların toplamı olarak yazıp üçgen eşitsizliğini kullanalım:
\[ \begin{aligned} |p_m - p_n| &= |(p_m - p_{m-1}) + (p_{m-1} - p_{m-2}) + \dots + (p_{n+1} - p_n)| \\[1mm] &\le |p_m - p_{m-1}| + |p_{m-1} - p_{m-2}| + \dots + |p_{n+1} - p_n| \\[1mm] &\le k^{m-1}|p_1 - p_0| + k^{m-2}|p_1 - p_0| + \dots + k^n|p_1 - p_0| \\[1mm] &= k^n\,|p_1 - p_0|\left(1 + k + k^2 + \dots + k^{m-n-1}\right). \end{aligned} \]
Teoreme göre \(m \to \infty\) iken \(p_m \to p\)’dir. Parantezdeki toplam \(\sum_{i=0}^{\infty} k^i\) geometrik serisinin bir kısmi toplamı olduğundan seriyi aşamaz. Böylece
\[ \begin{aligned} |p - p_n| &= \lim_{m \to \infty} |p_m - p_n| \le k^n\,|p_1 - p_0| \sum_{i=0}^{\infty} k^i \\[1mm] &= k^n\,|p_1 - p_0| \cdot \frac{1}{1 - k} \end{aligned} \]
olur, yani \(|p_n - p| \le \dfrac{k^n}{1 - k}\,|p_1 - p_0|\)’dır. \(\blacksquare\)
İki sınırda da hata \(k^n\) ile orantılı azalır. Dolayısıyla \(k\) değeri ne kadar küçükse yakınsama o kadar hızlıdır.
Bu gözlem Örnek 5.3’deki seçenekleri karşılaştırmayı sağlar. \(g'\) sürekli ve \(|g'(p)| < 1\) ise \(p\)’nin yeterince küçük bir \([p - \delta, p + \delta]\) komşuluğunda \(|g'(x)| \le k < 1\) olur. Bu komşuluktaki her \(x\) için Ortalama Değer Teoremi’nden
\[|g(x) - p| = |g(x) - g(p)| \le k\,|x - p| \le \delta\]
olduğundan \(g\) komşuluğu kendi içine gönderir ve Sabit Nokta Teoremi uygulanır. Kök civarındaki hızı belirleyen \(|g'(p)|\) değeridir. \(p = 2\) kökünde:
- \(g(x) = x^2 - 2\) için \(g'(x) = 2x\) ve \(|g'(2)| = 4 > 1\)’dir. \(2\)’ye yeterince yakın ama ondan farklı bir \(p_n\) için \(|g'(\xi)| > 1\) olur ve \(|p_{n+1} - 2| = |g'(\xi)|\,|p_n - 2|\) farkı \(|p_n - 2|\)’den büyüktür; iterasyon kökten uzaklaşır.
- \(g(x) = \sqrt{x + 2}\) için \(g'(x) = \dfrac{1}{2\sqrt{x + 2}}\) ve \(|g'(2)| = \dfrac{1}{4}\)’tür.
- \(g(x) = 1 + \dfrac{2}{x}\) için \(g'(x) = -\dfrac{2}{x^2}\) ve \(|g'(2)| = \dfrac{1}{2}\)’dir.
- \(g(x) = x + m(x^2 - x - 2)\) için \(g'(2) = 1 + 3m\)’dir. \(m = -\dfrac{1}{3}\) seçilirse \(g(x) = \dfrac{-x^2 + 4x + 2}{3}\) ve \(g'(2) = 0\) olur.
Yani ilk seçim \(p = 2\) kökünü bulmakta işe yaramaz, ikincisi üçüncüsünden hızlıdır, dördüncüsünde ise \(m = -\frac{1}{3}\) seçilerek kökteki türev sıfırlanır. \(g'(p) = 0\) yapacak biçimde iterasyon fonksiyonu seçmek, bir sonraki bölümde Newton-Raphson Metodu’na götürecek fikirdir.
Örnek 5.4 (Gereken İterasyon Sayısının Belirlenmesi) \(\sin x - \dfrac{x}{1{,}4} = 0\) denkleminin \(\left[1, \frac{\pi}{2}\right]\) aralığındaki çözümünü sabit nokta iterasyonuyla bulmak için bir \(g(x)\) iterasyon fonksiyonu belirleyiniz. Bu \(g\) ile \(p_0 = 1{,}4\) alındığında denklemin çözümünü \(10^{-6}\) hassasiyetle bulmak için gereken iterasyon sayısını Sonuç 5.1 (ii) ile belirleyiniz. İşlemlerde beş-basamak yuvarlama aritmetiği kullanınız.
Çözüm
İterasyon fonksiyonu. Denklemi \(x\)’e göre düzenlersek
\[\sin x - \frac{x}{1{,}4} = 0 \Rightarrow x = 1{,}4 \sin x \Rightarrow g(x) = 1{,}4 \sin x\]
olur. Bu \(g\)’nin Sabit Nokta Teoremi’nin koşullarını sağladığını gösterelim.
Süreklilik ve aralıkta kalma. \(g \in C\left[1, \frac{\pi}{2}\right]\)’dir. \(g'(x) = 1{,}4 \cos x\) ve \(x \in \left[1, \frac{\pi}{2}\right]\) için \(\cos x \ge 0\) olduğundan \(g'(x) \ge 0\)’dır; \(g\) bu aralıkta monoton artandır. Dolayısıyla her \(x \in \left[1, \frac{\pi}{2}\right]\) için \(g(1) \le g(x) \le g\left(\frac{\pi}{2}\right)\) olur. Burada
\[ \begin{aligned} g(1) &= 1{,}4 \sin 1 = 1{,}1781 > 1, \\[1mm] g\left(\tfrac{\pi}{2}\right) &= 1{,}4 \sin \tfrac{\pi}{2} = 1{,}4 < \tfrac{\pi}{2} = 1{,}5708 \end{aligned} \]
olduğundan her \(x \in \left[1, \frac{\pi}{2}\right]\) için \(g(x) \in \left[1, \frac{\pi}{2}\right]\) sağlanır.
Türev sınırı. \(\cos x\) fonksiyonu \(\left[1, \frac{\pi}{2}\right]\) aralığında negatif olmayan ve azalan bir fonksiyondur; en büyük değerini \(x = 1\)’de alır. Bu yüzden
\[ \begin{aligned} |g'(x)| &= 1{,}4\,|\cos x| \le 1{,}4 \max_{1 \le x \le \pi/2} |\cos x| \\[1mm] &= 1{,}4 \cos 1 = 0{,}75642 = k < 1 \end{aligned} \]
olur. Sabit Nokta Teoremi’nin koşulları sağlanır.
İterasyon sayısı. \(p_0 = 1{,}4\) için
\[p_1 = g(p_0) = 1{,}4 \sin(1{,}4) = 1{,}4 \cdot 0{,}98545 = 1{,}3796\]
bulunur. Sonuç 5.1 (ii)’ye göre
\[|p_n - p| \le \frac{k^n}{1 - k}\,|p_1 - p_0| < 10^{-6}\]
olmasını istiyoruz. Değerleri yerine koyalım:
\[ \begin{aligned} &\frac{0{,}75642^n}{1 - 0{,}75642}\,|1{,}3796 - 1{,}4| < 10^{-6} \\[1mm] &\Rightarrow \frac{0{,}75642^n}{0{,}24358} \cdot 0{,}0204 < 10^{-6} \\[1mm] &\Rightarrow 0{,}75642^n < 11{,}940 \cdot 10^{-6}. \end{aligned} \]
İki tarafın onluk logaritmasını alalım:
\[ \begin{aligned} &n \log 0{,}75642 < \log 11{,}940 - 6 \log 10 \\[1mm] &\Rightarrow n \cdot (-0{,}12124) < 1{,}0770 - 6 = -4{,}9230. \end{aligned} \]
Negatif sayıya bölerken eşitsizlik yön değiştirir:
\[n > \frac{4{,}9230}{0{,}12124} = 40{,}605 \Rightarrow n \ge 41.\]
Yani \(41\) iterasyon \(10^{-6}\) hassasiyeti güvenceye alır. \(\blacksquare\)
Aynı soruyu Sonuç 5.1’nin öteki sınırıyla da yanıtlayabiliriz.
Örnek 5.5 (Öteki Hata Sınırıyla İterasyon Sayısı) \(g(x) = 1{,}4 \sin x\), \(\left[1, \frac{\pi}{2}\right]\) ve \(p_0 = 1{,}4\) için (Örnek 5.4) \(10^{-6}\) hassasiyet için gereken iterasyon sayısını Sonuç 5.1 (i) ile belirleyiniz ve (ii) ile bulunan sonuçla karşılaştırınız. İşlemlerde beş-basamak yuvarlama aritmetiği kullanınız.
Çözüm
Örnek 5.4’nde koşulların sağlandığını ve \(k = 0{,}75642\) olduğunu gördük. \(a = 1\), \(b = \frac{\pi}{2} = 1{,}5708\) ve \(p_0 = 1{,}4\) için
\[ \begin{aligned} p_0 - a &= 1{,}4 - 1 = 0{,}4, \\[1mm] b - p_0 &= 1{,}5708 - 1{,}4 = 0{,}1708 \end{aligned} \]
olduğundan \(\max\{p_0 - a,\ b - p_0\} = 0{,}4\)’tür. Sonuç 5.1 (i)’ye göre
\[|p_n - p| \le 0{,}75642^n \cdot 0{,}4 < 10^{-6}\]
olmasını istiyoruz:
\[ \begin{aligned} &0{,}75642^n < \frac{10^{-6}}{0{,}4} = 2{,}5 \cdot 10^{-6} \\[1mm] &\Rightarrow n \log 0{,}75642 < \log 2{,}5 - 6 \log 10 \\[1mm] &\Rightarrow n \cdot (-0{,}12124) < 0{,}39794 - 6 = -5{,}6021 \\[1mm] &\Rightarrow n > \frac{5{,}6021}{0{,}12124} = 46{,}207 \Rightarrow n \ge 47. \end{aligned} \]
Karşılaştırma. (i) sınırı \(47\), (ii) sınırı \(41\) iterasyon verir; burada (ii) daha keskindir. (i) yalnız \(p\)’nin \(\left[1, \frac{\pi}{2}\right]\) içinde olduğunu bilir ve \(|p_0 - p|\) için en kötü durumu, \(0{,}4\) uzaklığı kullanır. (ii) ise ilk adımın büyüklüğünü kullanır. \(p_0 = 1{,}4\) köke yakın olduğundan \(|p_1 - p_0| = 0{,}0204\) küçüktür ve sınır daha iyi çıkar.
İki sınır da gerçek durumdan çok daha karamsardır. Sabit nokta \(p \approx 1{,}37259\)’dur ve tam duyarlıkla hesaplandığında \(|p_n - p| < 10^{-6}\) eşitsizliği \(n = 8\)’de sağlanır. Bunun nedeni, \(k = 0{,}75642\)’nin \(|g'|\)’nün bütün aralıktaki en büyük değeri olmasıdır; kökte ise \(|g'(p)| = 1{,}4 \cos p \approx 0{,}27568\)’dir. \(\blacksquare\)
5.5 Sabit Nokta İterasyonu ile Kök Bulma
Yöntemi bir denklemin kökünü bulmak için baştan sona uygulayalım. Durma kriteri olarak ya ardışık iki terimin farkı ya da \(|p_n - g(p_n)|\) kullanılır; \(g(p_n) = p_{n+1}\) olduğundan ikisi aynı büyüklüğü ölçer.
- \(f(x) = 0\) denklemini \(x = g(x)\) biçimine getir.
- \(g \in C[a, b]\) olduğunu ve monotonluk ya da ekstremumlar yardımıyla \(g([a, b]) \subset [a, b]\) olduğunu göster.
- \(k = \max |g'(x)|\) değerini hesapla ve \(k < 1\) olduğunu doğrula.
- \(p_0\)’dan başlayıp \(p_n = g(p_{n-1})\) değerlerini durma kriteri sağlanana kadar bir tabloda hesapla.
Örnek 5.6 (Bir Üstel Denklemin Kökü) \(x e^x = 0{,}3\) denkleminin \([0{,}1;\ 0{,}9]\) aralığındaki kökünü, uygun bir \(g\) iterasyon fonksiyonuyla, \(p_0 = 0{,}2\) alarak ve
\[|p_n - g(p_n)| < 10^{-4} \tag{3}\]
durma kriterini kullanarak sabit nokta iterasyonuyla belirleyiniz. İşlemlerde virgülden sonra 5. basamağa yuvarlama yapınız ve sonuçları bir tabloda gösteriniz.
Çözüm
İterasyon fonksiyonu. \(f(x) = x e^x - 0{,}3 = 0\) denkleminin iki tarafını \(e^x\)’e bölersek \(x = 0{,}3 e^{-x}\) olur. \(g(x) = 0{,}3 e^{-x}\) alalım.
Aralıkta kalma. \(g \in C[0{,}1;\ 0{,}9]\)’dur. \(g'(x) = -0{,}3 e^{-x} < 0\) olduğundan \(g\) bu aralıkta monoton azalandır. Dolayısıyla her \(0{,}1 \le x \le 0{,}9\) için \(g(0{,}9) \le g(x) \le g(0{,}1)\) olur. Burada
\[g(0{,}9) = 0{,}12197 > 0{,}1, \qquad g(0{,}1) = 0{,}27145 < 0{,}9\]
olduğundan
\[g(x) \in [0{,}12197;\ 0{,}27145] \subset [0{,}1;\ 0{,}9]\]
sağlanır. Teorem 5.1 (i)’ye göre \(g\)’nin bu aralıkta en az bir sabit noktası vardır.
Türev sınırı. \(e^{-x}\) azalan olduğundan en büyük değerini \(x = 0{,}1\)’de alır:
\[ \begin{aligned} |g'(x)| &= 0{,}3 e^{-x} \le 0{,}3 \max_{0{,}1 \le x \le 0{,}9} e^{-x} \\[1mm] &= 0{,}3 e^{-0{,}1} = 0{,}27145 = k < 1. \end{aligned} \]
Sabit Nokta Teoremi’ne (Teorem 5.2) göre sabit nokta tek türlü belirlidir ve iterasyon ona yakınsar.
İterasyon. \(p_0 = 0{,}2\) ve \(n \ge 1\) için \(p_n = g(p_{n-1})\) ile hesaplarsak şu tabloyu elde ederiz:
| \(n\) | \(p_n\) | \(g(p_n)\) | \(\lvert p_n - g(p_n)\rvert\) |
|---|---|---|---|
| \(0\) | \(0{,}20000\) | \(0{,}24562\) | \(0{,}04562\) |
| \(1\) | \(0{,}24562\) | \(0{,}23467\) | \(0{,}01095\) |
| \(2\) | \(0{,}23467\) | \(0{,}23725\) | \(0{,}00258\) |
| \(3\) | \(0{,}23725\) | \(0{,}23664\) | \(0{,}00061\) |
| \(4\) | \(0{,}23664\) | \(0{,}23678\) | \(0{,}00014\) |
| \(5\) | \(0{,}23678\) | \(0{,}23675\) | \(0{,}00003\) |
\(n = 5\)’te \(|p_5 - g(p_5)| = 0{,}00003 < 10^{-4}\) olduğundan (3) numaralı durma kriteri sağlanır ve \(p \approx p_5 = 0{,}23678\) bulunur.
Terimler kökün bir sağında bir solunda kalarak ona yaklaşır. Bunun nedeni \(g'\)’nün negatif olmasıdır: \(g'(x) = -g(x)\) olduğundan \(g'(p) = -p \approx -0{,}24\)’tür. Aşağıdaki örümcek ağı diyagramında bu salınımlı yakınsama, \(|g'| > 1\) olan bir iterasyonun ıraksamasıyla karşılaştırılıyor. Sağdaki panel Örnek 5.3’deki \(g(x) = x^2 - 2\) fonksiyonunu \(p_0 = 2{,}1\) ile gösterir: \(p_1 = 2{,}41\), \(p_2 = 3{,}8081\), \(p_3 \approx 12{,}5\) ve terimler \(p = 2\) kökünden hızla uzaklaşır.
\(\blacksquare\)
5.6 Alıştırmalar
Alıştırma 5.1 (Kök Üçe Sabit Nokta İterasyonuyla Yaklaşım) \(\sqrt{3}\) sayısına \([1{,}5;\ 2]\) aralığında
\[g(x) = 0{,}5\left(x + \frac{3}{x}\right)\]
iterasyon fonksiyonu ve
\[|p_n - p_{n-1}| < 10^{-4} \tag{4}\]
durma kriteriyle sabit nokta iterasyonu kullanarak yaklaşınız. \(p_0 = 1{,}5\) alıp işlemlerde virgülden sonra 5. basamağa yuvarlama yaparak bir tablo oluşturunuz.
Çözüm
Denklem. \(\sqrt{3}\), \(x^2 - 3 = 0\) denkleminin bir köküdür. \(f(x) = x^2 - 3\) olmak üzere bu denklemi \([1{,}5;\ 2]\) aralığında ele alalım. \(x \ne 0\) için
\[g(x) = x \iff \frac{3}{x} = x \iff x^2 = 3\]
olduğundan \(g\)’nin bu aralıktaki sabit noktası \(\sqrt{3}\)’tür.
Aralıkta kalma. \(g \in C[1{,}5;\ 2]\)’dir ve
\[g'(x) = 0{,}5\left(1 - \frac{3}{x^2}\right) = 0 \Rightarrow x = \sqrt{3}\]
kritik noktadır. \(g(1{,}5) = 1{,}75\), \(g(\sqrt{3}) = \sqrt{3}\) ve \(g(2) = 1{,}75\)’tir. \(g'\)’nün işaretine göre:
| \(x\) | \(1{,}5\) | \(\sqrt{3}\) | \(2\) | ||
|---|---|---|---|---|---|
| \(g'\) | \(-\) | \(0\) | \(+\) | ||
| \(g\) | \(1{,}75\) | \(\searrow\) | \(\sqrt{3}\) | \(\nearrow\) | \(1{,}75\) |
Buna göre
\[x \in [1{,}5;\ 2] \Rightarrow g(x) \in [\sqrt{3};\ 1{,}75] \subset [1{,}5;\ 2]\]
olur.
Türev sınırı. \(h(x) = \left|1 - \dfrac{3}{x^2}\right|\) diyelim. Parçalı olarak
\[ h(x) = \begin{cases} \dfrac{3}{x^2} - 1, & 1{,}5 \le x \le \sqrt{3}, \\[2mm] 1 - \dfrac{3}{x^2}, & \sqrt{3} \le x \le 2 \end{cases} \]
ve
\[ h'(x) = \begin{cases} -\dfrac{6}{x^3}, & 1{,}5 \le x < \sqrt{3}, \\[2mm] \dfrac{6}{x^3}, & \sqrt{3} < x \le 2 \end{cases} \]
olur. \(h\), \([1{,}5;\ \sqrt{3}]\) üzerinde azalan, \([\sqrt{3};\ 2]\) üzerinde artandır (\(h'(\sqrt{3})\) yoktur). \(h(1{,}5) = 0{,}33333\), \(h(\sqrt{3}) = 0\) ve \(h(2) = 0{,}25\) olduğundan her \(x \in [1{,}5;\ 2]\) için \(0 \le h(x) \le 0{,}33333\)’tür. En büyük değer \(x = 1{,}5\)’te alınır:
\[ \begin{aligned} |g'(x)| &= 0{,}5 \cdot h(x) \le 0{,}5 \cdot \left|1 - \frac{3}{1{,}5^2}\right| \\[1mm] &= 0{,}5 \cdot 0{,}33333 = 0{,}16667 = k < 1. \end{aligned} \]
Sabit Nokta Teoremi’nin (Teorem 5.2) koşulları sağlanır.
İterasyon. \(p_0 = 1{,}5\) ve \(n \ge 1\) için \(p_n = g(p_{n-1})\) olmak üzere:
| \(n\) | \(p_n\) | \(g(p_n)\) | \(\lvert p_n - p_{n-1}\rvert\) |
|---|---|---|---|
| \(0\) | \(1{,}50000\) | \(1{,}75000\) | |
| \(1\) | \(1{,}75000\) | \(1{,}73214\) | \(0{,}25000\) |
| \(2\) | \(1{,}73214\) | \(1{,}73205\) | \(0{,}01786\) |
| \(3\) | \(1{,}73205\) | \(1{,}73205\) | \(0{,}00009\) |
Örneğin
\[g(p_1) = 0{,}5\,(1{,}75 + 1{,}714286) = 1{,}732143\]
değeri \(1{,}73214\)’e yuvarlanır. \(n = 3\)’te \(|p_3 - p_2| = 0{,}00009 < 10^{-4}\) olduğundan (4) numaralı durma kriteri sağlanır ve
\[\sqrt{3} \approx p_3 = 1{,}73205\]
bulunur. \(\blacksquare\)
Alıştırma 5.2 (Gereken İterasyon Sayısı İçin Bir Alıştırma) Örnek 5.3’deki \(g(x) = \sqrt{x + 2}\) iterasyon fonksiyonunun \([1, 3]\) aralığında Sabit Nokta Teoremi’nin koşullarını sağladığını gösteriniz. \(p_0 = 1\) için \(p = 2\) köküne \(10^{-4}\) hassasiyetle yaklaşmak üzere gereken iterasyon sayısını Sonuç 5.1 (ii) ile belirleyiniz. İşlemlerde virgülden sonra 5. basamağa yuvarlama yapınız.
Çözüm
Aralıkta kalma. \(x + 2 > 0\) olduğundan \(g \in C[1, 3]\)’tür. \(g'(x) = \dfrac{1}{2\sqrt{x + 2}} > 0\) olduğundan \(g\) artandır ve
\[g(1) = \sqrt{3} = 1{,}73205, \qquad g(3) = \sqrt{5} = 2{,}23607\]
olur. Böylece \(g(x) \in [1{,}73205;\ 2{,}23607] \subset [1, 3]\)’tür.
Türev sınırı. \(g'\) pozitif ve azalandır; en büyük değerini \(x = 1\)’de alır:
\[|g'(x)| \le \frac{1}{2\sqrt{3}} = 0{,}28868 = k < 1.\]
Koşullar sağlanır ve \([1, 3]\)’teki tek sabit nokta \(p = 2\)’dir.
İterasyon sayısı. \(p_1 = g(1) = 1{,}73205\), \(|p_1 - p_0| = 0{,}73205\) ve \(1 - k = 0{,}71132\)’dir. Sonuç 5.1 (ii)’ye göre
\[ \begin{aligned} &\frac{0{,}28868^n}{0{,}71132} \cdot 0{,}73205 < 10^{-4} \\[1mm] &\Rightarrow 0{,}28868^n < 0{,}97168 \cdot 10^{-4} \end{aligned} \]
olmalıdır. Onluk logaritma alırsak
\[ \begin{aligned} &n \log 0{,}28868 < \log 0{,}97168 - 4 \log 10 \\[1mm] &\Rightarrow n \cdot (-0{,}53958) < -0{,}01248 - 4 = -4{,}01248 \\[1mm] &\Rightarrow n > \frac{4{,}01248}{0{,}53958} = 7{,}4363 \Rightarrow n \ge 8 \end{aligned} \]
bulunur. Yani \(8\) iterasyon \(10^{-4}\) hassasiyeti güvenceye alır. Gerçekte hata \(n = 7\)’de (\(p_7 \approx 1{,}99993\)) \(10^{-4}\)’ün altına iner; hata sınırı her zaman güvenli tarafta kalır. \(\blacksquare\)
Sabit nokta iterasyonunda hız \(|g'(p)|\) ile belirlenir ve iyi bir iterasyon fonksiyonu bulmak çoğu zaman deneme yanılma ister. Bir sonraki bölümde \(g'(p) = 0\) olacak biçimde \(g\)’yi türevle kuran ve çok daha hızlı yakınsayan yöntemi inceliyoruz: Newton-Raphson Metodu.