2.8 Vandermonde Matrices and Toeplitz Matrices 91 The alternative identification of rows and columns leads to the set of equations 1 1 1 W1 工2 2 名 N W3 3 (2.8.2) 21 4。 IN-I N Write this out and you will see that it relates to the problem of moments:Given the values of N points ri,find the unknown weights wi,assigned so as to match the given values gi of the first N moments.(For more on this problem,consult [3).)The routine given in this section solves (2.8.2). EOEE 8 The method of solution of both (2.8.1)and (2.8.2)is closely related to Lagrange's polynomial interpolation formula,which we will not formally meet until $3.I below.Notwith- standing,the following derivation should be comprehensible: Let Pi()be the polynomial of degree N-1 defined by N ICAL P(x)= E一tn Ij -In =∑Ax-1 (2.8.3) k三1 RECIPES Here the meaning of the last equality is to define the components of the matrix As as the coefficients that arise when the product is multiplied out and like terms collected. The polynomial Pi()is a function of generally.But you will notice that it is specifically designed so that it takes on a value of zero at all i with ij,and has a value of unity at x =j.In other words, Press. Programs B(e)==∑Ax-1 (2.8.4) k=1 But(2.8.4)says that A is exactly the inverse of the matrix of components,which appears in (2.8.2),with the subscript as the column index.Therefore the solution of(2.8.2) IENTIFIC is just that matrix inverse times the right-hand side, N =∑A9 (2.8.5) k As for the transpose problem(2.8.1),we can use the fact that the inverse of the transpose is the transpose of the inverse,so Numer (2.8.6) The routine in 83.5 implements this. It remains to find a good way of multiplying out the monomial terms in (2.8.3),in order to get the components of Ajk.This is essentially a bookkeeping problem,and we will let you read the routine itself to see how it can be solved.One trick is to define a master P()by North Software. N P(x)≡ (-2n) (2.8.7) work out its coefficients,and then obtain the numerators and denominators of the specific P,'s viasynthetic division by the one supernumerary term.(See 5.3 for more on synthetic division.) Since each such division is only a process of order N,the total procedure is of order N2 You should be warned that Vandermonde systems are notoriously ill-conditioned,by their very nature.(As an aside anticipating $5.8,the reason is the same as that which makes Chebyshev fitting so impressively accurate:there exist high-order polynomials that are very good uniform fits to zero.Hence roundoff error can introduce rather substantial coefficients of the leading terms of these polynomials.It is a good idea always to compute Vandermonde problems in double precision.2.8 Vandermonde Matrices and Toeplitz Matrices 91 Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). The alternative identification of rows and columns leads to the set of equations      1 1 ··· 1 x1 x2 ··· xN x2 1 x2 2 ··· x2 N ··· xN−1 1 xN−1 2 ··· xN−1 N      ·      w1 w2 w3 ··· wN      =      q1 q2 q3 ··· qN      (2.8.2) Write this out and you will see that it relates to the problem of moments: Given the values of N points xi, find the unknown weights wi, assigned so as to match the given values qj of the first N moments. (For more on this problem, consult [3].) The routine given in this section solves (2.8.2). The method of solution of both (2.8.1) and (2.8.2) is closely related to Lagrange’s polynomial interpolation formula, which we will not formally meet until §3.1 below. Notwith￾standing, the following derivation should be comprehensible: Let Pj (x) be the polynomial of degree N − 1 defined by Pj (x) = N n=1 (n
=j) x − xn xj − xn = N k=1 Ajkxk−1 (2.8.3) Here the meaning of the last equality is to define the components of the matrix Aij as the coefficients that arise when the product is multiplied out and like terms collected. The polynomial Pj (x) is a function of x generally. But you will notice that it is specifically designed so that it takes on a value of zero at all xi with i = j, and has a value of unity at x = xj . In other words, Pj (xi) = δij = N k=1 Ajkxk−1 i (2.8.4) But (2.8.4) says that Ajk is exactly the inverse of the matrix of components xk−1 i , which appears in (2.8.2), with the subscript as the column index. Therefore the solution of (2.8.2) is just that matrix inverse times the right-hand side, wj = N k=1 Ajkqk (2.8.5) As for the transpose problem (2.8.1), we can use the fact that the inverse of the transpose is the transpose of the inverse, so cj = N k=1 Akj yk (2.8.6) The routine in §3.5 implements this. It remains to find a good way of multiplying out the monomial terms in (2.8.3), in order to get the components of Ajk. This is essentially a bookkeeping problem, and we will let you read the routine itself to see how it can be solved. One trick is to define a master P(x) by P(x) ≡ N n=1 (x − xn) (2.8.7) work out its coefficients, and then obtain the numerators and denominators of the specific Pj ’s via synthetic division by the one supernumerary term. (See §5.3 for more on synthetic division.) Since each such division is only a process of order N, the total procedure is of order N2. You should be warned that Vandermonde systems are notoriously ill-conditioned, by their very nature. (As an aside anticipating §5.8, the reason is the same as that which makes Chebyshev fitting so impressively accurate: there exist high-order polynomials that are very good uniform fits to zero. Hence roundoff error can introduce rather substantial coefficients of the leading terms of these polynomials.) It is a good idea always to compute Vandermonde problems in double precision