METHODS

 Introduction

In practical use, an engineer would finally obtain result in a numerical form for example, for a set of tabulated data derived from an experiment, inferences may have to be drawn: or, a system of linear algebraic equations is to be solved.

                    The aim of the Numerical Analysis is to provide efficient methods for obtaining numerical answers to such problems.

           

Rounding-off

In Numerical computations, we come across numbers which have large number of digits and it will be necessary to cut them to a usable number of figures. This process is called Rounding-off.

                It is usual to round off numbers according to the following rules.

To round off number to n significant digits, discard all digit to the right of the     n^th digit, and if this discard number is-

1]   Less than half a unit in the n^th place, leave the n^th digit unaltered.
2]   Greater than half a unit in the n^th place, increase the n^th digit by unity.
3]    Exactly half a unit in the n^th place, increase the n^th digit by unity if it is odd        otherwise, leave it unchanged.

                The number thus rounded off said to be correct to n significant figures.

  

Errors

Absolute Error, Relative error and Percentage error

Absolute error :- Absolute error is the numerical difference between the true value of a quantity and its approximate value.

       Thus, if X is the true value of a quantity and X1 is its approximate value, then the absolute error E_A is given by

                                          E_A = X - X1 = δx                                   ....................... (1)

  Relative error :- The relative error E_R is defined by

                                          E_{R =}   E_A /x  =  δx/x                                ..................... (2)

Percentage error :- The percentage error E_P defined by

                                           E_P = 100 E_R                                               ......................... (3)

Let ∆X be a number such that

(4)

Then   is an upper limit on the magnitude of the absolute error and is said to measure absolute accuracy. Similarly, the quantity

                                      

                                               ∆X /|x|   ≈  ∆X /|x1|  

Measure the relative accuracy. It is easy to reduce that if two numbers are added or subtracted, then the magnitude of the absolute error in the result is the sum of the magnitudes of the absolute errors in the two numbers. More generally, if E_A¹, E_A^2, E_A^3....... E_Aⁿ   are the absolute errors in n numbers, and then the magnitude of the absolute error in their sum is given by

                                  |E_A¹| +| E_A² | + |E_A³ |......+ | E_Aⁿ |

NOTE:  While adding up several numbers of different absolute accuracies, the following procedure is adopted:

1.1)    Isolate the number with the greatest absolute error.

2.2)    Round-off all other numbers retaining in them one digit more than in the isolated number.

3.3)    Add up and Round=off the sum by discarding one digit.

                                                   

The Bisection Method

This method states that if a function f(x) is continuous between a and b, and f(a) and 

f(b) are of opposite sign, 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 let its approximate value be given by Xo = (a=b)/2. If f (Xo) = 0, we conclude that Xo is a root of equation f(x) = 0 otherwise, the root lies either between Xo & a depending on whether f(Xo) is negative or positive. We designate this new interval as [a1, b1] whose length is |b-a|/2. As before, this is bisected at X1 and the new interval will be exactly half the length of the previous one. We repeat this process until the latest interval is as small as desired, say ϵ. It is clear that the interval width is reduce by a factor of one half at each step and at the end of the n^th step, the new interval will be [a_n, b_n ] of length |b-a|/ 2ⁿ. We then have

                                      |b-a|/2ⁿ <=ϵ

  This gives on simplification

                      

                                        n >= [ loge(|b-a|)/ϵ]  / loge2 

Inequality equation (1) gives the number of iterations to achieve an accuracy ϵ. For example, if |b-a| = 1 and ϵ = 0.001,

Then it can be seen that

                                 n >= 10                                                   ...................... (2)

The method is shown graphically in figure (1)

    

It should be noted that this method always succeeds. If there are more roots than one in the interval, bisection finds one of the roots. It can be easily programmed using the following computational steps.

Steps for program:-

1)    Choose two real numbers a and b such that f(a) and f(b) <0.

2)    Set Xr = (a +b)/2

3)    (a): If f(a)*f (Xr) < 0, the root lies in the interval (a, Xr). Then, set

b = Xr and go to step 2 above.

                 (b): If f (a)*f (Xr) > 0, the root lies in the interval ( Xr, b). Then, set

