[Ryano121]

I just stumbled on a website providing a solution to the Newton Raphson method of solving polynomials.

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

[tsotne1990]

Choose one point (preferably a starting point if you have any interval) and iterate on it by interchanging the successive value on the x line. Alternatively, you can choose arbitrary numbers from the approximating scale and modify your code in such a way that it goes to different directions to catch all the values satisfying the requiring condition.

[sk8ermeb]

Ok so correct me if I am wrong but this method approximates the roots and x^2 + 5x + 6 has no real roots only imaginary. Second of all if you guess a point on the side of a function such that the derivative does not point in the direction of a root it will not converge to my knowledge. Finally if the newton method is used with a complex function, which I didn't know was possible, most functions can work with complex as if they are another dimension, aka if you pretend its the z axis then like a complex function you can set the Z coefficients 2 zero to get your real valued function.

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

[tsotne1990]

Quote

This sounds more like a math question I think.

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)

[Ryano121]

Thanks for the replies!

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

[sk8ermeb]

If you aren't concerned about useing a specific algorithym and just want a way to find the roots just scan the function mark every spot where it changes signs then use the bi-section method to get it as accurate as you want? or you just scan a bunch of data and find the closest one to zero, because were talking numerical approximators not closed form solutions rite?

This post has been edited by sk8ermeb: 03 February 2011 - 02:54 PM

[Ryano121]

Good call on the bi-section method and yeah im only looking for approximations. Getting closed solutions would be way beyond by ability.

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!

[tsotne1990]

Quote

Appart from the three point search approach, is there any other algorithms/methods that i could use to do this?

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 iteration-based 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

If you aren't concerned about useing a specific algorithym and just want a way to find the roots just scan the function mark every spot where it changes signs then use the bi-section method to get it as accurate as you want? or you just scan a bunch of data and find the closest one to zero, because were talking numerical approximators not closed form solutions rite?

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 escape-think about it for sharp corner functions. But for dynamic functions there is no problem with this approach.

[Ryano121]

Thanks for the advice Tsotne.

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

[tsotne1990]

Yes sure. I just uploaded it. You can find the algorithms very interesting for you in this file.

http://www.mediafire...7e14323vdfd1edl

[Ryano121]

Wow that is one amazing word document! Thanks for the link.

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 three-point 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!

[tsotne1990]

Quote

Wow that is one amazing word document! Thanks for the link.

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

[Ryano121]

Oh i see now lol. i got confused by how it went straight onto the Fibonacci search algorithm

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

[tsotne1990]

Quote

Am i missing something here or am i just having a bit of a nightmare trying to figure this one out?

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.

[Ryano121]

Thanks for that. It make so much more sense now!

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