Spectral method








Spectral methods are a class of techniques used in applied mathematics and scientific computing to numerically solve certain differential equations, potentially involving the use of the fast Fourier transform. The idea is to write the solution of the differential equation as a sum of certain "basis functions" (for example, as a Fourier series which is a sum of sinusoids) and then to choose the coefficients in the sum in order to satisfy the differential equation as well as possible.


Spectral methods and finite element methods are closely related and built on the same ideas; the main difference between them is that spectral methods use basis functions that are nonzero over the whole domain, while finite element methods use basis functions that are nonzero only on small subdomains. In other words, spectral methods take on a global approach while finite element methods use a local approach. Partially for this reason, spectral methods have excellent error properties, with the so-called "exponential convergence" being the fastest possible, when the solution is smooth. However, there are no known three-dimensional single domain spectral shock capturing results (shock waves are not smooth).[1] In the finite element community, a method where the degree of the elements is very high or increases as the grid parameter h decreases to zero is sometimes called a spectral element method.


Spectral methods can be used to solve ordinary differential equations (ODEs), partial differential equations (PDEs) and eigenvalue problems involving differential equations. When applying spectral methods to time-dependent PDEs, the solution is typically written as a sum of basis functions with time-dependent coefficients; substituting this in the PDE yields a system of ODEs in the coefficients which can be solved using any numerical method for ODEs. Eigenvalue problems for ODEs are similarly converted to matrix eigenvalue problems[citation needed].


Spectral methods were developed in a long series of papers by Steven Orszag starting in 1969 including, but not limited to, Fourier series methods for periodic geometry problems, polynomial spectral methods for finite and unbounded geometry problems, pseudospectral methods for highly nonlinear problems, and spectral iteration methods for fast solution of steady state problems. The implementation of the spectral method is normally accomplished either with collocation or a Galerkin or a Tau approach.


Spectral methods are computationally less expensive than finite element methods, but become less accurate for problems with complex geometries and discontinuous coefficients. This increase in error is a consequence of the Gibbs phenomenon.




Contents






  • 1 Examples of spectral methods


    • 1.1 A concrete, linear example


      • 1.1.1 Algorithm




    • 1.2 Nonlinear example




  • 2 A relationship with the spectral element method


  • 3 See also


  • 4 References





Examples of spectral methods



A concrete, linear example


Here we presume an understanding of basic multivariate calculus and Fourier series. If 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π)) then we are interested in finding a function f(x,y) so that


(∂2∂x2+∂2∂y2)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}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

where the expression on the left denotes the second partial derivatives of f in x and y, respectively. This is the Poisson equation, and can be physically interpreted as some sort of heat conduction problem, or a problem in potential theory, among other possibilities.


If we write f and g in Fourier series:



f=:∑aj,kei(jx+ky){displaystyle f=:sum a_{j,k}e^{i(jx+ky)}}f=:sum a_{j,k}e^{i(jx+ky)}

g=:∑bj,kei(jx+ky){displaystyle g=:sum b_{j,k}e^{i(jx+ky)}}g=:sum b_{j,k}e^{i(jx+ky)}


and substitute into the differential equation, we obtain this equation:


∑−aj,k(j2+k2)ei(jx+ky)=∑bj,kei(jx+ky){displaystyle sum -a_{j,k}(j^{2}+k^{2})e^{i(jx+ky)}=sum b_{j,k}e^{i(jx+ky)}}sum -a_{j,k}(j^2+k^2)e^{i(jx+ky)}=sum b_{j,k}e^{i(jx+ky)}

We have exchanged partial differentiation with an infinite sum, which is legitimate if we assume for instance that f has a continuous second derivative. By the uniqueness theorem for Fourier expansions, we must then equate the Fourier coefficients term by term, giving


(*) aj,k=−bj,kj2+k2{displaystyle a_{j,k}=-{frac {b_{j,k}}{j^{2}+k^{2}}}}a_{j,k}=-frac{b_{j,k}}{j^2+k^2}

which is an explicit formula for the Fourier coefficients aj,k.


