שיטת המיתר

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

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

השיטה

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

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

התכנסות

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

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

קוד דוגמה

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

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

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

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

#include <stdio.h>
#include <math.h>

double f(double x)
 {
     return x*x*x - cos(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. הערכים המתקבלים הם:

${\displaystyle x_{0}=0\,\!}$

${\displaystyle x_{1}=1\,\!}$

${\displaystyle x_{2}=0.685073357326045\,\!}$

${\displaystyle x_{3}=0.841355125665652\,\!}$

${\displaystyle x_{4}=0.870353470875526\,\!}$

${\displaystyle x_{5}=0.865358300319342\,\!}$

${\displaystyle x_{6}=0.865473486654304\,\!}$

${\displaystyle x_{7}=0.865474033163012\,\!}$

${\displaystyle x_{8}=0.865474033101614\,\!}$

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

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

• שיטת המיתר, באתר MathWorld (באנגלית)