Newton Yöntemi: Yinelemeli Yaklaşımla Kökleri Hızlı Bulun

Bazı denklemlerin temiz bir cebirsel çözümü yoktur.

İstediğiniz kadar çarpanlara ayırıp yerine koyma yapabilirsiniz, ancak bazı denklemlerin kapalı formda çözümü bulunmaz. Örneğin, beş veya daha yüksek dereceden bir polinomun genel bir cebirsel çözümü yoktur. Üstel ifadeleri polinomlarla karıştıran fonksiyonlar, örneğin e^x = 3x, aynı kategoriye girer. Bu durumlarda farklı bir yaklaşıma ihtiyaç vardır.

Newton yöntemi tam da bu yaklaşımdır. Kökleri sayısal olarak bulur; her tahmin, fonksiyonun mevcut kestirim noktasındaki teğet doğrusu tarafından yönlendirilen daha akıllı bir tahmindir.

Bu yazıda, Newton yönteminin ardındaki formülü, adım adım nasıl çalıştığını, ne zaman yakınsadığını ve ne zaman yakınsamadığını somut örneklerle açıklayacağım.

Bir veri bilimci olarak bilmeniz gereken daha fazla matematik konusu mu arıyorsunuz? Finans, fizik ve bilgisayar bilimlerine nasıl uygulandığını görmek için Geometrik Dizi: Formül, Yakınsama ve Örnekler blog yazımızı okuyun.

Newton Yöntemi Nedir?

Newton yöntemi, bir fonksiyonun köklerini bulmak için kullanılan yinelemeli bir tekniktir. Kökler, fonksiyonun sıfıra eşit olduğu girdi değerleridir.

Bu sürece bir başlangıç tahminiyle başlarsınız. Ardından, yöntem o noktadaki fonksiyonun geometrisini kullanarak daha iyi bir tahmin yapar. Bu süreci tekrarlarsınız ve her yineleme sizi gerçek köke daha da yaklaştırır.

Bütün fikir bu. Cevaba yakınsayan akıllı ve tekrarlanabilir bir güncelleme kuralına ihtiyacınız var.

Newton Yöntemi Formülü

Newton yönteminin özünde, köke yeterince yaklaşana kadar tekrar tekrar uygulanan tek bir güncelleme kuralı vardır.

Formül şöyle:

Newton’un yöntemi formülü

Her yineleme, mevcut kestiriminiz x_n’i alır ve ondan daha iyi birini, x_{n+1}’i üretir. Sonuç sıfıra yeterince yaklaşana kadar güncellemeye devam edersiniz.

Formülün üç bileşeni vardır:

• x_n - köke ilişkin mevcut kestiriminiz

• f(x_n) - fonksiyonun bu kestirimdeki değeri

• f'(x_n) - bu kestirimdeki fonksiyonun türevi; teğet doğrusunun eğimini verir

Eğer f(x_n) büyükse, kökten uzaksınız demektir. f'(x_n) dikse, fonksiyon hızlı değişiyor demektir; bu da daha büyük bir adım atabileceğiniz anlamına gelir. f(x_n) / f'(x_n) oranı tam olarak ne kadar hareket edeceğinizi söyler – ve mevcut tahmininizden bunu çıkararak daha da yaklaşırsınız.

Eğer f'(x_n) sıfır ya da sıfıra yakınsa, formül pek işlemez. Sıfıra bölme söz konusu olur ve yöntem bir sonraki kestirimi üretemez. Bunu sınırlamalar bölümünde daha ayrıntılı ele alacağım.

Newton Yöntemi Nasıl Çalışır

Newton yöntemi her yinelemede aynı dört adımı izler.

1. Bir başlangıç tahmini seçin: Kökün yakınlarında bir başlangıç değeri x_0 seçin. Tam isabetli olmanıza gerek yok – yalnızca fonksiyonun o noktada öngörülebilir davrandığı kadar yakın olun. “Yeterince yakın”ın ne demek olduğunu yakınsama bölümünde ele alacağım.

2. Fonksiyon değerini hesaplayın: f(x_0)’ı değerlendirin. Bu, mevcut kestiriminizde fonksiyonun sıfırdan ne kadar uzak olduğunu söyler. Eğer f(x_0) = 0 ise işiniz bitti – kökü buldunuz.

3. Türevi hesaplayın: f'(x_0)’ı değerlendirin. Bu, x_0’daki fonksiyonun eğimini, yani o noktadaki teğetin eğimini verir.

4. Kestirimi güncelleyin: Bir önceki bölümdeki formüle göre güncelleme kuralını uygulayın.

Ve hepsi bu!

