Polynomial iterators.

One of the ways in which we can create new, and hopefully better, iterators is by isolating subexpressions which are easy to invert, instead of isolating x. For example, the equation $6x^2-9x+6-\ln(8+x)$ generates the iterators

$$\begin{eqnarray*}x & = & \frac{6x^2+6-\ln (8+x)}{9} \\ & = & \pm \frac{ \sqrt{-4+6x + 2\ln (8+x)/3}}{2} \\ & = & e^{6x^2-9x+6}-8 \end{eqnarray*}$$

For the initial value x₀=1.23, all these iterators fail. The first one and the third one grow without bound, the positive second iterator converges too slowly and the negative oscillates between one value and its conjugate. For this equation we could instead isolate the polynomial part

$$6x^2-9x+6 = \ln (8+x)$$

solve it treating the $\ln (8+x)$ as a constant, and obtain two new iterators.

$$x = \frac{ 9 \pm \sqrt{24\ln (8+x)-63 }}{12}$$

Notice that these new iterators have only one occurrence of x on the rhs, compared to two for the previous ones. The positive choice for this iterator is successful and converges very quickly to x=0.7595...+0.2753...i. This is not a general rule, we could certainly find examples which show the contrary, but in general it is expected that such groupings will produce better iterators as they capture more information about the inverse.

So we will use the following rule, for each iterator F(x) which is a sum of a polynomial part and a non polynomial part, i.e.

x = F(x) = G(x) + p(x)

we will produce an iterator which is x-p(x)=G(x) and each iteration consists of evaluating $\beta=G(x)$ and then solving the polynomial $x-p(x)-\beta=0$. Removing the polynomial part will decrease the number of occurrences of x on the rhs, and hence improve our measure of quality of the iterators. The iterator can be written using Maple's RootOf² notation as

$$x_{i+1} = {\tt RootOf}( G(x_i)+p(z)-z=0, z )$$

A polynomial iterator, with degree d on its lhs, will normally have d roots. This has a cardinality advantage over handling a polynomial iterator by its individual terms. If the individual terms of the polynomial are isolated one by one, and for each monomial x^k, k roots have to be considered, up to d(d+1)/2 iterators could be generated. The drawback is obvious, instead of having a closed form solution for the iterator, we have to solve a polynomial of degree d, and this is typically an iterative process for d>2.

Selecting which root of the polynomial to use is non trivial. When roots are given by a formula, e.g. for d=2, then it is easy to write two iterators, one for each root. But when the roots are found numerically, it is not possible to have a consistent way of using the same root on successive iterations. Actually, the term ``same root'' does not even make sense for different polynomials, it only makes sense when the roots can be expressed as functions of the coefficients. On the other hand, if the polynomial iterator is converging, we want to select the root which is closest to the iteration value. I.e.

$$x_{i+1} = {\tt RootOf}( p(z) - F(x_i), z )$$

and we select the root which is closest to x_i. Since this selection is necessary for convergence, we will use it in every step of the algorithm. Furthermore, many iterative methods for solving polynomials can profit significantly from starting their iterators at an approximation of the root; the correct root could come almost for free. For example, for the solution of the equation

$$x^5 -6x^4 +5x^3 -7x^2 \ln x +6x -5 = 0$$

we define the iterator

$$x_{i+1} = {\tt RootOf}( z^5 -6z^4 +5z^3 +6z -5 = 7x_i^2 \ln x_i, z )$$

If we start with x₀ = 1, then the rounded roots of the polynomial are

$$-0.526224 \pm 0.844348i, \;\;\; 0.758845, \;\;\; 1.34521, \;\;\; 4.94839$$

The root which is closest to x₀=1 is 0.758845...Hence we set x₁=0.758845.... For the second iteration the polynomial to solve, is z⁵ -6z⁴ +5z³ +6z -5 =-1.11236...The roots of this polynomial are

$$-0.489123 \pm 0.829261i, \;\;\; 0.586566, \;\;\; 1.44569, \;\;\; 4.94599$$

and the root closest to x₁ is 0.586566... which becomes x₂. This process converges quite quickly, x₃=0.561733..., x₄=0.563302..., x₅=0.563168..., etc. This root selection can also be treated as a multiple value function problem, which is discussed in the next section.

 

Table 2: Iterators which have a non-linear polynomial in their lhs

66644 random equations producing 59428 iterators
method		failures
converged to a root	44.64%	converged to a non-root	1.67%
failed	55.36%	diverged	21.22%
average time	1.593	outside domain	18.06%
time per root	3.569	too many iterations	4.79%
		iterator fails	0.00%
iterators per equation	.892	no iterators	54.26%

Table 2 shows the simulation results for polynomial lhs iterators. Almost 45% of the iterators yield a root, in time which is of the same order of magnitude as for the simple iterators.