Mit dem Newton-Verfahren berechnet man Näherungen von Nullstellen von Funktionen. In jedem Schritt des Verfahrens wird eine Näherung verbessert, indem die Funktion linearisiert und die Nullstelle der Linearisierung als nächste Näherung verwendet wird.

Angenommen, die Näherung für die Nullstelle ist x0, dann ist die Linearisierung der Funktion an dieser Stelle

  y = f'(x0) (x - x0) + f(x0)

Die Nullstelle der Linearisierung lässt sich mit der Herleitung

  0 = f'(x0) (x - x0) + f(x0)
  - f(x0) = f'(x0) x - f'(x0) x0
  f'(x0) x0 - f(x0) = f'(x0) x
  x0 - f(x0) / f'(x0) = x

bestimmen.

Die Realisierung des Newton-Verfahrens in Lisp verwendet drei Funktionen:

Die Funktion newton-next berechnet aus einer Näherung eine bessere Näherung - wie oben beschrieben.

(defproc newton-next (f df x)
  (- x (/ (f x) (df x))))

Die Funktion newton-iteration verbessert eine Näherung so lange, bis der Betrag des Funktionswerts von f an der Stelle der Näherung kleiner als das Argument delta ist.

(defproc newton-iteration (f df x delta)
  (let
    ((x-next (approximate (newton-next f df x) delta)))
    (if
      (< (abs (f x-next)) delta)
      x-next
      (newton-iteration f df x-next delta))))

Die Funktion newton ruft newton-iteration mit passenden Argumenten auf.

(defproc newton (f df x delta)
  (approximate
    (newton-iteration f df x (* delta delta))
    delta))

Anhand der Funktion (Parameter f), ihrer Ableitung (Parameter df) und einer ersten Näherung (Parameter x) wird eine Näherung der Nullstelle auf eine gegebene Abweichung (Parameter delta) genau bestimmt wird.

Mit der Funktion (lambda (x) (- (* x x) 2)) und ihrer Ableitung (lambda (x) (* 2 x)) kann man ausgehend von der ersten Näherung 1 die Quadratwurzel von 2 auf etwa 50 Stellen genau bestimmen:

1.4142135623730950488016887242096980785696718

Quellen
http://de.wikipedia.org/wiki/Newton-Verfahren

Jochen Werner
"Numerische Mathematik 1"
Vieweg 1992
Seiten 101ff