Minimax approximation and Remez algorithms

Continuity and attainment in [F2] show that $S_{+}\cup S_{-}$ is nonempty and compact: the maximum of $\mathrm{\mid }e\mathrm{\mid }$ is attained and $E>0$, while each level set is closed in the compact interval [F1]. If one of $S_{+}$ or $S_{-}$ is empty, take $h=1$ or $h=-1$ according to the sign of the nonempty set; this has degree zero and the required sign.

Suppose both sets are nonempty. Their product is a closed bounded subset of ${\mathbb{R}}^2$. For $(x,y),(x^{\mathrm{\prime }},y^{\mathrm{\prime }})\in {\mathbb{R}}^2$, the reverse and ordinary triangle inequalities in [F3] give $\mid \mathrm{\mid }x-y\mathrm{\mid }-\mathrm{\mid }{x}^{\mathrm{\prime }}-y^{\mathrm{\prime }}\mathrm{\mid }\mid \le \mathrm{\mid }(x-y)-(x^{\mathrm{\prime }}-y^{\mathrm{\prime }})\mathrm{\mid }\le \mathrm{\mid }x-x^{\mathrm{\prime }}\mathrm{\mid }+\mathrm{\mid }y-y^{\mathrm{\prime }}\mathrm{\mid }\le 2\mathrm{\parallel }(x,y)-(x^{\mathrm{\prime }},y^{\mathrm{\prime }}){\mathrm{\parallel }}_2$, so the distance function is continuous. By [F2] it attains a minimum separation $\delta =\min \{\mathrm{\mid }x-y\mathrm{\mid }:x\in S_{+},y\in S_{-}\}$. This minimum is positive because a minimizing pair at distance zero would give a point in both disjoint sets. Starting at the leftmost point of $S_{+}\cup S_{-}$, repeatedly take the first point of the opposite-sign set to the right and the last current-sign point before it. These extrema exist because the level sets are compact, and each transition gives an open gap of length at least $\delta$ containing no point of $S_{+}\cup S_{-}$. The gaps are pairwise disjoint subintervals of $[a,b]$, so any $k$ transitions satisfy $k\delta \le b-a$; hence there are finitely many transitions, each with a distinct ordered gap.

If there were at least $n+1$ transitions, choosing one extremal point from each successive sign run would give $n+2$ ordered alternating points, contrary to the hypothesis. Thus the number $k$ of transitions is at most $n$. Choose one point ${\xi }_j$ in each transition gap and set $h(x)=c{\prod }_{j=1}^k(x-{\xi }_j)$, where $c\in \{-1,1\}$ is chosen so that $h$ has the sign of $e$ on the first run. The polynomial has degree $k\le n$, has no zero on $S_{+}\cup S_{-}$, and changes sign exactly when the extremal sign changes. Hence $e(x)h(x)>0$ on the entire extremal set.

Suppose that the nonzero values $p(x_i)$ alternate in sign. By [F1], $p$ is continuous on each $[x_i,x_{i+1}]$. Since the endpoint values are nonzero and have opposite signs, [F2] gives a root $z_i\in (x_i,x_{i+1})$ for every $0\le i\le n$. These open intervals are pairwise disjoint, so the $z_i$ are $n+1$ distinct real roots.

The $n+1$ distinct roots from step 1.1 contradict [F3], because $p$ is nonzero and has degree at most $n$. Therefore the assumed alternating nonzero values cannot occur.

Each denominator $t_j-t_k$ is nonzero, so every $L_j$ is a polynomial of degree at most $n$ and $L_j(t_i)$ is $1$ for $i=j$ and $0$ otherwise. The polynomial $p-{\sum }_{j}p(t_j)L_j$ has degree at most $n$ and vanishes at the $n+1$ distinct nodes; [F2] makes it the zero polynomial. This also covers $n=0$, when $L_0=1$.

Comparing the coefficients of $x^k$ in the identity of step 1.1 gives $c_k={\sum }_{j}p(t_j){\mathrm{\ell }}_{jk}$. The triangle inequality yields the stated coefficient bound.