With periodic boundary conditions, the Poisson equation possesses a solution only if b0,0 = 0. Therefore,
we can freely choose a0,0 which will be equal to the mean of the resolution. This corresponds to choosing the
integration constant.


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 hn{displaystyle h^{n}}h^n, where h:=1/n{displaystyle h:=1/n}h:=1/n and n{displaystyle n}n is the highest frequency treated.



Algorithm



  1. Compute the Fourier transform (bj,k) of g.

  2. Compute the Fourier transform (aj,k) of f via the formula (*).

  3. Compute f by taking an inverse Fourier transform of (aj,k).


Since we're only interested in a finite window of frequencies (of size n, say) this can be done using a Fast Fourier Transform algorithm. Therefore, globally the algorithm runs in time O(n log n).



Nonlinear example


We wish to solve the forced, transient, nonlinear Burgers' equation using a spectral approach.


Given u(x,0){displaystyle u(x,0)}u(x,0) on the periodic domain
x∈[0,2π){displaystyle xin left[0,2pi right)}xinleft[0,2piright), find u∈U{displaystyle uin {mathcal {U}}}u in mathcal{U} such that


∂tu+u∂xu=ρ∂xxu+f∀x∈[0,2π),∀t>0{displaystyle partial _{t}u+upartial _{x}u=rho partial _{xx}u+fquad forall xin left[0,2pi right),forall t>0}partial_{t} u + u partial_{x} u = rho partial_{xx} u + f quad forall xinleft[0,2piright), forall t>0

where ρ is the viscosity coefficient. In weak conservative form this becomes


⟨∂tu,v⟩=⟨∂x(−12u2+ρ∂xu),v⟩+⟨f,v⟩∀v∈V,∀t>0{displaystyle leftlangle partial _{t}u,vrightrangle =leftlangle partial _{x}left(-{frac {1}{2}}u^{2}+rho partial _{x}uright),vrightrangle +leftlangle f,vrightrangle quad forall vin {mathcal {V}},forall t>0}{displaystyle leftlangle partial _{t}u,vrightrangle =leftlangle partial _{x}left(-{frac {1}{2}}u^{2}+rho partial _{x}uright),vrightrangle +leftlangle f,vrightrangle quad forall vin {mathcal {V}},forall t>0}

where ⟨f,g⟩:=∫02πf(x)g(x)¯dx{displaystyle langle f,grangle :=int _{0}^{2pi }f(x){overline {g(x)}},dx}langle f, g rangle := int_{0}^{2pi} f(x)<br /> overline{g(x)},dx following inner product notation. Integrating by parts and using periodicity grants


⟨∂tu,v⟩=⟨12u2−ρ∂xu,∂xv⟩+⟨f,v⟩∀v∈V,∀t>0.{displaystyle langle partial _{t}u,vrangle =leftlangle {frac {1}{2}}u^{2}-rho partial _{x}u,partial _{x}vrightrangle +leftlangle f,vrightrangle quad forall vin {mathcal {V}},forall t>0.}{displaystyle langle partial _{t}u,vrangle =leftlangle {frac {1}{2}}u^{2}-rho partial _{x}u,partial _{x}vrightrangle +leftlangle f,vrightrangle quad forall vin {mathcal {V}},forall t>0.}

To apply the Fourier-Galerkin method, choose both


UN:={u:u(x,t)=∑k=−N/2N/2−1u^k(t)eikx}{displaystyle {mathcal {U}}^{N}:=left{u:u(x,t)=sum _{k=-N/2}^{N/2-1}{hat {u}}_{k}(t)e^{ikx}right}}mathcal{U}^N := left{ u : u(x,t)=sum_{k=-N/2}^{N/2-1} hat{u}_{k}(t) e^{i k x}right}

and


VN:= span{eikx:k∈−N/2,…,N/2−1}{displaystyle {mathcal {V}}^{N}:={text{ span}}left{e^{ikx}:kin -N/2,dots ,N/2-1right}}mathcal{V}^N :=text{ span}left{ e^{i k x} : kin -N/2,dots,N/2-1right}

where u^k(t):=12π⟨u(x,t),eikx⟩{displaystyle {hat {u}}_{k}(t):={frac {1}{2pi }}langle u(x,t),e^{ikx}rangle }hat{u}_k(t):=frac{1}{2pi}langle u(x,t), e^{i k x} rangle. This reduces the problem to finding u∈UN{displaystyle uin {mathcal {U}}^{N}}uinmathcal{U}^N such that


