שיטת המיתר

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

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

השיטה

קובץ:Secant method.svg

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

ניקח שני ערכים התחלתיים, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,x_0} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,x_1} , הקרובים יחסית לשורש המבוקש.
נבנה את הישר העובר דרך הנקודות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,(x_0,f(x_0))} ו- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,(x_1,f(x_1))} . משוואת הישר היא: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y = \frac{f(x_1)-f(x_0)}{x_1-x_0} (x-x_1)+f(x_1). } נבחר את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,x_2} , הערך הבא באיטרציה, להיות החיתוך של ישר זה עם ציר ה-x. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_2 = x_1 - f(x_1)\frac{x_1-x_0}{f(x_1)-f(x_0)}} כעת נבנה ישר בין הנקודות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,(x_1,f(x_1))} ו- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,(x_2,f(x_2))} , נחפש את החיתוך שלו בציר ה-x וכן הלאה. התהליך מוגדר בנוסחת הנסיגה הבאה:
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\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})}} ככל שנחשב יותר איטרציות של נוסחת הנסיגה, כך נקבל ערך קרוב יותר לערך השורש האמיתי.

התכנסות

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

השיטה לא תמיד מתכנסת, אך אם הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,f} רציפה וגזירה, הערכים ההתחלתיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,x_0} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,x_1} קרובים מספיק לשורש, והשורש הוא שורש פשוט (כלומר נגזרתה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,f} לא מתאפסת באותה נקודה), אזי ניתן להראות כי השיטה מתכנסת לשורש של הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,f} . סדר ההתכנסות הוא יחס הזהב הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,\varphi} , כאשר $\varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.618$.

קוד דוגמה

להלן קוד בשפת C אשר מיישם את שיטת המיתר. הקוד נכתב בדגש על בהירות ולא על יעילות. הבעיה: למצוא את המספר החיובי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,x} המקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x^3=\cos(x)} . הבעיה מומרת לבעיית מציאת שורש של הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f(x)=x^3-\cos(x)} .

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

1. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \, |x_{n+1} - x_n| < e }
2. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \, n < m }

כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,e} הוא קבוע (השגיאה המקסימלית המותרת), הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,n} הוא מספר האיטרציה ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\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. הערכים המתקבלים הם:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0 = 0 \,\!}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1 = 1 \,\!}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_2 = 0.685073357326045 \,\!}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_3 = 0.841355125665652 \,\!}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_4 = 0.870353470875526 \,\!}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_5 = 0.865358300319342 \,\!}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_6 = 0.865473486654304 \,\!}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_7 = 0.865474033163012 \,\!}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_8 = 0.865474033101614 \,\!}

הגרף הבא מראה את הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,f} באדום וקו המיתר האחרון בכחול. בגרף ניתן לראות שנקודת החיתוך של המיתר עם ציר ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,x} קרובה מאוד לשורש של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,f} .

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

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

שיטת המיתר29895374Q14915286