שיטת המיתר

באנליזה נומרית, שיטת המיתר היא שיטה איטרטיבית למציאת שורשים של פונקציה רציפה של משתנה אחד.

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

השיטה

בשיטת המיתר דרושים שני ערכים התחלתיים, $\,x_0$ ו-$\,x_1$, שאמורים להיות קרובים לשורש המבוקש. בהמשך מוגדרת סדרה של נקודות

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

ובמקרים מסוימים אפשר להבטיח שהסדרה מתכנסת לשורש של הפונקציה $\,f$.

תאור גרפי

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

בהינתן שתי נקודות על הישר, $\,a$ ו-$\,b$, אנו בונים את הישר העובר דרך הנקודות $\,(a,f(a))$ ו-$\,(b,f(b))$, כפי שניתן לראות בתמונה משמאל. נשים לב כי הקו הוא מיתר של הגרף של הפונקציה $\,f$. משוואת הישר היא:

$y - f(b) = \frac{f(b)-f(a)}{b-a} (x-b).$

נבחר את $\,c$, הערך הבא באיטרציה, להיות השורש של קו זה, כלומר נקודת החיתוך שלו עם הישר $\,y=0$:

$f(b) + \frac{f(b)-f(a)}{b-a} (c-b) = 0.$

פתרון משוואה זו נותן את היחס האיטרטיבי המגדיר את שיטת המיתר.

התכנסות

דוגמה ויזואלית הממחישה את התכנסות השיטה

השיטה לא תמיד מתכנסת, אך אם הפונקציה $\,f$ רציפה וגזירה, הערכים ההתחלתיים $\,x_0$ ו-$\,x_1$ קרובים מספיק לשורש, והשורש הינו שורש פשוט (כלומר נגזרתה של $\,f$ לא מתאפסת באותה נקודה), אזי ניתן להראות כי השיטה מתכנסת לשורש של הפונקציה $\,f$. סדר ההתכנסות הוא יחס הזהב $\,\varphi$, כאשר $\varphi = \frac{1+\sqrt{5}}{2} \approx 1.618$.

קוד דוגמה

להלן קוד בשפת C אשר מיישם את שיטת המיתר. הקוד נכתב בדגש על בהירות ולא על יעילות. הבעיה: למצוא את המספר החיובי $\,x$ המקיים $\ x^3=\cos(x)$. הבעיה מומרת לבעית מציאת שורש של הפונקציה $\ f(x)=x^3-\cos(x)$.

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

1. $\, |x_{n+1} - x_n| < e$
2. $\, n < m$

כאשר $\,e$ הוא קבוע (השגיאה המקסימלית המותרת), $\,n$ הוא מספר האיטרציה ו-$\,m$ הוא חסם על מספר האיטרציות.

#include <stdio.h>
#include <math.h>
  
double f(double x)
{
    return cos(x) - x*x*x;
}
  
double SecantMethod(double xn_1, double xn, double e, int m)
{
    int n;
    double d;
    for (n = 1; n <= m; n++)
    {
        d = (xn - xn_1) / (f(xn) - f(xn_1)) * f(xn);
        if (fabs(d) < e)
            return xn;
        xn_1 = xn;
        xn = xn - d;
    }
    return xn;
}
  
int main(void)
{
    printf("%0.15f\n", SecantMethod(0, 1, 5E-11, 100));
    return 0;
}

אחרי הרצה של הקוד התוצאה הסופית תהיה 0.865474033101614. הערכים המתקבלים הם:

$x_0 = 0 \,\!$

$x_1 = 1 \,\!$

$x_2 = 0.685073357326045 \,\!$

$x_3 = 0.841355125665652 \,\!$

$x_4 = 0.870353470875526 \,\!$

$x_5 = 0.865358300319342 \,\!$

$x_6 = 0.865473486654304 \,\!$

$x_7 = 0.865474033163012 \,\!$

$x_8 = 0.865474033101614 \,\!$

הגרף הבא מראה את הפונקציה $\,f$ באדום וקו המיתר האחרון בכחול. בגרף ניתן לראות שנקודת החיתוך של המיתר עם ציר ה-$\,x$ קרובה מאוד לשורש של $\,f$.