Numerical Analysis

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

Class 17: Monday October 14

SUMMARY Analyzing Iterative Methods READING Burden & Faires, 78–86

Asymptotic Rates of Convergence 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|^{α}} = λ

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. How is this definition different from “big oh” and “little oh”?

We have considered iterative methods in this class so far... Write them down below with their corresponding iterative step p_{n} = g(p_{n−1})

Let’s rank these in order of how fast they converge to the root, i.e. in asymptotic order.

\underline{Question} How can we prove this order? Can we determine the order of these methods analytically? can we do it experimentally? How???

Summary 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 Derive the error formula for the bisection method and write it below. In other words, get an expression for e_{n+1} in terms of e_{n} and or n.

Therefore, Bisection is a  method, with λ =  and α =

Fixed Point Iteration We shall derive the asymptotic rate 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} therefore p_{n+1} = g(p − e_{n}) =

Picard Iteration is a method with α = Newton’s Method In a similar fashion, we shall derive the asymptotic rate of convergence for Newton’s Method and fill-in the table below

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}|