שיטת החצייה

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

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

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

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

[עריכה] תיאור

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

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

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

אם $f$ הינה פונקציה רציפה במרווח [a,b] ו- $\!\,f(a)*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

[עריכה] קישורים נוספים

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

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