## Math 543 Computer Project 1

For this project you will need to use a mathematics software tool package like Matlab, Maple or Mathematica, or a programming language. The project will involve the use of the four test functions
• exp(x), for x in [-1,1],
• 1/(1+25x^2), for x in [-1,1],
• log(x), for x in [1,e], and
• Phi(x), for x in [0,5].
Note: Phi(x) is the normal distribution function, which can be defined in terms of the error function, erf(x), using Phi(x) = ( 1 + erf(x/sqrt(2)) )/2; if your programming environment does not have erf(x), you may translate the Matlab phi function into your selected progrmming language.
1. Construct a procedure or function that will determine the coefficients for either the divided difference or Lagrange (barycentric) form of the degree n interpolating polynomial. Your procedure should have input parameters:
• n --the degree of the approximation,
• x -- an array of length n+1 of x values,
• f -- an array of length n+1 of function values.
The output parameter for your procedure should be an array of length n+1 of coefficients for the interpolating polynomial.
2. Construct a function that takes for input the coefficients for an interpolating polynomial, and the x_i's (and f(x_i)'s if needed), and evaluates the interpolating polynomial at a new x value.
3. For each of the four test functions determine the interpolating polynomials for n = 1, 2, 4, 7, and 10, using a uniform spacing for the x_i's (if approximation interval is [a,b], x_i = a + i(b-a)/n ). For each n and each f(x) approximately determine the maximum error (absolute value) for 100 f(x_i)'s computed using 100 uniformly spaced x_i's. Plot the error curves for the n = 10 approximations for each f(x).
4. For each of the four test functions determine the interpolating polynomials using n = 1, 2, 4, 7, 10, using the degree n+1 Chebyshev polynomial zeros (transformed to [a,b] if necessary) for the x_i's. For each n and each f(x) approximately determine the maximum error (absolute value) for 100 f(x_i)'s computed using 100 uniformly spaced x_i's. Plot the error curves for the n = 10 approximations for each f(x).
5. Construct a procedure or function that will determine, using the "exchange" algorithm (Remez algorithm), the best uniform (minimax) polynomial approximation for a finite set of data values. The procedure should have as input parameters:
• n --the degree of the approximation,
• m -- the number of data points,
• x -- an array of length m of x values,
• f -- an array of length m of function values.
The output parameters for the procedure should be:
• e -- the size of the error for the best approximation,
• xs --an array of length n+2 of x values for the final reference,
• ps --an array of length n+1 of coefficients for the best approximation of degree n for the data. These coefficients should be divided difference or Lagrange coefficients for the interpolating polynomial which uses the first n+1 xs_i values, and function values given by f(xs_i) +- e(-1)^i.
6. For each of the four test functions determine the best uniform approximating polynomials for n = 1, 2, 4, 7, and 10, using m = 100 f(x_i)'s computed using 100 uniformly spaced x_i's taken from the appropriate interval [a,b]. For each n and each f(x) determine the maximum error. Plot the error curves for the n = 10 approximations for each f(x).
7. Hand in your computer source code, graphs, and a brief discussion of your results. You should also include coefficients for the best uniform approximations, and their maximum errors. Make sure that your source code is well-structured and reasonably efficient, with some comments to explain what you have done.