Polynomials - Horner's Method, etc.

a) Given a polynomial P(x) and a point xo, what 2 things does Horner's method give us? How is the result useful for polynomial root-finding P(x)=0?

b) One use of polynomials is interpolation of given data points {(xk, fk)} , k=0,....,n

1. Write down the Lagrange building block Ln,k (x)- that is the nth degree polynomial which is one in xk and zero in xj, where j doesn't equal k

2. Write down the Lagrange interpolating polynomial, which interpolates the data points {(xk,fk)}, k =0,......,n

c) 1. In one word, what is the problem with high-degree (interpolating) polynomials?
2. In general, it is hard to say anything useful about m(x) using the error term on an nth degree interpolating polynomial. However, if we are free to select the points xk freely we can select an optimal (Chebyshev) placement of the points, xk= cos((2k-1)*pi/(2n)). What can be said about m(x) in this case?

d) Numerical integration schemes are derived by piecewise polynomial interpolation of a function. Unlike spline interpolation, for integration schemes we don't worry about the continuity of the derivatives at the points where sub intervals meet.

1. If we base our numerical integration schemes on the use of interpolating polynomials using regularly spaced points, then if n is even, the error in the approximation (if the values ak are selected appropriately) is of the form Cn* h^(n+3)f^(n+2) / (n+2)! Cn E R. What is the highest degree polynomial for which this approximation scheme is exact? (The degree of precision.)
2. If we are free to place the points xi anywhere, then we can optimally place them and get the Gaussian quadrature formulas. What is the degree of precision for the Gaussian quadrature scheme which uses (n+1) points (n subintervals)? Here xk* and ak* denote the Gaussian quadrature points ,and the appropriate summation weights.