Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Finite Fourier Analysis"
 
Line 25: Line 25:
  
  
−
In ordinary Fourier analysis, we may for example take a function in <math>S</math> and write it as an infinite linear combination of the functions <math>F_n.</math>  In finite Fourier analysis, we may take a vector in <math>\mathbb{C}^N</math> and write it as a linear combination of the functions <math>f_n</math>.
+
In ordinary Fourier analysis, we may for example take a function in <math>S</math> and write it as an infinite linear combination of the functions <math>F_n.</math>  In finite Fourier analysis, we may take a vector in <math>\mathbb{C}^N</math> and write it as a linear combination of the vectors <math>f_n</math>.

Latest revision as of 18:15, 9 September 2006

Motivation

(This is what I currently think of as motivation for finite Fourier analysis. If anyone can improve on this, please do.)


Consider the set $S$ of functions $f:[0,1] \to \mathbb{C}$ such that $f$ is infinitely differentiable (using limits from the right or from the left at the endpoints) and such that $f(0) = f(1)$ and $\frac{d^m f}{dx^m}(0) = \frac{d^m f}{dx^m}(1)$ for all $m \in \mathbb{Z}^+$ . $S$ is a vector space under the ordinary operations of function addition and scalar multiplication.


Consider the one-dimensional Laplace operator, $\frac{d^2}{dx^2}: S \to S$. Integration by parts shows that this operator is self-adjoint. Therefore, from our experience with the spectral theorem from finite-dimensional linear algebra, we might hope that the eigenfunctions of the Laplace operator in some sense form a basis for $S$.


What are the eigenfunctions (and eigenvalues) of the Laplace operator $\frac{d^2}{dx^2}:S \to S$ ? We need to find all the functions $f$ in $S$ such that $\frac{d^2f}{dx^2} = \lambda f$ for some constant $\lambda$. Using basic ODE stuff, and using the boundary conditions, it can be shown that the eigenfunctions are $F_n(x) = e^{i 2 n \pi x}$, where $n \in \mathbb{Z}$. The corresponding eigenvalues are $\Lambda_n = -(2 n \pi)^2$. In Fourier analysis, it can be proved that these eigenfunctions do in some sense form a basis of $S$.


Let $N \in \mathbb{Z}^+$. Every function $G$ in $S$ can be associated with a column vector $g$ in $\mathbb{C}^N$ by sampling $G$ at the $N$ points $x=0$, $x=\frac1N$, $x=\frac2N$, $\ldots$, $x=\frac{N-1}N$. For each $n \in \mathbb{Z}$, let $f_n$ be the column vector in $\mathbb{C}^N$ obtained by sampling the eigenfunction $F_n$ at these $N$ points.


It may seem that there are infinitely many vectors $f_n$ here, one for each $n \in \mathbb{Z}$. However, there is some redundancy. The vectors $f_n$ where $n=0$, $\ldots$, $N-1$ are indeed distinct, but for example $f_N=f_0$, $f_{N+1}=f_1$, and so on. So we really only have $N$ distinct vectors here, corresponding to $n=0$, $\ldots$ , $n=N-1$.


These vectors $f_n$ have some properties that are, in a very nice and very cool way, analogous to certain properties of the eigenfunctions $F_n$.


Just as the $F_n$ are eigenfunctions of the Laplace operator, the vectors $f_n$ are eigenvectors of something called the "discrete Laplace operator", which is a self-adjoint operator, and which arises by approximating $G''$ with something called a "second-order centered difference" from numerical analysis. The eigenvalue $\lambda_n$ corresponding to $f_n$ is $-4 N^2 \sin^2(\frac{n \pi}N )$ , which is approximately equal to $\Lambda_n$ when $N$ is much larger than $n$. By directly taking dot products and using the formula for the sum of a finite geometric series, you can prove that the set of eigenvectors {${f_n : n=0,\ldots, N-1}$} is orthogonal, and that the norm of $f_n$ is $\sqrt{N}$. We can normalize $f_n$ by dividing it by $\sqrt{N}$ and so obtain an orthonormal basis of eigenvectors of the discrete Laplace operator for $\mathbb{C}^N$.


In ordinary Fourier analysis, we may for example take a function in $S$ and write it as an infinite linear combination of the functions $F_n.$ In finite Fourier analysis, we may take a vector in $\mathbb{C}^N$ and write it as a linear combination of the vectors $f_n$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Finite_Fourier_Analysis&oldid=10079"