Алгоритм Ремеза

14

Алгоритм Ремеза - это хорошо известная итерационная процедура для приближения функции полиномом в минимаксной норме. Но, как говорит Ник Трефетен [1]:

Большинство из этих [реализаций] уходят в прошлое на многие годы, и на самом деле, большинство из них не решают общую проблему наилучшего приближения, как изложено выше, а представляют собой варианты с дискретными переменными или цифровой фильтрацией. Можно найти несколько других компьютерных программ в обращении, но в целом, кажется, что в настоящее время нет широко используемой программы для вычисления наилучших приближений.

Минимаксное решение можно вычислить также, применяя метод наименьших квадратов или выпуклую оптимизацию, например, используя Matlab и бесплатный набор инструментов CVX, примененный к функции Рунге в [-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

Приближение с полиномами Чебышева имеет минимаксную норму, в 0.1090то время как этот подход здесь достигает минимума 0.0654, того же значения, которое вычисляется с помощью алгоритма Ремеза в chebfunнаборе инструментов Matlab .

Есть ли преимущество в применении более сложного алгоритма Ремеза, если вы можете быстрее и точнее вычислить минимаксное решение с помощью решателя оптимизации? Существуют ли какие-либо отчеты / статьи, сравнивающие эти два подхода по некоторым сложным проблемам или контрольным случаям?

-
[1] Р. Пачон и Л. Н. Трефетен. БИТ Численная математика (2008) Том. 46.

Ханс В.
источник

Ответы:

4

«Правильный» ответ сильно зависит от того, для чего вам нужен ваш пример. Вы действительно нуждаетесь в лучшем приближении для некоторой ошибки? Или просто хорошее приближение? Или просто хорошее приближение в смысле minmax?

Ник Трефетен недавно привел хороший пример, где аппроксимация Ремеза - плохая идея, поскольку она сводит к минимуму максимальную ошибку независимо от средней ошибки по всему интервалу, что может быть не тем, что вы хотите. Конечно, максимальная ошибка может быть большой, но это ограничено для гладких функций.

Обновить

После обсуждения в комментариях ниже я скачал набор инструментов CVX и провел прямое сравнение с алгоритмом Chebfun Remez (отказ от ответственности: я являюсь частью команды разработчиков 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' );

После большого количества выходных данных я получаю на своем ноутбуке с Matlab 2012a версию CVX 1.22 и последний снимок SVN от Chebfun:

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

Обратите внимание, что Chebfun fиспользуется для измерения ошибки с точностью до 15 цифр. Так что Remez от Chebfun занимает вдвое больше времени, но получает меньшую глобальную ошибку. Следует отметить, что CVX использует скомпилированный код для оптимизации, тогда как Chebfun является на 100% нативным Matlab. Минимальная ошибка 0.00654- это минимальная ошибка «на сетке», вне этой сетки ошибка может быть до 0.00659. Увеличение размера сетки, чтобы m = 1001я получил

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

почти такая же скорость, но дискретная оптимизация все еще хуже, чем с четвертой десятичной цифрой. Наконец, увеличив размер сетки дальше, чтобы m = 10001получить

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

т.е. дискретная оптимизация теперь более чем в десять раз медленнее и все еще хуже с шестой цифрой.

Суть в том, что Remez даст вам глобально оптимальный результат. Хотя дискретный аналог может быть быстрым на небольших сетках, он не даст правильного результата.

Pedro
источник
И Н. Трефетен подчеркивал то же самое и приводил аналогичный пример в статье, которую я цитировал. Вопрос был не о наилучшем приближении, а о том, каково преимущество алгоритма Ремеза (в настоящее время), если вы можете получить тот же результат с помощью разумного выпуклого решателя ?
Ганс В.
1
@HansWerner, извини, я неправильно понял твой вопрос. Ваш выпуклый решатель не дает вам тот же результат, по крайней мере, не для всех цифр. Если я правильно понимаю ваш выпуклый код, вы минимизируете максимальную ошибку по дискретному набору точек. Это хорошее приближение - но не то же самое, что - минимизация глобальной максимальной ошибки.
Педро
Выпуклый решатель в этом случае дал лучший результат. Подумайте об этом, алгоритм Ремеза - это итеративная процедура, очень похожая на процедуру оптимизации, которая также не даст точного результата. В конкретном случае выше, решение от оптимизации было лучше, т.е. имело в целом меньшую максимальную норму, чем результат от лучшей реализации Remez, которую я знаю. Вопрос все еще открыт .
Ганс В.
@ HansWerner, как вы измерили максимальную ошибку решения, полученного с помощью выпуклого решателя? Алгоритм Ремеза chebfunдолжен повторяться до тех пор, пока не будет достигнут минимум точности станка (в некотором смысле).
Педро
Не обязательно; Существуют такие параметры, как «tol» (относительный допуск) или «maxiter» для chebfun/remez, но есть аналогичные параметры для всех видов решателей оптимизации. В некотором смысле, Remez - это оптимизационная процедура, предназначенная для определенной задачи. И вопрос: догонят ли решатели общего назначения, и больше нет необходимости в таком специализированном решателе? Конечно, я могу ошибаться.
Ганс В.