GNU Info

(slib.info)Root Finding

---

Next: Minimizing Prev: Plotting Up: Mathematical Packages

---

Enter node , (file) or (file)node

Root Finding
============

  `(require 'root)'

 - Function: newtown:find-integer-root f df/dx x0
     Given integer valued procedure F, its derivative (with respect to
     its argument) DF/DX, and initial integer value X0 for which
     DF/DX(X0) is non-zero, returns an integer X for which F(X) is
     closer to zero than either of the integers adjacent to X; or
     returns `#f' if such an integer can't be found.

     To find the closest integer to a given integers square root:

          (define (integer-sqrt y)
            (newton:find-integer-root
             (lambda (x) (- (* x x) y))
             (lambda (x) (* 2 x))
             (ash 1 (quotient (integer-length y) 2))))
          
          (integer-sqrt 15) => 4

 - Function: integer-sqrt y
     Given a non-negative integer Y, returns the rounded square-root of
     Y.

 - Function: newton:find-root f df/dx x0 prec
     Given real valued procedures F, DF/DX of one (real) argument,
     initial real value X0 for which DF/DX(X0) is non-zero, and
     positive real number PREC, returns a real X for which `abs'(F(X))
     is less than PREC; or returns `#f' if such a real can't be found.

     If PREC is instead a negative integer, `newton:find-root' returns
     the result of -PREC iterations.

H. J. Orchard, `The Laguerre Method for Finding the Zeros of
Polynomials', IEEE Transactions on Circuits and Systems, Vol. 36, No.
11, November 1989, pp 1377-1381.

     There are 2 errors in Orchard's Table II.  Line k=2 for starting
     value of 1000+j0 should have Z_k of 1.0475 + j4.1036 and line k=2
     for starting value of 0+j1000 should have Z_k of 1.0988 + j4.0833.

 - Function: laguerre:find-root f df/dz ddf/dz^2 z0 prec
     Given complex valued procedure F of one (complex) argument, its
     derivative (with respect to its argument) DF/DX, its second
     derivative DDF/DZ^2, initial complex value Z0, and positive real
     number PREC, returns a complex number Z for which
     `magnitude'(F(Z)) is less than PREC; or returns `#f' if such a
     number can't be found.

     If PREC is instead a negative integer, `laguerre:find-root'
     returns the result of -PREC iterations.

 - Function: laguerre:find-polynomial-root deg f df/dz ddf/dz^2 z0 prec
     Given polynomial procedure F of integer degree DEG of one
     argument, its derivative (with respect to its argument) DF/DX, its
     second derivative DDF/DZ^2, initial complex value Z0, and positive
     real number PREC, returns a complex number Z for which
     `magnitude'(F(Z)) is less than PREC; or returns `#f' if such a
     number can't be found.

     If PREC is instead a negative integer,
     `laguerre:find-polynomial-root' returns the result of -PREC
     iterations.

 - Function: secant:find-root f x0 x1 prec
 - Function: secant:find-bracketed-root f x0 x1 prec
     Given a real valued procedure F and two real valued starting
     points X0 and X1, returns a real X for which `(abs (f x))' is less
     than PREC; or returns `#f' if such a real can't be found.

     If X0 and X1 are chosen such that they bracket a root, that is
          (or (< (f x0) 0 (f x1))
              (< (f x1) 0 (f x0)))
     then the root returned will be between X0 and X1, and F will not
     be passed an argument outside of that interval.

     `secant:find-bracketed-root' will return `#f' unless X0 and X1
     bracket a root.

     The secant method is used until a bracketing interval is found, at
     which point a modified regula falsi method is used.

     If PREC is instead a negative integer, `secant:find-root' returns
     the result of -PREC iterations.

     If PREC is a procedure it should accept 5 arguments: X0 F0 X1 F1
     and COUNT, where F0 will be `(f x0)', F1 `(f x1)', and COUNT the
     number of iterations performed so far.  PREC should return
     non-false if the iteration should be stopped.