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 (vorgegebenen Maximalgrades ) und der gegebenen (in einem Intervall) stetigen Funktion . 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 Stützstellen im Intervall auswertet und daraus neue Stützstellen berechnet.

Algorithmus

Gegeben:Ein Intervall und eine stetige Funktion ;
ferner ein maximaler Polynomgrad .
Gesucht:Ein Polynom vom Grad höchstens , welches
   
minimiert.

Aus dem Alternantensatz folgt, dass das Polynom im Limes eindeutig bestimmt ist und dass es Punkte gibt, für die gilt

mit der Abweichung (Supremumsnorm).

Das gesuchte Polynom s​ei mit

bezeichnet. Es gilt also, die Unbekannten

zu bestimmen.

Vorbereitung

Man beginnt mit den Extremstellen des Tschebyschow-Polynoms erster Art vom Grad

  mit   .

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

.

Berechnen einer Approximation auf der Referenz

Gesucht wird das Polynom vom Grad , dessen Fehlerfunktion auf der im vorangegangenen Schritt gewonnenen Referenz alterniert. D. h. gesucht sind

  und   .

mit

  für   .

Diese Aufgabe hat als Eingabe nur die Referenz und von der Funktion nur die Werte . 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]

Damit hat man neue Koeffizienten

für das Polynom und eine neue »Referenzabweichung« .

Finden lokale Extremstellen der Fehlerfunktion mit als einem Polynom vom Grad 2

Ersetzen der Referenz durch Extremstellen

Ausgehend vom Polynom gilt es, Extremstellen der Fehlerfunktion

zu finden. Ist differenzierbar, kann man Extremstellen oft durch Nullsetzen der Ableitungsfunktion gewinnen.

In jedem Fall lässt sich das Intervall in die durch die aktuelle Fehlerfunktion spezifizierbaren Teilintervalle folgendermaßen aufteilen. Da mit auch stetig ist, gibt es nach dem Zwischenwertsatz für alle Nullstellen der Fehlerfunktion (in der Abbildung Schnittstellen der roten Funktion mit dem blauen Polynom ) im Intervall , da das Vorzeichen der Fehlerfunktion an den Stellen alterniert (). Gibt es in zwei benachbarten Intervallen und jeweils nur eine Nullstelle beziehungsweise , dann ist die Fehlerfunktion im Intervall 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 (lokale) Extremstellen . Im Ergebnis ist das erste Extremum, die nachfolgenden Extrema alternieren zwischen Maximum und Minimum bis zum letzten Extremum .

Nebenbei fällt die (absolute) Güte der Approximation in Form von an. Ist sie unbefriedigend, kann man mit der neu gewonnenen Referenz iterieren. Es kann aber auch interessant sein, den Grad 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 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 , kann aber auch in geschafft werden (s. Polynominterpolation#Newtonscher Algorithmus).
  4. René Grothmann: Skriptum Approximationstheorie. (PDF) 1.71. Bemerkung
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.