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

x² = 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 x_i+1 from a previous value x_i. When there are multiple choices for x_i+1we want to select the one with minimal distance to x_i for convergence reasons. I.e. select the x_i+1 which makes | x_i+1-x_i| minimal. This observation is a crucial one for our algorithm. So from x_i+1² = h(x_i) 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(x_i+1)² = h(x_i) 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
  end;

In summary, when the result of an isolating step is a multivalued function, we can take two approaches

(a)

Enumerate all iterators, either explicitly as in the case for x² = h(x) or as a function of an arbitrary integer n as for $\sin x = x/100$.

(b)

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

$$\sqrt{ x_{i+1} } = h(x_i)$$

from which we isolate x_i+1 = h(x_i)². In this case there is no choice of inverse, but if h(x_i) 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
  end;