−
≤
−
— −
· · ·
· · ·
i i h
i+1
h
i i+1
Project Description
This project studies polynomial interpolation, which are composed of two parts: 1) the
polynomial interpolations on uniform points and Chebyshev points; and 2) cubic spline in-
terpolation. We use function f (x) =
−1
1 + 25x2
to generate a set of points for interpolation.
The x-values of these points are in between [ 1, 1] and y-values are obtained from the func-
tion y = f (x).
Part I: Polynomial interpolations on uniform points and Chebyshev points
Given n + 1 points, (x0, y0), (x1, y1), · · · , (xn, yn), we can find a unique polynomial pn(x) with
degree n such that pn(xi) = yi for i = 0 : n. Recall methods for con- structing this
polynomial such as Lagrange’s form or Newton’s form. The included python module
newtonPoly.py has the functions “coeffts()” and “evalPoly()” combined to interpolate the
given set of points and then use pn(x) to approximate unknown points. The
command“coeff=coeffts(xData,yData)” produces the coefficients of the polynomial pn(x)
from highest degree to the lowest. With these coefficients, the command“evalPoly(coeff,
xData,x)” returns the values pn(x). Read the module newtonPoly.py for more details.
For this part of the project, divide the interval [−1, 1] into n =4, 8, and 16 subintervals (thus
n + 1 points). For each value of n, implement the polynomial interpolation for pn(x) using
the “coeffts()” function on both uniform points and Chebyshev points. After obtaining the
coefficients of pn(x) for each case, plot both the function f (x) and pn(x) (use “evalPoly()”
function) on a fine mesh x = 1.5 : 0.01 : 1.5. You may also plot the interpolating points
for better illustration. Give a careful choice of styles of lines, markers, and colors. You can
use Python’s “subplot” command to organize all six graphic outputs. It is suggested use
“axis([ -1.5, 1.5, -1.5, 1.5 ])” for the window size. Give a title to each subplot. Read and
play subplots demo.py module to learn how to use subplot.
Note: in each subplot, you need plot three groups of x and y values: (1) x − y values of
interpolating points; (2) x y values for pn(x) on a refined mesh; (3) x y values for f (x)
on a refined mesh.
Part II: Cubic spline interpolation
The cubic spline s(x), which interpolates (x0, y0), (x1, y1), , (xn, yn), is a collection of
piecewise cubic polynomials satisfying
1) s(xi) = yi for i = 0, 1, · · · , n;
2) s(x), sJ(x), and sJJ(x) are continuous at x1, x2, , xn−1;
3) sJJ(x0) = sJJ(xn) = 0. (natural cubic spline)
Our derivation starts from the linear polynomial defined on [xi, xi+1]:
sJJ(x) = a
xi+1 − x
!
+ a
x − xi
!
, a , a : to be determined, i = 1 : n + 1.
Following the four steps as shown using all above conditions, we can obtain all ai’s from
solving the linear alge
aic system Aa = b as shown in step 4, where A ∈ R(n−1)×(n−1), a, b ∈
Rn−1 are two vectors, plus separated definition for a0 and an (we use the LUdecomp3.py
∈ −
· · ·
module to solve Aa = b). After obtaining all ai’s, for x [xi, xi+1], i = 0 : n 1, we can
approximate any values of y = s(x) by using the obtained spline as:
si(x) =
ai(xi+1 − x)3
6h
aih2
ai+1(x − xi)3
6h
ai+1h2
xi+1 − x
+ ci
x − xi
where bi = yi −
6
and ci = yi+1 −
6
.
For part II of this project, the routine of cubic spline interpolation has been coded in the
cubicSpline.py module. Study the module and interpolate n = 2, 4, 8, 16 points from f (x)
using cubic spline (e.g. k=curvatures(xData,yData)), then use the obtained cubic spline to
approximate the value of f (x) on a refined mesh (e.g. evalSpline(xData,yData,k,x)). Note:
Being different from the polynomial interpolation, the x value evaluated in evalSpline() must
e a scalar, thus a loop is needed to use each x[i] to evaluate s(x[i]) for vectors x and s(x).
On each of the four subplots for a specified n, plot function f (x) evaluated at x = −1.5 :
0.01 : 1.5, the interpolation points (x0, y0), (x1, y1), , (xn, yn) (n+1 points), and the ap-
proximated values from evaluating s(x) with a careful choice of styles of lines, markers, and
colors.
Project Specification
Your report should be produced using Jupyter notebook. Involved formulas should be typed
using Latex . The report should contain the following parts.
(1) (10pts) project description: describe the problem to solve and define polynomial interpo-
lation, uniform points and Chebyshev points, cubic spline, discuss in theory the advantages
and/or disadvantage of polynomial interpolation vs cubic spline, uniform points vs Cheby-
shev points.
(2) (10pts) code and explanation of the code (use comments to explain the code as needed)
(3) (10pts) numerical results and discussion: Numerical results should include one figure
of six subplots for polynomial interpolation and one figure of four subplots for cubic spline
interpolation. Discuss what you have observed, explain why by connecting to (2).
(4) (2pts) concluding remarks: summarize the project, and raise questions if there are any.
(5) (4pts) the report should be given in a neat, organized, readable, and professional way.
You may use section, markdown, and other functions of Jupyter notebook.
h h
+ + bi
Project Description
Project Specification