Rewriting equations in the fixed-point form

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.

🔗

Example 8.2.1. Rewrite and solve by fixed-point iteration.

Solve the equation \(x^3 + 5x = 2\) by the fixed-point iteration method.

🔗

Solution.

The function \(x^3 + 5x\) is increasing from 0 to 6 on the interval \([0, 1]\text{.}\) Therefore, the equation has a solution in this interval. Following the idea of the previous paragraph, rewrite it as \((2-x^3)/5 = x\text{.}\) This means \(g(x) = (2-x^3)/5\) and \(g'(x) = -3x^2/5\text{.}\) Note this \(|g'| \lt 1\) on \([0, 1]\) which guarantees that the fixed point is attracting. Here is the code to find it.

🔗

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

The reason for using a for loop is to set a limit for the number of attempts (1000). The loop ends sooner if the values of x essentially stop changing. We do not need separate variables for every element of the sequence: x0 and x1 keep being reused for “old” and “new” x-values. The output is “Found x = 0.388291441005”.

🔗

Prev Top Next