İkiye Bölme Yöntemi Algoritması ve Örnekleri

İkiye Bölme Yöntemi Nedir?

İkiye Bölme Yöntemi, bir polinomun veya aşkın denklemin kökünü bulmak için kullanılan en temel sayısal tekniklerden biridir. Kökü içeren aralığı parantez içine alarak ve ardından kök kabul edilebilir bir tolerans içinde bulunana kadar her yinelemede bu aralığı ikiye bölerek çalışır. Bu parantezleme davranışı nedeniyle, İkiye Bölme Yöntemi aynı zamanda parantezleme yöntemi olarak da adlandırılır.

Çalışma mekanizması ikili aramaya benzediği için, İkiye Bölme Yöntemi aynı zamanda ikili arama yöntemi, yarıya bölme yöntemi veya dikotomi yöntemi olarak da bilinir. Güçlü bir teorik temele dayanır: Bir aralıkta işaret değiştiren sürekli bir fonksiyonun o aralık içinde bir yerde sıfırı geçmesini garanti eden Ara Değer Teoremi.

Temel tanımı yaptıktan sonra, denklemlerin köklerini bulmanın neden önemli olduğunu ve İkiye Bölme Yönteminin bu daha geniş çerçeveye nasıl uyduğunu inceleyelim.

Denklemlerin Köklerini Bulma

Bu tartışmada, yalnızca tek bağımsız değişkenli denklemlere odaklanacağız. Bu tür denklemler doğrusal veya doğrusal olmayan olabilir. Doğrusal denklemler düz bir çizginin grafiğini tanımlarken, doğrusal olmayan denklemler eğrileri ve daha karmaşık şekilleri tanımlar.

Bir denklemin kökü, denklemi sağlayan bağımsız değişkenin değeridir. Örneğin, f(x) = 4 – x denkleminin kökü² = 0, 2'dir, çünkü f(2) = 4 – 2² = 0.

f(x)'i sürekli bir gerçek fonksiyon olarak ele alalım. Ara Değer Teoremi'ne göre, f(a)f(b) < 0 olduğunda f(x) = 0 denkleminin a ve b arasında en az bir kökü vardır. Başka bir deyişle, f(x) fonksiyonunun a ve b arasında bir yerde "c" adında bir kökü vardır.

İşaret değiştirme özelliği, İkiye Bölme Yöntemi'nin tam olarak kullandığı şeydir. Bir sonraki bölümde bu fikrin grafiksel olarak nasıl göründüğü gösterilecektir.

İkiye Bölme Yönteminin Grafiksel Gösterimi

Aşağıdaki grafik, İkiye Bölme Yönteminin çalışma mekanizmasını göstermektedir. Grafikten, denklemin gerçek kökünün kırmızı renkle işaretlendiğini görebiliriz.

İşlem şu şekilde özetlenebilir:

• Öncelikle iki başlangıç ​​tahmini seçiyoruz, a₁ ve B₁, f(a) için₁)f(b₁) < 0. Ara Değer Teoremi'ne göre, kök [a] aralığında yer almalıdır.₁, b₁].
• Daha sonra a'nın orta noktasını hesaplarız.₁ ve B₁, bu b₂. Başlangıç ​​aralığı şimdi [a] değerine indirgenmiştir.₁, b₂] çünkü f(a₁)f(b₂) < 0.
• Aynı şekilde, istenen tolerans dahilinde yaklaşık bir çözüm bulunana kadar aralık tekrar tekrar yarıya indirilir.

Geometrik sezgiyi netleştirdiğimize göre, artık bu prosedürü adım adım bir algoritma olarak resmileştirebiliriz.

Bölme Yöntemi Algoritması

f(x) = 0 denkleminin kökünü bulmak için İkiye Bölme Yöntemi algoritmasının uygulanmasına ilişkin adımlar aşağıdaki gibidir.

) 1 Adım Başlangıç ​​tahminleri a, b ve tolerans oranı e'yi seçin.

) 2 Adım Eğer f(a)f(b) >= 0 ise, kök bu aralıkta yer almaz. Bu durumda, [a, b] aralığında çözüm yoktur.

) 3 Adım Orta noktayı bulun, c = (a + b)/2.

(i) Eğer orta noktadaki fonksiyon değeri f(c) = 0 ise, c köktür. 5. adıma geçin.
(ii) Eğer f(a)f(c) < 0 ise, kök a ve c arasında yer alır. O halde a = a, b = c olarak ayarlayın.
(iii) Aksi takdirde, a = c, b = b olarak ayarlayın.

) 4 Adım Mutlak hata tolerans oranından yüksekse, yani (b – a) > e ise, 3. adıma geri dönün.

) 5 Adım c'yi yaklaşık kök olarak görüntüleyin.

Şimdi İkiye Bölme Yöntemi algoritmasının nasıl çalıştığına dair bir örnek görelim. Aşağıdaki sürekli fonksiyonun kökünü İkiye Bölme Yöntemi formülünü kullanarak bulacağız.

f(x) = x³ - x² + 2

İkiye Bölme Yöntemi Örneği

) 1 Adım Varsayalım ki,

         a = -10,
         b = 10 ve
         e = %1 veya 0.01.

) 2 Adım Şimdi f(a)f(b) >= 0 olup olmadığını kontrol edeceğiz.

         f(a) = f(-10) = (-10)³ – (-10)² + 2 = -1098
         f(b) = f(10) = (10)³ - (10)² + 2 = 902
         f(a)f(b) = f(-10)f(10) = (-1098)(902) < 0