⟨∂tu,eikx⟩=⟨12u2−ρ∂xu,∂xeikx⟩+⟨f,eikx⟩∀k∈{−N/2,…,N/2−1},∀t>0.{displaystyle langle partial _{t}u,e^{ikx}rangle =leftlangle {frac {1}{2}}u^{2}-rho partial _{x}u,partial _{x}e^{ikx}rightrangle +leftlangle f,e^{ikx}rightrangle quad forall kin left{-N/2,dots ,N/2-1right},forall t>0.}{displaystyle langle partial _{t}u,e^{ikx}rangle =leftlangle {frac {1}{2}}u^{2}-rho partial _{x}u,partial _{x}e^{ikx}rightrangle +leftlangle f,e^{ikx}rightrangle quad forall kin left{-N/2,dots ,N/2-1right},forall t>0.}

Using the orthogonality relation ⟨eilx,eikx⟩=2πδlk{displaystyle langle e^{ilx},e^{ikx}rangle =2pi delta _{lk}}langle e^{i l x}, e^{i k x} rangle = 2 pi delta_{lk} where δlk{displaystyle delta _{lk}}delta_{lk} is the Kronecker delta, we simplify the above three terms for each k{displaystyle k}k to see


⟨∂tu,eikx⟩=⟨∂t∑lu^leilx,eikx⟩=⟨∑l∂tu^leilx,eikx⟩=2π∂tu^k,⟨f,eikx⟩=⟨∑lf^leilx,eikx⟩=2πf^k, and⟨12u2−ρ∂xu,∂xeikx⟩=⟨12(∑pu^peipx)(∑qu^qeiqx)−ρ∂x∑lu^leilx,∂xeikx⟩=⟨12∑p∑qu^pu^qei(p+q)x,ikeikx⟩−⟨ρi∑llu^leilx,ikeikx⟩=−ik2⟨∑p∑qu^pu^qei(p+q)x,eikx⟩−ρk⟨∑llu^leilx,eikx⟩=−iπk∑p+q=ku^pu^q−2πρk2u^k.{displaystyle {begin{aligned}leftlangle partial _{t}u,e^{ikx}rightrangle &=leftlangle partial _{t}sum _{l}{hat {u}}_{l}e^{ilx},e^{ikx}rightrangle =leftlangle sum _{l}partial _{t}{hat {u}}_{l}e^{ilx},e^{ikx}rightrangle =2pi partial _{t}{hat {u}}_{k},\leftlangle f,e^{ikx}rightrangle &=leftlangle sum _{l}{hat {f}}_{l}e^{ilx},e^{ikx}rightrangle =2pi {hat {f}}_{k},{text{ and}}\leftlangle {frac {1}{2}}u^{2}-rho partial _{x}u,partial _{x}e^{ikx}rightrangle &=leftlangle {frac {1}{2}}left(sum _{p}{hat {u}}_{p}e^{ipx}right)left(sum _{q}{hat {u}}_{q}e^{iqx}right)-rho partial _{x}sum _{l}{hat {u}}_{l}e^{ilx},partial _{x}e^{ikx}rightrangle \&=leftlangle {frac {1}{2}}sum _{p}sum _{q}{hat {u}}_{p}{hat {u}}_{q}e^{ileft(p+qright)x},ike^{ikx}rightrangle -leftlangle rho isum _{l}l{hat {u}}_{l}e^{ilx},ike^{ikx}rightrangle \&=-{frac {ik}{2}}leftlangle sum _{p}sum _{q}{hat {u}}_{p}{hat {u}}_{q}e^{ileft(p+qright)x},e^{ikx}rightrangle -rho kleftlangle sum _{l}l{hat {u}}_{l}e^{ilx},e^{ikx}rightrangle \&=-ipi ksum _{p+q=k}{hat {u}}_{p}{hat {u}}_{q}-2pi rho {}k^{2}{hat {u}}_{k}.end{aligned}}}{displaystyle {begin{aligned}leftlangle partial _{t}u,e^{ikx}rightrangle &=leftlangle partial _{t}sum _{l}{hat {u}}_{l}e^{ilx},e^{ikx}rightrangle =leftlangle sum _{l}partial _{t}{hat {u}}_{l}e^{ilx},e^{ikx}rightrangle =2pi partial _{t}{hat {u}}_{k},\leftlangle f,e^{ikx}rightrangle &=leftlangle sum _{l}{hat {f}}_{l}e^{ilx},e^{ikx}rightrangle =2pi {hat {f}}_{k},{text{ and}}\leftlangle {frac {1}{2}}u^{2}-rho partial _{x}u,partial _{x}e^{ikx}rightrangle &=leftlangle {frac {1}{2}}left(sum _{p}{hat {u}}_{p}e^{ipx}right)left(sum _{q}{hat {u}}_{q}e^{iqx}right)-rho partial _{x}sum _{l}{hat {u}}_{l}e^{ilx},partial _{x}e^{ikx}rightrangle \&=leftlangle {frac {1}{2}}sum _{p}sum _{q}{hat {u}}_{p}{hat {u}}_{q}e^{ileft(p+qright)x},ike^{ikx}rightrangle -leftlangle rho isum _{l}l{hat {u}}_{l}e^{ilx},ike^{ikx}rightrangle \&=-{frac {ik}{2}}leftlangle sum _{p}sum _{q}{hat {u}}_{p}{hat {u}}_{q}e^{ileft(p+qright)x},e^{ikx}rightrangle -rho kleftlangle sum _{l}l{hat {u}}_{l}e^{ilx},e^{ikx}rightrangle \&=-ipi ksum _{p+q=k}{hat {u}}_{p}{hat {u}}_{q}-2pi rho {}k^{2}{hat {u}}_{k}.end{aligned}}}

