# שיטת החצייה (Bisection) למציאת שורשים - סיכום לבחינה --- ## מוטיבציה ### הבעיה רוצים למצוא **שורש** של פונקציה — ערך $x$ כך ש-$f(x) = 0$. **דוגמה:** מציאת $\sqrt{2}$ = מציאת $x$ כך ש-$x^2 - 2 = 0$. ### למה לא לפתור אלגברית? הרבה משוואות **אין להן פתרון סגור**. למשל: $x = \cos(x)$. --- ## ההבדל מחיפוש בינארי על מערך > **זה לא אותו דבר!** | | חיפוש בינארי (מערך) | שיטת החצייה (פונקציה) | |---|---|---| | **קלט** | מערך ממוין | פונקציה רציפה | | **מחפשים** | ערך מסוים במערך | x כך ש-f(x) = 0 | | **איך יודעים לאיזה חצי** | משווים לערך היעד | בודקים **החלפת סימן** | | **תנאי עצירה** | מצאנו או מיצינו | הקטע < ε | | **סיבוכיות** | $O(\log n)$ | $O(\log(\frac{b-a}{\varepsilon}))$ | | **תוצאה** | אינדקס מדויק | **קירוב** (עד דיוק ε) | --- ## העקרון: משפט ערך הביניים (IVT) ### הנחה $f$ **רציפה** בקטע $[a, b]$, ו-$f(a)$ ו-$f(b)$ הם **בסימנים מנוגדים**. ### מסקנה קיים $c \in (a, b)$ כך ש-$f(c) = 0$. ### אינטואיציה אם פונקציה רציפה מתחילה **מתחת** לציר x ומגיעה **מעל** (או להפך), היא **חייבת לחצות** את הציר. ``` f(b) > 0 ● / / ← חייב לחצות את ציר x! ───/────────── ציר x / ● f(a) < 0 ``` ### הקריטריון $$f(a) \cdot f(b) < 0 \iff \text{יש החלפת סימן} \iff \text{יש שורש בקטע}$$ --- ## האלגוריתם ```python def bisection(f, a, b, eps): """ מוצא שורש של f בקטע [a, b] בדיוק eps. דרישה: f(a) * f(b) < 0 (החלפת סימן) """ assert f(a) * f(b) < 0, "חייבת החלפת סימן!" while b - a > eps: mid = (a + b) / 2 if f(mid) == 0: return mid # מצאנו שורש מדויק (נדיר) elif f(a) * f(mid) < 0: b = mid # השורש בחצי השמאלי else: a = mid # השורש בחצי הימני return (a + b) / 2 # מחזירים את מרכז הקטע ``` ### הסבר שורה-שורה | שורה | מה קורה | |------|---------| | `f(a) * f(b) < 0` | מוודאים שיש שורש בקטע | | `b - a > eps` | ממשיכים כל עוד הקטע גדול מהדיוק | | `mid = (a + b) / 2` | **חילוק עשרוני** (לא שלם!) | | `f(a) * f(mid) < 0` | בודקים אם השורש בחצי השמאלי | | `b = mid` | מצמצמים ל-$[a, \text{mid}]$ | | `a = mid` | מצמצמים ל-$[\text{mid}, b]$ | | `(a + b) / 2` | הקירוב הטוב ביותר — מרכז הקטע | --- ## דוגמה: מציאת $\sqrt{2}$ ```python f = lambda x: x**2 - 2 # f(√2) = 0 root = bisection(f, 1, 2, 1e-10) print(root) # 1.4142135623... ``` ### מעקב (Trace) | איטרציה | a | b | mid | f(mid) | f(a)·f(mid) | פעולה | |---------|---|---|-----|--------|-------------|-------| | 1 | 1.0 | 2.0 | 1.5 | 0.25 | < 0 | b = 1.5 | | 2 | 1.0 | 1.5 | 1.25 | -0.4375 | > 0 | a = 1.25 | | 3 | 1.25 | 1.5 | 1.375 | -0.109 | > 0 | a = 1.375 | | 4 | 1.375 | 1.5 | 1.4375 | 0.066 | < 0 | b = 1.4375 | | ... | ... | ... | ... | ... | ... | ... | הקטע מתכווץ: $1.0 \to 0.5 \to 0.25 \to 0.125 \to \ldots$ --- ## סיבוכיות ### ניתוח בכל איטרציה, הקטע **מתחצה**: $$\text{אחרי } k \text{ איטרציות: אורך הקטע} = \frac{b - a}{2^k}$$ ### תנאי עצירה $$\frac{b - a}{2^k} < \varepsilon \implies k > \log_2\left(\frac{b-a}{\varepsilon}\right)$$ ### סיבוכיות $$O\left(\log\left(\frac{b-a}{\varepsilon}\right)\right)$$ ### דוגמה מספרית - קטע התחלתי: $[1, 2]$, דיוק $\varepsilon = 10^{-10}$ - מספר איטרציות: $\log_2\left(\frac{1}{10^{-10}}\right) = \log_2(10^{10}) \approx 33$ - רק 33 קריאות לפונקציה! --- ## שגיאת משתנה vs שגיאת פונקציה ### שני סוגי שגיאה **שגיאת משתנה** (variable error): $|x_{\text{approx}} - x_{\text{real}}|$ - כמה רחוק הקירוב שלנו מהשורש האמיתי - **זה מה שאנחנו שולטים בו** (דרך ε) **שגיאת פונקציה** (function error): $|f(x_{\text{approx}})|$ - כמה קרוב ערך הפונקציה לאפס ### הם **לא** אותו דבר! ```python # פונקציה תלולה: שגיאה קטנה ב-x → שגיאה גדולה ב-f f = lambda x: 1000 * x # f'(x) = 1000 # |x - root| = 0.001 → |f(x)| = 1.0 (!) # פונקציה שטוחה: שגיאה גדולה ב-x → שגיאה קטנה ב-f g = lambda x: 0.001 * x # g'(x) = 0.001 # |x - root| = 100 → |g(x)| = 0.1 ``` ### מסקנה > **אל תשתמשו ב-$|f(\text{mid})| < \varepsilon$ כתנאי עצירה!** > > תנאי נכון: **$b - a < \varepsilon$** (שגיאת משתנה) --- ## דרישות מהפונקציה 1. **רציפות** — הפונקציה חייבת להיות רציפה (בלי קפיצות) 2. **החלפת סימן** — $f(a) \cdot f(b) < 0$ (אחרת אין ערובה לשורש) 3. **מונוטוניות לא נדרשת!** — בניגוד לחיפוש בינארי ### מתי לא עובד? ```python # שורש כפול - הפונקציה נוגעת בציר x בלי לחצות f = lambda x: x**2 # שורש ב-0, אבל f(x) ≥ 0 תמיד! # אין החלפת סימן → bisection לא מוצא ``` --- ## טעויות נפוצות ### טעות 1: בלבול עם חיפוש בינארי על מערך ```python # שגוי - שימוש בחילוק שלם mid = (a + b) // 2 # לא! זה לא אינדקסים! # נכון - חילוק עשרוני mid = (a + b) / 2 ``` ### טעות 2: תנאי שגוי — f(a) < f(mid) במקום f(a)*f(mid) ```python # שגוי - משווים ערכים, לא סימנים if f(a) < f(mid): b = mid # נכון - בודקים החלפת סימן if f(a) * f(mid) < 0: b = mid ``` ### טעות 3: תנאי עצירה לפי ערך הפונקציה ```python # מסוכן - לא שולט בדיוק של x while abs(f(mid)) > eps: # יכול לתת x רחוק מהשורש! # נכון - שולט בדיוק של x while b - a > eps: ``` ### טעות 4: שכחה שצריך החלפת סימן ```python # f(x) = x² + 1 → תמיד חיובי! bisection(lambda x: x**2 + 1, -10, 10, 0.01) # לא ימצא כלום — אין שורש ממשי, אין החלפת סימן ``` ### טעות 5: Bisection מוצא רק שורש **אחד** ```python # f(x) = x³ - x → שורשים ב-{-1, 0, 1} bisection(f, -2, 2, 0.01) # ימצא רק את 0 (או אחד אחר, תלוי בקטע) ``` --- ## שאלות בחינה טיפוסיות ### שאלה 1: כמה איטרציות? **שאלה:** קטע $[0, 100]$, דיוק $\varepsilon = 0.01$. כמה איטרציות? **פתרון:** $$k = \lceil \log_2(100 / 0.01) \rceil = \lceil \log_2(10000) \rceil = \lceil 13.29 \rceil = 14$$ --- ### שאלה 2: מעקב **שאלה:** $f(x) = x^3 - 2$, קטע $[1, 2]$. בצע 3 איטרציות. | איטרציה | a | b | mid | $f(\text{mid})$ | פעולה | |---------|---|---|-----|--------|-------| | 1 | 1 | 2 | 1.5 | $1.375$ (>0) | $f(1) \cdot f(1.5) < 0$ → b=1.5 | | 2 | 1 | 1.5 | 1.25 | $-0.047$ (<0) | $f(1) \cdot f(1.25) > 0$ → a=1.25 | | 3 | 1.25 | 1.5 | 1.375 | $0.600$ (>0) | $f(1.25) \cdot f(1.375) < 0$ → b=1.375 | קירוב: $(1.25 + 1.375)/2 = 1.3125$ (השורש: $\sqrt[3]{2} \approx 1.2599$) --- ### שאלה 3: שגיאה **שאלה:** אחרי 20 איטרציות על קטע $[0, 1]$, מה השגיאה המקסימלית? **פתרון:** $\frac{1}{2^{20}} = \frac{1}{1{,}048{,}576} \approx 9.5 \times 10^{-7}$ --- ## סיכום נקודות חשובות - [ ] Bisection = **מציאת שורשים** של פונקציות רציפות (לא חיפוש במערך!) - [ ] דרישה: $f(a) \cdot f(b) < 0$ (החלפת סימן) - [ ] חילוק **עשרוני**: `mid = (a + b) / 2` (לא `//`!) - [ ] תנאי עצירה: `b - a > eps` (**שגיאת משתנה**, לא שגיאת פונקציה) - [ ] סיבוכיות: $O(\log(\frac{b-a}{\varepsilon}))$ - [ ] שגיאת משתנה ≠ שגיאת פונקציה - [ ] לא צריך מונוטוניות, רק רציפות + החלפת סימן --- ## קישורים נוספים - **השוואה:** [search_binary.md](search_binary.md) - חיפוש בינארי על מערכים - **העשרה:** [newton_raphson.md](newton_raphson.md) - שיטה מהירה יותר למציאת שורשים