אנליזה נומרית/שיטת חציית האינטרוולים

חיפוש פשוט

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

שיטת חציית האינטרוולים

שיטת חציית האינטרוולים (Interval Halving או bisection) - אשר מהווה מעין "חיפוש פשוט" משופר - מערבת את הגישות הבסיסיות ביותר בהתמודדות עם בעיות נומריות. בשיטה זו מתקדמים על גרף הפונקציה בקפיצות קבועות, וכאשר מגלים הפיכת סימן, מתחילים לחצות את אותו מרווח עד שנגיע לקירוב הרצוי. נניח שאנו מתקדמים בקפיצות קבועות. אם $f(x_{1})\cdot f(x_{2})<0$ אז באותו מרווח הפונקציה חותכת את ציר $x$ , ויש שם לפחות שורש אחד. למעשה יכולים להיות שם מספר אי-זוגי בלבד של שורשים, אחרת לא נקבל שינוי בסימן. לאלגוריתם זה שתי נקודות תורפה:

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

הרעיון הכללי של האלגוריתם הוא כזה:

חציית אינטרוולים כאשר השורש בתחום הימני

• אם פונקציה משנה סימן בין $x_{1},x_{2}$ , אז נבדוק את ערכה באמצע: $x_{0}={\frac {x_{1}+x_{2}}{2}}$ ונמשיך לצמצם את המרווח פי 2 כל שלב, עד שנגיע לקירוב הרצוי.

1. 1. אם $f(x_{0})=0$ אז סיימנו (נדיר שזה יקרה).
   2. אם $f(x_{0})\cdot f(x_{1})<0$ אז נמשיך לחפש בתחום $(x_{1},x_{0})$ .
   3. אם $f(x_{0})\cdot f(x_{1})>0$ אז נמשיך לחפש בתחום $(x_{0},x_{2})$ .

• כאשר הגענו לקירוב הרצוי (אשר נמצא בין $x_{1},x_{2}$ כלשהם), נציג כפלט את אותו x עבורו ערך הפונקציה קרוב יותר לאפס.
• אם הפונקציה לא משנה סימן, נמשיך להתקדם בקפיצות קבועות, עד אשר נגיע לקצה התחום שרצינו לסרוק.

נניח כי התחלנו את החיפוש בתחום $[a,b]$ . אם נגדיר את השגיאה מן השורש בכל איטרציה בתור $\varepsilon _{n}=x_{n}-\alpha$ אז מתקיים $|\varepsilon _{n}|\leq {\frac {b-a}{2^{n}}}$ , כי בכל איטרציה מצמצמים את תחום החיפוש פי 2, כמו בחיפוש בינארי. קל לראות כי $\lim _{n\to \infty }|\varepsilon _{n}|=0$ , כלומר התכנסות השיטה מובטחת.

הערות

1. תנאי העצירה $\varepsilon$ של החיפוש הוא ${\Big |}f(x_{0}){\Big |}<\varepsilon$ .
2. כדאי להדפיס את הקואורדינאטות עליהן עוברת התכנית על-מנת לעקוב כראוי אחר התנהגות הפונקציה והתכנית, ובמקרה של התבדרות או לולאה אינסופית לבצע תיקונים כנדרש.
3. כאשר פותרים בעיות פיזיקליות מוגדרות, ניתן לבחור בהתאם ניחוש התחלתי טוב.
4. לפני שבוחרים את גודל הקפיצות אפשר לשרטט את גרף הפונקציה בתוכנה מתאימה ולראות כיצד היא מתנהגת. לדוגמא, לפונקציה סינוסואידלית בתדירות גבוהה נבחר קפיצות קטנות יותר מאשר לפונקציה מעריכית.
5. אם ידוע שבתחום החיפוש נמצא שורש יחיד, אז מובטחת התכנסות לינארית.
6. בכל מקרה, ניסוי וטעייה יכולים להוביל אותנו אל הפתרון הנכון.

ראו גם

• קוד מקור

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

ערך בוויקיפדיה: חיפוש בינארי

הפרק הקודם: שגיאות

שיטת חציית האינטרוולים

הפרק הבא: מבוא לשיטות איטרטיביות