نرخ همگرایی

در آنالیز عددی، نرخ همگرایی را سرعتِ همگرایی یک دنباله به حد خود تعریف می‌کنند. منظور از «حد دنباله» مقداری است که دنباله در بی‌نهایت به آن همگرا می‌شود. (توجه کنید که لزوماً این مقدار وجود ندارد و می‌تواند حد یک دنباله بی‌نهایت باشد (همانند دنباله رو به رو: $a_{n}=n^{2}$) که در اینصورت اصطلاح نرخ «واگرایی» در عوض نرخ «همگرایی» برای آن تعریف می‌گردد).
همان‌طور که ذکر شود نرخ همگرایی توسط حد دنباله تعیین می‌گردد و از آنجا که حد دنباله اطلاعاتی راجع به جملات اولیهٔ دنباله (هر تعدادِ محدودی از اعضای ابتدای دنباله) به ما نمی‌دهد لذا «نرخ همگرایی» و «حد» هیچ‌کدام هیچ اطلاعی راجع به ابتدای دنباله به ما نمی‌دهند و هر دو مفاهیمی برای کاوشِ رفتار دنباله در بی‌نهایت اند.

مفهوم نرخ همگرایی در هنگام کارکردن با برخی دنباله‌ها از اهمیت ویژه ای برخوردار است، برای مثال دنباله تقریباً اعشاری (دنبالهٔ تقریبات یک عدد (مثلاً A) دنباله ای است که اعضای دنباله رفته رفته به عدد مدنظر(A) نزدیک تر می‌شوند و این نزدیکی عموماً به این صورت است که جمله بعدی نسبت به جمله قبلی یک دهم دقت بیشتر دارد، به عنوان مثال درادامه دنباله تقریبات عدد پی(π) آورده شده‌است:$a_{1}=3,a_{2}=3.1,a_{3}=3.14,...$. همان‌طور که مطرح گردید نرخ همگرایی برای بررسی دنباله تقریباتی که از یک روش تکراری محاسبه ای(iterative) همانند گاوس سیدل (یا هر روش موفق همگرایِ تکراری دیگری) از اهمیت ویژه ای برخوردار است چرا که تعیین اینکه این محاسبات تا چه حد ادامه پیدا کند از اهمیت ویژه ای برخوردار است زیرا هرچه تعداد محاسباتی که برای به دست آوردن دقتی خاص انجام می‌شود کمتر باشد هزینه ای کمتری (اعم از زمان و حافظه) مصرف می‌شود و تعیین کرانِ پایینِ تعدادِ محاسباتِ لازم به کمک نرخ همگرایی انجام می‌گیرد.

از جمله کاربردهای دیگر نرخ همگرایی می‌توان به مسایلی که به «گسسته سازیِ پروسه‌های پیوسته» می‌پردازند اشاره کرد.

سرعت همگرایی برای روندهای تکراری(itereative)

مفاهیم پایه

فرض کنید که دنباله دلخواه $a_{k}$ به عدد $L$ همگراست
۱- می‌گوییم این دنباله به صورت خطی به عدد $L$ همگراست اگر وجود داشته باشد ضریبی همانند $\mu \in (0,1)$ به طوری که داشته باشیم:

$\lim _{k\to \infty }{\frac {|a_{k+1}-L|}{|a_{k}-L|}}=\mu$

که در اینصورت به $\mu$ نرخ همگرایی می‌گویند.

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

$\lim _{k\to \infty }{\frac {|a_{k+1}-L|}{|a_{k}-L|}}=0$

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

$\lim _{k\to \infty }{\frac {|a_{k+1}-L|}{|a_{k}-L|}}=1$

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

$\lim _{k\to \infty }{\frac {|a_{k+2}-a_{k+1}|}{|a_{k+1}-a_{k}|}}=1,$

در این صورت همگرایی دنباله $a_{k}$ همگرایِ لگاریتمی است یعنی می‌گوییم این دنباله به صورت لگاریتمی به عدد$L$ همگراست. بدیهی است که سرعت این همگرایی کندتر از همگرایی‌های خطی و فراخطی است.

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

به کمک تعریف زیر به رده‌بندی همگرایی‌های فراخطی می‌پردازیم:
می‌گوییم دنباله با شدت $q$ به $L$ همگراست (توجه: $q>1$) اگر داشته باشیم که:

$\lim _{k\to \infty }{\frac {|a_{k+1}-L|}{|a_{k}-L|^{q}}}<M$

توجه کنید که $M$ یک عدد مثبت است (و لزوماً کوچکتر از ۱ نیست).

به ازای برخی مقادیر خاص $q$ نام هایِ به خصوصی درنظر گرفته شده‌است:
۱-اگر $q$ برابر ۲ باشد به دنباله $a_{k}$ همگرای مربعی (مرتبه ۲) گویند.
۲-اگر $q$ برابر ۳ باشد به دنباله $a_{k}$ همگرای مکعبی (مرتبه ۳) گویند و ….
بدیهی است که دنباله هایِ با $q>=2$ در رده دنباله‌های فراخطی قرار می‌گیرند.

یکی از روش‌های کاربردیِ محاسبه $q$ برای دنباله $a_{k}$ محاسبه دنبالهٔ زیر است که به عدد $q$ همگراست:

$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|}}.$

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

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

