If g(x) and g'(x) are continuous on an interval containing a root of the equation g(x) = x, and if |g'(x)| < 1 for all x in the interval then the series x_n+1 = g(x_n) will converge to the root.

However we are not restiricted to this choice of g.
If c is a root of f, then f (c) = 0. We can manipulate f algebraicaly to produce a function g such that g(c) = c (c is a fixed point of g).

For example if f (x) = x² - x - 2, then by solving f (x) = 0 in different ways, the following are all possible choices for g(x):

• g(x) = x² - 2,
• g(x) = sqrt(2 + x),
• g(x) = 1 + 2/x.
• g(x) = x - (x² - x - 2).
• g(x) = x - (x² - x - 2)/(2x - 1).

Provided that |g'(x)| < 1 the sequence generated by

The Algorithm

Methodological Error

The condition that |g'(x)| < 1 can be difficult to show, and even more difficult to automate.
A much more useful technique is to check if the difference of successive approximations is converging.
Thus we test |a_n+1 - a_n| on each iteration.
If |a₃ - a₂| > |a₂ - a₁| we should abort the iteration.

6. For each of the following functions, f provide 3 possible alternatives for an equivalent fixed point function, g. In each case find g'(x) and find the interval on which it is less than 1. [Hint: try the solve function with a D(g)(x) < 1.]
   1. x^2 - 3*x + 1
   2. sin(x)
   3. exp(x)-3*x^2
7. Implement the fixed point algorithm and use it to find the roots of the the functions in the previous question (where possible). If it is not possible to use the fixed point method tio find a particular root, explain why not.
8. Use your fixed point algorithm from the last question to solve the equation g(x) = x, where g(x) is given by the following:
   1. x^6 + x^4 - 3*x^5 + 5*x^3 - 6*x^2 + 3*x - 1 (both roots).
   2. tan(x) - x (principal root).
   3. e^x - 2x.
   4. sin(x) - x^2 + x (both roots).

Up to Main Lab Page

Next Lesson - Procedures

Previous Lesson - Newton's Method

Top of this Lesson