McGill COMP 350 Numerical Computing - Final Exam
(ACTUAL Sample) with solution
COMP 350 Final Exam (Sample)
Note: the difficulty of this sample exam is harder than the real one. The main purpose is to help you get a better and
deeper understanding of what we have learned in class and this is important for you to get a good grade in the real final.
1. Let P3(x) be the interpolating polynomial for the data (0, 0), (0.5, y), (1, 3) and (2, 2). Find y if the coefficient of
x3 in P3(x) is 6 .
2. Consider the data
x 1 3/2 0
f (x) 3 13/4 3
(a) What are the Vandermonde interpolation polynomial, Langrange interpolation polynomial and Newton inter-
polation for these data?
(b) When we add one point to the data,
x 1 3/2 0 2
f (x) 3 13/4 3 5/3
What is the Newton interpolation now?
(c) Compute the Newton interpolation p(x) of the following data
x 0 1 2 3
f (x) 0 −5/2 −2 27/2
Evaluate the minimum of p(x) over [0, 3] based on the result above.
3. (a) Show that if g interpolates f at points x0, . . . , xn—1 and h interpolates f at x1, . . . , xn, then
x0 − x
g(x) + (g(x) − h(x))
xn − x 0
interpolates f at x0, . . . , xn
(b) Let x0, x1, . . . , xn be distinct points and lj(x) be the Lagrange basis functions, prove the follow equality holds
at x = x0, x1, . . . , xn
Σn
(xj − x)k lj(x) ≡ 0, k = 1, 2, . . . , n
j=0
4. Consider quadrature
Σ
n
Iquad = αif (xi) , xi ∈ [−1, 1] (1)
i=0
for the integral ∫ 1
I = f (x)w(x)dx
—1
where w is a positive weight in (−1, 1) . Let
Y
n
Ωn+1(x) = (x − xi)
i=0
, denote the polynomial of degree n + 1 associated with the (distinct) quadrature nodes x0, x1, . . . , xn . Prove that
∫ 1
Ωn+1(x)p(x)w(x)dx = 0 (2)
—1
for any polynomial p(x) of degree less or equal to m − 1 if and only if the quadrature formula (1) is exact for all
polynomials f (x) of degree less or equal n + m.
5. (a) There
'
exists a one parameter family of 2-stage, second order Runge-Kutta methods for solving the ODE
y = f (x, y(x)). With step size h in the x-direction, and the parameter α arbitrary, these can be written as
d(1) = hf (xn, yn)
d(2) = hf xn + αh, yn + αd(1)
1 1 (2)
yn+1 = y n + 1 − d(1) + d
2α 2α
'
Verify that these
f (x, y(x)), by theschemes, forimplies
chain rule, all values
''
of α, indeed
∂f
provide
∂f
second order accuracy. Hint: Recall that y (x) =
y (x) = ∂x + f ∂y
'
(b) Consider the initial value problem y = f (t, y), y (t0) = y0. The Milne method is a linear multistep method
defined by ∫ tn
yn = yn—2 + P (t)dt
tn−2
where P (t) is the unique quadratic polynomial that interpolates f at the points tn—2, tn—1, tn, and tn = hn.
Derive the formula for this method.
∫b Σn
6. (a) Let the weights in the quadrature formula a f (x)dx ≈ i=0 wif (x )i with distinct nodes x0 , . . . , x n be based
on integrating the unique polynomial of degree ≤ n that interpolates the data. Give a formula relating the
weights wi to the Lagrange interpolating polynomials li(x).
∫b Σn
(b) Let the weights in the quadrature formula a f (x)dx ≈ i=0 wif (x )i with distinct nodes x0 , . . . , x n be chosen
so that the quadrature exactly integrates all polynomials up to degree ≤ n. Show that the resulting weights
are the same as in part (a).
∫1 Σ
(c) Find weights w0 , w1, w 2 and nodes x0 , x1, x 2 ∈ [−1, 1] such that the quadrature —1 f (x)dx ≈ i w if (x i)
integrates all quintic polynomials exactly.
(ACTUAL Sample) with solution
COMP 350 Final Exam (Sample)
Note: the difficulty of this sample exam is harder than the real one. The main purpose is to help you get a better and
deeper understanding of what we have learned in class and this is important for you to get a good grade in the real final.
1. Let P3(x) be the interpolating polynomial for the data (0, 0), (0.5, y), (1, 3) and (2, 2). Find y if the coefficient of
x3 in P3(x) is 6 .
2. Consider the data
x 1 3/2 0
f (x) 3 13/4 3
(a) What are the Vandermonde interpolation polynomial, Langrange interpolation polynomial and Newton inter-
polation for these data?
(b) When we add one point to the data,
x 1 3/2 0 2
f (x) 3 13/4 3 5/3
What is the Newton interpolation now?
(c) Compute the Newton interpolation p(x) of the following data
x 0 1 2 3
f (x) 0 −5/2 −2 27/2
Evaluate the minimum of p(x) over [0, 3] based on the result above.
3. (a) Show that if g interpolates f at points x0, . . . , xn—1 and h interpolates f at x1, . . . , xn, then
x0 − x
g(x) + (g(x) − h(x))
xn − x 0
interpolates f at x0, . . . , xn
(b) Let x0, x1, . . . , xn be distinct points and lj(x) be the Lagrange basis functions, prove the follow equality holds
at x = x0, x1, . . . , xn
Σn
(xj − x)k lj(x) ≡ 0, k = 1, 2, . . . , n
j=0
4. Consider quadrature
Σ
n
Iquad = αif (xi) , xi ∈ [−1, 1] (1)
i=0
for the integral ∫ 1
I = f (x)w(x)dx
—1
where w is a positive weight in (−1, 1) . Let
Y
n
Ωn+1(x) = (x − xi)
i=0
, denote the polynomial of degree n + 1 associated with the (distinct) quadrature nodes x0, x1, . . . , xn . Prove that
∫ 1
Ωn+1(x)p(x)w(x)dx = 0 (2)
—1
for any polynomial p(x) of degree less or equal to m − 1 if and only if the quadrature formula (1) is exact for all
polynomials f (x) of degree less or equal n + m.
5. (a) There
'
exists a one parameter family of 2-stage, second order Runge-Kutta methods for solving the ODE
y = f (x, y(x)). With step size h in the x-direction, and the parameter α arbitrary, these can be written as
d(1) = hf (xn, yn)
d(2) = hf xn + αh, yn + αd(1)
1 1 (2)
yn+1 = y n + 1 − d(1) + d
2α 2α
'
Verify that these
f (x, y(x)), by theschemes, forimplies
chain rule, all values
''
of α, indeed
∂f
provide
∂f
second order accuracy. Hint: Recall that y (x) =
y (x) = ∂x + f ∂y
'
(b) Consider the initial value problem y = f (t, y), y (t0) = y0. The Milne method is a linear multistep method
defined by ∫ tn
yn = yn—2 + P (t)dt
tn−2
where P (t) is the unique quadratic polynomial that interpolates f at the points tn—2, tn—1, tn, and tn = hn.
Derive the formula for this method.
∫b Σn
6. (a) Let the weights in the quadrature formula a f (x)dx ≈ i=0 wif (x )i with distinct nodes x0 , . . . , x n be based
on integrating the unique polynomial of degree ≤ n that interpolates the data. Give a formula relating the
weights wi to the Lagrange interpolating polynomials li(x).
∫b Σn
(b) Let the weights in the quadrature formula a f (x)dx ≈ i=0 wif (x )i with distinct nodes x0 , . . . , x n be chosen
so that the quadrature exactly integrates all polynomials up to degree ≤ n. Show that the resulting weights
are the same as in part (a).
∫1 Σ
(c) Find weights w0 , w1, w 2 and nodes x0 , x1, x 2 ∈ [−1, 1] such that the quadrature —1 f (x)dx ≈ i w if (x i)
integrates all quintic polynomials exactly.
