Newton–Raphson

Question

    

I All

Again some Bla-Bla from me

I was searching for something to talk to, and I thought that I could be usefull to some by talking about the Newton–Raphson method and the algorithms that can be derived from it.

With this method, it is possible to evaluate the value of any function and this very quickly.

I will here create a method that can compute any root of a number (SquareRoot, cubicRoot, ...  and even a decimal root  (ie.the (3.54)Root of 385))



BUT FIRST SOME THEORY

Let start with the basic:

   The Newton–Raphson is simply this:

     X(n+1) = X(n) - f(X(n)) / f'(X(n))

   Where f(X) is the function that need to be evaluate, and f'(X) is the derivative of this function

What is beautiful with this simple function is that it has a quadratic convergence. So in any case, seven iterations will give you a precision superior than the precision of a "Double". Therefore, even the more complex function can be solve VERY quickly.

To initialize the function, a value of X has to be guess. 

This guessed value can be any value, as long that the value is defined for the function. As exemple, if the function is Cos(x), any value between Pi and -Pi can be chosen as initial value.

So, let see what this would look like to evaluate a function f(X) with the initial value guess to be i

X = i
X1 = X - f(X) / f'(X)     [First iteration]
X2 = X1 - f(X1) / f'(X1)  [Second iteration]
X3 = X2 - f(X2) / f'(X2)  [Third iteration]
...
X7 = X6 - f(X6) / f'(X6)  [Seventh iteration]

At this point, after seven iterations the precision is already superior than the precision of a Double.

-------------

So, let put what we already have in code. 

This is a function that will take as argument, one Func(Of Double, Double) as being the function to evaluate, one  Func(Of Double, Double) as being the derivative of this function, and a Value as Double being the guessed value

    Private Function NewtonSolver(ByVal Funct As Func(Of Double, Double), ByVal Derivative As Func(Of Double, Double), ByVal Init As Double) As Double

        Dim Xn As Double = Init
        Dim Iteration As Integer = 0

        Do
            Iteration += 1
            Xn = Xn - (Funct(Xn) / Derivative(Xn))
        Loop Until Iteration = 7

        Return Xn
    End Function

     

At this point, this function is not very usefull, but still has some power!!

Let see an example of usage of it

This example will use this funtion to compute the value of X where: Cos(X) = X^3   

we can write:
   Cos(X) - X^3 = 0

So the function is, f(X) = Cos(X) - X^3 

The derivative is f'(X) = -Sin(X) - 3X^2

Therefore, translated in VB

Dim Funct As New Func(Of Double, Double)(Function(X As Double) Math.Cos(X) - X ^ 3)
Dim Deriv As New Func(Of Double, Double)(Function(X As Double) -Math.Sin(X) - 3 * X ^ 2)

   and the value that solve the equation is

Dim X As Double = NewtonSolver(Funct, Deriv, 0.5) 
   We find X = 0.865474033102

   We have used 0.5 to initialize the function since we know that 0.5 is defined for Cos(x) and X^3

----------------------

Now that we have see the theory of this, let build our function that can compute any root of a number

Well it is very easy to create this VB function, since the what we are doing is always to extract a root, we can hardcode the function that do so and it's derivative inside the VB function and therefore only pass as argument the value for which we want the root to be compute and which root we want


Seatching the n'th root of V
    [n-Root](V) = x
then
    V = x^n
then
    0 = x^n - V 
Finaly
    f(x) = x^n - V

The derivative is
    f'(x) = n*x^(n-1)

Since the root is defined for any real value, we can just use the value V as guessed value

Then, our VB function that can compute any root of any value will simply be this

    Private Function N_Rooth(ByVal Value As Double, ByVal N As Double) As Double

        Dim Xn As Double = Value
        Dim Iteration As Integer = 0
        Do
            Iteration += 1
            Xn = Xn - (Xn ^ N - Value) / (N * Xn ^ (N - 1))
        Loop Until Iteration = 7
        Return Xn
    End Function

Quick and easy !!

We can also create some friendlier function

    Private Function SquareRooth(ByVal Value As Double) As Double
        Return N_Rooth(Value, 2)
    End Function

or

    Private Function CubicRooth(ByVal Value As Double) As Double
        Return N_Rooth(Value, 3)
    End Function

We can now compute the value of the root I showed at the beginning of this post, the 3.54 root of 385

  Dim X as Double = N_Root(385, 3.54)

X = 37.700856681302

-------------------

Now, Using the same method, just have fun and create your own method that quickly compute your favorite function

Answer 1

too bad you cant help me with an xna physics coding problem in vb.net or c#.  Im trying to make a grenade move along a trajectory but trying to find the way to code it so it moves along a path (parabola) for a certain amount of time until it reaches desination. But trouble is knowing how far away the destination is to make it fall since im finding this information dynamic or as the person is moving.

Just thought i would see if anyone knows of any good links or has ideas for this since xna can be coded in vb.net now. Im actually doing coding in c# but can convert.

Pennie i know this was related but not quite 100% on topic I just wanted to see if you could make an efficent formula for something like this since it has more uses then just in an game (simulators).

---

Once you eliminate the impossible, whatever remains, no matter how improbable, must be the truth. - "Sherlock holmes" "speak softly and carry a big stick" - theodore roosevelt. Fear leads to anger, anger leads to hate, hate leads to suffering - Yoda. Blog - http://jefferycarlsonblog.blogspot.com/

Answer 2

