Numerical Methods with Programming

Section 8.2 Rewriting equations in the fixed-point form

We now have a new method of solving the equations \(f(x)=0\text{:}\) rewrite it as \(g(x)=x\text{,}\) and build a sequence \(x_{n+1} = g(x_n)\text{.}\) If this sequence has a limit, which we recognize by \(|x_{n+1} - x_n|\) being small, then we have a fixed point of \(g\text{,}\) hence a root of \(f\text{.}\) There are multiple ways to rewrite \(f(x)=0\) in the fixed-point form:

• \(\displaystyle f(x) + x = x\)
• \(\displaystyle x - f(x) = x\)
• \(\displaystyle x - 3 f(x)^3 = x\)

and so on. Although the fixed points are the same each case (they are the roots of \(f\)), their classification may be different. For example, consider \(f(x) = x^3 + 4x -5\text{.}\) We know it has a root at \(x=1\text{.}\) If we try to rewrite the equation \(f(x) = 0\) as \(x^3 + 5x - 5 = x\) the fixed point at 1 is repelling because \((x^3+5x -5)' = 3x^2 + 5\) has modulus \(8>1\text{.}\) Another rewrite is \((5-x^3)/4 = x\text{.}\) This one works because the derivative of \((5-x^3)/4\) is \(-3x^2/4\) with absolute value of \(3/4\) at \(x=1\text{.}\) The denominator \(4\) reduced the derivative here.

g = @(x) (2-x^3)/5;
x0 = 0;
max_tries = 1000;
for k = 1:max_tries
    x1 = g(x0);
    if abs(x1-x0) < 100*eps(x0)
        break
    end
    x0 = x1;
end
if k < max_tries
    fprintf('Found x = %.12g after %d steps\n', x1, k);
else
    disp('Failed to converge')
end