نرخ همگرایی
در آنالیز عددی، نرخ همگرایی را سرعتِ همگرایی یک دنباله به حد خود تعریف می‌کنند. منظور از «حد دنباله» مقداری است که دنباله در بی‌نهایت به آن همگرا می‌شود. (توجه کنید که لزوماً این مقدار وجود ندارد و می‌تواند حد یک دنباله بی‌نهایت باشد (همانند دنباله رو به رو: a_n = n^2) که در اینصورت اصطلاح نرخ «واگرایی» در عوض نرخ «همگرایی» برای آن تعریف می‌گردد). همان‌طور که ذکر شود نرخ همگرایی توسط حد دنباله تعیین می‌گردد و از آنجا که حد دنباله اطلاعاتی راجع به جملات اولیهٔ دنباله (هر تعدادِ محدودی از اعضای ابتدای دنباله) به ما نمی‌دهد لذا «نرخ همگرایی» و «حد» هیچ‌کدام هیچ اطلاعی راجع به ابتدای دنباله به ما نمی‌دهند و هر دو مفاهیمی برای کاوشِ رفتار دنباله در بی‌نهایت اند.
مفهوم نرخ همگرایی در هنگام کارکردن با برخی دنباله‌ها از اهمیت ویژه ای برخوردار است، برای مثال دنباله تقریباً اعشاری (دنبالهٔ تقریبات یک عدد (مثلاً A) دنباله ای است که اعضای دنباله رفته رفته به عدد مدنظر(A) نزدیک تر می‌شوند و این نزدیکی عموماً به این صورت است که جمله بعدی نسبت به جمله قبلی یک دهم دقت بیشتر دارد، به عنوان مثال درادامه دنباله تقریبات عدد پی(π) آورده شده‌است:formula_1. همان‌طور که مطرح گردید نرخ همگرایی برای بررسی دنباله تقریباتی که از یک روش تکراری محاسبه ای(iterative) همانند گاوس سیدل (یا هر روش موفق همگرایِ تکراری دیگری) از اهمیت ویژه ای برخوردار است چرا که تعیین اینکه این محاسبات تا چه حد ادامه پیدا کند از اهمیت ویژه ای برخوردار است زیرا هرچه تعداد محاسباتی که برای به دست آوردن دقتی خاص انجام می‌شود کمتر باشد هزینه ای کمتری (اعم از زمان و حافظه) مصرف می‌شود و تعیین کرانِ پایینِ تعدادِ محاسباتِ لازم به کمک نرخ همگرایی انجام می‌گیرد.
از جمله کاربردهای دیگر نرخ همگرایی می‌توان به مسایلی که به «گسسته سازیِ پروسه‌های پیوسته» می‌پردازند اشاره کرد.
فرض کنید که دنباله دلخواه formula_2 به عدد formula_3 همگراست
۱- می‌گوییم این دنباله به صورت خطی به عدد formula_3 همگراست اگر وجود داشته باشد ضریبی همانند formula_5 به طوری که داشته باشیم:
که در اینصورت به formula_7 نرخ همگرایی می‌گویند.
۲- می‌گوییم این دنباله به صورت فراخطی (سریع تر از خطی) به عدد formula_3 همگراست اگر:
۳- می‌گوییم این دنباله به صورت فروخطی (کندتر از خطی) به عدد formula_3 همگراست اگر:
۴- اگر دنباله ای که همگرایی فروخطی دارد شرط زیر را ارضا کند: در این صورت همگرایی دنباله formula_2 همگرایِ لگاریتمی است یعنی می‌گوییم این دنباله به صورت لگاریتمی به عددformula_3 همگراست. بدیهی است که سرعت این همگرایی کندتر از همگرایی‌های خطی و فراخطی است.
به کمک تعریف زیر به رده‌بندی همگرایی‌های فراخطی می‌پردازیم: می‌گوییم دنباله با شدت formula_15 به formula_3 همگراست (توجه: formula_17) اگر داشته باشیم که:
اشکال تعاریف فوق در این است که این تعاریف برخی دنباله هارا که همگرااند اما سرعت همگراییشان متغیر است را درنظر نمی‌گردد، برای مثال دنباله زیر (با جمله عمومی formula_19)را درنظر بگیرید، داریم:
همان‌طور که مشاهده می‌کنید این دنباله همگراست ولی در رده دسته‌بندی‌های ذکر شده قرار نمی‌گیرد لذا در برخی مواقع تعریف گسترش یافته زیر را درنظر می‌گیرند: تحت تعریف زیر دنباله formula_2 با حداقل شدت formula_15 همگرا است اگر وجود داشته باشد دنباله ای همانند formula_23 به قسمی که شرط زیر ارضا شود:
و داریم که دنباله formula_23 به عدد formula_26 با نرخ همگراییِ formula_15(طبق تعریفِ پیشین) همگراست.
مثال اول:
دنباله formula_2 با جمله عمومیِ formula_29:
همان‌طور که مشاهده می‌کنید دنباله formula_31به صورت خطی با نرخ formula_32 به عدد formula_26 همگرا است.
مثال دوم:
دنباله formula_34 با جمله عمومی formula_19:
همان‌طور که مشاهده می‌کنید دنباله formula_37 تحت تعریف گسترش یافته (و نه با تعریف ابتدایی) به صورت خطی با نرخ formula_32 به عدد formula_26 همگرا است.
مثال سوم:
دنباله formula_40 با جمله عمومی formula_41:
همان‌طور که مشاهده می‌کنید دنباله formula_43 با نرخ فراخطی (در اصل مربعی یا همان همگرایی مرتبه۲)) به صفر همگراست.
مثال چهارم:
دنباله formula_44 با جمله عمومی formula_45:
همان‌طور که مشاهده می‌کنید دنباله formula_47 با نرخ فروخطی و لگاریتمی به صفر همگراست.
حال نمودار همه دنباله هارادر کنار هم مشاهده می کنیم:
حال برای اینکه شهودمان از همگرایی بیشتر شود نمودار نرخ همگرایی هر کدام از دنباله‌های ذکر شده را رسم می‌کنیم: همانند مطالب گفته شده برای بحث روندهای تکراری، نرخ همگرایی با نکات و تعاریفی نسبتاً مشابه برای بحث گسسته سازی هم مطرح می‌گردد. در اینجا فرض می‌شود که خواننده محترم با مبحث گسسته سازی()آشنااست. پارامتر مهم در این حالت شماره تکرار(iteration Number)نیست بلکه در این حالت (گسسته سازی) پارامتر مهم تعداد نقاط شبکه و فضای شبکه(grid Spacing) است و این دو پارامتر رابطهٔ وارون بایکدیگر دارند. تعریف ریاضی:می‌گوییم دنباله formula_48 به عدد "L" با شدت "p" همگرا می‌شود اگر وجود داشته باشد عدد ثابت "C" به طوریکه که به صورت روبه رو نمایش داده می‌شود: formula_50،(جهت آشنایی با formula_51 به مراجعه کنید). لازم است ذکر شود که از تعریف اخیر گفته شده در حل و بررسی معادلات دیفرانسیل معمولی(ODE) استفاده می‌شود. (جهت آشنایی با معادلات دیفرانسیل معمولی به مراجعه کنید). یکی از روش‌های رایج و کاربردی جهت محاسبهٔ نرخ همگرایی formula_52 برای روندهای گسسته سازی استفاده کردن از فرمول زیراست:
که در اینجا formula_54 و formula_55 نشان دهندهٔ خطاهای جدید و قدیم اند با توجه به قدم هایِ محاسبه ایِ formula_56 و formula_57 .
۱- دنباله عددی formula_47 با formula_59 که در قسمت قبل مطرح گردید را درنظر بگیرید. . نرخ همگرایی این دنباله برابر با ۱ است. (با استناد به تعریف ذکر شده در قسمت گسسته سازی). ۲- دنباله عددی formula_31 باجمله عمومی formula_61که در قسمت قبل مطرح گردید را درنظر بگیرید، همان‌طور که مشاهده می‌کنید این دنباله با شدت formula_52(به ازای هر عدد formula_52) همگراست، علی ذلک می‌توان گفت که این دنباله با نرخ نمایی همگراست. (با استناد به تعریف ذکر شده در قسمت گسسته سازی) توجه کنید که طبق توافق قسمت قبل (روندهای تکراری) این دنباله با نرخ خطی همگرا بود. شدت همگرایی یک روند گسسته سازی به پارامتری به نام GTE آن مربوط است. (جهت اطلاع بیشتر به
همان‌طور که در ابتدا مطرح شد به کمک نرخ همگرایی می‌توان در محاسبات صرفه جویی کرد زیرا به کمک آن (نرخ همگرایی) می‌توانیم حداقل تعداد تکرار لازم جهت رسیدن به دقت مطلوب را محاسبه کرد و سپس فقط تا همان تعداد مرحله محاسبات را ادامه داد. حال جالب است بدانید که روش‌هایی وجود دارد که نرخ همگرایی یک دنباله را افزایش می‌دهند به این طریق که از دنبالهٔ ابتدایی موجود دنباله ای می‌سازد که از نرخ همگرایی بیشتری نسبت به دنباله اولیه برخوردار است و بدین طریق در محاسبات انجامی صرف جویی بیشتری می‌کند. من جملهٔ این روش‌ها می‌توان به موارد زیر اشاره کرد: 1- . 2- 3- 4- 5- جهت آشنایی با تبدیل دنباله‌ها به یکدیگر به لینک رو به رو می‌توانید مراجعه کنید. ()
۱- تعریف ابتدایی نرخ همگرایی از کتابِ Numerical analysis: a mathematical introduction, Clarendon Press, Oxford استخراج شده‌است. ۲- تعریف گسترش یافته نرخ همگرایی در منابع زیر موجود است. ۳- تعریف لگاریتمی از منبع زیر استخراج شده‌است: