From jdmccabe@ucdavis.edu Wed Sep 25 06:22:53 1996
Date: Wed, 25 Sep 1996 01:57:08 -0700 (PDT)
From: Jason McCabe <jdmccabe@ucdavis.edu>
X-Sender: ez053489@dale.ucdavis.edu
To: Kermit Rose <rose@garnet.acns.fsu.edu>
Subject: Re: qudradic equations


Well, before I explain what Aitken Acceleration is let me preface it with
an apology.  Aitken Acceleration is really not a method to find the roots
of a polynomial unto itself; it is a component of another method: fixed
point iteration.  It would appear that I jumped too far ahead of myself
and claimed otherwise and for this I am sorry.  That said let me explain.

In fixed point iteration one simply takes a function f(x) and rearranges
it to look like x = g(x).  For example:

Let f(x) = x^2 - 2x - 3 = 0 (We wish to find the roots of this quadratic
so we set it equal to zero)

One of the possible ways to rearrange this would be:

x = 3/(x - 2) <------------------ x = g(x)

Now what we do is make an initial guess at what we think a possible root
of f might be, say x = 4 (of course we actually know what the roots are
since f can be factored easily, but we pretend we don't for illustration).
We then plug x = 4 into the right hand side of the equation above which
yields 3/2.  We then use this as a better "guess" and repeat the procedure
until it converges to a root.  Only eight iterations are necessary for
this polynomial and the results are:

x0 = 4

x1 = 1.5

x2 = -6

x3 = -0.375

x4 = -1.263158

x5 = -0.919355

x6 = -1.02762

x7 = -0.990876

x8 = -1.00305

So that you can see we are getting closer and closer to the correct root
of -1.

Now, when doing numerical analysis it is important to examine the nature
of the error at each step.  It is assumed that with fixed-point iteration
the errors at each step are proportional to the previous error.  Remember
that this is only an assumption and should not be regarded as fact.
Nevertheless, the assumption has proven to work here as well as with other
methods.  If we take this assumption and take it to be true then we can,
with some derivation, come up with a method to arrive at the proper answer
faster than was demonstrated above.  We might be able to arrive at the
answer of -1 within 5 iterations or maybe even 4, instead of eight.  I
won't go over the details of this derivation, but what I have described 
is known as, you guessed it:  Aitken Acceleration.

Hope this helps a little.

Jason