אנליזה נומרית/שיטת ניוטון-רפסון

שיטת ניוטון-רפסון ("המשיק המשתנה")

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

מעבירים משיק לפונקציה בניחוש ההתחלתי. מיקום חיתוך המשיק עם ציר $x$ הוא הנקודה הבאה בה מעבירים משיק נוסף לגרף הפונקציה וכך הלאה. השיפוע של כל קו כזה הוא: $f^{\prime }(x_n)=\frac{f(x_n)-0}{x_n-x_{n+1}}$ ולכן נקבל את סדרת הקירובים שלנו על ידי:

$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$

נשים לב כי השיטה עלולה לקרוס כאשר $f^{\prime }(x_n)\approx 0$ . מצב דומה מתרחש כאשר יש ריבוי שורשים. כמו כן, כאשר הם קרובים מאוד זה לזה, משפט לגראנז' מבטיח שבנקודה כלשהי ביניהם השיפוע הוא 1, דבר אשר מפריע להתכנסות השיטה. כלומר ההתכנסות תלויה בבחירת $x_0$ .

נשים לב כי בשיטה זו מניחים שהנגזרת הראשונה רציפה.

בדיקת סדר האיטרציה

כזכור, השגיאה באיטרציה ה-$n$-ית היא ${\epsilon }_n=x_n-\alpha$ . נציב לשיטה ונקבל:

${\epsilon }_{n+1}+\alpha ={\epsilon }_n+\alpha -\frac{f({\epsilon }_n+\alpha )}{f^{\prime }({\epsilon }_n+\alpha )}\Rightarrow {\epsilon }_{n+1}=\frac{{\epsilon }_n{f}^{\prime }({\epsilon }_n+\alpha )-f({\epsilon }_n+\alpha )}{f^{\prime }({\epsilon }_n+\alpha )}$

נפתח את המונה והמכנה לטור טיילור:

${\epsilon }_{n+1}=\frac{{\epsilon }_n[f^{\prime }(\alpha )+{\epsilon }_n{f}^{″}(\alpha )+\frac{{\epsilon }_n^2}{2!}{f}^{‴}(\alpha )+\cdots ]-[f(\alpha )+{\epsilon }_n{f}^{\prime }(\alpha )+\frac{{\epsilon }_n^2}{2!}{f}^{″}(\alpha )+\cdots ]}{f^{\prime }(\alpha )+{\epsilon }_n{f}^{″}(\alpha )+\frac{{\epsilon }_n^2}{2!}{f}^{‴}(\alpha )}$

לאחר שכמה אברים במונה מצטמצמים, נקבל שהאיברים המובילים של הטורים במונה ובמכנה נותנים את הביטוי הבא:

${\epsilon }_{n+1}=\frac{\frac{{\epsilon }_n^2}{2!}{f}^{″}(\alpha )+\cdots }{f^{\prime }(\alpha )+\cdots }$

אם השיטה מתכנסת, אז עבור $\underset{n\to \mathrm{\infty }}{\lim }{\epsilon }_n=0$ נקבל בקירוב:

${\epsilon }_{n+1}\approx {\epsilon }_n^2\stackrel{A}{\overbrace{\frac{f^{″}(\alpha )}{2f^{\prime }(\alpha )}}}\Rightarrow {\epsilon }_n=A^{2^n-1}{\epsilon }_0^{2^n}$

כלומר, סדר האיטרציה הוא 2.

מצד שני, אם $\alpha$ הוא שורש כפול (שורש מריבוי 2) של $f$ , אז $f(\alpha )=f^{\prime }(\alpha )=0$ ואז האברים המובילים הם:

${\epsilon }_{n+1}=\frac{\frac{{\epsilon }_n^2}{2!}{f}^{″}(\alpha )+\cdots }{{\epsilon }_n{f}^{″}(\alpha )+\cdots }$

ואז הגבול הוא בקירוב:

${\epsilon }_{n+1}\approx \frac{{\epsilon }_n}{2}$

כלומר התכנסות לינארית. באופן זה, שיטת ניוטון-רפסון מהווה אינדיקציה לשורש כפול.

ניוטון-רפסון מתוקן עבור שורש כפול

ניתן לקבל התכנסות ריבועית באמצעות סדרת הקירובים המתוקנת הבאה:

$x_{n+1}=x_n-\frac{2f(x_n)}{f^{\prime }(x_n)}$

בדיקת סדר האיטרציה

כזכור, השגיאה באיטרציה ה-$n$-ית היא ${\epsilon }_n=x_n-\alpha$ . נציב לשיטה ונקבל:

