Rate of Convergence - Numerical Analysis, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET PDF Download

 Page 1


   
      
 
Order and rate of convergence
Iteration is a common approach widely used in various numerical methods. It is the hope that an iteration in the
general form of  will eventually converge to the true solution  of the problem at the limit
when . The concern is whether this iteration will converge, and, if so, the rate of convergence.
Specifically we use the following to represent how quickly the error  converges to zero: 
 
Here  is called the order of convergence, the constant  is the rate of convergence or asymptotic error
constant.
This expression may be better understood when it is interpreted as  when .
Obviously, the larger  and the smaller , the more quickly the sequence converges. Specially, we consider the
following cases:
If  and , , then
if , the convergence is sublinear
if , the convergence is linear with the rate of convergence of .
if , the convergence is superlinear
If , , the convergence is quadratic.
If , , the convergence is cubic.
The iteration  can be written in terms of the errors  and . Consider the Taylor
expansion: 
 
Subtracting  from both sides, we get 
 
Page 2


   
      
 
Order and rate of convergence
Iteration is a common approach widely used in various numerical methods. It is the hope that an iteration in the
general form of  will eventually converge to the true solution  of the problem at the limit
when . The concern is whether this iteration will converge, and, if so, the rate of convergence.
Specifically we use the following to represent how quickly the error  converges to zero: 
 
Here  is called the order of convergence, the constant  is the rate of convergence or asymptotic error
constant.
This expression may be better understood when it is interpreted as  when .
Obviously, the larger  and the smaller , the more quickly the sequence converges. Specially, we consider the
following cases:
If  and , , then
if , the convergence is sublinear
if , the convergence is linear with the rate of convergence of .
if , the convergence is superlinear
If , , the convergence is quadratic.
If , , the convergence is cubic.
The iteration  can be written in terms of the errors  and . Consider the Taylor
expansion: 
 
Subtracting  from both sides, we get 
 
At the limit , all higher order error terms become zero, we have 
 
If , then the convergence is linear. However, if , then 
 
and we have 
 
the convergence is quadratic. We see that if the iteration function has zero derivative at the fixed point, the
iteration may be accelerated.
Examples:
, the sequence is  
This is a sublinear convergence as only when  will the limit be a constant .
, the sequence is  
This is a linear convergence of order  and rate .
Page 3


   
      
 
Order and rate of convergence
Iteration is a common approach widely used in various numerical methods. It is the hope that an iteration in the
general form of  will eventually converge to the true solution  of the problem at the limit
when . The concern is whether this iteration will converge, and, if so, the rate of convergence.
Specifically we use the following to represent how quickly the error  converges to zero: 
 
Here  is called the order of convergence, the constant  is the rate of convergence or asymptotic error
constant.
This expression may be better understood when it is interpreted as  when .
Obviously, the larger  and the smaller , the more quickly the sequence converges. Specially, we consider the
following cases:
If  and , , then
if , the convergence is sublinear
if , the convergence is linear with the rate of convergence of .
if , the convergence is superlinear
If , , the convergence is quadratic.
If , , the convergence is cubic.
The iteration  can be written in terms of the errors  and . Consider the Taylor
expansion: 
 
Subtracting  from both sides, we get 
 
At the limit , all higher order error terms become zero, we have 
 
If , then the convergence is linear. However, if , then 
 
and we have 
 
the convergence is quadratic. We see that if the iteration function has zero derivative at the fixed point, the
iteration may be accelerated.
Examples:
, the sequence is  
This is a sublinear convergence as only when  will the limit be a constant .
, the sequence is  
This is a linear convergence of order  and rate .
, the sequence is  
This is superlinear, specifically quadratic, convergence of order  and rate .
From these examples we see that there is a unique exponent , the order of convergence, so that 
 
In practice, the true solution  is unknown and so is the error . However, it can be estimated if
the convergence is superlinear, satisfying 
 
Consider: 
 
   
  
i.e., when , 
The order and rate of convergence can be estimated by