Atkinson K. An Introduction to Numerical Analysis
Подождите немного. Документ загружается.
218
APPROXIMATION OF FUNCTIONS
Using ( 4.5.5) and a straightforward computation of
II
rn*11
2
,
we
have Bessel's
inequality:
n
llrn*ll~
= L (/,
rpj)
2
~
llfll~
(4.5.9)
j=O
and
using (4.5.7) in (4.5.5),
we
obtain Parseual's equality,
(4.5.10)
Theorem 4.7 does not say that
II/-
rn*lloo
-->
0.
But if additional differentiability
assumptions are placed on
f(x),
results on the uniform convergence of
rn*
to
f
can be proved.
An
example
is
given later.
Legendre Polynomial Expansions To solve the least squares problem on a finite
interval
[a,
b) with w(x) =
1,
we
can convert it to a problem on [
-1,
1].
The
change
of
variable
x=
b+a+(b-a)t
2
(4.5.11)
converts the interval
-1
~
t
~
1 to a
~
x
~
b.
Define
(
b+a+(b-a)t)
F(t) = J
2
-l~t~l
(4.5.12)
for a given
f E
C[
a, b
].
Then
f
b
2
(
b - a )
J1
2
[J(x)-
rn(x)]
dx
= -
[F(t)-
Rn(t)]
dt
u 2
-1
with Rn(t) obtained from rn(x) using (4.5.11). The change of variable (4.5.11)
gives a one-to-one correspondence between polynomials of degree m
on
[a,
b)
and
of
degree m on [
-1,
1],
for every m
;;:::::
0.
Thus minimizing
II/-
rn11
2
on
[a, b] is equivalent to minimizing llrp-
Rn11
2
on [
-1,
1].
We
therefore restrict
our
interest to
the
least squares problem on [
-1,
1].
Given f E [
-1,
1], the orthonormal family described in Theorem 4.2
is
rp
0
(x)
=
1/fi,
The
least squares approximation
is
n
rn*(x) = L (!,
IP
1
)<F
1
(x)
j=O
n;;:::::
1 (4.5.13)
(!,
<F
1
)
= f
J(x)'<p
1
(x)
dx
(4.5.14)
-1
THE
LEAST SQUARES APPROXIMATION PROBLEM CONTINUED 219
Table 4.2
Legendre expansion
coefficients for
ex
j
(/,
cpj)
j
(/,
cp;)
0 1.661985
3
.037660
1
.901117
4
.004698
2
.226302
5
.000469
the solution of the original least squares problem posed
in
Section 4.3. The
coefficients
(/,
cp)
are called Legendre coefficients.
Example
For
f(x)
=ex
on [
-1,
1],
the expansion coefficients(/,
cp;)
of (4.5.14)
are given in Table 4.2. The approximation r
3
*(x)
was
given
earlier in (4.3.7),
written in standard polynomial form. For the average
errorE
in r
3
*(x),
combine
(4.3.4), (4.5.4), (4.5.9), and the table coefficients to
give
Chebyshev polynomial expansions The weight function
is
w(
x)
=
1j
/1
- x
2
,
and
1
cpo(x) = fii ,
The least squares solution
is
n
en
(X)
= L
(!,
cp;)
cp;(
X)
j=O
n
~
1
(
.)
=
J1
f(x)cp;(x)
dx
J,cp, ,; 2
-1
1-
X
Using the definition of
cpn(x)
in terms of Tn(x),
n
Cn(x) = I:' c
1
7J(x)
j=O
c.=~
{
f(x)IJ(x)
dx
1
'lT
-1
V1-x
2
( 4.5 .15)
(4.5.16)
(4.5.17)
The prime on the summation symbol means that the first term should be halved
before beginning to sum.
The Chebyshev expansion
is
closely related to Fourier cosine expansions.
Using x = cos 8, 0
~
8
~
'lT,
n
Cn(cosO) =I:' c
1
cos(j8)
j=O
. 2
'1r
c
1
=
-1
cos
(JO)f(cos 8)
dO
'lT
0
(4.5.18)
(4.5.19)
220 APPROXIMATION OF FUNCTIONS
Thus C,(cos
0)
is
the truncation after n + 1 terms of the Fourier cosine expan-
sion
00
/(cos
0)
=
"£'
cj cos (JO)
0
If
the Fourier cosine expansion on
[0,
'lT]
of
/(cos
0)
is
known, then by substitut-
ing 0 =
cos-
1
x,
we
have the Chebyshev expansion of
f(x).
For reasons to be
given
later, the Chebyshev least squares approximation
is
more useful than the Legendre least squares approximation. For this reason,
we
give a more detailed convergence theorem for (4.5.17).
Theorem 4.8 Let
f(x)
have r continuous derivatives on [
-1,
1],
with
r;;:::
1.
Then for the Chebyshev least squares approximation Cn(x) de-
fined in-(4.5.17),
B
Inn
II/-
Cnll."'
~
-,-
n
n;;:::2
(4.5.20)
for a constant
B dependent on f
and
r. Thus
C,(x)
converges
uniformly to
f(x)
as n
~
oo, provided
f(x)
is
continuously
differentiable.
Proof Combine Rivlin
(1974,
theorem 3.3,
p.
134) and Meinardus (1967,
theorem 45,
p.
57).
II
Example We illustrate the Chebyshev expansion
by
again considering ap-
proximations to
f(x)
=ex.
For the coefficients cj of (4.5.17),
c.=
~
t
ex~(x)
dx
1
'lT
-1
Vl-x
2
217f
= - ecosO COS (jO)
dO
'lT
0
(
4.5.2-1)
The latter formula
is
better for numerical integration, since there are no singulari-
ties in the integrand. Either the midpoint rule
or
the trapezoidal rule
is
an
Table 4.3 Chebyshev expansion
coefficients for ex
j
cj
0
2.53213176
1
1.13031821
2
.27149534
3
.04433685
4
.00547424
5
.00054293
THE
LEAST SQUARES APPROXIMATION PROBLEM CONTINUED
221
.Y
0.00607
-0.00588
Figure
4.6 Error in cubic Chebyshev least
squares approximation to
ex.
excellent integration method because of the periodicity
of
the integrand (see the
Corollary
1 to Theorem 5.5 in Section 5.4). Using numerical integration we
obtain the values given in Table
4.3. Using (4.5.17) and the formulas for
Tj(x),
we obtain
C
1
(x)
= 1.266 +
l.l30x
C
3
(x)
= .994571 + .997308x + .542991x
2
+ .177347x
3
(4.5.22)
The
graph of
ex-
C
3
(x)
is
given in Figure 4.6,
and
it is very similar to Figure
4.4, the graph for the minimax error. The maximum errors for these Chebyshev
least squares approximations are quite close to the minimax errors, and are
generally adequate for most practical purposes.
The
polynomial Cn(x) can be evaluated accurately and rapidly using the form.
( 4.5.17), rather than converting it to the ordinary form using the monomials
xi,
as was done previously for the example in (4.5.22). We make use of the triple
recursion relation
(4.4.13) for the Chebyshev polynomials Tn(x). The following
algorithm is due to
C.
W.
Clenshaw, and our presentation follows Rivlin (1974,
p. 125).
Algorithm Chebeval (a, n, x value)
1.
Remark: This algorithm evaluates
2.
bn+1
=
bn+2
:=
0
n
Value== L a
1
1j(x)
j=O
z = 2x
3. Do through step 5 for j = n, n -
1,
...
,
0.
222 APPROXIMATION
OF
FUNCTIONS
5. Next
j.
6. Value
•=
(b
0
-
b
2
)/2.
This
is
almost as efficient as the nested multiplication algorithm (2.9.8)
of
Section 2.9.
We
leave the detailed comparison to Problem 25. Similar algorithms
are
avail~ble
for other orthogonal polynomial expansions, again using their
associated triple recursion relation.
For
an analysis
of
the effect
of
rounding
errors in Chebeval, see Rivlin (1974, p. 127),
and
Fox
and
Parker (1968, p. 57).
4.6 Minimax Approximations
For
a good
uniform
approximation to a given function
f(x),
it seems reasonable
to
expect
the
error
to
be
fairly uttiformly distributed throughout
the
interval
of
approximation.
The
earlier examples with
f(x)
=
ex
further illustrate this point,
and
they show
that
the maximum error will oscillate
in
sign. Table 4.4 sum-
marizes
the
statistics for the various forms
of
approximation
to
ex
on
[....:
1, 1],
including
some
methods given in Section 4.7.
To
show the importance
of
a
uniform
distribution
of
the error, with the error function oscillating in sign, we
present
two theorems.
The
first one is useful for estimating p
11
(f),
the minimax
error,
without
having to calculate the minimax approximation
q!(x).
Theorem
4.9
(de
la
Vallee-Poussin) Let f E
C[a,
b]
and
n;;::: 0. Suppose we
have
a polynomial
Q(x)
of
degree~
n which satisfies
f(x)
-
Q(x)
= (
-1)
1
e
1
j = 0, 1,
...
, n + 1 (4.6.1)
with all e
1
nonzero
and
of the same sign,
and
with
a:$;;
Xo
< X
1
< · · · <
Xn+l
:$;;
b
Then
Table
4.4 Comparison of various linear and cubic approximations to
ex
Method of Approximation
Taylor polynomial
p,
(
x)
Legendre least squares r,';(x)
Chebyshev least squares
C,,
(
x)
Chebyshev node interpolation formula
I,(x)
Chebyshev forced oscillation formula
F,,
(
x)
Minimax q,";(x)
Maximum Error
Linear
.718
.439
.322
.372
.286
.279
Cubic
.0516
.0112
.00607
.00666
.00558
.00553
MINIMAX APPROXIMATIONS
223
Proof
The upper inequality in (4.6.2) follows from the definition of
Pn(/).
To
prove the lower bound,
we
assume it
is
false and produce a contradiction.
Assume
(4.6.3)
Then by the definition of
Pn(/),
there
is
a polynomial
P(x)
of
degree
.::;;
n for which
PnU)
.::;;
II!-
Plloo
< Mini e)
(4.6.4)
Define
R(x)
=
Q(x)-
P(x)
a polynomial of degree
.::;;
n. For simplicity, let all
ej
>
0;
an analogous
argument works when all
ej
<
0.
Evaluate
R(x)
for each j and observe the sign of
R(x).
First,
R(x
0
)
=
Q(x
0
)-
P(x
0
)
=
[f(xo)-
P(x
0
)]
-
[J(x
0
)-
Q(xo)]
=
[J(x
0
)
-
P(x
0
)]
- e
0
< 0
by using (4.6.4). Next,
Inductively, the sign of
R(x)
is
(
-I)j+l,
j =
0,
I,
...
, n +
1.
This gives
R(x)
n + 2 changes of sign and implies
R(x)
has n + I zeros. Since
degree
(R)
.::;;
n, this
is
not possible unless R =
0.
Then P =
Q,
contrary
to (4.6.I) and (4.6.4).
•
Example Recall the cubic Chebyshev least squares approximation Cn(x) to ex
on
[-I,
I], given in (4.5.22).
It
has the maximum errors on the interval
[-I,
I]
given in Table 4.5. These errors satisfy
"the
hypotheses
of
the Theorem 4.9, and
thus
.00497
.:5:
p
3
(!)
.:5:
.00607
Table 4.5 Relative
maxima
of
lex-
C
3
(x)l
X
ex-
C
3
(x)
- 1.0
.00497
- .6919 -
.00511
.0310
.00547
.7229 -.00588
1.0
.00607
224 APPROXIMATION
OF
FUNCTIONS
From this,
we
could conclude that C
3
(x)
was
quite close to the best possible
approximation. Note that p
3
(f)
= .00553 from direct calculations using (4.2.7).
Theorem 4.10 (Chebyshev Equioscillation Theorem) Let f E C[
a,
b]
and n
~
0.
Then there exists a unique polynomial
q:(x)
of degree
::;
n for
which
This polynomial is uniquely characterized by the following prop-
erty: There are
at
least n + 2 points,
for which
j = 0, 1,
...
, n + 1 (4.6.5)
with
CJ
= ±
1,
depending only on I
and
n.
Proof
The
proof
is
quite technical, amounting to a complicated and manipula-
tory
proof
by contradiction. For that reason, it
is
omitted.
For
a
complete development, see Davis (1963, chap.
7).
Ill
Example
The
cubic minimax approximation
qj'(x)
to
eX,
given in (4.2.7),
satisfies the conclusions of this theorem, as can
be
seen from the graph of the
error in Figure 4.4 of Section 4.2.
From this theorem
we
can see that the Taylor series
is
always a poor uniform
approximation.
The
Taylor series error,
(x-
X
r+l
l(x)-
Pn(x) =
0
f(n+ll(~)
(n+1)!
x
(4.6.6)
does
not
vary uniformly through the interval
of
approximation, nor does it
oscillate much in sign.
To
give a
better
idea of how well
q~(x)
approximates
l(x)
with increasing n,
we give the following theorem
of
D. Jackson.
Theorem 4.11 (Jackson) Let
l(x)
have k continuous derivatives for some
k
:2'::
0.
Moreover, assume l<k>(x) satisfies
Supremumit<k>(x)-
t<k>(y)l::;
Mix-
Yl" (4.6.7)
a5,x,
y5.b
for some M > 0 and some 0 <a.:::;;
1.
[We say j<k>(x) satisfies a
Holder condition with exponent
a.] Then there is a constant dk,
independent
of
I and n, for which
Mdk
Pn
(/}
::;
-,;+a
n
n
~
1
(4.6.8)
NEAR-MINIMAX
APPROXIMA TlONS
225
Table
4.6
Comparison of
p, and
M,
for
f(x)
=
e:r
n
2
3
4
5
6
7
M,(f)
1.13E-
1
1.42E-
2
1.42E-
3
1.18E-
4
8.43E-
6
5.27E-
7
p,(f)
4.50E-
2
5.53E-
3
5.47E-
4
4.52E-
5
3.21E-
6 2.00E ·- 7
Proof
See Meinardus (1967, Theorem 45, p. 57).
Note
that
if
we wish to ignore
(4.6.7) with a k-times continuously differentiable function
f(x},
then
just
use k - 1 in place of k in the theorem, with a = 1
and
M =
JIJ<k>lloo·
This will then yield
(4.6.9)
Also
note
that if
f(x)
is
infinitely differentiable, then
q:(x)
converges
to
f(x)
uniformly on
[a,
b),
faster than any
power
1/nk,
k
~
1.
•
From
Theorem
4.12 in the next section, we
are
able to prove the following
result.
If
/(
x)
is n + 1 times continuously differentiable on [a, b
],
then
(/)
<
[(b-
a)/2]n+lllf(n+l)ll = M
(/)
P, -
(n+.1)!2"
oo
n
(4.6.10)
The
proof
is left as Problem
38.
There are infinitely differentiable functions for
which
M,(f)
--+
oo.
However, for most
of
the widely used functions, the
bound
in (4.6.10) seems to be a fairly accurate estimate
of
the magnitude of
p,(f).
This
estimate is illustrated in Table 4.6 for
f(x)
= e"'
on
[
-1,
1].
For
other estimates
and
bounds
for
p,(f),
see Meinardus (1967, sec. 6.2).
4.7 Near-Minimax Approximations
In
the light
of
the
Chebyshev equioscillation theorem, we can deduce methods
that
often give a good estimate
of
the minimax approximation. We begin with the
least squares approximation
C,(x)
of
(4.5.17).
It
is
often a good estimate
of
q:(x},
and
our
other near-minimax approximations
are
motivated by properties
of
C,(x).
From
(4.5.17),
n
C,(x) =
L:'
c
1
1j(x)
J-0
c.=~
r
f(x)Ij(x)
dx
1
'1T
-1
/l-x
2
(4.7.1)
with the
prime
on
the summation meaning that
the
first term
(j
= 0) should
be
halved before summing the series. Using (4.5.7),
iff
E
C[
-1,
1], then
00
f(x)
=
L:'
c
1
1j(x)
(4.7.2)
j=O
.
226
APPROXIMATION OF FUNCTIONS
with convergence holding in the sense that
1 [ n
]2
Limitj
1
.j
2
f(x)-
L:'c/j(x)
dx=O
n-co
-1
1-
X
J-0
For uniform convergence, we have the quite strong result that
(4.7.3)
For
a proof, see Rivlin (1974,
p.
134). Combining this with Jackson's result
(4.6.9) implies the earlier convergence bound (4.5.20) of Theorem 4.8.
Iff
E
cr[a,
b), it can be proved that there
is
a constant
c,
dependent on f
and
r, for which
·c
jc
I<-
j-f
}?:.1
(4.7.4)
This is proved by considering the
cj
as the Fourier coefficients
of
/(cos
0), and
then by using results from the theory of Fourier series on the rate of·decrease
of
such coefficients. Thus
as
r becomes larger, the coefficients cj decrease more
rapidly.
For
the truncated expansion Cn(x),
co
j(x)-
Cn(x) = L
cj1j(x)
= cn+lTn+l(x)
(4.7.5)
n+l
if c n +
1
=I=
0
and
if the coefficients
cj
are rapidly convergent to zero. From the
definition
of
Tn+
1
(x),
-l.S:x.S:1
(4.7.6)
Also, for the n + 2 points
X . =
COS
(
__/_!!_
)
1
n + 1
j=O,l,
...
,n+l
(4.7.7)
we
have
(4.7.8)
The
bound in (4.7.6) is attained at exactly n + 2 points, the maximum possible
number. Applying this to (4.7.5), the term
cn+lTn+
1
(x)
has exactly n + 2 relative
maxima
and
minima, all of equal magnitude. From the Chebyshev equioscillation
theorem, we would therefore expect Cn(x) to be nearly equal to the minimax
approximation
q:(x).
NEAR-MINIMAX APPROXIMATIONS 227
Example
Recall the example (4.5.22) for
f(x)
= ex near the end of Section 4.5.
In it, the coefficients
cJ
decreased quite rapidly, and
Jlex
-
q)lloo
= .00553
This illustrates the comments of the last paragraph.
Example
It
can be shown that
(4.7.9)
converging uniformly for - I
:::;
x:::;
I,
with a =
\.1'2
- I = 0.414.
Then
(4.7.10)
For the error,
2
E
(
)
-1
C ( )
(-l)n+1
2n+3T
(
).
2n+1
X
=tan
X-
2n+1
X = 2n + 3 a
2n+3
X
We bound these terms
to
estimate the error in C
2
n +
1
(
x)
and the minimax error
Pzn+l(f).
By
taking upper bounds,
oo
(-l)Ja2J+l
oo
a2j+1
2
O'.~n+5
2L
2.
+ 1 TzJ+'t(x)
::;;
2 L
-2--
<
--5.
-~--,
n+2
1
n+
2
j + 1 2n + - a-
Thus
we
obtain upper and lower bounds for
Ezn+
1
(
x
),
using a
2
/(1
- a
2
)
= .207. Similarly,