Algoritma Remez

14

Algoritma Remez adalah rutin iteratif yang terkenal untuk memperkirakan suatu fungsi oleh polinomial dalam norma minimum. Tapi, seperti yang dikatakan Nick Trefethen [1] tentang itu:

Sebagian besar dari [implementasi] ini telah berlangsung bertahun-tahun dan pada kenyataannya, sebagian besar dari mereka tidak menyelesaikan masalah aproksimasi umum terbaik seperti yang ditunjukkan di atas, tetapi varian yang melibatkan variabel diskrit atau penyaringan digital. Seseorang dapat menemukan beberapa program komputer lain yang beredar, tetapi secara keseluruhan, tampaknya tidak ada program yang banyak digunakan saat ini untuk menghitung perkiraan terbaik.

Seseorang dapat menghitung solusi minimax juga dengan menerapkan kuadrat-terkecil atau optimasi cembung, misalnya menggunakan Matlab dan kotak alat CVX gratis yang diterapkan ke fungsi Runge pada [-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

Perkiraan dengan polinomial Chebyshev memiliki norma 0.1090minimum sementara pendekatan ini mencapai minimum 0.0654, nilai yang sama yang dihitung dengan algoritma Remez di chebfunkotak alat Matlab .

Apakah ada manfaat dalam menerapkan algoritma Remez yang lebih rumit jika Anda dapat menghitung solusi minimax lebih cepat dan lebih akurat dengan pemecah optimasi? Apakah ada laporan / artikel yang membandingkan kedua pendekatan ini pada beberapa masalah sulit atau kasus uji?

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

Hans W.
sumber

Jawaban:

4

Jawaban "benar" sangat tergantung pada apa yang Anda butuhkan untuk perkiraan Anda. Apakah Anda benar-benar membutuhkan perkiraan terbaik untuk beberapa kesalahan terikat? Atau hanya perkiraan yang bagus? Atau hanya perkiraan yang baik dalam arti minmax?

Nick Trefethen baru-baru ini memberikan contoh yang bagus di mana perkiraan Remez adalah ide yang buruk karena meminimalkan kesalahan maksimum terlepas dari kesalahan rata-rata selama seluruh interval, yang mungkin bukan yang Anda inginkan. Tentu saja, kesalahan maksimum mungkin besar, tetapi ini dibatasi untuk fungsi yang halus.

Memperbarui

Mengikuti diskusi dalam komentar di bawah ini, saya mengunduh CVX Toolbox dan melakukan perbandingan langsung dengan algoritma Chebfun Remez (penafian: Saya bagian dari tim pengembangan 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' );

Setelah banyak output, saya dapatkan, di laptop saya dengan Matlab 2012a, CVX versi 1.22 dan Snapshot SVN terbaru Chebfun:

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

Perhatikan bahwa Chebfun yang fdigunakan untuk mengukur kesalahan akurat hingga 15 digit. Jadi Remez Chebfun membutuhkan waktu dua kali lebih lama, tetapi mendapat kesalahan global yang lebih kecil. Harus ditunjukkan bahwa CVX menggunakan kode terkompilasi untuk optimisasi sedangkan Chebfun adalah 100% asli Matlab. Kesalahan minimum 0.00654adalah kesalahan minimum 'di grid', dari grid itu, kesalahan bisa sampai 0.00659. Meningkatkan ukuran grid yang m = 1001saya dapatkan

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

yaitu kecepatan yang hampir sama, tetapi optimasi diskrit masih lebih buruk pada digit desimal keempat. Akhirnya, ncreasing ukuran grid lebih jauh untuk m = 10001saya dapatkan

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

yaitu optimasi diskrit sekarang lebih dari sepuluh kali lebih lambat dan masih lebih buruk pada digit keenam.

Intinya adalah bahwa Remez akan memberi Anda hasil optimal secara global. Sementara analog diskrit mungkin cepat pada grid kecil, itu tidak akan memberikan hasil yang benar.

Pedro
sumber
Dan N. Trefethen menekankan hal yang sama dan memberikan contoh serupa dalam artikel yang saya kutip. Pertanyaannya bukan tentang perkiraan terbaik, tetapi: Apa keuntungan dari algoritma Remez (saat ini) jika Anda bisa mendapatkan hasil yang sama dengan pemecah cembung yang masuk akal ?
Hans W.
1
@HansWerner, maaf, saya salah membaca pertanyaan Anda. Pemecah cembung Anda tidak memberi Anda hasil yang sama, setidaknya tidak untuk semua digit. Jika saya memahami kode cembung Anda dengan benar, Anda meminimalkan kesalahan maksimum pada set poin diskrit. Ini adalah perkiraan yang baik dari - tetapi tidak sama dengan - meminimalkan kesalahan maksimum global.
Pedro
Pemecah cembung dalam hal ini memberikan hasil yang lebih baik . Anggap saja, algoritma Remez adalah prosedur berulang, sangat mirip dengan rutin optimasi, dan tidak akan mengembalikan hasil yang tepat juga. Dalam kasus konkret di atas, solusi dari optimasi lebih baik, yaitu memiliki norma maksimum keseluruhan yang lebih kecil secara keseluruhan, daripada hasil dari implementasi Remez terbaik yang saya tahu. Pertanyaannya masih terbuka .
Hans W.
@HansWerner, bagaimana Anda mengukur kesalahan maksimum dari solusi yang diperoleh dengan pemecah cembung? Algoritma Remez di chebfunharus iterate sampai minimum dicapai untuk presisi mesin (dalam arti tertentu).
Pedro
Belum tentu; ada opsi seperti 'tol' (yang merupakan toleransi relatif) atau 'maxiter' untuk chebfun/remez, tetapi ada opsi serupa untuk semua jenis pemecah optimasi. Bisa dibilang, Remez adalah rutin optimasi yang khusus untuk tugas tertentu. Dan pertanyaannya adalah: Apakah pemecah-pemecah tujuan umum telah berhasil dan tidak perlu lagi untuk pemecah yang khusus seperti itu? Tentu saja, saya mungkin salah.
Hans W.