Yakınsama oranı - Rate of convergence

Diferansiyel denklemler
Bir engelin etrafındaki hava akışını simüle etmek için kullanılan Navier-Stokes diferansiyel denklemleri
Dürbün Doğa Bilimleri Mühendislik Astronomi Fizik Kimya Biyoloji Jeoloji Uygulamalı matematik Süreklilik mekaniği Kaos teorisi Dinamik sistemler Sosyal Bilimler Ekonomi Nüfus dinamikleri
Sınıflandırma
Türler Sıradan Kısmi Diferansiyel cebirsel Integro-diferansiyel Kesirli Doğrusal Doğrusal olmayan Değişken türüne göre Bağımlı ve bağımsız değişkenler Otonom Karmaşık Birleştirilmiş / Ayrılmış Kesin Homojen  / Homojen Olmayan Özellikleri Sipariş Şebeke Gösterim
Süreçlerle ilişki Fark (ayrık analog) Stokastik Stokastik kısmi Gecikme
Çözüm
Varlık ve benzersizlik Picard-Lindelöf teoremi Peano varoluş teoremi Carathéodory'nin varoluş teoremi Cauchy-Kowalevski teoremi
Genel başlıklar Wronskiyen Faz portresi Faz boşluğu Lyapunov  / Asimptotik  / Üstel kararlılık Yakınsama oranı Seri  / Entegre çözümler Sayısal entegrasyon Dirac delta işlevi
Çözüm yöntemleri Muayene Özellikler yöntemi Euler Üstel yanıt formülü Sonlu fark   ( Krank-Nicolson ) Sonlu elemanlar Sonsuz eleman Sonlu hacim Galerkin Petrov – Galerkin Entegrasyon faktörü İntegral dönüşümler Tedirginlik teorisi Runge-Kutta Değişkenlerin ayrılması Belirlenmemiş katsayılar Parametrelerin değişimi
İnsanlar Isaac Newton Gottfried Leibniz Leonhard Euler Emile Picard Józef Maria Hoene-Wroński Ernst Lindelöf Rudolf Lipschitz Augustin-Louis Cauchy John Crank Phyllis Nicolson Carl David Tolmé Runge Martin Kutta
v t e

Olarak sayısal analizi , yakınsama sırası ve yakınsama hızı a yakınsak dizisi sekansı sınıra kadar hızlı temsil miktarlardır. Bir dizi yakınsadığını sahip olacak şekılde bahsedilen yakınsama sırasını ve yakınsama hızı ise ${\ displaystyle (x_ {n})}$${\ displaystyle x ^ {*}}$ ${\ displaystyle q \ geq 1}$ ${\ displaystyle \ mu}$

${\ displaystyle \ lim _ {n \ sağ ok \ infty} {\ frac {\ sol | x_ {n + 1} -x ^ {*} \ sağ |} {\ sol | x_ {n} -x ^ {*} \ sağ | ^ {q}}} = \ mu.}$

Yakınsama oranına asimptotik hata sabiti de denir . Not Bu terminoloji standart değildir ve bazı yazarlar kullanacağı oranını bu makalede kullandığı nereye düzeni (örneğin). ${\ displaystyle \ mu}$

Uygulamada, yakınsama oranı ve sırası, sayısal yaklaşımları hesaplamak için yinelemeli yöntemler kullanılırken yararlı bilgiler sağlar . Yakınsama sırası daha yüksekse, yararlı bir yaklaşım elde etmek için tipik olarak daha az yineleme gerekir. Bununla birlikte, kesin olarak konuşursak, bir dizinin asimptotik davranışı , dizinin herhangi bir sonlu parçası hakkında kesin bilgi vermez.

Ayrıklaştırma yöntemleri için benzer kavramlar kullanılır . Ayrıklaştırılmış problemin çözümü, ızgara boyutu sıfıra giderken sürekli problemin çözümüne yakınsar ve yakınsama hızı, yöntemin etkinliğinin faktörlerinden biridir. Bununla birlikte, bu durumda terminoloji, yinelemeli yöntemler için kullanılan terminolojiden farklıdır.

Seri hızlandırma , bir dizi ayrıklaştırmanın yakınsama oranını iyileştirmeye yönelik bir teknikler koleksiyonudur. Bu tür hızlanma genellikle dizi dönüşümleri ile gerçekleştirilir .

