הצגת המקור של הדף "סדר התכנסות"

ב[[אנליזה נומרית]], '''סדר ההתכנסות וקצב ההתכנסות''' של [[סדרה מתכנסת]] הם מדדים המציינים עד כמה מהר הסדרה מתקרבת אל הגבול שלה. עבור סדרה <math>\{x_n\}_{n=1}^\infty</math> המתכנסת ל <math>x^*</math> נאמר כי ''סדר ההתכנסות שלה הוא'' <math>q \geq 1</math> ''וקצב ההתכנסות שלה הוא'' <math>\mu</math> אם:

: <math> \lim _{n \rightarrow \infty} \frac{\left|x_{n+1}-x^{*}\right|}{\left|x_{n}-x^{*}\right|^{q}}=\mu.</math><ref>{{Cite web|last=Ruye|first=Wang|date=2015-02-12|title=Order and rate of convergence|url=http://fourier.eng.hmc.edu/e176/lectures/NM/node3.html|access-date=2020-07-31|website=hmc.edu}}</ref>

קצב ההתכנסות <math>\mu</math> נקרא גם ''קבוע השגיאה האסימפטוטית''. שימו לב שהטרמינולוגיה הזו אינה סטנדרטית וחלק מהכותבים ישתמשו ''בקצב'' כאשר מאמר זה משתמש ''בסדר'' (למשל,{{הערה|שם=rate|{{Cite web|last=Senning|first=Jonathan R.|title=Computing and Estimating the Rate of Convergence|url=http://www.math-cs.gordon.edu/courses/ma342/handouts/rate.pdf|access-date=2020-08-07|website=gordon.edu}}}} ).

בפועל, קצב וסדר ההתכנסות מספקים תובנות שימושיות בעת שימוש [[שיטה איטרטיבית|בשיטות איטרטיביות]] לחישוב קירובים נומריים. כאשר סדר ההתכנסות גבוה, בדרך כלל ניתן להגיע לקירוב הרצוי בפחות איטרציות. עם זאת, ההתנהגות [[אסימפטוטה|האסימפטוטית]] של סדרה אינה נותנת מידע סופי לגבי חלק סופי כלשהו שלה.

מושגים דומים משמשים לשיטות דיסקרטיזציה. הפתרון של הבעיה הדיסקרטית מתכנס לפתרון הבעיה הרציפה כאשר גודל הרשת הולך לאפס, ומהירות ההתכנסות היא אחד הגורמים ליעילות השיטה. עם זאת, הטרמינולוגיה, במקרה זה, שונה מהטרמינולוגיה של שיטות איטרטיביות.

האצת התכנסות סדרה היא אוסף של טכניקות לשיפור קצב ההתכנסות של סדרה כלשהי. האצה כזו מושגת בדרך כלל עם טרנספורמציות רצף.

== מהירות התכנסות לשיטות איטרטיביות ==
=== הגדרות ===
בהינתן [[סדרה (מתמטיקה)|שהסדרה]] <math>\{x_n\}_{n=1}^\infty</math> מתכנסת למספר <math>L</math>, נאמר כי היא ''מתכנסת ל <math>L</math>'' ''מסדר <math>q</math>'', ועם ''קצב התכנסות<ref name="Bockelman2005">{{Cite web|last=Bockelman|first=Brian|date=2005|title=Rates of Convergence|url=http://www.math.unl.edu/~s-bbockel1/833-notes/node7.html|access-date=2020-07-31|website=math.unl.edu}}</ref>'' <math>\mu</math>, אם<math display="block">\lim_{k \to \infty} \frac{|x_{k+1} - L|}{|x_k - L|^q} = \mu </math>עבור קבוע חיובי <math>\mu \in (0, \infty)</math> אם <math>q > 1</math>, ו <math>\mu \in (0, 1)</math> אם <math>q = 1</math>.<ref>{{Cite web|last=Hundley|first=Douglas|title=Rate of Convergence|url=http://people.whitman.edu/~hundledr/courses/M467F06/ConvAndError.pdf|url-status=live|access-date=2020-12-13|website=Whitman College}}</ref><ref>{{Cite journal|last=Porta|first=F. A.|date=1989|title=On Q-Order and R-Order of Convergence|url=https://link.springer.com/content/pdf/10.1007/BF00939805.pdf|journal=Journal of Optimization Theory and Applications|volume=63|issue=3|pages=415–431|doi=10.1007/BF00939805|access-date=2020-07-31}}</ref> עם זאת, אין דרישה כי <math>q</math> יהיה מספר שלם. לדוגמה, ל[[שיטת המיתר]], כאשר מתכנסים לשורש פולינומי, יש סדר של [[יחס הזהב|φ]] ≈ 1.618.

==== התכנסות עם סדר ====
* כאשר <math>q = 1</math> נאמר כי הסדרה ''מתכנסת ליניארית'' אם <math>\mu \in (0, 1)</math>, ונאמר שהרצף ''מתכנס Q-ליניארית ל <math>L</math>''.
* כאשר <math>q = 2</math> נאמר כי הסדרה ''מתכנסת ריבועית.''

==== הערכת סדר ====
שיטה מעשית לחישוב סדר ההתכנסות של סדרה היא באמצעות הסדרה הבאה המתכנסת ל-<math>q</math> :

: <math> \lim_{k\to\infty}{\frac{\log \left|\frac{x_{k+1} - x_k}{x_k - x_{k-1}}\right|}{\log \left|\frac{x_k - x_{k-1}}{x_{k-1} - x_{k-2}}\right|}}=q</math>{{הערה|שם=rate}}

==== הגדרות Q-התכנסות ====
בנוסף להתכנסות Q-ליניארית שהוגדרה קודם לכן, קיימות עוד כמה הגדרות ל-Q-התכנסות. נאמר כי הסדרה ''מתכנסת Q-על-ליניארית ל-<math>L</math>'' (כלומר מהיר יותר מליניארי) בכל המקרים שבהם <math> q > 1</math> וגם המקרה <math> q = 1, \mu = 0</math>.<ref>{{Cite web|last=Arnold|first=Mark|title=Order of Convergence|url=https://arnold.hosted.uark.edu/NA/Pages/OrderConv.pdf|url-status=live|access-date=2022-12-13|website=University of Arkansas}}</ref> בהינתן הגדרה 1, נאמר שהרצף ''מתכנס Q-תת-ליניארי אל <math>L</math>'' (כלומר איטי יותר מליניארי) אם <math> q = 1, \mu = 1</math>. הרצף <math>\{x_n\}_{n=1}^\infty</math> ''מתכנס לוגריתמית ל <math>L</math>'' אם הרצף מתכנס באופן Q-תת-ליניארי ובנוסף אם

: <math>\lim_{k \to \infty} \frac{|x_{k+2} - x_{k+1}|}{|x_{k+1} - x_k|} = 1</math>.<ref>{{Cite journal|last=Van Tuyl|first=Andrew H.|year=1994|title=Acceleration of convergence of a family of logarithmically convergent sequences|url=https://www.ams.org/journals/mcom/1994-63-207/S0025-5718-1994-1234428-2/S0025-5718-1994-1234428-2.pdf|journal=Mathematics of Computation|volume=63|issue=207|pages=229–246|doi=10.2307/2153571|jstor=2153571|access-date=2020-08-02}}
</ref>

שימו לב שבניגוד להגדרות קודמות, התכנסות לוגריתמית אינה נקראת "Q-לוגריתמית".

בהגדרות לעיל, הקידומת "Q-" מייצגת את המילה "quotient" מכיוון שהמונחים מוגדרים באמצעות המנה בין שני מונחים עוקבים<ref name="NocedalWright2006">{{Cite book|last=Nocedal|first=Jorge|title=Numerical Optimization|last2=Wright|first2=Stephen J.|publisher=[[Springer-Verlag]]|year=2006|isbn=978-0-387-30303-1|edition=2nd|location=Berlin, New York}}</ref>. עם זאת, לעיתים קרובות, הקידומת "Q" נשמטת ונאמר בפשטות שלרצף יש ''התכנסות ליניארית, התכנסות'' ''ריבועית'' וכו'.

==== הגדרת R-התכנסות ====
להגדרות Q-התכנסות יש חסרון בכך שהן אינן כוללות רצפים מסוימים (דוגמה לכך למטה) שמתכנסים מהר למדי, אך שיעורם משתנה. לכן, ההגדרה של שיעור ההתכנסות מורחבת כדלקמן.

נניח ש <math>\{x_n\}_{n=1}^\infty</math> מתכנס ל <math>L</math>. אומרים שהרצף ''מתכנס R-ליניארית אל <math>L</math>'' אם קיים רצף <math>\{\epsilon_n\}_{n=1}^\infty</math> כך ש

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

ו <math> (\varepsilon_k) </math> מתכנס Q-ליניארית לאפס.{{הערה|שם=Bockelman2005}} הקידומת "R-" מייצגת "שורש",,{{הערה|שם=NocedalWright2006}}.

=== דוגמאות ===
נבחן את הסדרה:

: <math>\{a_k\}_{k=1}^\infty = \left\{1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{32}, \ldots, \frac{1}{2^k}, ... \right\}. </math>

ניתן להראות שסדרה זו מתכנסת ל <math>L = 0</math>. כדי לקבוע את סוג ההתכנסות, נציב את הסדרה בהגדרה של התכנסות Q-ליניארית,

: <math>\lim_{k \to \infty} \frac{\left| 1/2^{k+1} - 0\right|}{\left| 1/ 2^k - 0 \right|} = \lim_{k \to \infty} \frac{2^k}{2^{k+1}} = \frac{1}{2}. </math>

לפיכך, אנו מוצאים כי <math>(a_k)</math> מתכנס Q-ליניארית ויש לו קצב התכנסות של <math>\mu = 1/2</math>. באופן כללי יותר, לכל <math>c \in \mathbb{R}, \mu \in (-1, 1)</math>, הרצף <math>(c\mu^k)</math> מתכנס באופן ליניארי עם הקצב <math>|\mu|</math>.

הסדרה

: <math>\{b_k\}_{k=1}^\infty = \left\{1, 1, \frac{1}{4}, \frac{1}{4}, \frac{1}{16}, \frac{1}{16}, \ldots,\frac{1}{4^{\left\lfloor \frac{k}{2} \right\rfloor}}\, \ldots \right\}</math>

מתכנסת גם היא באופן ליניארי ל-0 עם קצב 1/2 בהגדרת התכנסות R, אך לא בהגדרת התכנסות Q. (שימו לב כי <math>\lfloor x \rfloor </math> היא [[פונקציית הערך השלם|פונקציית הרצפה]])

הסדרה

: <math>\{c_k\}_{k=1}^\infty = \left\{ \frac{1}{2}, \frac{1}{4}, \frac{1}{16}, \frac{1}{256}, \frac{1}{65,\!536}, \ldots, \frac{1}{2^{2^k}} \ldots \right\}</math>

מתכנסת בצורה על-ליניארית. למעשה, היא מתכנס באופן ריבועי.

לבסוף, הרצף

: <math>\{d_k\}_{k=1}^\infty = \left\{1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \frac{1}{6}, \ldots, \frac{1}{k + 1}, \ldots \right\}</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>.|מרכז|ממוזער|600x600 פיקסלים| קצב התכנסות ליניארי, ליניארי, סופר-ליניארי (ריבועי) ותת-ליניארי]]

== מהירות התכנסות לשיטות דיסקרטיזציה ==
מצב דומה קיים עבור שיטות דיסקרטיזציה המיועדות לקירוב פונקציה <math>y = f(x)</math>, שעשויה להיות אינטגרל המקורב על ידי [[שיטות נומריות לחישוב אינטגרלים מסוימים|ריבוע מספרי]], או פתרון של [[משוואה דיפרנציאלית רגילה]] (ראו דוגמה למטה). שיטת הדיסקרטיזציה יוצרת רצף <math>{y_0,y_1,y_2,y_3,...}</math>, כאשר כל איבר <math>y_j</math> הוא פונקציה של <math>y_{j-1},y_{j-2},...</math> יחד עם מרווח הרשת <math>h</math> בין ערכים עוקבים של המשתנה הבלתי תלוי <math>x</math>. הפרמטר החשוב כאן למהירות ההתכנסות ל <math>y = f(x)</math> הוא מרווח הרשת <math>h</math>, ביחס הפוך למספר נקודות הרשת, כלומר מספר הנקודות בסדרה הנדרש כדי להגיע לערך נתון של <math>x</math>.

במקרה זה, נאמר כי הסדרה <math>\{y_n\}_{n=1}^\infty</math> מתכנסת לסדרה <math>f(x_n)</math> עם סדר ''q'' אם קיים קבוע ''C'' כזה ש

: <math> |y_n - f(x_n)| < C h^{q} \text{ for all } n. </math>

ניתן לכתוב זאת כי <math>|y_n - f(x_n)| = \mathcal{O}(h^{q})</math> באמצעות [[סימון אסימפטוטי|סימון O גדול]].

זוהי ההגדרה הרלוונטית כאשר דנים בשיטות [[שיטות נומריות לחישוב אינטגרלים מסוימים|לריבוע מספרי]] או לפתרון של משוואות דיפרנציאליות רגילות. 

שיטה מעשית להערכת סדר ההתכנסות עבור שיטת דיסקרטיזציה היא בחירת גודלי צעדים <math>h_\text{new}</math> ו <math>h_\text{old}</math> וחישוב השגיאות המתקבלות <math>e_\text{new}</math> ו <math>e_\text{old}</math>. סדר ההתכנסות מוערך לאחר מכן על ידי הנוסחה הבאה:

: <math>q \approx \frac{\log(e_\text{new}/e_\text{old})}{\log(h_\text{new}/h_\text{old})},</math>

שמקורה בכתיבת שגיאת החיתוך, במרווחי הרשת הישנים והחדשים, כמו

: <math> e = |y_n - f(x_n)| = \mathcal{O}(h^{q}). </math>

הטעות <math>e</math> הוא, ליתר דיוק, שגיאת חיתוך גלובלית (GTE), בכך שהיא מייצגת סכום של שגיאות שנצברו על פני כל <math>n</math> איטרציות, בניגוד לשגיאת חיתוך מקומית (LTE) על איטרציה אחת בלבד.

=== דוגמה לשיטות דיסקרטיזציה ===
בהינתן המשוואה הדיפרנציאלית הבאה

: <math> \frac{dy}{dx} = - \kappa y </math>

עם תנאי התחלה <math>y(0) = y_0</math>. אנו יכולים לפתור את המשוואה הזו באמצעות [[שיטת אוילר]]:

: <math> \frac{y_{n+1} - y_n}{h} = - \kappa y_{n}, </math>

אשר לאחר הזזת אגפים מובילה ל:

: <math> y_{n+1} = y_n(1 - h\kappa). </math>

במונחים של <math>y(0) = y_0</math>, סדרה זו ניתנת לכתיבה באופן הבא, מתוך [[הבינום של ניוטון]]:<math display="block"> y_{n} = y_0(1 - h\kappa)^n = y_0\left(1 - nh\kappa + n(n-1)\frac{h^2\kappa^2}{2} + \dots\right) </math>הפתרון המדויק למשוואה דיפרנציאלית זו הוא <math>y = f(x) = y_0\exp(-\kappa x)</math>, המקביל ל[[טור טיילור]] הבא ב <math>h\kappa </math> ל <math>h\kappa \ll 1</math>:<math display="block"> f(x_n) = f(nh) = y_0\exp(-\kappa nh) = y_0\left[\exp(-\kappa h)\right]^n = y_0\left(1 - h\kappa + \frac{h^2\kappa^2}{2} + \dots\right)^n
 = y_0\left(1 - nh\kappa + \frac{n^2h^2\kappa^2}{2} + \dots\right). </math>במקרה זה, שגיאת החיתוך היא

: <math> e = |y_n - f(x_n)| = \frac{nh^2\kappa^2}{2} = \mathcal{O}(h^{2}), </math>

כך <math>\{y_n\}_{n=1}^\infty</math> מתכנס ל <math>f(x_n)</math> עם שיעור התכנסות <math>q = 2</math>.

== סדרה חוזרת ונקודות קבועות ==
המקרה של סדרות חוזרת <math>x_{n+1}:=f(x_n)</math> המתרחש [[מערכת דינמית|במערכות דינמיות]] ובהקשר של [[Fixed point theorems|משפטי נקודות שבת]] שונות הוא בעל עניין מיוחד. בהנחה שהנגזרות הרלוונטיות של ''f'' הן רציפות, אפשר (בקלות) להראות שעבור נקודה קבועה <math>f(p)=p</math> כך ש <math>|f'(p)| < 1</math>, יש התכנסות ליניארית לכל ערך התחלתי <math>x_0</math> קרוב מספיק ל - ''p''. אם <math>|f'(p)| = 0</math> ו <math>|f''(p)| < 1</math>, אז יש לפחות התכנסות ריבועית, וכן הלאה. אם <math>|f'(p)| > 1</math>, אז יש [[נקודת שבת]] בלתי יציבה ואין ערך התחלתי עבורו קיימת סדרה שתתכנס ל - ''p'' (אלא אם כן יקפוץ ישירות לנקודה ''p'' עצמה).

== האצת התכנסות ==
קיימות שיטות רבות להגברת קצב ההתכנסות של סדרה נתונה, כלומר להפוך סדרה נתונה לכזו המתכנסת מהר יותר לאותו גבול. מטרת האצת קצב ההתכנסות היא לפחות את עלות המשאבים של החישוב. דוגמה אחת להאצת סדרה היא אלגוריתם דלתא בריבוע של Aitken.

שיטות אלו באופן כללי (ובפרט שיטת אייטקן) אינן מגדילות את סדר ההתכנסות, והן מועילות רק אם התכנסות מלכתחילה אינה מהירה יותר מליניארית: '''אם''' <math>(x_n)</math> מתכנס באופן ליניארי, מקבלים רצף <math>(a_n)</math> שעדיין מתכנס באופן ליניארי (למעט מקרים מיוחדים בתכנון פתולוגי), אבל מהר יותר במובן זה <math>\lim (a_n-L)/(x_n-L)= 0</math>. מצד שני, אם ההתכנסות כבר בסדר גדול מ-2, שיטת Aitken לא תביא שיפור.

== הערות שוליים ==
{{הערות שוליים}}

[[קטגוריה:אנליזה נומרית]]
[[קטגוריה:אופטימיזציה מתמטית]]
[[קטגוריה:אופטימיזציה רציפה]]
[[קטגוריה:דפים עם תרגומים שלא נסקרו]]