העשרה: שיטת ניוטון-רפסון (Newton-Raphson)

מוטיבציה

שיטת החצייה (Bisection) עובדת תמיד, אבל מתכנסת לאט — ספרה מדויקת אחת כל ~3.3 איטרציות.

ניוטון-רפסון משתמש בנגזרת כדי להתכנס הרבה יותר מהר.

הרעיון

גיאומטרית

1. ניקח נקודה $x_n$ על הפונקציה
2. נמתח משיק (tangent line) לפונקציה בנקודה
3. נמצא איפה המשיק חוצה את ציר x
4. הנקודה הזו היא $x_{n+1}$ — הקירוב הבא

   f(x)
    │  ╱
    │ ╱ ← הפונקציה
    │╱
────┼─────── ציר x
   ╱│
  ╱ │  ← המשיק
 ╱  │
↑   ↑
x₁  x₀
(קירוב חדש, יותר קרוב לשורש)

נוסחת האיטרציה

$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$

גזירה

משוואת המשיק בנקודה $(x_n, f(x_n))$:

$y - f(x_n) = f'(x_n) \cdot (x - x_n)$

נציב $y = 0$ (חיתוך עם ציר x):

$0 - f(x_n) = f'(x_n) \cdot (x_{n+1} - x_n)$

$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$

מימוש

def newton_raphson(f, f_deriv, x0, eps, max_iter=100):
    """
    f: הפונקציה
    f_deriv: הנגזרת של f
    x0: ניחוש ראשוני
    eps: דיוק רצוי
    max_iter: מספר מקסימלי של איטרציות
    """
    x = x0
    for _ in range(max_iter):
        fx = f(x)
        fpx = f_deriv(x)

        if abs(fpx) < 1e-15:   # נגזרת קרובה ל-0 — בעיה!
            break

        x_new = x - fx / fpx

        if abs(x_new - x) < eps:
            return x_new        # התכנסנו!

        x = x_new

    return x

דוגמה: מציאת $\sqrt{2}$

הגדרה

$f(x) = x^2 - 2, \quad f'(x) = 2x$

נוסחת הניוטון הספציפית

$x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n} = \frac{x_n + 2/x_n}{2}$

קוד

f = lambda x: x**2 - 2
f_deriv = lambda x: 2 * x

root = newton_raphson(f, f_deriv, x0=1.0, eps=1e-10)
print(root)  # 1.4142135623730951

מעקב — התכנסות מדהימה

4 איטרציות לדיוק של 12 ספרות!

התכנסות ריבועית (Quadratic Convergence)

מה זה אומר?

בכל איטרציה, מספר הספרות המדויקות מוכפל.

השוואה ל-Bisection

מתי ניוטון-רפסון נכשל?

1. נגזרת אפס: $f'(x_n) = 0$

# f(x) = x³, f'(x) = 3x²
# בניחוש x = 0: f'(0) = 0 → חילוק באפס!

2. ניחוש ראשוני רע

# f(x) = x³ - 2x + 2
# עם x₀ = 0: האלגוריתם מתבדר (oscillates)
# עם x₀ = -2: מתכנס

3. שורשים מרובים

אם הפונקציה יותר מורכבת, אין ערובה לאיזה שורש נתכנס.

השוואה מלאה: Bisection vs Newton-Raphson

בפועל

לפעמים משלבים: מתחילים עם Bisection (אמין) ועוברים ל-Newton (מהיר).

סיכום נקודות חשובות

• נוסחה: $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$
• רעיון: משיק + חיתוך עם ציר x
• התכנסות ריבועית: ספרות מדויקות מכפילות בכל צעד
• דורש נגזרת — לא תמיד זמינה
• יכול להיכשל: $f'(x) = 0$, ניחוש ראשוני רע
• הרבה יותר מהיר מ-Bisection כשעובד

קישורים נוספים

• חלופה: bisection_method.md - שיטת החצייה (יותר אמינה, יותר איטית)