Yinelemeli yöntemler için yakınsama hızı

Q-yakınsama tanımları

Sıranın sayıya yakınsadığını varsayalım . Dizinin, Q-lineer olarak yakınsadığı söylenir, böyle bir sayı varsa, öyle ki ${\ displaystyle (x_ {k})}$${\ displaystyle L}$${\ displaystyle L}$${\ displaystyle \ mu \ in (0,1)}$

${\ displaystyle \ lim _ {k \ ile \ infty} {\ frac {| x_ {k + 1} -L |} {| x_ {k} -L |}} = \ mu.}$

Sayı , yakınsama oranı olarak adlandırılır .${\ displaystyle \ mu}$

Dizinin Q-süper ${\ displaystyle L}$ doğrusal olarak yakınsadığı söylenir (yani doğrusaldan daha hızlı)

${\ displaystyle \ lim _ {k \ ile \ infty} {\ frac {| x_ {k + 1} -L |} {| x_ {k} -L |}} = 0}$

ve Q-alt çizgisel ${\ displaystyle L}$ olarak yakınsadığı söylenir (yani doğrusaldan daha yavaş) eğer

${\ displaystyle \ lim _ {k \ ile \ infty} {\ frac {| x_ {k + 1} -L |} {| x_ {k} -L |}} = 1.}$

Dizi alt doğrusal olarak ve ek olarak yakınsarsa

${\ displaystyle \ lim _ {k \ ile \ infty} {\ frac {| x_ {k + 2} -x_ {k + 1} |} {| x_ {k + 1} -x_ {k} |}} = 1,}$

daha sonra dizinin logaritmik olarak yakınsadığı söylenir . Önceki tanımlardan farklı olarak, logaritmik yakınsamanın "Q-logaritmik" olarak adlandırılmadığına dikkat edin. ${\ displaystyle (x_ {k})}$ ${\ displaystyle L}$

Yakınsamayı daha fazla sınıflandırmak için yakınsama sırası aşağıdaki gibi tanımlanır. Sekansı, söylenen sırası ile konverjans için ${\ displaystyle q}$${\ displaystyle L}$ için ise ${\ displaystyle q \ geq 1}$

${\ displaystyle \ lim _ {k \ ile \ infty} {\ frac {| x_ {k + 1} -L |} {| x_ {k} -L | ^ {q}}} <M}$

