Remez algorithm: Difference between revisions

Revision as of 12:11, 8 October 2006

Revision as of 23:23, 3 November 2006

Line 1:

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 degredegree 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.

==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.

# 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. The result is called the [[minimax approximation]].

==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.

==External links==