Remez algorithm
From Wikipedia, the free encyclopedia
The Remez algorithm (Remez 1934), also called the Remez exchange algorithm, is an iterative algorithm that finds the polynomial of best approximation of a given degree to a real function on an interval.
The polynomial of best approximation of a given degree is defined to be the one that minimizes the maximum absolute difference between the polynomial and the function.
[edit] Procedure
The Remez algorithm starts with a set of sample points in the approximation interval, usually the Chebyshev nodes linearly mapped to the interval.
- A polynomial approximation of the function at the sample points is obtained through Lagrange interpolation.
- The difference between the approximation and the function is measured across the interval. The point where the difference has the largest absolute value is found.
- The sample point nearest the location of the maximum absolute difference is replaced with the location of the maximum absolute difference.
- The process is repeated until all sample points converge to the points of maximum absolute difference, and the sign of the difference between the function and the polynomial alternates.
The result is called the polynomial of best approximation, the Chebyshev approximation, or the minimax approximation.
[edit] Variants
Sometimes more than one sample point is replaced at the same time with the locations of nearby maximum absolute differences.
Sometimes relative error is used to measure the difference between the approximation and the function, especially if the approximation will be used to compute the function on a computer which uses floating-point arithmetic.
[edit] External links
 |
This mathematics-related article is a stub. You can help Wikipedia by expanding it. |
