Section 8.3 The speed of convergence of fixed-point iteration
Near an attracting fixed point with \(0 \lt |g'(x^*)| \lt 1\text{,}\) the convergence is linear in the sense that the error at the next step is about \(|g'(x^*)|\) times the error of the previous step. But if \(g'(x^*)=0\) (meaning \(x_0\) is a superattractive fixed point), then the rate of convergence is extremely fast. Indeed, Taylor's formula says that \(|g(x)-g(x^*)|\) is bounded by a constant multiple of \(|x-x^*|^2\text{,}\) where the constant depends on the value of the second derivative \(f''(x^*)\text{.}\) This rate of convergence is called quadratic because at each step, the error size gets squared (and multiplied by a constant).
Compare two functions: \(g_1(x) = \sqrt{x}\) and \(g_2(x) = (x+1/x)/2\text{.}\) Both have a fixed point \(x^*=1\text{.}\) Since \(|g_1'(1)| = 1/2\) and \(|g_2'(1)| = 0\text{,}\) the point 1 is attracting for \(g_1\) and super-attracting for \(g_1\text{.}\) Let's see how quickly the iteration converges to the fixed point, starting from 5 for example.
g = @(x) sqrt(x);
x = 5;
for k = 1:10
x = g(x);
fprintf('After %d steps got %.15g\n', k, x)
end
The numbers approach 1 but not very quickly.
After 1 steps got 2.23606797749979 After 2 steps got 1.49534878122122 After 3 steps got 1.22284454499385 After 4 steps got 1.10582301703024 After 5 steps got 1.05158119849598 After 6 steps got 1.02546633220988 After 7 steps got 1.01265311543977
And so on: each error is about half of the previous, indicating linear speed of convergence. After 10 steps we are still more than 0.001 away from the fixed point. In contrast, running the above code with g = @(x) (x+1/x)/2; results in much faster convergence.
After 1 steps got 2.6 After 2 steps got 1.49230769230769 After 3 steps got 1.0812053925456 After 4 steps got 1.00304952038898 After 5 steps got 1.00000463565079 After 6 steps got 1.00000000001074 After 7 steps got 1
After just 7 steps of iteration, the value is so close to 1 that it becomes equal to 1, due to round-off involved.