Top Qs
Timeline
Chat
Perspective
Equioscillation theorem
Theorem From Wikipedia, the free encyclopedia
Remove ads
In mathematics, the equioscillation theorem concerns the approximation of continuous functions using polynomials when the merit function is the maximum difference (uniform norm). Its discovery is attributed to Chebyshev.[1]
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.[1][2]
That is, the polynomial oscillates above and below at the interpolation points, and does so to the same degree.
Remove ads
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 polynomial
is also of degree less than or equal to . However, for every of the points , we know that because and (since is a better approximation than ).
Therefore, will have the same sign as (because the second term has a smaller magnitude than the first). 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 (given polynomial and function ) 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 (meaning that the union of the sections is the whole interval, and the intersection of any two sections is either empty or a single common endpoint) 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 [clarification needed]
Remove ads
Variants
The equioscillation theorem is also valid when polynomials are replaced by rational functions: among all rational functions whose numerator has degree and denominator has degree , the rational function , with and being relatively prime polynomials of degree and , minimizes the uniform norm of the difference if and only if there are points such that where is either -1 or +1.[1]
Remove ads
Algorithms
Several minimax approximation algorithms are available, the most common being the Remez algorithm.
References
External links
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads