הצגת המקור של הדף "אנליזה נומרית/שיטת ניוטון-רפסון"

[[תמונה:Newton–Raphson method.png|left|thumb|250px|שיטת ניוטון-רפסון ("המשיק המשתנה")]]
{{אנליזה נומרית}}
שיטת ניוטון-רפסון - אשר ידועה גם בתור "שיטת המשיק המשתנה" - היא שכלול של שיטת המשיק הקבוע.

מעבירים משיק לפונקציה בניחוש ההתחלתי. מיקום חיתוך המשיק עם ציר <math>x</math> הוא הנקודה הבאה בה מעבירים משיק נוסף לגרף הפונקציה וכך הלאה. השיפוע של כל קו כזה הוא: <math>f'(x_n)=\frac{f(x_n)-0}{x_n-x_{n+1}}</math> ולכן נקבל את סדרת הקירובים שלנו על ידי:
:<font size=4><math>x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}</math></font size=4>
נשים לב כי השיטה עלולה לקרוס כאשר <math>f'(x_n)\approx0</math> . מצב דומה מתרחש כאשר יש ריבוי שורשים. כמו כן, כאשר הם קרובים מאוד זה לזה, משפט לגראנז' מבטיח שבנקודה כלשהי ביניהם השיפוע הוא 1, דבר אשר מפריע להתכנסות השיטה. כלומר ההתכנסות תלויה בבחירת <math>x_0</math> .

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

