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 ${\displaystyle p}$ (vorgegebenen Maximalgrades ${\displaystyle n}$) und der gegebenen (in einem Intervall) stetigen Funktion ${\displaystyle f}$. Er ist benannt nach dem sowjetischen Mathematiker Jewgeni Jakowlewitsch Remes, der ihn im Jahr 1934 vorgestellt hat.[1]

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

Algorithmus

Gegeben:	Ein Intervall ${\displaystyle [a,b]\subset \mathbb {R} }$ und eine stetige Funktion ${\displaystyle f\colon [a,b]\to \mathbb {R} }$;
	ferner ein maximaler Polynomgrad ${\displaystyle n}$.
Gesucht:	Ein Polynom ${\displaystyle p(x)\in \mathbb {R} [x]}$ vom Grad höchstens ${\displaystyle n}$, welches
	${\displaystyle \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 ${\displaystyle n+2}$ Punkte ${\displaystyle (a\leq )\;x_{0}<x_{1}<\ldots <x_{n+1}\;(\leq b)}$ gibt, für die gilt

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

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

Das gesuchte Polynom s​ei mit

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

bezeichnet. Es gilt also, die ${\displaystyle n+1}$ Unbekannten

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

zu bestimmen.

Vorbereitung

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

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

Ein solcher Satz v​on Punkten w​ird „Referenz“[2] genannt. Es ist

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

Berechnen einer Approximation auf der Referenz

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

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

mit

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

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

Das z​u lösende Gleichungssystem i​n Matrixdarstellung:[3]

${\displaystyle \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 ${\displaystyle n+1}$ neue Koeffizienten

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

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

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

Ersetzen der Referenz durch Extremstellen

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

${\displaystyle f(x)-p(x)}$

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

In jedem Fall lässt sich das Intervall ${\displaystyle [a,b]}$ in die durch die aktuelle Fehlerfunktion spezifizierbaren Teilintervalle ${\displaystyle [s_{i},s_{i+1}]}$ folgendermaßen aufteilen. Da mit ${\displaystyle f}$ auch ${\displaystyle f-p}$ stetig ist, gibt es nach dem Zwischenwertsatz für alle ${\displaystyle i=1,\ldots ,n+1}$ Nullstellen ${\displaystyle s_{i}}$ der Fehlerfunktion (in der Abbildung Schnittstellen der roten Funktion ${\displaystyle f}$ mit dem blauen Polynom ${\displaystyle p}$) im Intervall ${\displaystyle [x_{i-1},x_{i}]}$, da das Vorzeichen der Fehlerfunktion an den Stellen ${\displaystyle x_{i}}$ alterniert (${\displaystyle \operatorname {sgn}(f-p)(x_{i-1})=-\operatorname {sgn}(f-p)(x_{i})}$). Gibt es in zwei benachbarten Intervallen ${\displaystyle [x_{i-1},x_{i}]}$ und ${\displaystyle [x_{i},x_{i+1}]}$ jeweils nur eine Nullstelle ${\displaystyle s_{i}\in [x_{i-1},x_{i}]}$ beziehungsweise ${\displaystyle s_{i+1}\in [x_{i},x_{i+1}]}$, dann ist die Fehlerfunktion im Intervall ${\displaystyle [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 ${\displaystyle [s_{i},s_{i+1}]}$ (lokale) Extremstellen ${\displaystyle {\tilde {x}}_{i}}$. Im Ergebnis ist ${\displaystyle {\tilde {x}}_{0}:=a}$ das erste Extremum, die nachfolgenden Extrema alternieren zwischen Maximum und Minimum bis zum letzten Extremum ${\displaystyle {\tilde {x}}_{n+1}:=b}$.

Nebenbei fällt die (absolute) Güte der Approximation in Form von ${\displaystyle \max _{i}|f({\tilde {x}}_{i})-p({\tilde {x}}_{i})|}$ an. Ist sie unbefriedigend, kann man mit der neu gewonnenen Referenz ${\displaystyle {\tilde {x}}_{0},{\tilde {x}}_{1},\ldots ,{\tilde {x}}_{n+1}}$ iterieren. Es kann aber auch interessant sein, den Grad ${\displaystyle 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 ${\displaystyle f}$ betreffend, konvergiert das Verfahren lokal quadratisch.[4]

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, 1978, S. 289–303. doi:10.1016/0021-9045(78)90014-X.

Einzelnachweise und Anmerkungen

1. E. Ya. Remez: Sur la détermination des polynômes d’approximation de degré donnée. In: Comm. Soc. Math. Kharkov, 1934, 10, S. 41.
   Sur un procédé convergent d’approximations successives pour déterminer les polynômes d’approximation. In: Compt. Rend. Acad. Sc., 1934, 198, S. 2063
   Sur le calcul effectiv des polynômes d’approximation de Tschebyscheff. In: Compt. Rend. Acad. Sc., 1934, 199, S. 337–340.
2. René Grothmann: Skriptum Approximationstheorie. (PDF) 1.69. Definition
3. Die angegebene Matrix hat Vandermonde-Matrizen als Untermatrizen.
   Die Lösung des Gleichungssystems kostet bei vielen Standardpaketen ${\displaystyle {\mathcal {O}}(n^{3})}$, kann aber auch in ${\displaystyle {\mathcal {O}}(n^{2})}$ geschafft werden (s. Polynominterpolation#Newtonscher Algorithmus).
4. René Grothmann: Skriptum Approximationstheorie. (PDF) 1.71. Bemerkung