Sayısal (Nümerik) Çözüm Algoritmaları

y = f(x) fonksiyonunda y değerini sıfır yapan x değerlerine kök ismi verilir. Fonksiyonun köklerini (f(x) = 0'ı sağlayan x değerlerini) bulmak için kullanılan sayısal çözüm algoritmalarından bir kısmı aşağıda listelenmiştir:

  • Newton-Raphson Metodu
  • Bisection (ikiye bölme) Metodu
  • Sekant Metodu
  • Yanlış Pozisyon Metodu (Regula Falsi)
  • Sabit nokta iterasyonu (Fixed-Point iteration)
  • Brent Metodu
  • Muller Metodu

Newton-Raphson Metodu

Newton-Raphson iterasyonu şu şekilde yapılır. Bir x0 değeri alınır ve bir sonraki x1 değeri hesaplanır.

x1 = x0 – f(x) / f_türev(x)

Eğer x0 değeri köklerden birine yakınsa ve fonksiyon sürekli bir fonksiyonsa iterasyon sonuca yakınsar (converge). Yani x1 ile hesaplanan değer belirli bir tekrardan sonra fonksiyonu sıfır yapan kök değerine gelir.

Newton-Raphson metodu yakınsama hızı yüksek bir yöntemdir. Yukarıda sıralanan diğer yöntemlere göre daha az iterasyon ile tolerans dahilinde kök bulunur. Fakat başlangıç değerine göre değişen bir performansı vardır. Ayrıca türevi hesaplamak zor olabilir. Türevi sıfır olan x değerleri civarında problemler oluşur.

Literatüre göre Brent Metodu yakınsama performansı ve hız performansını bir arada sunduğu için pratikte çoğunlukla kullanılan yöntemdir.

Sayısal (Nümerik) Çözüm Algoritmaları

Nümerik çözümleme yapmak için geometrik bir problem örneği kullanacağız. Parametrik olarak tanımlanan yüzeylerin, nokta ve normal vektörü ile tanımlanan düzlem ile kesişiminde oluşan noktaları hesaplayan nümerik çözümü kodlamak için aşağıdaki farklı geometrik şekilleri ele alacağız.

Geometrik Şekiller

  • Küre
  • Silindir
  • Koni
  • Kare ya da dikdörtgen prizma

Koni Örneği

Bu şekillerden koni için çalışalım. Öncelikle koninin parametrik denklemini çıkarmak gerekli. Konimizi Z ekseni boyunca yüksekliği artacak şekilde ve aşağısı mutlak koordinat sistemi merkezinde olacak gibi modelleyelim. R ve H değerleri verildiğinde h ve teta parametreleri ile nokta üreten parametrik fonksiyonumuz için aşağıdaki formüller yeterlidir.

\[\vec{P} = \begin{bmatrix} x \\ y \\ z \end{bmatrix} = F(h,teta)\] \[\tan(a) = \frac{R}{H}\] \[\tan(a) = \frac{Rh}{(H-h)} \quad R(h) = \tan(a) \times (H-h)\] \[Rh^2 = X^2 + Y^2 \text{ ya da açısal bir parametre olarak teta ile}\] \[Z = h \quad Rh = \tan(a) \times (H-Z) \quad X = Rh \times \cos(teta) \quad Y = Rh \times \sin(teta)\] \[h \in [0,H] \quad teta \in [0,2\pi]\]
Koni parametrik gösterimi Koni parametrik gösterimi

Sayısal (Nümerik) Çözüm Algoritmaları

Parametre Uzayı Görselleştirmesi

Bu parametrik denklem ile üreteceğimiz noktaların tamamını parametre uzayında bir dikdörtgen içinde gösterelim.

Parametre Uzayı Özellikleri

  • Şekildeki yeşil noktalardan her biri yükseklik ve açı parametresi olan bir h,teta ikilisidir.
  • Bütün bir alanı ayrık noktalar ile temsil etmek için ızgara oluşturulmuştur.
  • Bu ızgaradaki her 2 boyutlu h,teta noktası koni üzerinde 3 boyutlu bir nokta üretmek için kullanılabilir.

Problem Analizi

Bizim problemimizde hem koni hem de tanımladığımız düzlem üzerinde olan noktaları bulmaya çalışıyoruz. Koninin düzlem kesişimi sonsuz nokta verebilir veya boş küme olabilir. Biz ayrık noktalar ve adımlarla çözüm arayacağımız için koni yüzeyindeki bütün alanı temsil edecek örnekleme yapmamız gerekiyor.

Yandaki şekilde üstteki iki boyutlu parametre uzayında yer alan yeşil noktalar bu örneklemeyi yapabilir. Her parametre noktası civarında hem koni, hem de düzlem üstünde yer alan bir 3 boyutlu nokta bulunup bulunmadığını Newton-Raphson iterasyonu ile kontrol edebiliriz.

Bir sonraki slaytta noktanın hem koni, hem de düzlem üzerinde olması için gereken şart ve bunun bir fonksiyona dönüştürülerek Newton-Raphson iterasyonuna müsait hale gelmesi gösteriliyor.

Parametre uzayı ve koni gösterimi Parametre uzayı ve koni gösterimi

Sayısal (Nümerik) Çözüm Algoritmaları

Düzlem üzerindeki iki noktayı birleştiren çizginin vektörü ile düzlem normal vektörünün skaler çarpımı sıfır değerini verir.

\[ \left( \vec{Pp} - \vec{Pi} \right) \cdot \vec{Pn} = 0 \]

Pp ve Pn düzleme ait sabit vektörlerdir. Pi Newton-Raphson iterasyonu ile teta, h civarında aradığımız koni, düzlem ortak noktasıdır. Bu durumda F(teta,h) fonksiyonu koni üstünde bir noktayı değil skaler çarpımı vermelidir. Skaler çarpımın sıfır olduğu değeri aramak Newton-Raphson'a uygundur. İterasyon tek değer ile yapılabileceği için teta veya h ı sabit tutarak çözüm arayabiliriz. Sabit tutulan değer için diğer değişkenin hiç bir değeri fonksiyonu sıfır yapmıyor olabilir. Çözümsüz durumlarda Newton-Raphson yöntemi iterasyon yaptıkça ıraksayabilir, veya sonucu sıfır olmayan bir çözüm civarında takılıp kalabilir. Kesişim kümesini bulmak için bir çok nokta civarında iterasyon yapacağız. Kodumuz ıraksama ya da gerçek kök olmayan bir değere yakınsama durumlarını bu civarda düzlem koni kesişim noktası bulunmamaktadır şeklinde yorumlamalıdır.

Parametre uzayı ve koni gösterimi

Sayısal (Nümerik) Çözüm Algoritmaları

Sözde kod olarak koni düzlem kesişim noktalarının kümesini ayrık olarak bulmaya çalışan sayısal çözüm kodunu yazalım:

Steph = H / nh
Stepteta = 2π / nteta

h = 0, H arasında Steph artarak bütün değerler için

teta = 0, 2π arasında Stepteta artarak bütün değerler için

h ve tetanın mevcut değeri için önce h sabit değişken teta için Newton-Raphson iterasyonu ile kesişim teta değeri var mı ara. Varsa çözüm kümesine ekle. Teta sabit h değişken olacak şekilde Newton-Raphson ile bu civardaki kesişim h parametresini ara. Varsa çözüm kümesine ekle.

Sayısal (Nümerik) Çözüm Algoritmaları

Newton-Raphson algoritmamızı sözde kod olarak bir nesne içinde kodlamaya çalışalım.

\[ S(h, \theta) = \left( \tilde{P}_p - P_{geo}(h, \theta) \right) \cdot \tilde{P}_n \]

Pp ve Pn düzleme ait sabit vektörlerdir. Pgeo ise verilen parametre için yüzey üzerindeki noktadır. İterasyon yaparken h ya da tetayı sabit tutarak diğer değişken için S fonksiyonunu sıfır yapan kök değerini arayacağız.

Class NewtonRaphson { Constructor (Koni nesnesi, sayısal türev adımı)

Fonksiyon teta_için_kök_ara ( sabit h değeri , baslangic teta değeri )

Sonuç olarak kökteta değeri varsa onu döndürür yoksa boş küme döndürür. Rekürsiv bir alt fonksiyon çağırır.(iterasyon)

Fonksiyon h_için_kök_ara (sabit teta değeri , başlangıç h değeri )

Sonuç olarak kökh değeri varsa onu döndürür yoksa boş küme döndürür. Rekürsiv bir alt fonksiyon çağırır.(iterasyon)

Fonksiyon S_degeri_hesapla ( h, teta)

Pgeo = koni.Nokta(h,teta)

S = (Ppx – Pgeox).Pnx + (Ppy – Pgeoy).Pny + (Ppz-Pgeoz).Pnz

sonuç olarak S i döndürür.

Fonksiyon S_sayisal_türev_teta ( h , teta) ( S_sayisal_türev_h benzer şekilde eklenir)

D = S_degeri_hesapla (h,teta + sayisal türev adımı) - S_degeri_hesapla (h,teta) / ( sayisal türev adımı)

}