CODEWITHSUNDEEP
functionhaskellfunctional-programmingnewtons-method
Joel Giroud
Joel Giroud

Reputation: 51

Using function arguments in Haskell for the Newton-Raphson method

I need to write a Haskell function that resolves the Newton-Raphson algorithm by passing a function, its derivative and the initial point (x0) as arguments, and returns an approximation of the function root.

Example:

f(x) = x^2 − 2x + 1
f′(x) = 3x^2 − 2
x0​ = −1.5
.
x3 ​= −1.618 ​= x2​ − f′(x2​)/f(x2​)

I would appreciate a lot all of your help and suggestions.

What I have tried before is this:

newtonR f g x0 = 
    if (x0 - (f x0 / g x0)) /= 0 then
        newtonR f g (x0 - f x0 / g x0)
    else
        x0

... and it returns the following error message:

No instance for (Show (Double -\> Double))
arising from a use of \`print'
(maybe you haven't applied a function to enough arguments?)

Upvotes: 2

Views: 178

Answers (2)

Joel Giroud
Joel Giroud

Reputation: 51

Thanks a lot to 'jpmarinier' for helping me to resolve this. What i finaly did is:

    {-# OPTIONS_GHC -Wno-unrecognised-pragmas #-}
    {-# HLINT ignore "Redundant bracket" #-}
    import Prelude hiding (words)
    import qualified Data.Char as Char
    
    -------------------------------
    -- f's def
    f ::  Num a => a -> a
    f x = (x^3)-7
    
    -- f' = g
    g :: Num a => a -> a
    g x = 3*(x^2)
    
    -- Aux func that works with x0
    iterateF :: (Num a, Fractional a) => a -> a
    iterateF a =
          a - (f a)/(g a)
    
    -- To make rounded comparisons
    truncate' :: (RealFrac a, Integral p) => a -> p -> a
    truncate' x n = (fromIntegral (floor (x * t))) / t
        where t = 10^n
    
    -- Main func
    newtonR :: RealFrac t => t -> t
    newtonR x0 =  -- x0 specifies the start point
        if truncate' (iterateF x0) 3 == truncate' x0 3 then
            x0
        else
            newtonR (iterateF x0)

Notice that the accuracy level in the comparison is controlled by the algorythm.

Upvotes: 1

jpmarinier
jpmarinier

Reputation: 4733

One can start by writing a function that performs a single iteration of Newton-Raphson. Note that it is good and common practice to provide an explicit type signature before the body of the function:

nrIter :: (Double -> Double) -> (Double -> Double) -> Double -> Double
nrIter f f' x0 = x0 - (f x0 / f' x0)

It is one the idiosyncrasies of Haskell that f' is a valid identifier, unlike in classic imperative languages.

As mentioned in the comments, testing floating-point numbers for equality is error prone, because of inevitable rounding errors. Instead, we can provide an explicit tolerance level, and write the upper level logic for Newton-Raphson like this:

newtonR :: (Double -> Double) -> (Double -> Double) -> Double -> Double -> Double
newtonR f f' tol x0 =
    let
         x1 = nrIter f f' x0
         dx = abs (x1 -x0)
    in   
         if (dx < tol)  then  x1
                        else  newtonR f f' tol x1

Sample test code:

We can compute an approximation of the cubic root of 2 like this:

main :: IO ()
main = do
    let  cr2 = newtonR  (\x -> x^3 - 2.0)  (\x -> 3.0*x^2)  1.0e-9  1.0
    putStrLn $ "Cubic root of 2 is close to: " ++ (show cr2)

Upvotes: 5

Related Questions