NUMERICAL METHODS
1. Introduction
We are used to having exact solutions for equations. For example
/ has the solution // has the solution /
However, many equations, such as
are not easily solved, or are impossible to solve, exactly. Using numerical methods, we can get a good approximation to the solution of this equation, but not an exact answer.
2. Change of Sign
We can locate approximate values for the roots of the equation by seeing where changes sign (from negative to positive or vice versa).
The graph above shows there is a change in sign of as x moves form a to b. The solution of the equation therefore lies in the range .
Consider our equation
We begin with a table of values.
x / –3 / –2 / –1 / 0 / 1 / 2 / 3 / 4/ –31 / –1 / 11 / 11 / 5 / –1 / –1 / 11
We see that there are three intervals containing roots, namely [–2, –1], [1, 2] and [3, 4].
If we want to locate the root in the interval [3, 4], we can draw up another table.
x / 3 / 3.1 / 3.2 / 3.3 / 3.4 / 3.5 / 3.6 / 3.7 / 3.8 / 3.9 / 4/ –1 / –0.44 / 0.25 / 1.07 / 2.02 / 3.13 / 4.38 / 5.78 / 7.35 / 9.09 / 11
The root is now between 3.1 and 3.2. We can of course continue until we have the root to the desired accuracy.
This method has the advantage that rather than giving us an estimate for the solution, it tells us the interval within which the solution lies : estimates without a measure of their accuracy are valueless.
The disadvantages are that the method is very slow, and that it may miss one or more roots. Roots will also be missed when a graph touches rather than crosses the x-axis, or just dips across the axis for a short range of x values. In the diagram below, and have the same sign, so there would be no suspicion of a root between them.
A discontinuity in the function may yield a change of sign and lead us to suspect there is a root, when in fact there is none.
Example1:Show that the equation has a root in the interval [2, 3].
There is a change of sign, and hence a root lies in the interval [2, 3].
Example 2 : Sketch the graphs of and on the same axes. Hence determine the number of roots of the equation . Show further that there is a root in the interval [1, 2].
We can see from the graph that there is one root, and it is clear that this lies between 1 and 2. we can prove this using change of sign, but first we must rearrange the equation so it is of the form .
There is a change of sign, andhence a root lies in the interval [1, 2].
C3 p44 Ex 4A
3. Approximate Solutions of Equations by Iteration
This is the process of repeating a given procedure until an answer is found to the desired accuracy.
Example1:Perform the following iteration until an answer is obtained correct to three decimal places.
What equation was this iteration intended to solve?
Important note : to perform this iteration on a graphic calculator, type in the following...
1 ENTER(this makes )
1 + (1 ÷ Ans) ENTER(this uses the previous number to get the next one)
ENTER
ENTER
ENTER etc.(this generates further iterates)
If ENTER is now repeatedly pressed, the solution can be found to as many decimal places as can be held on the calculator.
The iteration process yields the following...
Because the sequence is converging in an oscillatory fashion, it is sufficient to have two consecutive iterates which agree to 3 d.p. So to three decimal places, the solution is 1.618.
To find the equation, we recognise that the iterates get closer and closer to the solution, which we shall x. In other words, for large n we have . Therefore we can write
Using the quadratic formula shows that our iterated answer is indeed one of the solutions.
Example2:Perform the following iteration until an answer is obtained correct to two decimal places.
What equation was this iteration intended to solve?
At this stage we have two consecutive iterates which agree to 2 decimal places, namely 1·87. However, as the sequence is converging monotonically, it is likely that the actual answer will be below this. (Note that this is not a problem with oscillatory convergence). Continuing,
These iterates make it seem very likely that the root, to 2 decimal places, is 1.86. We can check this using the change of sign method. To do this, we first find the equation we are solving...
We believe the root of our equation is 1.86 to 2 decimal places. This means the root lies in the interval [1.855, 1.865]. Using the change of sign method to check this...
There is a change of sign, so the root is in the interval [1.855, 1.865].. So to two decimal places, the root is 1.86.
Notice that this is a cubic equation, for which there is no simple formula (unlike quadratic equations). Therefore numerical methods are needed to solve it.
Example3:Show that the equation
can be rearranged into the the form
where the constants a, b, and c are to be found. Hence solve the equation to three decimal places.
So, and . Using the iteration …
At this stage we suspect the root is 2.262 to 3 decimal places. Using the change of sign method,
There is a change of sign, and so the root lies in [2.2615, 2.2625], and is therefore 2.262 to 3 d.p.
Example4:Find and perform some different iterations for the equation . Comment briefly on the effectiveness of each iteration.
We need to find ways of making x the ‘subject’ of the equation. Here are six possibilities!
1. / / 3. / / 5. /2. / / 4. / / 6. /
We will try each method with first term. A spreadsheet is very useful here!
iterate / / / / / // 1 / 1 / 1 / 1 / 1 / 1
/ 2 / 1.73205081 / 1.66666667 / 3 / 1.5 / 3
/ 0.5 / 1.23931367 / 1.36363636 / -0.33333333 / 1.44444444 / -7
/ 2.375 / 1.58788307 / 1.48648649 / -17 / 1.45 / -37
/ -0.32031250 / 1.35064202 / 1.43410853 / -2.29411765 / 1.44943820 / -1327
/ 2.44869995 / 1.51615170 / 1.45598194 / -4.17948718 / 1.44949495 / -1759597
/ -0.49806573 / 1.40274609 / 1.44676682 / -3.19631902 / 1.44948922 / -3.09618× 1012
/ 2.37596527 / 1.48138712 / 1.45063483 / -3.56429942 / 1.44948980 / -9.58633× 1024
/ -0.32260547 / 1.42731417 / 1.44900873 / -3.40280022 / 1.44948974 / -9.18977× 1049
/ 2.44796285 / 1.46470873 / 1.44969189 / -3.46937807 / 1.44948974 / -8.4452× 1099
/ -0.49626107 / 1.43895189 / 1.44940480 / -3.44118050 / 1.44948974 / -7.1321× 10199
We see that method 1 does not converge, and is therefore of no use in solving the equation (it seems that it is becoming periodic, with period 4). Method 2 converges to the solution very slowly, and in an oscillatory fashion. Method 3 converges to the solution more rapidly as does method 4, although this approaches the other solution of the quadratic. Method 5 has the most rapid convergence, and method 6 diverges rapidly to negative infinity.
We can interpret fixed point iteration graphically. Suppose we are using the iteration formula
Successive iterates may look like this...
Notice how we find , and assign this value to by going across to the line and then down. Then we find, and assign this value to . This process continues as the iterates converge to the value of x for which, and this is the solution of our equation.
Activity1:Do the Fixed Point Iteration worksheet. This shows graphically why fixed point iteration sometimes succeeds, and sometimes fails. In general, the condition for convergence is that at the point of intersection of and , .
Now illustrate all the methods in Example 4 using Autograph. Plot the graphs of and , select both, right-click and select ‘iteration’ from the menu. Choose to be 1 (or whatever value you prefer), and click the forward arrow in the dialogue box. Incidentally, you get a fantastic staircase using this iteration…
Set each axis from 0.9 to 1.5.
C3 p50 Ex4B Topic Review : Numerical Methods