Statement
Let f be a continuous function from [a,b] to \mathbb{R}. Among all the polynomials of degree \le n, the polynomial g minimizes the uniform norm of the difference \| f - g \| _\infty if and only if there are n+2 points a \le x_0 such that f(x_i) - g(x_i) = \sigma (-1)^i \| f - g \|_\infty where \sigma is either -1 or +1. That is, the polynomial g oscillates above and below f at the interpolation points, and does so to the same degree. == Proof ==
Proof
Let us define the equioscillation condition as the condition in the theorem statement, that is, the condition that there exists n+2 ordered points in the interval such that the difference f(x_i) - g(x_i) alternates in sign and is equal in magnitude to the uniform-norm of f(x) - g(x) . We need to prove that this condition is 'sufficient' for the polynomial g being the best uniform approximation to f , 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 p(x) of degree less than or equal to n existed that provides a uniformly better approximation to f , which means that \| f - p \|_\infty . Then the polynomial : h(x) = g(x) - p(x) = (g(x) - f(x)) - (p(x) - f(x)) is also of degree less than or equal to n. However, for every x_i of the n+2 points x_0, x_1, ... x_n , we know that | p(x_i) - f(x_i) | because |p(x_i) - f(x_i)| \le \| f - p \|_\infty and \| f - p ||_\infty (since p is a better approximation than g ). Therefore, h(x_i) = (g(x_i) - f(x_i)) - (p(x_i) - f(x_i)) will have the same sign as g(x_i) - f(x_i) (because the second term has a smaller magnitude than the first). Thus, h(x_i) will also alternate sign on these n+2 points, and thus have at least n+1 roots. However, since h is a 'polynomial' of at most degree n , it should only have at most n roots. This is a contradiction. Necessity Given a polynomial g , let us define M = \|f(x) - g(x) \|_\infty . We will call a point x an upper point if f(x) - g(x) = M and a lower point if it equals -M instead. Define an alternating set (given polynomial g and function f ) to be a set of ordered points x_0, ... x_n in [a,b] such that for every point x_i in the alternating set, we have f(x_i) - g(x_i) = \sigma (-1)^i M , where \sigma equals 1 or -1 as before. Define a sectioned alternating set to be an alternating set x_0, ... x_n along with nonempty closed intervals I_0, ... I_n called sections such that 1. the sections partition [a,b] (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 i , the ith alternating point x_i is in the ith section I_i 3. If x_i is an upper point, then I_i contains no lower points. Likewise, if x_i is a lower point, then I_i contains no upper points. Given an approximating polynomial g 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 n+2 points in which case our improvement cannot be guaranteed to still be a polynomial of degree at most n == Variants ==
Variants
The equioscillation theorem is also valid when polynomials are replaced by rational functions: among all rational functions whose numerator has degree \le n and denominator has degree \le m, the rational function g = p/q, with p and q being relatively prime polynomials of degree n-\nu and m-\mu, minimizes the uniform norm of the difference \| f - g \| _\infty if and only if there are m + n + 2 - \min\{\mu,\nu\} points a \le x_0 such that f(x_i) - g(x_i) = \sigma (-1)^i \| f - g \|_\infty where \sigma is either -1 or +1. == Algorithms ==