שיטת המיתר

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

מתחילים עם שתי ניחושיו התחלתיים x0 ו-x1 קרובים לשורש. בונים את הישר שעובר דרך הנקודות (x0,f(x0)) ו-(x1,f(x1)) ומחפשים את נקודת החיתוך של הישר עם ציר ה-x. הערך הזה הוא הניחוש הבא. בנוסחה פשוטה: x2 = x1 - f(x1)*(x1-x0)/(f(x1)-f(x0)). לאחר מכן חוזרים על הפעולה בין x1 ו-x2, וכן הלאה, בעזרת הנוסחת הנסיגה הכללית x_n = x_{n-1} - f(x_{n-1})*(x_{n-1}-x_{n-2})/(f(x_{n-1})-f(x_{n-2})). כל איטרציה קרובה את הערך לשורש, אם התהליך מתכנס.

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

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

התוצאה הסופית שהושגה בקוד היא בערך 0.865474033101614. סדרת הניחושים התחלתית שהוצגה כללה למשל: x0 = 0, x1 = 1, אחר כך x2 ≈ 0.68507, x3 ≈ 0.84136, ובסופו של דבר x8 ≈ 0.865474033101614. הגרף מדגים את פונקציית f (באדום) ואת המיתר האחרון (בכחול); חיתוך המיתר עם ציר ה-x קרוב לשורש של f.

שיטת המיתר עוזרת למצוא מספר שבו פונקציה שווה לאפס. פונקציה היא כלל שמקבל מספר ומחזיר מספר. "שורש" הוא המספר שגורם לפונקציה להיות אפס.

עובדים כך: מתחילים עם שני ניחושים של המספר. בגרף לוקחים את שתי הנקודות של הפונקציה באותם ניחושים. מציירים קו ישר בין שתי הנקודות.

מוצאים איפה הקו הזה חותך את ציר ה-x. זה הניחוש הבא. חוזרים על זה שוב ושוב עד שהניחוש לא משתנה יותר.

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

בדוגמה מצאו מספר שמקיים x בחזקת שלוש שווה לקוסינוס של x. זה הומר למציאת שורש של פונקציה פשוטה. הקוד מצא בסוף את המספר בערך 0.86547. התחילו ב-x0 = 0 ו-x1 = 1, והניחושים התקרבו לאט עד 0.86547.