${\begin{aligned}b_{0}&=1,\,&&b_{1}=1,\,&&b_{2}={\frac {1}{4}},\,&&b_{3}={\frac {1}{4}},\,&&b_{4}={\frac {1}{16}},\,&&b_{5}={\frac {1}{16}},&&\ldots ,\end{aligned}}$

همان‌طور که مشاهده می‌کنید این دنباله همگراست ولی در رده دسته‌بندی‌های ذکر شده قرار نمی‌گیرد لذا در برخی مواقع تعریف گسترش یافته زیر را درنظر می‌گیرند:
تحت تعریف زیر دنباله $a_{k}$ با حداقل شدت $q$ همگرا است اگر وجود داشته باشد دنباله ای همانند $(\varepsilon _{k})$ به قسمی که شرط زیر ارضا شود:

$|x_{k}-L|\leq \varepsilon _{k}\quad {\text{for all }}k\,$

و داریم که دنباله $(\varepsilon _{k})$ به عدد $0$ با نرخ همگراییِ $q$(طبق تعریفِ پیشین) همگراست.

مثال‌ها

مثال اول:

Ak_converganceRate

دنباله $a_{k}$ با جمله عمومیِ $a_{k}={\frac {1}{2^{k}}}$:

${\begin{aligned}a_{0}&=1,\,&&a_{1}={\frac {1}{2}},\,&&a_{2}={\frac {1}{4}},\,&&a_{3}={\frac {1}{8}},\,&&a_{4}={\frac {1}{16}},\,&&a_{5}={\frac {1}{32}},\,&&\ldots \end{aligned}}$

همان‌طور که مشاهده می‌کنید دنباله $(a_{k})$به صورت خطی با نرخ $1/2$ به عدد $0$ همگرا است.

مثال دوم:

Bk_converganceRate

دنباله $b_{k}$ با جمله عمومی $b_{k}={\frac {1}{4^{\left\lfloor {\frac {k}{2}}\right\rfloor }}}$:

${\begin{aligned}b_{0}&=1,\,&&b_{1}=1,\,&&b_{2}={\frac {1}{4}},\,&&b_{3}={\frac {1}{4}},\,&&b_{4}={\frac {1}{16}},\,&&b_{5}={\frac {1}{16}},...\end{aligned}}$

همان‌طور که مشاهده می‌کنید دنباله $(b_{k})$ تحت تعریف گسترش یافته (و نه با تعریف ابتدایی) به صورت خطی با نرخ $1/2$ به عدد $0$ همگرا است.

مثال سوم:

Ck_converganceRate

دنباله $c_{k}$ با جمله عمومی $c_{k}={\frac {1}{2^{2^{k}}}}$:

${\begin{aligned}c_{0}&={\frac {1}{2}},\,&&c_{1}={\frac {1}{4}},\,&&c_{2}={\frac {1}{16}},\,&&c_{3}={\frac {1}{256}},\,&&c_{4}={\frac {1}{65\,536}},\,&&\ldots \end{aligned}}$

