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.