Fixed Point Iteration

The goal of fixed point iteration is to find a root for f(x). To do this we convert the equation f(x) = 0 into the form of x = g(x)
• A point, p, is called a fixed point for a given function g if g(p) = p
• Let the initial guess be p₀ $$p_{i+1} = g(p_i)$$

Choosing a g(x) that will converge

Lets take the example of f(x) = x³ + x - 4
$$ 0 = x^3 + x - 4$$ $$ x = -x^3 + 4$$ $$ g_1 = -x^3 + 4$$ $$ x^3 = - x + 4$$ $$ x = ( - x + 4 )^{1/3} $$ $$ g_2 = \sqrt[3]( - x + 4 )$$ $$ x^3 = - x + 4$$ $$ x^2 = - 1 + 4/x$$ $$ x = \sqrt{4/x - 1}$$ $$ g_3 = \sqrt{4/x - 1}$$

So we have found 3 possible functions for g(x), there are numerous more, but let's start with these and test which converges the fastest.
• The end condition is when g(p) - p = 0 or |g(p) - p| < tolerance $$ g_1 = -x^3 + 4$$

You probably noticed that by using g₁(x) it will not converge
$$ g_2 = \sqrt[3]( - x + 4 )$$

$$ g_3 = \sqrt{4/x - 1}$$

We can see that it really matters which g(x) you use for finding a fixed point. We can also see that none of these choices converged as fast as Newton's Method.

Code for C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

// Fixed Point Iteration
// Implementation for c++
// Code by Austin Wimberley

#include <bits/stdc++.h>
using namespace std;

static int counter = 0;

// Chosen function g(x) such that rearranging f(x) = 0
// gets x = g(x)
// MODIFY HERE TO IMPLEMENT FOR YOUR FUNCTION
double g(double x) {
    double ans = pow((4/x - 1) , 0.5);
    return ans;
}

double applyFormula(double p, double const TOL) {
    while (abs(g(p) - p) > TOL && counter < 100) {
        printf("%4d\t%10f\n", counter++, p);
        p = g(p);
    }
    return p;
}

// Driver Function
int main()
{
    // MODIFY HERE FOR INITIAL POINT AND TOLERANCE
    double p0 = 1;
    double const TOL = 0.00001;
    double ans = applyFormula(p0, TOL);
    cout << "\nRoot found at " << ans;
    return 0;
}