שיטת החצייה

מספר צעדים של יישום שיטת החצייה במרווח התחלתי.${\displaystyle [a_{1},b_{1}]}$. הנקודה האדומה היא השורש של הפונקציה.

שיטת החצייה היא שיטה איטרטיבית למציאת השורש של הפונקציה, הנעשית באמצעות סדרת קירובים תוך שימוש בחישוב הערך האמצעי

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

תיאור

נניח שאנו רוצים לפתור את המשוואה ${\displaystyle f(x)=0}$, כאשר ${\displaystyle f}$ היא פונקציה רציפה. בהינתן שתי נקודות ${\displaystyle a}$ ו-${\displaystyle b}$, שלערכי הפונקציה בהן יש סימנים הפוכים, ממשפט ערך הביניים נובע שלפונקציה יש לפחות שורש אחד במרווח זה ${\displaystyle [a,b]}$. שיטה זו מחלקת את המרווח בשתיים בכל איטרציה:

${\displaystyle c={\frac {a+b}{2}}}$

אחר כך, ישנן שלוש אפשרויות: באפשרות הראשונה ${\displaystyle f(c)=0}$ ובכך מצאנו את מבוקשנו. שתי האפשרויות האחרות הן של-${\displaystyle f(a)}$ ול-${\displaystyle f(c)}$ יש ערכים הפוכים בסימנם, או של-${\displaystyle f(b)}$ ול-${\displaystyle f(c)}$ יש ערכים הפוכים בסימנם. האלגוריתם ימשיך לאיטרציה הבאה למרווח בין שני הערכים, שבהם הסימנים של הפונקציות שלהם הפוכים.

אם ${\displaystyle f}$ היא פונקציה רציפה במרווח ${\displaystyle [a,b]}$ ו-${\displaystyle f(a)\cdot f(b)<0}$, אזי שיטת החצייה מתכנסת. למעשה, ניתן לחשב שגיאה מוחלטת לשיטה החצייה ברוב המקרים:

${\displaystyle {\frac {b-a}{2^{n}}}}$

לאחר ${\displaystyle n}$ צעדים. במילים אחרות, השגיאה מתחלקת בשתיים בכל איטרציה, לכן השיטה מתכנסת באופן ליניארי (סדר ההתכנסות הוא 1). אבל השיטה מתכנסת באופן ודאי אם ל-${\displaystyle f(a)}$ ול-${\displaystyle f(b)}$ יש ערכים הופכיים. מכאן, שיטת החצייה יעילה פחות משיטת ניוטון-רפסון (מתכנסת לאט יותר), אולם בניגוד לשיטת ניוטון-רפסון, ההתכנסות בה מובטחת.

פסאדו-קוד

להלן הצגה של שיטה החצייה בקוד פייתון. הערכים ההתחלתיים של ${\displaystyle a}$ ו-${\displaystyle b}$ חייבים להיות כך ש-${\displaystyle f(a)\cdot f(b)<0}$ (כמו שנדרש למעלה). המשתנה epsilon מגדיר כמה מדויקת תהיה התוצאה.

# שיטת החצייה
while (b - a) > epsilon:
    
    #חישוב הערך האמצעי
    c = (a + b) / 2.
    
    if f(a)*f(c) > 0:
        #התעלם מהחצי השמאלי
        a = c
    else:
        #התעלם מהחצי הימני
        b = c

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

• שיטת החצייה ב-MathCad.
• שיטת החצייה, באתר MathWorld (באנגלית)