Atkinson K. An Introduction to Numerical Analysis
Подождите немного. Документ загружается.
238
APPROXIMATION
OF
FUNCTIONS
Askey,
R.
(ed.) (1975b). Theory and Application
of
Special Functions. Academic
Press, New York.
Baker, G., Jr. (1975). Essentials
of
Pade Approximants. Academic Press, New
York.
Brezinski, C. (1980). Pade-Type Approximation and General Orthogonal Polynomi-
als_.
Birkhauser,
Basel.
Cody,
W.
(1984). FUNPACK-A package of special function routines. In Sources
and
Development
of
Mathematical Software,
W.
Cowell (ed.), pp. 49-67.
Prentice-Hall, Englewood Cliffs, N.J.
Cody,
W.
and
W.
Waite
(1980).
Software Manual for the Elementary Functions.
Prentice-Hall, Englewood Cliffs, N.J.
Cody, W.,
W.
Fraser, and
J.
Hart (1968). Rational Chebyshev approximation
using linear equations.
Numer. Math.,
12,
242-251.
Davis,
P.
(1963). Interpolation and Approximation. Ginn (Blaisdell), Boston.
Erdelyi, A.,
W.
Magnus, F. Oberhettinger, and F. Tricomi (1953). lfigher
Transcendental Functions,
Vols.
I,
II, and III. McGraw-Hill, New York.
Fox, L., and
I.
Parker
(1968).
Chebyshev Polynomials in Numerical Analysis.
Oxford Univ. Press, Oxford, Englimd.
Fraser,
W.
(1965). A survey of methods of computing minimax and near-mini-
max polynomial approximations for functions of a single independent
variable.
J.
ACM,
12,
295-314.
Gautschi, W. (1975). Computational methods in special
functions-A
survey. In
'
R.
Askey (ed.), Theory and Application
of
Special Functions, pp. 1-98.
Academic
Press, New York.
Hart, J.,
E.
Cheney,
C.
Lawson,
H.
Maehly,
C.
Mesztenyi, J. Rice,
H.
Thacher,
and
C. Witzgall
(1968).
Computer Approximations. Wiley, New York. (Re-
printed in 1978, with corrections,
by
Krieger, Huntington, N.Y.)
Isaacson, E., and
H.
Keller (1966). Analysis
of
Numerical Methods. Wiley, New
York.
Lorentz, G. (1966). Approximation
of
Functions. Holt, Rinehart & Winston, New
York.
Luke,
Y.
(1969). The Special Functions and Their Applications,
Vols.
I and II.
Academic Press, New York.
Luke,
Y.
(1975). Mathematical Functions and Their Approximations. Academic
Press, New York.
Luke,
Y.
(1977). Algorithms for the Computation
of
Mathematical Functions.
Academic Press, New York.
Meinardus, G. (1967). Approximation
of
Functions: Theory and Numerical Meth-
ods
(transl.
L.
Schumaker). Springer-Verlag, New York.
Powell,
M.
(1981). Approximation Theory and Methods. Cambridge Univ. Press,
Cambridge, England.
Rice, J. (1964).
The Approximation
of
Functions: Linear Theory. Addison-Wesley,
Reading, Mass.
PROBLEMS 239
Rice,
J.
(1968). The Approximation
of
Functions: Advanced Topics. Addison-
Wesley, Reading, Mass.
Rivlin,
T.
(1974). The Chebyshev Polynomials. Wiley, New York.
Shampine,
L.
(1970). Efficiency of a procedure for near-minimax approximation.
J.
ACM,
17,
655-660.
Szego, G. (1967). Orthogonal Polynomials, 3rd
ed.
Amer. Math.
Soc.,
Providence,
R.I.
Wall,
H.
(1948). Analytic Theory
of
Continued Fractions. Van Nostrand, New
York.
Zygmund,
A. (1959). Trigonometric Series,
Vols.
I and II. Cambridge Univ. Press,
Cambridge, England.
Problems
1.
To illustrate that the Bernstein polynomials Pn(x) in Theorem4.1 are poor
approximations, calculate theJour:th-degree approximation
Pn(x) for
f(x)
= sin(7rx), 0 s x s
1.
Compare it with the fourth-degree Taylor poly-
nomial approximation, expanded about
x =
t.
00
2.
Let S = L (
-1
)ja
j be a convergent series, and assume that
all
a j
;:::.
0 and
1
Prove that
3. Using
Problem
2,
examine the convergence of the following
series.
Bound
the error
when.'.
truncating after n terms,
and
note the dependence on x.
Find the value of n for which the error is less than
lo-
5
•
lh.is
problem
illustrates another common technique for bounding the
error
in
Taylor
series.
(a)
(b)
4.
Graph the errors of the Taylor series approximations
Pn(.x)
10
f(x)
=
sin[(7r/2)x] on
-1
s x s
1,
for n =
1,
3,5.
Note
the behaviorof
the
error
both near the origin and near the endpoints.
PROBLEMS
241
Obtain a formula for a polynomial
q(x)
approximating
/(x),
with the
formula for
q(x)
inv.olving
a single integral.
(c) Assume that
f(x)
is
infinitely differentiable on [a,
b],
that
is,
JU>(x)
exists and
is
continuous on [a, b
],
for all j
~
0.
[This does not imply
that
f(x)
has a convergent Taylor series on
[a,
b].]
Prove there exists
a sequence of polynomials {
Pn(x)jn
~
1}
for which
Limit
II
/(j)
- P!j)
II
= 0
n-co
oo
for all j
~
0.
Hint: Use the Weierstrass theorem and part (b).
9.
Prove the following result. Let f E C
2
[a,
b]
with
f"(x)
> 0 for as;; xs;;
b.
If
qi(x)
= a
0
+ a
1
x
is
the linear minimax approximation to
f(x)
on.
[a,
b],
then
f(b)-.J(a)
al
=
b-
a
=
/(a)
+/(c)
_
(a
+
c)
[/(b)
-/(a)
] ·
00
2 2 ·
b-
a
where c
is
the unique solution of
f'(c)
=/(b)-
f(a)
b-a
What is
p?
10. (a) Produce the linear Taylor polynomials
to/(
x)
= ln (
x)
on 1
s;;
x
s;;
2,
expanding about x
0
=
f.
Graph the error.
(b) Produce the linear minimax approximation to
f(x)
= ln
(x)
on
[1,
2].
Graph the error, and compare it with the Taylor approximation.
11. (a) Show that the linear minimax approximation to
VI
+ x
2
on
[0,
1]
is
qi(
x)
=
.955
+ .414x
(b) Using part (a), derive the approximation
Vy
1
+ z
2
=
.955z
+ .414y
and determine the error.
12. Find the linear least squares approximation to
/(x)
=
ln(x)
on [1,2].
Compare the error with the results of Problem
10.
13. Find the value of a that minimizes
242 APPROXIMATION OF FUNCTIONS
What
is the minimum? This is a simple illustration of yet another way to
measure the error
of
an approximation
and
of the resulting best approxima-
tion.
14. Solve
the
following minimization problems and determine whether there
is
a unique value
of
a that gives the minimum. In each case, a
is
allowed to
range
over all real numbers. We are approximating the function
f(x)
= x
with polynomials
of
the form
ax
2
•
(a)
Min
J
1
[x-
ax
2
]
2
dx
a
-1
(b)
~in
f
1
1x
-
ax
2
1
dx
(c)
Min
Max lx -
ax
2
1
a
-l:Sx:Sl
15.
Using
(4.4.10), show that {Pn(x)} IS
an
orthogonal family
and
that
IIPnlb =
/2/(2n
+ 1), n
~
0.
16.
Verify
that
for n
~
0 are orthogonal on the interval [0,
oo)
with respect to the weight
function
w(x)
=e-x.
(Note:
{'><:>
e-xxm
dx
=
m!
for m = 0, 1, 2
...
)
17.
(a)
Find
the relative maxima
and
minima of Tn(x) on [
-1,
1], obtaining
(4.7.21).
(b)
Find
the zeros of
TAx),
obtaining (4.7.14).
18.
Derive
the
formulas for
bn
and
en
given in the triple recursion relation in
(4.4.21)
of
Theorem 4.5.
19. Modify the
Gram-Schmidt
procedure
of
Theorem 4.2, to avoid the normal-
ization step
IPn
=
lfin/111fnll2:
lfn(x) =
Xn
+ bn.n-tlfin-l(x) + · · · +bn.olfio(x)
.
and
find the coefficients
bn,
j•
0
~j
~
n - 1.
20.
Using Problem 19, find
1f
0
,
1f
1
,
1f
2
for the following weight functions
w(x)
on
the
indicated intervals
[a,
b
].
(a)
w(x)
=
ln(x),
O~x~l
n>O
240 APPROXIMATION
OF
FUNCTIONS
5. Let
/(x)
be
three times continuously differentiable on
[-a,
aJ
for some
a >
0,
and
consider
approximating
it by
the
rational function
a+
bx
R(x)
=
_1_+_c_x
To
generalize the
idea
of the
Taylor
series,
choose
the constants a,
b,
and
c
so
that
j =
0,1,2
Is
it
always possible to find
such
an
approximation
R(x)?
The
function
R(x)
is
an
example
of
a Pade approximation to
f(x).
See Baker (1975)
and
Brezinski (1980).
6.
Apply
the results
of
Problem 5
to
the
case
/(x)
=ex,
and give the resulting
approximation
R(x).
Analyze its
error
on
[
-1,
1],
and
compare
it
with
the
error
for
the
quadratic
Taylor
polynomial.
7. By
means
of
various identities,
it
is often possible to reduce the interval
on
which
a function needs
to
be
approximated.
Show how
to
reduce each
of
the
following functions from -
oo
< x <
oo
to
the
given interval. Usually a
few
additional,
but
simple,
operations
will
be
needed.
(a)
ex
0
~X~
1
(b)
cos(x)
0
~
x s; 'IT/4
{c)
tan-
1
(x)
0
s;
x
~
1
(d)
ln(x)
1
~
x s; 2.
Reduce
from
ln(x)
on
0 < x <
oo.
8. (a)
Let
f(x)
be
continuously differentiable
on
[a,
bJ.
Let
p(x)
be
a
polynomial
for which
II/' -
Plloo
s; £
and
define
q(x)
=/(a)+
jxp(t)
dt
a
Show
that
q(
x)
is
a polynomial
and
satisfies
11/-
qlloo
s;
£(b-
a)
{b)
Extend
part
(a)
to
the
case
where
f(x)
is N times
continuously
differentiable
on
[a,
b], N;;:: 2,
and
p(x)
is a polynomial satisfying
11/{N)
-
Plloo
~
(
PROBLEMS
243
(b)
w(x)
= x
O~x~1
(c)
w(x)=~
-1~x~1
21. Let {
<Jln(x)!n
~
1}
be orthogonal on
(a,
b)
with weight function
w(x)
~
0.
Denote the zeros of
<pn(x)
by
a<zn,n<zn-1.n<
...
<z1,n<b
Prove
that
the zeros
of
<Jln+
1
(x)
are separated by those
of
<pn(x),.
that is,
a<
zn+I,n+I <
zn,n
< zn,n+I <
...
<
z2,n+l
< zl,n < zl,n+I < b
Hint: Use induction on the degree n.
Write
<pn(x)
= Anxn + · ·
·,
with
An
> 0,
and
use the triple recursion relation ( 4.4.21) to evaluate the
polynomials
at
the zeros of
<pn(x).
Observe that the sign changes for
<Jln_
1
(x)
and
<Jln+I(x).
22. Extend the Christoffel-Darboux identity (4.4.27) to the case with x = y,
obtaining a formula for
£
[cpk(x)]2
k=O
"Yk
Hint: Consider the limit in (4.4.27) as y
-+
x.
23. Let
f(x)
=
cos-
1
(x)
for
-1
~
x
~
1
(the
principal branch 0
~~~
?T).
24.
Find
the polynomial
of
degree two,
which minimizes
!
I
[J(x)-
p(x
)]
2
----.,==~,.......:.-
dx
-1
/1-x
2
1
Define
Sn(x)
=
--
1
T~+
1
(x),
n
~
0, with
T,+
1
(x)
the Chebyshev poly-
n+
nomial
of
degree n +
1.
The polynomials
Sn(x)
are called Chebyshev
polynomials
of
the second kind.
(a) Show that
{Sn(x)!n~O}
is an orthogonal family on
[-1,1]
with
respect to the weight fmiction
w(
x)
=
·./1
- x
2
•
(b) Show that the family { Sn(x)} satisfies the same triple recursion
relation (4.4.13) as the family
{Tn(x)}.
244
APPROXIMATION
OF
FUNCTIONS
(c)
Given f E C(
-1,
1),
solve the problem
Min
f/1- x
2
[J(x)-
P
11
(x)]
2
dx
where p
11
(x)
is
allowed to range over all polynomials
of
degree::;;; n.
25.
Do
an operations count for algorithm Chebeval of Section 4.5. Give the
number of multiplications and the number
of
additions. Compare this to
the ordinary nested multiplication algorithm.
26. Show
that
the framework
of
Sections 4.4
and
4.5
also applies to the
trigonometric polynomials
of
degree
::;;;
n. Show
that
the family
{1,sin(x),cos(x),
...
,sin(nx),cos(nx)}
is
orthogonal
on
[0,277]. Derive
the least squares approximation to
f(
x)
on [0, 2
7T]
using such polynomials.
[Letting
n
~
oo,
we
obtain the well-known Fourier series (see Zygmund
(1959))].
27. Let
/(x)
be
a continuous even (odd) function
on
[-a,
a]. Show that the
minimax approximation
q:(x)
to
f(x)
will
be
an
even (odd) function on
[-a,
a], regardless of whether n
is
even
or
odd.
Hint: Use Theorem 4.10,
including
the
uniqueness result.
28. Using (4.6.10}, bound p
11
(/)
for the following functions
f(x)
on the given
interval, n
=
1,
2,
...
,
10.
(a)
sin(x)
0::;;;
X::;;;
7Tj2
(b)
ln(x)
1:;;;x:;;;e
(c)
tan-
1
(x)
O:;;;x:;;;7Tj4
(d)
ex
O:;;;x:;;;1
29.
For
the Chebyshev expansion (4.7.2), show
that
if
f(x)
is even (odd) on
[
-1,
1], then
cj
= 0 if j is odd (even).
30.
For
f(x)
= sin[(7T/2)x], -1::;;;
x::;;;
1, find both the Legendre and
Chebyshev least squares approximations of degree three to
f(x).
Determine
the error in each approximation
and
graph them. Use Theorem 4.9 to
bound
the minimax error p
3
(/).
Hint: Use numerical integration to sim-
plify constructing the least squares coefficients. Note the comments follow-
ing (4.7.13), for the Chebyshev least squares approximation.
31. Produce the interpolatory near-minimax approximation
In(x)
for the fol-
lowing basic mathematical functions
f
on
the indicated intervals, for
n = 1, 2,
...
,
8.
Using the standard routines
of
your computer, compute the
error.
Graph
the error, and using Theorem 4.9, give
upper
and lower
bounds for
P
11
(/).
(b)
sin(x)
(d) ln
(x)
O:;;;x,:;;;7Tj2
PROBLEMS
245
32. Repeat Problem
31
with
the near-minimax approximation Fn(x
).
33. Repeat Problem
31
and
32
for
1
1
x sin {t)
f(x)
=-
--dt
X 0 t
7T
0
<X<-
- - 2
Hint: Find a Taylor approximation of high degree for evaluating
f(x),
then
use the transformation (4.5.12)
to
obtain
an
approximation problem on
[
-1,
1).
34. For
f(x)
=ex
on [
-1,
1],
consider constructing
ln(x).
Derive the error
result
-1.:::;;
X.:::;;
1
for appropriate constants an,
f3n·
Find nonzero upper and lower bounds for
Pn(/).
35. (a) The function sin (
x)
vanishes at x =
0.1n
order
_to
better approximate
it in a relative error sense,
we
consider the function
f(x)
=
sin(x)jx.
Calculate the near-minimax approximation
ln(x)
on
0.:::;;
x.:::;;
7Tj2
for
n =
1,
2,
...
,
7,
and then compare sin
(x)
-
xln(x)
with the results of
Problem 31(b).
(b) Repeat part (a)
for
f(x)
=
tan-
1
(x),
O.::;;x.::;;l.
36. Let
f(x)
= anxn + · · ·
+a
1
x + a
0
,
an
=1=-
0.
Find the minimax approxima-
tion to
f(x)
on [
-1,
1]
by
a polynomial of
degree.:::;;
n -
1,
and also
find
Pn-l(f).
37. Let a = Min [Max I x
6
-
x
3
-
p
5
(
x)
1],
where the minimum
is
taken over
jxj.s
1 .
all polynomials of degree
.:::;;
5.
(a)
Find a.
(b) Find the polynomial p
5
(x)
for
which the minimum a
is
attained.
38. Prove the result (4.6.10).
Hint: Consider the near-minimax approximation
ln(x).
39.
(a)
For
f(x)
=ex
on [
-1,
1],
find
the Taylor polynomial p
4
(x)
of degree
four, expanded about
x =
0.
(b) Using Problem
36,
find
the minimax polynomial m
4
•
3
(x)
of degree
three that approximates
p
4
(x).
Graph the error
ex-
m
4
•
3
(x)
and
compare it to the Taylor error
ex-
PJ(x)
shown in Figure 4.1. The
process of reducing a Taylor polynomial to a lower degree one by this
246
APPROXIMATION OF FUNCTIONS
process
is
called economization or telescoping.
It
is
usually used
several times
in
succession, to reduce a high-degree Taylor polynomial
to
a polynomial approximation of much lower degree
..
40. Using a standard program from your computer center for computing
minimax approximations, calculate the minimax approximation
q:(x)
for
the following given functions
f(x}
on the given interval. Do this for
n = 1,
2,
3,
...
,
8.
Compare the results with those for problem
31.
(b) sin
(x)
O.:S:x.:S:'fT/2
(d)
ln (X) 1
~
X
~
2
41. Produce the minimax approximations
q:(x),
n =
1,
3,
5,
7,
9,
for
1
jx
2
f(x)
= ;-
e-
1
dt
Hint: First produce a Taylor approximation of high accuracy, and then use
it with the program of
Problem
40.
42. Repeat Problem
41
for
1
1
x sin
(t)
f(x)
=-
--dt
X 0 t
lxl
.:S:.,
FIVE