نرخ همگرایی

در آنالیز عددی، **نرخ همگرایی** را سرعتِ همگرایی یک دنباله به حد خود تعریف می‌کنند. منظور از «حد دنباله» مقداری است که دنباله در بی‌نهایت به آن همگرا می‌شود. (توجه کنید که لزوماً این مقدار وجود ندارد و می‌تواند حد یک دنباله بی‌نهایت باشد (همانند دنباله رو به رو: 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 = \mu

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

۲- می‌گوییم این دنباله به صورت فراخطی (سریع تر از خطی) به عدد L همگراست اگر:
: \lim_{k \to \infty} \frac = 0

۳- می‌گوییم این دنباله به صورت فروخطی (کندتر از خطی) به عدد L همگراست اگر:
: \lim_{k \to \infty} \frac = 1

۴- اگر دنباله ای که همگرایی فروخطی دارد شرط زیر را ارضا کند:
:\lim_{k \to \infty} \frac = 1,
در این صورت همگرایی دنباله a_k همگرایِ لگاریتمی است یعنی می‌گوییم این دنباله به صورت لگاریتمی به عددL همگراست. بدیهی است که سرعت این همگرایی کندتر از همگرایی‌های خطی و فراخطی است.

### دنباله‌های فراخطی
به کمک تعریف زیر به رده‌بندی همگرایی‌های فراخطی می‌پردازیم:
می‌گوییم دنباله با شدت q به L همگراست (توجه: q > 1) اگر داشته باشیم که:
:\lim_{k \to \infty} \frac{\log \left|\frac{a_k - a_{k-1}}{a_{k-1} - a_{k-2}}\right|}.

### بهبود و گسترش تعریف فوق
اشکال تعاریف فوق در این است که این تعاریف برخی دنباله هارا که همگرااند اما سرعت همگراییشان متغیر است را درنظر نمی‌گردد، برای مثال دنباله زیر
(با جمله عمومی b_k = \frac1{4^{\left\lfloor \frac{k}{2} \right\rfloor}})را درنظر بگیرید، داریم:
:\begin{align}
 b_0 &= 1 ,\,       &&b_1 = 1 ,\,  &&b_2 = \frac14 ,\,    &&b_3 = \frac14 ,\,     &&b_4 = \frac1{16} ,\,    &&b_5 = \frac1{16} , &&\ldots ,
\end{align}

همان‌طور که مشاهده می‌کنید این دنباله همگراست ولی در رده دسته‌بندی‌های ذکر شده قرار نمی‌گیرد لذا در برخی مواقع تعریف گسترش یافته زیر را درنظر می‌گیرند:
تحت تعریف زیر دنباله a_k با حداقل شدت q همگرا است اگر وجود داشته باشد دنباله ای همانند (\varepsilon_k) به قسمی که شرط زیر ارضا شود:

:
|x_k - L|\le\varepsilon_k\quad\text{for all }k \,


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

### مثال‌ها
مثال اول:

دنباله a_k با جمله عمومیِ a_k = \frac1{2^k}:

:\begin{align}
 a_0 &= 1 ,\,       &&a_1 = \frac12 ,\, &&a_2 = \frac14 ,\,    &&a_3 = \frac18 ,\,     &&a_4 = \frac1{16} ,\,    &&a_5 = \frac1{32} ,\, &&\ldots
\end{align}

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

مثال دوم:

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

:\begin{align}
  b_0 &= 1 ,\,       &&b_1 = 1 ,\,  &&b_2 = \frac14 ,\,    &&b_3 = \frac14 ,\,     &&b_4 = \frac1{16} ,\, &&b_5 = \frac1{16 },...
\end{align}

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

مثال سوم:

دنباله c_k با جمله عمومی c_k = \frac1{2^{2^k}}:

:\begin{align}
  c_0 &= \frac12 ,\, &&c_1 = \frac14 ,\, &&c_2 = \frac1{16} ,\, &&c_3 = \frac1{256} ,\, &&c_4 = \frac1{65\,536} ,\,&&\ldots
\end{align}

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

مثال چهارم:

دنباله d_k با جمله عمومی d_k = \frac1{k+1}:

:\begin{align}
   d_0 &= 1 ,\,       &&d_1 = \frac12 ,\, &&d_2 = \frac13 ,\,    &&d_3 = \frac14 ,\,     &&d_4 = \frac15 ,\,       &&d_5 = \frac16 ,\,    &&\ldots
\end{align}

همان‌طور که مشاهده می‌کنید دنباله (d_k) با نرخ فروخطی و لگاریتمی به صفر همگراست.

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

حال برای اینکه شهودمان از همگرایی بیشتر شود نمودار نرخ همگرایی هر کدام از دنباله‌های ذکر شده را رسم می‌کنیم:
بندانگشتی|alt=Plot showing the different rates of convergence for the sequences ''a''<sub>''k''</sub>, ''b''<sub>''k''</sub>, ''c''<sub>''k''</sub> and ''d''<sub>''k''</sub>.|همگرایی هایِ خطی، خطی (با تعریف گسترش یافته)، فراخطی (همگرایی مربعی (مرتبه۲)) و فروخطی (لگاریتمی)|600px|وسط

## سرعت همگرایی برای روند هایِ گسسته سازی(discretization)
همانند مطالب گفته شده برای بحث روندهای تکراری، نرخ همگرایی با نکات و تعاریفی نسبتاً مشابه برای بحث گسسته سازی هم مطرح می‌گردد. در اینجا فرض می‌شود که خواننده محترم با مبحث گسسته سازی(گسسته سازی)آشنااست. پارامتر مهم در این حالت شماره تکرار(iteration Number)نیست بلکه در این حالت (گسسته سازی) پارامتر مهم تعداد نقاط شبکه و فضای شبکه(grid Spacing) است و این دو پارامتر رابطهٔ وارون بایکدیگر دارند.
تعریف ریاضی:می‌گوییم دنباله (a_n) به عدد *L* با شدت *p* همگرا می‌شود اگر وجود داشته باشد عدد ثابت *C* به طوریکه
: |x_n - L| 
که به صورت روبه رو نمایش داده می‌شود:
|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.
۳- تعریف لگاریتمی از منبع زیر استخراج شده‌است:
* 

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