金融にフーリェ変換の続き
補遺に二つの証明が書いてあります。
1. F^-1F(a)=a. Let b=F(a). We show that F^-1(b)=a.
Let F^-1(b)=a~. a~(lth el)=(1/sqrt(n))SIGMA(from k=0 to n-1)(b(kth el)*zn^(-kl)). Here zn = e^(2pi*i/n).
Substituting (1/sqrt(n))SIGMA(from j=0 to n-1)(a(jth el)*zn^(kj))for b(kth el) we get
a~(lth el)= (1/n)(SIGMA(k=0 to n-1)(zn^(-kl))*(SIGMA(from j=0 to n-1)(a(jth el)*zn^(kj))))
We can, without changing the result, move the zn^(-kl) term inside the inner sum and reverse the order of the SIGMAs. We can then move the a(jth el) term outside the k SIGMA. The k SIGMA now becomes:
SIGMA(from k=0 to n-1)(zn^(j-l)^k) When j!=l, the sum considers n uniformly spaced points on the unit circle. The text states (can be proven in simple cases that the sum in this case is 0. When j==l, the sum is n.
Thus all terms in the outer (j) summation will be 0, except for the term: (1/n)*a(lth el)*n=a(lth el)
Thus, a~(lth el) = a(lth el)= lth element of F^-1F(a)
QED
2. F(a conv b) = sqrt(n)F(a)F(b).
First write expression for c=(a conv b).
Then write expression for d = F(c).
Substitute above c expression into d's to get a double summation. Some factoring of the zn term can be done, and it can be moved into the inner sum. Then b(kth)zn^(kl) can be moved in front of k SIGMA. The inner sum does not depend on k (although it contains references to k in a and zn terms). This is because the (j-kth) a term is multiplied by the (j-kth) power of zn^l for k over 0 to n-1. This is the same as saying that the jth "a" term is multiplied by the jth power of zn^l. Substituting this into the dual summation and factoring sqrt(n) out of 1/(sqrt(n)) yields:
d(lth el) = sqrt(n)*1*SIGMA(from k=0 to n-1)(b(kth el)*zn^(kl))*2*SIGMA(from j=0 to n-1)(a(jth el)*zn^(jl)))
Based on the earlier definition of F(a), we know that the above is equivalent to
sqrt(n)F(a)F(b)
QED
