Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

Code Snippets / [DBP] - Newton's method for polynomials

Author
Message
Neuro Fuzzy
16
Years of Service
User Offline
Joined: 11th Jun 2007
Location:
Posted: 26th Dec 2011 13:50
I swear I'll stop posting math stuff soon!

Newton's method is used for finding the roots of an equation numerically. It can also be extended to the complex numbers, so if you have the polynomial x^2+1, you can find its roots numerically using newton's method. (its roots are -i and i).

You start with a complex number Z, and then say Z=Z-f(x)/f'(x), and this new Z is (hopefully) a better approximation of a root of f(x). The deciding factor in what root you reach (i vs -i in the case of f(x)=x^2+1) is what Z you start out on. Newton's method is unpredictable though, and so the boundaries between reaching one root versus another are very very complicated (and cool looking), This program plots those boundaries.





TheComet
16
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 10th Jan 2012 23:07
Quote: "I swear I'll stop posting math stuff soon!"


Wha- What? No more math from Neuro Fuzzy? I love your math things! I haven't commented on all of them, but I've tested them and enjoyed every single one!

TheComet

Chris Tate
DBPro Master
15
Years of Service
User Offline
Joined: 29th Aug 2008
Location: London, England
Posted: 11th Jan 2012 16:12
Nice effect; this would be good for generating particle effects.

What would really be nice is a Neuro Fuzzy Code for Dummys thread; so dummies like me can understand how to use the code.

For each snippet, it could answer the questions: What are practical applications for this code? What are the purpose of each functions? What other uses can the code be used for?

If an 8 year old child can understand the answers to the questions; then I think I'd also understand...

Seriously, it is impressive; would make a nice texture generator, pixel animator. Could work well creating 3D transition effects if the dot command is replaced with 3D translation commands.

It's helpful that it is written in functions aswell, it makes easier to play around with and implement.

I wonder how good this would work in an animated pixel shader...

[I see that you are using Indigo aswell, it's a nice IDE]

Neuro Fuzzy
16
Years of Service
User Offline
Joined: 11th Jun 2007
Location:
Posted: 11th Jan 2012 19:58
Quote: "If an 8 year old child can understand the answers to the questions; then I think I'd also understand...
"

If that's in reference to my soon-to-be attempt at teaching, it's 8th grader and this definitely wouldn't be in there!

I'm planning on writing tutorials for this stuff... but I've been really lazy in revamping my website.



Basically, newton's method goes like this. At any point on a continuous (and differentiable) curve, you have a point on the line (at (x,f(x)) ), and a line tangent to that point with slope f'(x), where f' is the derivative of f.
The tangent line intersects the x-axis, and this is a good estimation of the root of the function. Wikipedia has a good animated gif on this.
Given a slope and a point, the equation of a line through the given point is:
y=m(x-x0)+y0
where (x0,y0) is the point.
So where y=0 we have
0=f'(x) *(xnew-x)+f(x)
solving for xnew (the point where y=0 approximates the point where f(x)=0)
-f'(x)*xnew=-x*f'(x)+f(x)
xnew=x-f(x)/f'(x)

So if we iterate this process again and again, we have something like:
x1=x0-f(x0)/f'(x0)
x2=x1-f(x1)/f'(x1)
x3=x1-f(x2)/f'(x2)
etc.
and x100 will be a really good approximation of the root.

The is an actual proof for newton's method converging, but this explanation is best. We take the linear approximation of the line using the slope at a point, and the root of the line is approximately the root of the function.

As you might imagine, there are plenty of places where this method won't converge. If there is no root, it will jump around forever. If there is no root closeby, it might jump around forever. It might cycle (so after n steps its back where it started), or it might do other weird stuff.
Cycling? Nonconvergence? This starts to sound a lot like the mandelbrot set. In fact, if you plug in a complex polynomial and complex starting values, you get a fractal!


The logarithms in the root finding code? I have no idea why that works. It's a trick I found online to get the shading smooth.
Also, the slider bar is not used in this, I just forgot to remove the code xD

All the unitleft/unitright values are just for getting the unit space into screen/pixel space.

Here's a code snippet that allows you to observe the process:

Each point undergoes 1 iteration of newton's method per frame, and they quickly converge to the polynomial's four roots. The picture in my first snippet graphs the details of this process simply by measuring how long it took for the graph to converge.

The areas of nonconvergence are really precise, so pretty much all points will converge in the code.

Login to post a reply

Server time is: 2024-03-29 07:57:25
Your offset time is: 2024-03-29 07:57:25