סדר התכנסות

באנליזה נומרית, סדר ההתכנסות וקצב ההתכנסות של סדרה מתכנסת הם מדדים המציינים עד כמה מהר הסדרה מתקרבת אל הגבול שלה. עבור סדרה $\{x_{n}\}_{n=1}^{\infty }$ המתכנסת ל $x^{*}$ נאמר כי סדר ההתכנסות שלה הוא $q\geq 1$ וקצב ההתכנסות שלה הוא $\mu$ אם:

$\lim _{n\rightarrow \infty }{\frac {\left|x_{n+1}-x^{*}\right|}{\left|x_{n}-x^{*}\right|^{q}}}=\mu .$

קצב ההתכנסות $\mu$ נקרא גם קבוע השגיאה האסימפטוטית. שימו לב שהטרמינולוגיה הזו אינה סטנדרטית וחלק מהכותבים ישתמשו בקצב כאשר מאמר זה משתמש בסדר (למשל, ).

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

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

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

מהירות התכנסות לשיטות איטרטיביות

הגדרות

בהינתן שהסדרה $\{x_{n}\}_{n=1}^{\infty }$ מתכנסת למספר $L$, נאמר כי היא מתכנסת ל $L$ מסדר $q$, ועם קצב התכנסות $\mu$, אם

$$\lim _{k\to \infty }{\frac {|x_{k+1}-L|}{|x_{k}-L|^{q}}}=\mu$$

עבור קבוע חיובי $\mu \in (0,\infty )$ אם $q>1$, ו $\mu \in (0,1)$ אם $q=1$. עם זאת, אין דרישה כי $q$ יהיה מספר שלם. לדוגמה, לשיטת המיתר, כאשר מתכנסים לשורש פולינומי, יש סדר של φ ≈ 1.618.

התכנסות עם סדר

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

הערכת סדר

שיטה מעשית לחישוב סדר ההתכנסות של סדרה היא באמצעות הסדרה הבאה המתכנסת ל-$q$ :

$\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$

הגדרות Q-התכנסות

בנוסף להתכנסות Q-ליניארית שהוגדרה קודם לכן, קיימות עוד כמה הגדרות ל-Q-התכנסות. נאמר כי הסדרה מתכנסת Q-על-ליניארית ל-$L$ (כלומר מהיר יותר מליניארי) בכל המקרים שבהם $q>1$ וגם המקרה $q=1,\mu =0$. בהינתן הגדרה 1, נאמר שהרצף מתכנס Q-תת-ליניארי אל $L$ (כלומר איטי יותר מליניארי) אם $q=1,\mu =1$. הרצף $\{x_{n}\}_{n=1}^{\infty }$ מתכנס לוגריתמית ל $L$ אם הרצף מתכנס באופן Q-תת-ליניארי ובנוסף אם

$\lim _{k\to \infty }{\frac {|x_{k+2}-x_{k+1}|}{|x_{k+1}-x_{k}|}}=1$.

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

בהגדרות לעיל, הקידומת "Q-" מייצגת את המילה "quotient" מכיוון שהמונחים מוגדרים באמצעות המנה בין שני מונחים עוקבים. עם זאת, לעיתים קרובות, הקידומת "Q" נשמטת ונאמר בפשטות שלרצף יש התכנסות ליניארית, התכנסות ריבועית וכו'.

הגדרת R-התכנסות

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

נניח ש $\{x_{n}\}_{n=1}^{\infty }$ מתכנס ל $L$. אומרים שהרצף מתכנס R-ליניארית אל $L$ אם קיים רצף $\{\epsilon _{n}\}_{n=1}^{\infty }$ כך ש

$|x_{k}-L|\leq \varepsilon _{k}\quad {\text{for all }}k\,,$

ו $(\varepsilon _{k})$ מתכנס Q-ליניארית לאפס. הקידומת "R-" מייצגת "שורש",,.

דוגמאות

נבחן את הסדרה:

$\{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\}.$

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

$\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}}.$

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

הסדרה

$\{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\}$

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

הסדרה

