A Spreadsheet for finding Roots of Polynomials | Hacker News Reader

A Spreadsheet for finding Roots of Polynomials

datanitro.com

33 pointskaramazov9 comments

"If you change a polynomial's coefficients slightly, its roots will only change slight as well."

If only: http://en.wikipedia.org/wiki/Wilkinson's_polynomial

That's a great point, and an awesome article. In the post, I'm referring to a continuous change versus a discontinuous one; with large coefficients or large powers, you can cause a big shift with a very small change.

However, you can always find a chance small enough that it won't make a substantial impact on the roots; this isn't the case with discontinuous functions.

Ehm. The big (as in BIG BROTHER) problem is that mere continuity is a very very weak property. The fact that "small" changes turn into other "small" changes depends essentially on the "smallness".

For example (I know this is not a polynomial, but the function is related to root-finding):

f(x) = x^(1/10)

which has x=0 as a root (f(0)=0).

Take a "small" increment of x, say x=0.01

f(0.01) = 0.63+

Which, to any reasonable human being is "quite large" with respect to the increment of x.

This is even worse for Wilkinson's Polynomial, which is what the parent was trying to convey, I guess.

I know I am referring just to a related problem but this is one of those days for me...

That is: roots depend continuously on the coefficients of a polynomial but that continuity is filled with very bad behaved constants all around dancing and whirling to make the problem very very bad behaved.

EDIT: I think I have realised what I want to say.

Take P(x) = x^10, it has a (multiplicity 10 root at x=0). Then take Q(x) = x^10 - .01 (which is a "small" deformation of P(x)). Then the roots of Q are 0.63+ and -0.63+, which are "huge" compared to 0, 0.01.

Unless I am still under this terrible drosiness...

The dependence of (real) roots on the coefficients of a polynomial isn’t even continuous; an arbitrarily small change to the coefficients of a polynomial with a double root will result in either the appearance of an extra root or in the (real) root disappearing entirely.

In the complex plane the situation is much happier, but root-finding remains extremely poorly conditioned for examples like Wilkonson’s.

Yes, yes, I know that, I was focusing on getting an example.

I think I should call it a day and reboot tomorrow...

Oh, it's actually the case that the roots change smoothly as you smoothly change coefficients, as long as you avoid hitting double roots -- this is an exercise in using the implicit function theorem. It's just as you say: the "delta" from the definition of continuity may be much, much smaller in general then the "epsilon".

Another thing that might be going on here is that while the roots vary continuously as function of coefficients, the continuity is probably not uniform. There's a whole notion of uniform continuity, which basically says in this case that, regardless of the starting point, if you change coefficients by some delta, the roots won't move further then some global constant time delta. In general, depending on the starting point, when you change the coefficients by delta, the roots may move by 10delta or 100000delta, but uniform continuity would say that this is not the case.

Yes, yes, I know all that.

The problem was my mind yesterday. It looked like a jellyfish inside a cup of lemon jelly with some caramel...

Section 3 "Roots are closely related to factoring a polynomial - for example, the roots of x2 - 4 are 2 and 2, and you can write x2 - 4 as (x-2)(x-2). We say that a root r has a multiplicity greater than one if (x-r) is a factor of the polynomial more than once." This is incorrect. x2 - 4 = (x - 2)(x + 2). Meaning the roots are 2 and -2. Also section 5, I'm not sure how you came up with those answers. The roots are 2 and -1. I tried the spreadsheet, but can't seem to get it to work.

these are fixed. thanks for pointing them out!

what's wrong with the spreadsheet?

Reply on news.ycombinator.com