Each $w_i\mathrm{\ne }0$. The Lagrange polynomial $L_i(t):=\omega (t)\mathrm{/}((t-x_i)w_i)$ has degree $N+1$ and values $L_i(x_j)=1$ for $j=i$ and $0$ otherwise. Thus $H(t):={\sum }_{i}g(x_i)L_i(t)$ has degree at most $N+1$ and agrees with $g$ at all $N+2$ nodes. By [F1], $H-g=0$, so $H=g$.

The coefficient of $t^{N+1}$ in $L_i$ is $1\mathrm{/}{w}_i$, while that coefficient in $g$ is $0$. Comparing the $t^{N+1}$ coefficients in $H=g$ from step 1.1 proves the displayed sum identity.

The sign of $w_i$ is $(-1{)}^{N+1-i}$, since exactly the $N+1-i$ factors with $j>i$ are negative. Hence all terms $g(x_i)\mathrm{/}{w}_i$ have one common weak sign when $\epsilon (-1{)}^{i}g(x_i)\ge 0$. Their sum is $0$ by step 2.1, so every term is $0$, and all $N+2$ values $g(x_i)$ vanish.

Since $g$ has degree at most $N$, its $N+2$ distinct roots in step 3.1 force $g=0$ by [F1].

For a nonzero quotient, let $d=\gcd (p,q)$ from [F1] and put $p_0=p\mathrm{/}d$, $q_0=q\mathrm{/}d$. Then $Ap+Bq=d$ implies $A{p}_0+B{q}_0=1$, so no nonconstant polynomial divides both $p_0$ and $q_0$. For the zero quotient, $p=0$ and division by the monic $\gcd (0,q)$ gives $(0,\mathrm{lc}(q))$; scaling by $1\mathrm{/}\mathrm{lc}(q)$ gives $(0,1)$. Any reduced pair representing zero has zero numerator and a nonzero constant denominator.

Suppose $p_0\mathrm{/}{q}_0=p_1\mathrm{/}{q}_1$ are nonzero reduced representations. By the stated equality convention, $p_0{q}_1=p_1{q}_0$. The Bézout identity $A{p}_0+B{q}_0=1$ from step 1.1, multiplied by $p_1$, shows $p_0$ divides $p_1$; multiplying the same identity by $q_1$ shows $q_0\mid q_1$. Write $p_1=h{p}_0$ and $q_1=k{q}_0$. The nonzero real leading coefficients of $p_0$ and $q_0$ have nonzero product, so $p_0{q}_0\mathrm{\ne }0$; cross-multiplication then gives $(h-k)p_0{q}_0=0$ and hence $h=k$. If $h$ were nonconstant, it would divide both $p_1$ and $q_1$, contradicting reduction. Thus $h=k$ is a nonzero real constant. The zero case is the reduced pair already identified in step 1.1.

Since $I$ is nonempty, choose $x\in I$. If the common scalar from step 2.1 is $c$, then $q_1(x)=c{q}_0(x)$ and both denominators are positive, so $c>0$. Homogeneity of the coefficient norm and $\mathrm{\parallel }{q}_0{\mathrm{\parallel }}_{\mathrm{c}\mathrm{o}\mathrm{e}\mathrm{f},2}=\mathrm{\parallel }{q}_1{\mathrm{\parallel }}_{\mathrm{c}\mathrm{o}\mathrm{e}\mathrm{f},2}=1$ give $c=1$, so the numerators agree as well.

Define the linear map $T:{\mathcal{P}}_n(I)\times \mathbb{R}\to {\mathbb{R}}^{n+2}$ by $T(p,\lambda {)}_i=p(x_i)+(-1{)}^i\lambda$. Choose a polynomial representative $P$ of $p$ using [F3] and [F4]. If $T(p,\lambda )=0$ and $\lambda =0$, then $P$ vanishes at all $n+2$ distinct nodes, so [F5] forces $P=0$ and hence $p=0$. If $\lambda \mathrm{\ne }0$, then $P(x_i)=-(-1{)}^i\lambda$ are nonzero alternating values, so $P$ is nonzero and [F1] rules this out. Thus $\ker T=\{(0,0)\}$.

