Atkinson K. An Introduction to Numerical Analysis
Подождите немного. Документ загружается.
PROBLEMS
187
convenient size for actual use) and to how many significant digits should
the table entries be given?
7. Repeat Problem
6,
but using
ex
on 0
:::;
x
:::;
1.
8. Generalize to quadratic interpolation the material on the effect
of
rounding
errors in table entries, given in Section 3.1. Let
€;
=
f(xJ
-/,
i =
0,
1,
2,
and
t:
~Max
{l£
0
1,
lt:
1
1,
l£
2
1}.
Show that the effect
of
these rounding errors
on the quadratic interpolation error
is
bounded by 1.25t:, assuming x
0
:::;
x
:::;
x
2
and
x
1
-
x
0
= x
2
-
x
1
=
h.
9. Repeat Problem
6,
but use quadratic interpolation and the result
of
Problem
8.
10.
Consider producing a table
of
values for
f(x)
= log
10
x, 1:::; x:::; 10, and
assume quadratic interpolation
is
to be used. Let the total interpolation
error, including the effect of rounding in table entries, be less than
10-
6
•
Choose an appropriate grid spacing h and the number
of
digits to which
the entries should be given. Would it be desirable to vary the spacing h as x
varies in [1, lOJ?If so, suggest a suitable partition
of
[1,
10] with correspond-
ing values
of
h. Use the result
of
Problem 8
on
the effect
of
rounding error.
11.
Let x
0
,
•••
, x n be distinct real points, and consider the following interpola-
tion problem. Choose a function
such
that
n
Pn(x) = L
cjejx
j=O
i =
0,1,
...
, n
with the {
Y;}
given data. Show there
is
a unique choice of c
0
,
...
,
en.
Hint:
The problem can
be
reduced to that of ordinary polynomial interpolation.
12. Consider finding a rational function
p(x)
=(a+
bx)/(1
+ex)
that
satisfies
p(x;)
=
Y;
i =
1,2,3
with x
1
,
x
2
,
x
3
distinct. Does such a function
p(x)
exist,
or
are additional
conditions needed to ensure existence and uniqueness
of
p(x)?
For
a
general theory of rational interpolation, see Stoer
and
Bulirsch (1980,
p. 58).
13. · (a) Prove the recursive form
of
the interpolation formula, as given
in
(3.2.8).
(b)
Prove the recursion formula (3.2.7) for divided differences.
188 INTERPOLATION THEORY
14.
Prove the relations (3.2.18), pertaining to the variable divided difference of
a polynomial.
15.
Prove
that
Vol(rn) =
1/n!,
where
rn
is
the simplex in
Rn
defined in (3.2.14)
of
Theorem
3.3
in Section 3.2. Hint: Use (3.2.13) and other results on
divided differences, along with a special choice for
f(x).
16.
Let p
2
(x)
be the quadratic polynomial interpolating
f(x)
at the evenly
spaced points
x
0
,
x
1
= x
0
+
h,
x
2
= x
0
+
2h.
Derive formulas for the
errors
f'(x;)-
p7_(x;),
i =
0,
1,
2.
Assuming
f(x)
is
three times continu-
ously differentiable, give computable bounds for these errors.
Hint: Use the
error formula
(3.2.11).
17.
Produce computer subroutine implementations of the algorithms Diudif
and
Interp given in Section 3.2, and then write a main driver program to
use them in doing table interpolation. Choose a table from Abramowitz and
Stegun
(1964) to test the program, considering several successive degrees of
n for the interpolation polynomial.
18.
Do
an
inverse interpolation problem using the table for J
0
(x)
given in
Section
3.2. Find the value of x for which J
0
(x)
=
0,
that
is,
calculate an
accurate estimate of the root. Estimate your accuracy, and compare this
with the actual value x
= 2.4048255577.
19.
Derive the analogue of Lemma
1,
given m Section 3.3, for backward
differences.
Use this and Newton's divided form of the interpolating
polynomial (3.2.9) to derive the backward difference interpolation formula
(3.3.11).
20.
Consider the following table of values for
taken from Abramowitz and Stegun (1964, chap. 10).
X
io(x)
X
io(x)
0.0 1.00000
0.7
.92031
0.1 .99833 0.8 .89670
0.2
.99335 0.9 .87036
0.3
.98507 1.0
.84147
0.4
.97355
1.1
.81019
0.5
.95885 1.2
.77670
0.6
.94107
1.3
.74120
PROBLEMS
189
Based
on
the rounding errors in the table entries, what should be the
maximum degree of polynomial interpolation used with the table? Hint:
Use the forward difference table to detect the influence of the rounding
errors.
21. The following data are taken from a polynomial
of
degree
:::;:
5.
What is the
degree
of
the polynomial?
-1
0 1 2 3
1 1 1 7
25
22.
The
following data have noise in them
that
is large relative to rounding
error.
Find
the noise and change the data appropriately. Only the function
values are given, since the node points are unnecessary for computing the
forward difference table.
304319
326313
348812
371806
395285
419327
443655
468529
493852
519615
545811
572433
599475
626909
654790
683100
711709
740756
770188
800000
23.
For
f(x)
= 1/(1 + x
2
),
-5:::;:
x:::;:
5,
produce Pn(x) using n + 1 evenly
spaced nodes on
[-
5,
5).
Calculate Pn(x)
at
a large number of points, anq
graph
it
or
its error on
[-
5,
5),
as in Figure
3.6.
24. Consider the function ex
on
[0,
b] and its approximation by an interpolat-
ing polynomial. For n
;;:::.
1,
let h =
bjn,
xj
=
jh,
j =
0,
1,
...
, n, and let
Pn(x)
be
the nth-degree polynomial interpolating ex on the nodes
Xo,
...
' xn. Prove that
as
n-+oo
Hint: Show
l'~'n(x)l
:::;:
n!hn+l, 0
:::;:
x:::;:
b;
look separately at each subinter-
val
[xj-l•
xJ
25. Prove that the general Hermite problem
(3.6.16)
has a unique solution
p(x)
among all polynomials
of
degree
:::;:
N -
1.
Hint: Show that the homoge;
neous problem for the associated linear system has only the zero solution.
26.
Consider the Hermite problem
i=1,2
j=0,1,2
with
p(x)
a polynomial
of
degree:::;:
5.
(a) Give a Lagrange type
of
formula for
p(x),
generalizing
(3.6.12)
for
cubic Hermite interpolation. Hint:
For
the basis functions satisfying
190 INTERPOLATION THEORY
/(x
2
)
=
/'(x
2
)
= /"(x
2
)
= 0,
use
l(x)
=
(x-
x
2
)
3
g(x), with
g(x)
of
degree
.::;
2.
Find
g(x).
(b) Give a Newton divided difference formula, generalizing (3.6.13).
(c) Derive an error formula generalizing (3.6.14).
27. Let
p(x)
be
a polynomial solving the Hermite interpolation problem
pU>(b)
= JUl(b)
j = 0, 1,
...
, n - 1
Its existence
is
guaranteed by the argument in Problem
25.
Assuming
f(x)
has 2n continuous 9erivatives on [a,
b],
show that
for
a.::; x.::;
b,
with a
.::;
~x.::;
b.
Hint: Generalize the argument used in Theorem
3.2.
28. (a) Find a polynomial
p(x)
of degree.::; 2 that satisfies
Give a formula in the form
(b) Find a formula
for
the following polynomial interpolation problem.
Let
xi=
x
0
+ ih, i =
0,
1,
2.
Find a polynomial
p(x)
of degree.::; 4
for which
i = 0,
1,
2
with the y values given.
29. Consider the problem of finding a quadratic polynomial
p(x)
for which
with
x
0
* x
2
and
{y
0
,
y{, y
2
}
the given data. Assuming that the nodes
x
0
,
x
1
,
x
2
are real, what conditions must be satisfied for such a
p(x)
to
exist
and
be unique? This problem, Problem 28(a), and the following
problem are examples of
Hermite-Birkhoff interpolation problems
[see
Lorentz
et
al.
(1983)).
PROBLEMS
191
30.
(a) Show there
is
a unique cubic polynomial p (
x)
for which
where
f(x)
is
a given function and x
0
'*
x
2
•
Derive a formula for
p(x).
(b) Let x
0
=
-1,
x
1
=
0,
x
2
=
1.
Assuming
f(x)
is
four times continu-
ously differentiable on [
-1,
1],
show that for
-1
.::;;
x
.::;;
1,
for some
~x
E [
-1,
1).
Hint: Mimic the proof of Theorem
3.2.
31.
For
the function
f(
x)
= sin ( x
),
0
.::;;
x
.::;;
.,
/2,
find the piecewise cubic
Hermite function
Q,.(x)
and the piecewise cubic Lagrange function
Lm(x),
for n = 3,6,
12,
m =
!n.
Evaluate the maximum errors
j(x)-
Lm(x),
f'(x)
- L:.,(x),
j(x)-
Q,.(x), and
f'(x)-
Q~(x).
This can be done with
reasonable accuracy by evaluating the errors at
8n
evenly spaced points on
[0, w/2].
32. (a) Let p
3
(x)
denote the cubic polynomial interpolating
j(x)
at the
evenly spaced points
xj
= x
0
+
jh,
j =
0,
1,
2,
3.
Assuming
j(x)
is
sufficiently differentiable, bound the error in using
p:3(
x)
as
an
approximation to
j'(x),
x
0
~
x
~
x
3
•
(b) Let H
2
(x)
denote the cubic Hermite polynomial interpolating
j(x)
and
f'(x)
at x
0
and x
1
= x
0
+ h. Bound the error
f'(x)
- HJ.(x) for
x
0
.:5:
x
.:5:
x
1
•
(c)
Consider the piecewise polynomial functions
Lm(x)
and
Q,.(x)
of
Section
3.7,
m =
2n/3,
and bound the errors
f'(x)
- L:.,(x) and
f'(x)-
Q~(x).
Apply it to the specific case of
f(x)
= x
4
and com-
pare your answers with the numerical results given in Table 3.14.
33. Let
s(x)
be a spline function of order m. Let b be a knot, and let
s(x)
be a
polynomial of
degree.::;;
m-
1 on [a, b] and [b,
c).
Show that if
s<m-tl(x)
is
continuous at x =
b,
then
s(x)
is
a polynomial of
degree.::;;
m - 1 for
a.::;;
x.:::;;
c.
34. Derive the conditions on the cubic interpolating spline
s(x)
that are
implied by the
"not-a-knot" endpoint conditions. Refer to the discussion of
case
2,
following (3.7.27).
192 INTERPOLATION THEORY
35. Consider finding a cubic spline interpolating function for the data
1 2
2.5
3
4
0.6
1.0
.65
.6
1.0
Use the
"not-a-knot"
condition to obtain boundary conditions supplement-
ing
(3.7.19). Graph the resulting function
s(x).
Compare it to the use of
piecewise linear interpolation, connecting the successive points
(xi,
Yi)
by
line segments.
36.
Write
a program to investigate the rate of convergence of cubic spline
interpolation (as in Table
3.13) with various boundary conditions. Many
computer
centers will have a package to produce such an interpolant, with
the
user allowed to specify the boundary conditions. Otherwise, use a linear
systems solver with
(3.7.19) and the additional boundary conditions. In-
vestigate the following boundary conditions: (a) derivatives given as in
(3.7.20);
(b)
the
"not-a-knot"
condition, given in Problem 34; and (c) the
natural
spline conditions, M
0
=
Mn
=
0,
o{
Problem 38. Apply this pro-
gram to studying the convergence of
s(x)
to
f(x)
in the following cases:
(1)
f(x)
= ex on
[0,
1],
(2)
/(x)
=
sin(x)
on
[0,
'11'/2],
and (3)
f(x)
=
x/X
on
[0,
1].
Note
and compare the behavior
of
the error near the endpoints.
37.
(a)
Let
q(x)
be a cubic spline with a single knot x = a.
In
addition,
suppose that
q(x)
= 0 for x
::s;
a.
Show that
q(x)
=
c(x-
a)~
for
some
c.
Hint:
For
x;;:::
a, write the cubic polynomial
s(x)
as
Then
apply the assumptions about
s(x).
(b)
Using
part (a), prove the representation (3.7.31) for cubic spline
functions (
m = 4).
38.
Consider calculating a cubic interpolating spline based on (3.7.19) with the
additional boundary conditions
·
~(x
0
)
= M
0
= 0
This
has a unique solution s(x). Show that
t"[.f'(x)J2 dx s {,"[g"(x)F dx
where
g(x)
is
any twice continuously differentiable function that satisfies
the
interpolating conditions
g(xi)
= yi, i = 0, 1,
...
, n.
lfint:
Show (3.7.27)
is valid for s(x). [This interpolating spline
s(x)
is called the natural cubic
interpolating spline.
It
is
a smooth interpolant to the data,
but
it usually
converges slowly near the endpoints.
For
more information on it, see
de
Boor (1978, p. 55).]
PROBLEMS 193
39. To define a B-spline of order m, with
[x
1
,
x
1
+ml
the interval on which it
is
nonzero, define
with
fx(t)
=
(t-
xr;-
1
.
Derive a recursion relation for
B,tm>(x)
in terms
of B-splines of order
m -
1.
40. Use the definition (3.7.33) to investigate the behavior of cubic B-splines
when nodes are allowed to coincide.
Show that if two of the nodes in
{x
1
,
x
1
+1,
.•.
, x
1
+4}
coincide, then B
1
(x)
has only one continuous deriva-
tive
at
the coincident node. Similarly, if three of them coincide, show that
B
1
(x)
is continuous
at
that point,
but
is
not differentiable.
41. Let 0::;; t
0
< t
1
< · · · < t
2
n <
27T,
and consider the trigonometric poly-
nomial interpolation problem (3.8.5). Define
for
j =
0,
1,
...
,.2n. Easily,
1/t;)
=
oij,
0
::;;
i,
j
::;;
2n. Show that
f/t)
is a
trigonometric polynomial of degree
::;;
n.
Then
the solution to (3.8.5)
is
given by
2n
Pn(t) = L
J(tJfj(t)
j=O
Hint: Use induction on n, along with standard trigonometric identities.
42. (a) Prove the following formulas:
m-1
(
27Tjk)
L sin
--
= 0, m
;;:::
2,
all integers k
J=1 m
m~1
(27Tjk)
{m
i...J
cos
--
=
J=O
m 0
k a multiple of m
k
not
a multiple of m
(b)
Use these formulas to derive
forri.mlas
for the following:
m-1
(27Tjk)
(27Tj/)
I:
cos
--
cos
--
j=o
m m
m-1.
(27Tjk).
(27Tj/)
L
sm
--
sm
--
J=1
m m
m-1
(27Tjk)
.
(27Tj/)
L cos
--
sm
--
J=O
m m
194
INTERPOLATION THEORY
for 0
~
k, I
~
m -
1.
The formulas obtained are referred
to
as
discrete orthogonality relations, and they are the analogues of integral
orthogonality relations for {cos (
kx
),
sin (
kx)}.
43. Calculate the finite Fourier transform of order m of the following se-
quences.
(a)
xk
= 1
O~k~m-l
O~k<m-l
m even
(c)
xk
= k
O~k~m-l
FOUR
APPROXIMATION
OF FUNCTIONS
To evaluate most mathematical functions,
we
must first produce computable
approximations to them. Functions are defined in a variety of
ways
in applica-
tions, with integrals and infinite series being the most common types of formulas
used for the definition. Such a definition
is
useful in establishing the properties of
the
function,
but
it is generally not an efficient way to evaluate the function. In
this chapter
we
examine the use of polynomials as approximations to a given
function. Various means of producing polynomial approximations are described,
and they are compared
as
to their relative accuracy.
For
evaluating a function
f(x)
on a computer, it
is
generally more efficient of
space and time to have an analytic approximation to
f(x)
rather than to store a
table and use interpolation. It
is
also desirable
to
use the lowest possible degree
of polynomial that
will
give
the desired accuracy in approximating
f(x).
The
following sections
give
a number of methods for producing an approximation,
and generally the better approximations are also the more complicated to
produce. The amount of time and
effort expended on producing an approxima-
tion should be directly proportional to
hdw much the approximation
will
be used.
If
it
is
only
to
be used a
few
times; a truncated Taylor series
will
often suffice. But
if an approximation
is
to be used millions of times by many people, then much
care should be used
in
producing·· the approximation.
There are forms of approximating functions other than polynomials. Rational
functions are quotients of polynomials, and they are usually a somewhat more
efficient form of approximation. But because polynomials furnish an adequate
and efficient form of approximation, and because the theory for rational function
approximation
is
more complicated than that of
poly!J-omial
approximation,
we
have chosen to consider only polynomials. The results of this chapter can also be
used to produce piecewise polynomial approximations, somewhat analogous to
the piecewise polynomial interpolating functions of Section
3.7
of the preceding
chapter.
4.1 The Weierstrass Theorem
and
Taylor's Theorem
To justify using polynomials to approximate continuous functions,
we
present the
following theorem.
197