• To get full credit, you must write down sufficient intermediate steps, only giving the final answer earns you no credit!
• Please make sure that your handwriting is recognizable, otherwise you only get partial credit for the recognizable part.

1. A min-max problem.For n N⁺, determine

,

where the minimum is taken over all a_i R and a₀ 6= 0.

1. Imitate the proof of Chebyshev Theorem.

Let a > 1 and denote.

Define

,

where T_n is the Chebyshev polynomial of degree n. Clearly . Define the max-norm of a function f : R R as

kfk = max |f(x)|.

x[1,1] Prove

, kp_n(x)k kpk.

Problems I and II weigh 4 and 6 points, respectively. There is no extra-credit problem for this homework.

The three programming assignments in the next section weigh 10, 5, and 5 points, respectively. The total number of points is thus 30.

2 C++ programming

• Implement the Newton formula in a subroutine thatproduces the value of the interpolation polynomial p_n(f;x₀,x₁,,x_n;x) at any real x, where n N⁺, x⁰_is are distinct, and f is a function assumed to be available in the form of a subroutine.
• Run your routine on the function

for x [5,5] using, and n = 2,4,6,8. Plot the polynomials against the exact function to reproduce the plot in the notes that illustrate the Runge phenomenon.

• Reuse your subroutine of Newton interpolation to perform Chebyshev interpolation for the function

for x [1,1] on the zeros of Chebyshev polynomials T_n with n = 5,10,15,20. Clearly the Runge function f(x) is a scaled version of the function in (b). Plot the interpolating polynomials against the exact function to observe that the Chebyshev interpolation is free of the wide oscillations in the previous homework