Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Spectral method
open-in-new
<h2 id="examples-of-spectral-methods">Examples of spectral methods</h2> <h3>A concrete, linear example</h3> <p>Here we presume an understanding of basic multivariate <a href="/facts/Calculus/MEmUTYoz">calculus</a> and <a href="/facts/Fourier_series/s3fsxPAT">Fourier series</a>. If g ( x , y ) {\displaystyle g(x,y)} is a known, complex-valued function of two real variables, and g is periodic in x and y (that is, g ( x , y ) = g ( x + 2 π , y ) = g ( x , y + 2 π ) {\displaystyle g(x,y)=g(x+2\pi ,y)=g(x,y+2\pi )} ) then we are interested in finding a function <i>f</i>(<i>x</i>,<i>y</i>) so that </p> ( ∂ 2 ∂ x 2 + ∂ 2 ∂ y 2 ) f ( x , y ) = g ( x , y ) for all x , y {\displaystyle \left({\frac {\partial ^{2}}{\partial x^{2}}}+{\frac {\partial ^{2}}{\partial y^{2}}}\right)f(x,y)=g(x,y)\quad {\text{for all }}x,y} <p>where the expression on the left denotes the second partial derivatives of <i>f</i> in <i>x</i> and <i>y</i>, respectively. This is the <a href="/facts/Poisson_equation/Pr8zkCXB">Poisson equation</a>, and can be physically interpreted as some sort of heat conduction problem, or a problem in potential theory, among other possibilities. </p><p>If we write <i>f</i> and <i>g</i> in Fourier series: </p> f =: ∑ a j , k e i ( j x + k y ) , g =: ∑ b j , k e i ( j x + k y ) , {\displaystyle {\begin{aligned}f&=:\sum a_{j,k}e^{i(jx+ky)},\\[5mu]g&=:\sum b_{j,k}e^{i(jx+ky)},\end{aligned}}} <p>and substitute into the differential equation, we obtain this equation: </p> ∑ − a j , k ( j 2 + k 2 ) e i ( j x + k y ) = ∑ b j , k e i ( j x + k y ) . {\displaystyle \sum -a_{j,k}(j^{2}+k^{2})e^{i(jx+ky)}=\sum b_{j,k}e^{i(jx+ky)}.} <p>We have exchanged partial differentiation with an infinite sum, which is legitimate if we assume for instance that <i>f</i> has a continuous second derivative. By the uniqueness theorem for Fourier expansions, we must then equate the Fourier coefficients term by term, giving </p> <table><tbody><tr><td> a j , k = − b j , k j 2 + k 2 {\displaystyle a_{j,k}=-{\frac {b_{j,k}}{j^{2}+k^{2}}}} </td> <td></td> <td>*</td></tr></tbody></table> <p>which is an explicit formula for the Fourier coefficients <i>a</i><i>j</i>,<i>k</i>. </p><p>With periodic boundary conditions, the <a href="/facts/Poisson_equation/Pr8zkCXB">Poisson equation</a> possesses a solution only if <i>b</i>0,0 = 0. Therefore, we can freely choose <i>a</i>0,0 which will be equal to the mean of the resolution. This corresponds to choosing the integration constant. </p><p>To turn this into an algorithm, only finitely many frequencies are solved for. This introduces an error which can be shown to be proportional to h n {\displaystyle h^{n}} , where h := 1 / n {\displaystyle h:=1/n} and n {\displaystyle n} is the highest frequency treated. </p> <h4>Algorithm</h4> <ol><li>Compute the Fourier transform (<i>bj,k</i>) of <i>g</i>.</li> <li>Compute the Fourier transform (<i>aj,k</i>) of <i>f</i> via the formula (*).</li> <li>Compute <i>f</i> by taking an inverse Fourier transform of (<i>aj,k</i>).</li></ol> <p>Since we're only interested in a finite window of frequencies (of size <i>n</i>, say) this can be done using a <a href="/facts/Fast_Fourier_transform/caT7UUCh">fast Fourier transform</a> algorithm. Therefore, globally the algorithm runs in time <i>O</i>(<i>n</i> log <i>n</i>). </p> <h3>Nonlinear example</h3> <p>We wish to solve the forced, transient, nonlinear <a href="/facts/Burgers%2527_equation/oslyMzES">Burgers' equation</a> using a spectral approach. </p><p>Given u ( x , 0 ) {\displaystyle u(x,0)} on the periodic domain x ∈ [ 0 , 2 π ) {\displaystyle x\in \left[0,2\pi \right)} , find u ∈ U {\displaystyle u\in {\mathcal {U}}} such that </p> ∂ t u + u ∂ x u = ρ ∂ x x u + f ∀ x ∈ [ 0 , 2 π ) , ∀ t > 0 {\displaystyle \partial _{t}u+u\partial _{x}u=\rho \partial _{xx}u+f\quad \forall x\in \left[0,2\pi \right),\forall t>0} <p>where ρ is the <a href="/facts/Viscosity/QLVfrdCz">viscosity</a> coefficient. In weak conservative form this becomes </p> ⟨ ∂ t u , v ⟩ = ⟨ ∂ x ( − 1 2 u 2 + ρ ∂ x u ) , v ⟩ + ⟨ f , v ⟩ ∀ v ∈ V , ∀ t > 0 {\displaystyle \left\langle \partial _{t}u,v\right\rangle ={\Bigl \langle }\partial _{x}\left(-{\tfrac {1}{2}}u^{2}+\rho \partial _{x}u\right),v{\Bigr \rangle }+\left\langle f,v\right\rangle \quad \forall v\in {\mathcal {V}},\forall t>0} <p>where following <a href="/facts/Inner_product_space/HoyjElEy">inner product</a> notation. <a href="/facts/Integration_by_parts/aV6JgBNd">Integrating by parts</a> and using periodicity grants </p> ⟨ ∂ t u , v ⟩ = ⟨ 1 2 u 2 − ρ ∂ x u , ∂ x v ⟩ + ⟨ f , v ⟩ ∀ v ∈ V , ∀ t > 0. {\displaystyle \langle \partial _{t}u,v\rangle =\left\langle {\tfrac {1}{2}}u^{2}-\rho \partial _{x}u,\partial _{x}v\right\rangle +\left\langle f,v\right\rangle \quad \forall v\in {\mathcal {V}},\forall t>0.} <p>To apply the Fourier–<a href="/facts/Galerkin_method/oYm8Iylo">Galerkin method</a>, choose both </p> U N := { u : u ( x , t ) = ∑ k = − N / 2 N / 2 − 1 u ^ k ( t ) e i k x } {\displaystyle {\mathcal {U}}^{N}:={\biggl \{}u:u(x,t)=\sum _{k=-N/2}^{N/2-1}{\hat {u}}_{k}(t)e^{ikx}{\biggr \}}} <p>and </p> V N := span { e i k x : k ∈ − 1 2 N , … , 1 2 N − 1 } {\displaystyle {\mathcal {V}}^{N}:=\operatorname {span} \left\{e^{ikx}:k\in -{\tfrac {1}{2}}N,\dots ,{\tfrac {1}{2}}N-1\right\}} <p>where u ^ k ( t ) := 1 2 π ⟨ u ( x , t ) , e i k x ⟩ {\displaystyle {\hat {u}}_{k}(t):={\frac {1}{2\pi }}\langle u(x,t),e^{ikx}\rangle } . This reduces the problem to finding u ∈ U N {\displaystyle u\in {\mathcal {U}}^{N}} such that </p> ⟨ ∂ t u , e i k x ⟩ = ⟨ 1 2 u 2 − ρ ∂ x u , ∂ x e i k x ⟩ + ⟨ f , e i k x ⟩ ∀ k ∈ { − 1 2 N , … , 1 2 N − 1 } , ∀ t > 0. {\displaystyle \langle \partial _{t}u,e^{ikx}\rangle =\left\langle {\tfrac {1}{2}}u^{2}-\rho \partial _{x}u,\partial _{x}e^{ikx}\right\rangle +\left\langle f,e^{ikx}\right\rangle \quad \forall k\in \left\{-{\tfrac {1}{2}}N,\dots ,{\tfrac {1}{2}}N-1\right\},\forall t>0.} <p>Using the <a href="/facts/Orthogonality/JVIjYPog">orthogonality</a> relation ⟨ e i l x , e i k x ⟩ = 2 π δ l k {\displaystyle \langle e^{ilx},e^{ikx}\rangle =2\pi \delta _{lk}} where δ l k {\displaystyle \delta _{lk}} is the <a href="/facts/Kronecker_delta/gcGAy0bm">Kronecker delta</a>, we simplify the above three terms for each k {\displaystyle k} to see </p> ⟨ ∂ t u , e i k x ⟩ = ⟨ ∂ t ∑ l u ^ l e i l x , e i k x ⟩ = ⟨ ∑ l ∂ t u ^ l e i l x , e i k x ⟩ = 2 π ∂ t u ^ k , ⟨ f , e i k x ⟩ = ⟨ ∑ l f ^ l e i l x , e i k x ⟩ = 2 π f ^ k , and ⟨ 1 2 u 2 − ρ ∂ x u , ∂ x e i k x ⟩ = ⟨ 1 2 ( ∑ p u ^ p e i p x ) ( ∑ q u ^ q e i q x ) − ρ ∂ x ∑ l u ^ l e i l x , ∂ x e i k x ⟩ = ⟨ 1 2 ∑ p ∑ q u ^ p u ^ q e i ( p + q ) x , i k e i k x ⟩ − ⟨ ρ i ∑ l l u ^ l e i l x , i k e i k x ⟩ = − 1 2 i k ⟨ ∑ p ∑ q u ^ p u ^ q e i ( p + q ) x , e i k x ⟩ − ρ k ⟨ ∑ l l u ^ l e i l x , e i k x ⟩ = − i π k ∑ p + q = k u ^ p u ^ q − 2 π ρ k 2 u ^ k . {\displaystyle {\begin{aligned}\left\langle \partial _{t}u,e^{ikx}\right\rangle &={\biggl \langle }\partial _{t}\sum _{l}{\hat {u}}_{l}e^{ilx},e^{ikx}{\biggr \rangle }={\biggl \langle }\sum _{l}\partial _{t}{\hat {u}}_{l}e^{ilx},e^{ikx}{\biggr \rangle }=2\pi \partial _{t}{\hat {u}}_{k},\\\left\langle f,e^{ikx}\right\rangle &={\biggl \langle }\sum _{l}{\hat {f}}_{l}e^{ilx},e^{ikx}{\biggr \rangle }=2\pi {\hat {f}}_{k},{\text{ and}}\\\left\langle {\tfrac {1}{2}}u^{2}-\rho \partial _{x}u,\partial _{x}e^{ikx}\right\rangle &={\biggl \langle }{\tfrac {1}{2}}{\Bigl (}\sum _{p}{\hat {u}}_{p}e^{ipx}{\Bigr )}{\Bigl (}\sum _{q}{\hat {u}}_{q}e^{iqx}{\Bigr )}-\rho \partial _{x}\sum _{l}{\hat {u}}_{l}e^{ilx},\partial _{x}e^{ikx}{\biggr \rangle }\\&={\biggl \langle }{\tfrac {1}{2}}\sum _{p}\sum _{q}{\hat {u}}_{p}{\hat {u}}_{q}e^{i\left(p+q\right)x},ike^{ikx}{\biggr \rangle }-{\biggl \langle }\rho i\sum _{l}l{\hat {u}}_{l}e^{ilx},ike^{ikx}{\biggr \rangle }\\&=-{\tfrac {1}{2}}ik{\biggl \langle }\sum _{p}\sum _{q}{\hat {u}}_{p}{\hat {u}}_{q}e^{i\left(p+q\right)x},e^{ikx}{\biggr \rangle }-\rho k{\biggl \langle }\sum _{l}l{\hat {u}}_{l}e^{ilx},e^{ikx}{\biggr \rangle }\\&=-i\pi k\sum _{p+q=k}{\hat {u}}_{p}{\hat {u}}_{q}-2\pi \rho {}k^{2}{\hat {u}}_{k}.\end{aligned}}} <p>Assemble the three terms for each k {\displaystyle k} to obtain </p> 2 π ∂ t u ^ k = − i π k ∑ p + q = k u ^ p u ^ q − 2 π ρ k 2 u ^ k + 2 π f ^ k k ∈ { − 1 2 N , … , 1 2 N − 1 } , ∀ t > 0. {\displaystyle 2\pi \partial _{t}{\hat {u}}_{k}=-i\pi k\sum _{p+q=k}{\hat {u}}_{p}{\hat {u}}_{q}-2\pi \rho {}k^{2}{\hat {u}}_{k}+2\pi {\hat {f}}_{k}\quad k\in \left\{-{\tfrac {1}{2}}N,\dots ,{\tfrac {1}{2}}N-1\right\},\forall t>0.} <p>Dividing through by 2 π {\displaystyle 2\pi } , we finally arrive at </p> ∂ t u ^ k = − i k 2 ∑ p + q = k u ^ p u ^ q − ρ k 2 u ^ k + f ^ k k ∈ { − 1 2 N , … , 1 2 N − 1 } , ∀ t > 0. {\displaystyle \partial _{t}{\hat {u}}_{k}=-{\frac {ik}{2}}\sum _{p+q=k}{\hat {u}}_{p}{\hat {u}}_{q}-\rho {}k^{2}{\hat {u}}_{k}+{\hat {f}}_{k}\quad k\in \left\{-{\tfrac {1}{2}}N,\dots ,{\tfrac {1}{2}}N-1\right\},\forall t>0.} <p>With Fourier transformed initial conditions u ^ k ( 0 ) {\displaystyle {\hat {u}}_{k}(0)} and forcing f ^ k ( t ) {\displaystyle {\hat {f}}_{k}(t)} , this coupled system of ordinary differential equations may be integrated in time (using, e.g., a <a href="/facts/Runge_Kutta/YRjbyHpY">Runge Kutta</a> technique) to find a solution. The nonlinear term is a <a href="/facts/Convolution/PVPrdz9J">convolution</a>, and there are several transform-based techniques for evaluating it efficiently. See the references by Boyd and Canuto et al. for more details. </p> <h2 id="a-relationship-with-the-spectral-element-method">A relationship with the spectral element method</h2> <p>One can show that if g {\displaystyle g} is infinitely differentiable, then the numerical algorithm using Fast Fourier Transforms will converge faster than any polynomial in the grid size h. That is, for any n>0, there is a C n < ∞ {\displaystyle C_{n}<\infty } such that the error is less than C n h n {\displaystyle C_{n}h^{n}} for all sufficiently small values of h {\displaystyle h} . We say that the spectral method is of order n {\displaystyle n} , for every n>0. </p><p>Because a <a href="/facts/Spectral_element_method/bToPLcIc">spectral element method</a> is a <a href="/facts/Finite_element_method/eUcfP1vn">finite element method</a> of very high order, there is a similarity in the convergence properties. However, whereas the spectral method is based on the eigendecomposition of the particular boundary value problem, the finite element method does not use that information and works for arbitrary <a href="/facts/Elliptic_boundary_value_problem/oxW9cVDd">elliptic boundary value problems</a>. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Finite_element_method/eUcfP1vn">Finite element method</a></li> <li><a href="/facts/Gaussian_grid/A3sPPl2d">Gaussian grid</a></li> <li><a href="/facts/Pseudo-spectral_method/62NCscTm">Pseudo-spectral method</a></li> <li><a href="/facts/Spectral_element_method/bToPLcIc">Spectral element method</a></li> <li><a href="/facts/Galerkin_method/oYm8Iylo">Galerkin method</a></li> <li><a href="/facts/Collocation_method/YMVkNS7m">Collocation method</a></li></ul> <ul><li>Bengt Fornberg (1996) <i>A Practical Guide to Pseudospectral Methods.</i> Cambridge University Press, Cambridge, UK</li> <li><a href="http://www-personal.umich.edu/~jpboyd/BOOK_Spectral2000.html">Chebyshev and Fourier Spectral Methods</a> by John P. Boyd.</li> <li>Canuto C., <a href="/facts/M._Yousuff_Hussaini/qyFChxY2">Hussaini M. Y.</a>, Quarteroni A., and Zang T.A. (2006) <i>Spectral Methods. Fundamentals in Single Domains.</i> Springer-Verlag, Berlin Heidelberg</li> <li>Javier de Frutos, Julia Novo (2000): <a href="https://epubs.siam.org/doi/10.1137/S0036142999351984">A Spectral Element Method for the Navier–Stokes Equations with Improved Accuracy</a></li> <li><a href="http://cdm.unimo.it/home/matematica/funaro.daniele/bube.htm">Polynomial Approximation of Differential Equations</a>, by Daniele Funaro, Lecture Notes in Physics, Volume 8, Springer-Verlag, Heidelberg 1992</li> <li>D. Gottlieb and S. Orzag (1977) "Numerical Analysis of Spectral Methods : Theory and Applications", SIAM, Philadelphia, PA</li> <li>J. Hesthaven, S. Gottlieb and D. Gottlieb (2007) "Spectral methods for time-dependent problems", Cambridge UP, Cambridge, UK</li> <li>Steven A. Orszag (1969) <i>Numerical Methods for the Simulation of Turbulence</i>, Phys. Fluids Supp. II, 12, 250–257</li> <li>Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). <a href="http://apps.nrbook.com/empanel/index.html#pg=1083">"Section 20.7. Spectral Methods"</a>. <i>Numerical Recipes: The Art of Scientific Computing</i> (3rd ed.). New York: Cambridge University Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-521-88068-8.</li> <li>Jie Shen, Tao Tang and Li-Lian Wang (2011) "Spectral Methods: Algorithms, Analysis and Applications" (Springer Series in Computational Mathematics, V. 41, Springer), <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 354071040X</li> <li>Lloyd N. Trefethen (2000) <i>Spectral Methods in MATLAB.</i> SIAM, Philadelphia, PA</li> <li>Muradova A. D. (2008) "The spectral method and numerical continuation algorithm for the von Kármán problem with postbuckling behaviour of solutions", Advances in Computational Mathematics, 29, pp. 179–206, <a href="https://doi.org/10.1007/s10444-007-9050-7">https://doi.org/10.1007/s10444-007-9050-7</a>.</li> <li>Muradova A. D. (2015) "A time spectral method for solving the nonlinear dynamic equations of a rectangular elastic plate", Journal of Engineering Mathematics, 92, pp. 83–101, <a href="https://doi.org/10.1007/s10665-014-9752-z">https://doi.org/10.1007/s10665-014-9752-z</a>.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>pp 235, Spectral Methods: evolution to complex geometries and applications to fluid dynamics, By Canuto, Hussaini, Quarteroni and Zang, Springer, 2007. <a href="https://books.google.com/books?id=7COgEw5_EBQC" target="_blank">https://books.google.com/books?id=7COgEw5_EBQC</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Muradova, Aliki D. (2008). "The spectral method and numerical continuation algorithm for the von Kármán problem with postbuckling behaviour of solutions". Adv Comput Math. 29 (2): 179–206, 2008. doi:10.1007/s10444-007-9050-7. hdl:1885/56758. S2CID 46564029. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Muradova, Aliki D. (2015). "A time spectral method for solving the nonlinear dynamic equations of a rectangular elastic plate". Journal of Engineering Mathematics. 92: 83–101, 2015. doi:10.1007/s10665-014-9752-z. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> </ol>