Homework 5 Solution

Description

1. The polynomial p(x) = x⁴ x³ + x² x + 1 has the values shown below.

x	-2	-1	0	1	2	3
p(x)	31	5	1	1	11	61

Using as little work as possible to nd a polynomial q which has values

x	-2	-1	0	1	2	3
q(x)	31	5	1	1	11	30

2. Prove that a polynomial interpolantion of degree at most n through the (n + 1) points

f(x₀; y₀); (x₁; y₁); : : : ; (x_n; y_n)g must be unique. (Hint: Assume that there are two such polynomials,

P and Q, and argue that they must be identical, that is R(x) = P (x) Q(x) must be zero.)

3. (a) Verify that the polynomials

p(x) = 5x³ 27x² + 45x 21; q(x) = x⁴ 5x³ + 8x² 5x + 3

both interpolate the points in the below table.

x	1	2	3	4
y	2	1	6	47

You showed that interpolation polynomials are unique. Does this problem contradict that? Why? (b) Verify that the polynomials

p(x) = 3 + 2(x 1) + 4(x 1)(x + 2);	q(x) = 3	(x + 2)x	3	(x 1)x		7	(x 1)(x + 2)
		3			6			2

both interpolate the points in the below table.

x	1	-2	0
y	3	-3	-7

You showed that interpolation polynomials are unique. Does this problem contradict that? Why?

4. Prove the recursion formula for computing Newton divided di erences.

f[x0; x1; : : : ; xk] =	f[x1; x2; : : : ; xk]		f[x0; x1; : : : ; xk 1]
		xk	x0

To do this, let P be the interpolating polynomial for f(x₀; y₀); (x₁; y₁); : : : ; (x_{k 1}; y_{k 1})g and Q the

interpolating polynomial for f(x₁; y₁); (x₂; y₂); : : : ; (x_k; y_k)g and consider the polynomial

R(x) =		xk	x	P (x) +	x x0	Q(x):
	xk
			x0		xk x0

1. Prove R is the unique polynomial of at most degree k which interpolates points f(x₀; y₀); (x₁; y₁); : : : ; (x_k; y_k)g.

2. Determine the coe cient of x^k on each side of the equation.

5. Consider y = sin x on [0; 2 ] with ve equally spaced interpolation points. Find the interpolation polynomial by hand via the following method

5. 1. Vandermonde matrix.

5. 2. Newton’s form using direct computing of the coe cients.

5. 3. Newton’s form via Newton divided di erence (attach your Newton divided di erence matrix.)

5. 4. Lagrange interpolation.

5. Write a Matlab function p = NewtonInt(x,y) for polynomial interpolation using Newton form and direct computing of the coe cients. The input for this function should be an array x with (n + 1) distinct points x₀; x₁; x₂; : : : ; x_n and also an array of function values y, with (n + 1) function values y₀; y₁; y₂; : : : ; y_n. Your function should return to a vector which contains the coe cients (in descend order) of your interpolation polynomial p such that p(x_i) = f(x_i) for i = 0; 1; : : : ; n.

5. Write a Matlab function p = NewtonDiv(x,y) for polynomial interpolation using Newton form and Newton divided di erence. The input for this function should be an array x with (n+1) distinct points x₀; x₁; x₂; : : : ; x_n and also an array of function values y, with (n + 1) function values y₀; y₁; y₂; : : : ; y_n. Your function should return to a vector which contains the coe cients (in descend order) of your interpolation polynomial p such that p(x_i) = f(x_i) for i = 0; 1; : : : ; n.

5. Write a Matlab function p = LagrangeInt(x,y) for polynomial interpolation using Lagrange form. The input for this function should be an array x with (n + 1) distinct points x₀; x₁; x₂; : : : ; x_n and also an array of function values y, with (n + 1) function values y₀; y₁; y₂; : : : ; y_n. Your function should return to a vector which contains the coe cients (in descend order) of your interpolation polynomial p such that p(x_i) = f(x_i) for i = 0; 1; : : : ; n.

5. Compare the e ciency of NewtonInt(x,y), NewtonDiv(x,y) and LagrangeInt(x,y). Try with large amount of sample points until you see a signi cant di erence.

5. To see the accuracy of an interpolation polynomial p(x), we evaluate the interpolation polynomial on evaluation points. To avoid machine error, instead of direct computing, we apply the Horner’s method. Check

https://en.wikipedia.org/wiki/Horner%27s_method

Let (x_i; y_i), q i m be the points to be evaluated, De ne ~x := (x₁; x₂; :::; x_m)^T and ~y := (y₁; y₂; :::; y_m)^T . The residual are then de ned by the average error

residual =	kp(~x) ~yk	; where m is the number of evaluation points:
	m

In real life application, you may use di erent vector norms depending on the problem. Three popular vector norms are

				n
			Xi
L1 norm: k~xk1 :=						jxij
			=1
				n
			Xi
L2 norm: k~xk2 :=						jxij2
			=1
	L	~x	:=	1		max			j	x	ij
		1 norm: k k1				i		n+1

(a) Read and understand the Horner’s method

1. 2. Write a Matlab script residual = eval(p,x,y,k) which evaluates the polynomial p at sample points x using Horner’s method with one of the norm above. Here p is a vector containing all the coe cients of the interpolation polynomial, x is a vector containing the evaluation points, y is the true value at sample points and k = 0; 1; 2 indicates which norm your are going to use (0 for L₁, 1 for L₁ and 2 for L²).

11. For each function below, do

11. 1. f(x) = sin(x); 0 x 2

11. 2. g(x) = cos(x); 0 x 2

11. 3. h(x) = ln(x); 0:5 x 2

11. 4. i(x) = e^x; 0 x 2

1. Apply your code to nd the coe cients of Newton’s interpolation polynomial and Lagrange’s interpolation polynomial. Use 201 equally spaced sample points of the give interval.

2. Matlab has a built in polynomial tting function \poly t”. Use this command to t your sample points using an appropriate degree n.

(c) Evaluate your result in (a) and (b) by computing the evaluation error residual = eval(p,x,y,k) with 1001 equally spaced evaluation points of the given interval. Use the three di erent norms and list your result for each method.

4. Based on what you see in (c), discuss which vector norm is better.

4. Read the help le of \poly t”, discuss when to use \poly t” and when to use interpolation polynomial. Think about real life applications.

1

12. Consider the Runge function f(x) = _{1 + 25x2} on [ 1; 1]. Graph the following all on the same plot.

Label your graph and include a legend.

1. Graph y = f(x) on [ 1; 1] using 100 uniformly distributed data points.

2. Find the degree 10 polynomial interpolant of function f through 11 equally spaced nodes in [ 1; 1]. Graph it using the same data points as in (a).

(c) Repeat (b) with 11 non-equally spaced Chebyshev points xj = cos	j	; j = 0; 1; : : : ; 10. Graph
	10
your polynomial using the same data points as in (a).

(d) (Challenge) Research on Chebyshev points and explain why it will solve the Runge phenomenon.

3