Numerical Analysis

Math 370  MWF 2:30-3:25
Spring 1997  127 Fowler

(02.10.97) \underline{Error Analysis of Iterative Methods} If we have a sequence of approximations {p_{n}} which converges to p and there exist positive constants α and λ so that

lim_{n→∞} \frac{|p_{n+1} − p|}{|p_{n} − p|^{α}} = λ = lim_{n→∞} \frac{|e_{n+1}|}{|e_{n}|^{α}}

then the sequence is said to converge to p with order α, with an asymptotic error constant λ. The method is said to be an “α order” method.

Recall that we define the error at each iterative step to be e_{n} = p − p_{n}

In other words the iterative method is said to be of order α if one can show a relationship like |e_{n+1}| ≈ λ|e_{n}|^{α}

\underline{Example} Consider the two sequences p_{n} and q_{n} which both to converge to zero. However, p_{n} converges linearly, while q_{n} converges quadratically.

Let’s assume that the two sequences have the same asymptotic error constant of λ = 0.5 and p_{0} = 1. Use your calculator to generate the first 6 or so elements of each sequence and record these in the table below.

You should be able to come up with a formula which relates the n-th iterate to the initial guess (zeroth iterate) for both p_{n} and q_{n} and makes filling out the table easier....

Iterate

Linear Convergence Quadratic Convergence

n  p_{n} =  q_{n} =

Do you think it is a “big deal” whether a method is linearly convergent versus quadratically convergent?

Bisection Method Recall the error formula for the bisection method and write it below:

Bisection is a  method, with λ =  and α =

Fixed Point Iteration We shall derive the order of convergence for Functional Iteration. p_{n+1} = g(p_{n}) and e_{n+1} = p − p_{n+1} and e_{n} = p − p_{n} therefor p_{n+1} = g(p − e_{n}) =

Picard Iteration is a method with α = Newton’s Method In a similar fashion, we shall derive the order of convergence for Newton’s Method

Method Order of Convergence

Error Formula

Bisection

False Position

1.442

Secant  \frac{1+\sqrt{5}}{2} ≈ 1.618

Newton’s

Picard

NOTE: The above only apply for simple roots (i.e. a root of multiplicity 1). Definition A root r of an equation f(r) = 0 has multiplicity m if and only if 0 = f(r) = f′(r) = ⋯ = f^{(m−1)}(r) = 0 but f^{(m)}(r) ≠ 0.

For roots of multiplicity m > 1 Newton’s Method has the relationship that |e_{n+1}| ≈ \frac{M − 1}{M}|e_{n}|