Der Remez-Algorithmus

14

Der Remez-Algorithmus ist eine bekannte iterative Routine zur Approximation einer Funktion durch ein Polynom in der Minimax-Norm. Aber, wie Nick Trefethen [1] dazu sagt:

Die meisten dieser [Implementierungen] reichen viele Jahre zurück und in der Tat lösen die meisten von ihnen nicht das allgemeine Problem der besten Näherung, wie oben dargestellt, sondern Varianten, die diskrete Variablen oder digitale Filterung beinhalten. Man kann ein paar andere Computerprogramme im Umlauf finden, aber insgesamt scheint es derzeit kein weit verbreitetes Programm für die Berechnung der besten Annäherungen zu geben.

Man kann die Minimax-Lösung auch durch Anwendung von Least-Squares oder konvexer Optimierung berechnen, beispielsweise mit Matlab und der kostenlosen CVX-Toolbox, die auf die Runge-Funktion unter [-1, 1] angewendet wird:

m = 101; n = 11;            % 101 points, polynomial of degree 10
xi = linspace(-1, 1, m);    % equidistant points in [-1, 1]
ri = 1 ./ (1+(5*xi).^2);    % Runge function

tic                         % p is the polynomial of degree (n-1)
cvx_begin                   % minimize the distance in all points
    variable p(n);
    minimize( max(abs(polyval(p, xi) - ri)) );
cvx_end
toc                         % 0.17 sec for Matlab, CVX and SeDuMi

Die Approximation mit Chebyshev-Polynomen hat eine Minimax-Norm von, 0.1090während dieser Ansatz hier ein Minimum von 0.0654demselben Wert erreicht, der mit dem Remez-Algorithmus in der Matlab- chebfunToolbox berechnet wird .

Gibt es einen Vorteil bei der Anwendung des komplizierteren Remez-Algorithmus, wenn Sie die Minimax-Lösung mit einem Optimierungslöser schneller und genauer berechnen können? Gibt es Berichte / Artikel, die diese beiden Ansätze zu einigen schwierigen Problemen oder Testfällen vergleichen?

-
[1] R. Pachön und LN Trefethen. BIT Numerical Mathematics (2008) Bd. 46.

Hans W.
quelle

Antworten:

4

Die "richtige" Antwort hängt stark davon ab, wofür Sie Ihren Näherungswert benötigen. Benötigen Sie wirklich die beste Annäherung für eine Fehlergrenze? Oder nur eine gute Annäherung? Oder nur eine gute Annäherung im Minmax-Sinne?

Nick Trefethen gab kürzlich ein schönes Beispiel, in dem die Remez-Approximation eine schlechte Idee ist, da sie den maximalen Fehler unabhängig vom durchschnittlichen Fehler über das gesamte Intervall minimiert, was möglicherweise nicht das ist, was Sie wollen. Natürlich kann der maximale Fehler groß sein, aber dies ist für reibungslose Funktionen begrenzt.

Aktualisieren

Im Anschluss an die Diskussion in den Kommentaren unten habe ich die CVX Toolbox heruntergeladen und einen direkten Vergleich mit dem Chebfun Remez-Algorithmus durchgeführt (Haftungsausschluss: Ich bin Teil des Chebfun-Entwicklungsteams):

% Do the convex optimization bit.
m = 101; n = 11;            % 101 points, polynomial of degree 10
xi = linspace(-1, 1, m);    % equidistant points in [-1, 1]
ri = 1 ./ (1+(5*xi).^2);    % Runge function

tic                         % p is the polynomial of degree (n-1)
cvx_begin                   % minimize the distance in all points
    variable p(n);
    minimize( max(abs(polyval(p, xi) - ri)) );
cvx_end
toc_or = toc                % 0.17 sec for Matlab, CVX and SeDuMi

% Extract a Chebfun from the result
x = chebfun( [-1,1] );
A = [ chebfun(1) , x ];
for k=3:n, A(:,k) = A(:,k-1).*x; end
or = A * flipud(p)

% Make a chebfun of Runge's function
f = chebfun( @(x) 1 ./ ( 1 + 25*x.^2 ) )

% Get the best approximation using Remez
tic, cr = remez( f , 10 ); toc_cr = toc

