Orthogonal Polynomials - due Monday, February 28

Write a program to compute

1.

The orthogonal polynomials with respect to a discrete weighted inner product on a data set of x_i.

2.

The expansion coefficients of a least squares polynomial approximation to a given function based on these polynomials and the data values y_i=f(x_i).

3.

The values at a given number of equally spaced points of any least squares polynomial based on these orthogonal polynomials.

The inputs to the overall program should be n,w,x,y,m,d where n is the number of data points, w is an n dimensional vector of weights, the data points are $(x_i,y_i),\ i=1,\ldots,n$, m+1 is the number of evaluation points and d is the maximum degree of the set of orthogonal polynomials. The subprogram for (1) should generate polynomials $q_j(x),j=0,\ldots,d$ which are orthogonal with respect to the inner product $<f,g>=\sum_1^n w_if(x_i)g(x_i)$. These polynomials should be calculated according to the three term recurrence relation described on pages 268-270. The subprogram (2) should compute the ``Fourier'' coefficients c<sub>k</sub>=<y,q<sub>k</sub>>/<q<sub>k</sub>,q<sub>k</sub>> of the ``function'' y. And the subprogram (3) should calculate the values of the approximation $p(x)=\sum _0^d c_kq_k(x)$ at m+1 equally spaced points in the interval [x₁,x_n].

Run your program with the following data and plot the approximation p.

$n=11,\ m=100$,

w=(1,1,1,1,1,1,1,1,1,1,1),

x=(-5,-4,-3,-2,-1,0,1,2,3,4,5),

y=(3,2,3,5,3,4,3,2,2,3,2),

d=2,5,10, (one run for each value of d)

Also run and plot the approximations when y=1/(1+x²). (The d=10 case is a polynomial interpolant (Why?) and should remind you of one of the polynomial interpolants plotted last quarter.)