## 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.