Bu yeni değer x_1, teğet doğrusunun x-eksenini kestiği yerdir. Geometrik olarak, x_0’da eğriye değen bir doğru çiziyor ve onu aşağı doğru sıfıra kadar izliyorsunuz. Bu kesişim noktası bir sonraki, daha iyi tahmininizdir.

Sonra tekrarlarsınız. x_1’i 2 ila 4. adımlara geri koyup x_2’yi, sonra x_3’ü ve böyle devam edersiniz. Her yineleme, güncellenen noktada yeni bir teğet çizer ve x-eksenini kestiği yeri bulur.

Süreç, f(x_n) sıfıra yeterince yaklaştığında durur – genellikle en başta tanımladığınız küçük bir eşik değerinin altına düştüğünde.

Newton Yönteminin Geometrik Yorumu

Bir grafikte bir eğri hayal edin – bu sizin f(x) fonksiyonunuzdur. Kök, eğrinin x-eksenini kestiği yerdir. Bu kesişimin nerede olduğunu henüz bilmediğiniz için x-ekseninde bir yerde bir tahmin x_0 ile başlarsınız.

Her adımda, eğri üzerinde (x_0, f(x_0)) noktasını işaretler, sonra o noktadaki teğeti çizersiniz – eğriye orada değen ve eğimi takip eden düz bir doğru. Bu teğet yatay değildir. Eğimlidir ve onu aşağı izlerseniz bir noktada x-eksenini keser. Bu kesişim bir sonraki kestiriminiz, x_1’dir.

Sonra tekrarlarsınız. x_1’de yeni bir teğet çizer ve x-eksenini kestiği yeri bulursunuz. Bu size x_2’yi verir. Her teğet, eğrinin yerel doğrusal yaklaştırmasıdır ve her kesişim noktası gerçek köke daha yakın düşer.

Aşağıdaki grafik, x_0 = 2.5’ten başlayarak f(x) = x^2 - 2 fonksiyonuna uygulanan Newton yönteminin iki yinelemesini gösterir:

Geometrik yorum grafiği

Bu yöntem işe yarar çünkü teğet doğru, herhangi bir noktada eğrinin en iyi doğru yaklaşımıdır. Kökten ne kadar yakınsanız, teğet doğru o kadar çok eğrinin kendisine benzer – ve bir sonraki adımınız o kadar isabetli olur.

Uygulamada kestirimler köke yavaşça sokulmakla kalmaz; oraya hızlıca sıçrarlar, çoğu zaman her yinelemede doğru ondalık basamak sayısını ikiye katlarlar.

Newton Yönteminin Adım Adım Örneği

f(x) = x^2 - 2 için Newton yöntemini uygulayalım. Bu fonksiyonun kökü x = sqrt(2) ≈ 1.4142’dir – yani 2’nin karekökünü hesaplıyoruz.

Türevi f'(x) = 2x olduğundan güncelleme kuralı şu hale gelir:

Örnek (güncelleme kuralı)

Başlangıç tahmini olarak x_0 = 2.5 alalım.

1. yineleme:

Örnek (1. yineleme)

2. yineleme:

Örnek (2. yineleme)

3. yineleme:

Örnek (3. yineleme)

Sadece üç yineleme sonrasında, dört ondalık basamağa kadar doğruyuz. Hata, x_0’da 1.086 iken x_3’te 0.0001’e düştü – ve her adımda azalmaya devam ediyor.

Bu kestirim ve hata değerleri görsel olarak şöyle çalışır:

Kestirim ve hata için görsel genel bakış

Sol panel, her kestirimin sqrt(2) ≈ 1.4142’ye nasıl yaklaştığını gösterirken; sağ panel, hatanın log ölçeğinde nasıl küçüldüğünü gösterir – her yineleme, kabaca bir öncekine göre doğruluğu karesel olarak artırır.

Newton Yönteminin Yakınsaması

Newton yöntemi hızlı yakınsayabilir, ancak yalnızca doğru koşullarda.

Başlangıç tahmininiz köke yakın olduğunda ve fonksiyon o bölgede düzgündür, yöntem karesel yakınsama sergiler. Bu, örnekte gördüğünüz şeyin teknik adıdır: her yineleme, öncekinin hatasını kabaca karesini alır. İki doğru ondalık basamak dört olur, dört sekiz olur ve böyle devam eder.

Bunun işlemesi için iki koşul gerekir:

• İyi bir başlangıç tahmini: x_0 gerçek köke ne kadar yakınsa, yöntem o kadar hızlı yakınsar. Çok uzaktan başlarsanız, o noktadaki teğet doğru sizi yanlış yöne gönderebilir.
• İyi huylu bir fonksiyon: Fonksiyon kökün yakınında düzgün ve türevlenebilir olmalıdır. Keskin dönüşler veya düz bölgeler, teğet yaklaşımına engel olabilir.

En yaygın başarısızlık modu, türevin sıfıra yakın olmasıdır. 

Eğer f'(x_n) sıfıra yakınsa, güncelleme kuralında çok küçük bir sayıya bölme yaparsınız; bu da bir sonraki kestirimi kökten çok uzağa savurur. En kötü durumda f'(x_n) = 0 olur ve sıfıra bölme yapılamayacağı için hesaplamalar işlemez.

Kötü bir başlangıç noktası da yöntemin salınım yapmasına veya ıraksamasına neden olabilir. Kökün etrafında toplanmak yerine kestirimler ileri geri sıçrar ya da her yinelemede daha da uzaklaşır.

Newton yöntemi iyi bir kurulumla ödüllendirir. Makul bir başlangıç tahmini ve düzgün bir fonksiyon, yakınsaması için – hem de hızlı yakınsaması için – yeterlidir.

Newton Yönteminin Avantajları

Koşullar uygun olduğunda Newton yöntemi rakipsizdir.

En büyük avantaj, karesel yakınsamadır. Çoğu sayısal yöntem köke doğrusal hızla yaklaşır; bu, her yinelemenin hatayı sabit bir miktarda azalttığı anlamına gelir. Newton yöntemi ise hatayı kareler; bu da çok az yinelemeyle hızla yüksek doğruluk elde ettiği anlamına gelir.

Ayrıca geneldir. Polinom, trigonometrik, üstel – çok çeşitli fonksiyonlara hiçbir şeyi değiştirmeden uygulayabilirsiniz. Bu nedenle mühendislik simülasyonlarından makine öğrenimi modellerinin eğitimine kadar pek çok alanda karşımıza çıkar.

Newton Yönteminin Sınırlamaları

Newton yöntemi, bu hız karşılığında çok şey ister. Aklınızda bulundurmanız gereken birkaç sınırlama şunlardır:

• Türev gerektirir: Tek bir yineleme çalıştırmadan önce f'(x) için analitik bir ifadeye ihtiyacınız vardır. Türevin hesaplanmasının zor olduğu (ya da var olmadığı) fonksiyonlarda farklı bir yaklaşıma ihtiyaç duyulur.

• Başlangıç tahminine duyarlıdır: Kökten çok uzakta başlarsanız yöntem sizi yanlış yöne gönderebilir.

• Yakınsamayabilir: Fonksiyonun düz bölgeleri veya keskin kıvrımları varsa teğet yaklaşımı işe yaramaz.

• Iraksayabilir veya salınım yapabilir: Kötü durumlarda kestirimler yakınsamaz; kökten uzaklaşır veya süresiz olarak ileri geri sıçrar.

Bu yüzden Newton yöntemine başvurmadan önce fonksiyonunuzu anladığınızdan emin olun.

Newton Yöntemi ve Diğer Kök Bulma Yöntemleri

Newton yöntemi kök bulmanın tek yolu değildir ve her zaman sizin için doğru seçim olmayabilir.

Sıklıkla iki başka yöntem gündeme gelir: yarılama yöntemi ve sekant yöntemi. Kısaca açıklayayım.

Yarılama yöntemi

Yarılama yöntemi üçü arasında en basit olanıdır. Fonksiyonun işaret değiştirdiği bir [a, b] aralığıyla başlarsınız – bu, içeride bir yerde mutlaka bir kök olduğu anlamına gelir. Sonra aralığı tekrar tekrar ikiye böler, işaret değişiminin devam ettiği yarıyı elde tutarsınız.

İşe yarar, ancak yavaştır. Hata her yinelemede yarıya iner; bu doğrusal yakınsamadır. Ancak fonksiyon sürekli olduğu ve başlangıç aralığınız bir kökü çevrelediği sürece çalışması garanti edilir. Türev gerekmez.

Sekant yöntemi

Sekant yöntemi, Newton yönteminin yakın bir akrabasıdır. Türevi analitik olarak hesaplamak yerine, iki önceki kestirimi kullanarak yaklaştırır:

Sekant yöntemi formülü

Türevin hesaplanmasının zor olduğu durumlarda iyi bir yaklaşımdır. Bunun bedeli yakınsama hızıdır – sekant yöntemi, yarılamadan hızlı ama Newton yönteminden daha yavaştır.

Newton Yönteminin Uygulamaları

Newton yöntemi bilim, mühendislik ve makine öğrenimi genelinde karşımıza çıkar. Nasıl olduğuna bakalım.

Denklemleri sayısal olarak çözme

En doğrudan uygulama. Bir fonksiyonun kapalı formda çözümü olmadığında Newton yöntemi kökü bulur. Bu durum bilimsel hesaplamalarda sürekli karşımıza çıkar – kimyasal reaksiyonlarda denge noktalarını bulmak ya da işaret işleme alanında aşkın denklemleri çözmek gibi düşünün.

