Numerical Methods: Roots of Equations – Iteration, Bisection, Newton-Raphson

---

## What is a Root of an Equation?
A **root** of an equation \( f(x) = 0 \) is a value of \( x \) that satisfies the equation. For example, in \( x^2 - 4 = 0 \), \( x = 2 \) and \( x = -2 \) are roots.

**Problem:** Some equations (like \( x^3 - 2x + 1 = 0 \)) cannot be solved exactly using algebra. For these, we use **numerical methods** to approximate roots.

---

## Why Use Numerical Methods?
- Exact solutions are not always possible.
- These methods give approximate roots with a desired accuracy.
- Useful in engineering, physics, and economics.

---

## Method 1: Iteration Method
The **Iteration Method** (also called the **Fixed-Point Method**) converts \( f(x) = 0 \) into an iterative formula \( x = g(x) \) and repeatedly applies it to approximate the root.

```figure
{"type":"graph","fns":[{"expr":"x^3 - 2*x + 1","label":"f(x) = x³ − 2x + 1"},{"expr":"cbrt(2*x - 1)","label":"g(x) = ∛(2x − 1)"},{"expr":"(x^3 + 1)/2","label":"g(x) = (x³ + 1)/2"},{"expr":"(2*x + 1)/(x^2)","label":"g(x) = (2x + 1)/x²"}],"x":[-2,2],"points":[{"x":-1.59,"y":0,"label":"Root (approx)"},{"x":0.618,"y":0,"label":"Root (approx)"}],"caption":"Iteration functions g(x) and the original function f(x) for x³ − 2x + 1 = 0"}

Steps:

1. Rewrite ( f(x) = 0 ) as ( x = g(x) ).
2. Choose an initial guess ( x_0 ).
3. Apply the formula repeatedly: ( x_{n+1} = g(x_n) ).
4. Stop when the difference between successive approximations is small enough.

Example:

Find the root of ( x^3 - 2x + 1 = 0 ) near ( x = 1 ) using Iteration.

Step 1: Rewrite the equation

We can write: [ x^3 - 2x + 1 = 0 ] [ x^3 = 2x - 1 ] [ x = \sqrt[3]{2x - 1} ] So, ( g(x) = \sqrt[3]{2x - 1} ).

Step 2: Choose ( x_0 = 1 )

Compute successive approximations: [ x_1 = \sqrt[3]{2(1) - 1} = \sqrt[3]{1} = 1 ] [ x_2 = \sqrt[3]{2(1) - 1} = 1 ] This does not converge! Let’s try another form.

Alternative Form:

Rewrite as: [ x = \frac{x^3 + 1}{2} ] So, ( g(x) = \frac{x^3 + 1}{2} ).

Now, apply iteration: [ x_0 = 1 ] [ x_1 = \frac{1^3 + 1}{2} = 1 ] [ x_2 = \frac{1^3 + 1}{2} = 1 ] Still not working! Let’s try another approach.

Correct Form:

Rewrite as: [ x = \frac{2x + 1}{x^2} ] So, ( g(x) = \frac{2x + 1}{x^2} ).

Now, apply iteration: [ x_0 = 1 ] [ x_1 = \frac{2(1) + 1}{1^2} = 3 ] [ x_2 = \frac{2(3) + 1}{3^2} = \frac{7}{9} \approx 0.777 ] [ x_3 = \frac{2(0.777) + 1}{(0.777)^2} \approx 3.5 ] This oscillates and does not converge!

Conclusion: Not all forms of ( g(x) ) work. We need a convergent form.

Working Form:

Rewrite as: [ x = \frac{1}{2} (x^3 + 1) ] But this also fails. Let’s try: [ x = \sqrt{2x - 1} ] But this is not valid for all ( x ).

Solution: Use Newton-Raphson or Bisection if iteration fails.

When Does Iteration Work?

The method converges if:

1. The function ( g(x) ) is continuous.
2. ( |g'(x)| < 1 ) near the root.

Method 2: Bisection Method

The Bisection Method repeatedly halves an interval ([a, b]) where ( f(a) ) and ( f(b) ) have opposite signs (Intermediate Value Theorem guarantees a root).

Steps:

1. Find ( a ) and ( b ) such that ( f(a) \cdot f(b) < 0 ).
2. Compute midpoint ( c = \frac{a + b}{2} ).
3. Check ( f(c) ):
   • If ( f(c) = 0 ), ( c ) is the root.
   • If ( f(c) \cdot f(a) < 0 ), the root is in ([a, c]). Set ( b = c ).
   • Else, the root is in ([c, b]). Set ( a = c ).
4. Repeat until the interval is small enough.

Example:

Find the root of ( f(x) = x^3 - 2x + 1 = 0 ) in ([0, 2]) with error ( < 0.01 ).

Step 1: Check ( f(0) ) and ( f(2) )

[ f(0) = 0 - 0 + 1 = 1 ] [ f(2) = 8 - 4 + 1 = 5 ] Both are positive! No root here. Try ([0, -2]): [ f(-2) = -8 + 4 + 1 = -3 ] Now, ( f(0) \cdot f(-2) = 1 \cdot (-3) = -3 < 0 ). Root is in ([-2, 0]).

Step 2: Apply Bisection

The interval is now ([-1.625, -1.5625]), and the midpoint is approximately (-1.59375). The error is ( \frac{b - a}{2} = 0.03125 ), which is less than (0.01). So, the approximate root is (-1.59).

Advantages of Bisection:

• Always converges if ( f(a) \cdot f(b) < 0 ).
• Easy to understand and implement.

Disadvantages:

• Slow convergence (error halves each time).
• Requires many iterations for high accuracy.

Method 3: Newton-Raphson Method

The Newton-Raphson Method uses the tangent line to approximate the root. It is faster than Bisection but requires the derivative ( f'(x) ).

Steps:

1. Start with an initial guess ( x_0 ).
2. Compute ( x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} ).
3. Repeat until the change is small enough.

Example:

Find the root of ( f(x) = x^3 - 2x + 1 = 0 ) near ( x = 0 ) using Newton-Raphson.

Step 1: Compute ( f'(x) )

[ f'(x) = 3x^2 - 2 ]

Step 2: Apply Newton-Raphson

Let ( x_0 = 0 ): [ x_1 = 0 - \frac{0 - 0 + 1}{0 - 2} = 0.5 ] [ x_2 = 0.5 - \frac{(0.5)^3 - 2(0.5) + 1}{3(0.5)^2 - 2} = 0.5 - \frac{0.125 - 1 + 1}{0.75 - 2} = 0.5 - \frac{0.125}{-1.25} = 0.5 + 0.1 = 0.6 ] [ x_3 = 0.6 - \frac{(0.6)^3 - 2(0.6) + 1}{3(0.6)^2 - 2} = 0.6 - \frac{0.216 - 1.2 + 1}{1.08 - 2} = 0.6 - \frac{0.016}{-0.92} \approx 0.6 + 0.017 = 0.617 ] [ x_4 \approx 0.618 ]

The root converges to approximately ( 0.618 ).

Advantages of Newton-Raphson:

• Faster convergence (error squares each time).
• Fewer iterations needed for high accuracy.

Disadvantages:

• Requires the derivative ( f'(x) ).
• May diverge if the initial guess is poor.

Comparison of Methods

Error Analysis

The error in numerical methods is the difference between the approximate root and the true root. For:

• Bisection: Error ( \approx \frac{b - a}{2^n} ).
• Newton-Raphson: Error ( \approx \frac{f''(x)}{2f'(x)} (x_n - x)^2 ).

NEB-Style Questions

Short Answer:

1. What is the condition for the Bisection Method to guarantee a root in ([a, b])?
2. Why might the Iteration Method fail to converge?

Long Answer:

3. Use the Bisection Method to find the root of ( f(x) = x^2 - 3 ) in ([1, 2]) with error ( < 0.05 ). Show all iterations.
4. Apply the Newton-Raphson Method to find the root of ( f(x) = x^3 - x - 1 = 0 ) near ( x = 1.5 ). Perform two iterations.

Exam Tip

• Bisection is the safest method for exams—always converges if ( f(a) \cdot f(b) < 0 ).
• Newton-Raphson is faster but requires careful choice of initial guess.
• Iteration is tricky—only use if the form ( g(x) ) is guaranteed to converge.
• Always show all steps and justify your interval choices in Bisection.
• For Newton-Raphson, clearly write the formula and compute derivatives carefully.

flowchart TD
    A["Start"] --> B["Choose Method"]
    B --> C["Iteration"]
    B --> D["Bisection"]
    B --> E["Newton-Raphson"]
    C --> F["Rewrite as x = g(x)"]
    D --> G["Find [a, b] with f(a)f(b) < 0"]
    E --> H["Compute f'(x)"]
    F --> I["Check convergence"]
    G --> J["Bisect and check sign"]
    H --> K["Apply xₙ₊₁ = xₙ − f(xₙ)/f'(xₙ)"]
    I --> L["If converges, stop"]
    J --> L
    K --> L
    L --> M["Approximate Root"]
    M --> N["End"]