% Get the maximum error in each case
fprintf( 'maximum error of convex optimization: %e (%f s)\n' , norm( f - or , inf ) , toc_or );
fprintf( 'maximum error of chebfun remez: %e (%f s)\n' , norm( f - cr , inf ) , toc_cr );

% Plot the two error curves
plot( [ f - cr , f - or ] );
legend( 'chebfun remez' , 'convex optimization' );

Nach viel Ausgabe erhalte ich auf meinem Laptop mit Matlab 2012a die CVX-Version 1.22 und Chebfuns neuesten SVN-Schnappschuss:

maximum error of convex optimization: 6.665479e-02 (0.138933 s)
maximum error of chebfun remez: 6.592293e-02 (0.309443 s)

Beachten Sie, dass das fzur Messung des Fehlers verwendete Chebfun auf 15 Stellen genau ist. Chebfuns Remez dauert also doppelt so lange, aber es tritt ein kleinerer globaler Fehler auf. Es sollte darauf hingewiesen werden, dass CVX kompilierten Code für die Optimierung verwendet, während Chebfun zu 100% natives Matlab ist. Der minimale Fehler von 0.00654ist der minimale Fehler "auf dem Gitter", außerhalb dieses Gitters kann der Fehler bis zu sein 0.00659. Das Vergrößern des Rasters m = 1001bekomme ich hin

maximum error of convex optimization: 6.594361e-02 (0.272887 s)
maximum error of chebfun remez: 6.592293e-02 (0.319717 s)

dh fast die gleiche Geschwindigkeit, aber die diskrete Optimierung ist ab der vierten Dezimalstelle noch schlechter. Schließlich wird die Rastergröße weiter vergrößert, bis m = 10001ich sie erhalte

maximum error of convex optimization: 6.592300e-02 (5.177657 s)
maximum error of chebfun remez: 6.592293e-02 (0.312316 s)

dh die diskrete Optimierung ist jetzt mehr als zehnmal langsamer und ab der sechsten Stelle noch schlechter.

Das Fazit ist, dass Remez Ihnen das global optimale Ergebnis liefert. Obwohl das diskrete Analog auf kleinen Gittern schnell ist, liefert es kein korrektes Ergebnis.

Pedro
quelle
Und N. Trefethen betonte dasselbe und gab ein ähnliches Beispiel in dem Artikel, den ich zitierte. Die Frage war nicht die beste Annäherung, sondern: Was ist der Vorteil des Remez-Algorithmus (heutzutage), wenn Sie mit einem vernünftigen konvexen Löser dasselbe Ergebnis erzielen können ?
Hans W.
1
@HansWerner, tut mir leid, ich habe deine Frage falsch verstanden. Ihr Konvexlöser liefert nicht das gleiche Ergebnis, zumindest nicht für alle Ziffern. Wenn ich Ihren konvexen Code richtig verstehe, minimieren Sie den maximalen Fehler über eine diskrete Menge von Punkten. Dies ist eine gute Annäherung an die Minimierung des globalen Maximalfehlers, aber nicht gleichbedeutend damit.
Pedro
Der konvexe Löser ergab in diesem Fall ein besseres Ergebnis. Denken Sie daran, der Remez-Algorithmus ist eine iterative Prozedur, die einer Optimierungsroutine sehr ähnlich ist und auch kein genaues Ergebnis liefert. Im obigen konkreten Fall war die Lösung aus der Optimierung besser, dh hatte eine insgesamt kleinere maximale Norm als das Ergebnis der besten Remez-Implementierung, die ich kenne. Die Frage ist noch offen .
Hans W.
@HansWerner, wie haben Sie den maximalen Fehler der mit dem Konvexlöser erhaltenen Lösung gemessen? Der Remez-Algorithmus chebfunsollte iterieren, bis das Minimum an Maschinengenauigkeit (in gewissem Sinne) erreicht ist.
Pedro
Nicht unbedingt; Es gibt Optionen wie 'tol' (relative Toleranz) oder 'maxiter' für chebfun/remez, aber es gibt ähnliche Optionen für alle Arten von Optimierungslösern. In gewisser Weise könnte man sagen, Remez ist eine Optimierungsroutine, die auf eine bestimmte Aufgabe spezialisiert ist. Und die Frage ist: Haben die Allzwecklöser aufgeholt und es besteht keine Notwendigkeit mehr für einen solchen spezialisierten Löser? Natürlich kann ich mich irren.
Hans W.