Efficient Computation of The Least Fixed Point of A Polynomial

Question

Let P(x) denote the polynomial in question. The least fixed point (LFP) of P is the lowest value of x such that x=P(x). The polynomial has real coefficients. There is no guarantee in general that an LFP will exist, although one is guaranteed to exist if the degree is odd and ≥ 3. I know of an efficient solution if the degree is 3. x=P(x) thus 0=P(x)-x. There is a closed-form cubic formula, solving for x is somewhat trivial and can be hardcoded. Degrees 2 and 1 are similarly easy. It's the more complicated cases that I'm having trouble with, since I can't seem to come up with a good algorithm for arbitrary degree.

EDIT:

I'm only considering real fixed points and taking the least among them, not necessarily the fixed point with the least absolute value.

Answer 1

Since you want the least fixed point, you can't get away without finding all real roots of P(x) - x and selecting the smallest.

Finding all the roots of a polynomial is a tricky subject. If you have a black box routine, then by all means use it. Otherwise, consider the following trick:

• Form M the companion matrix of P(x) - x
• Find all eigenvalues of M

but this requires you have access to a routine for finding eigenvalues (which is another tricky problem, but there are plenty of good libraries).

Otherwise, you can implement the Jenkins-Traub algorithm, which is a highly non trivial piece of code.

I don't really recommend finding a zero (with eg. Newton's method) and deflating until you reach degree one: it is very unstable if not done properly, and you'll lose a lot of accuracy (and it is very difficult to tackle multiple roots with it). The proper way do do it is in fact the above-mentioned Jenkins-Traub algorithm.

Answer 2

Just solve f(x) = P(x) - x using your favorite numerical method. For example, you could iterate

x_{n + 1} = x_n - P(x_n) / (P'(x_n) - 1).

You won't find closed-form formula in general because there aren't any closed-form formula for quintic and higher polynomials. Thus, for quintic and higher degree you have to use a numerical method of some sort.

Answer 3

This problem is trying to find the "least" (here I'm not sure if you mean in magnitude or actually the smallest, which could be the most negative) root of a polynomial. There is no closed form solution for polynomials of large degree, but there are myriad numerical approaches to finding roots.

As is often the case, Wikipedia is a good place to begin your search.

If you want to find the smallest root, then you can use the rule of signs to pin down the interval where it exists and then use some numerical method to find roots in that interval.