שיטת המיתר
באנליזה נומרית, שיטת המיתר היא שיטה איטרטיבית למציאת שורשים של פונקציה רציפה של משתנה אחד.
שיטה זו דומה לשיטת ניוטון-רפסון למציאת שורשים. בשיטת ניוטון-רפסון יש צורך בנגזרת הפונקציה בנקודה האחרונה. שיטת המיתר מקרבת את הנגזרת על ידי שיפוע המיתר המחבר את שתי הנקודות האחרונות שחושבו, ומכאן שמה. סדר ההתכנסות של השיטה נמוך יותר מזה של שיטת ניוטון-רפסון: בשיטת ניוטון-רפסון הסדר הוא 2, ואילו בשיטת המיתר, הסדר הוא יחס הזהב (1.618 לערך). יתרונה של שיטת המיתר היא בכך שהיא אינה משתמשת בנגזרת: אם הנגזרת אינה ידועה, או שחישובה גוזל משאבי חישוב רבים, שיטת המיתר מתכנסת מהר יותר.
השיטה[עריכת קוד מקור | עריכה]
ניקח שני ערכים התחלתיים, ו-, הקרובים יחסית לשורש המבוקש.
נבנה את הישר העובר דרך הנקודות ו- . משוואת הישר היא:
התכנסות[עריכת קוד מקור | עריכה]
השיטה לא תמיד מתכנסת, אך אם הפונקציה רציפה וגזירה, הערכים ההתחלתיים ו- קרובים מספיק לשורש, והשורש הוא שורש פשוט (כלומר נגזרתה של לא מתאפסת באותה נקודה), אזי ניתן להראות כי השיטה מתכנסת לשורש של הפונקציה . סדר ההתכנסות הוא יחס הזהב , כאשר .
קוד דוגמה[עריכת קוד מקור | עריכה]
להלן קוד בשפת C אשר מיישם את שיטת המיתר. הקוד נכתב בדגש על בהירות ולא על יעילות. הבעיה: למצוא את המספר החיובי המקיים . הבעיה מומרת לבעיית מציאת שורש של הפונקציה .
בקוד הרשום מטה, שיטת המיתר ממשיכה כל עוד מתקיימים שני התנאים הבאים:
כאשר הוא קבוע (השגיאה המקסימלית המותרת), הוא מספר האיטרציה ו- הוא חסם על מספר האיטרציות.
#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. הערכים המתקבלים הם:
הגרף הבא מראה את הפונקציה באדום וקו המיתר האחרון בכחול. בגרף ניתן לראות שנקודת החיתוך של המיתר עם ציר ה- קרובה מאוד לשורש של .
קישורים חיצוניים[עריכת קוד מקור | עריכה]
- שיטת המיתר, באתר MathWorld (באנגלית)