L'algorithme Remez

L'algorithme de Remez est une routine itérative bien connue pour approximer une fonction par un polynôme dans la norme minimax. Mais, comme le dit Nick Trefethen [1]:

La plupart de ces [implémentations] remontent à plusieurs années et en fait, la plupart d'entre elles ne résolvent pas le problème général de meilleure approximation tel que posé ci-dessus mais des variantes impliquant des variables discrètes ou un filtrage numérique. On peut trouver quelques autres programmes informatiques en circulation, mais dans l'ensemble, il semble qu'il n'y ait actuellement aucun programme largement utilisé pour calculer les meilleures approximations.

On peut également calculer la solution minimax en appliquant une optimisation par moindres carrés ou convexe, par exemple en utilisant Matlab et la boîte à outils CVX gratuite appliquée à la fonction Runge sur [-1, 1]:

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

L'approximation avec les polynômes de Chebyshev a une norme minimax 0.1090tandis que cette approche atteint ici un minimum de 0.0654, la même valeur qui est calculée avec l'algorithme Remez dans la chebfunboîte à outils Matlab .

Y a-t-il un avantage à appliquer l'algorithme Remez plus compliqué si vous pouvez calculer la solution minimax plus rapidement et plus précisément avec un solveur d'optimisation? Existe-t-il des rapports / articles comparant ces deux approches sur des problèmes difficiles ou des cas de test?

-
[1] R. Pachon et LN Trefethen. BIT Numerical Mathematics (2008) Vol. 46.

La «bonne» réponse dépend fortement de ce dont vous avez besoin pour votre approximant. Avez-vous vraiment besoin de la meilleure approximation pour une erreur liée? Ou juste une bonne approximation? Ou juste une bonne approximation au sens minmax?

Nick Trefethen a récemment donné un bel exemple où l'approximation de Remez est une mauvaise idée car elle minimise l'erreur maximale indépendamment de l'erreur moyenne sur tout l'intervalle, ce qui n'est peut-être pas ce que vous voulez. Bien sûr, l'erreur maximale peut être importante, mais elle est limitée pour les fonctions fluides.

Mise à jour

Suite à la discussion dans les commentaires ci-dessous, j'ai téléchargé la boîte à outils CVX et fait une comparaison directe avec l'algorithme Chebfun Remez (avertissement: je fais partie de l'équipe de développement Chebfun):

% 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' );

Après beaucoup de sortie, j'obtiens, sur mon ordinateur portable avec Matlab 2012a, la version 1.22 de CVX et le dernier instantané SVN de Chebfun:

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

Notez que le Chebfun futilisé pour mesurer l'erreur est précis à 15 chiffres. Donc, Remez de Chebfun prend deux fois plus de temps, mais obtient une erreur globale plus petite. Il convient de noter que CVX utilise du code compilé pour l'optimisation alors que Chebfun est 100% natif Matlab. L'erreur minimale de 0.00654est l'erreur minimale «sur la grille», hors de cette grille, l'erreur peut aller jusqu'à 0.00659. Augmenter la taille de la grille pour m = 1001obtenir

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

c'est-à-dire presque à la même vitesse, mais l'optimisation discrète est encore pire à partir du quatrième chiffre décimal. Enfin, en augmentant encore la taille de la grille pour m = 10001obtenir

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

c'est-à-dire que l'optimisation discrète est maintenant plus de dix fois plus lente et est encore pire à partir du sixième chiffre.

L'essentiel est que Remez vous obtiendra le résultat globalement optimal. Bien que l'analogique discret puisse être rapide sur de petites grilles, il ne donnera pas un résultat correct.