Best polynomial approximation in uniform norm

Version 1.1 (7,73 KB) von Andrew Knyazev
For a given function on an interval, the code calculates the min-max approximation by a polynomial.
801 Downloads
Aktualisiert 15 Mai 2015

Lizenz anzeigen

For a given real-valued function of one real variable on an interval, the code calculates the best approximation in the uniform (max) norm by a polynomial of a given degree. Approximating in a uniform norm is much computationally harder compared to the standard least squares fit, but gives eye pleasing results. It can be viewed as an optimal polynomial interpolation, where the interpolating nodes are not known in advance, but rather determined by the algorithm. The polynomial that best approximates the data (X,Y) in the discrete uniform norm, i.e. the polynomial with the minimum value of max{ | p(x_i) - y_i | , x_i in X }, also known as min-max (or minimax) polynomial, is obtained by the exchange algorithm. Technically, the exchange algorithm requires a finite number of calculations to find the best approximation, but this finite number grows exponentially with the increase of the data points.
The screenshot example:
M = 5; N = 10000; K = 0; EPSH = 10^-12; MAXIT = 10;
X = linspace(-1,1,N); % uniformly spaced nodes on [-1,1]
k=1; Y = abs(X).^k; % the function Y to approximate
[A,REF,HMAX,H,R,EQUAL] = polyfitinf(M,N,K,X,Y,EPSH,MAXIT);
p = polyval(A,X); plot(X,Y,X,p) % p is the best approximation

The MATLAB/OCTAVE algorithm and the comments are based on the original FORTRAN code written by Joseph C. Simpson and available on Netlib repository: http://www.netlib.org/toms/501 See also: Communications of the ACM, V14, pp.355-356(1971)

This routine has been mostly developed and modified by students as computer assignments in Approximation Theory courses by Andrew Knyazev, University of Colorado Denver, USA: Team Fall 98 (Revision 1.0): Chanchai Aniwathananon, Crhistopher Mehl, David A. Duran, Saulo P. Oliveira; Team Spring 11 (Revision 1.1): Manuchehr Aminian.

Zitieren als

Andrew Knyazev (2024). Best polynomial approximation in uniform norm (https://www.mathworks.com/matlabcentral/fileexchange/32425-best-polynomial-approximation-in-uniform-norm), MATLAB Central File Exchange. Abgerufen .

Kompatibilität der MATLAB-Version
Erstellt mit R2010b
Kompatibel mit allen Versionen
Plattform-Kompatibilität
Windows macOS Linux
Kategorien
Mehr zu Polynomials finden Sie in Help Center und MATLAB Answers

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Veröffentlicht Versionshinweise
1.1

renamed the function from approx to polyfitinf, to be consistent with polyfit.
added a conversion to a toolbox

1.0.0.0