What are that iteration methods compare different iterative method?

What are that iteration methods compare different iterative method?

What are the iteration methods?

An iterative method is a powerful device of solving and finding the roots of the non linear equations. It is a process that uses successive approximations to obtain more accurate solutions to a linear system at each step. Such a method involves a large number of iterations of arithmetic operations to arrive at a solution for which the computers are very often used in its process to make the task simple and efficient.

Iteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called iteration and the results of one iteration are used as the starting point for the next iteration.

For example, to solve the quadratic equation we may choose any one of the following iteration methods:

a0x^2 +a1x+a2=0

a) Xk+1 = -a2+a0xk^2/a1, k=0,1,2---

b) Xk+1= -a2/a0xk+a1,k=0,1,2-------

Types of iteration methods:

Based upon the number of initial approximation values iteration methods can be divided into two categories:

1. Bracketing iteration methods
2. Open end iteration methods

Bracketing iteration method:

These methods are also known as interpolation methods. Under these methods we start with two initial roots that in bracket, then systematically reduce the width of the bracket until the desired solution is arrived at.

There are two popular methods under this category:

1. Bisection method
2. Regular_falsi method

Open end iteration method: these methods are known as extrapolation methods. Under these methods we start with one or two initial roots that do not need the bracket the root.

These methods are various types:

1. Netwon_raphson method
2. Secant method
3. Muller's method

Bisection, regular_falsi and netwon_raphson methods are under root finding algorithm.

Root finding algo:

A root-finding algorithm is a numerical method, or algorithm, for finding a value x such that f(x) = 0, for a given function f. Such an x is called a root of the function f.

Iteration method is obtain the initial approximation to the root is based upon the intermediate value theorem.

This theorem is states that: if f(x) is continuous function on some interval[a,b] and f(a).f(b)<0, then the equation f(x)=0 has at least one real root in the interval(a, b).

1) Bisection method:

This method is based on the application of intermediate valued theorem. It is based on the assumption that if f(x) is real, in the interval, a<x<b, and f (a) and f (b) are opposite signs. There is a small interval [a, b] including f(x) such that f (a).f (b) <0. Taking the midpoint c of interval [a,b], there are three possibilities:

• C=a+b/2
• F(c)=0; then c is the root r
• F(c).f(a)<0; then the root in the interval [a,c]
• F(c).f(b)<0; then the root in the interval [c,b]

So root in small interval [a, c] or [c, b].

A few steps of the bisection method applied over the starting range [a1; b1]. The bigger red dot is the root of the function.

Procedure: There are following steps are to be taken to find the root of a function under the bisection methods:

1. Get the two initial values of x which falls on the opposite sides of roots.
2. Carry on the iteration cycle by bisecting the interval and by locating the root in one of the halves. Bisect further, the half of the interval in which the root lies.
3. See that each iteration takes us closer to the root by one binary digit.
4. Stop the iteration cycle when the interval size appears to be smaller than the specified precision required in the value of the root.

For example of bisection method:

Find the root of the function f(x) =x^2-4x-10 in the three iteration?

Sol: f(x) =x^2-4x-10

X0=-2, x1=-1

F (-2) = 2, f (-1) = -5

Iteration-1

X2=-2-1/2=1.5

F (-1.5) = -1.75

So root lie in interval [-1.5,-2]

Iteration-2

X3=-1.5-2/2=-1.75

F (-1.75) =0.0625

So root lie in interval [-1.5,-1.75]

Iteration-3

X4=-1.5-1.75/2=-1.625

F (-1.625) = -0.859

So root lie in interval [-1.75,-1.625]

2) Regular-falsi method:

This method has been evolved as an attempt to speed up the process of the bisection method retaining at the same time its guaranteed convergence. Under this method an improved estimate of the root called false position of the root is obtained at the point x0 where the straight line joining the two extreme points x1 and x2 of the interval cuts the x-axis.

Like the bisection method, the false position method starts with two points x0 and x10 such that f(x0) and f(x1) are of opposite signs, which implies by the intermediate value theorem that the function f has a root in the interval [x0, x1].

F(x) =a0x+a1=0

Find the value of x

X= -a1/a0

If xk-1 and xk are two approximations to the root:

Fxk-1 =a0xk-1+a1

Fxk=a0xk+a1

