4 İkiye Bölme Metodu
Nümerik analizin en temel uğraşlarından biri \(f(x) = 0\) denklemini çözmektir. Çarpanlarına ayrılabilen bir polinomun köklerini tam olarak buluruz; ama \(x^3 + 4x^2 - 10 = 0\) ya da \(\sqrt{x} - \cos x = 0\) gibi denklemlerde kökü kapalı bir formülle yazmak ya imkânsızdır ya da pratik değildir. Bu durumda köke istediğimiz kadar yaklaşan bir sayı dizisi üretmeye razı oluruz. Bu kısımda böyle dört yöntem göreceğiz; ilki ve en sağlamı ikiye bölme metodudur.
Yöntemin dayandığı ara değer teoreminin ilk analitik ispatı Bolzano’nun 1817 tarihli çalışmasıdır. Fikir basittir: uç noktalarında işaret değiştiren sürekli bir fonksiyonun kökünü içeren aralığı her adımda ikiye bölüp kökün bulunduğu yarıyı tutarız.
Önce neyi aradığımızı kesinleştirelim.
Tanım 4.1 (Kök) Bir \(f\) fonksiyonu verilsin. \(f(p) = 0\) eşitliğini sağlayan \(p\) reel sayısına \(f(x) = 0\) denkleminin kökü ya da çözümü denir.
Yani kök, \(f\)’nin grafiğinin \(x\)-eksenini kestiği noktanın apsisidir.
Tanım 4.2 (Yaklaşık Kök) \(f(x) = 0\) denkleminin kökü tam olarak bulunamıyorsa, \(|f(p^*)|\) değerini yeterince küçük yapan bir \(p^*\) sayısına denklemin bir yaklaşık kökü denir.
Yani yaklaşık kök, denklemi tam değil ama istenen ölçüde sağlayan bir sayıdır. Bu bölümden itibaren göreceğimiz yöntemler \(p\) köküne yaklaşan bir \((p_n)\) dizisi üretir ve sonlu sayıda adımdan sonra durup son terimi yaklaşık kök olarak verir.
4.1 İkiye Bölme Metodu
İkiye bölme (yarılama) metodu, kapalı aralıkta sürekli fonksiyonlar için ara değer teoremine (Teorem 1.7) dayanır. \(f \in C[a, b]\) ve \(f(a) \cdot f(b) < 0\) ise \(f\) uç noktalarda zıt işaretlidir ve teorem \((a, b)\) içinde en az bir \(p\) kökü bulunduğunu söyler.
Tanım 4.3 (İkiye Bölme Metodu) \(f \in C[a, b]\) ve \(f(a) \cdot f(b) < 0\) olsun. \(a_1 = a\), \(b_1 = b\) alınır ve \(n = 1, 2, \dots\) için
- \([a_n, b_n]\) aralığının orta noktası \(p_n = \dfrac{a_n + b_n}{2}\) bulunur;
- \(f(p_n) = 0\) ise \(p = p_n\) denklemin köküdür ve süreç durur;
- \(f(p_n)\) ile \(f(a_n)\) aynı işaretliyse \(a_{n+1} = p_n\), \(b_{n+1} = b_n\);
- \(f(p_n)\) ile \(f(b_n)\) aynı işaretliyse \(a_{n+1} = a_n\), \(b_{n+1} = p_n\)
alınır. Bu süreçle elde edilen \((p_n)\) dizisi kök için ikiye bölme metodu yaklaşımlarıdır.
Yani her adımda aralığın ortasına bakıp, fonksiyonun işaret değiştirdiği yarıyı saklarız. \(f(p_n) \neq 0\) ise \(f(p_n)\), \(f(a_n)\) ile \(f(b_n)\)’den tam birisiyle aynı işaretlidir, çünkü bu ikisi zıt işaretlidir.
Seçim kuralının neden doğru olduğunu ara değer teoremi söyler. \(f(p_n)\) ile \(f(a_n)\) aynı işaretliyse \(f(p_n)\) ile \(f(b_n)\) zıt işaretlidir; teorem \([p_n, b_n]\) üzerinde uygulanınca \(p \in (p_n, b_n)\) olan bir kök bulunur. Öbür durumda aynı akıl yürütme \(p \in (a_n, p_n)\) verir. Böylece her \([a_n, b_n]\) aralığı bir kök içerir ve bir öncekinin yarısı uzunluğundadır.
4.2 Durma Kriterleri
Süreç sonsuza kadar sürmez; sonlu sayıda adımdan sonra bulunan değer köke bir yaklaşım olarak kabul edilir. Bunun için yaklaşımın istenen \(\varepsilon\) hassaslığına ulaştığını sınayan bir ölçüt gerekir.
Tanım 4.4 (Durma Kriterleri) \(\varepsilon > 0\) verilsin ve \(p_1, p_2, \dots, p_N\) köke yapılan ardışık yaklaşımlar olsun. Aşağıdaki eşitsizliklerden biri sağlandığında yaklaşımın istenen hassaslıkta olduğu kabul edilir ve süreç durdurulur: \[ |p_N - p_{N-1}| < \varepsilon, \tag{1} \] \[ \frac{|p_N - p_{N-1}|}{|p_N|} < \varepsilon, \quad p_N \neq 0, \tag{2} \] \[ |f(p_N)| < \varepsilon. \tag{3} \] Bu eşitsizliklere sırasıyla (1), (2) ve (3) numaralı durma kriteri denir.
Yani (1) numaralı kriter ardışık iki yaklaşımın farkına, (2) numaralı kriter bu farkın son yaklaşıma oranına, (3) numaralı kriter ise denklemin ne ölçüde sağlandığına bakar. (2) numaralı kriter, köke dair bilgi olmadan bağıl hatayı (Tanım 2.4) test etmenin bir yoludur.
Üç kriter eşit derecede güvenilir değildir. (1) numaralı kriter aldatıcı olabilir, çünkü ardışık farkları sıfıra giden ama ıraksak olan diziler vardır. Örneğin \(p_n = 1 + \frac{1}{2} + \dots + \frac{1}{n}\) dizisinde \(|p_n - p_{n-1}| = \frac{1}{n} \to 0\) iken \(p_n \to \infty\)’dur; \(\varepsilon = 10^{-3}\) alınırsa (1) numaralı kriter \(N = 1001\)’de sağlanır, oysa dizinin yaklaştığı bir sayı yoktur. (3) numaralı kriter de aldatıcı olabilir: \(f(p_N)\) sıfıra çok yakın olduğu hâlde \(p_N\) gerçek kökten uzak olabilir.
Örnek 4.1 (Küçük Fonksiyon Değeri, Uzak Kök) \(f(x) = (x - 1)^9\) fonksiyonunun tek kökü \(p = 1\)’dir. \(p^* = 1{,}4\) için (3) numaralı durma kriterini \(\varepsilon = 10^{-3}\) ile sınayınız ve \(p^*\)’ın köke uzaklığını bulunuz.
Çözüm
\(f(1{,}4) = 0{,}4^9 = 0{,}000262144\) olduğundan \[ |f(p^*)| = 0{,}262144 \cdot 10^{-3} < 10^{-3} \] ve (3) numaralı kriter \(p^*\)’ı yaklaşık kök olarak kabul eder. Oysa \(|p^* - p| = 0{,}4\)’tür; bağıl hata da \(0{,}4 / 1 = 0{,}4\), yani yüzde kırktır.
Sorun fonksiyonun kök çevresinde çok yatık olmasıdır. \(|f(x)| < 10^{-3}\) eşitsizliği \(|x - 1|^9 < 10^{-3}\), yani \(|x - 1| < 10^{-1/3} \approx 0{,}4642\) demektir. Dolayısıyla \((0{,}5358;\ 1{,}4642)\) aralığındaki her sayı (3) numaralı kriteri geçer.
Kökün çevresinde bu kadar yatık bir fonksiyonda \(|f(p_N)|\)’nin küçüklüğü \(p_N\)’nin köke yakınlığı hakkında hiçbir şey söylemez. \(\blacksquare\)
Bu nedenlerle \(f\) ve \(p\) hakkında ek bir bilgi yoksa bağıl hataya yakın sonuç veren (2) numaralı durma kriterini kullanmak daha uygundur.
4.3 Başlangıç Aralığının Seçimi
Yöntemi başlatmak için önce \(f(a) \cdot f(b) < 0\) sağlayan bir \([a, b]\) aralığı bulunmalıdır. Her adım aralığı yarıya indirdiğinden, başlangıç aralığı ne kadar kısa olursa istenen hassaslığa o kadar az işlemle ulaşılır.
Örneğin \(f(x) = 2x^3 - x^2 + x - 1\) için \(f(-4) = -149\), \(f(4) = 115\), \(f(0) = -1\) ve \(f(1) = 1\)’dir. Hem \(f(-4) \cdot f(4) < 0\) hem de \(f(0) \cdot f(1) < 0\) sağlanır, ama başlangıç aralığı olarak \([-4, 4]\) yerine \([0, 1]\) almak daha uygundur. Uzunluğu \(8\) olan aralık, uzunluğu \(1\) olan aralığa ancak \(8 \to 4 \to 2 \to 1\) diye üç adımda iner; yani \([-4, 4]\) ile başlamak her hassaslık için üç fazla iterasyon demektir.
- Aralığı denetle. \(f\)’nin \([a, b]\) üzerinde sürekli ve \(f(a) \cdot f(b) < 0\) olduğunu göster; \(a_1 = a\), \(b_1 = b\) al.
- Orta noktayı bul. \(p_n = \frac{a_n + b_n}{2}\) ve \(f(p_n)\) değerini hesapla.
- Kökü içeren yarıyı seç. \(f(p_n)\), \(f(a_n)\) ile aynı işaretliyse \(a_{n+1} = p_n\), \(b_{n+1} = b_n\); değilse \(a_{n+1} = a_n\), \(b_{n+1} = p_n\).
- Durma kriterini sına. Kriter sağlanıyorsa \(p \approx p_n\); sağlanmıyorsa \(n\)’yi bir artırıp 2. adıma dön. Değerleri bir tabloda topla.
Örnek 4.2 (Bir Kübik Denklemin Kökü) \(f(x) = x^3 + 4x^2 - 10 = 0\) denkleminin \([1, 2]\) aralığında bir kökü olduğunu gösteriniz. İkiye bölme metodunu ve (2) numaralı durma kriterini kullanarak bu köke en az \(10^{-4}\) hassaslıkta bir yaklaşımda bulununuz.
Çözüm
\(f\) polinom olduğundan \([1, 2]\) üzerinde süreklidir. \(f(1) = -5 < 0\) ve \(f(2) = 14 > 0\) olduğundan ara değer teoremi gereği \((1, 2)\) aralığında \(f(p) = 0\) sağlayan en az bir \(p\) vardır.
İlk üç adım şöyledir:
- \(p_1 = \frac{1 + 2}{2} = 1{,}5\) ve \(f(1{,}5) = 2{,}375 > 0\). Bu değer \(f(b_1)\) ile aynı işaretli olduğundan \(p \in (1;\ 1{,}5)\) ve yeni aralık \([1;\ 1{,}5]\)’tir.
- \(p_2 = \frac{1 + 1{,}5}{2} = 1{,}25\) ve \(f(1{,}25) = -1{,}796875 < 0\). Bu kez \(f(a_2)\) ile aynı işaretli olduğundan \(p \in (1{,}25;\ 1{,}5)\).
- \(p_3 = \frac{1{,}25 + 1{,}5}{2} = 1{,}375\) ve \(f(1{,}375) = 0{,}162109375 > 0\), dolayısıyla \(p \in (1{,}25;\ 1{,}375)\).
Aynı işlemler sürdürülerek aşağıdaki tablo elde edilir. Hesaplar yuvarlama yapılmadan yürütülmüş, tablodaki değerler dokuz basamağa yuvarlanmıştır.
| \(n\) | \(a_n\) | \(b_n\) | \(p_n\) | \(f(p_n)\) | \(\frac{\lvert p_n - p_{n-1}\rvert}{\lvert p_n\rvert}\) |
|---|---|---|---|---|---|
| \(1\) | \(1\) | \(2\) | \(1{,}5\) | \(2{,}375\) | |
| \(2\) | \(1\) | \(1{,}5\) | \(1{,}25\) | \(-1{,}796875\) | \(0{,}2\) |
| \(3\) | \(1{,}25\) | \(1{,}5\) | \(1{,}375\) | \(0{,}162109375\) | \(0{,}090909091\) |
| \(4\) | \(1{,}25\) | \(1{,}375\) | \(1{,}3125\) | \(-0{,}848388672\) | \(0{,}047619048\) |
| \(5\) | \(1{,}3125\) | \(1{,}375\) | \(1{,}34375\) | \(-0{,}350982666\) | \(0{,}023255814\) |
| \(6\) | \(1{,}34375\) | \(1{,}375\) | \(1{,}359375\) | \(-0{,}096408844\) | \(0{,}011494253\) |
| \(7\) | \(1{,}359375\) | \(1{,}375\) | \(1{,}3671875\) | \(0{,}032355785\) | \(0{,}005714286\) |
| \(8\) | \(1{,}359375\) | \(1{,}3671875\) | \(1{,}36328125\) | \(-0{,}032149971\) | \(0{,}002865330\) |
| \(9\) | \(1{,}36328125\) | \(1{,}3671875\) | \(1{,}365234375\) | \(0{,}000072025\) | \(0{,}001430615\) |
| \(10\) | \(1{,}36328125\) | \(1{,}365234375\) | \(1{,}364257813\) | \(-0{,}016046691\) | \(0{,}000715820\) |
| \(11\) | \(1{,}364257813\) | \(1{,}365234375\) | \(1{,}364746094\) | \(-0{,}007989263\) | \(0{,}000357782\) |
| \(12\) | \(1{,}364746094\) | \(1{,}365234375\) | \(1{,}364990234\) | \(-0{,}003959102\) | \(0{,}000178859\) |
| \(13\) | \(1{,}364990234\) | \(1{,}365234375\) | \(1{,}365112305\) | \(-0{,}001943659\) | \(0{,}000089421\) |
\(n = 12\)’de bağıl fark \(0{,}000178859 > 10^{-4}\) iken \(n = 13\)’te \[ \frac{|p_{13} - p_{12}|}{|p_{13}|} = 0{,}000089421 = 0{,}89421 \cdot 10^{-4} < 10^{-4} \] olur. (2) numaralı kriter 13 iterasyon sonunda sağlandığından kök için \(p \approx p_{13} = 1{,}365112305\) yaklaşımını buluruz.
Tabloda \(|f(p_9)| < |f(p_{13})|\) olduğuna dikkat edin. Bu, \(p_9\)’un köke \(p_{13}\)’ten daha yakın olduğunu düşündürür; ama kökün gerçek değeri bilinmedikçe bundan emin olamayız. \(\blacksquare\)
4.4 Yakınsama ve Hata Sınırı
İkiye bölme metodu kolay anlaşılır; ama \(|p - p_n|\)’yi istenen küçüklüğe indirecek \(n\) bazen çok büyüktür, yani köke yakınsama yavaştır. Buna karşılık yöntem hiçbir ek koşul istemeden köke er ya da geç istenen hassaslıkta yaklaşır. Bunu ve hızını şu teorem verir.
Teorem 4.1 (İkiye Bölme Metodunun Yakınsaması) \(f \in C[a, b]\) ve \(f(a) \cdot f(b) < 0\) olsun. İkiye bölme metoduyla elde edilen \((p_n)_{n=1}^{\infty}\) dizisi \(f\)’nin \((a, b)\) aralığındaki bir \(p\) köküne yakınsar ve her \(n \geq 1\) için \[ |p_n - p| \leq \frac{b - a}{2^n} \] eşitsizliği sağlanır.
İspat
Bir \(N\) adımında \(f(p_N) = 0\) olursa süreç durur ve \(p = p_N\) kesin köktür. \(p_N\) bütün \([a_n, b_n]\) (\(n \leq N\)) aralıklarında yattığından aşağıdaki 4. adımın hesabı \(n \leq N\) için aynen geçer. Bu yüzden hiçbir adımda \(f(p_n) = 0\) olmadığını varsayabiliriz. Ayrıca \(f(a) < 0 < f(b)\) alabiliriz; aksi hâlde \(-f\) ile çalışırız, çünkü \(-f\)’nin kökleri ve işaret karşılaştırmaları, dolayısıyla üretilen dizi, \(f\)’ninkilerle aynıdır.
1. İşaretler korunur. Her \(n\) için \(f(a_n) < 0 < f(b_n)\)’dir. Gerçekten \(n = 1\) için bu varsayımdır; \(a_{n+1}\) ya \(a_n\)’dir ya da \(f(p_n)\)’nin \(f(a_n)\) ile aynı işaretli, yani negatif olduğu \(p_n\)’dir. Benzer biçimde \(f(b_{n+1}) > 0\)’dır.
2. Aralık her adımda yarıya iner. \(p_n\) orta nokta olduğundan \(b_{n+1} - a_{n+1} = \frac{b_n - a_n}{2}\)’dir. \(b_1 - a_1 = b - a\) olduğundan tümevarımla \[ b_n - a_n = \frac{b - a}{2^{n-1}}, \qquad n \geq 1. \]
3. Aralıklar bir köke büzülür. Kural gereği \(a_n \leq a_{n+1} \leq b_{n+1} \leq b_n\)’dir. \((a_n)\) azalmayan ve \(b\) ile üstten sınırlı, \((b_n)\) artmayan ve \(a\) ile alttan sınırlı olduğundan ikisi de yakınsaktır (bkz. Analiz 1). 2. adım gereği \(b_n - a_n \to 0\) olduğundan limitleri aynıdır; bu ortak limite \(p\) diyelim. Her \(n\) için \(a_n \leq p \leq b_n\)’dir. \(f\) sürekli olduğundan 1. adımdan \[ f(p) = \lim_{n \to \infty} f(a_n) \leq 0, \qquad f(p) = \lim_{n \to \infty} f(b_n) \geq 0 \] bulunur; yani \(f(p) = 0\)’dır. \(f(a) \neq 0\) ve \(f(b) \neq 0\) olduğundan \(p \in (a, b)\)’dir.
4. Hata sınırı. \(p\) ve \(p_n\) aynı \([a_n, b_n]\) aralığındadır ve \(p_n\) bu aralığın orta noktasıdır. Orta noktanın aralıktaki herhangi bir noktaya uzaklığı aralık uzunluğunun yarısını aşmaz, dolayısıyla \[ |p_n - p| \leq \frac{b_n - a_n}{2} = \frac{b - a}{2^n} \] olur. Sağ taraf \(n \to \infty\) iken sıfıra gittiğinden \(p_n \to p\)’dir. \(\blacksquare\)
Teoremdeki eşitsizlik \(|p_n - p| \leq (b - a) \cdot \frac{1}{2^n}\) biçiminde yazılırsa, yakınsama hızı tanımına (Tanım 3.4) göre \(K = b - a\) sabitiyle \[ p_n = p + O\left(\frac{1}{2^n}\right) \] elde edilir. Yani ikiye bölme dizisi köke \(\frac{1}{2^n}\) hızıyla yakınsar: her iterasyon hata sınırını yarıya indirir.
Teoremdeki eşitsizlik (Teorem 4.1) \(n\). adımdaki mutlak hata için bir üst sınır verir; bu sınır gerçek hatadan çok büyük olabilir. Kübik denklem örneğinde (Örnek 4.2) gerçek kök dokuz basamakla \(p = 1{,}365230013\)’tür. \(p_9\) için gerçek hata \[ |p_9 - p| = |1{,}365234375 - 1{,}365230013| = 0{,}4362 \cdot 10^{-5} \] iken teoremden elde edilen sınır \[ |p_9 - p| \leq \frac{2 - 1}{2^9} = 0{,}1953125 \cdot 10^{-2} \] olup gerçek hatanın yaklaşık 450 katıdır.
Buna karşılık sınırın değeri, istenen hassaslık için kaç adım gerektiğini önceden söyler; bunun için ne kökü ne de iterasyonları bilmemiz gerekir.
Örnek 4.3 (Gerekli Adım Sayısı) İkiye bölme metoduyla \([1, 2]\) aralığında \(x^3 + 4x^2 - 10 = 0\) denkleminin köküne \(10^{-3}\)’ten küçük bir mutlak hatayla yaklaşmak için gereken adım (iterasyon) sayısını belirleyiniz.
Çözüm
\(a = 1\), \(b = 2\) alıp yakınsama teoremindeki (Teorem 4.1) üst sınırı kullanırız: \[ |p_n - p| \leq \frac{b - a}{2^n} = \frac{1}{2^n} < 10^{-3} \] eşitsizliğini sağlayan en küçük \(n\) aranıyor. Her iki tarafın logaritmasını alırsak \[ \begin{aligned} 2^{-n} < 10^{-3} &\iff -n \log 2 < -3 \log 10 \\[1mm] &\iff n > \frac{3}{\log 2} = 9{,}965784285 \end{aligned} \] bulunur; yani \(n = 10\) adım yeterlidir.
Bunu kübik denklem örneğindeki (Örnek 4.2) tabloyla denetleyelim: \(p_{10} = 1{,}364257813\) ve \(p = 1{,}365230013\) olduğundan \[ |p_{10} - p| = 0{,}9722 \cdot 10^{-3} < 10^{-3} \] gerçekten sağlanır. \(\blacksquare\)
Aynı hesap genel olarak yapılabilir.
Örnek 4.4 (Adım Sayısının Genel Formülü) Uzunluğu \(b - a\) olan bir başlangıç aralığında, ikiye bölme metodunun mutlak hatasının \(\varepsilon\)’dan küçük olmasını teoremdeki sınırla garanti eden en küçük adım sayısını \(b - a\) ve \(\varepsilon\) cinsinden bulunuz.
Çözüm
Yakınsama teoremi (Teorem 4.1) gereği \(\frac{b - a}{2^n} < \varepsilon\) olması yeter. Bu eşitsizlik \(2^n > \frac{b - a}{\varepsilon}\), yani \[ n > \log_2 \frac{b - a}{\varepsilon} = \frac{\log(b - a) - \log \varepsilon}{\log 2} \] demektir. Dolayısıyla aranan sayı bu logaritmadan büyük en küçük tam sayıdır: \[ n = \left\lfloor \log_2 \frac{b - a}{\varepsilon} \right\rfloor + 1. \] Örneğin \(b - a = 1\), \(\varepsilon = 10^{-3}\) için \(n = \lfloor 9{,}97 \rfloor + 1 = 10\) bulunur; bu bir önceki örneğin (Örnek 4.3) sonucudur.
Formül iki gözlem verir. Hassaslığı on kat artırmak (\(\varepsilon\)’u \(10\)’a bölmek) yalnız \(\log_2 10 \approx 3{,}32\) adım ekler. Başlangıç aralığını yarıya indirmek ise tam bir adım kazandırır. \(\blacksquare\)
4.5 Alıştırmalar
Aşağıdaki sorularda istenen yuvarlama her adımda uygulanır ve sonraki adım yuvarlanmış değerlerle sürdürülür. Tablolarda son sütun, yakınsama teoremindeki (Teorem 4.1) \(\frac{b - a}{2^n}\) hata sınırıdır.
Alıştırma 4.1 (Karekök ve Kosinüs) \(\sqrt{x} - \cos x = 0\) denkleminin köküne \([0, 1]\) aralığında ikiye bölme metoduyla \(p_3\) yaklaşımında bulununuz. İşlemlerde virgülden sonra 5. basamağa yuvarlama yapınız ve sonuçları bir tabloda gösteriniz.
Çözüm
\(f(x) = \sqrt{x} - \cos x\) fonksiyonu \([0, 1]\) üzerinde süreklidir. \(a_1 = 0\), \(b_1 = 1\) için \[ f(a_1) = -1 < 0, \qquad f(b_1) = 1 - \cos 1 = 0{,}45970 > 0 \] olduğundan \(f(a_1) \cdot f(b_1) < 0\)’dır.
- \(p_1 = \frac{0 + 1}{2} = 0{,}5\) ve \(f(0{,}5) = -0{,}17048 < 0\). \(f(p_1)\), \(f(a_1)\) ile aynı işaretli olduğundan \(a_2 = 0{,}5\), \(b_2 = 1\).
- \(p_2 = \frac{0{,}5 + 1}{2} = 0{,}75\) ve \(f(0{,}75) = 0{,}13434 > 0\). Bu kez \(f(b_2)\) ile aynı işaretli olduğundan \(a_3 = 0{,}5\), \(b_3 = 0{,}75\).
- \(p_3 = \frac{0{,}5 + 0{,}75}{2} = 0{,}625\) ve \(f(0{,}625) = -0{,}02039\).
| \(n\) | \(a_n\) | \(b_n\) | \(p_n\) | \(f(p_n)\) |
|---|---|---|---|---|
| \(1\) | \(0\) | \(1\) | \(0{,}5\) | \(-0{,}17048\) |
| \(2\) | \(0{,}5\) | \(1\) | \(0{,}75\) | \(0{,}13434\) |
| \(3\) | \(0{,}5\) | \(0{,}75\) | \(0{,}625\) | \(-0{,}02039\) |
İstenen yaklaşım \(p_3 = 0{,}625\)’tir. \(\blacksquare\)
Alıştırma 4.2 (Dördüncü Dereceden Bir Polinom) \(x^4 - 2x^3 - 4x^2 + 4x + 4 = 0\) denkleminin \([-1, 4]\) aralığındaki bir kökünü en fazla \(0{,}005\) mutlak hatayla ikiye bölme metoduyla bulunuz. İşlemlerde virgülden sonra 4. basamağa yuvarlama yapınız ve sonuçları bir tabloda gösteriniz.
Çözüm
\(f(x) = x^4 - 2x^3 - 4x^2 + 4x + 4\) polinom olduğundan \(f \in C[-1, 4]\)’tür. \(f(-1) = -1 < 0\) ve \(f(4) = 84 > 0\) olduğundan yöntem uygulanabilir.
Kaç adım gerektiğini önceden bulalım. \(\frac{b - a}{2^n} = \frac{5}{2^n} < 0{,}005\) eşitsizliği \(2^n > 1000\) demektir. \(2^9 = 512\) ve \(2^{10} = 1024\) olduğundan \(n = 10\) adım yeterlidir.
| \(n\) | \(a_n\) | \(b_n\) | \(p_n\) | \(f(p_n)\) | \(\frac{b-a}{2^n}\) |
|---|---|---|---|---|---|
| \(1\) | \(-1\) | \(4\) | \(1{,}5\) | \(-0{,}6875\) | \(2{,}5\) |
| \(2\) | \(1{,}5\) | \(4\) | \(2{,}75\) | \(0{,}3477\) | \(1{,}25\) |
| \(3\) | \(1{,}5\) | \(2{,}75\) | \(2{,}125\) | \(-4{,}3630\) | \(0{,}625\) |
| \(4\) | \(2{,}125\) | \(2{,}75\) | \(2{,}4375\) | \(-3{,}6797\) | \(0{,}3125\) |
| \(5\) | \(2{,}4375\) | \(2{,}75\) | \(2{,}5938\) | \(-2{,}1738\) | \(0{,}1563\) |
| \(6\) | \(2{,}5938\) | \(2{,}75\) | \(2{,}6719\) | \(-1{,}0522\) | \(0{,}0781\) |
| \(7\) | \(2{,}6719\) | \(2{,}75\) | \(2{,}7110\) | \(-0{,}3877\) | \(0{,}0391\) |
| \(8\) | \(2{,}7110\) | \(2{,}75\) | \(2{,}7305\) | \(-0{,}0293\) | \(0{,}0195\) |
| \(9\) | \(2{,}7305\) | \(2{,}75\) | \(2{,}7403\) | \(0{,}1578\) | \(0{,}0098\) |
| \(10\) | \(2{,}7305\) | \(2{,}7403\) | \(2{,}7354\) | \(0{,}0637\) | \(0{,}0049\) |
\(n = 10\)’da hata sınırı \(0{,}0049 < 0{,}005\) olduğundan \(p \approx p_{10} = 2{,}7354\)’tür.
Sonucu denetleyebiliriz: \(f(x) = (x^2 - 2)(x^2 - 2x - 2)\) çarpanlarına ayrılır, dolayısıyla \([-1, 4]\) aralığında \(1 - \sqrt{3}\), \(\sqrt{2}\) ve \(1 + \sqrt{3}\) olmak üzere üç kök vardır. Yöntem bunlardan \(p = 1 + \sqrt{3} = 2{,}7320508\ldots\) köküne yaklaşmıştır ve gerçek hata \(|p_{10} - p| \approx 0{,}0033 < 0{,}005\)’tir. \(\blacksquare\)
Alıştırma 4.3 (Altıncı Dereceden Bir Polinom) \(x^6 - x - 1 = 0\) denkleminin \(\left[1, \frac{5}{4}\right]\) aralığındaki köküne mutlak hata \(0{,}01\)’den küçük olacak biçimde ikiye bölme metoduyla bir yaklaşımda bulununuz. İşlemlerde virgülden sonra 4. basamağa yuvarlama yapınız ve sonuçları bir tabloda gösteriniz.
Çözüm
\(f(x) = x^6 - x - 1\) polinom olduğundan \(f \in C[1;\ 1{,}25]\)’tir. \(f(1) = -1 < 0\) ve \(f(1{,}25) = 1{,}5647 > 0\)’dır.
\(\frac{b - a}{2^n} = \frac{0{,}25}{2^n} < 0{,}01\) eşitsizliği \(2^n > 25\) demektir; \(2^4 = 16\), \(2^5 = 32\) olduğundan \(n = 5\) adım yeterlidir.
| \(n\) | \(a_n\) | \(b_n\) | \(p_n\) | \(f(p_n)\) | \(\frac{b-a}{2^n}\) |
|---|---|---|---|---|---|
| \(1\) | \(1\) | \(1{,}25\) | \(1{,}125\) | \(-0{,}0977\) | \(0{,}125\) |
| \(2\) | \(1{,}125\) | \(1{,}25\) | \(1{,}1875\) | \(0{,}6167\) | \(0{,}0625\) |
| \(3\) | \(1{,}125\) | \(1{,}1875\) | \(1{,}1563\) | \(0{,}2338\) | \(0{,}0313\) |
| \(4\) | \(1{,}125\) | \(1{,}1563\) | \(1{,}1407\) | \(0{,}0624\) | \(0{,}0156\) |
| \(5\) | \(1{,}125\) | \(1{,}1407\) | \(1{,}1329\) | \(-0{,}0187\) | \(0{,}0078\) |
\(|p_5 - p| \leq 0{,}0078 < 0{,}01\) olduğundan \(p \approx p_5 = 1{,}1329\)’dur. \(\blacksquare\)
Alıştırma 4.4 (İterasyon Sayısı ve Yaklaşım) \(x^3 + x - 4 = 0\) denkleminin \([1, 4]\) aralığındaki köküne \(10^{-3}\) hassasiyetle (yani mutlak hata \(0{,}001\)’den küçük olacak biçimde) yaklaşmak için ikiye bölme metodunda en az kaç iterasyon gerekir? Bu sayıda iterasyonla kökü yaklaşık olarak bulunuz. İşlemlerde virgülden sonra 4. basamağa yuvarlama yapınız.
Çözüm
\(f(x) = x^3 + x - 4\) polinomu için \(f(1) = -2 < 0\) ve \(f(4) = 64 > 0\)’dır. Teorem 4.1 gereği \[ |p - p_n| \leq \frac{b - a}{2^n} = \frac{4 - 1}{2^n} < 10^{-3} \] olması yeter. Bu, \(2^n > 3000\) demektir: \[ n > \frac{\log 3000}{\log 2} = 11{,}5507, \] yani \(n \geq 12\). İstenen kritere uygun ilk yaklaşım \(p_{12}\)’dir.
| \(n\) | \(a_n\) | \(b_n\) | \(p_n\) | \(f(p_n)\) | \(\frac{b-a}{2^n}\) |
|---|---|---|---|---|---|
| \(1\) | \(1\) | \(4\) | \(2{,}5\) | \(14{,}1250\) | \(1{,}5\) |
| \(2\) | \(1\) | \(2{,}5\) | \(1{,}75\) | \(3{,}1094\) | \(0{,}75\) |
| \(3\) | \(1\) | \(1{,}75\) | \(1{,}375\) | \(-0{,}0254\) | \(0{,}375\) |
| \(4\) | \(1{,}375\) | \(1{,}75\) | \(1{,}5625\) | \(1{,}3772\) | \(0{,}1875\) |
| \(5\) | \(1{,}375\) | \(1{,}5625\) | \(1{,}4688\) | \(0{,}6376\) | \(0{,}0938\) |
| \(6\) | \(1{,}375\) | \(1{,}4688\) | \(1{,}4219\) | \(0{,}2967\) | \(0{,}0469\) |
| \(7\) | \(1{,}375\) | \(1{,}4219\) | \(1{,}3985\) | \(0{,}1337\) | \(0{,}0234\) |
| \(8\) | \(1{,}375\) | \(1{,}3985\) | \(1{,}3868\) | \(0{,}0539\) | \(0{,}0117\) |
| \(9\) | \(1{,}375\) | \(1{,}3868\) | \(1{,}3809\) | \(0{,}0141\) | \(0{,}0059\) |
| \(10\) | \(1{,}375\) | \(1{,}3809\) | \(1{,}3780\) | \(-0{,}0053\) | \(0{,}0029\) |
| \(11\) | \(1{,}3780\) | \(1{,}3809\) | \(1{,}3795\) | \(0{,}0047\) | \(0{,}0015\) |
| \(12\) | \(1{,}3780\) | \(1{,}3795\) | \(1{,}3788\) | \(0{,}0000\) | \(0{,}0007\) |
\(n = 11\)’de hata sınırı \(0{,}0015\) henüz \(0{,}001\)’in üstündedir; \(n = 12\)’de \(0{,}0007 < 0{,}001\) olur. Böylece \(p \approx p_{12} = 1{,}3788\) bulunur. Son satırdaki \(f(p_{12})\) değeri sıfır değildir (\(f(1{,}3788) \approx 0{,}00002\)); yalnız dört basamağa yuvarlanınca \(0{,}0000\) görünür. \(\blacksquare\)
Alıştırma 4.5 (Yaklaşım ve Bağıl Hatası) \(3x^2 - e^x = 0\) denkleminin \([0, 1]\) aralığındaki köküne ikiye bölme metoduyla \(10^{-2}\) hassasiyetle (yani mutlak hata \(0{,}01\)’den küçük olacak biçimde) bir yaklaşımda bulununuz. İşlemlerde virgülden sonra 4. basamağa yuvarlama yapınız ve sonuçları bir tabloda gösteriniz. Denklemin bu aralıktaki gerçek kökü \(p = 0{,}910007572\) olduğuna göre yaklaşımın bağıl hatasını belirleyiniz.
Çözüm
\(f(x) = 3x^2 - e^x\) fonksiyonu \([0, 1]\) üzerinde süreklidir; \(f(0) = -1 < 0\) ve \(f(1) = 3 - e = 0{,}2817 > 0\)’dır.
\(\frac{b - a}{2^n} = \frac{1}{2^n} < 0{,}01\) eşitsizliği \(2^n > 100\) demektir; \(2^6 = 64\), \(2^7 = 128\) olduğundan \(n = 7\) adım yeterlidir.
| \(n\) | \(a_n\) | \(b_n\) | \(p_n\) | \(f(p_n)\) | \(\frac{b-a}{2^n}\) |
|---|---|---|---|---|---|
| \(1\) | \(0\) | \(1\) | \(0{,}5\) | \(-0{,}8987\) | \(0{,}5\) |
| \(2\) | \(0{,}5\) | \(1\) | \(0{,}75\) | \(-0{,}4295\) | \(0{,}25\) |
| \(3\) | \(0{,}75\) | \(1\) | \(0{,}875\) | \(-0{,}1020\) | \(0{,}125\) |
| \(4\) | \(0{,}875\) | \(1\) | \(0{,}9375\) | \(0{,}0831\) | \(0{,}0625\) |
| \(5\) | \(0{,}875\) | \(0{,}9375\) | \(0{,}9063\) | \(-0{,}0110\) | \(0{,}0313\) |
| \(6\) | \(0{,}9063\) | \(0{,}9375\) | \(0{,}9219\) | \(0{,}0356\) | \(0{,}0156\) |
| \(7\) | \(0{,}9063\) | \(0{,}9219\) | \(0{,}9141\) | \(0{,}0122\) | \(0{,}0078\) |
\(0{,}0078 < 0{,}01\) olduğundan \(p \approx p_7 = 0{,}9141\)’dir.
Gerçek kök \(p = 0{,}910007572\) olduğuna göre bu yaklaşımın bağıl hatası \[ \left| \frac{p - p_7}{p} \right| = \frac{|0{,}910007572 - 0{,}9141|}{0{,}910007572} \approx 0{,}0045 \] olur. Mutlak hata da \(|p - p_7| \approx 0{,}0041 < 0{,}01\) olup istenen hassaslık sağlanmıştır. \(\blacksquare\)
İkiye bölme metodu her zaman yakınsar ama yavaştır ve yalnız işaret bilgisini kullanır. Sonraki bölümde denklemi \(x = g(x)\) biçimine sokup \(p_n = g(p_{n-1})\) iterasyonuyla köke yaklaşan, uygun koşullarda çok daha hızlı yakınsayan bir yönteme geçiyoruz: Sabit Nokta İterasyonu.