Remez-Algorithmus

Der Remez-Algorithmus in der Approximationstheorie ist ein Minimax-Approximations-Algorithmus. Als solcher minimiert er die maximale absolute Differenz zwischen dem gesuchten Polynom $p$ (vorgegebenen Maximalgrades $n$) und der gegebenen (in einem Intervall) stetigen Funktion $f$. Er ist benannt nach dem sowjetischen Mathematiker Jewgeni Jakowlewitsch Remes, der ihn im Jahr 1934 vorgestellt hat.

Der Algorithmus setzt dabei ganz wesentlich auf den Alternantensatz von Pafnuti Lwowitsch Tschebyschow, indem er iterativ die genannte Differenz an $n+2$ Stützstellen im Intervall auswertet und daraus neue $n+2$ Stützstellen berechnet.

Algorithmus

Gegeben:	Ein Intervall $[a,b]\subset \mathbb {R}$ und eine stetige Funktion $f\colon [a,b]\to \mathbb {R}$;
	ferner ein maximaler Polynomgrad $n$.
Gesucht:	Ein Polynom $p(x)\in \mathbb {R} [x]$ vom Grad höchstens $n$, welches
	$\max _{a\leq x\leq b}|f(x)-p(x)|$
	minimiert.

Aus dem Alternantensatz folgt, dass das Polynom im Limes eindeutig bestimmt ist und dass es $n+2$ Punkte $(a\leq )\;x_{0}<x_{1}<\ldots <x_{n+1}\;(\leq b)$ gibt, für die gilt

$f(x_{i})-p(x_{i})=\pm (-1)^{i}\cdot E$

mit der Abweichung $E:=\max _{a\leq x\leq b}|f(x)-p(x)|=\|f-p\|_{\infty }$ (Supremumsnorm).

Das gesuchte Polynom sei mit

$p(x)=:c_{0}+c_{1}\cdot x+\,...\,+c_{n}\cdot x^{n}$

bezeichnet. Es gilt also, die $n+1$ Unbekannten

$c_{0},c_{1},\ldots ,c_{n}$

zu bestimmen.

Vorbereitung

Man beginnt mit den Extremstellen des Tschebyschow-Polynoms erster Art vom Grad $n+1$

$x_{i}={\frac {a+b}{2}}-{\frac {b-a}{2}}\cdot \cos \left({\frac {i\pi }{n+1}}\right)$   mit   $i=0,\ldots ,n+1$.

Ein solcher Satz von Punkten wird „Referenz“ genannt. Es ist

$a=x_{0}<x_{1}<\,...\,<x_{n+1}=b$.

Iteration

Berechnen einer Approximation auf der Referenz

Gesucht wird das Polynom $p(x)$ vom Grad $\leq n$, dessen Fehlerfunktion $f(x)-p(x)$ auf der im vorangegangenen Schritt gewonnenen Referenz $x_{0}<x_{1}<\dots <x_{n+1}$ alterniert. D. h. gesucht sind

$c_{0},c_{1},\ldots ,c_{n}$   und   $E$.

mit

$p(x_{i})+(-1)^{i}\cdot E=f(x_{i})$   für   $i=0,\ldots ,n+1$.

Diese Aufgabe hat als Eingabe nur die Referenz und von der Funktion $f$ nur die $n+2$ Werte $f(x_{i})$. Sie kann auch als Optimierungsaufgabe formuliert werden, nämlich als beste Approximation auf der Referenz, und ist eindeutig lösbar.

Das zu lösende Gleichungssystem in Matrixdarstellung:

$\left({\begin{matrix}1&x_{0}&\cdots &x_{0}^{n}&1\\1&x_{1}&\cdots &x_{1}^{n}&-1\\\vdots &\vdots &\vdots &\vdots &\vdots \\1&x_{n}&\cdots &x_{n}^{n}&(-1)^{n}\\1&x_{n+1}&\cdots &x_{n+1}^{n}&(-1)^{n+1}\\\end{matrix}}\right){\begin{pmatrix}c_{0}\\c_{1}\\\vdots \\c_{n}\\E\end{pmatrix}}={\begin{pmatrix}f(x_{0})\\f(x_{1})\\\vdots \\f(x_{n})\\f(x_{n+1})\\\end{pmatrix}}$

