نرخ همگرایی

مفاهیم پایه

فرض کنید که دنباله دلخواه ${\displaystyle a_k}$

${\displaystyle \underset{k\to \mathrm{\infty }}{lim}\frac{|a_{k+1}-L|}{|a_k-L|}=\mu }$

که در اینصورت به ${\displaystyle \mu }$

۲- می‌گوییم این دنباله به صورت فراخطی (سریع تر از خطی) به عدد ${\displaystyle L}$

${\displaystyle \underset{k\to \mathrm{\infty }}{lim}\frac{|a_{k+1}-L|}{|a_k-L|}=0}$

۳- می‌گوییم این دنباله به صورت فروخطی (کندتر از خطی) به عدد ${\displaystyle L}$

${\displaystyle \underset{k\to \mathrm{\infty }}{lim}\frac{|a_{k+1}-L|}{|a_k-L|}=1}$

۴- اگر دنباله ای که همگرایی فروخطی دارد شرط زیر را ارضا کند:

${\displaystyle \underset{k\to \mathrm{\infty }}{lim}\frac{|a_{k+2}-a_{k+1}|}{|a_{k+1}-a_k|}=1,}$

در این صورت همگرایی دنباله ${\displaystyle a_k}$

دنباله‌های فراخطی

به کمک تعریف زیر به رده‌بندی همگرایی‌های فراخطی می‌پردازیم:
می‌گوییم دنباله با شدت ${\displaystyle q}$

توجه کنید که ${\displaystyle M}$

به ازای برخی مقادیر خاص ${\displaystyle q}$

یکی از روش‌های کاربردیِ محاسبه ${\displaystyle q}$

${\displaystyle q\approx \frac{\log \left|\frac{a_{k+1}-a_k}{a_k-a_{k-1}}\right|}{\log \left|\frac{a_k-a_{k-1}}{a_{k-1}-a_{k-2}}\right|}.}$

بهبود و گسترش تعریف فوق

اشکال تعاریف فوق در این است که این تعاریف برخی دنباله هارا که همگرااند اما سرعت همگراییشان متغیر است را درنظر نمی‌گردد، برای مثال دنباله زیر (با جمله عمومی ${\displaystyle b_k=\frac{1}{4^{\lfloor \frac{k}{2}\rfloor }}}$

همان‌طور که مشاهده می‌کنید این دنباله همگراست ولی در رده دسته‌بندی‌های ذکر شده قرار نمی‌گیرد لذا در برخی مواقع تعریف گسترش یافته زیر را درنظر می‌گیرند:
تحت تعریف زیر دنباله ${\displaystyle a_k}$

${\displaystyle |x_k-L|\le {\epsilon }_k\text{for all }k}$

و داریم که دنباله ${\displaystyle ({\epsilon }_k)}$

مثال‌ها

مثال اول:

دنباله ${\displaystyle a_k}$

همان‌طور که مشاهده می‌کنید دنباله ${\displaystyle (a_k)}$

مثال دوم:

دنباله ${\displaystyle b_k}$

همان‌طور که مشاهده می‌کنید دنباله ${\displaystyle (b_k)}$

مثال سوم:

دنباله ${\displaystyle c_k}$

همان‌طور که مشاهده می‌کنید دنباله ${\displaystyle (c_k)}$

مثال چهارم:

دنباله ${\displaystyle d_k}$

همان‌طور که مشاهده می‌کنید دنباله ${\displaystyle (d_k)}$

حال نمودار همه دنباله هارادر کنار هم مشاهده می کنیم:

حال برای اینکه شهودمان از همگرایی بیشتر شود نمودار نرخ همگرایی هر کدام از دنباله‌های ذکر شده را رسم می‌کنیم:

همانند مطالب گفته شده برای بحث روندهای تکراری، نرخ همگرایی با نکات و تعاریفی نسبتاً مشابه برای بحث گسسته سازی هم مطرح می‌گردد. در اینجا فرض می‌شود که خواننده محترم با مبحث گسسته سازی(گسسته سازی)آشنااست. پارامتر مهم در این حالت شماره تکرار(iteration Number)نیست بلکه در این حالت (گسسته سازی) پارامتر مهم تعداد نقاط شبکه و فضای شبکه(grid Spacing) است و این دو پارامتر رابطهٔ وارون بایکدیگر دارند.
تعریف ریاضی:می‌گوییم دنباله ${\displaystyle (a_n)}$

که به صورت روبه رو نمایش داده می‌شود: ${\displaystyle |x_n-L|=\mathcal{O}(n^{-p})}$

${\displaystyle p\approx \frac{\log (e_{\text{new}}/e_{\text{old}})}{\log (h_{\text{new}}/h_{\text{old}})},}$

که در اینجا ${\displaystyle e_{\text{new}}}$

مثال‌ها

۱- دنباله عددی ${\displaystyle (d_k)}$

همان‌طور که در ابتدا مطرح شد به کمک نرخ همگرایی می‌توان در محاسبات صرفه جویی کرد زیرا به کمک آن (نرخ همگرایی) می‌توانیم حداقل تعداد تکرار لازم جهت رسیدن به دقت مطلوب را محاسبه کرد و سپس فقط تا همان تعداد مرحله محاسبات را ادامه داد. حال جالب است بدانید که روش‌هایی وجود دارد که نرخ همگرایی یک دنباله را افزایش می‌دهند به این طریق که از دنبالهٔ ابتدایی موجود دنباله ای می‌سازد که از نرخ همگرایی بیشتری نسبت به دنباله اولیه برخوردار است و بدین طریق در محاسبات انجامی صرف جویی بیشتری می‌کند.
من جملهٔ این روش‌ها می‌توان به موارد زیر اشاره کرد:
1- آیتکین.
2- روش استفنسن
3- روش درون یابی ریچاردسون
4- تبدیل شانکس
5- تبدیلVan Wijngaarden
جهت آشنایی با تبدیل دنباله‌ها به یکدیگر به لینک رو به رو می‌توانید مراجعه کنید. (تبدیل دنباله‌ها)

۱- تعریف ابتدایی نرخ همگرایی از کتابِ Numerical analysis: a mathematical introduction, Clarendon Press, Oxford استخراج شده‌است.
۲- تعریف گسترش یافته نرخ همگرایی در منابع زیر موجود است.

• http://web.mit.edu/rudin/www/MukherjeeRuSc11COLT.pdf
• Walter Gautschi (1997), Numerical analysis: an introduction, Birkhäuser, Boston.
• and David Mayers (2003), An introduction to numerical analysis, Cambridge University Press.

۳- تعریف لگاریتمی از منبع زیر استخراج شده‌است:

• Van Tuyl, Andrew H. (1994). "Acceleration of convergence of a family of logarithmically convergent sequences". Mathematics of Computation.