Finite-budget polynomial Remez exchange with an exact extrema oracle

Inputs. A nondegenerate interval $I=[a,b]$, a degree $n\ge 0$, a continuous real function $f$ on $I$, an integer exchange budget $B\in {\mathbb{N}}_0$, and an initial reference $X=(x_0,\dots ,x_{n+1})$ with $a\le x_0<\cdots <x_{n+1}\le b$. Also supply an exact extrema oracle for a polynomial candidate $p$. On each call it returns one of:

• alternation$(E,y_0,\dots ,y_{n+1})$, only when $E=\mathrm{\parallel }f-p{\mathrm{\parallel }}_{\mathrm{\infty },I}$ and the returned ordered distinct nodes lie in $I$ and satisfy $f(y_i)-p(y_i)=\sigma (-1{)}^{i}E$ for one fixed sign $\sigma$;
• maximum$(E,y)$, only when $y\in I$, $E=\mathrm{\parallel }f-p{\mathrm{\parallel }}_{\mathrm{\infty },I}$ and $\mathrm{\mid }f(y)-p(y)\mathrm{\mid }=E$; or
• inconclusive, when neither exact certificate can be returned.

Procedure. For $k=0,\dots ,B$, solve the unique real linear system $p_k(x_i)+(-1{)}^i{\lambda }_k=f(x_i),0\le i\le n+1,$ for $p_k\in {\mathcal{P}}_n(I)$ and ${\lambda }_k\in \mathbb{R}$, using The Remez alternation linear system has a unique solution. Query the oracle for $p_k$. If it returns alternation$(0,Y)$ or maximum$(0,y)$, return exact$(p_k)$, since either response certifies zero uniform error. If it returns alternation$(E,Y)$ with $E>0$, return certified$(p_k,E,Y)$; the optimality claim is discharged by Exact polynomial equioscillation certifies best approximation. If it returns inconclusive, return oracle-inconclusive. If it returns maximum$(E,y)$ with $E>0$ and $E=\mathrm{\mid }{\lambda }_k\mathrm{\mid }$, return certified$(p_k,E,X)$, because the solved equations make $X$ an alternating set and the oracle certifies the global norm. If ${\lambda }_k=0<E$, return zero-level-no-exchange. If $k=B$, return budget-exhausted with $p_k$ and the current reference $X$ before attempting an exchange.

In the remaining case, let $s=\mathrm{sgn}(f(y)-p_k(y))$. Find the smallest index $i$ for which $s=\mathrm{sgn}({\lambda }_k)(-1{)}^i$ and replacing $x_i$ by $y$ preserves a strictly increasing reference tuple under these tests: for $i=0$, require $a\le y<x_1$; for $i=n+1$, require $x_n<y\le b$; and for $0<i<n+1$, require $x_{i-1}<y<x_{i+1}$. Thus a global maximum at an endpoint may replace the corresponding endpoint reference node, while distinctness and strict ordering are retained. Replace $x_i$ by $y$ and continue. If no such index exists, return no-order-preserving-exchange.

Outputs. The procedure returns an exact best-approximation certificate, an exact zero-error candidate, or one of the explicit inconclusive, zero-level, no-exchange, or budget statuses. It asserts no convergence of the iterates. Any implementation must ensure each exact solve and oracle call terminates.