bazı pozitif sabitler için (eğer 1'den küçük olması gerekmez ). Özellikle düzen ile yakınsama ${\ displaystyle M> 0}$${\ displaystyle q> 1}$

• ${\ displaystyle q = 1}$ doğrusal yakınsama (eğer ) olarak adlandırılır , ${\ displaystyle M <1}$
• ${\ displaystyle q = 2}$ ikinci dereceden yakınsama denir ,
• ${\ displaystyle q = 3}$ kübik yakınsama denir ,
• vb.

Bazı kaynaklar , davanın gerektirdiğinden kesinlikle daha büyük olmasını gerektirir, çünkü en iyi şekilde ayrı ayrı ele alınır. Ancak bunun bir tamsayı olması gerekli değildir . Örneğin, sekant yöntemi , normal, basit bir köke yakınsarken , φ ≈ 1.618 sırasına sahiptir . ${\ displaystyle q}$${\ displaystyle 1}$${\ displaystyle q = 1}$${\ displaystyle M <1}$${\ displaystyle q}$

Yukarıdaki tanımlarda, "Q-", "bölüm" anlamına gelir çünkü terimler, birbirini takip eden iki terim arasındaki bölüm kullanılarak tanımlanır. Bununla birlikte, çoğu zaman, "Q-" atılır ve bir dizinin basitçe doğrusal yakınsama , ikinci dereceden yakınsama vb. Olduğu söylenir .

Sipariş tahmini

Bir dizinin yakınsama sırasını hesaplamanın pratik bir yöntemi, aşağıdaki diziyi hesaplamaktır; ${\ displaystyle q}$

${\ displaystyle q \ yaklaşık {\ frac {\ log \ sol | {\ frac {x_ {k + 1} -x_ {k}} {x_ {k} -x_ {k-1}}} \ sağ |} { \ log \ left | {\ frac {x_ {k} -x_ {k-1}} {x_ {k-1} -x_ {k-2}}} \ sağ |}}.}$

R-yakınsama tanımı

Q-yakınsama tanımları, makul derecede hızlı yakınsayan, ancak hızı değişken olan aşağıdaki dizi gibi bazı dizileri içermemeleri bakımından bir eksikliğe sahiptir . Bu nedenle, yakınsama oranının tanımı aşağıdaki şekilde genişletilmiştir. ${\ displaystyle (b_ {k})}$

Bunun yakınsadığını varsayalım . Dizinin, R-doğrusal olarak yakınsadığı söylenir, böyle bir dizi varsa ${\ displaystyle (x_ {k})}$${\ displaystyle L}$${\ displaystyle L}$${\ displaystyle (\ varepsilon _ {k})}$

${\ displaystyle | x_ {k} -L | \ leq \ varepsilon _ {k} \ quad {\ text {tümü için}} k \ ,,}$

ve Q-doğrusal olarak sıfıra yakınsar. "R-" öneki "kök" anlamına gelir. ${\ displaystyle (\ varepsilon _ {k})}$

Örnekler

Sırayı düşünün

${\ displaystyle (a_ {k}) = \ sol \ {1, {\ frac {1} {2}}, {\ frac {1} {4}}, {\ frac {1} {8}}, { \ frac {1} {16}}, {\ frac {1} {32}}, \ ldots, {\ frac {1} {2 ^ {k}}}, ... \ sağ \}.}$

Bu dizinin yakınsadığı gösterilebilir . Yakınsama türünü belirlemek için diziyi Q-doğrusal yakınsama tanımına koyarız, ${\ displaystyle L = 0}$

${\ displaystyle \ lim _ {k \ ile \ infty} {\ frac {\ sol | 1/2 ^ {k + 1} -0 \ sağ |} {\ sol | 1/2 ^ {k} -0 \ sağ |}} = \ lim _ {k \ ila \ infty} {\ frac {2 ^ {k}} {2 ^ {k + 1}}} = {\ frac {1} {2}}.}$

Böylece, Q-doğrusal olarak yakınsadığını ve yakınsama oranına sahip olduğunu bulduk . Daha genel olarak, herhangi biri için , dizi hız ile doğrusal olarak birleşir . ${\ displaystyle (a_ {k})}$${\ displaystyle \ mu = 1/2}$${\ displaystyle c \ in \ mathbb {R}, \ mu \ in (-1,1)}$${\ displaystyle (c \ mu ^ {k})}$${\ displaystyle \ mu}$

Sekans

${\ displaystyle (b_ {k}) = \ sol \ {1,1, {\ frac {1} {4}}, {\ frac {1} {4}}, {\ frac {1} {16}} , {\ frac {1} {16}}, \ ldots, {\ frac {1} {4 ^ {\ left \ lfloor {\ frac {k} {2}} \ right \ rfloor}}}, \, \ noktalar \ sağ \}}$

ayrıca R-yakınsama tanımı altında 1/2 oranına sahip doğrusal olarak 0'a yakınsar, ancak Q-yakınsama tanımına göre değildir. (Not olan zemin işlevi ya da eşit daha az olan en büyük tam sayıyı verir .) ${\ displaystyle \ lfloor x \ rfloor}$${\ displaystyle x}$

Sekans

${\ displaystyle (c_ {k}) = \ sol \ {{\ frac {1} {2}}, {\ frac {1} {4}}, {\ frac {1} {16}}, {\ frac {1} {256}}, {\ frac {1} {65, \! 536}}, \ ldots, {\ frac {1} {2 ^ {2 ^ {k}}}}, \ ldots \ right \ }}$

süper doğrusal olarak birleşir. Aslında, ikinci dereceden yakınsaktır.

Son olarak, dizi

${\ displaystyle (d_ {k}) = \ sol \ {1, {\ frac {1} {2}}, {\ frac {1} {3}}, {\ frac {1} {4}}, { \ frac {1} {5}}, {\ frac {1} {6}}, \ ldots, {\ frac {1} {k + 1}}, \ ldots \ right \}}$

alt doğrusal ve logaritmik olarak birleşir.

Doğrusal, doğrusal, süper doğrusal (ikinci dereceden) ve alt doğrusal yakınsama oranları

Ayrıklaştırma yöntemleri için yakınsama hızı

Ayrıklaştırma yöntemleri için de benzer bir durum söz konusudur. Yakınsama hızı için buradaki önemli parametre yineleme sayısı k değil, ızgara noktalarının sayısı ve ızgara aralığıdır. Bu durumda, ayrıklaştırma sürecindeki ızgara noktalarının sayısı n , ızgara aralığı ile ters orantılıdır.

Bu durumda, bir dizi yakınsaması söylenen L sırası ile q sabit mevcutsa C şekildedir ${\ displaystyle (x_ {n})}$

${\ displaystyle | x_ {n} -L | <Cn ^ {- q} {\ text {tümü için}} n.}$

Bu, büyük O gösterimi kullanılarak yazılmıştır . ${\ displaystyle | x_ {n} -L | = {\ mathcal {O}} (n ^ {- q})}$

Bu, sayısal kareleme yöntemlerini veya sıradan diferansiyel denklemlerin çözümünü tartışırken ilgili tanımdır .

Bir ayrıklaştırma yöntemi için yakınsama sırasını tahmin etmek için pratik bir yöntem, adım boyutlarını seçmek olup ve ve elde edilen hataları hesaplar ve . Yakınsama sırası daha sonra aşağıdaki formülle tahmin edilir: ${\ displaystyle h _ {\ text {yeni}}}$${\ displaystyle h _ {\ text {eski}}}$${\ displaystyle e _ {\ text {yeni}}}$${\ displaystyle e _ {\ text {eski}}}$

${\ displaystyle q \ yaklaşık {\ frac {\ log (e _ {\ text {yeni}} / e _ {\ text {eski}})} {\ log (h _ {\ text {yeni}} / h _ {\ text { eski}})}}.}$

Örnekler (devam)

Dizisi ile yukarıda tanıtıldı. Bu sekans, ayrıklaştırma yöntemleri konvansiyonuna göre 1. sırayla yakınsar. ${\ displaystyle (d_ {k})}$${\ displaystyle d_ {k} = 1 / (k + 1)}$

Dizisi ile de sipariş, yukarıda yakınlaşıyor tanıtıldı, q her numara için q . Ayrıklaştırma yöntemleri için konvansiyonu kullanarak üssel olarak yakınsadığı söylenir. Ancak, yinelemeli yöntemler için konvansiyonu kullanarak yalnızca doğrusal olarak (yani, 1. sırayla) yakınsar. ${\ displaystyle (a_ {k})}$${\ displaystyle a_ {k} = 2 ^ {- k}}$

Bir ayrıklaştırma yönteminin yakınsama sırası, genel kesme hatasıyla (GTE) ilgilidir .

Yakınsamanın hızlanması

Belirli bir dizinin yakınsama oranını artırmak, yani belirli bir diziyi aynı sınıra daha hızlı yakınsayan bir diziye dönüştürmek için birçok yöntem mevcuttur . Bu tür teknikler genel olarak " seri hızlandırma " olarak bilinir . Dönüştürülen dizinin amacı, hesaplamanın hesaplama maliyetini azaltmaktır . Seri hızlanmanın bir örneği, Aitken'in delta-kare işlemidir .

Referanslar

Edebiyat

Basit tanım,

• Michelle Schatzman (2002), Sayısal analiz: matematiksel bir giriş , Clarendon Press, Oxford. ISBN   0-19-850279-6 .

Genişletilmiş tanım,

• Walter Gautschi (1997), Sayısal analiz: bir giriş, Birkhäuser, Boston. ISBN   0-8176-3895-4 .
• Endre Süli ve David Mayers (2003), Sayısal analize giriş, Cambridge University Press. ISBN   0-521-00794-1 .

Büyük O tanımı,

• Richard L. Burden ve J. Douglas Faires (2001), Sayısal Analiz (7. baskı), Brooks / Cole. ISBN   0-534-38216-9

Terimleri S doğrusal ve R doğrusal kullanılmaktadır; Taylor serisini kullanırken Büyük O tanımı şu durumlarda kullanılır:

• Nocedal, Jorge; Wright, Stephen J. (2006). Sayısal Optimizasyon (2. baskı). Berlin, New York: Springer-Verlag . s. 619 + 620. ISBN   978-0-387-30303-1 . .