### 5.12 Root Finding ¶

`(require 'root)`

In the Newton method, divide the df/dx argument by the multiplicity of the desired root in order to preserve quadratic convergence.

Function: newton: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 integer’s 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: 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.