MATH/APPM 4650
Class notes, February 2
Error analysis for iterative methods
Most of today's notes including all examples will be on the board, but here are the basic concepts.
Definition: Suppose xn is a sequence converging to a limit p, and the error in the nth term is en = xn - p. If
limn→∞ | en/enα | = λ
for some numbers α and λ where 0<λ<∞, then α is called the order of convergence and λ is called the asymptotic error constant.
We can also define this without the absolute values, which would allow us to know the sign of the error (which is useful for getting upper or lower bounds on the approximation). The absolute values are more standard though.
- If α = 1, then we need λ<1 for convergence.
- If α > 1, then it doesn't matter what λ is; the sequence will converge as long as the initial error is sufficiently small. (How small we need it to be depends on the situation.)
- If α = 1, the sequence converges linearly. If α = 2, the sequence converges quadratically.
If a sequence is defined by the recursion relation
xn+1 = g(xn)
for some smooth function g, then if it converges to p, we know that g(p) = p.
The error term can always be expressed as a Taylor series based at the fixed point p.
en+1 = g'(p) en + g''(p)/2 en2 + g'''(p)/6 en3 + ...
Hence we can say:
- If g'(p) ≠ 0 then α = 1 and λ = | g'(p) |.
- If g''(p) = 0 but g''(p) ≠ 0 then α = 2 and λ = | g''(p)/2 |.
- etc.
Example:
If g(x) = x - f(x)/f'(x), i.e., Newton's method, then the convergence is quadratic if f'(p) ≠ 0, but it can degenerate to only linear if f'(p) = 0.
Example:
For the secant method, the convergence has order α = (1+√5)/2 = 1.62...