LECTURE NOTES ON REAL ROOT-FINDING
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      for  Math. 128 A/B

        Prof. W. Kahan
      Math. Dept.,  and 
  E.E. & Computer Science Dept.
   Univ. of Calif. @ Berkeley
        4 March 1998

NOT YET READY FOR DISTRIBUTION
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Abstract: 
These course notes concern the solution of one real equation  f(z) = 0  
for one real root  z ,  also called a real  zero  z  of function  f(x) .  
They  supplement,  not  supplant,  textbooks and deal mathematically 
with troublesome practical details not discussed in my article about a 
calculator's  [SOLVE]  key in the  Hewlett-Packard Journal 30 #12 (Dec. 
1979) pp. 20-26.  ( See  http://www.cs.berkeley.edu/~wkahan/Math128/
SOLVEkey.pdf .)  It should be read first;  it offers easy-to-read 
advice about real root-finding in general to anyone who wishes merely 
to use a root-finder to solve an equation in hand.  These course notes 
are harder to read;  intended for the would-be designer of a root-
finder,  they exercise what undergraduates may learn about  Real 
Analysis  from texts like  Bartle's  " Elements of Real Analysis " 2d 
ed.(1976)  Wiley,  New York.  Collected here are proofs,  mostly short,  
for mathematical phenomena,  some little known,  worth knowing during 
the design of robust and rapid root-finders.

Almost all  Numerical Analysis  texts cover the solution of one real 
equation  f(z) = 0  for one real root  z  by a variety of iterative 
algorithms, like  x -> U(x)  for some function  U  that has  z = U(z)  
as a fixed-point.  The best known iteration is  Newton's:
              x  ->  x - f(x)/f'(x) .
Another is  Secant  iteration:  Replace the pair of guesses  {x, y}  by 
the pair  {w, x}  where  w  :=  x - f(x)(x-y)/( f(x) - f(y) ) .  But no 
text I know mentions some of the most interesting questions:

Is some simple  Combinatorial  (Homeomorphically invariant)  condition 
   both  Necessary  and  Sufficient  for convergence of  x -> U(x) ?  
   (Yes;  $5)

Is that condition relevant to the design of root-finding software?  
   (Yes;  $6)

Are there other iterations  x -> U(x)  besides  Newton's ?  
   (Not really;  $3)

Must there be a neighborhood of  z  within which  Newton's  iteration 
   converges if  f'(x)  and  x - f(x)/f'(x)  are continuous?  
   (Maybe Not;  $7)

Do useful conditions less restrictive than  Convexity  suffice  
   Globally  for the convergence of  Newton's  and  Secant  iteration? 
   (Yes;  $8)

Why are these less restrictive conditions not  Projective Invariants,  
   as are  Convexity  and the convergence of  Newton's  and  Secant  
   iterations?   ( I don't know;  $A3)

Is slow convergence to a multiple root worth accelerating?  
   (Probably not;  $7)

Can slow convergence from afar be accelerated with no risk of
   overshooting and thus losing the desired root?  
   (In certain common cases, Yes;  $10)

When should iteration be stopped?   
   ( Not for the reasons usually cited;  $6)

Which of  Newton's  and  Secant  iterations converges faster? 
   (Depends;  $7)

Which of  Newton's  and  Secant  iterations converges from a wider 
   range of initial guesses at  z ?   
   ( Secant,  unless  z  has even multiplicity;  $9)

      THEREFORE,  WHY USE  TANGENTS  WHEN  SECANTS  WILL DO?

( Have  ALL  the foregoing answers been  PROVED ?  Yes.  Most were 
proved over twenty years ago,  and influenced the design of the  
[SOLVE]  key on  Hewlett-Packard Calculators.)


Contents:
   $1.  Overview
   $2.  Three Phases of a Search
   $3.  Models and Methods
   $4.  "Global" Convergence Theory  from  Textbooks
   $5.  Global Convergence Theory
   $6.  A One-Sided Contribution to Software Strategy
   $7.  Local Behavior of  Newton's  and  Secant  Iterations
   $8.  Sum-Topped Functions
   $9.  The Projective Connection between  Newton's  and  Secant  Iterations
   $10.  Accelerated Convergence to Clustered Zeros  (incomplete)
   $11.  All Real Zeros of a Real Polynomial  (to appear)
   $12.  Zeros of a Real Cubic  (to appear)
   $13.  Error Bounds for Computed Roots  (to appear)
   $ccc.  Conclusion
   $A1.  Appendix:  Divided Differences Briefly 
   $A2.  Appendix:  Functions  of Restrained Variation
   $A3.  Appendix:  Projective Images
   $A4.  Appendix:  Parabolas
   $A5.  Appendix:  Running Error Bounds for Polynomial Evaluation  (to appear)
   $:  Citations

NOT YET READY FOR DISTRIBUTION
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

PostScript file:  http://www.cs.berkeley.edu/~wkahan/Math128/RealRoots.ps
Acrobat(TM) Reader  PDF  files:   .../SOLVEkey.pdf  and  .../RealRoots.pdf