Newton's Method

mathalgorithms

Newtons method (also know as the Newton-Raphson method) is a textbook example of an iterated method for finding successively better approximations to the roots (or zeroes) of a real-valued function. This program calculates the square root using anonymous recursion by way of the _fixpoint combinator_ (a.k.a. Haskell Curry's paradoxical _Y-combinator_) which satisfies $y f = f (y f)$. By setting $x = y f$, it represents a fixed-point of the equation $x = f x$. The Newton-Raphson method can easily be implemented in terms of the Y-combinator as shown below. The helper functions are taken from SICP §1.1.7

6 Sept 2014 by rm-hull

rm-hull/89f92e408c66179914a2

newtons-method.cljs

(ns fixpoint.newtons-method)

(defn square [x]
  (* x x))

(defn average [x y]
  (/ (+ x y) 2))

(defn improve [guess x]
  (average guess (/ x guess)))

(defn good-enough? [guess x]
  (< (Math/abs (- (square guess) x)) 0.0000001))

(defn fix [r]     ; fix point combinator
  ((fn [f] (f f))
   (fn [f]
     (r (fn [x] ((f f) x))))))

(defn sqrt [x]
  (letfn [(iter [func]
            (fn [guess]
              (if (good-enough? guess x)
                guess
                (func (improve guess x)))))]
    ((fix iter) 1.0)))

(doseq [x (range 1 10)]
  (println (str "√" x " = " (sqrt x))))