Roots of equation

Bisection Method

The simplest root finding algorithm is the bisection method. The algorithm applies to any continuous function f(x) on an interval [a,b] where the value of the function f(x) changes sign from a to b. The idea is simple: divide the interval in two, a solution must exist within one subinterval, select the subinterval where the sign of f(x) changes and repeat.

The bisection method procedure is:

1. Choose a starting interval [a₀,b₀] such that f(a₀)f(b₀)<0.
2. Compute f(m₀) where m₀=(a₀+b₀)/2 is the midpoint.
3. Determine the next subinterval [a₁,b₁]:
   • If f(a₀)f(m₀)<0, then let [a₁,b₁] be the next interval with a₁=a₀ and b₁=m₀.
   • If f(b₀)f(m₀)<0, then let [a₁,b₁] be the next interval with a₁=m₀ and b₁=b₀.
4. Repeat (2) and (3) until the interval [a_N,b_N] reaches some predetermined length.
5. Return the midpoint value m_N=(a_N+b_N)/2.

A solution of the equation f(x)=0 in the interval [a,b] is guaranteed by the Intermediate Value Theorem provided f(x) is continuous on [a,b] and f(a)f(b)<0. In other words, the function changes sign over the interval and therefore must equal 0 at some point in the interval [a,b].

Newton raphson method:

$$ x_{i+1}=x_i-\frac {f(x_i)}{f'(x_i)} $$

Example:

Find a root of an equation f(x)=x³-x-1 using Newton Raphson method

Solution:

$$ \text{Here} \ x^3-x-1=0 $$

$$ \text{Let} \ f(x)= x^3-x-1 $$

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

$$ \text{Here} \ f(1)=-1\lt 0 \ \text{and} \ f(2)=5\gt 0 $$

$$ \therefore \text{Root lies between 1 and 2} $$

$$ x_0=\frac {1+2}{2}=1.5 $$

1^st iteration :

$$ f(x_0)=f(1.5)=0.875 $$

$$ f′(x_0)=f′(1.5)=5.75 $$

$$ x_1=x_0-\frac {f(x_0)}{f'(x_0)} $$

$$ x_1=1.5-\frac {0.875}{5.75} $$

$$ x_1=1.34783 $$

2^nd iteration :

$$ f(x_1)=f(1.34783)=0.10068 $$

$$ f′(x_1)=f′(1.34783)=4.44991 $$

$$ x_2=x_1-\frac {f(x_1)}{f'(x_1)} $$

$$ x_2 =1.34783- \frac {0.10068}{4.44991} $$

$$ x_2=1.3252 $$

3^rd iteration :

$$ f(x_2)=f(1.3252)=0.00206 $$

$$ f′(x_2)=f′(1.3252)=4.26847 $$

$$ x_3=x_2-\frac {f(x_2)}{f'(x_2)} $$

$$ x_3=1.3252-\frac {0.00206}{4.26847} $$

$$ x_3=1.32472 $$

4^th iteration :

$$ f(x_3)=f(1.32472)=0 $$

$$ f′(x_3)=f′(1.32472)=4.26463 $$

$$ x_4=x_3-\frac {f(x_3)}{f'(x_3)} $$

$$ x_4=1.32472-\frac {0}{4.26463} $$

$$ x4=1.32472 $$

Approximate root of the equation x³-x-1=0 using Newton Raphson mehtod is 1.32472

Secant method:

$$ x_{i+1}=x_i- \left[ \frac {f(x_i)(x_{i-1}-x_i)}{f(x_{i-1})-f(x_i)}\right] $$

Example:

Compute the root of the equation \( x^2e^{–\frac x2} = 1 \) in the interval [0, 2] using the secant method. The root should be correct to three decimal places.

Solution:

$$ x_0 = 1.42, x_1 = 1.43, f(x_0) = – 0.0086, f(x_1) = 0.00034. $$

Apply, secant method, The first approximation is,

$$ x_2 = x_1 – \left[ \frac {( x_0 – x_1)}{(f(x_0) – f(x_1)} \right]f(x_1) $$

$$ = 1.43 – \left[ \frac {( 1.42 – 1.43)}{(0.00034 – (– 0.0086))} \right](0.00034) $$

$$ = 1.4296 $$

$$ f(x2) = – 0.000011 (–ve) $$

The second approximation is,

$$ x_3 = x_2 – \left[ \frac {( x_1 – x_2)}{(f(x_1) – f(x_2))} \right]f(x_2) $$

$$ = 1.4296 – \left[ \frac {( 1.42 – 1.4296)}{(0.00034 – (– 0.000011))} \right](– 0.000011) $$

$$ = 1.4292 $$

Since, x₂ and x₃ matching up to three decimal places, the required root is 1.429.

$$ $$

$$ $$

$$ $$

$$ $$