3 Algoritmalar ve Yakınsama Hızı
Nümerik bir yöntem, bir problemin çözümüne adım adım yaklaşan bir algoritmadır. Her adımda yapılan işlemler makinede yuvarlanır; bu yüzden iki soru öne çıkar. Birincisi, küçük bir yuvarlama hatası sonraki adımlarda büyüyüp sonucu bozuyor mu? İkincisi, algoritmanın ürettiği yaklaşımlar gerçek değere ne kadar hızlı yaklaşıyor?
Bu bölümde ilk soru için hata büyümesini lineer ve üstel diye ikiye ayırıyoruz. İkinci soru için de \(O\) gösterimini kuruyoruz: \(y_n = y_0 + O\left(\frac{1}{n^p}\right)\) ve \(f(h) = L + O(h^p)\). Sonraki bölümlerdeki her yöntemi bu dille karşılaştıracağız.
3.1 Algoritmalar ve Kararlılık
Önce algoritmanın ne olduğunu ve iyi bir algoritmadan ne beklediğimizi belirleyelim.
Tanım 3.1 (Algoritma) Belirli bir sırayla uygulanacak adımların sonlu bir dizisini kesin biçimde tarif eden yönteme algoritma denir.
Yani algoritma, ne yapılacağı her adımda açıkça belli olan ve sonlu sayıda adımda biten bir tariftir. Bu kitaptaki algoritmaların amacı bir problemin çözümüne (bir köke, bir integralin değerine, bir fonksiyonun değerine) yaklaşımda bulunmaktır.
Tanım 3.2 (Kararlı Algoritma) Girdideki küçük değişiklikler çıktıda da yalnız küçük değişikliklere yol açıyorsa algoritmaya kararlı algoritma denir.
Yani kararlı bir algoritmada girdilerin makinede yuvarlanmasından doğan küçük hatalar (Tanım 2.8) sonucu bozmaz. Bir algoritmanın kararlı olup olmadığını, hatanın adım sayısıyla nasıl büyüdüğüne bakarak anlarız.
Tanım 3.3 (Lineer ve Üstel Hata Büyümesi) Bir hesabın herhangi bir adımında ilk ortaya çıkan hata \(E_0 > 0\), bu adımı izleyen \(n\) adımdan sonraki hatanın büyüklüğü \(E_n\) olsun. \(C\), \(n\)’den bağımsız bir sabit olmak üzere
- \(E_n \approx C \cdot n \cdot E_0\) ise hatanın büyümesi lineerdir,
- \(C > 1\) ve \(E_n \approx C^n E_0\) ise hatanın büyümesi üsteldir
denir. Hata büyümesi lineer olan yaklaşıma kararlı hata büyümesine sahip, üstel olan yaklaşıma kararsız hata büyümesine sahip yaklaşım denir.
Yani lineer büyümede \(100\) adım sonra hata ilk hatanın yaklaşık \(100\,C\) katıdır; üstel büyümede ise \(C^{100}\) katıdır. \(C = 3\) için bu \(3^{100} \approx 5 \cdot 10^{47}\) eder. Bu yüzden hata büyümesi lineer olan bir algoritmayla yaklaşımda bulunmak genellikle kabul edilebilirdir; hata büyümesi üstel olan algoritmalardan kaçınılır.
3.2 Üstel ve Lineer Hata Büyümesine Örnekler
Aşağıdaki iki örnekte başlangıç değerindeki \(10^{-5}\) mertebesinde tek bir yuvarlama hatasının izini sürüyoruz. Birinci örnekte hata her adımda üç katına çıkar, ikincisinde ise yalnız adım sayısıyla orantılı büyür.
Örnek 3.1 (İndirgeme bağıntısının çözümü) \(c_1\) ve \(c_2\) reel sabitler olmak üzere \((p_n)_{n=0}^{\infty}\) dizisi \(n = 0, 1, 2, \dots\) için
\[p_n = c_1 \left(\frac{1}{3}\right)^n + c_2\, 3^n\]
ile tanımlansın. Bu dizinin \(n = 2, 3, \dots\) için
\[p_n = \frac{10}{3}\, p_{n-1} - p_{n-2} \tag{1}\]
indirgeme bağıntısının bir çözümü olduğunu gösteriniz.
Çözüm
\(p_{n-1}\) ve \(p_{n-2}\)’yi (1)’in sağ tarafında yerine yazıp ortak çarpanları ayıralım:
\[\begin{aligned} \frac{10}{3}\, p_{n-1} - p_{n-2} &= \frac{10}{3}\left[c_1 \left(\frac{1}{3}\right)^{n-1} + c_2\, 3^{n-1}\right]\\[1mm] &\quad - \left[c_1 \left(\frac{1}{3}\right)^{n-2} + c_2\, 3^{n-2}\right]\\[1mm] &= c_1 \left(\frac{1}{3}\right)^{n-2}\left(\frac{10}{3} \cdot \frac{1}{3} - 1\right)\\[1mm] &\quad + c_2\, 3^{n-2}\left(\frac{10}{3} \cdot 3 - 1\right)\\[1mm] &= c_1 \left(\frac{1}{3}\right)^{n-2} \cdot \frac{1}{9} + c_2\, 3^{n-2} \cdot 9\\[1mm] &= c_1 \left(\frac{1}{3}\right)^{n} + c_2\, 3^{n} = p_n. \end{aligned}\]
Demek ki \(c_1\) ve \(c_2\) ne olursa olsun \((p_n)\) dizisi (1) bağıntısını sağlar. \(\blacksquare\)
Örnek 3.2 (Başlangıç değerlerinden sabitler) \(p_n = c_1 \left(\frac{1}{3}\right)^n + c_2\, 3^n\) dizisinde \(p_0 = 1\) ve \(p_1 = \frac{1}{3}\) verilirse \(c_1\) ve \(c_2\) sabitleri ne olur?
Çözüm
\(n = 0\) ve \(n = 1\) yazalım:
\[\begin{aligned} p_0 = 1 &\implies c_1 + c_2 = 1,\\[1mm] p_1 = \frac{1}{3} &\implies \frac{1}{3}\, c_1 + 3 c_2 = \frac{1}{3} \implies c_1 + 9 c_2 = 1. \end{aligned}\]
İkinci denklemden birinciyi çıkarırsak \(8 c_2 = 0\), yani \(c_2 = 0\) ve \(c_1 = 1\) bulunur. Bu sabitlerle dizi
\[p_n = \left(\frac{1}{3}\right)^n\]
olur ve \(n \to \infty\) iken sıfıra yakınsar. \(\blacksquare\)
Örnek 3.3 (Beş-basamak yuvarlamada hatanın büyümesi) \(p_n = c_1 \left(\frac{1}{3}\right)^n + c_2\, 3^n\) dizisinde \(p_0 = 1\) ve \(p_1 = \frac{1}{3}\) başlangıç değerleri beş-basamak yuvarlama aritmetiğiyle (Tanım 2.8) gösterilsin ve \(c_1\), \(c_2\) sabitleri bu değerlerden bulunsun. Dizi (1) bağıntısıyla hesaplandığında oluşan hatanın karakteristiğini araştırınız.
Çözüm
Başlangıç değerleri. Beş-basamak yuvarlamayla
\[p_0^* = 0{,}10000 \cdot 10^{1}, \qquad p_1^* = 0{,}33333\]
olur. Yalnız \(p_1\) yuvarlanmıştır; \(\left\lvert p_1 - p_1^* \right\rvert = \frac{1}{3} \cdot 10^{-5}\).
Sabitler. \(n = 0\) için \(c_1^* + c_2^* = 0{,}10000 \cdot 10^{1}\), yani \(c_1^* = 1 - c_2^*\). Bunu \(n = 1\) denkleminde kullanalım:
\[\begin{aligned} \frac{1}{3}\, c_1^* + 3 c_2^* = 0{,}33333 &\implies \frac{1}{3}\left(1 - c_2^*\right) + 3 c_2^* = 0{,}33333\\[1mm] &\implies \frac{8}{3}\, c_2^* = 0{,}33333 - \frac{1}{3} = -0{,}33333 \cdot 10^{-5}\\[1mm] &\implies c_2^* = -0{,}12500 \cdot 10^{-5}. \end{aligned}\]
Buradan \(c_1^* = 1 + 0{,}12500 \cdot 10^{-5}\), yani \(c_1^* = 1{,}00000125\) bulunur; beş basamağa yuvarlanınca \(c_1^* = 0{,}10000 \cdot 10^{1}\) olur. Böylece
\[p_n^* = \left(\frac{1}{3}\right)^n - 0{,}12500 \cdot 10^{-5} \cdot 3^n.\]
Bu biçimdeki her dizi (1)’i sağlar (bkz. Örnek 3.1). Bu dizi \(n = 0\)’da \(1 - 0{,}125 \cdot 10^{-5}\) verir; beş basamakta bu yine \(0{,}10000 \cdot 10^{1} = p_0^*\) demektir. Dolayısıyla (1) bağıntısını \(p_0^*\) ve \(p_1^*\)’dan başlatırsak (ara işlemlerdeki yeni yuvarlamaları bir yana bırakırsak) beş basamak duyarlığında bu diziyi üretiriz. Gerçek çözümde sıfır olan \(3^n\) katsayısı, yuvarlama yüzünden sıfır olmayan küçük bir \(c_2^*\) değeri almıştır.
Hatanın büyümesi. Mutlak hata
\[\begin{aligned} E_n = \left\lvert p_n - p_n^* \right\rvert &= \left\lvert \left(\frac{1}{3}\right)^n - \left(\frac{1}{3}\right)^n + 0{,}12500 \cdot 10^{-5} \cdot 3^n \right\rvert\\[1mm] &= 0{,}12500 \cdot 10^{-5} \cdot 3^n \end{aligned}\]
olur. Bu, \(E_n \approx C^n E_0\) biçimidir (Tanım 3.3): \(C = 3 > 1\) ve \(E_0 = 0{,}12500 \cdot 10^{-5}\). Burada \(E_0\), \(3^n\) çarpanının önündeki sabittir; başlangıçtaki \(\frac{1}{3} \cdot 10^{-5}\) yuvarlama hatasıyla aynı mertebededir. Demek ki \((p_n^*)\) dizisiyle \((p_n)\) dizisine yaklaşım üstel hata büyümesine sahiptir; bu yaklaşım kararsızdır.
Tablo. Aşağıdaki tabloda \(p_n^*\) değerleri (1) bağıntısından, \(\frac{10}{3}\) yerine \(0{,}33333 \cdot 10^{1}\) alınarak ve her çarpma ile her çıkarmanın sonucu beş basamağa yuvarlanarak hesaplanmıştır. Gerçek \(p_n = \left(\frac{1}{3}\right)^n\) değerleri de beş basamakla verilmiş, mutlak ve bağıl hatalar (Tanım 2.4) bu beş basamaklı değerlerden hesaplanmıştır; bu yüzden \(n = 0\) ve \(n = 1\) satırlarında hata \(0\) görünür.
| \(n\) | Hesaplanan \(p_n^*\) | Gerçek \(p_n\) | Bağıl Hata | Mutlak Hata |
|---|---|---|---|---|
| \(0\) | \(0{,}10000 \cdot 10^{1}\) | \(0{,}10000 \cdot 10^{1}\) | \(0\) | \(0\) |
| \(1\) | \(0{,}33333\) | \(0{,}33333\) | \(0\) | \(0\) |
| \(2\) | \(0{,}11110\) | \(0{,}11111\) | \(0{,}90001 \cdot 10^{-4}\) | \(0{,}10000 \cdot 10^{-4}\) |
| \(3\) | \(0{,}37000 \cdot 10^{-1}\) | \(0{,}37037 \cdot 10^{-1}\) | \(0{,}99900 \cdot 10^{-3}\) | \(0{,}37000 \cdot 10^{-4}\) |
| \(4\) | \(0{,}12230 \cdot 10^{-1}\) | \(0{,}12346 \cdot 10^{-1}\) | \(0{,}93958 \cdot 10^{-2}\) | \(0{,}11600 \cdot 10^{-3}\) |
| \(5\) | \(0{,}37660 \cdot 10^{-2}\) | \(0{,}41152 \cdot 10^{-2}\) | \(0{,}84856 \cdot 10^{-1}\) | \(0{,}34920 \cdot 10^{-3}\) |
| \(6\) | \(0{,}32300 \cdot 10^{-3}\) | \(0{,}13717 \cdot 10^{-2}\) | \(0{,}76453\) | \(0{,}10487 \cdot 10^{-2}\) |
| \(7\) | \(-0{,}26893 \cdot 10^{-2}\) | \(0{,}45725 \cdot 10^{-3}\) | \(0{,}68815 \cdot 10^{1}\) | \(0{,}31466 \cdot 10^{-2}\) |
| \(8\) | \(-0{,}92872 \cdot 10^{-2}\) | \(0{,}15242 \cdot 10^{-3}\) | \(0{,}61932 \cdot 10^{2}\) | \(0{,}94396 \cdot 10^{-2}\) |
Mutlak hata her adımda yaklaşık üç katına çıkıyor (\(0{,}10487 \cdot 10^{-2}\), \(0{,}31466 \cdot 10^{-2}\), \(0{,}94396 \cdot 10^{-2}\)); bu, \(3^n\) çarpanının tahmin ettiği davranıştır. Gerçek değerler sıfıra giderken hesaplanan değerler \(n = 7\)’den itibaren negatife düşer ve \(n = 8\)’de bağıl hata \(60\)’ı aşar. \(\blacksquare\)
Aynı başlangıç değerleriyle bu kez çözümleri \(n\)’ye göre doğrusal olan bir bağıntıya bakalım.
Örnek 3.4 (Lineer hata büyümesi) \(c_1 + c_2 n\) biçimindeki diziler \(n \geq 2\) için
\[p_n = 2\, p_{n-1} - p_{n-2} \tag{2}\]
bağıntısını sağlar. \(p_0 = 1\) ve \(p_1 = \frac{1}{3}\) başlangıç değerleri beş-basamak yuvarlamayla gösterilip \(c_1\), \(c_2\) bu değerlerden bulunursa hata nasıl büyür?
Çözüm
Çözüm olduğu. \(p_n = c_1 + c_2 n\) için
\[2\left[c_1 + c_2 (n-1)\right] - \left[c_1 + c_2 (n-2)\right] = c_1 + c_2 n = p_n.\]
Gerçek sabitler. \(p_0 = 1\) ile \(c_1 = 1\), \(p_1 = \frac{1}{3}\) ile \(c_2 = \frac{1}{3} - 1 = -\frac{2}{3}\) bulunur; \(p_n = 1 - \frac{2}{3} n\).
Beş-basamak sabitler. \(p_0^* = 0{,}10000 \cdot 10^{1}\) ve \(p_1^* = 0{,}33333\) ile
\[c_1^* = 0{,}10000 \cdot 10^{1}, \qquad c_2^* = 0{,}33333 - 1 = -0{,}66667\]
olur; \(p_n^* = 1 - 0{,}66667\, n\).
Hatanın büyümesi.
\[E_n = \left\lvert p_n - p_n^* \right\rvert = \left\lvert 0{,}66667 - \frac{2}{3} \right\rvert n \approx 0{,}33333 \cdot 10^{-5} \cdot n.\]
Bu, \(E_n \approx C \cdot n \cdot E_0\) biçimidir (Tanım 3.3; \(C = 1\), \(E_0 = 0{,}33333 \cdot 10^{-5}\)). Hata büyümesi lineerdir, yaklaşım kararlıdır.
Karşılaştıralım: \(n = 8\)’de buradaki hata yaklaşık \(0{,}26667 \cdot 10^{-4}\)’tür; üstel örnekteki (Örnek 3.3) mutlak hata ise \(0{,}94396 \cdot 10^{-2}\), yani yaklaşık \(350\) kat büyüktür. Başlangıçtaki yuvarlama hatası iki örnekte de aynı mertebededir; farkı yaratan, bağıntının hatayı nasıl taşıdığıdır.
\(\blacksquare\)
3.3 Dizilerde Yakınsama Hızı
Bir algoritma çoğu zaman bir yaklaşımlar dizisi üretir. Dizinin yakınsaması yetmez; iki algoritmayı karşılaştırmak için dizinin limitine ne kadar hızlı yaklaştığını da ölçmek isteriz. Bunu, hızı bilinen bir sıfır dizisiyle karşılaştırarak yaparız.
Tanım 3.4 (Dizilerde Yakınsama Hızı) \((x_n)_{n=1}^{\infty}\) dizisi sıfıra (\(x_n \to 0\)), \((y_n)\) dizisi de bir \(y_0\) sayısına (\(y_n \to y_0\)) yakınsasın. Yeterince büyük \(n\) değerleri için
\[\left| y_n - y_0 \right| \leq K \left| x_n \right|\]
eşitsizliğini sağlayan bir \(K > 0\) sayısı varsa \(y_n \to y_0\) yakınsaması \(O(x_n)\) hızındadır denir ve \(y_n = y_0 + O(x_n)\) yazılır.
Yani \(y_n\) ile limiti arasındaki fark, sabit bir çarpan dışında, en az \(x_n\) kadar hızlı küçülür. Bu kitapta karşılaştırma dizisi olarak \(p > 0\) için \(x_n = \frac{1}{n^p}\) biçimindeki dizileri alıyoruz ve eşitsizliğin sağlandığı en büyük \(p\)’yi arıyoruz:
\[y_n = y_0 + O\left(\frac{1}{n^p}\right).\]
\(p\) ne kadar büyükse yakınsama o kadar hızlıdır.
Örnek 3.5 (İki dizinin hızını karşılaştırma) \(a_n = \dfrac{n+1}{n^2}\) ve \(b_n = \dfrac{n+3}{n^3}\) dizilerinin yakınsama hızlarını karşılaştırınız.
Çözüm
İki dizi de sıfıra yakınsar. Paydaki sabitleri \(n\) ile üstten sınırlayalım. \(n \geq 1\) için \(1 \leq n\) olduğundan
\[\left| a_n - 0 \right| = \frac{n+1}{n^2} \leq \frac{n+n}{n^2} = \frac{2n}{n^2} = 2 \cdot \frac{1}{n},\]
yani \(a_n = 0 + O\left(\frac{1}{n}\right)\). Benzer biçimde \(3 \leq 3n\) olduğundan
\[\left| b_n - 0 \right| = \frac{n+3}{n^3} \leq \frac{n+3n}{n^3} = \frac{4n}{n^3} = 4 \cdot \frac{1}{n^2},\]
yani \(b_n = 0 + O\left(\frac{1}{n^2}\right)\).
Bu üsler en büyüktür: \(a_n \geq \frac{1}{n}\) olduğundan \(p > 1\) için \(n^p a_n \geq n^{p-1} \to \infty\) ve hiçbir \(K\) yetmez; aynı nedenle \(b_n \geq \frac{1}{n^2}\) olduğundan \(b_n\) için \(p = 2\)’den büyük üs alınamaz.
Demek ki \((a_n)\) dizisi sıfıra \(\frac{1}{n}\) hızında, \((b_n)\) dizisi ise \(\frac{1}{n^2}\) hızında yakınsar; \((b_n)\) sıfıra \((a_n)\)’den daha hızlı yakınsar. İlk değerler (beş anlamlı basamakla):
| \(n\) | \(a_n\) | \(b_n\) |
|---|---|---|
| \(1\) | \(2{,}0000\) | \(4{,}0000\) |
| \(2\) | \(0{,}75000\) | \(0{,}62500\) |
| \(3\) | \(0{,}44444\) | \(0{,}22222\) |
| \(4\) | \(0{,}31250\) | \(0{,}10938\) |
| \(5\) | \(0{,}24000\) | \(0{,}064000\) |
| \(6\) | \(0{,}19444\) | \(0{,}041667\) |
| \(7\) | \(0{,}16327\) | \(0{,}029155\) |
\(n = 1\)’de \(b_n\) daha büyükken \(n = 2\)’den itibaren \(a_n\)’nin gerisinde kalır ve fark hızla açılır.
\(\blacksquare\)
3.4 Fonksiyonlarda Yakınsama Hızı
Nümerik türev ve integral formüllerinde yaklaşım bir adım uzunluğu \(h\)’ye bağlıdır ve \(h \to 0\) iken gerçek değere yaklaşır. Bu durumda hızı, \(h\)’nin bir kuvvetiyle ölçeriz.
Tanım 3.5 (Fonksiyonlarda Yakınsama Hızı) \(\lim\limits_{h \to 0} g(h) = 0\) ve \(\lim\limits_{h \to 0} f(h) = L\) olsun. Yeterince küçük \(h\) değerleri için
\[\left| f(h) - L \right| \leq K \left| g(h) \right|\]
eşitsizliğini sağlayan bir \(K > 0\) sayısı varsa \(f(h)\) fonksiyonu \(L\) sayısına \(O(g(h))\) hızında yakınsar denir ve \(f(h) = L + O(g(h))\) yazılır.
Yani \(h\) küçüldükçe \(f(h)\) ile \(L\) arasındaki fark, sabit bir çarpan dışında, en az \(g(h)\) kadar hızlı küçülür. Bu kitapta \(p > 0\) için \(g(h) = h^p\) biçimindeki fonksiyonları alıyor ve en büyük \(p\)’yi arıyoruz: \(f(h) = L + O(h^p)\). Örneğin \(p = 4\) ise \(h\) yarıya indiğinde hata kabaca \(16\)’da birine düşer.
Örnek 3.6 (Kosinüsün Taylor polinomuyla hız) Kosinüs fonksiyonunun \(h = 0\) civarındaki 3. mertebeden Taylor polinomunu kullanarak
\[\cos(h) + \frac{1}{2} h^2 = 1 + O(h^4)\]
olduğunu, yani \(h \to 0\) iken \(\cos(h) + \frac{1}{2} h^2\) fonksiyonunun \(1\) sayısına \(h^4\) hızında yakınsadığını gösteriniz.
Çözüm
\(\cos\) fonksiyonunun \(0\)’daki türevleri sırasıyla \(1, 0, -1, 0\) olduğundan 3. mertebeden Taylor polinomu \(P_3(h) = 1 - \frac{1}{2} h^2\)’dir. Dördüncü türev yine \(\cos\) olduğundan Taylor teoremi (Teorem 1.9) gereği
\[\cos(h) = 1 - \frac{1}{2} h^2 + \frac{\cos(\xi(h))}{24}\, h^4\]
olur; burada \(\xi(h)\), \(0\) ile \(h\) arasındadır. \(\left|\cos(\xi(h))\right| \leq 1\) olduğundan
\[0 \leq \left| \cos(h) + \frac{1}{2} h^2 - 1 \right| = \frac{h^4}{24} \left| \cos(\xi(h)) \right| \leq \frac{1}{24}\, h^4.\]
\(h \to 0\) iken sağ taraf sıfıra gittiğinden sıkıştırma teoremiyle \(\cos(h) + \frac{1}{2} h^2 \to 1\) olur. Bu eşitsizlik, \(K = \frac{1}{24}\) ve \(g(h) = h^4\) ile Tanım 3.5 koşuludur:
\[\cos(h) + \frac{1}{2} h^2 = 1 + O(h^4).\]
\(4\) en büyük üstür: \(\xi(h) \to 0\) olduğundan fark bölü \(h^4\) oranı \(\frac{\cos(\xi(h))}{24} \to \frac{1}{24} \neq 0\) olur; bu yüzden \(p > 4\) için fark bölü \(h^p\) sınırsız büyür. \(\blacksquare\)
3.5 Alıştırmalar
Aşağıdaki alıştırmalarda hata kestirimleri ve \(O\) gösterimiyle yakınsama hızları üzerinde çalışıyoruz.
\(\frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} - \cdots\) serisini Leibniz 1674’te buldu. İlk alıştırma bu serinin \(\pi\)’yi ne kadar yavaş verdiğini gösterir.
Alıştırma 3.1 (Leibniz serisiyle π) \(-1 < x \leq 1\) için
\[\arctan(x) = \lim_{n \to \infty} P_n(x), \qquad P_n(x) = \sum_{k=1}^{n} (-1)^{k+1} \frac{x^{2k-1}}{2k-1} \tag{3}\]
olduğuna göre, \(\tan\left(\frac{\pi}{4}\right) = 1\) eşitliğini kullanarak \(\left| 4 \cdot P_n(1) - \pi \right| < 10^{-3}\) eşitsizliğinin sağlanması için \(n\)’nin en az kaç olması gerektiğini belirleyiniz.
Çözüm
Seriyi kuralım. \(\tan\left(\frac{\pi}{4}\right) = 1\) olduğundan \(\frac{\pi}{4} = \arctan(1)\), yani
\[\pi = 4 \arctan(1) = 4 \sum_{k=1}^{\infty} \frac{(-1)^{k+1}}{2k-1} = 4\left(1 - \frac{1}{3} + \frac{1}{5} - \cdots\right).\]
Hatayı sınırlayalım. \(a_k = \frac{1}{2k-1}\) terimleri pozitif, azalan ve sıfıra yakınsaktır. Alterne seriler için hata kestirimine göre kısmi toplamın hatası atılan ilk terimi aşmaz (bkz. Analiz 2):
\[\left| P_n(1) - \arctan(1) \right| \leq a_{n+1} = \frac{1}{2(n+1) - 1} = \frac{1}{2n+1}.\]
Dolayısıyla
\[\left| 4 \cdot P_n(1) - \pi \right| = 4 \left| P_n(1) - \arctan(1) \right| \leq \frac{4}{2n+1}.\]
\(n\)’yi bulalım. Sağ tarafın \(10^{-3}\)’ten küçük olması yeterlidir:
\[\frac{4}{2n+1} < 10^{-3} \iff 4000 < 2n+1 \iff \frac{3999}{2} < n \iff 1999{,}5 < n.\]
Hata kestirimi \(n \geq 2000\) terim alındığında istenen hassasiyeti garanti eder.
Kestirim yalnız yeterli bir koşuldur. Doğrudan hesap, gerçek hatanın yaklaşık \(\frac{1}{n}\) olduğunu gösterir: \(n = 999\)’da \(1{,}0010 \cdot 10^{-3}\), \(n = 1000\)’de \(0{,}99999975 \cdot 10^{-3}\). Yani hata \(10^{-3}\)’ün altına ilk kez \(n = 1000\)’de iner. İki durumda da sonuç aynıdır: üç basamak için bile binlerce terim gerekir, bu seri \(\pi\)’yi hesaplamak için çok yavaştır. \(\blacksquare\)
John Machin 1706’da \(\frac{\pi}{4} = 4 \arctan\left(\frac{1}{5}\right) - \arctan\left(\frac{1}{239}\right)\) formülüyle \(\pi\)’nin 100 basamağını hesapladı. Küçük argümanlarda \(\arctan\) serisi çok daha hızlı yakınsar.
Alıştırma 3.2 (Machin formülüyle π) \(\frac{\pi}{4} = 4 \arctan\left(\frac{1}{5}\right) - \arctan\left(\frac{1}{239}\right)\) eşitliğini ve \(\arctan(x)\)’in (3)’teki Maclaurin serisi açılımını kullanarak \(\pi\) sayısına \(10^{-3}\) hassasiyetle yaklaşımda bulunmak için en az kaç terim kullanılmalıdır?
Çözüm
Seriyi kuralım. Eşitliği \(4\) ile çarpıp iki \(\arctan\)’ı da serisine açalım:
\[\pi = 16 \sum_{k=1}^{\infty} \frac{(-1)^{k+1}}{5^{2k-1}(2k-1)} - 4 \sum_{k=1}^{\infty} \frac{(-1)^{k+1}}{239^{2k-1}(2k-1)}.\]
İkinci serinin ilk terimi \(\frac{4}{239} \approx 0{,}016736\)’dır; \(10^{-3}\)’ten büyük olduğu için atılamaz. Bu terimden sonra kalan kısım ise hata kestirimi gereği
\[4 \cdot \frac{1}{239^{3} \cdot 3} \approx 0{,}98 \cdot 10^{-7}\]
ile sınırlıdır, yani ihmal edilebilir. Bu yüzden ikinci seriden yalnız ilk terimi alırız ve yaklaşımımız
\[\pi \approx 16 \sum_{k=1}^{n} \frac{(-1)^{k+1}}{5^{2k-1}(2k-1)} - \frac{4}{239}\]
olur. Belirleyici olan, birinci seriden kaç terim gerektiğidir.
Hatayı sınırlayalım. Birinci serinin terimleri \(\frac{1}{5^{2k-1}(2k-1)}\) pozitif, azalan ve sıfıra yakınsaktır. Önceki alıştırmadaki kestirimle (Alıştırma 3.1), \(n\) terimden sonra kalan kısmın \(16\) katı
\[16 \cdot \frac{1}{5^{2n+1}(2n+1)}\]
ile sınırlıdır. Bunun \(10^{-3}\)’ten küçük olması gerekir:
\[\frac{16}{5^{2n+1}(2n+1)} < 10^{-3} \iff 16000 < (2n+1) \cdot 5^{2n+1}.\]
\(n\)’yi bulalım.
\[\begin{aligned} n = 1:&\quad 3 \cdot 5^{3} = 375 < 16000,\\[1mm] n = 2:&\quad 5 \cdot 5^{5} = 15625 < 16000,\\[1mm] n = 3:&\quad 7 \cdot 5^{7} = 546875 > 16000. \end{aligned}\]
Eşitsizliğin sağlandığı ilk değer \(n = 3\)’tür. \(n = 3\) için iki kalanın toplamı da \(2{,}93 \cdot 10^{-5} + 0{,}98 \cdot 10^{-7} < 10^{-3}\) olur. Demek ki birinci seriden \(3\) terim, ikinci seriden \(1\) terim yeterlidir:
\[\begin{aligned} \pi &\approx 16\left(\frac{1}{5} - \frac{1}{3 \cdot 5^{3}} + \frac{1}{5 \cdot 5^{5}}\right) - \frac{4}{239}\\[1mm] &= 3{,}1583573 - 0{,}0167364 = 3{,}1416209. \end{aligned}\]
Gerçek hata \(\left| \pi - 3{,}1416209 \right| \approx 2{,}8 \cdot 10^{-5}\)’tir. \(n = 2\)’de kestirim \(1{,}024 \cdot 10^{-3}\) verdiği için hassasiyeti garanti etmez (gerçek hata \(0{,}996 \cdot 10^{-3}\) ile sınırın hemen altında kalır). Leibniz serisinin gerektirdiği binlerce terimle (Alıştırma 3.1) karşılaştırınca, küçük argümanın yakınsamayı ne kadar hızlandırdığı görülür. \(\blacksquare\)
Sıradaki dört alıştırmada dizilerde yakınsama hızını (Tanım 3.4) kullanıyoruz.
Alıştırma 3.3 (sin(1/n) dizisinin hızı) \(a_n = \sin\left(\frac{1}{n}\right)\) dizisinin yakınsama hızını belirleyiniz.
Çözüm
\(\frac{1}{n} \to 0\) ve \(\sin\) sürekli olduğundan \(\lim\limits_{n \to \infty} \sin\left(\frac{1}{n}\right) = \sin 0 = 0\)’dır.
Her \(x\) için \(\left| \sin x \right| \leq \left| x \right|\)’dir: ortalama değer teoremine (Teorem 1.4) göre \(\sin x - \sin 0 = \cos(\xi)\, x\) ve \(\left| \cos \xi \right| \leq 1\). Buna göre
\[\left| a_n - 0 \right| = \left| \sin\left(\frac{1}{n}\right) \right| \leq \frac{1}{n} = 1 \cdot \frac{1}{n^1},\]
yani
\[\sin\left(\frac{1}{n}\right) = 0 + O\left(\frac{1}{n}\right).\]
\(p = 1\) en büyük üstür: \(n \sin\left(\frac{1}{n}\right) \to 1\) olduğundan \(p > 1\) için \(n^p \sin\left(\frac{1}{n}\right) = n^{p-1} \cdot n \sin\left(\frac{1}{n}\right) \to \infty\). \(\blacksquare\)
Alıştırma 3.4 (sin(1/n²) dizisinin hızı) \(b_n = \sin\left(\frac{1}{n^2}\right)\) dizisinin yakınsama hızını belirleyiniz.
Çözüm
\(\frac{1}{n^2} \to 0\) olduğundan \(\lim\limits_{n \to \infty} \sin\left(\frac{1}{n^2}\right) = 0\)’dır. \(\left| \sin x \right| \leq \left| x \right|\) eşitsizliğini \(x = \frac{1}{n^2}\) ile kullanırsak
\[\left| b_n - 0 \right| = \left| \sin\left(\frac{1}{n^2}\right) \right| \leq 1 \cdot \frac{1}{n^2},\]
yani
\[\sin\left(\frac{1}{n^2}\right) = 0 + O\left(\frac{1}{n^2}\right).\]
\(n^2 \sin\left(\frac{1}{n^2}\right) \to 1\) olduğundan \(p = 2\)’den büyük üs alınamaz. \(\blacksquare\)
Alıştırma 3.5 (sin²(1/n) dizisinin hızı) \(c_n = \left(\sin \frac{1}{n}\right)^2\) dizisinin yakınsama hızını belirleyiniz.
Çözüm
\(\sin\left(\frac{1}{n}\right) \to 0\) olduğundan karesi de sıfıra gider. \(\left| \sin x \right| \leq \left| x \right|\) eşitsizliğinin iki tarafının karesini alırsak
\[\left| c_n - 0 \right| = \left(\sin \frac{1}{n}\right)^2 \leq \left(\frac{1}{n}\right)^2 = \frac{1}{n^2},\]
yani
\[\left(\sin \frac{1}{n}\right)^2 = 0 + O\left(\frac{1}{n^2}\right).\]
\(n^2 c_n = \left(n \sin \frac{1}{n}\right)^2 \to 1\) olduğundan \(p = 2\) en büyük üstür. \(\blacksquare\)
Alıştırma 3.6 (ln(n+1) − ln(n) dizisinin hızı) \(d_n = \ln(n+1) - \ln(n)\) dizisinin yakınsama hızını belirleyiniz.
Çözüm
Logaritmanın özelliği ve sürekliliğiyle
\[\lim_{n \to \infty} \left(\ln(n+1) - \ln(n)\right) = \lim_{n \to \infty} \ln\left(\frac{n+1}{n}\right) = \ln 1 = 0.\]
\(x > 0\) için \(\ln(1 + x) \leq x\)’tir: ortalama değer teoremiyle \(\ln(1+x) - \ln 1 = \frac{x}{1 + \xi}\), \(0 < \xi < x\), ve \(\frac{1}{1+\xi} < 1\). Bunu \(x = \frac{1}{n}\) ile kullanalım:
\[\left| d_n - 0 \right| = \ln\left(\frac{n+1}{n}\right) = \ln\left(1 + \frac{1}{n}\right) \leq \frac{1}{n}.\]
Buradan
\[\ln(n+1) - \ln(n) = 0 + O\left(\frac{1}{n}\right)\]
bulunur. \(n \to \infty\) iken
\[n \ln\left(1 + \frac{1}{n}\right) = \ln\left(1 + \frac{1}{n}\right)^n \to \ln e = 1\]
olduğundan \(p = 1\) en büyük üstür. \(\blacksquare\)
Sonraki dört alıştırmada fonksiyonlarda yakınsama hızını (Tanım 3.5) Maclaurin açılımlarıyla belirliyoruz. Açılımda sıfıra en yavaş giden terim, yani \(x\)’in en küçük kuvvetli terimi, hızı belirler. \(K\) sabitini ise kalan terimin Taylor teoremindeki (Teorem 1.9) biçiminden okuruz; \(\xi\) her seferinde \(0\) ile \(x\) arasındadır.
Alıştırma 3.7 (sin x / x fonksiyonunun hızı) \(\lim\limits_{x \to 0} \dfrac{\sin x}{x} = 1\) yakınsamasının hızını belirleyiniz.
Çözüm
Açılım. \(\sin x = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \cdots\) olduğundan
\[\frac{\sin x}{x} = 1 - \frac{x^2}{6} + \frac{x^4}{120} - \cdots\]
Sıfıra en yavaş giden terim \(x^2\)’li terimdir; hız \(x^2\)’dir.
Sabit. Taylor teoremiyle \(\sin x = x - \frac{x^3}{6} + \frac{\cos(\xi)}{120}\, x^5\). Buna göre \(0 < \left| x \right| \leq 1\) için
\[\left| \frac{\sin x}{x} - 1 \right| = \left| -\frac{x^2}{6} + \frac{\cos(\xi)}{120}\, x^4 \right| \leq \frac{x^2}{6} + \frac{x^2}{120} = \frac{7}{40}\, x^2;\]
burada \(\left| \cos \xi \right| \leq 1\) ve \(x^4 \leq x^2\) kullanıldı.
Demek ki \(K = \frac{7}{40}\) ile
\[\frac{\sin x}{x} = 1 + O(x^2).\]
\(\left(\frac{\sin x}{x} - 1\right) / x^2 \to -\frac{1}{6} \neq 0\) olduğundan \(p = 2\) en büyük üstür. \(\blacksquare\)
Alıştırma 3.8 ((1 − cos x) / x fonksiyonunun hızı) \(\lim\limits_{x \to 0} \dfrac{1 - \cos x}{x} = 0\) yakınsamasının hızını belirleyiniz.
Çözüm
Açılım. \(\cos x = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \cdots\) olduğundan
\[\frac{1 - \cos x}{x} = \frac{1 - \left(1 - \frac{x^2}{2} + \frac{x^4}{24} - \cdots\right)}{x} = \frac{x}{2} - \frac{x^3}{24} + \cdots\]
En yavaş giden terim \(x\)’li terimdir.
Sabit. Taylor teoremiyle \(\cos x = 1 - \frac{x^2}{2} + \frac{\cos(\xi)}{24}\, x^4\). \(0 < \left| x \right| \leq 1\) için
\[\left| \frac{1 - \cos x}{x} - 0 \right| = \left| \frac{x}{2} - \frac{\cos(\xi)}{24}\, x^3 \right| \leq \frac{\left| x \right|}{2} + \frac{\left| x \right|}{24} = \frac{13}{24} \left| x \right|;\]
burada \(\left| x \right|^3 \leq \left| x \right|\) kullanıldı.
Demek ki
\[\frac{1 - \cos x}{x} = 0 + O(x).\]
Oran \(\frac{1 - \cos x}{x^2} \to \frac{1}{2} \neq 0\) olduğundan \(p = 1\) en büyük üstür. \(\blacksquare\)
Alıştırma 3.9 ((sin x − x cos x) / x fonksiyonunun hızı) \(\lim\limits_{x \to 0} \dfrac{\sin x - x \cos x}{x} = 0\) yakınsamasının hızını belirleyiniz.
Çözüm
Açılım. İki açılımı yerine yazıp aynı kuvvetleri toplayalım:
\[\begin{aligned} \frac{\sin x - x \cos x}{x} &= \frac{x - \frac{x^3}{6} + \frac{x^5}{120} - \cdots - x\left(1 - \frac{x^2}{2} + \frac{x^4}{24} - \cdots\right)}{x}\\[1mm] &= -\frac{x^2}{6} + \frac{x^2}{2} + \frac{x^4}{120} - \frac{x^4}{24} + \cdots\\[1mm] &= \frac{x^2}{3} - \frac{x^4}{30} + \cdots \end{aligned}\]
En yavaş giden terim \(x^2\)’li terimdir.
Sabit. Taylor teoremiyle
\[\sin x = x - \frac{x^3}{6} + \frac{\cos(\xi_1)}{120}\, x^5, \qquad \cos x = 1 - \frac{x^2}{2} + \frac{\cos(\xi_2)}{24}\, x^4.\]
Bunları yerine yazarsak
\[\frac{\sin x - x \cos x}{x} = \frac{x^2}{3} + \left(\frac{\cos(\xi_1)}{120} - \frac{\cos(\xi_2)}{24}\right) x^4\]
olur. \(0 < \left| x \right| \leq 1\) için
\[\left| \frac{\sin x - x \cos x}{x} \right| \leq \frac{x^2}{3} + \left(\frac{1}{120} + \frac{1}{24}\right) x^2 = \frac{23}{60}\, x^2;\]
burada \(x^4 \leq x^2\) kullanıldı.
Demek ki
\[\frac{\sin x - x \cos x}{x} = 0 + O(x^2).\]
Fonksiyon bölü \(x^2\) oranı \(\frac{1}{3} \neq 0\)’a gittiğinden \(p = 2\) en büyük üstür. \(\blacksquare\)
Alıştırma 3.10 ((1 − eˣ) / x fonksiyonunun hızı) \(\lim\limits_{x \to 0} \dfrac{1 - e^x}{x} = -1\) yakınsamasının hızını belirleyiniz.
Çözüm
Açılım. \(e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots\) olduğundan
\[\frac{1 - e^x}{x} = \frac{1 - \left(1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \cdots\right)}{x} = -1 - \frac{x}{2} - \frac{x^2}{6} - \cdots\]
\(-1\)’den sonra en yavaş giden terim \(x\)’li terimdir.
Sabit. Taylor teoremiyle \(e^x = 1 + x + \frac{e^{\xi}}{2}\, x^2\). \(0 < \left| x \right| \leq 1\) için \(e^{\xi} \leq e\) olduğundan
\[\left| \frac{1 - e^x}{x} - (-1) \right| = \frac{e^{\xi}}{2} \left| x \right| \leq \frac{e}{2} \left| x \right|.\]
Demek ki
\[\frac{1 - e^x}{x} = -1 + O(x).\]
Fark bölü \(x\) oranı \(-\frac{1}{2} \neq 0\)’a gittiğinden \(p = 1\) en büyük üstür. \(\blacksquare\)
Fibonacci dizisi Leonardo Fibonacci’nin 1202 tarihli Liber Abaci’sinde geçer. Son alıştırmada bu dizinin ardışık terimlerinin oranının limitini buluyoruz.
Alıştırma 3.11 (Fibonacci oranları ve altın oran) \(F_0 = 1\), \(F_1 = 1\) ve \(n \geq 0\) için \(F_{n+2} = F_{n+1} + F_n\) ile tanımlanan Fibonacci dizisini ele alalım ve \(x_n = \frac{F_{n+1}}{F_n}\) olsun. \(\lim\limits_{n \to \infty} x_n = x\) yakınsamasında limitin altın oran olarak bilinen \(x = \frac{1 + \sqrt{5}}{2}\) sayısı olduğunu gösteriniz.
Çözüm
Oranın bağıntısı. \(x_{n+1}\)’i \(x_n\) cinsinden yazalım:
\[x_{n+1} = \frac{F_{n+2}}{F_{n+1}} = \frac{F_{n+1} + F_n}{F_{n+1}} = 1 + \frac{F_n}{F_{n+1}} = 1 + \frac{1}{x_n}.\]
Limit denklemi. \(x_n \to x\) ise \(x_{n+1} \to x\)’tir. Bağıntıda limit alırsak (\(x \neq 0\) olduğu aşağıda görülüyor)
\[x = 1 + \frac{1}{x} \implies x^2 - x - 1 = 0.\]
Diskriminant \(\Delta = 1 + 4 = 5 > 0\) olduğundan iki kök vardır:
\[x_1 = \frac{1 - \sqrt{5}}{2} < 0, \qquad x_2 = \frac{1 + \sqrt{5}}{2} > 0.\]
Doğru kökü seçelim. Dizinin ilk terimleri
\[(F_n) = (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \dots),\]
\[(x_n) = \left(1, 2, \frac{3}{2}, \frac{5}{3}, \frac{8}{5}, \frac{13}{8}, \frac{21}{13}, \frac{34}{21}, \frac{55}{34}, \frac{89}{55}, \frac{144}{89}, \dots\right)\]
olur. Fibonacci sayıları pozitif ve \(n \geq 1\) için \(F_{n+1} = F_n + F_{n-1} \geq F_n\) olduğundan her \(n\) için \(x_n \geq 1\)’dir. Limit de \(x \geq 1\) olmalıdır; negatif kök elenir ve
\[x = x_2 = \frac{1 + \sqrt{5}}{2} \approx 1{,}618034\]
bulunur.
Yakınsama hızı. \(\varphi = \frac{1 + \sqrt{5}}{2}\) diyelim; \(\varphi = 1 + \frac{1}{\varphi}\)’dir. Bağıntıdan
\[x_{n+1} - \varphi = \left(1 + \frac{1}{x_n}\right) - \left(1 + \frac{1}{\varphi}\right) = \frac{\varphi - x_n}{x_n\, \varphi}\]
ve \(x_n \geq 1\) olduğundan \(\left| x_{n+1} - \varphi \right| \leq \frac{1}{\varphi} \left| x_n - \varphi \right|\) elde edilir. Bunu tekrar tekrar uygularsak (\(\left| x_0 - \varphi \right| = \varphi - 1 = \frac{1}{\varphi}\))
\[\left| x_n - \varphi \right| \leq \frac{1}{\varphi^{n}} \left| x_0 - \varphi \right| = \frac{1}{\varphi^{n+1}}.\]
\(\frac{1}{\varphi} \approx 0{,}618 < 1\) olduğundan bu, limitin gerçekten var olduğunu da gösterir: hata her adımda en az \(0{,}618\) çarpanıyla küçülür. Örneğin \(x_{10} = \frac{144}{89} \approx 1{,}617978\) ve \(\left| x_{10} - \varphi \right| \approx 0{,}56 \cdot 10^{-4}\)’tür. \(\blacksquare\)
Yakınsama hızını ölçecek dili kurduk. Bir sonraki bölümde ilk kök bulma algoritmasını ve hata sınırını bu dille inceliyoruz: İkiye Bölme Metodu.