We take formula of regular falsi method

Xk+1=xk-[(xk-xk-1)/ (fk-fk-1)]*fk

K=0, 1, 2, 3------

Regula-Falsi Algorithm.

Find the real root of f(x) =x^2-4x-10 by two iteration method

Sol: f(x) =x^2-4x-10

X0=-1, x1=-2

F(x0)=-5, f(x1)=2

Xk+1=xk-[(xk-xk-1)/(fk-fk-1)]*fk

X2=-2-[(-2+1)/(2+5)]2

X2=-1.71428

F (-1.71428) =.00855184

X3=x2-[(x2-x1)/(fx2-fx1)]*fx2

X3=-1.7189

3) Netwon-raphson method:

This is an iterative method of successive approximation which terminates when the difference between any two successive values is within a prescribed limit. This method is applicable in general and can be used to find out the roots of the polynomial.

Netwon_raphson formula:

For finding the successive approximates to root of a polynomial function, we can apply following formula:

Given a function ƒ (xk) and its derivative ƒ'(xk), we begin with a first guess xk.

Xk+1=xk-[f (xk)/f' (xk)]

Description of the method

An illustration of one iteration of Newton's method (the function ƒ is shown in blue and the tangent line is in red). We see that xn+1 is a better approximation than xn for the root x of the function f.

Application to minimization and maximization problems

Newton's method can also be used to find a minimum or maximum of a function. The derivative is zero at a minimum or maximum, so minima and maxima can be found by applying Newton's method to the derivative. The iteration becomes:

Xk+1=xk-(fk/f'k)

Newton's method is an extremely powerful technique -- in general the convergence is quadratic: the error is essentially squared at each step (that is, the number of accurate digits doubles in each step). However, there are some difficulties with the method.

1. Newton's method requires that the derivative be calculated directly. In most practical problems, the function in question may be given by a long and complicated formula, and hence an analytical expression for the derivative may not be easily obtainable. In these situations, it may be appropriate to approximate the derivative by using the slope of a line through two points on the function. In this case, the Secant method results. This has slightly slower convergence than Newton's method but does not require the existence of derivatives.
2. If the initial value is too far from the true zero, Newton's method may fail to converge. For this reason, Newton's method is often referred to as a local technique. Most practical implementations of Newton's method put an upper limit on the number of iterations and perhaps on the size of the iterates.
3. If the derivative of the function is not continuous the method may fail to converge.

Example of netwon_ raphson method:

Square root of a number

For example, three iteration to find the cube root of 17, with initial approximation number is 2

X^3=17

The function to use in Newton's method is then,

F(x) = x^3-17

F (2) = -9

With derivative,

F'(x) = 3x^2

F' (2) = 12

First iteration:

X1= x0-[f(x0)/f'(x0)]

2-[-9/12] = 2.75

X1=2.75

Second iteration:

X2=x1-[f(x1)/f'(x1)]

2.75-[3.7968/22.6875]= 2.58265

X2=2.58265

Third iteration:

X3=x2-[f(x2)/f'(x2)]

2.58265-[f (2.58265)/f'(2.58265)]=2.5332

X3= 2.5332

Comparison of the different iteration methods

We have already explain the three different iterative methods:

1. Bisection method
2. Reguler falsi method
3. Newton raphson method

Now we take a comparison between these methods on the basis of following points:

Rate of convergence

Amount of efforts

Sensitivity to the initial and intermediate values

1. Rate of convergence: in the bisection methods the rate of converges slowly and steadily. Regular falsi method is the improvement of bisection so rate of convergence is slow but not bisection as it first order convergent. But the netwon_raphson method is guaranteed to converge and the rate of its convergence is fastest one.
2. Amount of efforts: bisection method needs very less amount of efforts in computational works as it is the simplest of all the iterative method. In the regular_falsi method needs little more amounts of computational works per iteration which is equal to one function evaluation only. But the netwon_raphson method needs considerable amount of efforts and time in computation of the values of f(x) and f'(x).
3. Sensitivity to the initial and intermediate values: on the point of sensitivity to the initial and intermediate values we find that the bisection method is quite sensitive to the initial and intermediate values. The falsi method is little sensitive to these values. But the netwon_raphson methods are highly sensitive to the initial and intermediate values.

From all the above points the netwon_raphson method is the excellent one.