Fixed Point Iteration

An iterative formula is a formula that uses one term to generate the next term.

For example,

This tells us two things:

means that the first term is

The formula means:

“To find the next term, double the current term and then add

So, if

To find (the second term)​, we substitute (the current term) into the formula.

To find we substitute (the new current term) into the formula.

To find we substitute into the formula.

So, the first four terms are and

For an iterative formula,

means the current term

means the next term

and

is our general iterative formula where is any expression in terms of

Important note: Follow these steps on the calculator to complete the above iterations much faster,

1) Press and then

2) Type in the iterative formula but where you see use the ANS button which in this case looks like ANS

3) Keep pressing

Keep doing this for the required number of iterations. Scroll down to NeilDoesMaths’ YouTube video to see him completing this process in a tougher iteration question.

A root of an equation is a value of that makes

Graphically, a root is where the graph crosses or touches the axis.

For example, if then is a root of the equation This is saying that if you substitute into the equation of the quadratic above, it will give you

Some equations can be solved exactly. For example, many quadratics can be solved by factorising, completing the square or using the quadratic formula.

However, some equations are difficult or impossible to solve neatly using GCSE methods. For these, we often find an approximate solution instead. Fixed point iteration is one method for finding approximate solutions.

Showing that a Root Lies in an Interval

Suppose we want to show that has a root between two values and

If and have opposite signs, then the function has gone from negative to positive, or from positive to negative. If the graph is continuous, this means the graph must have crossed the axis somewhere between and

At GCSE, the functions we use in these questions are usually continuous. For example, polynomials such as are continuous.

At GCSE, we do not need to study continuity in detail. For this topic, it is enough to think of a continuous graph as a graph that can be drawn without lifting your pen off the page.

If we take another look at our quadratic from above where was our root, we can see that the quadratic is negative (below the axis) when and positive (above the axis) at which indicates that some value in-between and gives us In this case, we already know it is at

To show that has a root between and

1) Show that and have opposite signs.

2) Then, state that is continuous, and therefore, there is a root between and

To show that a root is correct to decimal places, check the upper and lower bounds of

We do this because we must consider all the values that round to our root correct to decimal places.

For example, to show that correct to decimal place, check the lower bound and the upper bound

If there is a change in sign between these two values, and is continuous, then the root is correct to decimal place.

So far, in this note, we have learned how to locate the interval in which a root lies within a given interval provided there is a change in sign and that our function is continuous. Fixed point iteration is a method used to find the approximate root to that function.

Suppose we want to solve

Instead of solving the equation directly, we rearrange it into the form We do this because we are trying to solve for after all. It is just that here, does not equal a single number, but it is equal to a function.

Then, we write this as an iterative formula:

This allows us to start with an initial value and repeatedly substitute the answer back into the formula (like we did in Example 1).

For example, if

​and we are given then we substitute to find

Then we substitute to find and so on.

Note: In some iterative sequences, the first term is labelled In fixed point iteration, the starting value is often labelled This just means the value we start with before finding

In fixed point iteration, as we continue to compute further iterations we hope that the values get closer and closer to a fixed point. This fixed point gives us an approximate solution to the original equation.

Graphically, the approximate root to is represented by the intersection of the lines and

In fixed point iteration:

is rearranged into the form

Then we write the iterative formula as

The solution to is the same as the solution to

In Example 2 we proved that the equation has a root between and Let's continue the question to find a root correct to decimal places.