Blog

Roots of equation

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 [a0,b0] such that f(a0)f(b0)<0.
  2. Compute f(m0) where m0=(a0+b0)/2 is the midpoint.
  3. Determine the next subinterval [a1,b1]:
    • If f(a0)f(m0)<0, then let [a1,b1] be the next interval with a1=a0 and b1=m0.
    • If f(b0)f(m0)<0, then let [a1,b1] be the next interval with a1=m0 and b1=b0.
  4. Repeat (2) and (3) until the interval [aN,bN] reaches some predetermined length.
  5. Return the midpoint value mN=(aN+bN)/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)=x3-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 $$
x 0 1 2
f(x) -1 -1 5
$$ \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 $$

1st 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 $$

2nd 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 $$

3rd 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 $$

4th 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 x3-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, x2 and x3 matching up to three decimal places, the required root is 1.429.

$$ $$

$$ $$
$$ $$
$$ $$

Leave a Reply