# Math 373 Fall 2000 Solution of exercise

Programming iteration and Steffensen's acceleration in a spreadsheet leads to the following results. The equation we are solving is

f(x) = x3 - x - 1 = 0

on the interval from 1 (where the value of the function is -1) to 2 (where the value of the function is +5). In order to have an iteration that converges to the root, it is necessary to write the equation in the form x = g(x), where g is a function whose derivative is strictly between -1 and 1 on (at least a large subinterval of) the given interval. This rules out most of the choices that can be easily computed. One choice that is allowed is
g(x) = (x + 1)1/3

Here is a list of the iterates starting from 1.
 1 1.25992 1.31229 1.32235 1.32427 1.32463 1.3247 1.32471 1.32472 1.32472 1.32472 1.32472 1.32472 1.32472 1.32472 1.32472
The derivative of g is about 0.2 so it takes 14 steps to get 10 decimal place accuracy.

Now apply Steffensen acceleration to the same iteration. The first three steps are the same, but we follow the text in writing them in a row rather than a column. Each new row begins with the result of the extrapolation formula (essentially formula (2.11) which appears as the third expression of Step 3 of Algorithm 2.6). Knowing the answer, we see that the first extrapolation is accurate to three decimal places and the second to ten decimal places. Since the algorithm has quadratic convergence, the third extrapolation could be expected to be accurate to twenty places if we took the trouble to compute everything that accurately. In particular, the stopping condition in Step 4 is very conservative, since it means that the previous extrapolation was already good enough.

p0 p1 p2
jump 1 1.2599210499 1.3122938367
jump 1.3255096004 1.3248683102 1.3247465157
jump 1.3247179612 1.3247179580 1.3247179574
jump 1.3247179572 1.3247179572
One iteration in the last row shows that the desired accuracy has been reached. At this accuracy, there does not seem to be much of a saving since we have computed 11 values of the function in the Steffensen calculation. However, if all values were computed to sufficient accuracy, it would take another 14 computations to get 20 place accuracy with the linearly convergent iteration, but the 20 place versions of the numbers in the last row of the Steffensen version are 1.32471 79572 44746 02606 and 1.32471 79572 44746 02598, so we almost have the full accuracy already. Finishing this row and doing one more jump will give the required accuracy with only two more computations. I did the computations to 30 decimal places in Maple and the value after the jump was a fixed point to that accuracy. Repeating the calculation using 50 place accuracy revealed that the error was less than 10-40. Actually, Steffensen's acceleration, like Newton's method is self-correcting, so the same effect could have been found by using the last value as starting value after increasing the number of digits instead of repeating the whole calculation.