Chebyshev’s Theorem - Study Guide

Chebyshev’s Theorem 2006 1 Introduction What we saw in the last exercise is an example of the Runge Phenomenon. That is, polynomials on evenly spaced points tend to start giving us huge oscillations towards the ends of the interval. This is very troubling because it tells us that We cannot necessarily get a more accurate approximation to f by simply taking more points for the interpolation! Is it possible to choose the x−values (presumably NOT evenly spaced) so as to minimize this “wiggle”? It is, and is the result of Chebyshev. Practically speaking, we may or may not be able to choose the domain values- For example, if we are measuring a change in voltage across the scalp (in an EEG device, for example), we cannot pre-determine the time values. On some devices, it is possible to do this, and in those cases, the best way to interpolate is to use the Chebyshev points. Our motivation comes from the error term, f (n) (c) (x − x1 )(x − x2 ) · · · (x − xn ) n! We can’t do anything about the term in the front- It’s coming from the function we’re interpolating. Even if the nth derivative is bounded, we still may run into very difficult problems (Note that the Wilkinson Polynomial was exactly of this form- and it had an extremely large condition number). So here’s the big question: Can we choose xi so as to minimize the maximum of the quantity (x − x1 )(x − x2 ) · · · (x − xn ) and to be more specific, let’s fix the interval to [−1, 1] (we’ll generalize later). 1 And the answer is: Yes! Theorem 1 (Chebyshev’s Theorem) The choice of real numbers −1 ≤ x1 , x2 , . . . , xn ≤ 1 that makes the value of max |(x − x1 )(x − x2 ) · · · (x − xn )| −1≤x≤1 as small as possible is: ! (2i − 1)π xi = cos , 2n i = 1, 2, . . . , n Furthermore, the minimum value is 1/2n−1 . We’ll see why this is true shortly, but first let us see where these values come from. Definition 1 (Chebyshev Polynomials) Define the nth Chebyshev polynomial by:   Tn (x) = cos n cos−1 (x) These are in fact polynomials, which we will construct recursively. Note that T0 (x) = 1 and T1 (x) = x. For T2 (x), use the cosine sum formula: cos(a + b) = cos(a) cos(b) − sin(a) sin(b) and let y = cos−1 (x). Then: T2 (x) = cos(2y) = cos2 (y) − sin2 (y) = 2 cos2 (y) − 1 = 2x2 − 1 Similarly, we notice that: Tn+1 (x) = cos((n + 1)y) = cos(ny) cos(y) − sin(ny) sin(y) and Tn−1 (x) = cos((n − 1)y) = cos(ny) cos(y) + sin(ny) sin(y) Add the two equations, and we get the recursion relation: Tn+1 (x) = 2xTn (x) − Tn−1 (x) 2 2 Properties of the Polynomials Property 1 Tn (x) is a polynomial for every n. Here are the first few so we can see what they look like: T0 (x) = 1, T1 (x) = x, T2 (x) = 2x2 − 1, T3 (x) = 4x3 − 3x, T4 (x) = 8x4 − 8x2 + 1 With the recursion formula, it is clear that all remaining Tn will also be polynomials (the sum of two polynomials is again a polynomial). Property 2 The leading coefficient of Tn (x) is 2n−1 . Again, this is due to the recursion formula. We see that the statement is true for n = 1 and n = 2. Then T3 (x) = 2xT2 (x) − T1 (x) The effect of this is to multiply the lead coefficient by 2. The rest of the polynomials are constructed likewise, and we always multiply the lead coefficient by 2. Property 3 Tn (1) = 1, Tn (−1) = (−1)n We can see this directly: Tn (1) = cos(n cos−1 (1)) = cos(n · 0) = 1 Tn (−1) = cos(n cos−1 (−1)) = cos(nπ) = ±1 or more precisely, (−1)n Property 4 The maximum value of Tn (x) is 1. This comes immediately from the cosine form of its definition. Property 5 All zeros of Tn (x) are between −1 and 1 In fact, Tn (x) = 0 0 = cos(n cos−1 (x)) ⇔ Since cos(A) = 0 iff A =odd integer ·π/2, n cos−1 (x) = odd integer · π/2 so odd π 2n x = cos ! Property 6 Tn (x) alternates between ±1 exactly n + 1 times. 3 We can solve this directly from the definition: Tn (x) = ±1 cos(n cos−1 (x)) = ±1 ⇒ Now, cos(θ) = 1 if θ is an even multiple of π (including zero), and cos(θ) = −1 if θ is an odd multiple of π. Therefore, n cos−1 (x) = kπ cos−1 (x) = ⇒ kπ n The range of the inverse cosine is the interval [0, π], so we get: cos−1 (x) = 0, π , n 2π , n ..., (n − 1)π , n π so we note that there are exactly n + 1 solutions, all between ±1: π cos , n   x = 1, 3 2π cos ,..., n   ! (n − 1)π cos , n −1 Proof of Chebyshev’s Theorem We now prove Chebyshev’s Theorem. The first part of the proof is due to the Chebyshev Polynomial, where we scale the lead coefficient to 1. Let x1 , x2 , . . . , xn be the zeros for Tn (x). Then 1 |(x − x1 )(x − x2 ) · · · (x − xn )| = n−1 |Tn (x)| 2 By Property 4, 1 1 |(x − x1 )(x − x2 ) · · · (x − xn )| = n−1 |Tn (x)| ≤ n−1 2 2 with equality at the n + 1 points found in Property 6. Now the key question is this: By choosing other values of x1 , x2 , . . . , xn , is it possible to make max |(x − x1 )(x − x2 ) · · · (x − xn )| −1≤x≤1 smaller than 1/2n−1 ? Let P (x) be any such polynomial. In particular, such a polynomial must satisfy the following properties: • The leading term of P (x) is xn , same as • |P (x)| < 1 2n−1 for all x in [−1, 1]. 4 1 T (x). 2n−1 n These two items will lead us to a contradiction: In that case, no such P (x) can exist. Here we go: (x) Let F (x) = P (x) − T2nn−1 . We will show that F is a degree n polynomial (and that will be a contradiction). Note the following computations (from Property 6): F (1) = P (1) − 1 2n−1 <0 F (cos(π/n)) = P (cos(π/n)) + 1 >0 2n−1 1 F (cos(2π/n)) = P (cos(2π/n)) − n−1 < 0 2 and so on. There are n + 1 sign changes for F , so there must be n zeros for F (IVT). Therefore, F must be a degree n polynomial. BUT Tn (x) 2n−1 so the degree of F is no larger than n − 1. Thus, we have a contradiction- NO such P (x) can exist. What does that imply? That implies that Tn (x)/2n−1 is the SMALLEST such polynomial, and the theorem is proven. F (x) = P (x) − 4 4.1 Practical Notes Impact on Computation and Error In practice, we do not have to actually construct the Chebyshev polynomials. If f (x) is on the interval [−1, 1], we simply interpolate on: ! (2i − 1)π , xi = cos 2n i = 1, 2, . . . , n using any method available. The error to the approximation using the degree n−1 polynomial Pn−1 (x) found by Lagrange or Newton’s Divided Differences is then: f (x) − Pn−1 (x) = f n (c) Tn (x) · n−1 n! 2 In particular, if |f n (c)| ≤ M is bounded for all n, |f (x) − Pn−1 (x)| ≤ 5 M n!2n−1 which does indeed go to zero as n → ∞. Additionally, the maximum error occurs at the n + 1 points found in Property 6 - that is, the error from the term |(x − x1 )(x − x2 ) · (x − xn )| is spread out somewhat evenly across the interval, rather than being concentrated at the endpoints. Let’s go back to our lead-in example. Suppose f (x) = 1/(1 + 12x2 ). We’ll now use the Chebyshev points and look at how well the polynomials approximate f (note that these are only slight changes to our previous script). The output is in HTML format, and is available on our class website. 4.2 Changing the Interval Suppose the function f (x) is being interpolated on [a, b] instead of [−1, 1]. We can compute the proper x− values by considering the linear mapping h(t) = mt + c from ti ∈ [−1, 1] to xi ∈ [a, b]. We could reason it out, or if you want some equations: h(−1) = a h(0) = a+b 2 h(1) = b We actually only need two equations: −m + c = a ⇒ m+c=b m= b−a b+a ,c = 2 2 ! (2i − 1)π , so we conclude that: Now, ti = cos 2n Given f (x) on [a, b], use the domain points: b−a (2i − 1)π xi = cos 2 2n ! + b+a , 2 i = 1, 2, . . . , n to construct the degree n − 1 polynomial approximation. In this case,  |(x − x1 )(x − x2 ) · · · (x − xn )| ≤ 6 n b−a 2 2n−1 , for all a ≤ x ≤ b