Engineering Mathematics : Numerical Methods

1. An Iterative Method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems.

A specific implementation of an iterative method, including the termination criteria, is an algorithm of the iterative method.

The different iterative methods for Non Linear System of Equations are

1.    Bisection / Binary search method

2.    Regula Falsi / False position method

3.    Secant method

4.    Newton – Raphson method

The different iterative methods for Linear System of Equations are

1.    Gauss Seidel method  ( Upper + LD )

2.    Jacobi’s method  ( Diagonal + LU )
Direct methods are procedures that apply a few steps and get the exact solution in one shot. No iterations are performed.

The Direct methods for Linear system of equations are –

1.    Gauss Elimination method

2.    Gauss Jordan method

Gauss Elimination is faster than Gauss Jordan, although both share the O(n³) time complexity.

            Rate of convergence –

            Gauss Elimination = n³ / 3

            Gauss Jordan        = n³ / 2

GAUSS SEIDEL’s Method (Method of Simultaneous Displacements)

1. It is an iterative method for solving Linear System of Equations.

2. Although it can be applied to any matrix with non-zero elements on the diagonals, convergence is only guaranteed if the matrix is either diagonally dominant, or symmetric and positive definite.

A matrix is said to be diagonally dominant if for every row of the matrix, the magnitude of the diagonal entry in a row is larger than or equal to the sum of the magnitudes of all the other (non-diagonal) entries in that row.

3. Given a square system of n linear equations with unknown x:

Where:

Then A can be decomposed into a lower triangular component L_*, and a strictly upper triangular component U:

4. In Gauss Seidel method to calculate the value of an in-determinate, i.e., an unknown, we take into consideration the most recent values of other unknowns. Thus, for storage only one vector is required since the new value can overwrite the old one and be used for subsequent calculations.

But in Jacobi’s method only the old values are considered. The new values must be kept separately. Hence, an extra storage vector is needed in Jacobi’s method. But parallelism is possible in the sense that all unknowns can be calculated simultaneously. This parallelism is not possible in Gauss Seidel method.

JACOBI’s Method (Method of Simultaneous Displacements)

It is exactly same as Gauss Seidel method with only Few differences –

1. The given matrix A is broken down as a Diagonal matrix(D) and a Remainder matrix  which is nothing but the sum of the strict Lower triangular matrix of A and the strict Upper triangular matrix.

A = D + R , where

R= L+U

Therefore, for Ax = B,

(D + R) x = B

Dx = B - Rx

X(n+1) =  - D ^{− 1} * R * X(n) +  D ^{− 1} * B

X(n+1) =  - D ^{− 1} * (L+U) * X(n) +  D ^{− 1} * B

It can be clearly seen here that the all diagonal elements of A must be non zero. If even one is 0 then D ^{− 1} won’t exist.

2. Whereas in the Gauss Seidel the A was decomposed in a Lower Triangular Matrix (L+D) and the Remainder Matrix (U) containing the sum of Diagonal Matrix and the Strict Lower Triangular Matrix.

      A = (L+D) + R , where

      R = U

     

Therefore, for Ax = B,

((L+D) + R) x = B

(L+D)x = B - Rx

X(n+1) =  - (L+D)^{− 1} * R * X(n) +  (L+D) ^{− 1} * B

X(n+1) =  - (L + D)^{− 1} * U * X(n) +  (L+D) ^{− 1} * B

And here the diagonal elements can be zero in contrast to Jacobi’s method.

3. Gauss Seidel’s method uses the latest values of unknowns while going through the iterations whereas Jacobi’s method uses only the old values.

4. Spectral Radius (Gauss Seidel) = [ Spectral Radius (Jacobi) ] ²

Rate of Variance (Gauss Seidel) = 2 x [ Rate of Variance (Jacobi) ]

( since, Rate of Variance = - ln(spectral radius) )

Newton-Raphson Method

A function ƒ is said to be continuously differentiable if the derivative ƒ′(x) exists, and is itself a continuous function. Though the derivative of a differentiable function never has a jump discontinuity, it is possible for the derivative to have an essential discontinuity. For example, the function

is differentiable at 0, since

exists. However, for x≠0, f '(x) = 2xsin (1 / x) − cos (1 / x) which has no limit as x → 0.

Types Of Discontinuities –

Consider a real valued function ƒ of a real variable x, defined in a neighborhood of the point x₀ in which ƒ is discontinuous. Then three situations may be distinguished:

1. The one-sided limit from the negative direction

and the one-sided limit from the positive direction

at x₀ exist, are finite, and are equal to L = L ⁻ = L ⁺ . Then, if ƒ(x₀) is not equal to L, x₀ is called a removable discontinuity. This discontinuity can be removed to make ƒ continuous at x₀, or more precisely, the function

is continuous at x=x₀.

2. The limits L ⁻ and L ⁺ exist and are finite, but not equal. Then, x₀ is called a jump discontinuity or step discontinuity. For this type of discontinuity, the function ƒ may have any value in x₀.

