Big "O" Truncation Error


The [Graphics:Images/BigOMod_gr_1.gif] Order of Approximation

    Clearly, the sequences  
[Graphics:Images/BigOMod_gr_2.gif]  and  [Graphics:Images/BigOMod_gr_3.gif]  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  [Graphics:Images/BigOMod_gr_4.gif]  is said to be big Oh of  [Graphics:Images/BigOMod_gr_5.gif],  denoted  [Graphics:Images/BigOMod_gr_6.gif],  if there exist constants  [Graphics:Images/BigOMod_gr_7.gif]  and  [Graphics:Images/BigOMod_gr_8.gif]  such that  

[Graphics:Images/BigOMod_gr_9.gif]   whenever   [Graphics:Images/BigOMod_gr_10.gif].  


Example 1.  Consider the functions  [Graphics:Images/BigOMod_gr_11.gif]  and  [Graphics:Images/BigOMod_gr_12.gif].   Show that   [Graphics:Images/BigOMod_gr_13.gif],  over the interval  [Graphics:Images/BigOMod_gr_14.gif].  
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 ([Graphics:Images/BigOMod_gr_31.gif], etc.).  The rate of convergence of sequences can be described in a similar manner.


Definition 2.  Let  [Graphics:Images/BigOMod_gr_32.gif]  and  [Graphics:Images/BigOMod_gr_33.gif]  be two sequences.  The sequence[Graphics:Images/BigOMod_gr_34.gif]is said to be of order big Oh of[Graphics:Images/BigOMod_gr_35.gif], denoted  [Graphics:Images/BigOMod_gr_36.gif],  if there exist  [Graphics:Images/BigOMod_gr_37.gif]  and  N  such that  

[Graphics:Images/BigOMod_gr_38.gif]   whenever   [Graphics:Images/BigOMod_gr_39.gif].  


Example 2.  Given the sequences [Graphics:Images/BigOMod_gr_40.gif]  and  [Graphics:Images/BigOMod_gr_41.gif].  Show that  [Graphics:Images/BigOMod_gr_42.gif].  
Solution 2.


    Often a function  [Graphics:Images/BigOMod_gr_46.gif]  is approximated by a function  [Graphics:Images/BigOMod_gr_47.gif]  and the error bound is known to be  [Graphics:Images/BigOMod_gr_48.gif].  This leads to the following definition.


Definition 3.  Assume that  [Graphics:Images/BigOMod_gr_49.gif]  is approximated by the function  [Graphics:Images/BigOMod_gr_50.gif]  and that there exist a real constant  [Graphics:Images/BigOMod_gr_51.gif]  and a positive integer n so that  

[Graphics:Images/BigOMod_gr_52.gif]   for sufficiently small h.  
We say that  approximates  with order of approximation  and  write


    When this relation is rewritten in the form  [Graphics:Images/BigOMod_gr_54.gif],  we see that the notation[Graphics:Images/BigOMod_gr_55.gif]  stands in place of the error bound  [Graphics:Images/BigOMod_gr_56.gif].  The following results show how to apply the definition to simple combinations of two functions.


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

Assume that  [Graphics:Images/BigOMod_gr_57.gif]  and  [Graphics:Images/BigOMod_gr_58.gif],  and  [Graphics:Images/BigOMod_gr_59.gif].  Then

(i)        [Graphics:Images/BigOMod_gr_60.gif],   
(ii)        [Graphics:Images/BigOMod_gr_61.gif],  
(iii)        [Graphics:Images/BigOMod_gr_62.gif],

provided that   [Graphics:Images/BigOMod_gr_63.gif].  

Proof  Big O Truncation Error  Big O Truncation Error  


    It is instructive to consider  [Graphics:Images/BigOMod_gr_66.gif]  to be the [Graphics:Images/BigOMod_gr_67.gif] degree Taylor polynomial approximation of  [Graphics:Images/BigOMod_gr_68.gif];  then the remainder term is simply designated  [Graphics:Images/BigOMod_gr_69.gif],  which stands for the presence of omitted terms starting with the power  [Graphics:Images/BigOMod_gr_70.gif].  The remainder term converges to zero with the same rapidity that[Graphics:Images/BigOMod_gr_71.gif]  converges to zero as h approaches zero, as expressed in the relationship