Damit hat man $n+1$ neue Koeffizienten

$c_{0},c_{1},\ldots ,c_{n}$

für das Polynom $p(x)$ und eine neue »Referenzabweichung« $E$.

Finden lokale Extremstellen ${\tilde {x}}_{1},{\tilde {x}}_{2}$ der Fehlerfunktion $1/(37/12-x)-p(x)$ mit ${\color {Blue}p}$ als einem Polynom vom Grad 2

Ersetzen der Referenz durch Extremstellen

Ausgehend vom Polynom $p(x)$ gilt es, $n+2$ Extremstellen ${\tilde {x}}_{0},{\tilde {x}}_{1},\ldots ,{\tilde {x}}_{n+1}$ der Fehlerfunktion

$f(x)-p(x)$

zu finden. Ist $f$ differenzierbar, kann man Extremstellen oft durch Nullsetzen der Ableitungsfunktion $f'-p'$ gewinnen.

In jedem Fall lässt sich das Intervall $[a,b]$ in die durch die aktuelle Fehlerfunktion spezifizierbaren Teilintervalle $[s_{i},s_{i+1}]$ folgendermaßen aufteilen. Da mit $f$ auch $f-p$ stetig ist, gibt es nach dem Zwischenwertsatz für alle $i=1,\ldots ,n+1$ Nullstellen $s_{i}$ der Fehlerfunktion (in der Abbildung Schnittstellen der roten Funktion $f$ mit dem blauen Polynom $p$) im Intervall $[x_{i-1},x_{i}]$, da das Vorzeichen der Fehlerfunktion an den Stellen $x_{i}$ alterniert ($\operatorname {sgn}(f-p)(x_{i-1})=-\operatorname {sgn}(f-p)(x_{i})$). Gibt es in zwei benachbarten Intervallen $[x_{i-1},x_{i}]$ und $[x_{i},x_{i+1}]$ jeweils nur eine Nullstelle $s_{i}\in [x_{i-1},x_{i}]$ beziehungsweise $s_{i+1}\in [x_{i},x_{i+1}]$, dann ist die Fehlerfunktion im Intervall $[s_{i},s_{i+1}]$ nur nicht-negativ oder nur nicht-positiv. (Aber auch wenn es mehrere Nullstellen gibt, gilt das Weitere – die Extrema sind ggf. nur nicht so ausgeprägt.) Wegen der Stetigkeit der Fehlerfunktion gibt es nach dem Satz vom Minimum und Maximum in jedem Teilintervall $[s_{i},s_{i+1}]$ (lokale) Extremstellen ${\tilde {x}}_{i}$. Im Ergebnis ist ${\tilde {x}}_{0}:=a$ das erste Extremum, die nachfolgenden Extrema alternieren zwischen Maximum und Minimum bis zum letzten Extremum ${\tilde {x}}_{n+1}:=b$.

Nebenbei fällt die (absolute) Güte der Approximation in Form von $\max _{i}|f({\tilde {x}}_{i})-p({\tilde {x}}_{i})|$ an. Ist sie unbefriedigend, kann man mit der neu gewonnenen Referenz ${\tilde {x}}_{0},{\tilde {x}}_{1},\ldots ,{\tilde {x}}_{n+1}$ iterieren. Es kann aber auch interessant sein, den Grad $n$ der Approximation durch Einfügen von Zwischenpunkten in die Referenz zu erhöhen. Das Beispiel 2 im Artikel Alternantensatz zeigt, wie die Qualität der dortigen besten Approximation vom Polynomgrad abhängt.

Konvergenzgeschwindigkeit

Unter geeigneten Voraussetzungen, die Funktion $f$ betreffend, konvergiert das Verfahren lokal quadratisch.

Literatur

• Leçons sur l’approximation des fonctions d’une variable réelle. Gauthier-Villars, Paris 1919, 1952; archive.org
• C. de Boor, A. Pinkus: Proof of the conjectures of Bernstein and Erdös concerning the optimal nodes for polynomial interpolation. In: Journal of Approximation Theory. 24. Jahrgang, 1978, S. 289–303, doi:10.1016/0021-9045(78)90014-X.