Spectral Methods.pdf
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Spectral Methods.pdf as PDF for free.
More details
- Words: 2,011
- Pages: 28
Basic principles
Two illustrative examples of spectral methods
Summary
Introduction to Spectral Methods Lu Yixin
September 26, 2007
The end
Basic principles
Two illustrative examples of spectral methods
Summary
Outline
1
Basic principles Problem formulation Various numerical methods Various spectral methods How to choose trial functions
2
Two illustrative examples of spectral methods A Fourier Galerkin method for the wave equation A Chebyshev collocation method for the heat equation
3
Summary
The end
Basic principles
Two illustrative examples of spectral methods
Summary
Problem formulation
Solving a PDE numerically
Consider the PDE with boundary condition Lu = f , in Ω u = g, on ∂Ω. Question: How to solve the above PDE numerically? Approximate the unknown u(x, t) by a sum of “basis functions”: u(x, t) ≈ u N (x, t) =
N X
an (t)φn (x)
n=0
and use some strategy to minimize the Residual Lu N − f .
The end
Basic principles
Two illustrative examples of spectral methods
Summary
Problem formulation
Trial functions and test functions
Search for solution u N in a finite-dimensional sub-space HN of some Hilbert space H. Trial Functions: basis of HN : (φ0 , . . . , φN ) N
u =
N X
ak φk
k =0
Test Functions: family of functions (ψ0 , . . . , ψN ) ∀n ∈ 0, . . . , N, (ψn , R) = 0
The end
Basic principles
Two illustrative examples of spectral methods
Summary
Various numerical methods
Classification according to trial functions
Finite difference: trial functions: overlapping local polynomials of low order Finite element: trial functions: local smooth functions, nearly orthogonal Spectral methods: trial functions: global smooth functions, nearly orthogonal
The end
Basic principles
Two illustrative examples of spectral methods
Summary
Various spectral methods
Classification according to test functions
Galerkin: ψn = φn , φn satisfy some or all of the boundary conditions. Collocation: ψn = δ(x − xn ), xn are collocation points. Tau: ψn = φn , but φn do not satisfy the boundary conditions.
The end
Basic principles
Two illustrative examples of spectral methods
Summary
How to choose trial functions
What sets of "trial functions" will work?
It is obvious that we would like our trial function sets to have a number of properties: easy to compute rapid convergence completeness
The end
Basic principles
Two illustrative examples of spectral methods
Summary
Outline of the second part
A Fourier Galerkin method for the wave equation: trial function test function weak formulation accuracy comparison with FD
A Chebyshev collocation method for the heat equation: . . . , comparison with Galerkin method, . . .
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Fourier Galerkin method for the wave equation
Wave equation
Many evolution equations can be written as ∂u = M(u). ∂t Consider the domain (0, 2π) with periodic boundary conditions. The approximate solution u N is represented as u N (x, t) =
N/2 X −N/2
ak (t)φk (x).
The end
Basic principles
Two illustrative examples of spectral methods
Summary
The end
A Fourier Galerkin method for the wave equation
Weak formulation
In general, ∂u N 6= M(u N ). ∂t The approximation is obtained by selecting a set of test functions ψk and requiring that Z
2π
[ 0
∂u N − M(u N )]ψk (x)dx = 0, ∂t
for k = −N/2,. . . ,N/2.
(1)
Basic principles
Two illustrative examples of spectral methods
Summary
The end
A Fourier Galerkin method for the wave equation
Spectral method using trigonometric polynomials
Trigonometric polynomials: φk (x) = eikx , 1 −ikx ψk (x) = 2π e . If this were merely an approximation problem, then u N (x, t) would be the truncated Fourier series of the known function u(x, t) with Z 2π ak (t) = u(x, t)ψk (x)dx. 0
However, for the PDE, u(x, t) is not known; the approximation is determined by (1).
Basic principles
Two illustrative examples of spectral methods
Summary
A Fourier Galerkin method for the wave equation
How does the scheme work (1) ?
For the linear hyperbolic problem ∂u ∂u − = 0, ∂t ∂x i.e.,for M(u) =
∂u , ∂x
condition (1) becomes 1 2π
Z
2π
[( 0
N/2 ∂ X ∂ − ) al (t)eilx ]e−ikx dx = 0, ∂t ∂x −N/2
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Fourier Galerkin method for the wave equation
How does the scheme work (2)?
The analytical (spatial) differentiation of the trial functions and the analytical integration of that expression produce the dynamical equations: dak − ikak = 0, k = −N/2, . . . , N/2. dt The initial conditions are: Z ak (0) =
2π
u(x, 0)ψk (x)dx. 0
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Fourier Galerkin method for the wave equation
The accuracy of the Fourier Galerkin method (1) Use the initial condition u(x, 0) = sin(π cos(x)) to illustrate the accuracy of the Fourier Galerkin method for the above hyperbolic equation. The exact solution, u(x, t) = sin(π cos(x + t)), has the Fourier expansion u(x, t) =
∞ X k =−∞
ak (t)eikx ,
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Fourier Galerkin method for the wave equation
The accuracy of the Fourier Galerkin method (2) The Fourier coefficients are ak (t) = sin(
kπ )Jk (π)eikt 2
and Jk (t) is the Bessel function of order k . The asymptotic properties of the Bessel functions imply that k p ak (t) →
0 as k → ∞
for all positive integers p. Thus,the truncated Fourier series, u N (x, t) =
N/2 X
ak (t)eikx
−N/2
converges faster than any finite power of 1/N.
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Fourier Galerkin method for the wave equation
Comparison with finite difference method An illustrative of the superior accuracy from the spectral method for this problem is given in the following figure.
Figure: Maximum errors for the linear hyperbolic problem at t = 2π for Fourier Galerkin and several finite difference schemes
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Chebyshev collocation method for the heat equation
Chebyshev polynomials for the heat equation Chebyshev polynomials: Tk (x) = cos(k cos−1 x), for k = 0, 1, . . . . The first few Chebshev polynomials are T0 (x) = 1 T1 (x) = x T2 (x) = 2x 2 − 1 ... Tn+1 (x) = 2xTn (x) − Tn−1 (x).
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Chebyshev collocation method for the heat equation
The approximate solution (1) Given the heat equation ∂u ∂ 2 u ∂2u − = 0, i.e., M(u) = ∂t ∂x 2 ∂x 2 on (−1, 1) with homogeneous Dirichlet boundary conditions, u(−1, t) = 0, u(1, t) = 0. Choosing the trial functions φk (x) = Tk (x),
k = 0, 1, . . . , N,
the approximate solution has the representation N
u (x, t) =
N X k =0
ak (t)φk (x).
The end
Basic principles
Two illustrative examples of spectral methods
Summary
The end
A Chebyshev collocation method for the heat equation
The approximate solution (2)
In the collocation approach the above PDE must be satisfied exactly by the approximate solution at collocation points xj in the domain of (−1, 1): ∂u N − M(u N )|x=xj = 0, j = 1, . . . , N − 1. ∂t u N (−1, t) = 0, u N (1, t) = 0. u N (xk , 0) = u(xk , 0),
k = 0, . . . , N.
(2)
Basic principles
Two illustrative examples of spectral methods
Summary
A Chebyshev collocation method for the heat equation
Choice of collocation points
A convenient choice for the collocation points xj is xj = cos(
πj ). N
Note that
πjk ). N We can apply Fast Fourier Transform (FFT) to evaluate M(u N )|x=xj . φk (xj ) = cos(
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Chebyshev collocation method for the heat equation
How the Chebyshev collocation approach works (1)
For the particular initial condition u(x, 0) = sin πx, the exact solution is 2
u(x, t) = e−π t sin πx. It has the infinite Chebyshev expansion u(x, t) =
∞ X k =0
bk (t)Tk (x),
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Chebyshev collocation method for the heat equation
How the Chebyshev collocation approach works (2)
. . . where bk (t) =
kπ 2 2 sin( )Jk (π)e−π t ck 2
with
ck =
2, 1,
k = 0, k ≥1
Since Jk (π) is decaying rapidly, the truncated series converges at an exponential rate. A well-designed collocation method will do the same.
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Chebyshev collocation method for the heat equation
How the Chebyshev collocation approach works (3) A collocation method is implemented in terms of the nodal values uj (t) = u N (xj , t) and we have the expansion u N (x, t) =
N X
uj (t)φj (x),
j=0
and now φj denote the characteristic Lagrange polynomials with the property φj (xi ) = δij for 0 ≤ i, j ≤ N. The expansion coefficients are given by ak (t) =
N 2 X cl Nc k
−1
ul (t) cos
l=0
where
ck =
2, 1,
πlk , N
k = 0, 1, . . . , N,
k = 0 or N 1≤k ≤N −1
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Chebyshev collocation method for the heat equation
How the Chebyshev collocation approach works (4) The exact derivative of u N (x, t) becomes N
X (2) ∂2uN ak (t)Tk (x), (t) = ∂x 2 k =0
where (1)
(1)
aN+1 (t) = 0, aN (t) = 0, (1) (1) c k ak (t) = ak +2 (t) + 2(k + 1)ak +1 (t), k = N − 1, . . . , 0, and (2)
(2)
aN+1 (t) = 0, aN (t) = 0, (2) (2) (1) c k ak (t) = ak +2 (t) + 2(k + 1)ak +1 (t), k = N − 1, . . . , 0.
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Chebyshev collocation method for the heat equation
How the Chebyshev collocation approach works (5) (2)
The coefficients ak depend linearly on the nodal values ul ; thus, there exists a matrix DN2 such that N
N
k =0
l=0
X X (2) ∂2uN πjk (DN2 )jl ul (t). = (t)|x=xj = ak (t) cos 2 N ∂x Substituting the above expression into (2), we obtain a system of ODE for the nodal unknowns: N
X duj (t) = (DN2 )jl ul (t), dt
j = 1, . . . , N − 1.
l=0
Supplemented by the initial conditions, the ODE system for the nodal values of solution is readily integrated in time.
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Chebyshev collocation method for the heat equation
Comparison with Finite difference method An illustrative of the superior accuracy from the spectral method for this problem is given in the following figure.
Figure: Maximum errors for the heat equation problem at t = 1 for Chebyshev collocation and several finite difference schemes
The end
Basic principles
Two illustrative examples of spectral methods
Summary
Pros and Cons of spectral methods
Spectral methods have many advantages over FD and FE methods: high accuracy efficiency exponential convergency/spectral convergency However, spectral methods also suffers drawbacks in the following folds: coding: more difficult to code than FD cost: costly per degree of freedom than FD geometry: for complicated domains, heavy loss of accuracy
The end
Basic principles
Two illustrative examples of spectral methods
Summary
The end
Thanks for your attention!
Two illustrative examples of spectral methods
Summary
Introduction to Spectral Methods Lu Yixin
September 26, 2007
The end
Basic principles
Two illustrative examples of spectral methods
Summary
Outline
1
Basic principles Problem formulation Various numerical methods Various spectral methods How to choose trial functions
2
Two illustrative examples of spectral methods A Fourier Galerkin method for the wave equation A Chebyshev collocation method for the heat equation
3
Summary
The end
Basic principles
Two illustrative examples of spectral methods
Summary
Problem formulation
Solving a PDE numerically
Consider the PDE with boundary condition Lu = f , in Ω u = g, on ∂Ω. Question: How to solve the above PDE numerically? Approximate the unknown u(x, t) by a sum of “basis functions”: u(x, t) ≈ u N (x, t) =
N X
an (t)φn (x)
n=0
and use some strategy to minimize the Residual Lu N − f .
The end
Basic principles
Two illustrative examples of spectral methods
Summary
Problem formulation
Trial functions and test functions
Search for solution u N in a finite-dimensional sub-space HN of some Hilbert space H. Trial Functions: basis of HN : (φ0 , . . . , φN ) N
u =
N X
ak φk
k =0
Test Functions: family of functions (ψ0 , . . . , ψN ) ∀n ∈ 0, . . . , N, (ψn , R) = 0
The end
Basic principles
Two illustrative examples of spectral methods
Summary
Various numerical methods
Classification according to trial functions
Finite difference: trial functions: overlapping local polynomials of low order Finite element: trial functions: local smooth functions, nearly orthogonal Spectral methods: trial functions: global smooth functions, nearly orthogonal
The end
Basic principles
Two illustrative examples of spectral methods
Summary
Various spectral methods
Classification according to test functions
Galerkin: ψn = φn , φn satisfy some or all of the boundary conditions. Collocation: ψn = δ(x − xn ), xn are collocation points. Tau: ψn = φn , but φn do not satisfy the boundary conditions.
The end
Basic principles
Two illustrative examples of spectral methods
Summary
How to choose trial functions
What sets of "trial functions" will work?
It is obvious that we would like our trial function sets to have a number of properties: easy to compute rapid convergence completeness
The end
Basic principles
Two illustrative examples of spectral methods
Summary
Outline of the second part
A Fourier Galerkin method for the wave equation: trial function test function weak formulation accuracy comparison with FD
A Chebyshev collocation method for the heat equation: . . . , comparison with Galerkin method, . . .
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Fourier Galerkin method for the wave equation
Wave equation
Many evolution equations can be written as ∂u = M(u). ∂t Consider the domain (0, 2π) with periodic boundary conditions. The approximate solution u N is represented as u N (x, t) =
N/2 X −N/2
ak (t)φk (x).
The end
Basic principles
Two illustrative examples of spectral methods
Summary
The end
A Fourier Galerkin method for the wave equation
Weak formulation
In general, ∂u N 6= M(u N ). ∂t The approximation is obtained by selecting a set of test functions ψk and requiring that Z
2π
[ 0
∂u N − M(u N )]ψk (x)dx = 0, ∂t
for k = −N/2,. . . ,N/2.
(1)
Basic principles
Two illustrative examples of spectral methods
Summary
The end
A Fourier Galerkin method for the wave equation
Spectral method using trigonometric polynomials
Trigonometric polynomials: φk (x) = eikx , 1 −ikx ψk (x) = 2π e . If this were merely an approximation problem, then u N (x, t) would be the truncated Fourier series of the known function u(x, t) with Z 2π ak (t) = u(x, t)ψk (x)dx. 0
However, for the PDE, u(x, t) is not known; the approximation is determined by (1).
Basic principles
Two illustrative examples of spectral methods
Summary
A Fourier Galerkin method for the wave equation
How does the scheme work (1) ?
For the linear hyperbolic problem ∂u ∂u − = 0, ∂t ∂x i.e.,for M(u) =
∂u , ∂x
condition (1) becomes 1 2π
Z
2π
[( 0
N/2 ∂ X ∂ − ) al (t)eilx ]e−ikx dx = 0, ∂t ∂x −N/2
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Fourier Galerkin method for the wave equation
How does the scheme work (2)?
The analytical (spatial) differentiation of the trial functions and the analytical integration of that expression produce the dynamical equations: dak − ikak = 0, k = −N/2, . . . , N/2. dt The initial conditions are: Z ak (0) =
2π
u(x, 0)ψk (x)dx. 0
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Fourier Galerkin method for the wave equation
The accuracy of the Fourier Galerkin method (1) Use the initial condition u(x, 0) = sin(π cos(x)) to illustrate the accuracy of the Fourier Galerkin method for the above hyperbolic equation. The exact solution, u(x, t) = sin(π cos(x + t)), has the Fourier expansion u(x, t) =
∞ X k =−∞
ak (t)eikx ,
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Fourier Galerkin method for the wave equation
The accuracy of the Fourier Galerkin method (2) The Fourier coefficients are ak (t) = sin(
kπ )Jk (π)eikt 2
and Jk (t) is the Bessel function of order k . The asymptotic properties of the Bessel functions imply that k p ak (t) →
0 as k → ∞
for all positive integers p. Thus,the truncated Fourier series, u N (x, t) =
N/2 X
ak (t)eikx
−N/2
converges faster than any finite power of 1/N.
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Fourier Galerkin method for the wave equation
Comparison with finite difference method An illustrative of the superior accuracy from the spectral method for this problem is given in the following figure.
Figure: Maximum errors for the linear hyperbolic problem at t = 2π for Fourier Galerkin and several finite difference schemes
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Chebyshev collocation method for the heat equation
Chebyshev polynomials for the heat equation Chebyshev polynomials: Tk (x) = cos(k cos−1 x), for k = 0, 1, . . . . The first few Chebshev polynomials are T0 (x) = 1 T1 (x) = x T2 (x) = 2x 2 − 1 ... Tn+1 (x) = 2xTn (x) − Tn−1 (x).
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Chebyshev collocation method for the heat equation
The approximate solution (1) Given the heat equation ∂u ∂ 2 u ∂2u − = 0, i.e., M(u) = ∂t ∂x 2 ∂x 2 on (−1, 1) with homogeneous Dirichlet boundary conditions, u(−1, t) = 0, u(1, t) = 0. Choosing the trial functions φk (x) = Tk (x),
k = 0, 1, . . . , N,
the approximate solution has the representation N
u (x, t) =
N X k =0
ak (t)φk (x).
The end
Basic principles
Two illustrative examples of spectral methods
Summary
The end
A Chebyshev collocation method for the heat equation
The approximate solution (2)
In the collocation approach the above PDE must be satisfied exactly by the approximate solution at collocation points xj in the domain of (−1, 1): ∂u N − M(u N )|x=xj = 0, j = 1, . . . , N − 1. ∂t u N (−1, t) = 0, u N (1, t) = 0. u N (xk , 0) = u(xk , 0),
k = 0, . . . , N.
(2)
Basic principles
Two illustrative examples of spectral methods
Summary
A Chebyshev collocation method for the heat equation
Choice of collocation points
A convenient choice for the collocation points xj is xj = cos(
πj ). N
Note that
πjk ). N We can apply Fast Fourier Transform (FFT) to evaluate M(u N )|x=xj . φk (xj ) = cos(
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Chebyshev collocation method for the heat equation
How the Chebyshev collocation approach works (1)
For the particular initial condition u(x, 0) = sin πx, the exact solution is 2
u(x, t) = e−π t sin πx. It has the infinite Chebyshev expansion u(x, t) =
∞ X k =0
bk (t)Tk (x),
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Chebyshev collocation method for the heat equation
How the Chebyshev collocation approach works (2)
. . . where bk (t) =
kπ 2 2 sin( )Jk (π)e−π t ck 2
with
ck =
2, 1,
k = 0, k ≥1
Since Jk (π) is decaying rapidly, the truncated series converges at an exponential rate. A well-designed collocation method will do the same.
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Chebyshev collocation method for the heat equation
How the Chebyshev collocation approach works (3) A collocation method is implemented in terms of the nodal values uj (t) = u N (xj , t) and we have the expansion u N (x, t) =
N X
uj (t)φj (x),
j=0
and now φj denote the characteristic Lagrange polynomials with the property φj (xi ) = δij for 0 ≤ i, j ≤ N. The expansion coefficients are given by ak (t) =
N 2 X cl Nc k
−1
ul (t) cos
l=0
where
ck =
2, 1,
πlk , N
k = 0, 1, . . . , N,
k = 0 or N 1≤k ≤N −1
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Chebyshev collocation method for the heat equation
How the Chebyshev collocation approach works (4) The exact derivative of u N (x, t) becomes N
X (2) ∂2uN ak (t)Tk (x), (t) = ∂x 2 k =0
where (1)
(1)
aN+1 (t) = 0, aN (t) = 0, (1) (1) c k ak (t) = ak +2 (t) + 2(k + 1)ak +1 (t), k = N − 1, . . . , 0, and (2)
(2)
aN+1 (t) = 0, aN (t) = 0, (2) (2) (1) c k ak (t) = ak +2 (t) + 2(k + 1)ak +1 (t), k = N − 1, . . . , 0.
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Chebyshev collocation method for the heat equation
How the Chebyshev collocation approach works (5) (2)
The coefficients ak depend linearly on the nodal values ul ; thus, there exists a matrix DN2 such that N
N
k =0
l=0
X X (2) ∂2uN πjk (DN2 )jl ul (t). = (t)|x=xj = ak (t) cos 2 N ∂x Substituting the above expression into (2), we obtain a system of ODE for the nodal unknowns: N
X duj (t) = (DN2 )jl ul (t), dt
j = 1, . . . , N − 1.
l=0
Supplemented by the initial conditions, the ODE system for the nodal values of solution is readily integrated in time.
The end
Basic principles
Two illustrative examples of spectral methods
Summary
A Chebyshev collocation method for the heat equation
Comparison with Finite difference method An illustrative of the superior accuracy from the spectral method for this problem is given in the following figure.
Figure: Maximum errors for the heat equation problem at t = 1 for Chebyshev collocation and several finite difference schemes
The end
Basic principles
Two illustrative examples of spectral methods
Summary
Pros and Cons of spectral methods
Spectral methods have many advantages over FD and FE methods: high accuracy efficiency exponential convergency/spectral convergency However, spectral methods also suffers drawbacks in the following folds: coding: more difficult to code than FD cost: costly per degree of freedom than FD geometry: for complicated domains, heavy loss of accuracy
The end
Basic principles
Two illustrative examples of spectral methods
Summary
The end
Thanks for your attention!
Related Documents
Spectral Range
June 2020 4
Spectral Methods.pdf
April 2020 3
Hyper Spectral
November 2019 9
Quentin Meillassoux - Spectral Dilemma
July 2020 7
Channel Spectral Characteristics
June 2020 0
Philippines Spectral Map.pdf
May 2020 1More Documents from "Joseph Cloyd Lamberte"
Dicas Sobre Como.docx
April 2020 7