- 8.6.1: Determine the trigonometric interpolating polynomial S2(x) of degre...
- 8.6.2: Determine the trigonometric interpolating polynomial of degree 4 fo...
- 8.6.3: Use the Fast Fourier Transform Algorithm to compute the trigonometr...
- 8.6.4: a. Determine the trigonometric interpolating polynomial S4(x) of de...
- 8.6.5: Use the approximations obtained in Exercise 3 to approximate the fo...
- 8.6.6: Use the Fast Fourier Transform Algorithm to determine the trigonome...
- 8.6.7: Use the Fast Fourier Transform Algorithm to determine the trigonome...
- 8.6.8: Use a trigonometric identity to show that 2m1 j=0 (cos mxj)2 = 2m.
- 8.6.9: Show that c0, ... , c2m1 in Algorithm 8.3 are given by c0 c1 c2 . ....
- 8.6.10: In the discussion preceding Algorithm 8.3, an example for m = 4 was...
Solutions for Chapter 8.6: Fast Fourier Transforms
Full solutions for Numerical Analysis | 9th Edition
Adjacency matrix of a graph.
Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected). Adjacency matrix of a graph. Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected).
A matrix can be partitioned into matrix blocks, by cuts between rows and/or between columns. Block multiplication ofAB is allowed if the block shapes permit.
A = CTC = (L.J]))(L.J]))T for positive definite A.
Conjugate Gradient Method.
A sequence of steps (end of Chapter 9) to solve positive definite Ax = b by minimizing !x T Ax - x Tb over growing Krylov subspaces.
A(B + C) = AB + AC. Add then multiply, or mUltiply then add.
Echelon matrix U.
The first nonzero entry (the pivot) in each row comes in a later column than the pivot in the previous row. All zero rows come last.
Eigenvalue A and eigenvector x.
Ax = AX with x#-O so det(A - AI) = o.
A symmetric matrix with eigenvalues of both signs (+ and - ).
lA-II = l/lAI and IATI = IAI.
The big formula for det(A) has a sum of n! terms, the cofactor formula uses determinants of size n - 1, volume of box = I det( A) I.
Linear transformation T.
Each vector V in the input space transforms to T (v) in the output space, and linearity requires T(cv + dw) = c T(v) + d T(w). Examples: Matrix multiplication A v, differentiation and integration in function space.
Nilpotent matrix N.
Some power of N is the zero matrix, N k = o. The only eigenvalue is A = 0 (repeated n times). Examples: triangular matrices with zero diagonal.
Nullspace N (A)
= All solutions to Ax = O. Dimension n - r = (# columns) - rank.
Every v in V is orthogonal to every w in W.
Outer product uv T
= column times row = rank one matrix.
Ps = pascal(n) = the symmetric matrix with binomial entries (i1~;2). Ps = PL Pu all contain Pascal's triangle with det = 1 (see Pascal in the index).
The diagonal entry (first nonzero) at the time when a row is used in elimination.
Pseudoinverse A+ (Moore-Penrose inverse).
The n by m matrix that "inverts" A from column space back to row space, with N(A+) = N(AT). A+ A and AA+ are the projection matrices onto the row space and column space. Rank(A +) = rank(A).
Similar matrices A and B.
Every B = M-I AM has the same eigenvalues as A.
Symmetric matrix A.
The transpose is AT = A, and aU = a ji. A-I is also symmetric.
Unitary matrix UH = U T = U-I.
Orthonormal columns (complex analog of Q).