שיטת המיתר

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

שיטה זו דומה לשיטת ניוטון-רפסון למציאת שורשים. בשיטת ניוטון-רפסון יש צורך בנגזרת הפונקציה בנקודה האחרונה. שיטת המיתר מקרבת את הנגזרת על-ידי שיפוע המיתר המחבר את שתי הנקודות האחרונות שחושבו, ומכאן שמה. סדר ההתכנסות של השיטה נמוך יותר מזה של שיטת ניוטון-רפסון: בשיטת ניוטון-רפסון הסדר הוא 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$ . סדר ההתכנסות הוא $\,\varphi$ , כאשר $\varphi = \frac{1+\sqrt{5}}{2} \approx 1.618$

ניתן לראות את התכנסות השיטה בעזרת הדוגמה הויזואלית הבאה:

[עריכה] קוד דוגמה

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

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

$\, |x_{n+1} - x_n| < e$
$\, 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$ .

חשבון אינפיניטסימלי
מושגי יסוד:	חשבון אינפיניטסימלי \| סדרה \| גבול \| סדרת קושי \| טור \| אינפיניטסימל \| שדה המספרים הממשיים \| ערך מוחלט \| אי-שוויון המשולש \| אי-שוויון קושי-שוורץ
פונקציות:	פונקציה \| גרף פונקציה \| פונקציה לינארית \| פונקציה מונוטונית \| נקודת קיצון \| פונקציה קעורה \| פונקציה קמורה \| פונקציה רציפה \| רציפות במידה שווה \| נקודת אי רציפות \| נגזרת \| טור טיילור \| סדרת פונקציות \| התכנסות במידה שווה
משפטים:	משפט בולצאנו-ויירשטראס \| משפטי ויירשטראס \| משפט קנטור \| משפט ערך הביניים \|משפט פרמה \| משפט רול \| משפט הערך הממוצע של לגראנז' \| משפט הערך הממוצע של קושי \| משפט דארבו \| כלל השרשרת \| כלל הסנדוויץ' \| כלל לופיטל \| משפט שטולץ \| אריתמטיקה של גבולות
האינטגרל:	אינטגרל \| המשפט היסודי של החשבון הדיפרנציאלי והאינטגרלי \| אינטגרציה בחלקים \| שיטות אינטגרציה
אנליזה מתקדמת:	פונקציה מרוכבת \| אנליזה וקטורית \| שיטת ניוטון-רפסון \| משוואה דיפרנציאלית \| טופולוגיה \| תורת המידה
אנליזה מתמטית - אנליזה וקטורית - טופולוגיה - אנליזה מרוכבת - אנליזה פונקציונלית - תורת המידה