Newton'un yöntemi - Newton's method

Olarak sayısal analizi , Newton yöntemi olarak da bilinen, Newton Raphson usulü adını, Isaac Newton ve Joseph Raphson , a, kök bulma algoritması ardışık olarak daha üreten yaklaşımları için kökleri a (ya da sıfır) gerçek -valued fonksiyonu . Tek değişken fonksiyonlu en temel sürüm başlar f bir için tanımlandığı gerçek değişken x , işlevin türev f , ve bir ilk tahmin x ₀ for a kök bölgesinin f . Eğer fonksiyon yeterli varsayımı sağlıyorsa ve ilk tahmin yakınsa, o zaman

${\displaystyle x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}}$

kökün x _0'dan daha iyi bir yaklaşımıdır . Geometrik olarak, ( x ₁ , 0) kesiştiği x -Axis ve teğet ait grafik bir f de ( x ₀ , f  ( x ₀ )) : olduğu, geliştirilmiş bir tahmin eşsiz köküdür lineer yaklaşım başlangıç ​​noktasında. İşlem şu şekilde tekrarlanır

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}}$

Yeterince kesin bir değere ulaşılana kadar. Bu algoritma, Householder'ın yöntemleri sınıfında ilk olup, Halley'in yöntemiyle başarılı olmuştur . Yöntem ayrıca karmaşık fonksiyonlara ve denklem sistemlerine genişletilebilir .

Açıklama

f fonksiyonu mavi, teğet doğru ise kırmızı ile gösterilmiştir. Biz görüyoruz x _{n + 1} daha iyi bir tahmindir x _n kök için x fonksiyonu f .

Buradaki fikir, gerçek köke makul ölçüde yakın olan bir ilk tahminle başlamak, sonra kalkülüs kullanarak tanjant doğrusuna göre fonksiyona yaklaşmak ve son olarak da bu teğet doğrunun x- kesişimini temel cebir ile hesaplamaktır . Bu x- intercept, orijinal işlevin köküne ilk tahminden daha iyi bir yaklaşım olacaktır ve yöntem yinelenebilir .

Daha resmi olarak, varsayalım ki f  : ( a , b ) → ℝ , ( a , b ) aralığında tanımlanmış ℝ reel sayılardaki değerlerle türevlenebilir bir fonksiyondur ve x _n bazı güncel yaklaşımlarımız vardır . Daha sonra sağdaki diyagrama bakarak daha iyi bir yaklaşım için formül x _{n + 1} türetebiliriz . Denklemi teğet çizgi eğrisi için y = f  ( x ) olarak X = X _N olduğu  