The Thinker,

I have not play too much with XNA, 

However, to compute the position of a projectile on the parabola, it is not required to compute the position of the object on the function of the parabola. There is an easier way to do that

In the X-Y plan, the speed of the object is constant. so the position = Vt where V is the speed into this plan X-Y at which the object was threw and t is the time elapsed since the object was threw

In the Z direction, your position is ( Vt - (gt^2)/2). Where t is the time elapsed since since the object was threw, V is the initial speed in the Z direction at what the object was threw, and finally g is whatever constant value that represent the gravity

To compute these two speed, ( in the plan and in the direction of Z) , V(Z) will be the Sin of the angle at what the object was threw time the speed at what the object was threw --- and the speed, V(X-Y) plan, is the cos  of the angle at what the object was threw time the speed at what the object was threw

Hope I am helpful

Answer 3

Trouble is i know createtranslation(x,y,z) can move to x,y,z point in 3d but cant figure out how to implement correctly. Heres my thread in which i was given a simple version for 2d and a person explained some 3d topics:

http://xboxforums.create.msdn.com/forums/t/103885.aspx

im more looking for the equation/math path then anyother code because i can move the object i and find its starting position in 3d space but not the end position of where the greanade falls.

BTW, good topic and formula and sorry for getting a little into another space.

I think his formula works for 3d too but i need to figure out angle of head(which probably depends on my viewport in xna or what the player sees).

---

Once you eliminate the impossible, whatever remains, no matter how improbable, must be the truth. - "Sherlock holmes" "speak softly and carry a big stick" - theodore roosevelt. Fear leads to anger, anger leads to hate, hate leads to suffering - Yoda. Blog - http://jefferycarlsonblog.blogspot.com/

Answer 4

Very interesting indeed ;)

---

If you want something you've never had, you need to do something you've never done. If you believe something to be true, then one day you will be called upon to demonstrate that truth.

Answer 5

Following some comment I got from a friend,

I will add some comment here about my "NewtonSolver"

This NewtonSolver method will always return a solution to the function that was passed to it, however, if the function passed as argument is a polynomial, more than one solution may exists.

There is no method that will let your find directly all the solution for an equation, however, there is possibility to find them.

I will implement here a method that will return all the solution for an equation that one or more solution. My solution to this problem is based on the Vincent's theorem

( The solutions that the method will find are those in the range between Integer.MinValue and Integer.MaxValue. If the equation has some solution outside of this range, they will either be ignored. There is also a possibility of overflow, if the convergence attempt to go to a solution outside of the valid range for a Double. )

What I will do is use the Newton–Raphson to converge from a point located at Integer.MinValue to the point of the left most solution on the absissa.

Then, repeat the same process to converge from Integer.MaxValue to the right most solution.

At this point, if the right most solution = the left most solution, then only one solution exists 

Then, I will scan the absissa from the leftmost solution to the right most and using the sign variation idea from the Vincent's theorem, I will be able to locate the points where I am in close proximity of a solution. 

Then I will use again the Newton–Raphson method to converge from the found points to the solution.

Once all the solution are found, The method will return an array that contains all the solutions

    Private Function Solver(ByVal Funct As Func(Of Double, Double), ByVal Derivative As Func(Of Double, Double)) As Double()

        Dim Solutions As New List(Of Double)

        'Get the left most solution
        Dim LeftMostSolution As Double
        Dim tmpVal As Double = Integer.MinValue
        Do
            LeftMostSolution = tmpVal
            TmpVal = NewtonSolver(Funct, Derivative, Math.Round(TmpVal))
        Loop Until LeftMostSolution = tmpVal

        'Get the right most solution
        Dim RightMostSolution As Double
        tmpVal = Integer.MaxValue
        Do
            RightMostSolution = tmpVal
            tmpVal = NewtonSolver(Funct, Derivative, Math.Round(tmpVal))
        Loop Until RightMostSolution = tmpVal

        'if the left most solution = Rightmost solution it means that
        'only one solution exists.
        'So return the solution found
        If RightMostSolution = LeftMostSolution Then
            Return New Double() {RightMostSolution}
        End If

        'If more than one solution exists, then we will
        'scan the the abscissa from the left most solution to the right most solution
        'Each time the value of the function will change sign, we will know that
        'we are in close proximty of a solution. We then use the newtom solver to 
        'converge to this solution
        Dim Left As Double = LeftMostSolution
        Dim SignFlag As Boolean = Funct(Left) < 0
        For i = Math.Floor(LeftMostSolution) To Math.Ceiling(RightMostSolution)
            For j = 1 To 10
                Left += 0.1
                If Not SignFlag = (Funct(Left) < 0) Then
                    Solutions.add(NewtonSolver(Funct, Derivative, Left))
                    SignFlag = Not SignFlag
                    Stop
                End If
            Next
        Next
        Return Solutions.ToArray
    End Function

An example of usage:

the function:

  f(x) = (x+4)(x+2)(x-2)(x-4)

Can be writen

  f(x) = x^4 - 20x^2 + 64

and its derivative

  f'(x) = 4x^3 - 40x

        Dim F As New Func(Of Double, Double)(Function(X As Double) (X ^ 4 - 20 * X ^ 2 + 64))
        Dim D As New Func(Of Double, Double)(Function(X As Double) (4 * X ^ 3 - 40 * X))

        Solver(F, D)

Solver does return the array { -4, -2, 2, 4 }

Which are the 4 solutions possible