Assemble the three terms for each k{displaystyle k}k to obtain


2π∂tu^k=−iπk∑p+q=ku^pu^q−2πρk2u^k+2πf^kk∈{−N/2,…,N/2−1},∀t>0.{displaystyle 2pi partial _{t}{hat {u}}_{k}=-ipi ksum _{p+q=k}{hat {u}}_{p}{hat {u}}_{q}-2pi rho {}k^{2}{hat {u}}_{k}+2pi {hat {f}}_{k}quad kin left{-N/2,dots ,N/2-1right},forall t>0.}<br /> 2 pi partial_t hat{u}_k<br /> =<br /> - i pi k sum_{p+q=k} hat{u}_p hat{u}_q <br /> - 2pirho{}k^2hat{u}_k<br /> + 2 pi hat{f}_k<br /> quad kinleft{ -N/2,dots,N/2-1 right}, forall t>0.<br />

Dividing through by 2π{displaystyle 2pi }2pi , we finally arrive at


∂tu^k=−ik2∑p+q=ku^pu^q−ρk2u^k+f^kk∈{−N/2,…,N/2−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 kin left{-N/2,dots ,N/2-1right},forall t>0.}<br /> partial_t hat{u}_k<br /> =<br /> - frac{i k}{2} sum_{p+q=k} hat{u}_p hat{u}_q <br /> - rho{}k^2hat{u}_k<br /> + hat{f}_k<br /> quad kinleft{ -N/2,dots,N/2-1 right}, forall t>0.<br />

With Fourier transformed initial conditions u^k(0){displaystyle {hat {u}}_{k}(0)}hat{u}_{k}(0) and forcing f^k(t){displaystyle {hat {f}}_{k}(t)}hat{f}_{k}(t), this coupled system of ordinary differential equations may be integrated in time (using, e.g., a Runge Kutta technique) to find a solution. The nonlinear term is a convolution, and there are several transform-based techniques for evaluating it efficiently. See the references by Boyd and Canuto et al. for more details.



A relationship with the spectral element method


One can show that if g{displaystyle g}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 Cn<∞{displaystyle C_{n}<infty }{displaystyle C_{n}<infty } such that the error is less than Cnhn{displaystyle C_{n}h^{n}}{displaystyle C_{n}h^{n}} for all sufficiently small values of h{displaystyle h}h. We say that the spectral method is of order n{displaystyle n}n, for every n>0.


