Big "O" Truncation Error

Big "O" Truncation Error

The 0^th Order of Approximation

Clearly, the sequencesandare 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 functionis said to be big Oh of,denoted,if there exist constantsandsuch that

whenever.

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.Letandbe two sequences.The sequenceis said to be of order big Oh of, denoted,if there existandNsuch that

whenever.

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

Definition 3.Assume thatis approximated by the functionand that there exist a real constantand a positive integer n so that

for sufficiently small h.
We say thatapproximateswith order of approximationandwrite

.

When this relation is rewritten in the form,we see that the notationstands 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 thatand,and.Then

(i),

(ii),

(iii),

provided that.

It is instructive to considerto 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 thatconverges to zero as h approaches zero, as expressed in the relationship



for sufficiently smallh.Hence the notationstands in place of the quantity, whereMis a constant or behaves like a constant.

Theorem (Taylor polynomial).

Assume that the functionand its derivativesare all continuous on.Ifbothandlie in the interval,andthen

,

is the n-th degree Taylor polynomial expansion ofabout.The Taylor polynomial of degree nis


and
.

The integral form of the remainder is

,

and Lagrange's formula for the remainder is



where depends on and lies somewhere between.

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

(i),

(ii)where,

(iii)where.

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 thatandis a sequence with.We say thatconverges to x with the order of convergence,if there exists a constantsuch that

for n sufficiently large.

This is indicated by writing


or
with order of convergence .

Example.Letand;thenwith a rate of convergence.
Solution.