a = Xr and go to step 2 above.

4)    If f (a)*f (Xr) = 0, it means that Xr is a root of a equation f(x) = 0 and the computation may be terminated.

In practical problems, the root may not be exact so that condition (3) above is never satisfied. In such a case, we need to adopt a criterion for deciding when to terminate the computations.

            A convenient criterion is to compute the percentage error

Ep defined by:

                            ϵ_r = | Xr' - Xr/ X'r| * 100%                  ....................... (3)

Where Xr’ is the new value of Xr.

        The computation can be terminated when Ep becomes less than a prescribed tolerance, say ϵ_p.  In addition, the maximum number of iterations may also be specified in advance.

The method of False Position

(Bracketing Method/ chord method)

This is the oldest method for finding the real root of the non-linear equation f(x) = 0 and closely resemble the Bisection method.

 This method is also known as Regular Falsi Method or method of chords, we choose two points a and b such that f(a) and f(b) are of opposite sign. 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)    =                          ................. (1)

The method consists in replacing the parts of the curve between the points [a, f(a)] and [b, f(b)] by means of the chord joining these points, and taking the points 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 substituting y = 0 in equation (1), thus we obtain

x1 = a – [f(a) / (f(b) - f(a)] *(b – a) = [a.f(b) - b.f(a)] / (f(b) -f (a))  ...... (2)

Which is the first approximation to the root of f(x) = 0.

                  If now f(x1) and f(a)  are opposite signs, then the root lies between a and x1, and we replaced b by x1 in equation (2) and obtained 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 (b) gives a graphical representation of the method.

                           

The error criterion can be used in this method is:

                               ϵ_r = | X0' - X0 / X0' | * 100%

Where x0’ is the new value of x0.The computations can be terminated when ϵ_r becomes less than a prescribed tolerance, say ϵ_p. In advance, the maximum number of iterations may also be specified in advanced.

Newton Raphson method

This method is used to improve the result obtained iby one of the previous methods (Bisection and False position method)

Let x0 be an approximate root of f(x) = 0 and let x1 = x0 + h be the correct root so that f(x1) = 0. Expanding f(x0+h) by Taylor’s series, we obtain h²

                   F(x0) + hf ’(x0) +h² /2 f ''(x0)+ ......... = 0

Neglecting the second and higher order derivatives, we have

                   F(x0) + hf’(x0) = 0

This gives

                                       h = - f(x0)/ f '(x0)

a better approximation than x0 is therefore given by x1, where

                                  x1 = x0 - [f(x0)/ f '(x0)]            ....................... (1)

Successive approximation are given by x2, x3.... x_n + 1, where

                            X_n +1 = X_n – [f(xn)/ f '(xn)]         ..................... (2)

This is the Newton Raphson formula.

Graphically the method consists in replacing the part of the curve between the points [x0, f(x0)] and the x-axis by means of the tangent to the curve at the point, and is described graphically in fig.(c). It can be used for solving both algebraic and transcendental equations and it can also be used when the roots are complex.

Secant Method

We have seen that the Newton Raphson method requires the evaluation of derivatives of the function and this is not always possible particularly in the case of functions arising in practical problems. In the Secant method, the derivatives at xi are approximated by the formula:

                                  f ’(xi) ≈ {[f(xi) - f(xi-1)]/[xi - (xi-1)]} 

This can be written as:

                                    f ’ = {[fi - (fi-1)]/ [xi - (xi-1)]}          ............. (1)

Where fi’ = f(xi). Hence, the Newton Raphson formula becomes

                            xi+1 =xi - { fi[xi - (xi-1)] / [fi - (fi-1)]

                                            =  {[(xi-1)fi] - [xi(fi-1)]/ [fi - (fi-1)] ....... (2)

Or

                         x0+1 = x0 -  { f(x0)[(x0 - (x0-1)] / [f(x0) - f(x0-1)]

                                =   {[(x0-1)f(x0)] - [x0.f(x0-1)]/ [f(x0) - (f(x0)-1)] .... (2)

It should be noted that this formula requires two initial approximation the root. 

x2= [xo.f(x1) - x1. f(x0)] / [f(x1) -f(x0)]