Ch 2: Numerical solution of nonlinear equations in one variable, cont'd

2.3 Functional iteration to a fixed point

We have seen that functional iteration may or may not converge to a fixed point.

Thm 2.3 Contraction Mapping Theorem provides a guarantee of convergence (and a rate) given conditions:

• g maps G into G
• g Lipschitz on G with L < 1 (contraction)

how to show its hypotheses apply? (not always easy directly)

brute force on example i? g(x) = (x^2+6)/5 , G = [1,2.3]

Prop 2.4 - gives an often-more-easily checkable condition on satisfaction of hypotheses of CM Thm on nhood of fixed point.

Definition of order of convergence to a fixed point

Next question: Given convergence, under what conditions on g are we guaranteed convergence with order q?

Proof: use Taylor's theorem to bound |x_k + 1 − z| in terms of |x_k − z|

Meant to show this proof but neglected to (that's why I ended unexpectedly early!):

Newton's method and Theorems 2.3 and 2.4

Newton typically achieves quadratic convergence. The exception is when f'(z)=0.