Atkinson K. An Introduction to Numerical Analysis
Подождите немного. Документ загружается.
208 APPROXIMATION OF FUNCTIONS
the polynomials, based on polynomials that are orthogonal in a function space
sense that
is
given below. These results are of fundamental importance
in
the
approximation of functions and
for
much work
in
classical applied mathematics.
Let
w(x)
be the same
as
in
(4.3.8) and (4.3.9), and define the inner product of
two continuous functions
f and g by
(/,g)=
tw(x)f(x)g(x)
dx
a
f,gE
C[a,b]
Then the following simple properties are easily shown.
1.
(a./,
g)=(/,
a.g)
= a.(f,
g)
for all scalars a
2.
Ut
+ /2,
g)=
Ut,
g)+
U1,
g)
(/,
gl + g2) =
(/,
gl) +
(/,
g2)
3.
(/,g)
=
(g,
f)
4.
(/,
f)
~
0 for
all
f E C[ a, b
J,
and
(/,
f)
= 0 if and only if
f(x)
= 0, a
.::;;
x.::;;
b
Define the two
norm
or Euclidean norm by
(4.4.1)
(4.4.2)
This definition will satisfy the norm properties (4.1.6)-(4.1.8). But the proof of
the triangle inequality (4.1.8)
is
no longer obvious, and it depends on the
following well-known inequality.
Lemma
(Cauchy-Schwartz inequality) For
f,
g E C[a,
b],
J(!,
g)
J.::;;
ll/llzllgll2
(4.4.3)
Proof
If
g =
0,
the result
is
trivially true. For g *
0,
consider the following.
For
any real number
a.,
0.::;;
(/
+
a.g,
f + a.g)
=(/,f)+
2a.(/,
g)+
a.2(g,
g)
The polynomial on the right has at most one real root, and thus the
discriminant cannot be positive,
4j(/,
g) 1
2
-
4(/,
/)(g,
g).::;;
0
This implies (4.4.3). Note that
we
have equality in (4.4.3) only if the
discriminant
is
exactly zero. But that implies there
is
an
a.*
for which the
polynomial
is
zero. Then
(!
+ a* g, f +
a*
g) = 0
ORTHOGONAL POLYNOMIALS
209
and thus f =
-a*
g.
Thus equality holds in ( 4.3.4) if and only if either
(1)
f is a multiple of
g,
or
(2)
for
g
is
identically zero. •
To
prove
th(.
triangle inequality (4.1.8),
II!+
gil~=(!+
g,J
+g)=
(f,J)
+ 2{!,
g)+
(g,
g)
:s:
11/11~+
211fll211gll2
+
llgll~
=
(11/112
+
llgll2)
2
Take
square roots of each side of the inequality to obtain
II!+
gllz
:S:
ll/1!2
+
llgll2
(4.4.4)
We are interested in obtaining a basis for the polynomials other than the
ordinary basis, the monomials
{1,
x, x
2
,
.••
}.
We produce what
is
called an
orthogonal basis, a generalization of orthogonal basis in the space
Rn
(see
Section 7.1). We say thai
f and g are orthogonal if
(f,g)=O
( 4.4.5)
The
following
is
a constructive existence result for orthogonal polynomials.
Theorem 4.2 (Gram-Schmidt) There exists a sequence of polynomials
{ cpn(x)jn
~
0}
with degree(cpn) = n, for all n, and
for all
n
=I=
m
n,
m
~
0 (4.4.6)
In
addition,
we
can construct the sequence with the additional
properties: (1)
(<pn,
cpn)
=
1,
for all
n;
(2) the coefficient of xn in
<Fn(x)
is
positive. With' these additional properties, the sequence
{
<Fn
} is unique.
Proof
We show a constructive and recursive method
of
obtaining the members
·of
the sequence; it is called the Gram-Schmidt process. Let
IPo(x)
= c
a constant. Pick it such that
II~Poll
2
= 1
and
c >
0.
Then
(cp
0
,
cp
0
)
= c
2
jbw(x)
dx
= 1
a
[
b ]
-1/2
c=
iw(x)dx
For
constructing
cp
1
(x), begin with
210 APPROXIMATION OF FUNCTIONS
Then
(
1/11,
cro)
= 0 implies 0 =
(x,
cro)
+ al.o(
<Jlo,
<Jlo)
-
Jhxw(x)
dx
al.O
= -
(x,
<Jlo)
=
__
a
___
_
[£bw(x)
dxf
12
Define
and note that
and the coefficient of
x
is
positive.
To construct
<pn(x
),
first define
(4.4.7)
and choose the constants to make
1/1
n.
orthogonal
to
<pj
for j =
0,
...
,
n-
1. Then
j =
0,
1,
...
,
n-
1 (4.4.8)
The desired
cpn(x)
is
(4.4.9)
Continue the derivation inductively.
1!111
Example
For
the special case of w(x1 =
1,
[a,
b]
= [
-1,
1],
we
have
<iln(X)
= A
<p~(x)
=
~A
(3x~
-
I)
and further polynomials can be constructed
by
the same process.
There
is
a very large literature on these polynomials, including a variety of
formulas for them.
Of necessity
we
only skim the surface. The polynomials are
usually given in a form for which
II<Jlnll
2
'*
1.
Particular Cases
1.
The Legendre polynomials. Let w(x) = 1 on [
-1,
1).
Define
(
-1)"
d"
2 n
Pn(x)
= -
2
n
1
•
-d
J(1-
X ) ]
n. x
n
~
1
(4.4.10)
ORTHOGONAL
POLYNOMIALS
211
with P
0
(x)
=
1.
These are orthogonal
on
[
-1,
1],
degree
Pn(x)
= n, and
Pn(1)
= 1 for all n. Also,
(4.4.11)
2.
The Chebyshev polynomials. Let
w(
x)
= 1 I h - x
2
,
-1
.::;;
x
.::;;
1.
Then
n;;:::;O
(4.4.12)
is
an orthogonal family of polynomials with
deg
(Tn) = n. To
see
that Tn(x)
is
a
polynomial, let
cos-
1
x =
8,
0
::;;
8
::;;
1f.
Then
Tn±
1
(x)
=
cos(n
± 1)8 =
cos(n8)cos8
+
sin(n8)sin8·
Tn+
1
(x)
+
Tn_
1
(x)
=
2cos(n8)cos8
=
2Tn(x)x
Also by direct calculation in
(4.4.12),
Using (4.4.13)
The polynomials also satisfy
Tn(1)
= 1, n
;;:::
1,
n¢m
m=n=O
n = m > 0
n;;:::
1 (4.4.13)
(4.4.14)
The Chebyshev polynomials are extremely important in approximation theory,
and they also arise in many other areas of applied mathematics. For a more
complete discussion of them,
see
Rivlin
(1974),
and
Fox and Parker
(1968).
We
give further properties of the Chebyshev polynomials in the following sections.
3. The Laguerre polynomials. Let
w(x)
=e-x,
[a,
b]
=
[0,
oo).
Then
n;;:::;O
( 4.4.15)
212 APPROXIMATION
OF
FUNCTIONS
JJL,JJ
2
= 1 for all n, and {L,} are orthogonal on
[0,
oo)
relative to the weight.
function
e-x.
We say that a family of functions
is
an orthogonal family if each member
is
orthogonal to every other member of the family. We call it an orthonormal family
if it
is
an
orthogonal family and if every member has length one, that
is,
IIIII
2
= 1. For other examples of orthogonal polynomials, see Abramowitz and
Stegun
(1964, chap. 22), Davis (1963, app.), Szego (1968).
Some properties of orthogonal polynomials These results
will
_be
useful later in
this chapter and in the
next chapter.
Theorem
4.3 Let { <p,(x)Jn
~
0}
be an orthogonal family of polynomials on
(a,
b)
with weight function w(x). With such a family
we
always
assume implicitly that degree
<p,
= n, n
~
0.
If
f(x)
is
a poly-
nomial of degree m, then
(
)
~
(!,
<p,) ( )
f X =
i...J
( )
<p,
X
n~O
<p,,
IPn
(4.4.16)
Proof
We begin by showing that every polynomial can be written
as
a combina-
tion of orthogonal polynomials of no greater degree. Since degree (
<p
0
)
=
0, we have
<p
0
(x)
=
c,
a constant, and thus
Since degree (
<p
1
)
=
1,
we
have from the construction m the
Gram-Schmidt
process,
By
induction in the Gram-Schmidt process,
and
1
x'
=
-[<p,(x)-
c, ,_
1
<p,_
1
(x)-
· · ·
-c,
oiPo(x)]
c , I 1
r,
r
Thus every monomial can be rewritten as a combination of orthogonal
polynomials of no greater degree. From this it follows easily that an
ORTHOGONAL
POLYNOMIALS 213
arbitrary
polynomial
f(x)
of
degree m
can
be written as
for some choice
of
b
0
,
•••
,
bm.
To
calculate each
b;,
multiply
both
sides
by
w(x)
and
'P;(x),
and
integrate over
(a,
b). Then
m
U.'P;)
=
L:
bj('Pj•'Pi) = b;('P;.cp;)
j-0
which proves (4.4.16)
and
the theorem.
Corollary
If
f(x)
is a polynomial
of
degree~
m - 1, then
and
'Pm(x) is-orthogonal to
f(x).
•
(4.4.17)
Proof
It
follows easily from (4.4.16) and
the
orthogonality
of
the family
{
'Pn(x)}. g
The
following result gives some intuition as
to
the shape
of
the graphs
of
the
orthogonal
polynomials.
It
is also crucial to the
work
on
Gaussian
quadrature
in
Chapter
5.
Theorem 4.4 Let { 'Pn(x)in;;:::;
0}
be
an orthogonal family
of
polynomials
on
(a,
b)
with weight function
w(x)
~
0.
Then
the polynomial 'Pn(x)
has exactly n distinct real roots
in
the
open
interval
(a,
b).
Proof Let x
1
,
x
2
,
•••
, xm be all
of
the zeros
of
'Pn(x) for which
1.
a<
X;<
b
2. 'Pn(x) changes sign
at
X;
Since degree('Pn) = n, we trivially have m
~
n. We assume m < n
and
then
derive a contradiction.
Define
By the definition
of
the points x
1
,
•••
, xm, the polynomial
does
not
change sign in
(a,
b).
To
see this more clearly, the assumptions
214
APPROXIMATION
OF
FUNCTIONS
On
Xp
...
,
Xm
imply
with each
r;
odd and with
h(x)
not changing sign in (a, b). Then
and the conclusion follows. Consequently,
jbw(x)B(x)cpn(x)
dx * 0
a
since clearly B(x)cpn(x)
¥=
0. But since
degree(B)
= m < n, the corollary
to Theorem 4.3 implies
t
w(x
)B(x
)cpn(x) dx =
(B,
cpJ = 0
a
This
is
a contradiction, and thus we must have m = n. But then the
conclusion of the theorem will follow, since
cpn(x)
can have at most n
roots,
and
the assumptions
on
x
1
,
•••
,
xn
imply that they must all be
simple,
that
is, cp'(x;) *
0.
1111
As previously, let {
cpn(x)ln
~
0}
be an orthogonal family
on
(a,
b)
with
weight function
w(x)
~
0.
Define
An
and
Bn
by
(4.4.18)
Also, write
(4.4.19)
Let
(4.4.20)
Theorem 4.5 (Triple Recursion Relation) Let {
cpn}
be
an
orthogonal family of
polynomials on
(a,
b) with weight function
w(x)
~
0. Then for
n
~
1,
(4.4.21)
with
b=a·[Bn+l_Bnl
n n
An+l
An
Yn-1
(4.4.22)
Proof First
note
that the triple recursion relation (4.4.13) for Chebyshev
polynomials
is
an example
of
(4.4.21). To derive (4.4.21), we begin by
ORTHOGONAL POLYNOMIALS
215
considering the polynomial
A
n+l
[A
n B
n-1
]
---x
X + X +
···
A n n
n
[
An+
IBn
l
= B - xn + · · ·
n+l
A
n
and degree(G).:::;;
n.
By
Theorem 4.3, we can write
for an appropriate set
of
constants d
0
,
•••
,
dn.
Calculating
d;,
(4.4.23)
We
have (
'Pn+
1
,
'P;)
= 0 for i
.:::;;
n, and
(x'Pn•
q:>;)
= Jbw(x)cpn(x
)x'P;(x)
dx = 0
a
for
i.:::;;
n -
2,
since then
degree(xq:>;(.x)).:::;;
n -
1.
Combining these
results,
Osisn-2
and therefore
G
(X)
= d
n'Pn
(X)
+ d n _ 1
'Pn
_ 1
(X)
'Pn+l(x)
=
(anx
+ dn)'Pn(x) +
dn-l'Pn-l(x)
(4.4.24)
This shows the existence of a triple recursion relation, and the remaining
work
is
manipulation
of
the formulas to
obtain
d n and
d,
_
1
,
given as b,
and
en
in (4.4.22). These constants are
not
derived here,
but
their values
are important for some applications (see Problem 18). •
Example
1.
For
Laguerre polynomials,
1 n
Ln+I(x)
=
--
1
[2n +
1-
x]L,(x)-
--L,_
1
(x)
(4.4.25)
n + n + 1
2.
For
Legendre polynomials,
2n + 1 n
Pn+
1
(x)
=
xP,(x)-
--Pn_
1
(x)
n+l
n+1
(4.4.26)
216 APPROXIMATION OF FUNCTIONS
Theorem 4.6 (Christoffel-Darboux Identity)
For'
{
rpn}
an orthogonal family of
polynomials with weight function
w(x)
~
0,
t rpk(x)rpk(y) rpn+l(x)rpn(Y)- rpn{x)rpn+l(y)
k-0
Yk
anyn(x-
Y)
Xi=
y
( 4.4.27)
Proof
The
proof
is
based on manipulating the triple recursion relation [see
Szego
(1967,
p.
43)].
IIIII
4.5 The Least Squares Approximation Problem
(continued)
We
now
return
to the general least squares problem, of minimizing (4.3.10)
among all polynomials
of
degree::;
n. Assume
that
lcpk(x)ik
~
0}
is
an ortho-
normal family
of
polynomials with weight function
w(x)
~
0,
that
is,
n=m
ni=m
Then
an
arbitrary
polynomial
l(x)
of degree::; n can be written as
r(x)
= b
0
rp
0
(x)
+ · · · +bnrpn(x)
For
a given
IE
C[a,
b],
( 4.5.1)
Ill-
rlli =
[w(x)[l(x)-
t b
1
rp
1
(x)]
2
dx =
G(b
0
,
...
,
bn)
{4.5.2)
a
j-0
We
solve the least squares problem by minimizing
G.
As before, we could set
a a
-=0
ab;
i·=
0,1,
...
, n
But
to
obtain
a more complete result, we proceed in another way.
For
any choice
of
b
0
,
•••
,
bn,
0$;.
G(bo,
...
,
bn)
=
(1-
t
bjrpj,
I-
t
b;rp;)
1-o
;-o
n
=
u.
I)
- 2
I:
b
1
(!, rpJ +
I:
l:b;b
1
(
rp;.
rp
1
)
j-0
i j
n n
=
11111~-
2
I:
b/I.<JJ
1
)
+
I:
bf
j-0
j-0
n n
=
11111~-
I:
(!,
cpJ
2
+
I:
[ (f,.cpj)-
bj]
2
(4.5.3)
j-0
j-0
THE
LEAST SQUARES
APPROXIMATION
PROBLEM
CONTINUED
217
which can be checked
by
expanding the last term. Thus G
is
a minimum if and
only if
j=O,l,
...
,n
Then the least squares approximation exists,
is
unique, and is given by
n
rn*(x)
= L (/, cpJcpj(x)
j=O
Moreover, from (4.5.2) and (4.5.3),
II/-
r:u,
~
[u/ul-
t,
{!,
~Y
rl'
=
/IIJII~
-
llrn*ll~
11/11
~
=
llrn*ll
~
+
II/-
rn*ll
~
As-a practical note in obtaining
rn*+
1
(
x
),
use
Theorem
4.7
Assuming [a,
b]
is
finite,
Limit
II/-
rn*ll
2
= 0
n-oo
·
(4.5.4)
( 4.5 .5)
(4.5.6)
(4.5.7)
Proof
By
definition of
rn*
as
a minimizing polynomial for
II/-
rnll
2
,
we
have
(4.5.8)
Let
E > 0 be arbitrary. Then by the Weierstrass theorem, there is a
polynomial
Q(x) of some degree, say
m,
for which
E
Max
IJ(x)-
Q(x)
I~-
a:s;x:s;b
C,
By
the definition of r!(x),
[l
h
]1/2
II/-
r!lb
~II/-
Qlb
= a
w(x)[f(x)-
Q(x)]
2
dx
Combining this with (4.5.8),
111-
1-:112
~
f
for all n
;;:::
m. Since E
was
arbitrary, this proves (4.5.7).
•