92 Chapter 2.Solution of Linear Algebraic Equations The routine for (2.8.2)which follows is due to G.B.Rybicki. #include "nrutil.h" void vander(double x[],double w[],double g[],int n) Solves the Vandermonde linear system(1..N).Input consists of the vectors x[1..n]and q[1..n];the vector w[1..n]is output. f int i,j,k; double b,s,t,xx; double米c; c=dvector(1,n); if(n=1)[1]=g[1] 83 else 鱼 granted for 19881992 for(i=1;i<=n;i++)c[i]=0.0: Initialize array. c[n]=-x[1]; Coefficients of the master polynomial are found 1800 for(1=2;i<n;i++)( by recursion. xx=-x[1]; for(j=(n+1-1);j<=(n-1);j++)c[j]+=xx*c[j+1]: to any Cambridge c[n]+xx; from NUMERICAL RECIPES IN 2 for(i=1;i<=n;i++){ Each subfactor in turn (North to make Xx=x[1]; t=b=1.0; America 州bMe se one paper UnN电.t THE s=q[n]; for(k=n;k>=2;k--)[ is synthetically divided, ART b=c[k]+xx*b; s+=qk-1]*b; matrix-multiplied by the right-hand side, t=xx*t+b; st st Programs [1]=s/t; and supplied with a denominator 2 free_dvector(c,1,n); to dir 18881920 OF SCIENTIFIC COMPUTING(ISBN Toeplitz Matrices v@cam 12-521 An N x N Toeplitz matrix is specified by giving 2N-1 numbers R&,k =-N+ 1,...,-1,0,1,...,N-1.Those numbers are then emplaced as matrix elements constant Numerical Recipes 43108 along the (upper-left to lower-right)diagonals of the matrix: Ro R-1 R-2 R-(N-2) R-N-1) (outside Ro R-1 R-(N-3) R-(N-2) R2 Ro R-(N-4) R-(N-3) (2.8.8) North Software. RN-2 N-3 RN-4 Ro R-1 Ame .RN-1 RN-2 RN-3 Ri Ro The linear Toeplitz problem can thus be written as Ri-jxj =Vi (i=1,,N) (2.8.9) j=】 where the j's,j=1,...,N,are the unknowns to be solved for. The Toeplitz matrix is symmetric if Rk=R-k for all k.Levinson [4]developed an algorithm for fast solution of the symmetric Toeplitz problem,by a bordering method,that is,92 Chapter 2. Solution of Linear Algebraic Equations 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 routine for (2.8.2) which follows is due to G.B. Rybicki. #include "nrutil.h" void vander(double x[], double w[], double q[], int n) Solves the Vandermonde linear system N i=1 xk−1 i wi = qk (k = 1,...,N). Input consists of the vectors x[1..n] and q[1..n]; the vector w[1..n] is output. { int i,j,k; double b,s,t,xx; double *c; c=dvector(1,n); if (n == 1) w[1]=q[1]; else { for (i=1;i<=n;i++) c[i]=0.0; Initialize array. c[n] = -x[1]; Coefficients of the master polynomial are found for (i=2;i<=n;i++) { by recursion. xx = -x[i]; for (j=(n+1-i);j<=(n-1);j++) c[j] += xx*c[j+1]; c[n] += xx; } for (i=1;i<=n;i++) { Each subfactor in turn xx=x[i]; t=b=1.0; s=q[n]; for (k=n;k>=2;k--) { is synthetically divided, b=c[k]+xx*b; s += q[k-1]*b; matrix-multiplied by the right-hand side, t=xx*t+b; } w[i]=s/t; and supplied with a denominator. } } free_dvector(c,1,n); } Toeplitz Matrices An N × N Toeplitz matrix is specified by giving 2N − 1 numbers Rk, k = −N + 1,..., −1, 0, 1,...,N − 1. Those numbers are then emplaced as matrix elements constant along the (upper-left to lower-right) diagonals of the matrix:       R0 R−1 R−2 ··· R−(N−2) R−(N−1) R1 R0 R−1 ··· R−(N−3) R−(N−2) R2 R1 R0 ··· R−(N−4) R−(N−3) ··· ··· RN−2 RN−3 RN−4 ··· R0 R−1 RN−1 RN−2 RN−3 ··· R1 R0       (2.8.8) The linear Toeplitz problem can thus be written as N j=1 Ri−jxj = yi (i = 1,...,N) (2.8.9) where the xj ’s, j = 1,...,N, are the unknowns to be solved for. The Toeplitz matrix is symmetric if Rk = R−k for all k. Levinson [4] developed an algorithm for fast solution of the symmetric Toeplitz problem, by a bordering method, that is