אנליזה נומרית/שיטות איטרטיביות עם מיתרים

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

שיטת המיתר הקבוע

בשיטה זו מתחילים עם שני ניחושים x₁, x₂ קרובים, והשיפוע של כל מיתר נתון על ידי:

$\frac{f(x_1)-f(x_0)}{x_1-x_0}=\frac{f(x_n)-0}{x_n-x_{n+1}}\Rightarrow x_{n+1}=x_n-\frac{f(x_n)(x_1-x_0)}{f(x_1)-f(x_0)}$

שיטת המיתר הקבוע

נשים לב כי כאשר $|f(x_1)-f(x_0)|<<1$ השיטה קורסת.

שיטת המיתר המשתנה (secant)

גם כאן מתחילים עם שני ניחושים x₁, x₂, והשיפוע של כל מיתר נתון על ידי:

$\frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}=\frac{f(x_n)-0}{x_n-x_{n+1}}\Rightarrow x_{n+1}=x_n-f(x_n)\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}$

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

שיטת המיתר המשתנה

נשים לב כי כאשר $|f(x_n)-f(x_{n-1})|<<1$ השיטה קורסת.

קוריוז מעניין הוא שסדר האיטרציה הזו הוא בדיוק חיתוך הזהב: $\frac{1+\sqrt{5}}{2}\approx 1.618$.

מציאת הביטוי לשגיאה

נשתמש בקשר $x_n={ϵ}_n+\alpha$:

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

$\Rightarrow {ϵ}_{n+1}=\frac{f^{″}(\alpha ){ϵ}_n{ϵ}_{n-1}}{2[f^{\prime }(\alpha )+\frac{1}{2}{f}^{″}(\alpha )({ϵ}_n+{ϵ}_{n-1})]}\approx {ϵ}_n{ϵ}_{n-1}\frac{f^{″}(\alpha )}{2f^{\prime }(\alpha )}$

או בקיצור: ${ϵ}_n=A{ϵ}_{n-1}{ϵ}_{n-2}$.

מציאת סדר השיטה

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

${ϵ}_{n+1}=B{ϵ}_n^s\Rightarrow \{\begin{array}{cc}{ϵ}_{n+1}& =B{ϵ}_n^s\\ {ϵ}_n& =B{ϵ}_{n-1}^s\end{array}$

נשתמש בקשר אשר מצאנו מקודם:

$\begin{array}{cc}{ϵ}_{n+1}& =A{ϵ}_n{ϵ}_{n-1}=A(B{ϵ}_{n-1}^s){ϵ}_{n-1}=AB{ϵ}_{n-1}^{s+1}\\ {ϵ}_{n+1}& =B{ϵ}_n^s=B(B{ϵ}_{n-1}^s{)}^s=B^{s+1}{ϵ}_{n-1}^{s^2}\end{array}$

נבצע השוואת מקדמים:

$AB{ϵ}_{n-1}^{s+1}=B^{s+1}{ϵ}_{n-1}^{s^2}\Rightarrow \{\begin{array}{cc}A& =B^s\\ {ϵ}_{n-1}^{s+1}& ={ϵ}_{n-1}^{s^2}\end{array}\Rightarrow s^2=s+1,\to s=\varphi$

כאשר $\varphi =\frac{1+\sqrt{5}}{2}\approx 1.618$ הוא חיתוך הזהב (התעלמנו מהשורש השלילי של המשוואה הריבועית כי אינו יכול להיות סדר ההתכנסות). בסופו של דבר נקבל:

$\{\begin{array}{c}s=\varphi \approx 1.618\\ A=B^{\varphi }\end{array}$

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

קישורים חיצוניים

• מצגות וגליונות באתר אוניברסיטת USF.
• אתר אוניברסיטת CSU
• אתר MathWorld

שיטת Regula Falsi

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

שיטת False Position

גם כאן מתחילים עם שני ניחושים x₁, x₀ קרובים, אך הפעם הם נמצאים משני צידי השורש, כך שמתקיים: $f(x_0)\cdot f(x_1)<0$. נניח שהמיתר חותך את ציר x בנקודה c. נשתמש בשיטת המיתר המשתנה:

$c=x_1-\frac{f(x_1)(x_1-x_0)}{f(x_1)-f(x_0)}$

ההמשך דומה לשיטת חציית האינטרוולים:

1. אם $f(x_0)f(c)>0$ אז ממשיכים בתחום (c,x₁), כלומר בתוכנית המחשב נבצע פעולת השמה: x₀:=c.
2. אם $f(x_0)f(c)<0$ אז ממשיכים בתחום (x₀,c), כלומר בתוכנית המחשב נבצע פעולת השמה: x₁:=c.
3. אם $f(x_0)f(c)=0$ אז c=α וסיימנו.