Equioscillation theorem
In mathematics, the equioscillation theorem concerns the approximation of continuous functions using polynomials when the merit function is the maximum difference. Its discovery is attributed to Chebyshev.
Statement
Let be a continuous function from to. Among all the polynomials of degree, the polynomial minimizes the uniform norm of the difference if and only if there are points such that where is either -1 or +1.That is, the polynomial oscillates above and below at the interpolation points, and does so to the same degree.
Proof
Let us define the equioscillation condition as the condition in the theorem statement, that is, the condition that there exists ordered points in the interval such that the difference alternates in sign and is equal in magnitude to the uniform-norm of.We need to prove that this condition is 'sufficient' for the polynomial being the best uniform approximation to, and we need to prove that this condition is 'necessary' for a polynomial to be the best uniform approximation.
Sufficiency
Assume by contradiction that a polynomial of degree less than or equal to existed that provides a uniformly better approximation to, which means that. Then the polynomialis also of degree less than or equal to. However, for every of the points, we know that because and .
Therefore, will have the same sign as . Thus, will also alternate sign on these points, and thus have at least roots. However, since is a 'polynomial' of at most degree, it should only have at most roots. This is a contradiction.
Necessity
Given a polynomial, let us define.We will call a point an upper point if and a lower point if it equals instead.
Define an alternating set to be a set of ordered points in such that for every point in the alternating set, we have, where equals or as before.
Define a sectioned alternating set to be an alternating set along with nonempty closed intervals called sections such that
1. the sections partition
2. For every, the th alternating point is in the th section
3. If is an upper point, then contains no lower points. Likewise, if is a lower point, then contains no upper points.
Given an approximating polynomial that does not satisfy the equioscillation condition, it is possible to show that the polynomial will have a two point alternating set. This alternating set can then be expanded to a sectioned alternating set. We can then use this sectioned alternating set to improve the approximation, unless the sectioned alternating set has more than points in which case our improvement cannot be guaranteed to still be a polynomial of degree at most