${\displaystyle y=f'(x_{n})\,(x-x_{n})+f(x_{n}),}$

burada f' türevi belirtir . Bu doğrunun x kesme noktası ( y = 0 yapan x değeri ), x _{n + 1} köke bir sonraki yaklaşım olarak alınır , böylece teğet doğrunun denklemi şu durumlarda sağlanır : ${\displaystyle (x,y)=(x_{n+1},0)}$

${\displaystyle 0=f'(x_{n})\,(x_{n+1}-x_{n})+f(x_{n}).}$

x _{n + 1} için çözme verir

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.}$

İşleme rastgele bir başlangıç ​​değeri x ₀ ile başlıyoruz . (Sıfıra ne kadar yakınsa o kadar iyidir. Ancak, sıfırın nerede olabileceğine dair herhangi bir sezginin yokluğunda, bir "tahmin et ve kontrol et" yöntemi, ara değer teoremine başvurarak olasılıkları oldukça küçük bir aralığa daraltabilir .) Bu ilk tahminin bilinmeyen sıfıra yeterince yakın olması ve f ′ ( x ₀ ) ≠ 0 olması koşuluyla, yöntem genellikle yakınsayacaktır . Ayrıca, çokluk  1'in sıfırı için , yakınsama sıfırın bir komşuluğunda en azından ikinci derecedendir ( yakınsama hızına bakın ) , bu sezgisel olarak doğru basamakların sayısının her adımda kabaca iki katına çıktığı anlamına gelir. Daha fazla ayrıntı aşağıdaki analiz bölümünde bulunabilir .

Hane halkının yöntemleri benzerdir ancak daha da hızlı yakınsama için daha yüksek sıraya sahiptir. Bununla birlikte, her adım için gereken ekstra hesaplamalar, özellikle f veya türevlerinin değerlendirilmesi hesaplama açısından pahalıysa , Newton'un yöntemine göre genel performansı yavaşlatabilir .

Tarih

Adı "Newton yöntemi" türetilmiştir Isaac Newton yöntemin özel bir durum 's bilgi de analysi başına aequationes Numero terminorum infinitas (1711 yılında yayınlanan, 1669 yazılmış William Jones ve) içerisinde De metodis Fluxionum ve serierum infinitarum ( 1671'de yazılmış, John Colson tarafından 1736'da Method of Fluxions olarak çevrilmiş ve yayınlanmıştır ). Ancak onun yöntemi, yukarıda verilen modern yöntemden önemli ölçüde farklıdır. Newton, yöntemi yalnızca polinomlara uyguladı, ilk kök tahminiyle başlayıp bir dizi hata düzeltmesini çıkardı. Her düzeltmeyi polinomu kalan hata cinsinden yeniden yazmak için kullandı ve daha sonra daha yüksek dereceli terimleri ihmal ederek yeni bir düzeltme için çözdü. Yöntemi türevlerle açıkça ilişkilendirmedi veya genel bir formül sunmadı. Newton, bu yöntemi hem sayısal hem de cebirsel problemlere uyguladı ve ikinci durumda Taylor serisini üretti .

Newton, yöntemini benzer ancak daha az kesin olan Vieta yönteminden türetmiş olabilir . VIETA yönteminin özü çalışmalarında bulunabilir Pers matematikçi Şaraf-Din el-tusi halefi ise, Gıyaseddin Cemşid çözmek için Newton yöntemin bir formu kullanılmıştır x ^P - N = 0 kökleri bulmak N ( Ypma 1995). Newton'un karekök hesaplama yönteminin özel bir durumu eski zamanlardan beri biliniyordu ve genellikle Babil yöntemi olarak adlandırılıyor .

Newton'un yöntemi, 17. yüzyıl Japon matematikçisi Seki Kōwa tarafından tek değişkenli denklemleri çözmek için kullanıldı, ancak kalkülüs ile bağlantı eksikti.

Newton'un yöntemi ilk olarak 1685'te John Wallis tarafından A Treatise of Cebir Hem Tarihsel hem de Pratik'te yayınlandı . 1690'da Joseph Raphson , Analysis aequationum universalis'te basitleştirilmiş bir açıklama yayınladı . Raphson ayrıca yöntemi yalnızca polinomlara uyguladı, ancak orijinal polinomdan her ardışık düzeltmeyi çıkararak Newton'un sıkıcı yeniden yazma sürecinden kaçındı. Bu, her problem için tekrar kullanılabilir bir yinelemeli ifade türetmesine izin verdi. Son olarak, 1740'ta Thomas Simpson , Newton'un yöntemini, esasen yukarıdaki açıklamayı vererek, kalkülüs kullanarak genel doğrusal olmayan denklemleri çözmek için yinelemeli bir yöntem olarak tanımladı. Aynı yayında, Simpson ayrıca iki denklemli sistemlere genelleme verir ve Newton'un yönteminin gradyanı sıfıra ayarlayarak optimizasyon problemlerini çözmek için kullanılabileceğini not eder.

Arthur Cayley 1879'da The Newton-Fourier hayali probleminde Newton'un yöntemini, derecesi 2'den büyük ve karmaşık başlangıç ​​değerlerine sahip karmaşık polinom köklerine genelleştirmedeki zorlukları ilk fark eden kişiydi. Bu , rasyonel fonksiyonların yinelemeleri teorisinin çalışmasına giden yolu açtı .

pratik düşünceler

Newton'un yöntemi güçlü bir tekniktir—genel olarak yakınsama ikinci derecedendir: yöntem kökte yakınsadıkça, kök ile yaklaşıklık arasındaki farkın karesi alınır (doğru basamak sayısı kabaca iki katına çıkar). Ancak, yöntemin bazı zorlukları vardır.

Bir fonksiyonun türevini hesaplamada zorluk

Newton'un yöntemi, türevin doğrudan hesaplanabilmesini gerektirir. Türev için analitik bir ifade kolayca elde edilemeyebilir veya değerlendirilmesi pahalı olabilir. Bu durumlarda, fonksiyon üzerindeki iki yakın noktadan geçen bir doğrunun eğimini kullanarak türevi yaklaşık olarak hesaplamak uygun olabilir. Bu yaklaşımı kullanmak , yakınsaması Newton'un yönteminden daha yavaş olan sekant yöntemi gibi bir şeyle sonuçlanacaktır .

Yöntemin köke yakınsamaması

Uygulamadan önce Newton'un yönteminin ikinci dereceden yakınsaklığının kanıtını gözden geçirmek önemlidir . Spesifik olarak, ispatta yapılan varsayımlar gözden geçirilmelidir. İçin yöntem yakınsama başarısız durumlarda bu kanıtı yapılan varsayımlar yerine getirilmediği, bunun nedeni.

aşma

Birinci türev belirli bir kökün komşuluğunda iyi davranmazsa, yöntem o kökten uzaklaşabilir ve uzaklaşabilir. Kökün komşuluğunda türevinin iyi davranmadığı tek köklü bir fonksiyon örneği,

${\displaystyle f(x)=|x|^{a},\quad 0<a<{\tfrac {1}{2}}}$

bunun için kökün aşılacağı ve x dizisinin ayrılacağı . İçin bir = 1/2, kök hala aşılacak, ancak dizi iki değer arasında salınacak. İçin1/2< A <1 , kök hala üstten su olacak ama dizi yakınsama olacak ve için bir ≥ 1 kök hiç üstten su olmayacaktır.

Bazı durumlarda, Newton'un yöntemi ardışık aşırı gevşeme kullanılarak stabilize edilebilir veya aynı yöntem kullanılarak yakınsama hızı artırılabilir.

Sabit nokta

Bir halinde , sabit bir nokta işlevi karşılaşıldığında, türev sıfırdır ve yöntem nedeniyle sona erer Sıfıra bölme .

Kötü ilk tahmin

İlk tahmindeki büyük bir hata, algoritmanın yakınsamamasına katkıda bulunabilir. Bu sorunun üstesinden gelmek için, genellikle analiz, günlükler, diferansiyeller veya hatta stokastik tünelleme gibi evrimsel algoritmalar kullanılarak optimize edilen fonksiyon doğrusallaştırılabilir . İyi başlangıç ​​tahminleri, nihai global optimal parametre tahminine yakındır. Doğrusal olmayan regresyonda, karesel hataların (SSE) toplamı, son parametre tahminleri bölgesinde yalnızca parabolik "yakın"dır. Burada bulunan ilk tahminler, Newton-Raphson yönteminin hızla yakınsamasına izin verecektir. Sadece burada SSE'nin Hessian matrisi pozitiftir ve SSE'nin birinci türevi sıfıra yakındır.

Yakınsama durumunun azaltılması

Newton'un yönteminin sağlam bir uygulamasında, yineleme sayısına sınırlar koymak, çözümü kökü içerdiği bilinen bir aralığa bağlamak ve yöntemi daha sağlam bir kök bulma yöntemiyle birleştirmek yaygındır.

1'den büyük çokluğun kökleri için yavaş yakınsama

Aranan kökün çokluğu birden büyükse, özel adımlar atılmadıkça yakınsama oranı yalnızca doğrusaldır (her adımda sabit bir faktör tarafından azaltılan hatalar). Birbirine yakın iki veya daha fazla kök olduğunda, ikinci dereceden yakınsamanın belirgin olması için yinelemelerin bunlardan birine yeterince yaklaşması için birçok yineleme gerekebilir. Bununla birlikte, kökün çokluğu biliniyorsa, aşağıdaki değiştirilmiş algoritma ikinci dereceden yakınsama oranını korur: ${\görüntüleme stili m}$

${\displaystyle x_{n+1}=x_{n}-m{\frac {f(x_{n})}{f'(x_{n})}}.}$

Bu, art arda aşırı gevşeme kullanmaya eşdeğerdir . Öte yandan, kökün çokluğu m bilinmiyorsa, bir veya iki iterasyon gerçekleştirdikten sonra tahmin yapmak ve daha sonra yakınsama oranını artırmak için bu değeri kullanmak mümkündür. ${\görüntüleme stili m}$

Kökün m çokluğu sonlu ise, o zaman g ( x ) = f ( x ) / f′ ( x ) birden çokluk ile aynı yerde bir köke sahip olacaktır. g ( x )' in kökünü bulmak için Newton'un yöntemini uygulayarak kurtarır. kuadratik yakınsama çoğu durumda f ( x ) ' in ikinci türevini içermesine rağmen . Özellikle basit bir durumda, eğer f ( x ) = x ^{m ise,} o zaman g ( x ) = x / m ve Newton'un yöntemi, kökü şu şekilde tek bir yinelemede bulur:

${\displaystyle x_{n+1}=x_{n}-{\frac {g(x_{n})}{g'(x_{n})}}=x_{n}-{\frac {x_{ n}/m}{1/m}}=0\,.}$

analiz

Fonksiyonu olduğunu varsayalım f bir de sıfır sahip a , yani f  ( α ) = 0 , ve f bir de ayırt edilebilirdir mahalle arasında a .

Eğer f sürekli türevlenebilir ve onun türevi ile sıfır olmayan  a , o zaman bir vardır mahalle arasında α tüm başlangıç değerleri için olduğu gibi x ₀ olduğu mahalle, sekans ( x _{, n} ) olacak yakınsama için α .

Fonksiyonu sürekli türevlenebilir ve türev değil 0 ise a ve bir yer alır , ikinci türevi de a sonra yakınsama kare veya daha hızlıdır. İkinci türev α'da 0 değilse , yakınsama yalnızca ikinci derecedendir. Üçüncü türev varsa ve α komşuluğunda sınırlıysa , o zaman:

${\displaystyle \Delta x_{i+1}={\frac {f''(\alpha )}{2f'(\alpha )}}(\Delta x_{i})^{2}+O(\Delta x_{i})^{3}\,,}$

nerede

${\displaystyle \Delta x_{i}\triangleq x_{i}-\alpha \,.}$

Türev, 0 ise a , o zaman yakınsama genellikle sadece doğrusaldır. Spesifik olarak, eğer f sürekli olarak iki kez türevlenebilirse, f ′ ( α ) = 0 ve f ″ ( α ) ≠ 0 , o zaman o komşuluktaki tüm x ₀ başlangıç ​​değerleri için , yineleme dizisi yakınsayan bir α komşuluğu vardır. doğrusal ile oranı Alternatif olarak 1/2, eğer f ( α ) = 0 ve F ' ( x ) ≠ 0 için x ≠ α , x  , bir de mahalle U arasında a , α a sıfır olmak üzere çokluğu r , ve eğer f ∈ C ^r ( U ) , o zaman, o komşuluktaki tüm x ₀ başlangıç ​​değerleri için , yineleme dizisinin doğrusal olarak yakınsadığı bir α komşuluğu vardır .

Bununla birlikte, patolojik durumlarda doğrusal yakınsama bile garanti edilmez.

Pratikte bu sonuçlar yereldir ve yakınsama komşuluğu önceden bilinmemektedir. Ancak küresel yakınlaşma da bazı sonuçlar var: Örneğin, bir hak mahalle verilen U ₊ ait a'dan eğer, f içinde iki defa diferensiyellenebilirdir U ₊ eğer f ' ≠ 0 , f · f " > 0 yılında U ₊ , o zaman, için her x ₀ olarak U ₊ dizisi x _k isimli monoton bir şekilde azalan a .

Newton'un yinelemeli yöntemi için ikinci dereceden yakınsama kanıtı

Göre Taylor teoremi , herhangi bir fonksiyon f  ( x ) , bir ikinci sürekli bir türeve sahiptir yakın bir kök olduğu bir noktada yaklaşık bir genişleme ile temsil edilebilir f  ( x ) . Bu kökün α olduğunu varsayalım . Daha sonra genişleme f  ( α ) yaklaşık x _n olduğu:

${\displaystyle f(\alpha )=f(x_{n})+f'(x_{n})(\alpha -x_{n})+R_{1}\,}$

( 1 )

burada Taylor serisi genişletme kalanı Lagrange biçimi olan

${\displaystyle R_{1}={\frac {1}{2!}}f''(\xi _{n})(\alpha -x_{n})^{2}\,,}$

burada ξ _n , x _n ve α arasındadır .

Yana α köküdür ( 1 ) haline gelir:

${\displaystyle 0=f(\alpha )=f(x_{n})+f'(x_{n})(\alpha -x_{n})+{\tfrac {1}{2}}f'' (\xi _{n})(\alpha -x_{n})^{2}\,}$

( 2 )

( 2 ) denklemini f ′ ( x _n ) ile bölmek ve yeniden düzenlemek

${\displaystyle {\frac {f(x_{n}))}{f'(x_{n})}}+\left(\alpha -x_{n}\sağ)={\frac {-f''( \xi _{n})}{2f'(x_{n})}}\left(\alpha -x_{n}\sağ)^{2}}$

( 3 )

x _{n + 1'in} şu şekilde tanımlandığını hatırlayarak :

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\,,}$

( 4 )

biri bunu bulur

${\displaystyle \underbrace {\alpha -x_{n+1}} _{\varepsilon _{n+1}}={\frac {-f''(\xi _{n})}{2f'(x_ {n})}}(\,\underbrace {\alpha -x_{n}} _{\varepsilon _{n}}\,)^{2}\,.}$

Yani,

${\displaystyle \varepsilon _{n+1}={\frac {-f''(\xi _{n})}{2f'(x_{n})}}\cdot {\varepsilon _{n}} ^{2}\,.}$

( 5 )

Her iki tarafın mutlak değerini alarak verir

${\displaystyle \left|{\varepsilon _{n+1}}\right|={\frac {\left|f''(\xi _{n})\right|}{2\left|f'( x_{n})\right|}}\cdot {\varepsilon _{n}}^{2}\,.}$

( 6 )

Denklem ( 6 ), aşağıdaki koşullar sağlandığında yakınsama oranının en az ikinci dereceden olduğunu gösterir:

1. f ′ ( x ) ≠ 0 ; tüm x ∈ I , I aralığıdır [ α - r , α + r ] bazı r ≥ | α - x ₀ | ;
2. f ″ ( x ) tüm x ∈ I için süreklidir;
3. x ₀ , α köküne yeterince yakındır.

Bu bağlamda yeterince yakın terimi şu anlama gelir:

Son olarak, ( 6 ) aşağıdaki şekilde ifade edilebilir:

${\displaystyle \left|{\varepsilon _{n+1}}\right|\leq M{\varepsilon _{n}}^{2}\,}$

burada M , koşul 1'de tanımlanan I aralığında ε _n ² değişken katsayısının toplamıdır , yani:

${\displaystyle M=\sup _{x\in I}{\frac {1}{2}}\left|{\frac {f''(x)}{f'(x)}}\sağ|. \,}$

Başlangıç ​​noktası x ₀ öyle seçilmelidir ki, üçüncü koşul M | ε ₀ | < 1 .

cazibe havzaları

Çekim havzalarının ayrık alt kümeleri -her bölge içinde herhangi bir noktadan yinelemenin belirli bir köke yol açacağı gerçek sayı doğrusu bölgeleri- sayıca sonsuz ve keyfi olarak küçük olabilir. Örneğin, f  ( x ) = x ³ − 2 x ² − 11 x + 12 = ( x − 4)( x − 1)( x + 3) fonksiyonu için, ardışık çekim havzalarında aşağıdaki başlangıç ​​koşulları vardır:

2.352 875 27	yakınsar	4;
2.352 841 72	yakınsar	-3;
2.352 837 35	yakınsar	4;
2.352 836 327	yakınsar	-3;
2.352 836 323	yakınsar	1.

Başarısızlık analizi

Newton'un yönteminin yalnızca belirli koşullar yerine getirildiğinde yakınsaması garanti edilir. İkinci dereceden yakınsaklığın ispatında yapılan varsayımlar karşılanırsa, yöntem yakınsayacaktır. Aşağıdaki alt bölümler için yöntemin yakınsamaması, ispatta yapılan varsayımların karşılanmadığını gösterir.

Kötü başlangıç ​​noktaları

Bazı durumlarda, yakınsama için gerekli olan fonksiyon üzerindeki koşullar sağlanır, ancak başlangıç ​​noktası olarak seçilen nokta, yöntemin yakınsadığı aralıkta değildir. Bu, örneğin, x ∞ veya −∞'ye giderken kökü aranan fonksiyon asimptotik olarak sıfıra yaklaşırsa gerçekleşebilir . Bu gibi durumlarda , sıfırın başlangıç ​​noktası olarak kullanılması için daha iyi bir tahmin elde etmek için ikiye bölme gibi farklı bir yöntem kullanılmalıdır.

Yineleme noktası sabit

İşlevi düşünün:

${\displaystyle f(x)=1-x^{2}.}$

x = 0'da bir maksimumu ve x = ±1'de f  ( x ) = 0'ın çözümleri vardır . Durağan x ₀ = 0 noktasından (türevin sıfır olduğu yerde) yinelemeye başlarsak , (0,1) noktasındaki tanjant x eksenine paralel olduğundan x ₁ tanımsız olacaktır :

${\displaystyle x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}=0-{\frac {1}{0}}. }$

Aynı sorun, başlangıç ​​noktası yerine herhangi bir yineleme noktası sabitse oluşur. Türev küçük olsa da sıfır olmasa bile, bir sonraki iterasyon çok daha kötü bir yaklaşım olacaktır.

Başlangıç ​​noktası bir döngüye girer

0 ve 1'deki x ³ − 2 x + 2'nin teğet çizgileri , x eksenini sırasıyla 1 ve 0'da keser ve Newton'un yönteminin bazı başlangıç ​​noktaları için bu değerler arasında neden salındığını gösterir.

Bazı fonksiyonlar için, bazı başlangıç ​​noktaları yakınsamayı önleyerek sonsuz bir döngüye girebilir. İzin vermek

${\displaystyle f(x)=x^{3}-2x+2\!}$

ve başlangıç ​​noktası olarak 0 alın. İlk yineleme 1 üretir ve ikinci yineleme 0'a döner, böylece dizi bir köke yakınsamadan ikisi arasında değişecektir. Aslında, bu 2 döngü kararlıdır: tüm noktaların 2 döngüye (ve dolayısıyla fonksiyonun köküne değil) asimptotik olarak yinelendiği 0 ve 1 civarında komşuluklar vardır. Genel olarak dizinin davranışı çok karmaşık olabilir (bkz. Newton fraktal ). Bu denklemin gerçek çözümü−1.769 292 35 ….

türev sorunları

Eğer fonksiyon kökün bir komşuluğunda sürekli olarak türevlenemiyorsa, çözüm ilk denemede tahmin edilmedikçe Newton'un yönteminin her zaman sapması ve başarısız olması mümkündür.

Kökte türev yok

Newton'un yönteminin ıraksadığı bir fonksiyona basit bir örnek, sıfırın küp kökünü bulmaya çalışmaktır. Küp kökü süreklidir ve türevinin tanımsız olduğu x = 0 dışında sonsuza kadar türevlenebilir:

${\displaystyle f(x)={\sqrt[{3}]{x}}.}$

Herhangi bir yineleme noktası x _n için bir sonraki yineleme noktası şöyle olacaktır:

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{\frac {{x_ {n}}^{\frac {1}{3}}}{{\frac {1}{3}}{x_{n}}^{{\frac {1}{3}}-1}}} =x_{n}-3x_{n}=-2x_{n}.}$

Algoritma çözümü aşar ve y ekseninin diğer tarafına, başlangıçta olduğundan daha uzağa iner ; Newton'un yöntemini uygulamak, aslında her yinelemede çözüme olan mesafeleri iki katına çıkarır.

Aslında, yinelemeler her f  ( x ) = | x | ^α , burada 0 < α <1/2. α = sınırlama durumunda1/2(kare kök), yinelemeler x ₀ ve − x ₀ noktaları arasında süresiz olarak değişecektir , bu nedenle bu durumda da yakınlaşmazlar.

süreksiz türev

Türev kökte sürekli değilse, kökün herhangi bir komşuluğunda yakınsama gerçekleşmeyebilir. işlevi düşünün

${\displaystyle f(x)={\begin{cases}0&{\text{if }}x=0,\\x+x^{2}\sin {\frac {2}{x}}&{\ metin{if }}x\neq 0.\end{durumlar}}}$

Türevi:

${\displaystyle f'(x)={\begin{cases}1&{\text{if }}x=0,\\1+2x\sin {\frac {2}{x}}-2\cos {\ frac {2}{x}}&{\text{if }}x\neq 0.\end{durumlar}}}$

Olarak kökün herhangi bir mahallede bulunan bu türev işareti sürekli değişiyor x iken sağa (ya da soldan) den 0 yaklaşır f  ( x ) ≥ x - x ² > 0 için 0 < x <1 .

Yani f  ( x )/f' ( x ) kökün yakınında sınırsızdır ve Newton'un yöntemi, aşağıdakilere rağmen, hemen hemen her yerde, herhangi bir mahallede farklılık gösterecektir:

• fonksiyon her yerde türevlenebilir (ve dolayısıyla süreklidir);
• kökteki türev sıfırdan farklıdır;
• f , kök dışında sonsuza kadar türevlenebilir; ve
• türev, kökün bir komşuluğunda sınırlıdır (farklı olarak f  ( x )/f' ( x )).

ikinci dereceden olmayan yakınsama

Bazı durumlarda yinelemeler birleşir ancak söz verildiği kadar hızlı bir şekilde birleşmez. Bu durumlarda daha basit yöntemler, Newton'un yöntemi kadar hızlı bir şekilde yakınsar.

sıfır türev

Kökte birinci türev sıfır ise, yakınsama ikinci dereceden olmayacaktır. İzin vermek

${\displaystyle f(x)=x^{2}\!}$

o zaman f ′ ( x ) = 2 x ve sonuç olarak

${\displaystyle x-{\frac {f(x)}{f'(x)}}={\frac {x}{2}}.}$

Dolayısıyla, fonksiyon her yerde sonsuz derecede türevlenebilir olsa da, yakınsama ikinci dereceden değildir.

Kök yalnızca "neredeyse" iki katına çıktığında bile benzer sorunlar ortaya çıkar. Örneğin, izin ver

${\displaystyle f(x)=x^{2}(x-1000)+1.}$

Sonra ilk birkaç yineleme başlayan x ₀ = 1 olan

x ₀ = 1

x ₁ =0,500 250 376 …

x ₂ =0.251 062 828 …

x ₃ =0.127 507 934 …

x ₄ =0.067 671 976 …

x ₅ =0.041 224 176 …

x ₆ =0.032 741 218 …

x ₇ =0.031 642 362 …

yakınsamanın ikinci dereceden olduğu bir noktaya ulaşmak için altı yineleme gerekir.

İkinci türev yok

Kökte ikinci türev yoksa yakınsama ikinci dereceden olmayabilir. İzin vermek

${\displaystyle f(x)=x+x^{\frac {4}{3}}.}$

Sonra

${\displaystyle f'(x)=1+{\tfrac {4}{3}}x^{\frac {1}{3}}.}$

Ve

${\displaystyle f''(x)={\tfrac {4}{9}}x^{-{\frac {2}{3}}}}$

tanımsız olduğu x = 0 olduğu durumlar hariç . Verilen x _n ,

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}={\frac {{\frac {1}{ 3}}{x_{n}}^{\frac {4}{3}}}}{1+{\tfrac {4}{3}}{x_{n}}^{\frac {1}{3} }}}}$

yaklaşık olarak 4/3x _n'nin sahip olduğu kadar kesinlik biti . Bu, ikinci dereceden yakınsama için gerekli olanın 2 katından daha azdır. Dolayısıyla Newton'un yönteminin yakınsaması (bu durumda) ikinci dereceden değildir: fonksiyon her yerde sürekli olarak türevlenebilir; türev kökte sıfır değildir; ve f , istenen kök dışında sonsuza kadar türevlenebilir.

genellemeler

karmaşık fonksiyonlar

x ⁵ − 1 = 0 için çekim havzaları ; daha koyu, yakınsamak için daha fazla yineleme anlamına gelir.

Karmaşık fonksiyonlarla uğraşırken , sıfırlarını bulmak için Newton'un yöntemi doğrudan uygulanabilir. Her sıfırın karmaşık düzlemde bir çekim havzası vardır , yöntemin o belirli sıfıra yakınsamasına neden olan tüm başlangıç ​​değerleri kümesi. Bu kümeler, gösterilen resimdeki gibi haritalanabilir. Birçok karmaşık fonksiyon için çekim havzalarının sınırları fraktallardır .

Bazı durumlarda, karmaşık düzlemde bu çekim havzalarının hiçbirinde olmayan bölgeler vardır, bu da yinelemelerin yakınsamadığı anlamına gelir. Örneğin, x ² + 1 kökünü aramak için gerçek bir başlangıç ​​koşulu kullanılırsa , sonraki tüm yinelemeler gerçek sayılar olacaktır ve bu nedenle, her iki kök de gerçek olmadığı için yinelemeler iki kökten birine yakınsayamaz. Bu durumda, hemen hemen tüm gerçek başlangıç ​​koşulları kaotik davranışa yol açarken, bazı başlangıç ​​koşulları ya sonsuza ya da herhangi bir sonlu uzunluktaki tekrar eden döngülere kadar yinelenir.

Curt McMullen, Newton'un yöntemine benzer herhangi bir olası tamamen yinelemeli algoritma için, algoritmanın, derece 4 veya daha yüksek bir polinoma uygulandığında karmaşık düzlemin bazı açık bölgelerinde sapacağını göstermiştir. Bununla birlikte, McMullen, 3. dereceden polinomlar için genel olarak yakınsak bir algoritma verdi.

Chebyshev'in üçüncü dereceden yöntemi

Nash-Moser yinelemesi

denklem sistemleri

k değişken, k fonksiyon

Newton'un yöntemi , sürekli türevlenebilir fonksiyonların (eşzamanlı) sıfırlarını bulmak anlamına gelen denklem sistemlerini çözmek için de kullanılabilir . Bu, vektör değerli tek bir fonksiyonun sıfırlarını bulmaya eşdeğerdir . Yukarıda verilen formülasyonda, skalerlerin yerini vektörler alır ve fonksiyonu türevine bölmek yerine, Jacobian matrisinin tersi ile fonksiyonu soldan çarpmak gerekir . Bu ifade ile sonuçlanır ${\görüntüleme stili k}$${\görüntüleme stili k}$${\displaystyle f:\mathbb {R} \to \mathbb {R} }$${\displaystyle F:\mathbb {R} ^{k}\to \mathbb {R} ^{k}}$${\displaystyle x_{n}}$${\displaystyle \mathbf {x} _{n}}$${\görüntüleme stili f(x_{n})}$${\ Displaystyle f'(x_{n})}$${\displaystyle F(\mathbf {x} _{n})}$${\görüntüleme stili k\kez k}$ ${\displaystyle J_{F}(\mathbf {x} _{n})}$

${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-J_{F}(\mathbf {x} _{n})^{-1}F(\mathbf { x} _{n})}$.

Jacobian matrisinin tersini hesaplamak yerine , lineer denklemler sistemini çözerek zamandan tasarruf edebilir ve sayısal kararlılığı artırabilir .

${\displaystyle J_{F}(\mathbf {x} _{n})(\mathbf {x} _{n+1}-\mathbf {x} _{n})=-F(\mathbf {x} _{n})}$

bilinmeyen için . ${\displaystyle \mathbf {x} _{n+1}-\mathbf {x} _{n}}$

k değişkenleri, m denklemleri, m > k ile

K boyutlu varyant Newton yönteminin daha büyük sistemleri çözmek için kullanılabilir k algoritması kullanır de sanki (doğrusal olmayan) denklemleri genelleştirilmiş ters kare olmayan bir Jacobi matrisi J ⁺ = ( J ^T J ) ^-1 J ^{, T} J'nin tersi yerine. Eğer doğrusal olmayan sistem bir çözüm vardır, yöntem denemeleri bir çözüm bulmak için , doğrusal olmayan en küçük kareler anlamda. Daha fazla bilgi için Gauss–Newton algoritmasına bakın .

Bir Banach uzayında

Başka bir genelleme, Newton'un Banach uzayında tanımlanan bir fonksiyonel F'nin kökünü bulma yöntemidir . Bu durumda formülasyon

${\displaystyle X_{n+1}=X_{n}-{\bigl (}F'(X_{n}){\bigr )}^{-1}F(X_{n}),\,}$

burada F' ( X _n ) , X _n'de hesaplanan Fréchet türevidir . Yöntemin uygulanabilmesi için Fréchet türevinin her X _n'de sınırlı bir şekilde ters çevrilebilir olması gerekir. Bir kökün varlığı ve yakınsaması için bir koşul Newton-Kantorovich teoremi tarafından verilir .

Aşırı p -adic numaralar

Gelen s -adic analiz, standart yöntem, bir değişken olarak, bir çok terimli denklem sahip göstermek s -adic kök olduğu Hensel lemması ile Newton yönteminden yineleme kullandığında, s -adic sayı. Gerçek sayılarla karşılaştırıldığında p -adic sayılarda toplama ve çarpmanın daha kararlı davranışı nedeniyle (özellikle, p -adiclerdeki birim top bir halkadır), Hensel lemmasındaki yakınsama, öncekinden çok daha basit hipotezler altında garanti edilebilir. gerçek çizgide klasik Newton yöntemi.

Newton-Fourier yöntemi

Newton-Fourier yöntemi, Joseph Fourier'nin Newton'un yönteminin kök yaklaşımının mutlak hatası üzerinde sınırlar sağlamak ve yine de ikinci dereceden yakınsama sağlamak için genişletilmiş halidir.

Varsayalım f  ( x ) ile ikinci türevi sürekli [ a , b ] ve f , bu aralık içinde bir kök ihtiva eder. Bu aralıkta f ′ ( x ), f ″ (x) ≠ 0 olduğunu varsayalım ( örneğin, f  ( a ) < 0 , f  ( b ) > 0 ve f ′ ( x ) > 0 ise durum budur ve f ″ ( x ) > 0 bu aralıkta). Bu, bu aralıkta benzersiz bir kök olduğunu garanti eder, buna α deyin . Bu içbükey kadar yerine aşağı içbükeydir sonra yerine f  ( x ) ile - f  ( x ) aynı kökleri çünkü.

Let x ₀ = b aralığının doğru uç noktasını olabilir ve izin z ₀ = bir aralık sol uç nokta olarak. Verilen x _n , tanımla

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}},}$

bu daha önce olduğu gibi sadece Newton'un yöntemidir. sonra tanımla

${\displaystyle z_{n+1}=z_{n}-{\frac {f(z_{n})}{f'(x_{n})}},}$

paydanın f ′ ( x _n ) olduğu ve f ′ ( z _n ) olmadığı durumlarda . x _n yinelemeleri köke doğru kesin olarak azalırken, z _n yinelemeleri köke doğru kesin olarak artacaktır. Ayrıca,

${\displaystyle \lim _{n\to \infty }{\frac {x_{n+1}-z_{n+1}}{(x_{n}-z_{n})^{2}}}= {\frac {f''(\alpha )}{2f'(\alpha )}}}$

böylece x _n ve z _n arasındaki mesafe ikinci dereceden azalır.

Yarı Newton yöntemleri

Jacobian kullanılamıyorsa veya her yinelemede hesaplanamayacak kadar pahalıysa, Newton benzeri bir yöntem kullanılabilir.

q-analog

Newton'un yöntemi , olağan türevin q-analoğu ile genelleştirilebilir .

Modifiye Newton yöntemleri

Maehly'nin prosedürü

Doğrusal olmayan bir denklemin genel olarak birden çok çözümü vardır. Ancak başlangıç ​​değeri uygun değilse, Newton'un yöntemi istenen çözüme yakınsamayabilir veya daha önce bulunan aynı çözüme yakınsayabilir. 'nin N çözümünü zaten bulduğumuzda , bir sonraki kök, Newton'un yöntemini bir sonraki denkleme uygulayarak bulunabilir: ${\görüntüleme stili f(x)=0}$

${\displaystyle F(x)={\frac {f(x)}{\prod _{i=1}^{N}(x-x_{i})}}=0.}$

Bu yöntem, ikinci tür Bessel fonksiyonunun sıfırlarını elde etmek için uygulanır .

Hirano'nun değiştirilmiş Newton yöntemi

Hirano'nun değiştirilmiş Newton yöntemi, Newton yönteminin yakınsamasını koruyan ve kararsızlığı önleyen bir modifikasyondur. Karmaşık polinomları çözmek için geliştirilmiştir.

Aralık Newton'un yöntemi

Newton'un yöntemini aralık aritmetiğiyle birleştirmek bazı bağlamlarda çok yararlıdır. Bu, normal olanlardan (fonksiyonun küçük bir değeri veya ardışık yinelemeler arasındaki değişkenin küçük bir varyasyonu olan) daha güvenilir bir durdurma kriteri sağlar. Ayrıca, bu Newton yönteminin teorik olarak yakınsadığı, ancak yetersiz kayan nokta kesinliği nedeniyle sayısal olarak ayrıldığı durumları tespit edebilir (bu, tipik olarak, değişkendeki çok küçük bir değişikliğin fonksiyonun değerini önemli ölçüde değiştirebildiği büyük dereceli polinomlar için geçerlidir). ; Wilkinson polinomuna bakınız ).

Düşünün nerede, gerçek aralığı, ve biz bir aralık uzantısına sahip olduğunu varsayalım ait , yani giriş olarak bir aralık alır ve bir aralık verir şekilde: ${\displaystyle f\in {\matematiksel {C}}^{1}(X)}$${\görüntüleme stili X}$${\görüntüleme stili F'}$${\görüntüleme stili f'}$${\görüntüleme stili F'}$${\görüntüleme stili Y\alt küme X}$${\görüntüleme stili F'(Y)}$

${\displaystyle {\begin{hizalanmış}F'([y,y])&=\{f'(y)\}\\[5pt]F'(Y)&\supseteq \{f'(y)\ orta y\in Y\}.\end{hizalanmış}}}$

Ayrıca , özellikle en fazla bir kökü olduğunu varsayıyoruz . Daha sonra Newton operatörünü şu şekilde tanımlarız: ${\displaystyle 0\notin F'(X)}$${\görüntüleme stili f}$${\görüntüleme stili X}$

${\displaystyle N(Y)=m-{\frac {f(m)}{F'(Y)}}=\left\{\left.m-{\frac {f(m)}{z}} ~\sağ|~z\in F'(Y)\sağ\}}$

nerede . Üzerindeki hipotezin iyi tanımlanmış ve bir aralık olduğunu ima ettiğini unutmayın ( aralık işlemleri hakkında daha fazla ayrıntı için aralık aritmetiğine bakın ). Bu doğal olarak aşağıdaki sıraya yol açar: ${\görüntüleme stili m\Y'de}$${\görüntüleme stili F'}$${\görüntüleme stili N(Y)}$

${\displaystyle {\begin{aligned}X_{0}&=X\\X_{k+1}&=N(X_{k})\cap X_{k}.\end{hizalı}}}$

Ortalama değer teoremi bir kök varsa garanti de , o zaman da olduğu . Ayrıca, üzerinde hipotez aktarımı sağlar en devre büyüklüğü olan zaman ve orta noktası olan bu dizi yakınsak doğru, yani burada, köküdür içerisinde . ${\görüntüleme stili f}$${\displaystyle X_{k}}$${\displaystyle X_{k+1}}$${\görüntüleme stili F'}$${\displaystyle X_{k+1}}$${\displaystyle X_{k}}$${\görüntüleme stili m}$${\görüntüleme stili Y}$${\görüntüleme stili [x^{*},x^{*}]}$${\görüntüleme stili x^{*}}$${\görüntüleme stili f}$${\görüntüleme stili X}$

Eğer sıkı içeren , genişletilmiş aralık bölümü kullanımı için iki aralıkları bir birlik oluşturur  ; birden çok kök bu nedenle otomatik olarak ayrılır ve sınırlandırılır. ${\görüntüleme stili F'(X)}$${\görüntüleme stili 0}$${\görüntüleme stili N(X)}$

Uygulamalar

Minimizasyon ve maksimizasyon problemleri

Newton'un yöntemi, bir fonksiyonun minimum veya maksimumunu bulmak için kullanılabilir . Türev, minimum veya maksimumda sıfırdır, bu nedenle Newton'un yöntemini türevi uygulayarak yerel minimum ve maksimumlar bulunabilir. yineleme olur: ${\görüntüleme stili f(x)}$

${\displaystyle x_{n+1}=x_{n}-{\frac {f'(x_{n})}{f''(x_{n})}}.}$

Sayıların ve güç serilerinin çarpımsal tersi

Önemli bir uygulamadır Newton-Raphson bölümü hızlı bir şekilde bulmak için kullanılabilir, tersi ile bir numarası a sayısı demek ki, sadece çarpma ve çıkarma ile, x şekildedir1/x= bir . Bunu f ( x ) = sıfırını bulmak olarak yeniden ifade edebiliriz.1/x- bir . elimizde f ′( x ) = −1/x ².

Newton'un yinelemesi

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}+{\frac {{\ frac {1}{x_{n}}}-a}{\frac {1}{x_{n}^{2}}}}=x_{n}(2-ax_{n}).}$

Bu nedenle, Newton'un yinelemesi yalnızca iki çarpma ve bir çıkarma işlemine ihtiyaç duyar.

Bu yöntem aynı zamanda bir kuvvet serisinin çarpımsal tersini hesaplamak için de çok verimlidir .

Transandantal denklemleri çözme

Birçok aşkın denklem Newton yöntemi kullanılarak çözülebilir. denklem verildiğinde

${\görüntüleme stili g(x)=h(x),}$

ile g ( x ) ve / veya h ( x ) bir aşkın bir fonksiyonu , bir yazma

${\görüntüleme stili f(x)=g(x)-h(x).}$

Orijinal denklemi çözen x değerleri, Newton yöntemiyle bulunabilen f  ( x ) ' in kökleridir .

Özel fonksiyonların sıfırlarının elde edilmesi

Kökünü elde etmek için Newton'un yöntemi Bessel fonksiyonlarının oranına uygulanır.

Doğrusal olmayan denklemlerin çözümleri için sayısal doğrulama

Doğrusal olmayan denklemlerin çözümlerinin sayısal doğrulaması, Newton'un yöntemi birden çok kez kullanılarak ve bir dizi çözüm adayı oluşturularak oluşturulmuştur.

CFD modellemesi

Tekrarlanan bir Newton-Raphson prosedürü stabil Dirichlet sınır koşulu empoze etmek amacıyla kullanılmıştır CFD elektrokimyasal hücre yığınları için mevcut ve muhtemel dağılımı modeli oldukça genel bir strateji olarak,.

Örnekler

Kare kök

Bir sayı karekökünü bulma sorununu ele alalım a pozitif sayı demek ki, x olacak şekilde x ² = a . Newton'un yöntemi, karekök hesaplamanın birçok yönteminden biridir . Bunu f ( x ) = x ² − a ' nın sıfırını bulmak olarak yeniden ifade edebiliriz . Biz f '( x ) = 2 x .

Örneğin, x ₀ = 10 başlangıç ​​tahminiyle 612'nin karekökünü bulmak için Newton'un yöntemiyle verilen sıra şöyledir:

${\displaystyle {\begin{matrix}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})}}&=&10-{\dfrac {10^{2}-612}{2\times 10}}&=&35.6\qquad \qquad \qquad \quad \;\,{}\\x_{2}&=&x_{1}-{\ dfrac {f(x_{1})}{f'(x_{1})}}&=&35.6-{\dfrac {35.6^{2}-612}{2\times 35.6}}&=&{ \underline {2}}6.395\,505\,617\,978\dots \\x_{3}&=&\vdots &=&\vdots &=&{\underline {24.7}}90\,635\, 492\,455\dots \\x_{4}&=&\vdots &=&\vdots &=&{\underline {24.738\,6}}88\,294\,075\dots \\x_{5} &=&\vdots &=&\vdots &=&{\underline {24.738\,633\,753\,7}}67\dots \end{matrix}}}$

doğru rakamların altı çizilidir. Yalnızca birkaç yinelemeyle, birçok ondalık basamak için doğru bir çözüm elde edilebilir.

Formülü aşağıdaki gibi yeniden düzenlemek, Babil'in karekök bulma yöntemini verir :

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{\frac {x_{ n}^{2}-a}{2x_{n}}}={\frac {1}{2}}{\biggl (}2x_{n}-{\Bigl (}x_{n}-{\frac) {a}{x_{n}}}{\Bigr )}{\biggr )}={\frac {1}{2}}{\Bigl (}x_{n}+{\frac {a}{x_{) n}}}{\Büyük )}}$

yani tahminin aritmetik ortalaması , x _n vea/x _n.

cos( x ) = x ^3'ün çözümü

x pozitif sayısını cos( x ) = x ³ ile bulma problemini ele alalım . Bunu f ( x ) = cos( x ) − x ^3'ün sıfırını bulmak olarak yeniden ifade edebiliriz . elimizde f ′( x ) = −sin( x ) − 3 x ^{2 var} . Yana cos ( x ) ≤ 1 için tüm x ve x ³ > 1 için x > 1 , bildiğimiz bizim çözüm 0 ile 1 arasında yatıyor.

Örneğin, x ₀ = 0,5 başlangıç ​​tahminiyle , Newton'un yöntemiyle verilen sıra şöyledir (başlangıç ​​değerinin 0'ın tanımsız bir sonuca yol açacağını ve çözüme yakın bir başlangıç ​​noktası kullanmanın önemini gösterdiğini unutmayın):

${\displaystyle {\begin{matrix}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})}}&=&0.5-{ \dfrac {\cos 0.5-0.5^{3}}{-\sin 0.5-3\times 0.5^{2}}}&=&1.112\,141\,637\,097\dots \\x_{2 }&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})}}&=&\vdots &=&{\underline {0.}}909\, 672\,693\,736\dots \\x_{3}&=&\vdots &=&\vdots &=&{\underline {0.86}}7\,263\,818\,209\dots \\x_ {4}&=&\vdots &=&\vdots &=&{\underline {0.865\,47}}7\,135\,298\dots \\x_{5}&=&\vdots &=&\ vdots &=&{\underline {0.865\,474\,033\,1}}11\dots \\x_{6}&=&\vdots &=&\vdots &=&{\underline {0.865\,474 \,033\,102}}\dots \end{matris}}}$

Yukarıdaki örnekte doğru rakamların altı çizilmiştir. Özellikle, x ₆ , 12 ondalık basamak için doğrudur. Ondalık noktadan sonraki doğru basamak sayısının 2'den ( x _{3 için} ) 5 ve 10'a yükseldiğini ve ikinci dereceden yakınsamanın gösterildiğini görüyoruz .

kod

Aşağıda, türevi olan bir fonksiyonun kökünü bulmak için Julia programlama dilinde Newton yönteminin bir uygulama örneği verilmiştir . ffprime

İlk tahmin x ₀ = 1 olacak ve fonksiyon f ( x ) = x ² − 2 olacak, böylece f ′( x ) = 2 x olacak .

Newton yönteminin her yeni yinelemesi ile gösterilecektir x1. Hesaplama sırasında paydanın ( yprime) çok küçük olup olmadığını ( 'den daha küçük) kontrol edeceğiz epsilon, ki bu f ′( x _n ) ≈ 0 ise durum böyle olacaktır , çünkü aksi takdirde büyük miktarda hata ortaya çıkabilir.

x0            = 1         # The initial guess
f(x)          = x^2 - 2   # The function whose root we are trying to find
fprime(x)     = 2x        # The derivative of the function
tolerance     = 1e-7      # 7 digit accuracy is desired
epsilon       = 1e-14     # Do not divide by a number smaller than this
maxIterations = 20        # Do not allow the iterations to continue indefinitely
solutionFound = false     # Have not converged to a solution yet

for i = 1:maxIterations
  y      = f(x0)
  yprime = fprime(x0)

  if abs(yprime) < epsilon            # Stop if the denominator is too small
    break
  end

  global x1 = x0 - y/yprime           # Do Newton's computation

  if abs(x1 - x0) <= tolerance        # Stop when the result is within the desired tolerance
    global solutionFound = true
    break
  end

  global x0 = x1                      # Update x0 to start the process again
end

if solutionFound
  println("Solution: ", x1)           # x1 is a solution within tolerance and maximum number of iterations
else
  println("Did not converge")         # Newton's method did not converge
end

Ayrıca bakınız

Notlar

Referanslar

• Gil, A.; Segura, J.; Temme, NM (2007). Özel fonksiyonlar için sayısal yöntemler . Endüstriyel ve Uygulamalı Matematik Derneği. ISBN'si 978-0-89871-634-4.
• Süli, Endre ; Mayers, David (2003). Sayısal Analize Giriş . Cambridge Üniversitesi Yayınları. ISBN'si 0-521-00794-1.

daha fazla okuma

• Kendall E. Atkinson, Sayısal Analize Giriş , (1989) John Wiley & Sons, Inc, ISBN  0-471-62489-6
• Tjalling J. Ypma, Newton–Raphson yönteminin tarihsel gelişimi, SIAM Review 37 (4), 531–551, 1995. doi : 10.1137/1037125 .
• Bonnans, J. Frederic; Gilbert, J. Charles; Lemarechal, Claude ; Sagastizábal, Claudia A. (2006). Sayısal optimizasyon: Teorik ve pratik yönler . Universitext (1997 Fransızca ed. çevirisinin ikinci gözden geçirilmiş baskısı). Berlin: Springer-Verlag. s. xiv+490. doi : 10.1007/978-3-540-35447-5 . ISBN'si 3-540-35445-X. MR  2265882 .
• P. Deuflhard, Doğrusal Olmayan Problemler için Newton Yöntemleri. Afin Değişmezlik ve Uyarlamalı Algoritmalar. Hesaplamalı Matematikte Springer Serisi, Cilt. 35. Springer, Berlin, 2004. ISBN  3-540-21099-7 .
• CT Kelley, Doğrusal Olmayan Denklemleri Newton Metodu ile Çözme , Algoritmaların Temellerinde no 1, SIAM, 2003. ISBN  0-89871-546-6 .
• JM Ortega, WC Rheinboldt, Doğrusal Olmayan Denklemlerin Çeşitli Değişkenlerde Yinelemeli Çözümü. Uygulamalı Matematikte Klasikler, SIAM, 2000. ISBN  0-89871-461-3 .
• Basın, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Bölüm 9. Kök Bulma ve Doğrusal Olmayan Denklem Kümeleri Önem Örneklemesi" . Sayısal Tarifler: Bilimsel Hesaplama Sanatı (3. baskı). New York: Cambridge University Press. ISBN'si 978-0-521-88068-8.. Özellikle Bölüm 9.4 , 9.6 ve 9.7'ye bakın .
• Avriel, Mordekay (1976). Doğrusal Olmayan Programlama: Analiz ve Yöntemler . Prentice Salonu. s. 216–221. ISBN'si 0-13-623603-0.

Dış bağlantılar

• "Newton yöntemi" , Matematik Ansiklopedisi , EMS Press , 2001 [1994]
• Weisstein, Eric W. "Newton Yöntemi" . Matematik Dünyası .
• Newton'un yöntemi, Citizendium.
• Mathews, J., Hızlandırılmış ve Değiştirilmiş Newton Yöntemleri, Ders notları.
• Wu, X., Denklemlerin Kökleri, Ders notları.