The Order of Approximation

    Clearly, the sequences    and    are both converging to zero.  In addition, it should be observed that the first sequence is converging to zero more rapidly than the second sequence.  In the coming modules some special terminology and notation will be used to describe how rapidly a sequence is converging.

Definition 1.  The function    is said to be big Oh of  ,  denoted  ,  if there exist constants    and    such that  

           whenever   .  

Example 1.  Consider the functions    and  .   Show that   ,  over the interval  .  
Solution 1.

    The big Oh notation provides a useful way of describing the rate of growth of a function in terms of well-known elementary functions (, etc.).  The rate of convergence of sequences can be described in a similar manner.

Definition 2.  Let    and    be two sequences.  The sequenceis said to be of order big Oh of, denoted  ,  if there exist    and  N  such that  

           whenever   .  

Example 2.  Given the sequences   and  .  Show that  .  
Solution 2.

    Often a function    is approximated by a function    and the error bound is known to be  .  This leads to the following definition.

Definition 3.  Assume that    is approximated by the function    and that there exist a real constant    and a positive integer n so that  

           for sufficiently small h.  
We say that  approximates  with order of approximation  and  write

        .  

    When this relation is rewritten in the form  ,  we see that the notation  stands in place of the error bound  .  The following results show how to apply the definition to simple combinations of two functions.

Theorem (Big "O" Remainders for Series Approximations).  

Assume that    and  ,  and  .  Then

(i)        ,   
    
(ii)        ,  
    
(iii)        ,

provided that   .  

Proof  Big O Truncation Error  Big O Truncation Error  
Exploration.

    It is instructive to consider    to be the degree Taylor polynomial approximation of  ;  then the remainder term is simply designated  ,  which stands for the presence of omitted terms starting with the power  .  The remainder term converges to zero with the same rapidity that  converges to zero as h approaches zero, as expressed in the relationship

        

for sufficiently small  h.  Hence the notation    stands in place of the quantity  , where  M  is a constant or behaves like a constant.

Theorem ( Taylor polynomial ).  Assume that the function    and its derivatives    are all continuous on  .  If  both    and    lie in the interval  ,  and    then  

    ,  
    
is the n-th degree Taylor polynomial expansion of    about  .  The Taylor polynomial of degree n  is

       
and  
    .

The integral form of the remainder is  

    ,

and Lagrange's formula for the remainder is

    

where depends on and lies somewhere between  .  

Proof  Big O Truncation Error  Big O Truncation Error  
Exploration.

Example 3.  Consider    and the Taylor polynomials of degree    expanded about  .  

        

          

          

          
Solution 3.

    The following example illustrates the theorems above.  The computations use the addition properties  

(i)        ,  

(ii)           where   ,  

(iii)             where      .    

Example 4.  First find Maclaurin expansions for    and    of order    and   ,  respectively.
Then experiment and find the order of approximation for their sum, product and quotient.  
Solution 4.

Example 5.  First find Maclaurin expansions for    and    of order    and   ,  respectively.
Then experiment and find the order of approximation for their sum, product and quotient.  
Solution 5.

Order of Convergence of a Sequence

    Numerical approximations are often arrived at by computing a sequence of approximations that get closer and closer to the answer desired. The definition of big Oh for sequences was given in definition 2, and the definition of order of convergence for a sequence is analogous to that given for functions in Definition 3.

Definition 4.  Suppose that    and    is a sequence with  .  We say that  converges to x with the order of convergence  ,  if there exists a constant    such that

           for n sufficiently large.  

This is indicated by writing

        
or
          with order of convergence .  

Example 6.  Let    and  ;  then    with a rate of convergence  .  
Solution 6.

A Scenarios and Animations related to this module.

Animations (Taylor and Maclaurin Polynomial Approximation  Taylor and Maclaurin Polynomial Approximation).  Internet hyperlinks to animations.

Research Experience for Undergraduates

Big O Truncation Error  Big O Truncation Error  Internet hyperlinks to web sites and a bibliography of articles.  

Download this Mathematica Notebook Big O Truncation Error

(c) John H. Mathews 2004