$\{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\}$

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

לבסוף, הרצף

$\{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\}$

מתכנס באופן תת-ליניארי ולוגריתמי.

קצב התכנסות ליניארי, ליניארי, סופר-ליניארי (ריבועי) ותת-ליניארי

מהירות התכנסות לשיטות דיסקרטיזציה

מצב דומה קיים עבור שיטות דיסקרטיזציה המיועדות לקירוב פונקציה $y=f(x)$, שעשויה להיות אינטגרל המקורב על ידי ריבוע מספרי, או פתרון של משוואה דיפרנציאלית רגילה (ראו דוגמה למטה). שיטת הדיסקרטיזציה יוצרת רצף ${y_{0},y_{1},y_{2},y_{3},...}$, כאשר כל איבר $y_{j}$ הוא פונקציה של $y_{j-1},y_{j-2},...$ יחד עם מרווח הרשת $h$ בין ערכים עוקבים של המשתנה הבלתי תלוי $x$. הפרמטר החשוב כאן למהירות ההתכנסות ל $y=f(x)$ הוא מרווח הרשת $h$, ביחס הפוך למספר נקודות הרשת, כלומר מספר הנקודות בסדרה הנדרש כדי להגיע לערך נתון של $x$.

במקרה זה, נאמר כי הסדרה $\{y_{n}\}_{n=1}^{\infty }$ מתכנסת לסדרה $f(x_{n})$ עם סדר q אם קיים קבוע C כזה ש

$|y_{n}-f(x_{n})|<Ch^{q}{\text{ for all }}n.$

ניתן לכתוב זאת כי $|y_{n}-f(x_{n})|={\mathcal {O}}(h^{q})$ באמצעות סימון O גדול.

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

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

$q\approx {\frac {\log(e_{\text{new}}/e_{\text{old}})}{\log(h_{\text{new}}/h_{\text{old}})}},$

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

$e=|y_{n}-f(x_{n})|={\mathcal {O}}(h^{q}).$

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

דוגמה לשיטות דיסקרטיזציה

בהינתן המשוואה הדיפרנציאלית הבאה

${\frac {dy}{dx}}=-\kappa y$

עם תנאי התחלה $y(0)=y_{0}$. אנו יכולים לפתור את המשוואה הזו באמצעות שיטת אוילר:

${\frac {y_{n+1}-y_{n}}{h}}=-\kappa y_{n},$

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

$y_{n+1}=y_{n}(1-h\kappa ).$

במונחים של $y(0)=y_{0}$, סדרה זו ניתנת לכתיבה באופן הבא, מתוך הבינום של ניוטון:

$$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)$$

הפתרון המדויק למשוואה דיפרנציאלית זו הוא $y=f(x)=y_{0}\exp(-\kappa x)$, המקביל לטור טיילור הבא ב $h\kappa$ ל $h\kappa \ll 1$:

$$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^{2}h^{2}\kappa ^{2}}{2}}+\dots \right).$$

במקרה זה, שגיאת החיתוך היא

$e=|y_{n}-f(x_{n})|={\frac {nh^{2}\kappa ^{2}}{2}}={\mathcal {O}}(h^{2}),$

כך $\{y_{n}\}_{n=1}^{\infty }$ מתכנס ל $f(x_{n})$ עם שיעור התכנסות $q=2$.

סדרה חוזרת ונקודות קבועות

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

האצת התכנסות

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

שיטות אלו באופן כללי (ובפרט שיטת אייטקן) אינן מגדילות את סדר ההתכנסות, והן מועילות רק אם התכנסות מלכתחילה אינה מהירה יותר מליניארית: אם $(x_{n})$ מתכנס באופן ליניארי, מקבלים רצף $(a_{n})$ שעדיין מתכנס באופן ליניארי (למעט מקרים מיוחדים בתכנון פתולוגי), אבל מהר יותר במובן זה $\lim(a_{n}-L)/(x_{n}-L)=0$. מצד שני, אם ההתכנסות כבר בסדר גדול מ-2, שיטת Aitken לא תביא שיפור.