next up previous
Next: Conclusions Up: Partial inverse heuristic for Previous: Remove linear term heuristic.

Inverting functions

To generate iterators we often need to invert functions or expressions. For example, if at one point of our isolation process we have the equation

x2 = h(x)

we derive $x =\pm \sqrt{h(x)}$. The choice of signs presents a problem. The easiest way to resolve it is to derive two iterators, one for each sign as we have done before. Almost all functions except for lineal polynomials, present this or other problems for isolation.

An alternative to computing inverses which are multiple-valued is the following. We want to compute a value xi+1 from a previous value xi. When there are multiple choices for xi+1we want to select the one with minimal distance to xi for convergence reasons. I.e. select the xi+1 which makes | xi+1-xi| minimal. This observation is a crucial one for our algorithm. So from xi+12 = h(xi) we will select $x_{i+1} = \pm \sqrt{ h(x_i) }$, the sign depending on whether $\vert x_i-\sqrt{h(x_i)}\vert$ or $\vert x_i+\sqrt{h(x_i)}\vert$ is smaller. This resolves the first problem, the choice between multiple values. For isolating, we use a function ${\tt Inverse\_square}$. E.g. from g(xi+1)2 = h(xi) we derive $g(x_{i+1}) = {\tt Inverse\_square}( h(x_i), g(x_i) )$, where

  Inverse_square := proc( rhs, lhs )
      r := sqrt( rhs );
      if abs(r-lhs) <= abs(r+lhs) then r else -r fi
In summary, when the result of an isolating step is a multivalued function, we can take two approaches
Enumerate all iterators, either explicitly as in the case for x2 = h(x) or as a function of an arbitrary integer n as for $\sin x = x/100$.
Leave the choice to be determined during the actual computation, by choosing the one closest to the previous value, and hence improving the chances of convergence.

A second problem that we have with inverting functions is a domain problem, and it can be illustrated with the equation

\begin{displaymath}\sqrt{ x_{i+1} } = h(x_i) \end{displaymath}

from which we isolate xi+1 = h(xi)2. In this case there is no choice of inverse, but if h(xi) is negative (or $\vert \arg h(x_i) \vert > \pi/2$) then the inverse cannot be computed, as we assume that $\sqrt{x}$ returns its principal value. E.g. for $\sqrt{x} = -1$, isolation gives x=1 which is not a solution of the original equation. Such a situation should be treated as a domain error. In this case we use a new function to define this type of manipulation, $x_{i+1} = {\tt Inverse\_sqrt}( h(x_i) )$ and
  Inverse_sqrt := proc( rhs )
      a := argument( rhs );
      if a <= -Pi/2 or a > Pi/2 then
           ERROR( `cannot invert sqrt` )
      else rhs^2 fi

next up previous
Next: Conclusions Up: Partial inverse heuristic for Previous: Remove linear term heuristic.
Gaston Gonnet