20 Replies  8220 Views  Last Post: 11 February 2011  12:54 PM
#1
Newton Raphson Method
Posted 03 February 2011  01:22 PM
Newton Raphson Website
However the particular example that they implement asks for a series of real coefficients which makes sense, but it also asks for 'imaginary coefficients', but i have no idea why it asks for them.
To try and solve an equation such as x^2 + 5x + 6, i put in 1,5,6 (at least i think this is correct) and because i dont know what to put for the imaginary coefficients i put the same. It gives me the correct answers of 2 and 3 along with some other weird answers.
Any ideas what this could be for and what i should put for them? I wont be dealing with complex numbers at all so can i just delete it? The rest of the code requires the list that it produces so i guess not.
However for other equations such as 2x^2 + 10x  15 i put in 2,10,15 for both and it gives me one correct answer but the other one doesnt work, is it me putting in the coefficients wrong or something to do with the code?
I am particulary interested in this code because of the way it solves for all roots instead of just the one that i am currently solving for in my implementation.
Thanks in advance
Replies To: Newton Raphson Method
#2
Re: Newton Raphson Method
Posted 03 February 2011  01:51 PM
#3
Re: Newton Raphson Method
Posted 03 February 2011  02:06 PM
This sounds more like a math question I think. There are a lot of problem using this method with code because if you dont make a good initial gues based on visuals it doesn't work. There are also overshooting and other non converging issues you should review.
This post has been edited by sk8ermeb: 03 February 2011  02:07 PM
#4
Re: Newton Raphson Method
Posted 03 February 2011  02:24 PM
Quote
Then you're lucky. Im concerned with math too. The Newton  Raphson method and the newton iteration model both requires you chose the initial guess.(Usually taken as the arbitrary value on the argument axis). So if you don't want to supply any initial value and then build your code algorithm on the basis of that value, or maybe you are not sure of the scale and have no clue what should be the initial arbitrary value supplied, then the Newton Methods are not the perfect models you need. Try the three points search approach. You can get as many roots as the equation actually has. (if it is not too complicated)
#5
Re: Newton Raphson Method
Posted 03 February 2011  02:34 PM
It seems that this implementation isnt too accurate anyways, but it was the deflation code that looked interesting. However it seems to confuse me when it says the results can be written as 1 * x − 1 = 0. Using the template for other equations works well but i dont see where it gets it from. Plus with cubic equations what is the system for deflation?
At the moment i have written an expression parser and a very basic differentiation class (all be it a little buggy). I am looking to create a basic equation solver for linear, quadratics and cubics but the equations it solves wont be very complex at all. Appart from the three point search approach, is there any other algorithms/methods that i could use to do this? I started with the Newton Raphson method as it seems to be quite popular but as users of the program hopefully wont have to supply a starting guess, its not the best way to go it seems. Im not too bad with maths but are there any accurate ones out there that are relatively easy to code? (I dont mind about efficiency)
Thanks again
#6
Re: Newton Raphson Method
Posted 03 February 2011  02:53 PM
This post has been edited by sk8ermeb: 03 February 2011  02:54 PM
#7
Re: Newton Raphson Method
Posted 03 February 2011  03:11 PM
Going back to Newtons method however with a supplied starting value this time, is it possible for it to solve all roots of quadratics and cubics? It seems like such a waste to start on a completely new method when this one finds one root practically all of the time on simple equations that i am likley to use.
Thanks for the suggestions!
#8
Re: Newton Raphson Method
Posted 03 February 2011  03:14 PM
Quote
First of all, I want to state that there is no such algorithm not mathematical, not programming that would effectively catch all the roots of a given equation. You have to ALWAYS give up something when relying on approximating or iterationbased algorithms. For example either you give up precision in exchange for speed and vise versa. There are infinitely many algorithms(not sure they are easy to code) that does the optimization and root calculation jobs(given constraints or whatever). Simplex,Dual Simplex, Karmarkar,Cut algorithm, Bound error algorithm, etc. (The last ones are not easy to code). But I would suggest the three point search algorithm where in the same vein I stated above, you have to give up the accuracy of finding a root. Thats how the excel's Goal Seek algorithm is created. You find the nearest root.
Quote
Second of all, with all respect to sk8ermeb, I would strongly reject this suggestion unless you want to create something very simple with a little scale(very little). Because imagine for example, that there is a scale of 10000 to 10000 and you want to iterate over this interval. What kind of precision would you choose? 0.01? Then you end up with
2 000 000 iteration which will hardly(if ever) be handled by your PC. So the approximation algorithms are normal and all in all, I would suggest three point search algorithm, since it is fast and effective. However it also has some holes. That is, some roots can escapethink about it for sharp corner functions. But for dynamic functions there is no problem with this approach.
#9
Re: Newton Raphson Method
Posted 03 February 2011  03:23 PM
I dont mind giving up precision at all. Its mainly just a case of attempting to find the roots. As i said before for the Newton method is there a way to effectively deflate the expression to attempt to calculate other roots or does it have to be a case of putting in a different starting value in the hope that it converges?
Its mainly only for fun really. Of course finding the middle man would be beneficial but i would say that an innacurate guess on all roots with a sacrifice on some speed would be the way i want to go
Do you have any documentation on the three point search algorithm. Google doesnt seem to be helping me too much on this one.
Thanks a lot for the advice. I think ill end up switching to this algorithm it seems
#10
Re: Newton Raphson Method
Posted 03 February 2011  03:28 PM
http://www.mediafire...7e14323vdfd1edl
#11
Re: Newton Raphson Method
Posted 04 February 2011  12:01 PM
However their definition of the Three  point search algorithm is a little hazy for me :S
Their definition for others to see =
"The interval under consideration is divided into quarters and the objective function evaluated at the three equally spaced interior points. The interior point yielding the best value of the objective is determined (in case of a tie, arbitrarily choose one point), and the subinterval centered at this point and made up of two quarters of the current interval replaces the current interval. The threepoint interval search is the most efficient equally spaced search procedure in terms of achieving a prescribed tolerance with a minimum number of functional evaluations. It is also one of the easiest sequential searches to code for the computer."
The document will definately come in handy for some other projects but for now does anyone have a more 'simplified' explanation of how to implement this method to solve equations?
Thanks again for document!
#12
Re: Newton Raphson Method
Posted 04 February 2011  04:45 PM
Quote
However their definition of the Three  point search algorithm is a little hazy for me :S
You're welcome.
Nono Ryano, look, this is just one little definition just for introduction. You are not expected to understand that algorithm by reading it alone. Below every algorithm definitions, there are examples solved by each algorithms. So see the example below the introduction to algorithm definitions and search for three point solution.
This post has been edited by Tsotne: 04 February 2011  04:46 PM
#13
Re: Newton Raphson Method
Posted 05 February 2011  08:17 AM
After going through the document it seems that for this particular algorithm the examples are based solely on how to maximize and minimize functions and not on how to actually solve them in any way :s Its perfectly possible that it does but i dont recall having seen anything like this before in my maths ventures so far.
Am i missing something here or am i just having a bit of a nightmare trying to figure this one out?
Thanks again
#14
Re: Newton Raphson Method
Posted 05 February 2011  05:06 PM
Quote
Three point search provides the way to find the roots. The algorithms stated there are mainly minimization/maximization problems with constraints or not. But the three point search algorithm provides a way to find the roots. You can employee the same model in min/max problem. Its very easy and intuitive. All you have to do is to divide the axis into 3 points and check the intervals for the value you are looking for whether they are min/max/0. 0 in our case. And approach the point with as much precision as you want.
#15
Re: Newton Raphson Method
Posted 06 February 2011  03:28 AM
Correct me if I'm wrong but isn't it just the same as the brute force method where you just loop through all possible values and see which ones are closest to zero?
Plus in my case to figure out all roots of the equation I would have to have many iterations to work out all real roots, especially to a degree of reasonable accuracy
Thanks again for the reply
