Fixed Point Iteration
Neil Trivedi
Teacher
Contents
Locating Roots
Finding the roots to a function is to simply find the values of , such that . Another way of thinking about this is to find where the function crosses the axis.
We have learned techniques such as the quadratic formula to find the roots of a quadratic and have found the roots to numerous trigonometric functions such as .
However, we are sometimes given functions where solving becomes tedious such as cubic equations and many other non-linear functions.
For these, we have numerous techniques to find approximate solutions such as fixed point iteration (from GCSE) and the Newton-Raphson method (more on this in the Newton-Raphson method note).
Let’s take the function as an example.
The equation has three real roots, as we can see in the diagram, but calculating them exactly is not easy.
From the graph, we can observe that the leftmost root lies between and , the middle root lies between and , and the rightmost root lies between and .
We can also observe from the graph that the sign of changes from positive to negative or vice versa before and after the root. For example, at the leftmost root, between and , the values to the left of the root are negative (in red) and the values to the right of the root are positive (in green), hence the change in sign from negative to positive. This then implies that a root, when , must exist within that interval of moving from negative to positive.
Also, the function is continuous (which essentially means you do not need to take your pen off the page to draw the graph like you have to with ).
Here are the two conditions that need to be met when showing that a root lies within an interval.
1) A change in sign in within the interval. It can go from positive to negative or negative to positive.
2) must be continuous within the interval.
Fixed Point Iteration
In the process of fixed point iteration, we rearrange into the form and we use to generate solutions for .
Let’s revisit . When , we can rearrange it in the form , for which . Here are two graphs, with the first one showing and the second one showing the line with equation and the curve with equation .
Example 1:
Let .
a) Show that has a root between and .
Single Step: Substitute and into and check that the sign changes.
In the interval between and , there is a change in sign and is continuous so has a root between and .
b) Show that can be written in the form .
Single Step: Rearrange the equation to isolate one of the ’s.
Moving the and over to the other side,
Cube rooting both sides,
c) By writing b) in the form and using , find the root correct to decimal places.
Step 1: Rewrite the function obtained in part (b), replacing with .
This is known as the iterative formula and we find the next value, , by substituting the previous value, , into the formula.
Step 2: Starting with , substitute values of into the iterative formula.
and agree to decimal places.
Therefore, a root of is to decimal places.
d) Verify that your answer to part c) is a root of .
Single Step: Find the upper and lower bounds of our answer to part c), substitute them into and check for a change in sign.
correct to decimal places so the upper and lower bounds will be and , respectively.
Substituting them into ,
There is a change in sign and is continuous between and so we have verified that the root is to decimal places.
Note: We can find the other roots by rearranging in different ways to get it in the form and then applying the fixed point iteration process.
No answer provided.
Iterative Diagrams – Staircase and Cobweb Diagrams
Iterative diagrams (staircase or cobweb) provide a graphical illustration of the fixed point iteration process. They help us visualise how the sequence defined by behaves and whether it converges towards a root or diverges away from the root.
Consider the previous example where . We rearranged it to give:
and using the iterative formula, we found a root to be to decimal places.
We now visualise what is happening during the fixed point iteration process. Firstly, below are the graphs of and and , which represents our root.
As a reminder, we had the following iterations when finding :
When constructing the iterative diagram, we begin by reading off from the graph. From this point, we move vertically upwards to the curve with equation . Then, we move horizontally to the line with equation . The point at which we meet the line will be our . We then repeat the process, moving vertically to the curve and horizontally to the line to obtain and so on.
Here, we get a staircase (indicated by the red arrows). We also see that our iterations are converging towards .
Generally, when we draw iterative diagrams, we follow this sequence:
Up\down to Left\right to Up\down to Left\right to
the curve to get the curve to get
Example 2:
Solve by first writing it in the form and using , show using a cobweb diagram how our iterations approach the root .
Step 1: Rearrange the equation to get our iterative formula.
Adding to both sides,
Factorising the LHS,
Dividing both sides by , we get
Step 2: Draw a cobweb diagram, showing the iterations.
Firstly, here are the graphs of and .
Note: These sketches will be provided in the exam.
Here, we start from . Then, we move vertically downwards to the curve with equation , then move horizontally towards the line with equation to get our . Then, we repeat this process with more iterations, and a cobweb will be formed.
We can see from our cobweb diagram that the iterations converge to the root .
No answer provided.
In iterative diagrams, whether staircase or cobweb, convergence towards or divergence away from a root can be determined by the gradient of the curve at the point where it intersects the line with equation .
In general, let α be the point at which and let , where is the gradient of the curve at the point of intersection.
Challenging Question