🎯 Newton's Method

What is Newton's Method?

Newton's Method (also called the Newton-Raphson Method) is a powerful technique for finding approximate solutions to equations of the form $f(x) = 0$.

💡 Key Idea: Start with a guess, use the tangent line to get a better guess, and repeat!

---

The Problem

We want to solve $f(x) = 0$, but:

• Can't solve algebraically
• Need a numerical approximation

Example: Solve $x^5 - 2x - 1 = 0$

No algebraic method exists! Newton's Method to the rescue! 🚀

---

The Method (How It Works)

The Recursive Formula

Start with an initial guess $x_0$, then generate better approximations:

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

Repeat this process until the values converge!

Geometric Interpretation

Step 1: Start at point $(x_n, f(x_n))$ on the curve

Step 2: Draw the tangent line at that point

Step 3: Find where the tangent line crosses the $x$-axis

Step 4: This $x$-intercept becomes $x_{n+1}$ (your next guess)

Step 5: Repeat!

The tangent line equation at $(x_n, f(x_n))$ is: $y - f(x_n) = f'(x_n)(x - x_n)$

Setting $y = 0$ and solving for $x$ gives: $x = x_n - \frac{f(x_n)}{f'(x_n)}$

This is $x_{n+1}$!

---

Step-by-Step Process

Step 1: Make sure $f'(x)$ exists and can be calculated

Step 2: Choose an initial guess $x_0$ (look at a graph if possible)

Step 3: Apply the formula: $x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$

Step 4: Repeat with $x_1$ to get $x_2$: $x_2 = x_1 - \frac{f(x_1)}{f'(x_1)}$

Step 5: Continue until:

• $|x_{n+1} - x_n|$ is very small, OR
• $|f(x_n)|$ is very close to 0, OR
• You've reached a specified number of iterations

---

Example 1: Finding a Square Root

Use Newton's Method to approximate $\sqrt{2}$ (starting with $x_0 = 1$).

Step 1: Set up the equation

We want $\sqrt{2}$, so we need to solve $x^2 = 2$

Rewrite as: $f(x) = x^2 - 2 = 0$

---

Step 2: Find $f'(x)$

$f'(x) = 2x$

---

Step 3: Write Newton's formula

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

Simplify: $x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n} = \frac{2x_n^2 - (x_n^2 - 2)}{2x_n} = \frac{x_n^2 + 2}{2x_n}$

$x_{n+1} = \frac{1}{2}\left(x_n + \frac{2}{x_n}\right)$

---

Step 4: Iterate starting from $x_0 = 1$

$x_0 = 1$

$x_1 = \frac{1}{2}\left(1 + \frac{2}{1}\right) = \frac{1}{2}(3) = 1.5$

$x_2 = \frac{1}{2}\left(1.5 + \frac{2}{1.5}\right) = \frac{1}{2}(1.5 + 1.333...) = \frac{1}{2}(2.833...) \approx 1.4167$

$x_3 = \frac{1}{2}\left(1.4167 + \frac{2}{1.4167}\right) \approx \frac{1}{2}(1.4167 + 1.4118) \approx 1.4142$

$x_4 = \frac{1}{2}\left(1.4142 + \frac{2}{1.4142}\right) \approx 1.41421356...$

---

Check: $\sqrt{2} \approx 1.41421356...$ ✓

After just 4 iterations, we have 8 decimal places of accuracy!

---

Example 2: Solving a Polynomial

Find the root of $f(x) = x^3 - x - 1 = 0$ near $x = 1$.

Step 1: Find $f'(x)$

$f'(x) = 3x^2 - 1$

---

Step 2: Newton's formula

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

---

Step 3: Iterate starting from $x_0 = 1$

$x_0 = 1$

$x_1 = 1 - \frac{1^3 - 1 - 1}{3(1)^2 - 1} = 1 - \frac{-1}{2} = 1 + 0.5 = 1.5$

$x_2 = 1.5 - \frac{(1.5)^3 - 1.5 - 1}{3(1.5)^2 - 1}$

$= 1.5 - \frac{3.375 - 1.5 - 1}{6.75 - 1}$

$= 1.5 - \frac{0.875}{5.75} \approx 1.5 - 0.152 = 1.348$

$x_3 = 1.348 - \frac{(1.348)^3 - 1.348 - 1}{3(1.348)^2 - 1}$

$\approx 1.348 - \frac{0.0447}{4.452} \approx 1.348 - 0.010 = 1.338$

$x_4 \approx 1.3247$

$x_5 \approx 1.32472$ (converged!)

---

Answer: The root is approximately $x \approx 1.32472$

Check: $f(1.32472) = (1.32472)^3 - 1.32472 - 1 \approx 0.00001$ ✓

---

Example 3: Finding Where Functions Intersect

Find where $\cos x = x$ (i.e., solve $\cos x - x = 0$).

Step 1: Set up

$f(x) = \cos x - x$

$f'(x) = -\sin x - 1$

---

Step 2: Choose initial guess

From a graph, the intersection is near $x = 1$

Let $x_0 = 1$

---

Step 3: Newton's formula

$x_{n+1} = x_n - \frac{\cos x_n - x_n}{-\sin x_n - 1}$

---

Step 4: Iterate

$x_0 = 1$

$x_1 = 1 - \frac{\cos(1) - 1}{-\sin(1) - 1}$

$\approx 1 - \frac{0.5403 - 1}{-0.8415 - 1}$

$\approx 1 - \frac{-0.4597}{-1.8415} \approx 1 - 0.2497 = 0.7503$

$x_2 \approx 0.7391$

$x_3 \approx 0.7391$ (converged!)

---

Answer: $\cos x = x$ at $x \approx 0.739$

---

When Newton's Method Works Best

Good Conditions

Newton's Method converges quickly when:

1. $f'(x) \neq 0$ near the root
2. Good initial guess (close to actual root)
3. $f$ is smooth (continuous, differentiable)
4. $f'$ doesn't change sign near the root

Convergence Rate

When it works, Newton's Method has quadratic convergence:

• The number of correct digits roughly doubles each iteration!
• This is why we got 8 decimals in just 4 steps for $\sqrt{2}$

---

When Newton's Method Fails

Failure Case 1: Division by Zero

If $f'(x_n) = 0$, the formula breaks down!

Example: Finding root of $f(x) = x^3$ starting at $x_0 = 0$

$f'(0) = 0$ → Cannot compute $x_1$!

Failure Case 2: Cycles

Sometimes the iterates go in circles and never converge.

Example: $f(x) = x^3 - 2x + 2$ with $x_0 = 0$ creates a 2-cycle

Failure Case 3: Divergence

Poor initial guess can cause iterates to move away from the root.

Example: Finding $\sqrt{2}$ but starting with $x_0 = -1$ can diverge

Failure Case 4: Multiple Roots

At a multiple root (where $f(x) = f'(x) = 0$), convergence is much slower.

Example: $f(x) = (x-1)^2$ has a double root at $x = 1$

---

Tips for Choosing $x_0$

Strategy 1: Use a Graph

Sketch or plot $y = f(x)$ to see where it crosses the $x$-axis

Strategy 2: Try Simple Values

Test $x = 0, 1, -1, 2$, etc. and see which gives $f(x)$ closest to 0

Strategy 3: Use Algebra

Simplify or factor $f(x)$ as much as possible first

Strategy 4: Intermediate Value Theorem

Find $a$ and $b$ where $f(a)$ and $f(b)$ have opposite signs

The root is between $a$ and $b$ → use $x_0 = \frac{a+b}{2}$

---

How Many Iterations?

Stopping Criteria

Stop when ONE of these is true:

1. Relative error: $\left|\frac{x_{n+1} - x_n}{x_n}\right| < \epsilon$ (e.g., $\epsilon = 0.0001$)

2. Absolute error: $|x_{n+1} - x_n| < \epsilon$

3. Function value: $|f(x_n)| < \epsilon$

4. Maximum iterations: Reached some limit (e.g., 50 iterations)

---

Applications of Newton's Method

Application 1: Square Roots

The formula for $\sqrt{a}$: $x_{n+1} = \frac{1}{2}\left(x_n + \frac{a}{x_n}\right)$

This was the ancient Babylonian method!

Application 2: Finding Reciprocals

To compute $\frac{1}{a}$, solve $f(x) = \frac{1}{x} - a = 0$: $x_{n+1} = x_n(2 - ax_n)$

Used in calculators (avoids division!)

Application 3: Optimization

Newton's Method can optimize $f(x)$ by finding where $f'(x) = 0$

Apply the method to $g(x) = f'(x)$!

Application 4: Root-Finding in Engineering

Used in:

• Solving nonlinear circuits
• Finding equilibrium points
• Solving transcendental equations
• Computer graphics and animation

---

⚠️ Common Mistakes

Mistake 1: Wrong Sign

The formula is $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$ (MINUS, not plus!)

Mistake 2: Derivative of the Whole Expression

Calculate $f(x)$ and $f'(x)$ separately, don't mix them up!

Mistake 3: Stopping Too Early

Check that consecutive iterates are actually close before stopping

Mistake 4: Bad Initial Guess

If iterates jump around wildly, try a different $x_0$

Mistake 5: Not Checking the Answer

Always verify: plug your answer into $f(x)$ to see if it's close to 0!

---

Comparison with Other Methods

Bisection Method

• Pros: Always converges (if conditions met), simple
• Cons: Slow (linear convergence)

Newton's Method

• Pros: Very fast (quadratic convergence)
• Cons: Requires derivative, can fail

Secant Method

• Pros: No derivative needed, faster than bisection
• Cons: Slower than Newton's, can still fail

---

Modified Newton's Method

For multiple roots (where $f(x) = f'(x) = 0$), use:

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

where $m$ is the multiplicity of the root.

This restores quadratic convergence!

---

The Big Picture

Historical Significance

• Discovered by Isaac Newton (1669) and Joseph Raphson (1690)
• One of the first iterative numerical methods
• Foundation for modern computational mathematics

Modern Importance

• Built into calculators and computer software
• Basis for more advanced methods
• Essential in scientific computing

---

📝 Practice Strategy

1. Write down $f(x)$ and $f'(x)$ clearly
2. Set up the formula: $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$
3. Choose a reasonable $x_0$ (use a graph or test values)
4. Calculate systematically - make a table with columns for $n$, $x_n$, $f(x_n)$, $f'(x_n)$, $x_{n+1}$
5. Check convergence - are successive values getting closer?
6. Verify your answer by substituting into $f(x)$
7. Keep 6-8 decimal places during calculations to avoid rounding errors