نرخ همگرایی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
←نرخ همگرایی: ابرابزار |
ابرابزار |
||
خط ۶:
{{سخ}}از جمله کاربردهای دیگر نرخ همگرایی می‌توان به مسایلی که به «گسسته سازیِ پروسه‌های پیوسته» می‌پردازند اشاره کرد.
== سرعت همگرایی برای
=== مفاهیم پایه ===
فرض کنید که دنباله دلخواه <math>a_k</math> به عدد <math>L</math> همگراست
{{سخ}}
:<math> \lim_{k \to \infty} \frac{|a_{k+1} - L|}{|a_k - L|} = \mu</math>
:<math> \lim_{k \to \infty} \frac{|a_{k+1} - L|}{|a_k - L|} = 0</math>
:<math> \lim_{k \to \infty} \frac{|a_{k+1} - L|}{|a_k - L|} = 1</math>
:<math>\lim_{k \to \infty} \frac{|a_{k+2} - a_{k+1}|}{|a_{k+1} - a_k|} = 1,</math>
در این صورت همگرایی دنباله <math>a_k</math> همگرایِ لگاریتمی است یعنی
===
به کمک تعریف زیر به
{{سخ}}
:<math>\lim_{k \to \infty} \frac{|a_{k+1} - L|}{|a_k - L|^q} < M</math>
توجه کنید که <math>M</math> یک عدد مثبت است (و لزوماً کوچکتر از
به ازای برخی مقادیر خاص <math>q</math> نام هایِ به خصوصی درنظر گرفته
{{سخ}}
{{سخ}}
{{سخ}}بدیهی است که دنباله هایِ با <math>q>=2</math> در رده
یکی از
:<math>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|}.</math>
=== بهبود و گسترش تعریف فوق ===
اشکال تعاریف فوق در این است که این تعاریف برخی دنباله هارا که همگرااند اما سرعت همگراییشان متغیر است را درنظر
(با جمله عمومی <math>b_k = \frac1{4^{\left\lfloor \frac{k}{2} \right\rfloor}}</math>)را درنظر
:<math>\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}</math>
{{سخ}}تحت تعریف زیر دنباله <math>a_k</math> با حداقل شدت <math>q</math> همگرا است اگر وجود داشته باشد دنباله ای همانند <math>(\varepsilon_k)</math> به قسمی که شرط زیر ارضا شود:
سطر ۵۲ ⟵ ۵۳:
</math>
===
مثال اول:
{{سخ}}دنباله <math>a_k</math> با جمله عمومیِ <math>a_k = \frac1{2^k}</math>:
:<math>\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}</math>
{{سخ}}دنباله <math>b_k</math> با جمله عمومی <math>b_k = \frac1{4^{\left\lfloor \frac{k}{2} \right\rfloor}}</math>:
سطر ۷۱ ⟵ ۷۲:
\end{align}</math>
{{سخ}}دنباله <math>c_k</math> با جمله عمومی <math>c_k = \frac1{2^{2^k}}</math>:
:<math>\begin{align}
c_0 &= \frac12 ,\, &&c_1 = \frac14 ,\, &&c_2 = \frac1{16} ,\, &&c_3 = \frac1{256} ,\, &&c_4 = \frac1{65\,536} ,\,&&\ldots
\end{align}</math>
{{سخ}}دنباله <math>d_k</math> با جمله عمومی <math>d_k = \frac1{k+1}</math>:
سطر ۸۹ ⟵ ۹۰:
\end{align}</math>
حال برای اینکه شهودمان از همگرایی بیشتر شود نمودار هر کدام از
[[پرونده:ConvergencePlots.png|بندانگشتی|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>.|همگرایی هایِ خطی، خطی (با تعریف گسترش یافته)
== سرعت همگرایی برای روند هایِ گسسته سازی(discretization) ==
همانند مطالب گفته شده برای بحث
{{سخ}}تعریف ریاضی:
:<math> |x_n - L| < C n^{-p} \text{ for all } n. </math>
که به صورت روبه رو نمایش داده
<math>|x_n - L | = \mathcal{O}(n^{-p})</math>،(جهت آشنایی با <math>\mathcal{O}</math> به [
لازم
{{سخ}}یکی از
:<math>p \approx \frac{\log(e_\text{new}/e_\text{old})}{\log(h_\text{new}/h_\text{old})},</math>
که در اینجا <math>e_\text{new}</math> و <math>e_\text{old}</math> نشان
===
{{سخ}}
[[:en:Truncation error (numerical integration)|پارامترGTE]] مراجعه کنید.
▲1- دنباله عددی <math>(d_k)</math> با <math>d_k = 1/(k+1)</math> که در قسمت قبل مطرح گردید را درنظر بگیرید. .نرخ همگرایی این دنباله برابر با 1 است.(با استناد به تعریف ذکر شده در قسمت گسسته سازی).
▲{{سخ}}2- دنباله عددی <math>(a_k)</math> باجمله عمومی <math>a_k = 2^{-k}</math>که در قسمت قبل مطرح گردید را درنظر بگیرید،همانطور که مشاهده می کنید این دنباله با شدت <math>p</math>(به ازای هر عدد <math>p</math>) همگراست،علی ذلک می توان گفت که این دنباله با نرخ نمایی همگراست.(با استناد به تعریف ذکر شده در قسمت گسسته سازی)
▲توجه کنید که طبق توافق قسمت قبل(روند های تکراری) این دنباله با نرخ خطی همگرا بود.
{{سخ}}1- [[:en:Aitken%27s delta-squared processروش|آیتکین]].
▲{{سخ}}شدت همگرایی یک روند گسسته سازی به پارامتری به نام GTE آن مربوط است.(جهت اطلاع بیشتر به
{{سخ}}2- [
▲== روش های ارتقای نرخ همگرایی دنباله ها ==
▲همانطور که در ابتدا مطرح شد به کمک نرخ همگرایی می توان در محاسبات صرفه جویی کرد زیرا به کمک آن(نرخ همگرایی) می توانیم حداقل تعداد تکرار لازم جهت رسیدن به دقت مطلوب را محاسبه کرد و سپس فقط تا همان تعداد مرحله محاسبات را ادامه داد.حال جالب است بدانید که روش هایی وجود دارد که نرخ همگرایی یک دنباله را افزایش می دهند به این طریق که از دنباله ی ابتدایی موجود دنباله ای می سازد که از نرخ همگرایی بیشتری نسبت به دنباله اولیه برخوردار است و بدین طریق در محاسبات انجامی صرف جویی بیشتری می کند.
▲{{سخ}}من جمله ی این روش ها می توان به موارد زیر اشاره کرد:
▲{{سخ}}2- [//en.wikipedia.org/wiki/Steffensen%27s_method روش استفنسن]{{سخ}}3- [//en.wikipedia.org/wiki/Richardson_extrapolation روش درون یابی ریچاردسون]{{سخ}}4- [//en.wikipedia.org/wiki/Shanks_transformation تبدیل شانکس]{{سخ}}5- [//en.wikipedia.org/wiki/Van_Wijngaarden_transformation تبدیلVan_Wijngaarden]{{سخ}}جهت آشنایی با تبدیل دنباله ها به یکدیگر به لینک رو به رو می توانید مراجعه کنید.([//en.wikipedia.org/wiki/Sequence_transformation تبدیل دنباله ها])
== منابع ==
۱- تعریف ابتدایی نرخ همگرایی از کتابِ 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.
* {{cite journal | last = Van Tuyl | first = Andrew H. | year = 1994 | title = Acceleration of convergence of a family of logarithmically convergent sequences | journal = Mathematics of Computation | url = http://www.ams.org/journals/mcom/-}}
| |||