${\epsilon }_{n+1}+\alpha ={\epsilon }_n+\alpha -\frac{2f({\epsilon }_n+\alpha )}{f^{\prime }({\epsilon }_n+\alpha )}=\frac{{\epsilon }_n\cdot f^{\prime }({\epsilon }_n+\alpha )-2f({\epsilon }_n+\alpha )}{f^{\prime }({\epsilon }_n+\alpha )}$

נפתח מונה ומכנה לטור טיילור:

${\epsilon }_{n+1}=\frac{{\epsilon }_n[f^{\prime }(\alpha )+{\epsilon }_n{f}^{″}(\alpha )+\cdots ]-2[f(\alpha )+{\epsilon }_n{f}^{\prime }(\alpha )+\frac{{\epsilon }_n^2}{2!}{f}^{″}(\alpha )+\cdots ]}{f^{\prime }(\alpha )+{\epsilon }_n{f}^{″}(\alpha )+\cdots }$

כעת, שוב, נסתכל על האברים המובילים וניקח גבול כאשר $n$ גדול: ${\epsilon }_{n+1}=\frac{\frac{{\epsilon }_n^3}{3!}{f}^{‴}(\alpha )-\frac{2{\epsilon }_n^3}{3!}{f}^{‴}(\alpha )+\cdots }{{\epsilon }_n{f}^{″}(\alpha )+\cdots }\approx \frac{{\epsilon }_n^2{f}^{‴}(\alpha )}{6f^{″}(\alpha )}$

הכללה

בהינתן פונקציה f עם שורש α בריבוי s, ניתן להציג: $f(x)=(x-\alpha {)}^{s}h(x)$ כאשר $h(\alpha )\ne 0$ . במקרה זה, שיטת ניוטון-רפסון המתוקנת היא מהצורה:

$x_{n+1}=x_n-s\frac{f(x_n)}{f^{\prime }(x_n)}$

נראה שבמקרה זה ישנה התכנסות ריבועית:

${ϵ}_{n+1}=\frac{[\frac{{ϵ}_n^s}{(s-1)!}{f}^{(s)}(\alpha )+\frac{{ϵ}_n^{s+1}}{s!}{f}^{(s+1)}(\alpha )+...]}{\frac{{ϵ}_n^{s-1}}{(s-1)!}{f}^{(s)}(\alpha )+...}+$

$\frac{-s[\frac{{ϵ}_n^s}{s!}{f}^{(s)}(\alpha )+\frac{{ϵ}_n^{s+1}}{(s+1)!}{f}^{(s+1)}(\alpha )+...]}{\frac{{ϵ}_n^{s-1}}{(s-1)!}{f}^{(s)}(\alpha )+...}\approx$

$\approx \frac{f^{(s+1)}(\alpha )}{f^{(s)}(\alpha )}\frac{{ϵ}_n^2}{s(s+1)}$

עוד נוסחה מתוקנת של ניוטון-רפסון

שימו לב כי אם α הוא שורש כפול של f, אז הוא יהיה שורש בודד של $h(x)=\frac{f(x)}{f^{\prime }(x)}$. לכן אם נפעיל את שיטת ניטון רפסון על h, נקבל התכנסות מסדר 2 לאותו שורש α ובצורה המפורשת עבור f נקבל:

$x_{n+1}=x_n-\frac{f(x_n)f^{\prime }(x_n)}{[f^{\prime }(x_n){]}^2-f(x_n)f^{″}(x_n)}$

שיטת ניוטון-פורייה

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

$\{\begin{array}{cc}{x}_{n+1}& =x_n-\frac{f(x_n)}{f^{\prime }(x_n)}\\ z_{n+1}& =z_n-\frac{f(z_n)}{f^{\prime }(x_n)}\\ \end{array}$

כאשר הניחוש ההתחלתי הוא: $x_0=b,z_0=a$.

המרחק בין שתי הסדרות בכל איטרציה קטן ריבועית ונתון על ידי:

$x_n-z_n\approx (x_{n-1}-z_{n-1}{)}^2\frac{f^{″}(\alpha )}{2f^{\prime }(\alpha )}$

שיטת Steffenson

שיטת סטפנסון אף היא מודיפיקציה של שיטת ניוטון-רפסון:

$x_{n+1}=x_n-\frac{f(x_n)}{z(x_n)},z(x_n)=\frac{f[x_n+f(x_n)]-f(x_n)}{f(x_n)}$

כך שכאשר α הוא שורש בודד של f, שיטת סטפנסון היא מסדר 2 לפחות.

ראו גם

• /קוד מקור/