The restrictions of $1,x,\dots ,x^n$ span ${\mathcal{P}}_n(I)$ by [F3] and [F4]. If a linear combination of them restricts to zero on $I$, its representing polynomial vanishes at $x_0,\dots ,x_n$. These are $n+1$ distinct roots, so [F5] makes that polynomial zero; the coefficient representation then makes every coefficient zero. Thus the restrictions are linearly independent and form a basis, so $\dim {\mathcal{P}}_n(I)=n+1$. Therefore $(1,0),(x,0),\dots ,(x^n,0),(0,1)$ is a basis of the domain, while the standard coordinate vectors form a basis of the codomain; both dimensions are $n+2$. By [F2] and step 1.1, $T$ has image dimension $n+2$ and is therefore bijective. Its equation $T(p,\lambda {)}_i=f(x_i)$ has exactly one solution.

Write $p_c(x)={\sum }_{j=0}^n{c}_j{x}^j$ for $c=(c_0,\dots ,c_n)\in {\mathbb{R}}^{n+1}$ and set $F(c)=\mathrm{\parallel }f-p_c{\mathrm{\parallel }}_{\mathrm{\infty },I}$. For $0\le j\le n$, compactness of $I$ and [F2] give $M_j:={\max }_{x\in I}\mathrm{\mid }x{\mathrm{\mid }}^j<\mathrm{\infty }$. For every $x\in I$, the triangle inequality gives $\mathrm{\mid }f(x)-p_c(x)\mathrm{\mid }\le \mathrm{\mid }f(x)-p_d(x)\mathrm{\mid }+\mathrm{\mid }{p}_d(x)-p_c(x)\mathrm{\mid }$; taking suprema and then exchanging $c,d$ yields $\mathrm{\mid }F(c)-F(d)\mathrm{\mid }\le \mathrm{\parallel }{p}_c-p_d{\mathrm{\parallel }}_{\mathrm{\infty },I}\le {\sum }_{j=0}^n\mathrm{\mid }{c}_j-d_j\mathrm{\mid }{M}_j$. Thus $F$ is continuous. The sublevel set $K:=\{c:F(c)\le \mathrm{\parallel }f{\mathrm{\parallel }}_{\mathrm{\infty },I}\}$ is closed and contains $0$.

If $c\in K$, then $\mathrm{\parallel }{p}_c{\mathrm{\parallel }}_{\mathrm{\infty },I}\le \mathrm{\parallel }f{\mathrm{\parallel }}_{\mathrm{\infty },I}+F(c)\le 2\mathrm{\parallel }f{\mathrm{\parallel }}_{\mathrm{\infty },I}$. For $n=0$, take ${\tau }_0=a$; for $n\ge 1$, take distinct nodes ${\tau }_j=a+j(b-a)\mathrm{/}n$, $0\le j\le n$. Each $\mathrm{\mid }{p}_c({\tau }_j)\mathrm{\mid }\le 2\mathrm{\parallel }f{\mathrm{\parallel }}_{\mathrm{\infty },I}$, so [F4] bounds every coefficient $c_k$ uniformly on $K$. Hence $K$ is bounded.

By [F3], the nonempty closed bounded set $K$ is compact, so the continuous function $F$ attains a minimum $\alpha$ on $K$. Since $0\in K$, $\alpha \le \mathrm{\parallel }f{\mathrm{\parallel }}_{\mathrm{\infty },I}$; every coefficient vector outside $K$ has $F(c)>\mathrm{\parallel }f{\mathrm{\parallel }}_{\mathrm{\infty },I}\ge \alpha$. Therefore $\alpha$ is the minimum over all of ${\mathbb{R}}^{n+1}$, which by [F1] is $E_n(f;I)$. The attaining polynomial is the required $p_{\ast }$.

Suppose $q\in {\mathcal{P}}_n([a,b])$ has $\mathrm{\parallel }f-q{\mathrm{\parallel }}_{\mathrm{\infty },[a,b]}<E$. At a node with $f(x_i)-p(x_i)=\sigma (-1{)}^{i}E$, the strict inequality gives $\mathrm{\mid }f(x_i)-q(x_i)\mathrm{\mid }<E$, so $q(x_i)-p(x_i)=(f(x_i)-p(x_i))-(f(x_i)-q(x_i))$ has the same nonzero sign as $\sigma (-1{)}^i$.

