שיטת החצייה

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

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

באנליזה נומרית, שיטת החצייה (באנגלית: 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)$ יש ערכים הופכיים. מכאן, שיטת החצייה יעילה פחות משיטת ניוטון-רפסון (מתכנסת לאט יותר), אולם בניגוד לשיטת ניוטון-רפסון, ההתכנסות בה מובטחת.

פסאדו-קוד

להלן הצגה של שיטה החצייה בקוד פייתון. הערכים ההתחלתיים של $a$ ו-$b$ חייבים להיות כך ש-$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

קוד ב-Java

על מנת שהתוכנית תקבל כקלט כלל העתקה של פולינום $\deg p(x)=n$ ניתן להגדיר לשם הנוחות מערך חד ממדי $factor[]$ בגודל $n-1$ ומשתנה $var$ כך שיתקיים $\sum _{i=0}^{n}a_{i}x^{i}=\sum _{i=0}^{n-1}f_{i}x^{i+1}+var$ וכך נגדיר את הפולינום $p(x)$ ואת הפעולה $f$

public class Polynom {

    private double[] factor; 
    private double var;

    public Polynom(double[] factor, double var) {  //Constructor

        this.factor = factor;
        this.var = var;
    }
    
    public double f(double x) {  // f(x) = Polynom(x)  

        double f = var;

        for (int i = 0; i < factor.length; i++) {

            f = f + factor[i] * Math.pow(x, i + 1);
        }

        return f ;
}

public class Bisection {

    public static void BisectionMethod(Polynom p ,double Xleft,double Xright,
                                       int m, double ep, double delta)
    {
        double fXleft= p.f(Xleft);
        double fXright=p.f(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=p.f(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;
            }
        }
    }
}

פלט התוכנית

נריץ את התוכנית עבור הפולינום $p(x)=x^{2}-4$. יש לשים לב שככל שנריץ את התוכנית מספר רב יותר של איטרציות כך למעשה נגיע לקירוב טוב יותר. בתוכנית הנ"ל ההרצה מתבצעת 40 פעמים. והקירוב המרבי שקיבלנו הוא:$x_{40}=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.
• שיטת החצייה, באתר MathWorld (באנגלית)   

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

28226206שיטת החצייה