hw4.dvi
Mathematics 5610—Home Work 4—Monday November 15, 2021, 2018−1−
As you know I recommend you work on these problems with one or two partners. If you
do your team should hand in just one set of answers.
Email me a pdf with your typeset answers to the following questions on
Friday, December 3, 2021
efore the lecture−2−. All questions have equal weight.
-1- (Spline versus Cubic Hermite Interpolation.) Let the function s(x) be defined by
s(x) =
{
(γ − 1)(x3 − x2) + x+ 1 if x ∈ [0, 1]
γx3 − 5γx2 + 8γx− 4γ + 2 if x ∈ [1, 2]
a. Show that s is the piecewise cubic Hermite interpolant to the data:
s(0) = 1, s(1) = s(2) = 2, s′(0) = 1, s′(1) = γ, s′(2) = 0
. For what value of γ does s become a cubic spline?
-2- (More on Cubic Splines.) Consider the data
xi : XXXXXXXXXX
yi : XXXXXXXXXX
(1)
a. Construct the cubic interpolant, i.e., find the cubic polynomial p that satisfies
p(xi) = yi, i = 1, 2, 3, 4 (2)
and draw its graph.
. Construct the interpolating natural cubic spline and draw its graph.
c. Comment on your results.
-3- (Polynomial Interpolation.) Suppose you want to interpolate to the data (xi, yi),
i = 0, . . . , n by a polynomial of degree n. Recall that the interpolating polynomial p can
e written in its Lagrange form as
p(x) =
n
∑
i=0
yiLi(x) where Li(x) =
Πi 6=j(x− xj)
Πi 6=j(xi − xj)
. (3)
Show that
n
∑
i=0
xjiLi(x) = x
j for j = 0, . . . , n. (4)
−1− Peter Alfeld, XXXXXXXXXX, TEX processing date: November 13, 2021.
−2− Procrastination is hazardous.
Math 5610, Fall 2018, Home Work #4, page 1
-4- (The infamous Runge-Phenomenon.) It is not generally true that higher degree
interpolation polynomials yield more accurate approximations. This is illustrated in this
problem. Let
f(x) =
1
1 + x2
and xj = −5 + jh, j = 0, 1, · · · , n, h =
10
n
.
Fo
n = 1, 2, 3, · · · , 20
plot the graph (in the interval [-5,5]) of the interpolant
p(x) =
n
∑
i=0
αix
i
defined by
p(xi) = f(xi), i = 0, 1, · · · , n.
-5- (Judicious interpolation.) Repeat the above except that you interpolate at the roots
of the Chebycheff polynomials, i.e.,
xi = 5 cos
iπ
n
, i = 0, 1, . . . , n. (5)
-6- (The interpolant to symmetric data is symmetric.) Suppose you are given sym-
metric data
(xi, yi), i = −n,−n+ 1, · · · , n− 1, n, (6)
such that
x−i = −xi, and y−i = −yi i = 0, 1, · · · , n. (7)
What is the required degree of the interpolating polynomial p? Show that the interpolating
polynomial is odd, i.e.,
p(x) = −p(−x) (8)
for all real numbers x.
-7- (Uniqueness of the interpolating polynomial.) Assume you are given the data
xi : XXXXXXXXXX
yi : XXXXXXXXXX
(9)
Construct the interpolating polynomial using
a. the power form,
. the Lagrange form,
Math 5610, Fall 2018, Home Work #4, page 2
c. the Newton form,
and show that they all yield the same polynomial.
-8- (The Method of undetermined coefficients.) Suppose that for some reason you wish
to use a differentiation formula of the form
f ′(a) =
1
h
[
α0f(a) + α1f(a+
h
3
) + α2f(a+
h
2
) + α3f(a+ h)
]
(10)
where the αs are chosen so as to make the formula exact for polynomials of degree as high
as possible. What are the αs?
-9- (Recu
ence Relation.) Consider the inner product
(f, g) =
∫
1
−1
f(x)g(x)dx. (11)
Use the recu
ence relation
Qn = (x− an)Qn−1 − bnQn−2
with Q0 = 1, Q1 = x− a1,
an = (xQn−1, Qn−1)/(Qn−1, Qn−1)
n = (xQn−1, Qn−2)/(Qn−2, Qn−2) (12)
to compute Qi for i = 0, 1, 2, 3, 4, 5.
-10- (More on the Recu
ence Relation.) Remember that a key property of the inne
products for which we established the three term relation was that (xf, g) = (f, xg). Find
an inner product that violates that rule, and for which the recu
ence relation does indeed
fail to yield orthogonal polynomials. (Thus use the recu
ence relation (12) to construct
the first few polynomials, until you find two that are not orthogonal.)
-11- (Example for Gram Schmidt Process.) Use the Gram-Schmidt Process to find a basis
of
span{1, x, ex}
that is orthonormal with respect to the inner product
(f, g) =
∫
1
0
f(x)g(x)dx. (13)
Math 5610, Fall 2018, Home Work #4, page 3
Math 5610 Fall 2021
Notes of 11/5/21
Continuous Least Squares
• We have already discussed the idea in the
past, but for our purposes today let’s rein-
troduce it in its simplest form.
• Suppose f is continuous on [a, b] and we want
to approximate it by a linear combination of
asis functions
f(x) ≈ p(x) =
n
∑
i=1
αiφi(x) (1)
• The basis functions φi could be polynomials,
for example,
φi(x) = x
i−1, (2)
ut they may not be.
• For example, we could use periodic, exponen-
tial, or rational functions depending on what
we know about f .
• We pick the coefficients αj such that
F (α1, . . . ,αn) =
∫
a
n
∑
j=1
αjφj(x)− f(x)
2
dx = min .
(3)
Math 5610 Fall 2021 Notes of 11/5/21 page 1
• This approach is called Continuous Linea
Least Squares
− Continuous because we are approximat-
ing a function, not a vector (which would
lead to a discrete least squares problem).
− Linear because we approximate by a lin-
ear combination of basis functions, which
will give rise to a linear system of equa-
tions. Linear does not mean that the ap-
proximating function p is linear!
− Least because we minimize.
− Squares because we minimize the integral
of a square.
• We can find the linear system by the stan-
dard Calculus approach of computing partial
derivatives of F and setting them to zero:
∂
∂αi
F (α1, . . . ,αn) =
∫
a
2
n
∑
j=1
αjφj(x)− f(x)
φi(x) = 0.
(4)
• This can be rewritten as the linear system
n
∑
j=1
αj
∫
a
φj(x)φi(x)dx =
∫
a
φi(x)f(x)dx, i = 1, 2, . . . , n
(5)
• We have actually seen this before in the spe-
cial case that
[a, b] = [0, 1] and φi(x) = x
i−1. (6)
Math 5610 Fall 2021 Notes of 11/5/21 page 2
• The coefficient matrix of that linear system is
the infamous Hilbert Matrix
[ ∫ 1
0
xi−1xj−1dx
]
=
[
1
i+j−1
]
i,j,1,...,n
(7)
• of course, we know that the Hilbert Matrix
is extremely ill-conditioned, so we need to be
careful with our choice of basis functions.
• Moreover, the integral
∫
a
f(x)g(x)dx looks much
like the dot product
f • g = fT g =
n
∑
i=1
figi (8)
of two vectors f and g.
• It’s a powerful simplifying principle that inte-
grals behave just like sums.
• There must be a way to exploit the similarity.
• The relevant concept here is that of an inne
product, which is a generalization of the fa-
miliar dot product”.
• The basic generalization procedure (we saw
this earlier for norms) is to ask what proper-
ties of some concept are important, and then
what other objects have the same properties.
• The relevant important properties of the dot
Math 5610 Fall 2021 Notes of 11/5/21 page 3
product are:
uT v = vTu
uTu ≥ 0
uTu = 0 ⇐⇒ u = 0
(αu+ βv)Tw = αuTw + βvTw
(9)
• We also use the dot product to define the 2-
norm of vectors:
‖u‖2 =
√
uTu. (10)
• All these properties ca
y over when we re-
place the vectors with functions.
• An inner product is a function that asso-
ciates a number (f, g) with two continuous
functions f and g defined on an interval [a, b]
such that these properties hold:
(f, g) = (g, f)
(f, f) ≥ 0
(f, f) = 0 ⇐⇒ f = 0
(αf + βg, h) = α(f, h) + β(g, h)
(11)
• moreover, we define the inner product norm
‖f‖ =
√
(f, f). (12)
Math 5610 Fall 2021 Notes of 11/5/21 page 4
up ut f g
fig
• The requirement of continuity can be relaxed.
• As in the case of the standard inner products
of vectors, we say that two functions f and
g are orthogonal (with respect to the inne
product (·, ·)) if
(f, g) = 0. (13)
Math 5610 Fall 2021 Notes of 11/5/21 page 5
Examples of Inner Products
• For vectors there are possible inner products
other than the dot product. For example if A
is symmetric and positive definite then
(u, v) = uTAv (14)
defines an inner product (exercise).
• For functions inner products can be used, fo
example, to give extra weight to the end points
or other specific points, or to incorporate deriva-
tives (provided the functions involved are dif-
ferentiable).
• For example, the following define inner prod-
ucts (exercise):
(f, g)1 =
∫
a
f(x)g(x)dx
(f, g)2 =
∫
a
w(x)f(x)g(x)dx, w > 0
(f, g)3 =
∫
a
w(x)f(x)g(x) + ŵ(x)f ′(x)g′(x)dx, w > 0, ŵ ≥ 0
(f, g)4 =
∫
a
w(x)f(x)g(x)dx+ f(c)g(c), w > 0
(15)
• Proceeding just as before one can show easily
(exercise) that for any inner product (·, ·) the
Math 5610 Fall 2021 Notes of 11/5/21 page 6
A I U U UTV
solution of
F (α1, . . .αn) = (f−
n
∑
i=1
αiφi, f−
n
∑
i=1
αiφi) = min
(16)
is given by the solution of the linear system
Ha = b (17)
where
H = [(φi,φj)], a =
α1
...
αn
, and b =
(f,φ1)
.