שיטת החצייה

מספר צעדים של יישום שיטת החצייה במרווח התחלתי. [a₁;b₁]. הנקודה האדומה היא השורש של הפונקציה.

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

תיאור

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

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

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

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

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

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

פס‎א‎דו-קוד

להלן הצגה של שיטה החצייה בקוד של ויזואל בייסיק. המשתנים xL ,xR ו-xM הם b, a ו-c בהתאמה. הערכים ההתחלתיים של xL ו-xR חייבים להיות כך ש-$\!\,f(xL)*f(xR)<0$ (זה בסיס לקבלת השורש). המשתנה epsilon מגדיר כמה מדויקת תהיה התוצאה.

'שיטת החצייה

'התחלת לולאה
Do While (xR - xL) > epsilon
  
  'חישוב ערך אמצעי
  xM = (xR + xL) / 2
  
  'מציאת f(xM)
  If ((f(xL) * f(xM)) > 0) Then
    'התעלם מהחצי שמאלי
    xL = xM
  Else
    'התעלם מהחצי ימני
    xR = xM
  End If
Loop

‏

קוד ב-Java

main :  Bisection.BisectionMethod(1,50, 200,5E-11, 5E-11);
 
public class Bisection {
        private static double function(double x)
        {
                return Math.pow(x,2)-4;
        }
        public static void BisectionMethod(double Xleft,double Xright,
                                         int m, double ep, double delta)
        {
                double fXleft=function(Xleft);
                double fXright=function(Xright);
                double interval=Xright-Xleft;
                double Xmid,fXmid;
                if (fXright*fXleft>0)
                        System.exit(0);
                for(int i=0;i<m;i++)
                {
                        interval=interval/2;
                        Xmid=Xleft+interval;
                        fXmid=function(Xmid);
                        System.out.println("x"+i+" = "+Xmid);
                        if(Math.abs(interval)<ep && Math.abs(fXmid)<delta)
                                System.exit(0);
                        if(fXmid*fXleft>0)
                        {
                                Xleft=Xmid;
                                fXleft=fXmid;
                        }
                        else
                        {
                                Xright=Xmid;
                                fXright=fXmid;
                        }
                }
        }
}

פלט התוכנית

יש לשים לב שככל שנריץ את התוכנית מספר רב יותר של איטרציות כך למעשה נגיע לקירוב טוב יותר. בתוכנית הנ"ל ההרצה מתבצעת 40 פעמים. והקירוב המרבי שקיבלנו הוא: x40 = 1.9999999999886313

x0 = 25.5
x1 = 13.25
x2 = 7.125
x3 = 4.0625
x4 = 2.53125
x5 = 1.765625
x6 = 2.1484375
x7 = 1.95703125
x8 = 2.052734375
x9 = 2.0048828125
x10 = 1.98095703125
x11 = 1.992919921875
x12 = 1.9989013671875
x13 = 2.00189208984375
x14 = 2.000396728515625
x15 = 1.9996490478515625
x16 = 2.0000228881835938
x17 = 1.9998359680175781
x18 = 1.999929428100586
x19 = 1.9999761581420898
x20 = 1.9999995231628418
x21 = 2.0000112056732178
x22 = 2.00000536441803
x23 = 2.000002443790436
x24 = 2.000000983476639
x25 = 2.0000002533197403
x26 = 1.999999888241291
x27 = 2.0000000707805157
x28 = 1.9999999795109034
x29 = 2.0000000251457095
x30 = 2.0000000023283064
x31 = 1.999999990919605
x32 = 1.9999999966239557
x33 = 1.999999999476131
x34 = 2.0000000009022187
x35 = 2.000000000189175
x36 = 1.999999999832653
x37 = 2.000000000010914
x38 = 1.9999999999217835
x39 = 1.9999999999663487
x40 = 1.9999999999886313

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

• שיטת החצייה ב-MathCad.