Dolayısıyla, yukarıdaki fonksiyonun kökü [-10, 10] aralığındadır.

) 3 Adım Ardından, orta nokta c hesaplanır.

Şimdi aşağıdaki koşulların kontrol edilmesi gerekiyor:

(i) f(c) = 0 olup olmadığı:
         f(c) = f(0) = (0)³ - (0)² + 2 = 2, bu da 0'a eşit değildir.

(ii) f(a)f(c) < 0 olup olmadığı:
         f(c)f(a) = 2 * (-1098) < 0

Koşul sağlandı. Bir sonraki yineleme için değerler şöyle olacaktır:

         bir = bir = -10
         b = c = 0

) 4 Adım (b – a) = (0 – (-10)) = 10 > 0.01 olduğundan işlem tekrarlanır. Sonraki yinelemeler aşağıdaki tabloda gösterilmiştir.

) 5 Adım 11. yinelemede, 4. adımdaki koşul yanlış hale gelir. Dolayısıyla, bu denklemin yaklaşık kökü -1.00586'dır.

Sayısal örnek tamamlandıktan sonra, bir sonraki bölümde tüm kontrol akışını gösteren mantıksal şema sunulacaktır.

İkiye Bölme Yöntemi Mantıksal Diyagramı

Aşağıdaki akış şeması, parantez kontrolü, orta nokta güncellemesi ve tolerans testi de dahil olmak üzere İkiye Bölme Yönteminin karar mantığını özetlemektedir.

yalancıCode

Aşağıdaki sözde kod, algoritmayı yansıtır ve herhangi bir programlama dilinde İkiye Bölme Yöntemini uygulamak için bir şablon görevi görür.

Start
Set a, b, e
if f(a)*f(b) >= 0
    Output("Root does not exist in this interval")
    Stop
while (b-a) > e do
    c ← (a + b)/2
    if f(c) = 0
        break
    end if
    if f(c)*f(a) < 0 then
        b ← c
    else
        a ← c
end while
Output(c)
Stop

C/'de İkiye Bölme Yöntemi ÖrneğiC++

Aşağıdaki C/C++ Bu program, f(x) = x fonksiyonunun kökünü bulmak için İkiye Bölme Yöntemini uygular.³ - x² [-10, 10] aralığında +2.

Giriş:

#include <bits/stdc++.h>
using namespace std;
#define Error 0.01
double value(double x)
{
    return x*x*x - x*x + 2;
}
void bisection_method(double a, double b)
{
    if (value(a) * value(b) >= 0)
    {
        cout << "The root does not lie in this interval\n";
        return;
    }
    double c = a;
    while ((b-a) >= Error)
    {
        c = (a+b)/2;
        if (value(c) == 0.0)
            break;
        else if (value(c)*value(a) < 0)
            b = c;
        else
            a = c;
    }
    cout << "The root is :" << c;
}
int main()
{
    double a = -10, b = 10;
    bisection_method(a, b);
    return 0;
}

Çıktı:

The root is :-1.00586

İkiye Bölme Yöntemi Örneği Python

MKS Python Aşağıdaki versiyon, aynı mantığı kullanarak yaklaşık olarak aynı kökü üretir; bu da onu hızlı deneyler ve öğretim için ideal hale getirir.

Giriş:

def value(x):
    return x*x*x - x*x + 2

def bisection_method(a, b):
    if (value(a) * value(b) >= 0):
        return
    c = a
    while ((b-a) >= 0.01):
        c = (a+b)/2
        if (value(c) == 0.0):
            break
        if (value(c)*value(a) < 0):
            b = c
        else:
            a = c
    print("The root is : ", "%.4f" % c)

a = -10
b = 10
bisection_method(a, b)

Çıktı:

The root is :  -1.0059

İkiye Bölme Yönteminin Avantajları ve Sınırlamaları

Her sayısal teknik gibi, İkiye Bölme Yöntemi'nin de belirgin güçlü yönleri ve birkaç pratik dezavantajı vardır. Aşağıdaki tablo en önemli avantaj ve dezavantajları özetlemektedir.

İkiye Bölme Yönteminin Uygulamaları

İkiye bölme yöntemi, sağlam bir kök bulma adımının gerekli olduğu birçok pratik ve modern bilişim senaryosunda kullanılır.

• Mühendislik simülasyonları: Isı transferi, akışkanlar dinamiği ve yapısal analizde ortaya çıkan doğrusal olmayan denklemlerin çözümü.
• Finansal modelleme: Kapalı form çözümlerinin bulunmadığı durumlarda verimlilik oranlarını, iç getiri oranlarını ve başabaş noktalarını hesaplamak.
• Makine öğrenimi ve yapay zeka: Yapay zekâ destekli sayısal çözümleyicilerde eşik değerlerinin belirlenmesi, modellerin kalibrasyonu ve hiperparametrelerin ayarlanması.
• Bilgisayar grafikleri: Eğriler boyunca ışın-yüzey kesişimlerinin ve parametre değerlerinin belirlenmesi.
• Gömülü sistemler: Basitliğin ve öngörülebilirliğin hızdan daha değerli olduğu, düşük kaynaklı kontrolcülerde köklerin yaklaşık olarak belirlenmesi.

SSS