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.2599210499 |
| 1.3122938367 |
| 1.3223538191 |
| 1.3242687446 |
| 1.3246326253 |
| 1.3247017485 |
| 1.3247148784 |
| 1.3247173724 |
| 1.3247178462 |
| 1.3247179361 |
| 1.3247179532 |
| 1.3247179564 |
| 1.3247179571 |
| 1.3247179572 |
| 1.3247179572 |
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.
Return to section page.