for sufficiently small  
h.  Hence the notation  [Graphics:Images/BigOMod_gr_73.gif]  stands in place of the quantity  [Graphics:Images/BigOMod_gr_74.gif], where  M  is a constant or behaves like a constant.


Theorem ( Taylor polynomial ).  Assume that the function  [Graphics:Images/BigOMod_gr_75.gif]  and its derivatives  [Graphics:Images/BigOMod_gr_76.gif]  are all continuous on  [Graphics:Images/BigOMod_gr_77.gif].  If  both  [Graphics:Images/BigOMod_gr_78.gif]  and  [Graphics:Images/BigOMod_gr_79.gif]  lie in the interval  [Graphics:Images/BigOMod_gr_80.gif],  and  [Graphics:Images/BigOMod_gr_81.gif]  then  

is the n-th degree Taylor polynomial expansion of  [Graphics:Images/BigOMod_gr_83.gif]  about  [Graphics:Images/BigOMod_gr_84.gif].  The Taylor polynomial of degree n  is


The integral form of the remainder is  


and Lagrange's formula for the remainder is


where [Graphics:Images/BigOMod_gr_91.gif] depends on [Graphics:Images/BigOMod_gr_92.gif] and lies somewhere between  [Graphics:Images/BigOMod_gr_93.gif].  

Proof  Big O Truncation Error  Big O Truncation Error  


Example 3.  Consider  [Graphics:Images/BigOMod_gr_96.gif]  and the Taylor polynomials of degree  [Graphics:Images/BigOMod_gr_97.gif]  expanded about  [Graphics:Images/BigOMod_gr_98.gif].  

    [Graphics:Images/BigOMod_gr_99.gif]    [Graphics:Images/BigOMod_gr_100.gif]

    [Graphics:Images/BigOMod_gr_101.gif]    [Graphics:Images/BigOMod_gr_102.gif]  

    [Graphics:Images/BigOMod_gr_103.gif]    [Graphics:Images/BigOMod_gr_104.gif]  

    [Graphics:Images/BigOMod_gr_105.gif]    [Graphics:Images/BigOMod_gr_106.gif]  
Solution 3.


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

(i)        [Graphics:Images/BigOMod_gr_122.gif],  

(ii)        [Graphics:Images/BigOMod_gr_123.gif]   where   [Graphics:Images/BigOMod_gr_124.gif],  

(iii)        [Graphics:Images/BigOMod_gr_125.gif]     where      [Graphics:Images/BigOMod_gr_126.gif].    


Example 4.  First find Maclaurin expansions for  [Graphics:Images/BigOMod_gr_127.gif]  and  [Graphics:Images/BigOMod_gr_128.gif]  of order  [Graphics:Images/BigOMod_gr_129.gif]  and   [Graphics:Images/BigOMod_gr_130.gif],  respectively.
Then experiment and find the order of approximation for their sum, product and quotient.  
Solution 4.


Example 5.  First find Maclaurin expansions for  [Graphics:Images/BigOMod_gr_143.gif]  and  [Graphics:Images/BigOMod_gr_144.gif]  of order  [Graphics:Images/BigOMod_gr_145.gif]  and   [Graphics:Images/BigOMod_gr_146.gif],  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  [Graphics:Images/BigOMod_gr_159.gif]  and  [Graphics:Images/BigOMod_gr_160.gif]  is a sequence with  [Graphics:Images/BigOMod_gr_161.gif].  We say that[Graphics:Images/BigOMod_gr_162.gif]  converges to x with the order of convergence  [Graphics:Images/BigOMod_gr_163.gif],  if there exists a constant  [Graphics:Images/BigOMod_gr_164.gif]  such that

[Graphics:Images/BigOMod_gr_165.gif]   for n sufficiently large.  

This is indicated by writing

[Graphics:Images/BigOMod_gr_167.gif]  with order of convergence [Graphics:Images/BigOMod_gr_168.gif].  


Example 6.  Let  [Graphics:Images/BigOMod_gr_169.gif]  and  [Graphics:Images/BigOMod_gr_170.gif];  then  [Graphics:Images/BigOMod_gr_171.gif]  with a rate of convergence  [Graphics:Images/BigOMod_gr_172.gif].  
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