Sunday, October 4, 2009

False Position Method

This is the oldest method for finding the real root of a nonlinear equation f(x) = 0 and closely resembles the bisection method. In this method, also known as regula falsi or the method of chords, we choose two points a and b such that f(a) and f(b) are of opposite signs. Hence, a root must lie in between these points. Now, the equation of the chord joining the two points [a, f(a)] and [b, f(b)] is given by

{y – f(a)}/{x – a} = {f(b) – f(a)}/{b – a}

The method consists in replacing the part of the curve between the points [a, f(a)] and [b, f(b)] by means of the chord joining these points, and taking the point of intersection of the chord with the x-axis as an approximation to the root. The point of intersection in the present case is obtained by putting y = 0 in first equation. Thus, we obtain

x1 = a – {(b – a)f(a)}/{f(b) – f(a)} = {af(b) – bf(a)}/{f(b) – f(a)}

Which is the first approximation to the root of f(x) = 0. If now f(x1) and f(a) are of opposite signs, then the root lies between a and x1, and we replace b by x1 in second equation, and obtain the next approximation. Otherwise, we replace a by x1 and generate the next approximation. The procedure is repeated till the root is obtained to the desired accuracy. Figure gives a graphical representation of the method.

Example: - Find a real root of the equation f(x) = x3 - 2x - 5 = 0.

Soln: -

We find f(2) = -1 and f(3) = 16. Hence a = 2 , b = 3, and a root lies between 2 and 3. Using False Position Method Formula:

x1 = {2(16) - 3(-1)}/{16 - (-1)} = 2.058823529

Now, f(x1) = -0.390799917 and hence the root lies between 2.058823529 and 3.0. Using False Position Method Formula:

x2 = {2.058823529(16) - 3(-0.390799917)}/{16 - (-0.390799917)} = 2.08126366

Since f(x2) = -0.147204057, it follows that the root lies between 2.08126366 and 3.0. Hence, we have

x3 = {2.08126366(16) - 3(-0.147204057)}/{16 - (-0.147204057)} = 2.089639211

Proceeding in this way, we obtain successively:

x4 = 2.092739575, x5 = 2.09388371,

x6 = 2.094305452, x7 = 2.094460846, ………..

The correct value is 2.0945…., so that x7 is correct to five significant figures.

Saturday, October 3, 2009

Newton-Raphson Method

This method is generally used to improve the result obtained by one of the previous methods. Let xo be an approximate root of f(x) = 0 and let x1 = xo + h be the correct root so that f(x1) = 0. Expanding f(xo + h) by Taylor’s series, we obtain

f(xo) + hf’(xo) + h2f’’(xo)/2! +-----= 0

Neglecting the second and higher order derivatives, we have

f(xo) + hf’(xo) = 0

Which gives

h = - f(xo)/f’(xo)

A better approximation than xo is therefore given be x1, where

x1 = xo – f(xo)/f’(xo)

Successive approximations are given by x2, x3,----,xn+1, where

xn+1 = xn – f(xn)/f’(xn)

Which is the Newton-Raphson formula.

Example: - Find a real root of the equation x3 -5x + 3 = 0.

Soln: -

Let, f(x) = x3 -5x + 3 = 0

f’(x) = 3x2 - 5

Choosing xo = 1

Step-1:

f(xo) = -1

f(xo) = -2

So, x1 =1 – ½ = 0.5

Step-2:

f(x1) = 0.625

f’(x1) = -4.25

x2 = 0.5 + 0.625/4.25 = 0.647

Step-3:

f(x2) = 0.0356

f’(x2) = -4.139

X3 = 0.647+ 0.0356/4.1393 = 0.6556

Step-4:

f(x3) = 0.0037

f’(x3) = -3.7105

x4 = 0.6556 + 0.0037/3.7105 = 0.6565

The successive approximation 0.6565

The Bisection Method

If a function f(x) is continuous between a and b, and f(a) and f(b) are of opposite signs, then there exists at least one root between a and b. For definiteness, let f(a) be negative and f(b) be positive. Then the root lies between a and b and let its approximate value be given by x0 = (a+b)/2. If f(x0)=0, we conclude that x0 is a root of the equation f(x) =0. Otherwise, the root lies either between x0 and b, or between x0 and a depending on whether f(x0) is negative or positive.

The method is shown graphically on the below

Example: - Find a real root of the equation f(x) = x3 – x – 1 = 0.

Soln: -

Given, f(x) = x3 – x – 1

And f(1) = -1

f(2) = 5

Since f(1) is negative and f(2) is positive, a root lies between 1 and 2,

Step-1:

Here, a = 1 and b = 2

So, xo =(1+2)/2=1.5

f(xo) = 0.875

xo =1.5

Step-2:

a = 1 , b = 1.5

x1 = (1+1.5)/2 = 1.25

f (x1) = -0.296875

x1 = 1.25

Step-3:

a = 1.25 , b = 1.5

x2 = 1.375

f(x2) = 0.2246

x2 =1.375

The procedure is repeated and the successive approximations are

x3 = 1.3125, x4 = 1.34375, x5 = 1.328125, etc.


Introductory Methods of Numerical Analysis