From: Michael Orlitzky <michael@orlitzky.com>
Date: Tue, 18 Sep 2012 19:15:04 +0000 (-0400)
Subject: Add Newton's method.
X-Git-Url: http://gitweb.michael.orlitzky.com/?p=numerical-analysis.git;a=commitdiff_plain;h=587fda23c4c1e3f2f1a46063a9e6766d002ea356

Add Newton's method.
---

diff --git a/src/Roots/Simple.hs b/src/Roots/Simple.hs
index 64124a8..101b7e2 100644
--- a/src/Roots/Simple.hs
+++ b/src/Roots/Simple.hs
@@ -9,8 +9,9 @@
 module Roots.Simple
 where
 
-import qualified Roots.Fast as F
+import Data.List (find)
 
+import qualified Roots.Fast as F
 
 -- | Does the (continuous) function @f@ have a root on the interval
 --   [a,b]? If f(a) <] 0 and f(b) ]> 0, we know that there's a root in
@@ -71,3 +72,31 @@ bisect :: (Fractional a, Ord a, Num b, Ord b)
        -> Maybe a
 bisect f a b epsilon =
   F.bisect f a b epsilon Nothing Nothing
+
+
+
+-- | The sequence x_{n} of values obtained by applying Newton's method
+--   on the function @f@ and initial guess @x0@.
+newton_iterations :: (Fractional a, Ord a)
+                    => (a -> a) -- ^ The function @f@ whose root we seek
+                    -> (a -> a) -- ^ The derivative of @f@
+                    -> a       -- ^ Initial guess, x-naught
+                    -> [a]
+newton_iterations f f' x0 =
+  iterate next x0
+  where
+  next xn =
+    xn - ( (f xn) / (f' xn) )
+
+
+
+newtons_method :: (Fractional a, Ord a)
+                 => (a -> a) -- ^ The function @f@ whose root we seek
+                 -> (a -> a) -- ^ The derivative of @f@
+                 -> a       -- ^ The tolerance epsilon
+                 -> a       -- ^ Initial guess, x-naught
+                 -> Maybe a
+newtons_method f f' epsilon x0
+  = find (\x -> abs (f x) < epsilon) x_n
+  where
+    x_n = newton_iterations f f' x0