همان‌طور که مشاهده می‌کنید دنباله $(c_{k})$ با نرخ فراخطی (در اصل مربعی یا همان همگرایی مرتبه۲)) به صفر همگراست.

مثال چهارم:

Dk_converganceRate

دنباله $d_{k}$ با جمله عمومی $d_{k}={\frac {1}{k+1}}$:

${\begin{aligned}d_{0}&=1,\,&&d_{1}={\frac {1}{2}},\,&&d_{2}={\frac {1}{3}},\,&&d_{3}={\frac {1}{4}},\,&&d_{4}={\frac {1}{5}},\,&&d_{5}={\frac {1}{6}},\,&&\ldots \end{aligned}}$

همان‌طور که مشاهده می‌کنید دنباله $(d_{k})$ با نرخ فروخطی و لگاریتمی به صفر همگراست.

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

All_converganceRate

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

همگرایی هایِ خطی، خطی (با تعریف گسترش یافته)، فراخطی (همگرایی مربعی (مرتبه۲)) و فروخطی (لگاریتمی)

سرعت همگرایی برای روند هایِ گسسته سازی(discretization)

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

$|x_{n}-L|<Cn^{-p}{\text{ for all }}n.$

که به صورت روبه رو نمایش داده می‌شود: $|x_{n}-L|={\mathcal {O}}(n^{-p})$،(جهت آشنایی با ${\mathcal {O}}$ به نماد O بزرگ مراجعه کنید). لازم است ذکر شود که از تعریف اخیر گفته شده در حل و بررسی معادلات دیفرانسیل معمولی(ODE) استفاده می‌شود. (جهت آشنایی با معادلات دیفرانسیل معمولی به معادلات دیفرانسیل معمولیمراجعه کنید).
یکی از روش‌های رایج و کاربردی جهت محاسبهٔ نرخ همگرایی $p$ برای روندهای گسسته سازی استفاده کردن از فرمول زیراست:

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

که در اینجا $e_{\text{new}}$ و $e_{\text{old}}$ نشان دهندهٔ خطاهای جدید و قدیم اند با توجه به قدم هایِ محاسبه ایِ $h_{\text{new}}$ و $h_{\text{old}}$ .

مثال‌ها

۱- دنباله عددی $(d_{k})$ با $d_{k}=1/(k+1)$ که در قسمت قبل مطرح گردید را درنظر بگیرید. . نرخ همگرایی این دنباله برابر با ۱ است. (با استناد به تعریف ذکر شده در قسمت گسسته سازی).
۲- دنباله عددی $(a_{k})$ باجمله عمومی $a_{k}=2^{-k}$که در قسمت قبل مطرح گردید را درنظر بگیرید، همان‌طور که مشاهده می‌کنید این دنباله با شدت $p$(به ازای هر عدد $p$) همگراست، علی ذلک می‌توان گفت که این دنباله با نرخ نمایی همگراست. (با استناد به تعریف ذکر شده در قسمت گسسته سازی) توجه کنید که طبق توافق قسمت قبل (روندهای تکراری) این دنباله با نرخ خطی همگرا بود.
شدت همگرایی یک روند گسسته سازی به پارامتری به نام GTE آن مربوط است. (جهت اطلاع بیشتر به پارامترGTE مراجعه کنید.)

روش‌های ارتقای نرخ همگرایی دنباله‌ها

همان‌طور که در ابتدا مطرح شد به کمک نرخ همگرایی می‌توان در محاسبات صرفه جویی کرد زیرا به کمک آن (نرخ همگرایی) می‌توانیم حداقل تعداد تکرار لازم جهت رسیدن به دقت مطلوب را محاسبه کرد و سپس فقط تا همان تعداد مرحله محاسبات را ادامه داد. حال جالب است بدانید که روش‌هایی وجود دارد که نرخ همگرایی یک دنباله را افزایش می‌دهند به این طریق که از دنبالهٔ ابتدایی موجود دنباله ای می‌سازد که از نرخ همگرایی بیشتری نسبت به دنباله اولیه برخوردار است و بدین طریق در محاسبات انجامی صرف جویی بیشتری می‌کند.
من جملهٔ این روش‌ها می‌توان به موارد زیر اشاره کرد:
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.