===בדיקת סדר האיטרציה===
כזכור, השגיאה באיטרציה ה-<math>n</math>-ית היא <math>\varepsilon_n=x_n-\alpha</math> . נציב לשיטה ונקבל:
:<font size=4><math>\varepsilon_{n+1}+\alpha=\varepsilon_n+\alpha-\frac{f(\varepsilon_n+\alpha)}{f'(\varepsilon_n+\alpha)}\quad\Rightarrow\quad\varepsilon_{n+1}=\frac{\varepsilon_nf'(\varepsilon_n+\alpha)-f(\varepsilon_n+\alpha)}{f'(\varepsilon_n+\alpha)}</math></font size=4>

נפתח את המונה והמכנה לטור טיילור:
:<font size=4><math>\varepsilon_{n+1}=\frac{\varepsilon_n\left[f'(\alpha)+\varepsilon_nf''(\alpha)+\dfrac{\varepsilon_n^2}{2!}f'''(\alpha)+\cdots\right]-\left[f(\alpha)+ \varepsilon_nf'(\alpha)+\dfrac{\varepsilon_n^2}{2!}f''(\alpha)+\cdots\right]}{f'(\alpha)+\varepsilon_nf''(\alpha)+\dfrac{\varepsilon_n^2}{2!}f'''(\alpha)}</math></font size=4>
לאחר שכמה אברים במונה מצטמצמים, נקבל שהאיברים המובילים של הטורים במונה ובמכנה נותנים את הביטוי הבא:
:<font size=4><math>\varepsilon_{n+1}=\frac{\dfrac{\varepsilon_n^2}{2!}f''(\alpha)+\cdots}{f'(\alpha)+\cdots}</math></font size=4>
אם השיטה מתכנסת, אז עבור <math>\lim_{n\to\infty}\varepsilon_n=0</math> נקבל בקירוב:
:<font size=4><math>\varepsilon_{n+1}\approx\varepsilon_n^2\overbrace{\frac{f''(\alpha)}{2f'(\alpha)}}^A\quad\Rightarrow\quad\varepsilon_n=A^{2^n-1}\varepsilon_0^{2^n}</math></font size=4>
כלומר, סדר האיטרציה הוא 2.

מצד שני, אם <math>\alpha</math> הוא שורש כפול (שורש מריבוי 2) של <math>f</math> , אז <math>f(\alpha)=f'(\alpha)=0</math> ואז האברים המובילים הם:
:<font size=4><math>\varepsilon_{n+1}=\frac{\dfrac{\varepsilon_n^2}{2!}f''(\alpha)+\cdots}{\varepsilon_nf''(\alpha)+\cdots}</math></font size=4>
ואז הגבול הוא בקירוב:
:<font size=4><math>\varepsilon_{n+1}\approx\frac{\varepsilon_n}{2}</math></font size=4>
כלומר התכנסות לינארית. באופן זה, שיטת ניוטון-רפסון מהווה אינדיקציה לשורש כפול.

==ניוטון-רפסון מתוקן עבור שורש כפול==
ניתן לקבל התכנסות ריבועית באמצעות סדרת הקירובים המתוקנת הבאה:
:<math>x_{n+1}=x_n-\frac{2f(x_n)}{f'(x_n)}</math>

===בדיקת סדר האיטרציה===
כזכור, השגיאה באיטרציה ה-<math>n</math>-ית היא <math>\varepsilon_n=x_n-\alpha</math> . נציב לשיטה ונקבל:
:<math>\varepsilon_{n+1}+\alpha=\varepsilon_n+\alpha-\frac{2f(\varepsilon_n+\alpha)}{f'(\varepsilon_n+\alpha)}=\frac{\varepsilon_n\cdot f'(\varepsilon_n+\alpha)- 2f(\varepsilon_n+\alpha)}{f'(\varepsilon_n+\alpha)}</math>
נפתח מונה ומכנה לטור טיילור:
:<math>\varepsilon_{n+1}=\frac{\varepsilon_n\Big[f'(\alpha)+\varepsilon_nf''(\alpha)+\cdots\Big]-2\left[f(\alpha)+\varepsilon_nf'(\alpha)+\dfrac{\varepsilon_n^2}{2!}f''(\alpha)+\cdots\right]}{f'(\alpha)+\varepsilon_nf''(\alpha)+\cdots}</math>
כעת, שוב, נסתכל על האברים המובילים וניקח גבול כאשר <math>n</math> גדול:
<math>\varepsilon_{n+1}=\frac{\dfrac{\varepsilon_n^3}{3!}f'''(\alpha)-\dfrac{2\varepsilon_n^3}{3!}f'''(\alpha)+\cdots}{\varepsilon_nf''(\alpha)+\cdots}\approx\frac{\varepsilon_n^2f'''(\alpha)}{6f''(\alpha)}</math>

===הכללה===
בהינתן פונקציה f עם שורש &alpha; בריבוי s, ניתן להציג: <math>f(x)=(x-\alpha)^sh(x)</math> כאשר <math>h(\alpha)\ne0</math> . במקרה זה, שיטת ניוטון-רפסון המתוקנת היא מהצורה:
:<math>\ x_{n+1}= x_n- s\frac{f(x_n)}{f'(x_n)}</math>
נראה שבמקרה זה ישנה התכנסות ריבועית:
:<math>\ \epsilon_{n+1}= \frac{\left[ \frac{\epsilon_n^s}{(s-1)!} f^{(s)}(\alpha)+ \frac{\epsilon_n^{s+1}}{s!} f^{(s+1)}(\alpha)+...\right]}{\frac{\epsilon_n^{s-1}}{(s-1)!} f^{(s)}(\alpha)+...}+</math>
:<math>\frac{-s \left[\frac{\epsilon_n^s}{s!} f^{(s)}(\alpha)+ \frac{\epsilon_n^{s+1}}{(s+1)!} f^{(s+1)}(\alpha) +... \right]}{\frac{\epsilon_n^{s-1}}{(s-1)!} f^{(s)}(\alpha)+...}\approx</math>
:<math>\ \approx \frac{f^{(s+1)}(\alpha)}{f^{(s)}(\alpha)} \frac{\epsilon_n^2}{s(s+1)} </math>

===עוד נוסחה מתוקנת של ניוטון-רפסון===
שימו לב כי אם &alpha; הוא שורש כפול של f, אז הוא יהיה שורש בודד של <math>\ h(x)= \tfrac{f(x)}{f'(x)}</math>. לכן אם נפעיל את שיטת ניטון רפסון על h, נקבל התכנסות מסדר 2 לאותו שורש &alpha; ובצורה המפורשת עבור f נקבל:
:<math>\ x_{n+1}= x_n- \frac{f(x_n)f'(x_n)}{[f'(x_n)]^2- f(x_n)f''(x_n)}</math>

==שיטת ניוטון-פורייה==
בשיטה זו יוצרים שתי סדרות איטרטיביות במקביל, כאשר שתיהן מתקבלות משיטת ניוטון-רפסון, אך באחת מהן מציבים את ערכי הסדרה האחרת עבור הנגזרת:
:<math>\ \left\{ \begin{align}
x_{n+1} & = x_n- \frac{f(x_n)}{f'(x_n)} \\
z_{n+1} & = z_n- \frac{f(z_n)}{f'(x_n)} \\
\end{align} \right.</math>
כאשר הניחוש ההתחלתי הוא: <math>\ x_0=b,\ z_0=a</math>.

המרחק בין שתי הסדרות בכל איטרציה קטן ריבועית ונתון על ידי:
:<math>\ x_n-z_n\approx (x_{n-1}-z_{n-1})^2 \frac{f''(\alpha)}{2f'(\alpha)}</math>

==שיטת Steffenson==
שיטת סטפנסון אף היא מודיפיקציה של שיטת ניוטון-רפסון:
:<math>\ x_{n+1}= x_n- \frac{f(x_n)}{z(x_n)}\ , \qquad z(x_n)= \frac{f[x_n+f(x_n)]- f(x_n)}{f(x_n)}</math>
כך שכאשר &alpha; הוא שורש בודד של f, שיטת סטפנסון היא מסדר 2 לפחות.

==ראו גם==
* [[/קוד מקור/]]

==קישורים חיצוניים==
{{מיזמים|ויקיפדיה=שיטת ניוטון-רפסון}}

{{אנליזה נומרית|מוגבל=כן}}

[[קטגוריה:אנליזה נומרית]]