Because a spectral element method is a finite element method 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 elliptic boundary value problems.



See also



  • Finite element method

  • Gaussian grid

  • Pseudo-spectral method

  • Spectral element method

  • Galerkin method

  • Collocation method




References





  1. ^ pp 235, Spectral Methods: evolution to complex geometries and applications to fluid dynamics, By Canuto, Hussaini, Quarteroni and Zang, Springer, 2007.




  • Bengt Fornberg (1996) A Practical Guide to Pseudospectral Methods. Cambridge University Press, Cambridge, UK


  • Chebyshev and Fourier Spectral Methods by John P. Boyd.

  • Canuto C., Hussaini M. Y., Quarteroni A., and Zang T.A. (2006) Spectral Methods. Fundamentals in Single Domains. Springer-Verlag, Berlin Heidelberg

  • Javier de Frutos, Julia Novo: A Spectral Element Method for the Navier--Stokes Equations with Improved Accuracy


  • Polynomial Approximation of Differential Equations, by Daniele Funaro, Lecture Notes in Physics, Volume 8, Springer-Verlag, Heidelberg 1992

  • D. Gottlieb and S. Orzag (1977) "Numerical Analysis of Spectral Methods : Theory and Applications", SIAM, Philadelphia, PA

  • J. Hesthaven, S. Gottlieb and D. Gottlieb (2007) "Spectral methods for time-dependent problems", Cambridge UP, Cambridge, UK

  • Steven A. Orszag (1969) Numerical Methods for the Simulation of Turbulence, Phys. Fluids Supp. II, 12, 250-257


  • Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 20.7. Spectral Methods". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output .citation q{quotes:"""""""'""'"}.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-maint{display:none;color:#33aa33;margin-left:0.3em}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}

  • Lloyd N. Trefethen (2000) Spectral Methods in MATLAB. SIAM, Philadelphia, PA




-

Popular posts from this blog

Guess what letter conforming each word

Image
6 $begingroup$ This is an entry in the Fortnightly Topic Challenge #41: Short and Sweet. 1 letter only could be mean anything . With an additional letter in front , could be used as medicine component and something you definitely learn or at least heard once. Add another letter in front , you would possibly hear that many times . Add an additional letter in front , you would found an independent country . With an additional letter, in the end , you would found something related to apple . Add another letter in the end , you would found something bad . Hint: Each letter is unique . word knowledge letters chemistry share | improve this question ...
Read more

Port of Spain

Image
For ports in the country of Spain, see List of ports in Spain. City in City of Port of Spain, Trinidad and Tobago Port of Spain City City of Port of Spain Top to bottom (left to right): Skyline of Port of Spain from Gulf of Paria; National Academy for the Performing Arts, Independence Square, Eric Williams Plaza; MovieTowne, Port of Port of Spain Motto(s):  "We Gather Strength As We Go Along" Port of Spain Coordinates: 10°40′N 61°31′W  /  10.667°N 61.517°W  / 10.667; -61.517 Coordinates: 10°40′N 61°31′W  /  10.667°N 61.517°W  / 10.667; -61.517 Country   Trinidad and Tobago Jurisdiction City of Port of Spain Settled 1560 Incorporated (town) 1853 Incorporated (city) 1914 Government  • Mayor Joel Martinez  • Governing body City Corporation Area [1]  • City 12 km 2 (5 sq mi) Elevation [2] 66 m (217 ft) Population (2011) [1]  • City 37,074  • Rank 3rd  • Density 3,090/km 2 (8,000/sq mi)...
Read more

Run scheduled task as local user group (not BUILTIN)

Image
0 I am trying to run a scheduled task with User Group (not a single user). This is working fine when I in the field "when running a task, use the following user account:" insert BUILTIN User Group (for example: Administrators or Users). But when I try it with the created Local User Group (example: TestGroup) it is not working. The Users in the TestGroup are the same as in the Administrators group. What could be the problem? Are there some restrictions to the Created User Group compared to BUILTINUsers? scheduled-tasks taskscheduler windowstaskschedule share | improve this question asked Nov 15 '18 at 15:36 Far...
Read more