Numerical Analysis

Math 370 Fall 1998  MWF 11:30am - 12:25pm
\begin{matrix}c \\ ◯ \end{matrix}1998 Ron Buckmire  Fowler 127

Class 6: Wednesday September 16

SUMMARY Orders of Convergence of a Sequence CURRENT READING Burden & Faires (6th edition,) pages 36-37

Convergence of a Sequence

In a large number of numerical problems we will get a sequence of approximate answers to the single real number which is the exact solution of the problem we are looking at (e.g., a definite integral, a particular value of a solution to an initial value problem, etc). We often write this sequence as x_{1}, x_{2}, x_{3}, … and the limit as L or x_{∞} and denote this by

lim_{n→∞} x_{n} = L

The formal definition of the above limit can be written as:

We are interested in looking at rates of convergence of sequences.

Definition

Suppose we know that a sequence {β_{n}} converges to zero and {α_{n}} converges to α. The sequence {α_{n}} is said to converge to α at the rate of convergence O(β_{n}) if

lim_{n→∞} \frac{|α_{n}|}{|β_{n}|} = K, where 0 < K < ∞

This is often written as α_{n} = α + O(β_{n})

We read this as:

In addition, we say that {α_{n}} is o(β_{n}) if

lim_{n→∞} \frac{|α_{n}|}{|β_{n}|} = 0

and that {α_{n}} is equivalent to {β_{n}} (this is written α_{n} ∼ β_{n}) if

lim_{n→∞} \frac{|α_{n}|}{|β_{n}|} = 1

The typical orders of convergence that we are interested in are linear, superlinear and quadratic orders of convergence.

Can you write these orders using “big oh” and “little oh” notation?

\underline{Example} We use this knowledge about rates of convergence to compare competing algorithms. Suppose {A_{n}} and {B_{n}} are two algorithms described by

A_{n} = \frac{(n + 1)}{n}, B_{n} = \frac{(n + 3)}{n^{2}}

What does A_{n} converge to? What does B_{n} converge to?

Which of the sequences converges faster? (How can we find out?)

To help answer this question, try computing their rates of convergence relative to the sequences γ_{n} = 1/n and γ̃_{n} = 1/n^{2}

\underline{Groupwork} Find the rates of convergence of the following sequences:

lim_{n→∞} \frac{7n + 2}{n^{2}}  =  lim_{n→∞} \frac{n^{2}}{n^{3}} =  lim_{n→∞} \frac{n^{3}}{n^{2}} =

lim_{n→∞} \frac{(7n + 2)/n^{2}}{1/n^{2}} =  lim_{n→∞} \frac{(7n + 2)/n^{2}}{1/n} =  lim_{n→∞} \frac{(7n + 2)/n^{2}}{n} =

Rates of convergence

Here is a summary of the information about relative rates of convergence of sequences.

lim_{n→∞} \frac{|α_{n}|}{|β_{n}|} = \{ \begin{matrix}0 & means α_{n} = α + o(β_{n}) \\ 1 & means α_{n} ∼ β_{n} \\ 0 < K < ∞ & means α_{n} = α + O(β_{n}) \\ ∞ & means β_{n} = β + o(α_{n}) \end{matrix}

Extension to Functions The “big oh” and “little oh” notation can also be extended to describe the rate at which functions converge to values.

If we know that lim_{h→0} F (h) = L and and lim_{h→0} G(h) = 0 If a positive constant K exists with

|F (h) − L| ≤ KG(h), mboxforsufficientlysmallh

then we write F (h) = L + O(G(h))

This can also be computed using the idea that F (h) = L + O(G(h)) if

lim_{h→0} \frac{|F (h) − L|}{|G(h)|} = K

where K is some positive, finite constant. \underline{Example}

Show that cos(h) + \frac{h^{2}}{2} = 1 + O(h^{4})

What is the rate of convergence of sin(h^{3}) as h → 0?