Just been reading Chapter 1.

Am very confused by the example of the unstable algorithm to calculate integer powers of the 'Golden Mean'. I am hoping this is just a little brain short-circuit or something!

We are given an approximation 1.3.3. Then we are given a recurrence relation 1.3.4 to show that we can use a single subtraction rather than repeated multiplications.

Onto the bit I don't understand ...

"Unfortunately ... 1.3.4 has another solution ... and since this undesired solution has magnitude greater than unity, any small admixture of it introduced by roundoff errors will grow exponentially."

Questions: What has this undesired solution got to do with anything?! How can this solution, in particular, be 'admixed' by roundoff errors? What is the relevance of its magnitude being greater than unity if a "small" admixture is introduced?

Once you've stopped laughing, a little help is appreciated! I'm going to meditate on this in the mean time.

Cheers

CR

OK, let's repeat that important part of your message:

..."Unfortunately ... 1.3.4 has another solution ... and since this undesired solution has magnitude greater than unity, any small admixture of it introduced by roundoff errors will grow exponentially."

Questions: What has this undesired solution got to do with anything?! How can this solution, in particular, be 'admixed' by roundoff errors? What is the relevance of its magnitude being greater than unity if a "small" admixture is introduced?...

Now, this is how I understand it:
the recurrence formula used to generate the powers of the golden mean is an example of a so-called difference equation, which can be thought of as a discrete analogue of a differential equation.

If we try to solve this ANALYTICALLY, we find two solutions:

f^n , and

(-f)^n.

(I use f here to represent (1+sqrt(5))/2, since I don't know how to put the "phi" character, the traditional symbol for the golden mean.)

When we implement this formula NUMERICALLY, however, what happens is that our approximation becomes something like

a*(f^n)+b*((-f)^n),

a and b being constants. Ideally, a=1 and b=0, however, roundoff error can swamp the solution by causing b to be a bit (or worse, a lot) greater than zero. This happens because f will be only known to a finite number of digits by the computer, which contributes to the error.

The problem will become worse if you use the incorrect value just generated in the recurrence. That's what they meant by the "exponential increase", since multiplying your erroneous value with another erroneous value (your non-zero b) will increase th error by a factor of it, i.e., exponentially in the long run.

This situation is similar to what happens when you blindly use Runge-Kutta for a particular ODE without checking for stiffness.

Hope this helps. If there is anything wrong or inaccurate in what I said earlier, please correct me.

Jan M. (^_^)