שיטת החצייה

[student47]

שיטת החצייה

האלגוריתם הוא כזה:
repeat
x3 = (x1+x2)/2
if f(x3)f(x1)<0 then
x2 = x3
else
x1 = x3
until |x1-x2| < 2TOL

2 שאלות:
1. משום מה לא ברור לי האם זה משנה אם אני מחליף את השורה הירוקה בכחולה, ואת הכחולה בירוקה?
2. השורה האחרונה לא ברורה לי. לא ממש ברור לי מה המשמעות כאן של TOL, ושל האי שיוויון עצמו.

אודה על עזרכתם!

 

[student47]

הבהרה בנוגע לשאלה הראשונה שלי

במידה ומניחים ש-f(x1)>0 וגם f(x2)<0, השורה הירוקה חייבת להופיע במקומה והכחולה במקומה?
אם הסימנים הפוכים (כלומר f(x1)>0 וגם f(x2)<0) אז השורה הירוקה והכחולה צריכות להתחלף ביניהן?

כי בסיכום שיש לי, כתבו את האלגוריתם שכתבתי בפוסט הקודם, מבלי לציין מה הסימנים של (f(x1 ושל (f(x2.

 

[אורי769]

תשובה

השורות הכחולה והירוקה חייבות להופיע במקומן. החלפה ביניהן נוגדת את האלגוריתם. כדי להבין זאת צריך אולי לחזור לתיאור המילולי של האלגוריתם:
המטרה למצוא שורש של f בקטע שבין x1 ל-x2 כלשהם. מניחים ש-f רציפה וש-(f(x1 ו-(f(x2 הם בעלי סימן שונה. לפי משפט ערך הביניים יש שורש בקטע. השיטה היא זו - מציבים ב-x3 את אצמע הקטע בין x1 ל-x2. אם (f(x3 הוא שונה בסימן מ-(f(x1 אז ממשיכים את התהליך הזה על הקטע x1,x3. אחרת זה אומר ש-(f(x3 שונה בסימן מ-(f(x2 ובמקרה זה ממשיכים את התהליך על הקטע x3,x2. נשאר רק להגיד מתי עוצרים... עוצרים כאשר קצות הקטע קרובים מספיק לשורש. הערך הקובע את מידת הקרבה הרצויה הוא ה-TOL.