The polynomial $q-p$ has degree at most $n$ and, by step 1.1, has nonzero alternating signs at $n+2$ ordered nodes. This contradicts [F2]. Therefore no such $q$ exists, and $p$ is a best approximant.

Define $\mathrm{\Phi }:{\mathcal{P}}_m\times {\mathcal{P}}_n\to \mathbb{R}[x]$ by $\mathrm{\Phi }(u,v)=uq-pv$. It is linear. If $r=0$, [F1] gives $p=0,q=1,d=n,N=m$, so $\mathrm{\Phi }(u,v)=u$ and its image is exactly ${\mathcal{P}}_m={\mathcal{P}}_N$.

Suppose $r\mathrm{\ne }0$. If $(u,v)\in \ker \mathrm{\Phi }$, then $uq=pv$. Multiply the Bézout identity in [F2] by $u$: $u=Apu+Bqu=Apu+Bpv=p(Au+Bv)$, so $u=hp$ for $h:=Au+Bv$. Substitution into $uq=pv$ and cancellation of the nonzero polynomial $p$ give $v=hq$. Conversely, every $(hp,hq)$ lies in the kernel.

The degree bounds on $u=hp$ and $v=hq$, together with [F4], are equivalent to $\mathrm{deg}h\le \min (m-\mathrm{deg}p,n-\mathrm{deg}q)=d$; the zero polynomial $h$ is included. Thus the kernel has basis $(p,q),(xp,xq),\dots ,(x^{d}p,x^{d}q)$ and dimension $d+1$. By [F3] and [F5], the image dimension is $(m+n+2)-(d+1)=m+n+1-d=N+1$.

For all $u,v$, the degree of $uq-pv$ is at most $\max (m+\mathrm{deg}q,n+\mathrm{deg}p)=m+n-d=N$ by [F1] and [F4]. Hence the image is a subspace of ${\mathcal{P}}_N$, whose dimension is $N+1$ by [F5]. Its dimension from step 3.1 is also $N+1$, so the two spaces are equal.

Let $\gamma :={\min }_{x\in I}w(x)>0$ and $M:=\mathrm{\parallel }wf{\mathrm{\parallel }}_{\mathrm{\infty },I}$. Positivity of $\gamma$ follows because the continuous positive function $w$ attains its minimum on compact $I$ by [F3]. In the coefficient space for pairs $(p,q)$ of degrees at most $(m,n)$ and an extra scalar $t$, define $K$ by $\mathrm{\parallel }q{\mathrm{\parallel }}_{\mathrm{c}\mathrm{o}\mathrm{e}\mathrm{f},2}=1$, $q(x)\ge 0$ on $I$, $0\le t\le M$, and $\mathrm{\mid }w(x)(f(x)q(x)-p(x))\mathrm{\mid }\le tq(x)$ for every $x\in I$. The triple $(0,1,M)$ lies in $K$, so $K$ is nonempty.

The coefficient norm equation, the interval for $t$, and each pointwise inequality defining $K$ are closed conditions on the finite coefficient vector, so $K$ is closed. Its denominator coefficients have norm $1$, and for every $(p,q,t)\in K$, $\mathrm{\mid }p(x)\mathrm{\mid }\le (\mathrm{\mid }f(x)\mathrm{\mid }+M\mathrm{/}\gamma )q(x)$ on $I$. The coefficient norm bound gives $\mathrm{\parallel }q{\mathrm{\parallel }}_{\mathrm{\infty },I}\le {\sum }_{j=0}^n\max (\mathrm{\mid }a\mathrm{\mid },\mathrm{\mid }b\mathrm{\mid }{)}^j$, hence $\mathrm{\parallel }p{\mathrm{\parallel }}_{\mathrm{\infty },I}$ is uniformly bounded. For $m=0$, evaluation at one node bounds the sole coefficient of $p$. For $m\ge 1$, evaluate at the $m+1$ distinct nodes ${\tau }_j=a+j(b-a)\mathrm{/}m$; each value is bounded by $\mathrm{\parallel }p{\mathrm{\parallel }}_{\mathrm{\infty },I}$, so [F7] bounds every coefficient. Thus $K$ is bounded.