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.1090
minimum sementara pendekatan ini mencapai minimum 0.0654
, nilai yang sama yang dihitung dengan algoritma Remez di chebfun
kotak 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.
sumber
chebfun
harus iterate sampai minimum dicapai untuk presisi mesin (dalam arti tertentu).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.