Zum Inhalt springen

Remez-Algorithmus

aus Wikipedia, der freien Enzyklopädie

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

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

Algorithmus[Bearbeiten]

Gegeben
Ein Intervall <math>[a,b] \subset\R</math> und eine stetige Funktion <math>f\colon[a,b]\to \R</math>; ferner ein maximaler Polynomgrad <math>n</math>.
Gesucht
Ein Polynom <math>p(x) \in \R[x]</math> vom Grad höchstens <math>n</math>, welches
<math>\max_{a\le x\le b}|f(x)-p(x)|</math>
minimiert.

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

<math>f(x_i) - p(x_i) = \pm (-1)^i \cdot E </math>

mit der Abweichung <math>E:=\max_{a\le x\le b}|f(x)-p(x)|= \| f - p \|_\infty</math> (Supremumsnorm).

Das gesuchte Polynom sei mit

<math>p(x) =: c_0 + c_1 \cdot x + \, \cdots \, + c_n \cdot x^n </math>

bezeichnet. Es gilt also, die <math>n+1</math> Unbekannten

<math>c_0 , c_1 , \ldots , c_n</math>

zu bestimmen.

Vorbereitung[Bearbeiten]

Man beginnt mit den Extremstellen des Tschebyschow-Polynoms erster Art vom Grad <math>n+1</math>

<math>x_i = \frac{a+b}{2} - \frac{b-a}{2} \cdot \cos\left(\frac{i\pi}{n+1}\right)</math>   mit   <math>i=0,\ldots,n+1</math>.

Ein solcher Satz von Punkten wird „Referenz“<ref>René Grothmann: Skriptum Approximationstheorie. (PDF) 1.69. Definition</ref> genannt. Es ist

<math>a=x_0 < x_1 < \, ... \, < x_{n+1}=b</math>.

Iteration[Bearbeiten]

Berechnen einer Approximation auf der Referenz[Bearbeiten]

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

<math>c_0 , c_1 , \ldots , c_n</math>   und   <math>E </math>.

mit

<math>p(x_i) + (-1)^i \cdot E = f(x_i)</math>   für   <math>i=0,\ldots,n+1</math>.

Diese Aufgabe hat als Eingabe nur die Referenz und von der Funktion <math>f</math> nur die <math>n+2 </math> Werte <math>f(x_i) </math>. 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:<ref>Die angegebene Matrix hat Vandermonde-Matrizen als Untermatrizen.
Die Lösung des Gleichungssystems kostet bei vielen Standardpaketen <math>\mathcal{O}(n^3)</math>, kann aber auch in <math>\mathcal{O}(n^2)</math> geschafft werden (s. Polynominterpolation#Newtonscher Algorithmus).</ref>

<math>

\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}</math> Damit hat man <math>n+1</math> neue Koeffizienten

<math>c_0 , c_1 , \ldots , c_n</math>

für das Polynom <math>p(x)</math> und eine neue »Referenzabweichung« <math>E </math>.

Datei:Remez-Approximation.svg
Finden lokale Extremstellen <math>\tilde{x}_1 , \tilde{x}_2</math> der Fehlerfunktion <math>1/(37/12-x) - p(x)</math> mit <math> {\color{Blue}p}</math> als einem Polynom vom Grad 2

Ersetzen der Referenz durch Extremstellen[Bearbeiten]

Ausgehend vom Polynom <math>p(x)</math> gilt es, <math>n+2</math> Extremstellen <math>\tilde{x}_0 , \tilde{x}_1 , \ldots , \tilde{x}_{n+1}</math> der Fehlerfunktion

<math>f(x) - p(x) </math>

zu finden. Ist <math>f</math> differenzierbar, kann man Extremstellen oft durch Nullsetzen der Ableitungsfunktion <math>f'-p'</math> gewinnen.

In jedem Fall lässt sich das Intervall <math>[a,b]</math> in die durch die aktuelle Fehlerfunktion spezifizierbaren Teilintervalle <math>[s_i,s_{i+1}]</math> folgendermaßen aufteilen. Da mit <math>f</math> auch <math>f-p</math> stetig ist, gibt es nach dem Zwischenwertsatz für alle <math>i=1,\ldots,n+1</math> Nullstellen <math>s_i</math> der Fehlerfunktion (in der Abbildung Schnittstellen der roten Funktion <math>f</math> mit dem blauen Polynom <math>p</math>) im Intervall <math>[x_{i-1},x_i]</math>, da das Vorzeichen der Fehlerfunktion an den Stellen <math>x_i</math> alterniert Gibt es in zwei benachbarten Intervallen <math>[x_{i-1},x_i]</math> und <math>[x_i,x_{i+1}]</math> jeweils nur eine Nullstelle <math>s_i\in [x_{i-1},x_i]</math> beziehungsweise <math>s_{i+1}\in [x_i,x_{i+1}]</math>, dann ist die Fehlerfunktion im Intervall <math>[s_i,s_{i+1}]</math> 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 <math>[s_i,s_{i+1}]</math> (lokale) Extremstellen <math>\tilde{x}_i</math>. Im Ergebnis ist <math>\tilde{x}_0:=a</math> 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 <math>\max_i |f(\tilde{x}_i)-p(\tilde{x}_i)|</math> an. Ist sie unbefriedigend, kann man mit der neu gewonnenen Referenz <math>\tilde{x}_0 , \tilde{x}_1 , \ldots , \tilde{x}_{n+1}</math> iterieren. Es kann aber auch interessant sein, den Grad <math> n </math> 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[Bearbeiten]

Unter geeigneten Voraussetzungen, die Funktion <math>f</math> betreffend, konvergiert das Verfahren lokal quadratisch.<ref>René Grothmann: Skriptum Approximationstheorie. (PDF) 1.71. Bemerkung</ref>

Literatur[Bearbeiten]

Einzelnachweise und Anmerkungen[Bearbeiten]

<references />

Abgerufen von „https://wiki.kertz.ch/index.php?title=Remez-Algorithmus&oldid=3938399“