نرخ همگرایی کیست؟ توضیح بده.
در آنالیز عددی، نرخ همگرایی را سرعتِ همگرایی یک دنباله به حد خود تعریف می‌کنند. منظور از «حد دنباله» مقداری است که دنباله در بی‌نهایت به آن همگرا می‌شود. (توجه کنید که لزوماً این مقدار وجود ندارد و می‌تواند حد یک دنباله بی‌نهایت باشد (همانند دنباله رو به رو: formula_1) که در اینصورت اصطلاح نرخ «واگرایی» در عوض نرخ «همگرایی» برای آن تعریف می‌گردد).همان‌طور که ذکر شود نرخ همگرایی توسط حد دنباله تعیین می‌گردد و از آنجا که حد دنباله اطلاعاتی راجع به جملات اولیهٔ دنباله (هر تعدادِ محدودی از اعضای ابتدای دنباله) به ما نمی‌دهد لذا «نرخ همگرایی» و «حد» هیچ‌کدام هیچ اطلاعی راجع به ابتدای دنباله به ما نمی‌دهند و هر دو مفاهیمی برای کاوشِ رفتار دنباله در بی‌نهایت اند.مفهوم نرخ همگرایی در هنگام کارکردن با برخی دنباله‌ها از اهمیت ویژه ای برخوردار است، برای مثال دنباله تقریباً اعشاری (دنبالهٔ تقریبات یک عدد (مثلاً A) دنباله ای است که اعضای دنباله رفته رفته به عدد مدنظر(A) نزدیک تر می‌شوند و این نزدیکی عموماً به این صورت است که جمله بعدی نسبت به جمله قبلی یک دهم دقت بیشتر دارد، به عنوان مثال درادامه دنباله تقریبات عدد پی(π) آورده شده‌است:formula_2. همان‌طور که مطرح گردید نرخ همگرایی برای بررسی دنباله تقریباتی که از یک روش تکراری محاسبه ای(iterative) همانند گاوس سیدل (یا هر روش موفق همگرایِ تکراری دیگری) از اهمیت ویژه ای برخوردار است چرا که تعیین اینکه این محاسبات تا چه حد ادامه پیدا کند از اهمیت ویژه ای برخوردار است زیرا هرچه تعداد محاسباتی که برای به دست آوردن دقتی خاص انجام می‌شود کمتر باشد هزینه ای کمتری (اعم از زمان و حافظه) مصرف می‌شود و تعیین کرانِ پایینِ تعدادِ محاسباتِ لازم به کمک نرخ همگرایی انجام می‌گیرد.از جمله کاربردهای دیگر نرخ همگرایی می‌توان به مسایلی که به «گسسته سازیِ پروسه‌های پیوسته» می‌پردازند اشاره کرد.سرعت همگرایی برای روندهای تکراری(itereative).مفاهیم پایه.فرض کنید که دنباله دلخواه formula_3 به عدد formula_4 همگراست۱- می‌گوییم این دنباله به صورت خطی به عدد formula_4 همگراست اگر وجود داشته باشد ضریبی همانند formula_6 به طوری که داشته باشیم:که در اینصورت به formula_8 نرخ همگرایی می‌گویند.۲- می‌گوییم این دنباله به صورت فراخطی (سریع تر از خطی) به عدد formula_4 همگراست اگر:۳- می‌گوییم این دنباله به صورت فروخطی (کندتر از خطی) به عدد formula_4 همگراست اگر:۴- اگر دنباله ای که همگرایی فروخطی دارد شرط زیر را ارضا کند:در این صورت همگرایی دنباله formula_3 همگرایِ لگاریتمی است یعنی می‌گوییم این دنباله به صورت لگاریتمی به عددformula_4 همگراست. بدیهی است که سرعت این همگرایی کندتر از همگرایی‌های خطی و فراخطی است.دنباله‌های فراخطی.به کمک تعریف زیر به رده‌بندی همگرایی‌های فراخطی می‌پردازیم:می‌گوییم دنباله با شدت formula_16 به formula_4 همگراست (توجه: formula_18) اگر داشته باشیم که:بهبود و گسترش تعریف فوق.اشکال تعاریف فوق در این است که این تعاریف برخی دنباله هارا که همگرااند اما سرعت همگراییشان متغیر است را درنظر نمی‌گردد، برای مثال دنباله زیر(با جمله عمومی formula_20)را درنظر بگیرید، داریم:همان‌طور که مشاهده می‌کنید این دنباله همگراست ولی در رده دسته‌بندی‌های ذکر شده قرار نمی‌گیرد لذا در برخی مواقع تعریف گسترش یافته زیر را درنظر می‌گیرند:تحت تعریف زیر دنباله formula_3 با حداقل شدت formula_16 همگرا است اگر وجود داشته باشد دنباله ای همانند formula_24 به قسمی که شرط زیر ارضا شود:و داریم که دنباله formula_24 به عدد formula_27 با نرخ همگراییِ formula_16(طبق تعریفِ پیشین) همگراست.مثال‌ها.مثال اول:دنباله formula_3 با جمله عمومیِ formula_30:همان‌طور که مشاهده می‌کنید دنباله formula_32به صورت خطی با نرخ formula_33 به عدد formula_27 همگرا است.مثال دوم:دنباله formula_35 با جمله عمومی formula_20:همان‌طور که مشاهده می‌کنید دنباله formula_38 تحت تعریف گسترش یافته (و نه با تعریف ابتدایی) به صورت خطی با نرخ formula_33 به عدد formula_27 همگرا است.مثال سوم:دنباله formula_41 با جمله عمومی formula_42:همان‌طور که مشاهده می‌کنید دنباله formula_44 با نرخ فراخطی (در اصل مربعی یا همان همگرایی مرتبه۲)) به صفر همگراست.مثال چهارم:دنباله formula_45 با جمله عمومی formula_46:همان‌طور که مشاهده می‌کنید دنباله formula_48 با نرخ فروخطی و لگاریتمی به صفر همگراست.حال نمودار همه دنباله هارادر کنار هم مشاهده می کنیم:حال برای اینکه شهودمان از همگرایی بیشتر شود نمودار نرخ همگرایی هر کدام از دنباله‌های ذکر شده را رسم می‌کنیم:سرعت همگرایی برای روند هایِ گسسته سازی(discretization).همانند مطالب گفته شده برای بحث روندهای تکراری، نرخ همگرایی با نکات و تعاریفی نسبتاً مشابه برای بحث گسسته سازی هم مطرح می‌گردد. در اینجا فرض می‌شود که خواننده محترم با مبحث گسسته سازی()آشنااست. پارامتر مهم در این حالت شماره تکرار(iteration Number)نیست بلکه در این حالت (گسسته سازی) پارامتر مهم تعداد نقاط شبکه و فضای شبکه(grid Spacing) است و این دو پارامتر رابطهٔ وارون بایکدیگر دارند.تعریف ریاضی:می‌گوییم دنباله formula_49 به عدد "L" با شدت "p" همگرا می‌شود اگر وجود داشته باشد عدد ثابت "C" به طوریکهکه به صورت روبه رو نمایش داده می‌شود:formula_51،(جهت آشنایی با formula_52 به مراجعه کنید).لازم است ذکر شود که از تعریف اخیر گفته شده در حل و بررسی معادلات دیفرانسیل معمولی(ODE) استفاده می‌شود. (جهت آشنایی با معادلات دیفرانسیل معمولی به مراجعه کنید).یکی از روش‌های رایج و کاربردی جهت محاسبهٔ نرخ همگرایی formula_53 برای روندهای گسسته سازی استفاده کردن از فرمول زیراست:که در اینجا formula_55 و formula_56 نشان دهندهٔ خطاهای جدید و قدیم اند با توجه به قدم هایِ محاسبه ایِ formula_57 و formula_58 .مثال‌ها.۱- دنباله عددی formula_48 با formula_60 که در قسمت قبل مطرح گردید را درنظر بگیرید. . نرخ همگرایی این دنباله برابر با ۱ است. (با استناد به تعریف ذکر شده در قسمت گسسته سازی).۲- دنباله عددی formula_32 باجمله عمومی formula_62که در قسمت قبل مطرح گردید را درنظر بگیرید، همان‌طور که مشاهده می‌کنید این دنباله با شدت formula_53(به ازای هر عدد formula_53) همگراست، علی ذلک می‌توان گفت که این دنباله با نرخ نمایی همگراست. (با استناد به تعریف ذکر شده در قسمت گسسته سازی)توجه کنید که طبق توافق قسمت قبل (روندهای تکراری) این دنباله با نرخ خطی همگرا بود.شدت همگرایی یک روند گسسته سازی به پارامتری به نام GTE آن مربوط است. (جهت اطلاع بیشتر به مراجعه کنید.)روش‌های ارتقای نرخ همگرایی دنباله‌ها.همان‌طور که در ابتدا مطرح شد به کمک نرخ همگرایی می‌توان در محاسبات صرفه جویی کرد زیرا به کمک آن (نرخ همگرایی) می‌توانیم حداقل تعداد تکرار لازم جهت رسیدن به دقت مطلوب را محاسبه کرد و سپس فقط تا همان تعداد مرحله محاسبات را ادامه داد. حال جالب است بدانید که روش‌هایی وجود دارد که نرخ همگرایی یک دنباله را افزایش می‌دهند به این طریق که از دنبالهٔ ابتدایی موجود دنباله ای می‌سازد که از نرخ همگرایی بیشتری نسبت به دنباله اولیه برخوردار است و بدین طریق در محاسبات انجامی صرف جویی بیشتری می‌کند.من جملهٔ این روش‌ها می‌توان به موارد زیر اشاره کرد:1- .2- 3- 4- 5- جهت آشنایی با تبدیل دنباله‌ها به یکدیگر به لینک رو به رو می‌توانید مراجعه کنید. ()منابع.۱- تعریف ابتدایی نرخ همگرایی از کتابِ Numerical analysis: a mathematical introduction, Clarendon Press, Oxford استخراج شده‌است.۲- تعریف گسترش یافته نرخ همگرایی در منابع زیر موجود است.۳- تعریف لگاریتمی از منبع زیر استخراج شده‌است: