Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Spectral method

From Wikipedia, the free encyclopedia
Class of methods used in numerical analysis and scientific computing to solve ODE/PDE
This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(August 2013) (Learn how and when to remove this message)

Spectral methods are a class of techniques used inapplied mathematics andscientific computing to numerically solve certaindifferential equations. The idea is to write the solution of the differential equation as a sum of certain "basis functions" (for example, as aFourier series which is a sum ofsinusoids) and then to choose the coefficients in the sum in order to satisfy the differential equation as well as possible.

Spectral methods andfinite-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 generally nonzero over the whole domain, while finite element methods use basis functions that are nonzero only on small subdomains (compact support). Consequently, spectral methods connect variablesglobally while finite elements do solocally. Partially for this reason, spectral methods have excellent error properties, with the so-called "exponential convergence" being the fastest possible, when the solution issmooth. However, there are no known three-dimensional single-domain spectralshock 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 parameterh increases is sometimes called aspectral-element method.

Spectral methods can be used to solvedifferential equations (PDEs, ODEs, eigenvalue, etc)[2] andoptimization problems. 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 anynumerical method for ODEs.[3] Eigenvalue problems for ODEs are similarly converted to matrix eigenvalue problems[citation needed].

Spectral methods were developed in a long series of papers bySteven 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 withcollocation or aGalerkin or aTau approach . For very small problems, the spectral method is unique in that solutions may be written out symbolically, yielding a practical alternative to series solutions for differential equations.

Spectral methods can be computationally less expensive and easier to implement than finite element methods; they shine best when high accuracy is sought in simple domains with smooth solutions. However, because of their global nature, the matrices associated with step computation are dense and computational efficiency will quickly suffer when there are many degrees of freedom (with some exceptions, for example if matrix applications can be written asFourier transforms). For larger problems and nonsmooth solutions, finite elements will generally work better due to sparse matrices and better modelling of discontinuities and sharp bends.

Examples of spectral methods

[edit]

A concrete, linear example

[edit]

Here we presume an understanding of basic multivariatecalculus andFourier series. Ifg(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 functionf(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}

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

If we writef andg in Fourier series:

f=:∑aj,kei(jx+ky),g=:∑bj,kei(jx+ky),{\displaystyle {\begin{aligned}f&=:\sum a_{j,k}e^{i(jx+ky)},\\[5mu]g&=:\sum b_{j,k}e^{i(jx+ky)},\end{aligned}}}

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)}.}

We have exchanged partial differentiation with an infinite sum, which is legitimate if we assume for instance thatf 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}}}}*

which is an explicit formula for the Fourier coefficientsaj,k.

With periodic boundary conditions, thePoisson equation possesses a solution only ifb0,0 = 0. Therefore, we can freely choosea0,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 tohn{\displaystyle h^{n}}, whereh:=1/n{\displaystyle h:=1/n} andn{\displaystyle n} is the highest frequency treated.

Algorithm

[edit]
  1. Compute the Fourier transform (bj,k) ofg.
  2. Compute the Fourier transform (aj,k) off via the formula (*).
  3. Computef by taking an inverse Fourier transform of (aj,k).

Since we're only interested in a finite window of frequencies (of sizen, say) this can be done using afast Fourier transform algorithm. Therefore, globally the algorithm runs intimeO(n logn).

Nonlinear example

[edit]

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

Givenu(x,0){\displaystyle u(x,0)} on the periodic domainx∈[0,2π){\displaystyle x\in \left[0,2\pi \right)}, findu∈U{\displaystyle u\in {\mathcal {U}}} such that

∂tu+u∂xu=ρ∂xxu+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}

where ρ is theviscosity coefficient. In weak conservative form this becomes

⟨∂tu,v⟩=⟨∂x(−12u2+ρ∂xu),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}

where followinginner 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,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.}

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}:={\biggl \{}u:u(x,t)=\sum _{k=-N/2}^{N/2-1}{\hat {u}}_{k}(t)e^{ikx}{\biggr \}}}

and

VN:=span⁡{eikx:k∈−12N,…,12N−1}{\displaystyle {\mathcal {V}}^{N}:=\operatorname {span} \left\{e^{ikx}:k\in -{\tfrac {1}{2}}N,\dots ,{\tfrac {1}{2}}N-1\right\}}

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

⟨∂tu,eikx⟩=⟨12u2−ρ∂xu,∂xeikx⟩+⟨f,eikx⟩∀k∈{−12N,…,12N−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.}

Using theorthogonality relation⟨eilx,eikx⟩=2πδlk{\displaystyle \langle e^{ilx},e^{ikx}\rangle =2\pi \delta _{lk}} whereδlk{\displaystyle \delta _{lk}} is theKronecker delta, we simplify the above three terms for eachk{\displaystyle 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⟩=−12ik⟨∑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}\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}}}

Assemble the three terms for eachk{\displaystyle k} to obtain

2π∂tu^k=−iπk∑p+q=ku^pu^q−2πρk2u^k+2πf^kk∈{−12N,…,12N−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.}

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

∂tu^k=−ik2∑p+q=ku^pu^q−ρk2u^k+f^kk∈{−12N,…,12N−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.}

With Fourier transformed initial conditionsu^k(0){\displaystyle {\hat {u}}_{k}(0)} and forcingf^k(t){\displaystyle {\hat {f}}_{k}(t)}, this coupled system of ordinary differential equations may be integrated in time (using, e.g., aRunge Kutta technique) to find a solution. The nonlinear term is aconvolution, 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

[edit]

One can show that ifg{\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 aCn<∞{\displaystyle C_{n}<\infty } such that the error is less thanCnhn{\displaystyle C_{n}h^{n}} for all sufficiently small values ofh{\displaystyle h}. We say that the spectral method is of ordern{\displaystyle n}, for every n>0.

Because aspectral element method is afinite 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 arbitraryelliptic boundary value problems.

See also

[edit]

References

[edit]
  1. ^pp 235, Spectral Methods: evolution to complex geometries and applications to fluid dynamics, By Canuto, Hussaini, Quarteroni and Zang, Springer, 2007.
  2. ^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.
  3. ^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.
  • 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 (2000):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.
  • Jie Shen, Tao Tang and Li-Lian Wang (2011) "Spectral Methods: Algorithms, Analysis and Applications" (Springer Series in Computational Mathematics, V. 41, Springer),ISBN 354071040X
  • Lloyd N. Trefethen (2000)Spectral Methods in MATLAB. SIAM, Philadelphia, PA
  • 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,https://doi.org/10.1007/s10444-007-9050-7.
  • 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,https://doi.org/10.1007/s10665-014-9752-z.
Finite difference
Parabolic
Hyperbolic
Others
Finite volume
Finite element
Meshless/Meshfree
Domain decomposition
Others
Related
Spaces
Properties
Theorems
Operators
Algebras
Open problems
Applications
Advanced topics
Basic concepts
Main results
Special Elements/Operators
Spectrum
Decomposition
Spectral Theorem
Special algebras
Finite-Dimensional
Generalizations
Miscellaneous
Examples
Applications
Retrieved from "https://en.wikipedia.org/w/index.php?title=Spectral_method&oldid=1299590508"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2026 Movatter.jp