Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 44
Текст из файла (страница 44)
This workshould consist in choosing the φi (x) carefully.A seemingly simple way to avoid the condition problem is to choosethe φi (x) to be orthogonal on the points x1, . . . , xN, that is, so thatwhenever ij(6.24)For if (6.24) holds, Eqs. (6.23) reduce toi = 1 ,...,k(6.25)whose solution offers, offhand, no further difficulty.Of course, this nice way out of the condition problem merely replacesone problem by another, for now we have to get hold of orthogonalfunctions. If we also want the φi ‘s to be polynomials, it is possible toconstruct such orthogonal polynomial functions quite efficiently using athree-term recurrence relation valid for sequences of orthogonal polynomials.
This we discuss in Secs. 6.3 and 6.4. If, as is often the case in practice,f(x) cannot be assumed to be of polynomial form, other means forconstructing appropriate orthogonal functions have to be used. One suchtechnique, the modified Gram-Schmidt algorithm, is discussed in sometexts (see, for example, Rice [17]).
Alternatively, one has to be satisfiedwith choosing φ1 (x), . . . , φk(x) to be “nearly” orthogonal. This vagueterm is meant to describe the fact that the coefficient matrix of (6.23) forsuch φi (x) is “nearly” diagonal, e.g., diagonally dominant. If the points*6.3ORTHOGONAL POLYNOMIALS251x1, . . .
, xN are distributed nearly uniformly in some interval (a,b), thenφ1 (x), . . . , φk(x) tend to be “nearly” orthogonal if each φ i (x) changes signin (a,b) one more time than does φi-1(x) (see Exercise 6.2-3).EXERCISES6.2-l Calculate the least-squares approximation to the data plotted in Fig. 6.5 by functions ofthe formF(x) = c l + c 2 x + c 3 sin[123(x - 1)]by solving the appropriate normal equations. Do you feel that this approximation representsall the information about f(x) contained in the data? Why?6.2-2 Derive the normal equations for the best c1*, c2*, in caseF(x) = F(x; cl, c2 ) = c1eC2xfollowing the argument given in the text.
Are these normal equations still linear?6.2-3 Repeat all the calculations in Example 6.5 using the functionsφ 1(x) = 1φ2(x) = x - 10.5φ 3(x) = (x - 10.3)(x - 10.7)According to the last paragraph of this section, the normal equations should now be muchbetter conditioned. Are they?*6.3 ORTHOGONAL POLYNOMIALSIn this section, we discuss briefly some pertinent properties and specificexamples of sequences of orthogonal polynomials. Although our immediate motivation for this discussion comes from the problem of leastsquares approximation by polynomials (to be discussed in the next section), we have use for orthogonal polynomials in different contexts lateron, e.g., in Sec.
7.3. In preparation for that section, we use now a notion oforthogonality of functions which is somewhat more general than the oneintroduced in Sec. 6.2.In what is to follow, let (a,b) be a given interval and let w(x) be agiven function defined (at least) on (a,b) and positive there. Further, wedefine the scalar productof any two functions g(x) and h(x) [defined on (a,b)] in one of two ways:(6.26)or(6.27)In the first case, we assume that the integral exists (at least as an improperintegral) for all functions g(x) and h(x) of interest; in the second case, we252APPROXIMATIONassume that we have given N points x1, .
. . , xN all in the interval (a,b)which are considered fixed during the discussion. Note that, with w(x) =1, (6.27) reduces to the scalar product g T h = hT g of two functions whichappears in the discussion of least-squares approximation in Sec. 6.2.With the scalar product of two functions defined, we say that the twofunctions g(x) and h(x) are orthogonal (to each other) in case< g, h> = 0It is easy to verify, for example, that the functions g(x) = 1, h(x) = x areorthogonal if the scalar product isThey are also orthogonal if the scalar product isor if the scalar product isThe functions g(x) = sin nx, h(x) = sin mx are orthogonal, for n and mintegers, ifand nm, as are the functions g(x) = sin nx, h(x) = cos mx.Further, we say that P0 (x), P1 (x), P2 (x), . .
. is a (finite or infinite)sequence of orthogonal polynomials provided the Pi (x) are all orthogonal toeach other and each Pi (x) is a polynomial of exact degree i. In otherwords,(i) For each i, Pi (x) = αi xi + a polynomial of degree < i, with α i(ii) Whenever i j, then <Pi , Pj> = 0The functionsP0 (x) = 1P 1 (x) = xP2 (x) = 3x2 - 1for instance, form a sequence of three orthogonal polynomials ifWe mentioned earlier that <P0, P1 > = 0.
Also0*6.3ORTHOGONAL POLYNOMIALS253whileLet P0(x), P1(x), . . . , Pk(x) be a finite sequence of orthogonal polynomials. Then the following facts can be proved:Property 1 If p(x) is any polynomial of degree < k, then p(x) can bewritten(6.28)p(x) = d0 P0 (x) + d1 P1 (x) + . . . + dkPk(x)with the coefficients d0, . . . , dk uniquely determined by p(x). Specificallyifp(x) = akxk + a polynomial of degree < kand if the leading coefficient of Pk(x) is α k, thenThis property follows from (i), above, by induction on k. For theexample above, we can write the general polynomial of degree < 2,p2(x) = a0 + a1x + a2x2asBy combining Property 1 with (ii), one gets Property 2.Property 2 If p(x) is a polynomial of degree < k, then p(x) is orthogonal to Pk(x), that is,<p, Pk> = 0If in the example above we take p(x) = 1 + x, we find thatThis rather innocuous property has several important consequences.Property 3 If the scalar product is given by (6.26), then Pk(x) has ksimple real zeros, all of which lie in the interval (a,b); that is, Pk(x) is ofthe form(6.29)for certain k distinct points ξ1,k, .
. . , ξk,kFor our example,in (a,b).A simple proof of Property 3 goes as follows: Let k > 0 and letξ l,k, . . . ξr,k be all the points in the interval (a,b) at which Pk(x) changes254APPROXIMATIONsign. We claim that thenr > kFor if r were less than k, then, withwould be a polynomial of degree < k which, at every point in (a,b), hasthe same sign as Pk(x). Hence, on the one hand, by Property 3,while on the other hand,for all x(a,b) except x = ξ1,k . . .
, ξr , kand these two facts certainly contradict each other. Consequently, we musthave r > k: that is, Pk(x) must change sign in (a,b) at least k times. Butsince Pk(x) is a polynomial of degree k and each ξi,k is a zero of Pk(x), rcannot be bigger than k (see Sec. 2.1); therefore r must equal k, that is, thek distinct points ξi,k, i = 1, . .
. , k, are exactly the zeros of Pk(x).One proves similarly that (6.29) holds when the scalar product is givenby (6.27), provided there are at least k distinct points among the xn ’s.Property 4 The orthogonal polynomials satisfy a three-term recurrencerelation. If we setp(x)p k (x)w(x) > 0all iP- 1 (x) = 0and ifSi = <Pi , Pi >is not zero for i = 0, . . . , k - 1, then this recurrence relation can bewrittenP i + 1 (x) = A i (x - Bi) Pi (x)-Ci Pi-1(x)i = 0, l, . . . ,k - 1(6.30)whereandThis property can be used to generate sequences of orthogonal polynomials (provided the numbers Si and Bi can be calculated and the Si arenot zero). In such a process, one usually chooses the leading coefficients αi ,or equivalently, the numbers Ai , so that the resulting sequence is particularly simple in some sense.*6.3ORTHOGONAL POLYNOMIALS255Table 6.2Example 6.6: Legendre polynomials If the scalar product is given bythen the resulting orthogonal polynomials are associated with Legendre’s name.
StartingwithP0(x) = 1one getsHence, from Property 4, with the choice Ai = 1, all i, we getP1 (x) = xFurther,so, again by Property 4,P2(x) = x2 - 1/3againsoIt is customary to normalize the Legendre polynomials so thatP k (l) = 1all kWith this normalization, the coefficients in the recurrence relation becomeso thatTable 6.2 gives the first few Legendre polynomials.Example 6.7: Chebyshev polynomial If the scalar product is given bythen one gets the Chebyshev polynomials Tk (x) introduced in Sec.
6.1. We already256APPROXIMATIONderived there their recurrence relationT k + 1 ( x ) = 2xTk(x)-Tk-1(x)k = 1, 2,. . .from their defining relationT k( cos θ) = cos kθExample 6.8: Hermite polynomials Hk(x) result when the scalar productis used. With the customary normalization, these polynomials satisfy the recurrencerelationHk+1(x) = 2xHk(x)-2kH k - 1 (x)k = 0, 1, 2, . . .The first few Hermite polynomials are given in Table 6.3.Table 6.3Example 6.9 Generalized Laguerre polynomialsproductare associated with the scalarThe coefficients for the recurrence relation areWe leave the generation of the first five Laguerre polynomials (with α = 0) to thestudent (see Exercise 6.3-l).The last two examples are of particular importance in the numericalquadrature over semi-infinite or infinite intervals (see Sec.
7.3).We conclude this section with the discussion of an algorithm for theevaluation of a polynomial given in terms of orthogonal polynomials.Suppose that P0(x), P1(x), . . . , Pk(x) is a finite sequence of orthogonalpolynomials, and suppose that we have given a polynomial p(x) of degree< k in terms of the Pi (x), that is, we know the coefficients d0, . . . , dk sothat(6.3 1)p(x) = d 0 P0 (x) + d 1 P1 (x) + · · · + d k Pk (x)In evaluating p(x) at a particular pointwe can make use of the*6.3ORTHOGONAL POLYNOMIALS257three-term recurrence relation (6.30) for the Pi (x) as follows: By (6.30),Thereforeor with the abbreviationswe have(6.32)Again by (6.30),and substituting this into (6.32), we getwhere we have used the abbreviationProceeding in this fashion, we calculate sequentiallygetting finally thatAlgorithm 6.1 Nested multiplication for orthogonal polynomials Giventhe coefficients Aj, Bj, Cj, j = 0, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
