Mathematics 371 – Numerical Analysis Discussion 1 – Rates of Convergence September 5, 2001

Background

Many numerical algorithms are iterative – that is, they involve executing some sequence of computations repeatedly using the results of the previous stage to derive the result of the current stage in the process. In the nth stage, we usually have a current approximation to the quantity we are trying to compute. If we call that current approximation x_{n} and the desired quantity x^{⋆}, then in principle (i.e. if we never stopped the process), we would generate a sequence of approximations x_{n} converging to x^{⋆} as n → ∞. In this situation, there is a notion of rate of convergence that can be used to describe how fast x_{n} approaches x^{⋆}:

We say x_{n} = x^{⋆} + O(n^{−p}), or x_{n} → x^{⋆} with rate of convergence O(n^{−p}), if there is a positive constant K and n_{0} ≥ 1 such that |x_{n} − x^{⋆}| ≤ K · \frac{1}{n^{p}} for all n ≥ n_{0}.

Discussion Questions

A)

1) The two sequences

x_{n} = 1 + \frac{1}{10n} y_{n} = 1 + \frac{(−1)^{n}}{n^{2}}

both approach x^{⋆} = 1 as n → ∞. Intuitively, which approaches its limit faster? Explain by analyzing |x_{n} − 1| and |y_{n} − 1|.

2) What is the largest power p such that x_{n} = 1 + O(n^{−p})? Same question for y_{n}? How does this relate to your answer to part 1?

B) (One not-so-intuitive feature of our definition) Let 0 < q < p and assume that x_{n} = x^{⋆} + O(n^{−p}). Then show that x_{n} = x^{⋆} + O(n^{−q}) as well.

C) Suppose x_{n} = f(\frac{1}{n}) is produced by evaluating some differentiable function f. How could you use properties of that function to analyze the rate of convergence of x_{n}? Use your idea to determine the rate of convergence of each of the following sequences.

1) lim_{n→∞} sin (\frac{1}{n}) = 0

2) lim_{n→∞} n sin (\frac{1}{n}) = 1 (first show that this sequence does tend to 1 as n → ∞)

3) lim_{n→∞}(ln(n + 1) − ln(n)) = 0 (first show that this sequence does tend to 0 as n → ∞)

4) lim_{n→∞} n(1 − e^{1/n}) (what is the limit?)

D) In some very good cases, we will be able to produce numerical algorithms that converge to their results with a rate that is O(n^{−p}) for all p ≥ 1 (no matter how large). This means we have a very fast rate of convergence.

1) For instance show that x_{n} = 10^{−2^{n}} → 0 has this property: 10^{−2^{n}} = O(n^{−p}) for all p ≥ 1.

2) A sequence x_{n} → x^{⋆} is said to converge quadratically (respectively cubically) to its limit if there exists a positive constant K such that

lim_{n→∞} \frac{|x_{n+1} − x^{⋆}|}{|x_{n} − x^{⋆}|^{2}} = K,

respectively

lim_{n→∞} \frac{|x_{n+1} − x^{⋆}|}{|x_{n} − x^{⋆}|^{3}} = K.

(In intuitive terms, quadratic convergence, for instance, means that for large n,

|x_{n+1} − x^{⋆}| ≐ K|x_{n} − x^{⋆}|^{2}.

Show that x_{n} = 10^{−2^{n}} → 0 has quadratic convergence.

3) Construct a sequence that converges to 0 cubically.

Assignment

Write-ups due Monday, September 10.