next up previous
Next: Numerical experiments Up: No Title Previous: Attaching poles to the

The optimization problem

In order to find a best denominator, we will solve the optimization problem of minimizing $\Vert r - f\Vert _\infty$ with respect to the zi's, where r is given by (3).

It should be noted that it is not possible that a pole zi thereby comes to lie in the interval [-1,1]: the corresponding r could never be a best approximation to the continuous f. In particular, no zi can be 0.

The existence of an optimum is easily seen. For that purpose, write r as

r := {\sum_{k=0}^N {w_k { \prod\limits_{i=1}^P}\big(1-{x_k\o...
...limits_{i=1}^P}\big(1-{x_k\over z_i}\big)
\over x-x_k}}\right.
\end{displaymath} (4)

and consider every zi on its Riemann sphere $\overline{\hbox{\rm C\kern-.43em\raise0.03em\hbox{\vrule width 0.015em height .6em}}\}$. For the polynomial, every pole is at infinity, i.e., at the north pole of its sphere. And there must exist a set of zi's for which $\Vert r - f\Vert _\infty$ is minimal, since the latter is a continuous function over the cross product of the P spheres, which is compact.

The unicity question is more involved. The constant function example $f\equiv c$ (and, more generally, every polynomial of degree less or equal to N-P) shows that there are $f\in C[a,b]$ for which no pole can be attached to p [4]: every set of numbers replacing the wk in (1) results in $r\equiv f$ (which appears only reasonable from an approximation point of view). In practical computations, such a large connected set of optimal points manifests itself in the optimization routine going around without direction.

Unicity is warranted if the optimization yields $\Vert r-f\Vert _\infty = 0$, i.e., if r=fon [-1,1]. Indeed, when two analytic functions r1, r2 agree on an interval I, then r1 = r2 on every domain of analyticity containing I, by the fundamental lemma on analytic continuation [13, p. 150]. Therefore $\Vert r-f\Vert _\infty = 0$ if and only if $f=r\in\Rscr_{N,P}$ on [-1,1]. Numerically, however, the unicity shows up only if P is not chosen larger than the actual number of poles of f, for otherwise the condition of the problem is so good that many combinations of P poles yield $\Vert r-f\Vert _\infty\le \nu$, $\nu=$unit-roundoff error of the machine.

The unicity question can also be narrowed to an interesting one, to which we do not have the answer. It is obvious from the above construction that nonvanishing of the numerator at zi is a sufficient condition for r to have a pole there. We have checked this condition in its equivalent form [4]

c_i:= \sum_{k=0}^N w_kf_k\prod_{\ss j=1\atop \ss j\ne i}^P
(x_k - z_j)\ne 0.
\end{displaymath} (5)

Do the conditions (5)--one for every zi--imply that the corresponding optimal r is the only one minimizing $\Vert r - f\Vert _\infty$ ?

We want to point to another representation of (5). Indeed, $\sum_{k=0}^N w_k g(x_k)$is the leading coefficient of the polynomial interpolating a function g between the xk's, and this coefficient is the divided difference of g with respect to all xk's [2]. Condition (5) can therefore be written as

g_i\big[x_0,x_1,\ldots,x_N]\ne 0,\quad\mbox{where }
g_i(x) := f(x)\prod_{\ss j=1\atop \ss j\ne i}^P (x - z_j).
\end{displaymath} (6)

A nice property of the suggested interpolation deserves special notice: the approximation error cannot increase with the number of poles, this in sharp contrast with classical rational interpolation. Indeed, as a new unknown, say zP, is added to the set of variables, $\{z_1,\ldots,z_{P-1}\}$, the optimal value of the latter is a feasible vector for the higher dimensional optimization--simply set $z_P=\infty$ in (4). In particular, attaching poles to the interpolating polynomial can never worsen the quality of the approximation.

next up previous
Next: Numerical experiments Up: No Title Previous: Attaching poles to the
Hans Mittelmann