Optimizasyon

Bir f(x) fonksiyonunun minimumunu veya maksimumunu bulmak, türevinin f'(x) = 0 olduğu yeri bulmak demektir. Bu bir kök bulma problemidir – yani Newton yöntemi uygulanabilir. Algoritmayı f(x) yerine f'(x) üzerinde çalıştırır, birinci türev yerine ikinci türev f''(x)i kullanırsınız.

Bu varyanta optimizasyon için Newton yöntemi denir ve düzgün, iyi huylu fonksiyonlarda gradyan inişinden daha hızlı yakınsar.

Makine öğrenimi

Makine öğreniminde bir modeli eğitmek, bir kayıp fonksiyonunu en aza indirmek demektir. Newton yöntemi ve türevleri burada birkaç yerde karşımıza çıkar.

L-BFGS (Limited-memory Broyden-Fletcher-Goldfarb-Shanno), ikinci türevi doğrudan hesaplamaktan kaçınmak için onu yaklaştıran bir yarı-Newton optimizasyonudur. Lojistik regresyon ve diğer konveks problemlerde standart bir tercihtir. Newton yöntemi ayrıca genelleştirilmiş doğrusal modeller gibi istatistiksel model kurulumlarında kullanılan Newton-Raphson güncellemelerinin de temelidir.

Fizik ve mühendislik

Newton yöntemi simülasyon ve tasarımda her yerdedir. Mühendisler, fiziksel sistemleri tanımlayan doğrusal olmayan denklem sistemlerini çözmek için kullanır – yapısal gerilme analizi ve akışkanlar dinamiğini düşünün. Her durumda, altta yatan problem bir denklem kümesinin sıfıra eşit olduğu yerleri bulmaya indirgenir.

Newton Yönteminde Yapılan Yaygın Hatalar

Newton yöntemindeki hataların çoğu aynı dört hataya dayanır. Bunları tek tek ele alayım:

• Kökten çok uzakta başlamak: Kötü bir başlangıç tahmini, yöntemin ıraksamasının veya salınım yapmasının en yaygın nedenidir. Kökün nerede olduğuna dair iyi bir sezginiz yoksa, önce fonksiyonu çizin. Bu size nereden başlayacağınızı gösterecektir.

• Türevi yanlış hesaplamak: Güncelleme kuralı f'(x)’e dayanır. Hesap hatası ya da kodlama hatası kaynaklı yanlış bir türev, daha ilk yinelemeden itibaren hatalı kestirimler üretir ve hata yinelemelerle katlanır.

• Sıfıra bölmeyi kontrol etmemek. Eğer f'(x_n) sıfıra eşitse ya da çok yaklaşıyorsa, güncelleme adımı çalışamaz. Uygulamanıza bir koruma ekleyin: türev belirlediğiniz küçük bir eşikten aşağı düşerse durdurun ve saçma bir sonuç üretmek yerine hatayı bildirin.

• Çok erken durdurmak. Kestirim yakınsamadan yinelemeleri kesmek, yakın gibi görünen ama doğru olmayan bir yanıtla kalmanıza neden olur. Durdurma koşulunuzu gerçek hataya göre belirleyin – ya |f(x_n)| ya da |x_{n+1} - x_n| sizin bilinçli olarak seçtiğiniz bir eşik değerinin altına düştüğünde, sadece sabit bir yineleme sayısı değil.

Sonuç

Newton yöntemi, sayısal hesaplamadaki en faydalı araçlardan biridir. Tek bir güncelleme kuralı, tekrar tekrar uygulandığında, sadece birkaç yinelemede kökleri keyfi doğrulukta bulabilir.

Bu hızın bir bedeli vardır. Hızlı yakınsama için iyi bir başlangıç tahmini, düz olmayan bir fonksiyon, sivri olmayan bir fonksiyon ve sıfır olmayan bir türev gerekir. Bu koşulları anlarsanız, Newton yöntemine ne zaman başvuracağınızı ve ne zaman başka bir şey (örneğin yarılama veya sekant yöntemleri) kullanacağınızı bilirsiniz.

Bu sezgiyi geliştirmenin en iyi yolu basit örneklerle pratik yapmaktır. f(x) = x^2 - 2 ile başlayın, farklı başlangıç noktalarını deneyin ve ne olduğuna bakın. Birden fazla kökü veya düz bölgeleri olan fonksiyonlara geçin ve yöntemin nerede bozulduğunu görün.

Yineleme yoluyla optimizasyon fikrini sevdiyseniz, mutlaka gradyan inişi bilmelisiniz. Makine öğrenimi için modelleri nasıl optimize ettiğini öğrenmek üzere Makine Öğreniminde Gradyan İnişi: Derinlemesine İnceleme yazımızı okuyun.