3. One or both of the limits L ⁻ and L ⁺ does not exist or is infinite. Then, x₀ is called an essential discontinuity, or infinite discontinuity.

Convergence –

Let f(x) be a continuous differentiable and x=a be a simple root to the equation f(x) = 0 (and also it is assumed that the initial point chosen is not bad, as explained in next section), then

1.    If f ’(a) <> 0 then there exists a neighborhood of ‘a’ such that any value of x in that neighborhood will lead to convergence.

2.    If f ’(a) <> 0 and f ”(a) exists then there exists a neighborhood of ‘a’ such that any value of x in that neighborhood will cause the rate of convergence to be quadratic or faster.

3.    If f(x) is twice continuous differentiable and f ‘(a) = 0 and also f”(a) <> 0, then there exists a neighborhood of ‘a’ such that any initial value in that neighborhood causes the iterations to converge linearly.

Thus Derivative being zero doesn’t mean that Newton-Raphson method will diverge.

Alternatively, if f(x) is continuous differentiable in U, which is a neighborhood of ‘a’ such that f ‘(a) = 0 but f ‘(x) <> 0 for all x <> a in U, then there exists a neighborhood of ‘a’ such that any initial value in that neighborhood would cause the iterations to converge linearly.

NOTE: The function f(x) must be continuous differentiable in the neighborhood of the root else the Newton-Raphson method diverges.

All the above points talk about convergence with respect to some neighborhood of the root. This is called local convergence. But not always do we know the neighborhood in advance. Thus for global convergence a result is as follows –

If f(x) is twice differentiable (may or may not be twice continuous differentiable) to the right of a simple root x=a, and for all such x (, i.e., all x to the right of ‘a’) if we have f ‘(x) <> 0 and f(x) * f “(x) > 0 then the iterations will cause convergence.

Bad Starting Points –

In some cases the conditions on the function that are necessary for convergence are satisfied, but the point chosen as the initial point is not in the interval where the method converges. This can happen, for example, if the function whose root is sought approaches zero asymptotically as x goes to  or  - In such cases a different method, such as bisection, should be used to obtain a better estimate for the zero to use as an initial point.

1. If the initial point is a stationary point, i.e., where the derivative = 0 then Newton-Raphson method diverges.

Example –

f(x) = 1- x² has a maximum at x=0, i.e., f (0) = 1 (which is maximum). Thus if x=0 is chosen as the initial point then Newton-Raphson won’t work.

2. Starting point enters a cycle

                          

The tangent lines of x³ - 2x + 2 at 0 and 1 intersect the x-axis at 1 and 0 respectively, illustrating why Newton's method oscillates between these values for some starting points.

For some functions, some starting points may enter an infinite cycle, preventing convergence. Let,

       

and take 0 as the starting point. The first iteration produces 1 and the second iteration returns to 0 so the sequence will alternate between the two without converging to a root.

Thus, even if a function is twice continuous differentiable (as is x³ - 2x + 2), i.e., f ”(x) is continuous, then irrespective of the fact that whether f ’(a) and f ”(a) are equal to 0 or not (‘a’ being a simple root) we can’t be sure of it’s convergence. The Newton-Raphson method may fall in a closed orbit.

Divergence –

Derivative issues

If the function is not continuously differentiable in a neighborhood of the root then it is possible that Newton's method will always diverge and fail, unless the solution is guessed on the first try.

Derivative does not exist at root

A simple example of a function where Newton's method diverges is the cube root, which is continuous and infinitely differentiable, except for x=0, where its derivative is undefined (this, however, does not affect the algorithm, since it will never require the derivative if the solution is already found):

For any iteration point x_n, the next iteration point will be:

The algorithm overshoots the solution and lands on the other side of the y-axis, farther away than it initially was; applying Newton's method actually doubles the distances from the solution at each iteration.

In fact, the iterations diverge to infinity for every f(x) = | x | ^α, where

 .

In the limiting case of (square root), the iterations will alternate indefinitely between points x₀ and −x₀, so they do not converge in this case either.

Discontinuous derivative

If the derivative is not continuous at the root, then convergence may fail to occur in any neighborhood of the root. Consider the function

Its derivative is:

Within any neighborhood of the root, this derivative keeps changing sign as x approaches 0 from the right (or from left) while f(x) ≥ x − x² > 0 for 0 < x < 1.

So f(x)/f '(x) is unbounded near the root, and Newton's method will diverge almost everywhere in any neighborhood of it, even though:

• The function is differentiable (and thus continuous) everywhere;
• The derivative at the root is nonzero;
• f  is infinitely differentiable except at the root; and
• The derivative is bounded in a neighborhood of the root (unlike f(x)/f '(x)).

Transcendental Functions –

The logarithm and the exponential function are examples of transcendental functions. Transcendental function is a term often used to describe the trigonometric functions (sine, cosine, tangent, their reciprocals cotangent, secant, and cosecant).

All of the following functions are transcendental.