HOMEWORK SOLUTIONS 4 (MATH 170B, WINTER 2022)
DUE DATE: SEE CANVAS
REVISION NUMBER: 4.0
INSTRUCTOR: Prof. Michael Holst
BOOKS:
[1] D. Kincaid and W. Cheney. Numerical Analysis: Mathematics of Scientific Computing. Third. Providence, RI: American Mathematical
Society, 2017.
MATERIAL COVERED BY HOMEWORK 4: This homework covers mainly material from lectures in weeks eight and nine (with a little
material from week seven, and the beginning of week ten). This covers roughly the following sections of [1]: 6.8, 7.1, 7.2, 7.3, 7.4.
SUBMITTING HOMEWORK ON GRADESCOPE: For non-computer problems, create a PDF file of your work by whatever means you prefer
(scanning handwritten work with your phone, or using LaTeX to typeset your mathematics, either is fine), and upload that PDF to Gradescope. For
computer problems, take a screen shot of both your MATLAB functions (the code you write) and the output they produce, and upload that PDF to
Gradescope.
OUR HOMEWORK RULES ALWAYS APPLY: As discussed in detail on the syllabus, you are allowed (encouraged) to discuss homework
problems with other students in our class, but you must write up your own solutions yourself. You are not allowed to post these questions, or their
solutions, on homework help websites (such as Chegg.com) or other websites.
[Q1] (Section 6.8: Problem 6.8.1-6.8.2)
Consider the function vpxq “ sinx on the interval r0, pi{2s.
(a) Find the best approximation upxq “ λx in the L8-norm.
(b) Find the best approximation upxq “ λx in the L2-norm.
(Hint: You have two tools: first-quarter calculus, and ideas we learned in Section 6.8 regarding best
approximation when we are fortunate enough to have an inner-product.)
Solution:
(a) Suppose the best approximation in the L8-norm is upxq “ λ0x, then
λ0 “ argmin
λ
}u´ v}L8 “ argmin
λ
p max
xPr0,pi
2
s
|sinx´ λx|q
When λ ą 1 or λ ă 0, we can easily find that |epx, λq| “ |sinx ´ λx| achieves its
maximum at x “ pi
2
.
Consider the case 0 ď λ ď 1. The maximum value of |epx, λq|might arise from either
the end points x “ 0, pi
2
or the critical point at which Bepx, λq{Bx “ 0.
First we find the local extrema. Bepx, λq{Bx “ cosx ´ λ “ 0, then consider the root
x0 “ arccosλ, at which point
epx0, λq “ sinparccosλq ´ λarccosλ “
?
1´ λ2 ´ λarccosλ
Compare this with the value at the endpoint x “ 0 and x “ pi
2
ep0, λq “ 0
eppi
2
, λq “ 1´ pi
2
λ
By plotting the graph of the functions sinx and x, we can observe that the minimum
of |sinx ´ λx| for 0 ď λ ď 1 attains when |eppi
2
, λq| “ |epx0, λq|. This leads to the
equation ?
1´ λ2 ´ λarccosλ “ pi
2
λ´ 1
for λ ě 2
pi
.
1
2 REFERENCES
Then the problem is transformed to calculate the root of the equation
?
1´ λ2 ´ λarccosλ´ pi
2
λ` 1 “ 0
You can use numerical method like Newton’s method to solve it.
(b) The best approximation upxq should satisfy the property that u ´ v K G, where G is
the space spanned by x. Thus we require that xu´ v, xy “ 0, which can be written as
xλx, xy “ xsinx, xyż pi{2
0
λx2 dx “
ż pi{2
0
xsinx dx
λ “ p
ż pi{2
0
xsinx dxq{p
ż pi{2
0
x2 dxq “ 3 ¨ p 2
pi
q3
[Q2] (Section 6.8: Problem 6.8.4)
Let p0, p1, p2, . . . be a (countably infinite) sequence of polynomials such that for each n,
the polynomial pnpxq has exact degree n. Show that the sequence is linearly independent.
(Hint: Think back on how we showed such things in 170A.)
Solution: Let pn1 , pn2 , . . . , pnk be a finite subset of p0, p1, p2, . . .with n1 ă n2 ă ¨ ¨ ¨ ă nk.
Suppose
ppxq ” a1pn1pxq ` a2pn2pxq ` ¨ ¨ ¨ ` akpnkpxq “ 0, @x.
Since pnk has exactly degree nk and p1, . . . , pnk´1 all have degree ă nk, we can write
ppxq “ akcxnk ` p˜pxq “ 0
where c ‰ 0 and p˜ is a polynomial of degree ă nk (we are just separating the leading term
of pnk from all the other lower-degree terms). This implies ak “ 0. But then
ppxq “ a1pn1pxq ` a2pn2pxq ` ¨ ¨ ¨ ` ak´1pnk´1pxq “ 0 @x
so a similar argument shows that ak´1 “ 0. We can continue this process to get
a1 “ a2 “ ¨ ¨ ¨ “ ak “ 0.
This shows that any finite subset pn1 , pn2 , . . . , pnk is linearly independent. Therefore p0, p1, p2, . . .
is linearly independent.
[Q3] (Section 6.8: Problem 6.8.5)
Let X be an inner-product space and let S Ă X be a finite-dimensional subspace spanned
by an orthonormal basis tukunk“1:
S “ spantu1, u2, . . . , unu.
Prove the Parseval identity for any f, g P S:
xf, gy “
nÿ
i“1
xf, uiyxg, uiy.
REFERENCES 3
(Hint: Just look at the entries of the Gram-matrix that shows up when you expand both f and g in
the basis, inside the inner-product, using the simple properties of the inner-product.)
Solution: Since f, g P S, we have f “
nř
i“1
fiui and g “
nř
i“1
giui where fi, gi P R are
coefficients for the linear combinations. Then we have
xf, gy “ x
nÿ
i“1
fiui,
nÿ
j“1
gjujy
“
nÿ
i“1
nÿ
j“1
figjxui, ujy
“
nÿ
i“1
figi
The second equality holds because of the linearity of the inner product. The third equal-
ity hold because tu1, . . . , unu are orthonormal.
Then we calculate the right hand side of the equation.
xf, uiy “ x
nÿ
j“1
fjuj, uiy
“
nÿ
j“1
fjxuj, uiy
“ fi
Similarly, we have xg, uiy “ gi. Combine all we get, we just show that the Parseval
identity holds.
[Q4] (Section 6.8: Problem 6.8.22)
Using Theorem 5 directly, find p0, p1, p2, p3 for ra, bs “ r0, 1s and ωpxq “ 1.
(Hint: This orthogonal polynomial family does not have a famous name.)
Solution: Following Theorem 5,
p0pxq “ 1
Next, p1pxq “ x´ a1, where
xxp0, p0y “ xx, 1y “
ż 1
0
x dx “ x2
2
ˇˇ1
0
“ 1
2
xp0, p0y “ x1, 1y “
ż 1
0
1 dx “ xˇˇ1
0
“ 1
a1 “ xxp0, p0y{xp0, p0y “ 12{1 “ 12
so
p1pxq “ x´ 12
4 REFERENCES
Next, p2pxq “ px´ a2qp1pxq ´ b2p0pxq, where
xxp1, p1y “ xxpx´ 12q, x´ 12y “
ż 1
0
xpx´ 1
2
q2 dx
“
ż 1
0
px3 ´ x2 ` x
4
q dx
“ px4
4
´ x3
3
` x2
8
qˇˇ1
0
“ 1
4
´ 1
3
` 1
8
“ 1
24
xp1, p1y “ xx´ 12 , x´ 12y “
ż 1
0
px´ 1
2
q2 dx
“
ż 1
0
px2 ´ x` 1
4
q dx
“ px3
3
´ x2
2
` x
4
qˇˇ1
0
“ 1
3
´ 1
2
` 1
4
“ 1
12
a2 “ xxp1, p1y{xp1, p1y “ 124{ 112 “ 12
xxp1, p0y “ xxpx´ 12q, 1y “
ż 1
0
xpx´ 1
2
q dx
“
ż 1
0
px2 ´ x
2
q dx
“ px3
3
´ x2
4
qˇˇ1
0
“ 1
3
´ 1
4
“ 1
12
xp0, p0y “ x1, 1y “ 1 pfrom beforeq
b2 “ xxp1, p0y{xp0, p0y “ 112{1 “ 112
p2pxq “ px´ 12qpx´ 12q ´ 112 “ x2 ´ x` 14 ´ 112
so
p2pxq “ x2 ´ x` 16
Finally, p3pxq “ px´ a3qp2pxq ´ b3p1pxq, where
xxp2, p2y “ xxpx2 ´ x` 16q, x2 ´ x` 16y “
ż 1
0
xpx2 ´ x` 1
6
q2 dx
REFERENCES 5
“
ż 1
0
px5 ´ 2x4 ` 4
3
x3 ´ 1
3
x2 ` 1
36
xq dx
“ p1
6
x6 ´ 2
5
x5 ` 1
3
x4 ´ 1
9
x3 ` 1
72
x2qˇˇ1
0
“ 1
6
´ 2
5
` 1
3
´ 1
9
` 1
72
“ 1
360
xp2, p2y “ xx2 ´ x` 16 , x2 ´ x` 16y “
ż 1
0
px2 ´ x` 1
6
q2 dx
“
ż 1
0
px4 ´ 2x3 ` 4
3
x2 ´ 1
3
x` 1
36
q dx
“ p1
5
x5 ´ 1
2
x4 ` 4
9
x3 ´ 1
6
x2 ` 1
36
xqˇˇ1
0
“ 1
5
´ 1
2
` 4
9
´ 1
6
` 1
36
“ 1
180
a3 “ xxp2, p2y{xp2, p2y “ 1360{ 1180 “ 12
xxp2, p1y “ xxpx2 ´ x` 16q, x´ 12y “
ż 1
0
xpx2 ´ x` 1
6
qpx´ 1
2
q dx
“
ż 1
0
px4 ´ 3
2
x3 ` 2
3
x2 ´ 1
12
xq dx
“ p1
5
x5 ´ 3
8
x4 ` 2
9
x3 ´ 1
24
x2qˇˇ1
0
“ 1
5
´ 3
8
` 2
9
´ 1
24
“ 1
180
xp1, p1y “ xx´ 12 , x´ 12y “ 112 pfrom beforeq
b2 “ xxp2, p1y{xp1, p1y “ 1180{ 112 “ 115
p3pxq “ px´ 12qpx2 ´ x` 16q ´ 115px´ 12q “ x3 ´ 32x2 ` 23x´ 112 ´ 115x` 130
so
p3pxq “ x3 ´ 32x2 ` 35x´ 120
[Q5] (Section 7.1: Related to Problems 7.1.5 and 7.1.12)
Formula (9) on page 469 of [1] for f2pxq is often used in the numerical solution of differ-
ential equations. By adding the Taylor series for fpx`hq and fpx´hq, show that the error
in this formula has the form
ř8
n“1 a2nh
2n.
(a) Determine the coefficients a2n explicitly.
6 REFERENCES
(b) Derive the error term given in Formula (9).
(c) Show how to use Richardson extrapolation if
L “ φphq ` a1h` a3h3 ` a5h5 ` ¨ ¨ ¨
(Hint: For the first two parts, just Taylor expand-away For the third part, just slightly modify the
derivation on page 472 in [1].)
Solution:
(a) We have
fpx` hq “
8ÿ
k“0
1
k!
hkf pkqpxq
fpx´ hq “
8ÿ
k“0
1
k!
p´1qkhkf pkqpxq
Then
f2pxq “ 1
h2
pfpx` hq ` fpx´ hq ´ 2fpxqq ´ p2h
2
4!
f p4qpxq ` 2h
4
6!
f p6qpxq ` ¨ ¨ ¨ q
“ 1
h2
pfpx` hq ` fpx´ hq ´ 2fpxqq ´
8ÿ
n“1
2 ¨ f p2n`2qpxq
p2n` 2q! h
2n
So the coefficients should be a2n “ 2¨f p2n`2qpxqp2n`2q! .
(b) Rewrite the Taylor expansion of fpx` hq and fpx´ hq as
fpx` hq “ fpxq ` hf 1pxq ` h
2
2
f2pxq ` h
3
3!
f3pxq ` h
4
4!
f p4qpξ1q
fpx´ hq “ fpxq ´ hf 1pxq ` h
2
2
f2pxq ´ h
3
3!
f3pxq ` h
4
4!
f p4qpξ2q
Add them together and rearrange, we get
f2pxq “ 1
h2
pfpx` hq ` fpx´ hq ´ 2fpxqq ´ h
2
4!
pf p4qpξ1q ` f p4qpξ2qq
Let c “ 1
2
pf p4qpξ1q` f p4qpξ2qq, if f p4q is continuous on the interval rx´h, x`hs, then
it assumes the value c at some point ξ in rx´ h, x` hs. Thus
f p4qpξq “ 1
2
pf p4qpξ1q ` f p4qpξ2qq
and
f2pxq “ 1
h2
pfpx` hq ` fpx´ hq ´ 2fpxqq ´ h
2
12
f p4qpξq
(c) To eliminate the leading term a1h in the error, first substitute h with h{2 we have
L “ ϕph
2
q ` a1h
2
` a3ph
2
q3 ` a5ph
2
q5 ` ¨ ¨ ¨
REFERENCES 7
Then multiply the latter one by 2 and subtract the former one from it
L “ 2ϕph
2
q ´ ϕphq ´ 3
4
a3h
3 ´ 15
16
a5h
5 ´ ¨ ¨ ¨
[Q6] (Section 7.2: Related to Problems 7.2.10 and 7.2.12)
Consider the quadrature formula:ż 1
´1
fpxq dx « Af p´1q `Bf p0q ` Cf p1q .
(a) Determine the coefficients A, B, and C that make the rule exact for all polynomials of
degree 2 by using the Newton-Cotes procedure of integrating the Lagrange interpolant.
(b) Determine the coefficients A, B, and C that make the rule exact for all polynomials of
degree 2 by using the Method of Undetermined Coefficients.
(c) Pick your favorite degree 2 (or less) polynomial, and show that the rule you derived is
in fact exact for your polynomial.
(Hint: Similar to discussion on pages 482–483 in [1].)
Solution:
(a) The Lagrange polynomials for nodes ´1, 0, and 1 are
`0pxq “ px´ 0qpx´ 1qp´1´ 0qp´1´ 1q “
1
2
xpx´ 1q “ 1
2
x2 ´ 1
2
x
`1pxq “ px` 1qpx´ 1qp0` 1qp0´ 1q “ ´px` 1qpx´ 1q “ ´x
2 ` 1
`2pxq “ px` 1qpx´ 0qp1` 1qp1´ 0q “
1
2
px` 1qx “ 1
2
x2 ` 1
2
x
The coefficients are
A “
ż 1
´1
`0pxq dx “
ż 1
´1
p1
2
x2 ´ 1
2
xq dx “ p1
6
x3 ´ 1
4
x2qˇˇ1´1 “ p16 ´ 14q ´ p´16 ´ 14q “ 13
B “
ż 1
´1
`1pxq dx “
ż 1
´1
p´x2 ` 1q dx “ p´1
3
x3 ` xqˇˇ1´1 “ p´13 ` 1q ´ p13 ´ 1q “ 43
C “
ż 1
´1
`2pxq dx “
ż 1
´1
p1
2
x2 ` 1
2
xq dx “ p1
6
x3 ` 1
4
x2qˇˇ1´1 “ p16 ` 14q ´ p´16 ` 14q “ 13
so A “ 1
3
, B “ 4
3
, and C “ 1
3
.
(b) Using the polynomials fpxq “ 1, x, and x2, we have
2 “
ż 1
´1
1 dx “ A`B ` C (1)
8 REFERENCES
0 “
ż 1
´1
x dx “ ´A` C (2)
2
3
“
ż 1
´1
x2 dx “ A` C (3)
Equation (2) gives A “ C. Plugging this into Equation (3) gives A “ C “ 1
3
. Then
plugging these into Equation (1) gives B “ 2
3
. So A “ 1
3
, B “ 4
3
, and C “ 1
3
as
in part (a).
(c) We will pick fpxq “ x2 ´ 2x` 1. For this degree 2 polynomial,ż 1
´1
fpxq dx “
ż 1
´1
px2 ´ 2x` 1q dx “ p1
3
x3 ´ x2 ` xqˇˇ1´1 “ p13 ´ 1` 1q ´ p´13 ´ 1´ 1q “ 83
and
Afp´1q `Bfp0q ` Cfp1q “ 1
3
p4q ` 4
3
p1q ` 1
3
p0q “ 8
3
so the rule is exact.
[Q7] (Section 7.3: Related to Problem 7.3.22)
Consider the quadrature formula from Example 1 on page 496 in [1]:ż 1
´1
fpxq dx « 5
9
f
˜
´
c
3
5
¸
` 8
9
f p0q ` 5
9
f
˜c
3
5
¸
,
which was derived using the Legendre polynomials as an example of a Gaussian Quadra-
ture rule that is exact for polynomials of degree 5.
(a) Show that the same formula can be derived using either the Newton-Cotes procedure
or the Method of Undetermined Coefficients, by simply taking the roots of the Le-
gendre polynomials as the interpolation points.
(b) Pick your favorite degree 5 (or less) polynomial, and show that the rule is in fact exact
for your polynomial.
(c) Transform the formula to one for integration over ra, bs instead of r´1, 1s.
(d) Apply the formula to:
şpi{2
0
x dx.
(Hint: For the first part, just follow the discussion on pages 482-483 in [1]. For the third part, use
the idea for changing intervals described on page 485. For the last part, just use the transformation.)
Solution:
(a) Newton-Cotes: Suppose we interpolates at x0 “ ´
b
3
5
, x1 “ 0, x2 “
b
3
5
, then the
three coefficients in the estimate formula
ş1
´1 fpxq dx « A0fp´
b
3
5
q ` A1fp0q `
A2fp
b
3
5
q can be calculated as
A0 “
ż 1
´1
px´ x1qpx´ x2q
px0 ´ x1qpx0 ´ x2q dx “
5
6
ż 1
´1
xpx´
c
3
5
q dx “ 5
9
REFERENCES 9
A1 “
ż 1
´1
px´ x0qpx´ x2q
px1 ´ x0qpx1 ´ x2q dx “ ´
5
3
ż 1
´1
px2 ´ 3
5
q dx “ 8
9
A2 “
ż 1
´1
px´ x0qpx´ x1q
px2 ´ x0qpx2 ´ x1q dx “
5
6
ż 1
´1
xpx`
c
3
5
q dx “ 5
9
The method of undetermined coefficients: again for the estimate formula
ş1
´1 fpxq dx «
A0fp´
b
3
5
q ` A1fp0q ` A2fp
b
3
5
q, using the polynomials 1, x, x2, we get
2 “ A0 ` A1 ` A2
0 “ ´
c
3
5
A0 ` 0`
c
3
5
A2
2
3
“ 3
5
A0 ` 0` 3
5
A2
Solving the above linear system we can get the same values of A0, A1, A2 as before.
(b) For fpxq “ x5, the exact value of the integration should be ş1´1 x5 dx “ 0. By the
formula we haveż 1
´1
fpxq dx « 5
9
p´
c
3
5
q5 ` 8
9
¨ 0` 5
9
p
c
3
5
q5 “ 0
(c) First we define the function λptq “ b´a
2
t` a`b
2
such that when t traverses r´1, 1s, λptq
will traverse ra, bs. Then we haveż b
a
fpxq dx “ b´ a
2
ż 1
´1
fpλptqq dt
« b´ a
2
«
5
9
f
˜
λp´
c
3
5
q
¸
` 8
9
f pλp0qq ` 5
9
f
˜
λp
c
3
5
q
¸ff
(d) ż pi{2
0
x dx « pi
4
«
5
9
ppi
4
¨ ´
c
3
5
` pi
4
q ` 8
9
p0` pi
4
q ` 5
9
ppi
4
¨
c
3
5
` pi
4
q
ff
“ pi
2
8
[Q8] (Section 7.2/7.3/7.4: Related to Problem 7.2.7 and others)
We wish to approximate the following integral to 8 digits of accuracy:ż 1
0
ex
2
dx. (1.1)
(a) In MATLAB, implement a numerical integration of this function using a truncated
n-term Taylor expansion as on page 480 in [1], using just enough terms n to achieve
the accuracy.
10 REFERENCES
(b) In MATLAB, implement the Composite Trapezoid Rule (equation (4) on page 482) to
approximate a general integral:ż b
a
fpxq dx,
taking as input: a, b, f and n (the number of subintervals). Apply your implementation
to integrate (1.1), using just enough points/intervals n to achieve the required accuracy.
(c) In MATLAB, implement the Composite Simpson Rule (page 484) to approximate a
general integral: ż b
a
fpxq dx,
taking as input: a, b, f and n (the number of subintervals). Apply your implementation
to integrate (1.1), using just enough points/intervals n to achieve the required accuracy.
(d) Compare n for all three approaches.
Solution:
(a) Truncated Taylor expansion:
1 function I = part_a(n)
2
3 I = 0;
4 for k = 0:n
5 I = I + 1/((2*k+1)*factorial(k));
6 end
(b) Composite Trapezoid Rule:
1 function I = composite_trapezoid(a,b,f,n)
2
3 h = (b-a)/n;
4
5 I = h*f(a)/2;
6 for i=1:(n-1)
7 I = I + h*f(a+i*h);
8 end
9 I = I + h*f(b)/2;
(c) Composite Simpson Rule:
1 function I = composite_Simpson(a,b,f,n)
2
3 h = (b-a)/n;
4
5 I = h*f(a)/3;
6 I = I + 4*h*f(a+h)/3; % i=1
7 for i=2:(n/2)
8 I = I + 2*h*f(a+(2*i-2)*h)/3;
REFERENCES 11
9 I = I + 4*h*f(a+(2*i-1)*h)/3;
10 end
11 I = I + h*f(b)/3;
(d) The exact integral to 8 digits is
ş1
0
ex
2
dx “ 1.46265174. The number of terms needed
for 8 digits of accuracy with each method is:
– Part (a): n “ 10
– Part (b): n “ 10522
– Part (c): n “ 94

欢迎咨询51作业君