查看“擬譜法”的源代码

{{Refimprove|time=2019-07-17T22:58:53+00:00}}
'''擬譜法'''（Pseudo-spectral methods）<ref>{{cite journal|last1=Orszag|first1=Steven A.|title=Comparison of Pseudospectral and Spectral Approximation|journal=Studies in Applied Mathematics|date=September 1972|volume=51|issue=3|pages=253–259|doi=10.1002/sapm1972513253}}</ref>也稱為'''離散變數表示'''（discrete variable representation、DVR）法，是在[[应用数学]]及[[计算科学]]中求解[[偏微分方程]]用的[[数值分析]]方法。擬譜法和{{link-en|谱方法|spectral method}}有密切關係，但在谱方法中[[基 (線性代數)|基底]]函數中使用了擬譜的基底函數，也就是可以在分割網格上表示的函數。此作法簡化一些運算子的計算，在使用快速演算法（例如[[快速傅里叶变换]]）時可以加速計算速度。

==說明==
考慮以下的初值問題

:<math>i \frac{\partial}{\partial t} \psi(x, t) = \Bigl[-\frac{\partial^2}{\partial x^2} + V(x) \Bigr] \psi(x,t), \qquad\qquad \psi(t_0) = \psi_0</math>

有週期性條件<math>\psi(x+1, t) = \psi(x, t)</math>。這個例子是勢能為<math>V(x)</math>之粒子的[[薛定谔方程]]，不過其結構可適用到其他應用。在許多實務上的偏微分方程中，其中有一項是和導數（例如是動能相關的量）有關，另一項則是和另一個函數（此處為勢能）的乘積。

在譜方法中，其解<math>\psi</math>會展開為一組適合基底函數的組合，例如平面波。

:<math>\psi(x,t) = \frac{1}{\sqrt{2\pi}} \sum_n c_n(t) e^{2\pi i n x} .</math>

將解代入，並且計算係數的方程，可以得到係數的[[常微分方程]]

:<math>i\frac{d}{dt} c_n(t) = (2\pi n)^2 c_n + \sum_k V_{n-k} c_k,</math>

而其元素<math>V_{nk}</math>可以透過顯式的傅立葉轉換求得

:<math>V_{n-k} = \int_0^{1} V(x) \ e^{2\pi i (k-n) x} dx .</math>

若將<math>N</math>基底函數的展開到一定項次後截斷，並且找<math>c_n(t)</math>的解，就可以得到偏微分方程的解。一般而言會用{{link-en|常微分方程的數值方法|Numerical methods for ordinary differential equations|數值方法}}進行，例如[[龙格－库塔法]]。為了數值解，常微分方程的右側需重覆計算在許多不同時間間隔下的值。此時，譜方法有個和勢能項<math>V(x)</math>有關的主要問題。

在譜方法下，和勢能函數<math>V(x)</math>的相乘會轉換為向量和矩陣的乘法，其複雜度是<math>N^2</math>，而且在求解係數的微分方程時，需要另外去計算矩陣元素<math>V_{nk}</math>，這也需要時間。

在擬譜法中，會用不同的方式來計算。給定係數<math>c_n(t)</math>，會用反離散傅立葉轉換來計算函數<math>\psi</math>在離散格點<math>x_j = 2\pi j/N</math>下的值。在格點上，計算函數的乘積 <math>\psi'(x_i, t) = V(x_i) \psi(x_i, t)</math>，再用傅立葉轉換轉換回來，可以得到一組新的係數<math>c'_n(t)</math>，來代替矩陣乘積運算<math>\sum_k V_{n-k} c_k(t)</math>。

可以證明二個方法有類似的精準度，而且擬譜法可以使用快速傅立葉轉換，其時間複雜度為<math>O(N\ln N)</math>，理論上比矩陣乘法要快很多。而且，可以直接計算函數<math>V(x)</math>，不用再經過額外的積分運算。

==技術討論==
若用比較抽象的方式來描述，擬譜法是處理在偏微分方程中二個函數<math>V(x)</math>和<math>f(x)</math>的乘積。為了簡化表示式，省略掉函數中時間的自變數。在概念上，擬譜法包括三個步驟：

# 將<math>f(x)</math>以及<math>\tilde{f}(x) = V(x)f(x)</math>擴展為由有限多個基底函數形成的組合（此為{{link-en|譜方法|spectral method}}）。
# 針對一組給定的基底函數，找到一組分割方式可以將基底函數的純量積轉換為在格點上的加權和。
# 在每一個格點將<math>V</math>和<math>f</math>相乘，來計算函數的乘積。
===基底的展開===
函數<math>f</math>和<math>\tilde f</math>可以用一組有限基底的函數來擴展<math>\{\phi_n\}_{n = 0,\ldots,N}</math>：

:<math>f(x) = \sum_{n=0}^N c_n \phi_n(x)</math>
:<math>\tilde f(x) = \sum_{n=0}^N \tilde c_n \phi_n(x)</math>

為了簡化起見，令基底是正交且正規化的，<math>\langle \phi_n, \phi_m \rangle = \delta_{nm}</math>，利用內積<math>\langle f, g \rangle = \int_a^b f(x) \overline{g(x)} dx</math>配合適當的邊界<math>a,b</math>，其係數為

:<math>c_n = \langle f, \phi_n \rangle</math>
:<math>\tilde c_n = \langle \tilde f, \phi_n \rangle</math>

配合一些計算可得

:<math>\tilde c_n = \sum_{m=0}^N V_{n-m} c_m</math>

而<math>V_{n-m} = \langle V\phi_m, \phi_n \rangle</math>。這是譜方法的基礎。為了區分<math>\phi_n</math>的基底以及正交的基底，有時會將上述擴展稱為有限基底表示（Finite Basis Representation、FBR）。

===分割===
針對給定基底<math>\{\phi_n\}</math>以及<math>N+1</math>個基底函數，可以設法找到分割方式，也就是<math>N+1</math>個點以及加權，使得

:<math>\langle \phi_n, \phi_m \rangle = \sum_{i=0}^N w_i \phi_n(x_i) \overline{\phi_m(x_i)} \qquad\qquad n,m = 0,\ldots,N</math>

特別的例子包括多項式的[[高斯求积]]以及平面波的[[离散傅里叶变换]]，特別需注意的是格點及加權<math>x_i,w_i</math>都是基底及數量<math>N</math>的函數。

利用分割方式，可以透過格點上的值，以另一種方式來表示函數<math>f(x), \tilde f(x)</math>的數值。此表示法有時稱為離散變數表示法（Discrete Variable Representation、DVR），完全等效於基底的展開。

:<math>f(x_i) = \sum_{n=0}^N c_n \phi_n(x_i)</math>
:<math>c_n = \langle f, \phi_n \rangle = \sum_{n=0}^{N} w_i f(x_i) \overline{\phi_n(x_i)}</math>

===相乘===
和函數<math>V(x)</math>的相乘會在格點上進行

:<math>\tilde f(x_i) = V(x_i) f(x_i).</math>

一般來說這裡會有一些近似，可以計算其中一個係數<math>\tilde c_n</math>:

:<math>\tilde c_n = \langle \tilde f, \phi_n \rangle = \sum_i w_i \tilde f(x_i) \overline{\phi_n(x_i)} = \sum_i w_i V(x_i) f(x_i) \overline{\phi_n(x_i)}</math>

利用譜方法，對應的係數會是<math>\tilde c_n = \langle Vf, \phi_n \rangle</math>。擬譜法則會用以下皂的近似來處理

:<math>\langle Vf, \phi_n \rangle \approx \sum_i w_i V(x_i) f(x_i) \overline{\phi_n(x_i)}.</math>

若乘積可以用<math>Vf</math>給定的有限基底函數組合來表現，則上式在給定分割方式上會完全正確。
==特殊的擬譜架構==
===傅立葉法===
若問題中有週期性的邊界條件，其週期為<math>[0,L]</math>，基底函數可以用平面波來產生，

:<math>\phi_n(x) = \frac{1}{\sqrt{L}} e^{-\imath k_n x}</math>

其中<math>k_n = (-1)^n \lceil n/2 \rceil 2\pi/L</math>，而<math>\lceil\cdot\rceil</math>是[[取整函数]]。

在<math>n_{\text{max}} = N</math>處截斷的分割為[[離散傅立葉轉換]]，格點會平均分佈<math>x_i = i \Delta x</math>，間隔為<math>\Delta x = L / (N+1)</math>，各點的加權會是相同旳定值<math>w_i = \Delta x</math>。

在討論誤差時，需注意到平面波的乘積也是平面波，<math>\phi_{a} + \phi_b = \phi_c</math>，<math>c \leq a+b</math>。因此，定量來說，若函數<math>f(x), V(x)</math>可以用<math>N_f, N_V</math>基底函數足夠準確的呈現，只要用<math>N_f + N_V</math>個基底函數，即可用擬譜法得到足夠準確的結果。

平面波的擴展一般效果較差，需要許多的基底函數才能收斂。不過。基底展開和格點表示的轉換可以用[[快速傅立葉轉換]]進行，其時間複雜度較低，為<math>N \ln N</math>。因此，平面波是擬譜法中常用的一種基底函數。

===多項式===
另一種常見的展開方式是多項式，此處會使用[[高斯求积]]（Gaussian quadrature），其中提到可以找到加權係數<math>w_i</math>及格點<math>x_i</math>使得

:<math>\int_a^b w(x) p(x) dx = \sum_{i=0}^N w_i p(x_i)</math>

對任意的<math>2N+1</math>次或是更低次的多項式<math>p(x)</math>都成立。一般而言，加權函數<math>w(x)</math>及範圍<math>a,b</math>都是根據特定問題所選定的，因此會選擇幾種分割方式中的一種。若要用在擬譜法，需選擇基底函數為<math>\phi_n(x) = \sqrt{w(x)} P_n(x)</math>，其中<math>P_n</math>為<math>n</math>階多項式，有以下特性

:<math>\int_a^b w(x) P_n(x) P_m(x) dx = \delta_{mn}.</math>

在上述條件下，the <math>\phi_n</math>會是正交基底，其內積為<math>\langle f, g \rangle = \int_a^b f(x) \overline{g(x)} dx</math>。此基底以及分割點可以用在擬譜法中。

有關其誤差，若<math>f</math>可以用<math>N_f</math>個基底函數很好的呈現，而<math>V</math>可以用<math>N_V</math>階多項式很好的呈現，則其積可以用前<math>N_f+N_V</math>個基底函數很好的呈現。且擬譜法用該數量的基底函數，會有足夠準確的結果。

在一些標準問題中，會出現這些多項式。例如量子簡諧振動子可以擴展為[[埃爾米特多項式]]，而在轉動問題中，會用[[雅可比多項式]]來定義相關的[[勒壤得多項式]]。

==參考資料==
{{Reflist}}
* {{cite journal|last1=Orszag|first1=Steven A.|title=Numerical Methods for the Simulation of Turbulence|journal=Physics of Fluids|date=1969|volume=12|issue=12|pages=II-250|doi=10.1063/1.1692445}}
* {{cite book|last1=Gottlieb|first1=David|last2=Orszag|first2=Steven A.|title=Numerical analysis of spectral methods : theory and applications|date=1989|publisher=Society for Industrial and Applied Mathematics|location=Philadelphia, Pa.|isbn=978-0898710236|edition=5. print.}}
* {{cite book|last1=Hesthaven|first1=Jan S.|last2=Gottlieb|first2=Sigal|last3=Gottlieb|first3=David|title=Spectral methods for time-dependent problems|date=2007|publisher=Cambridge Univ. Press|location=Cambridge [u.a.]|isbn=9780521792110|edition=1. publ.}}
* {{cite book|last1=Trefethen|first1=Lloyd N.|title=Spectral methods in MATLAB|date=2000|publisher=SIAM|location=Philadelphia, Pa|isbn=978-0-89871-465-4|edition=3rd. repr.}}
* {{cite book|last1=Fornberg|first1=Bengt|title=A Practical Guide to Pseudospectral Methods|date=1996|publisher=Cambridge University Press|location=Cambridge|isbn=9780511626357}}
* {{cite book|last1=Boyd|first1=John P.|title=Chebyshev and Fourier spectral methods|date=2001|publisher=Dover Publications|location=Mineola, N.Y.|isbn=978-0486411835|edition=2nd ed., rev.|url=http://www-personal.umich.edu/~jpboyd/BOOK_Spectral2000.html}}
* {{cite book|last1=Funaro|first1=Daniele|title=Polynomial approximation of differential equations|date=1992|publisher=Springer-Verlag|location=Berlin|isbn=978-3-540-46783-0|url=http://cdm.unimo.it/home/matematica/funaro.daniele/bube.htm}}
* {{cite journal|last1=de Frutos|first1=Javier|last2=Novo|first2=Julia|title=A Spectral Element Method for the Navier--Stokes Equations with Improved Accuracy|journal=SIAM Journal on Numerical Analysis|date=January 2000|volume=38|issue=3|pages=799–819|doi=10.1137/S0036142999351984}}
* {{cite book|last1=Claudio|first1=Canuto|last2=M. Yousuff|first2=Hussaini|last3=Alfio|first3=Quarteroni|last4=Thomas A.|first4=Zang|title=Spectral methods fundamentals in single domains|date=2006|publisher=Springer-Verlag|location=Berlin|isbn=978-3-540-30726-6}}
*{{Cite book | last1=Press | first1=WH | last2=Teukolsky | first2=SA | last3=Vetterling | first3=WT | last4=Flannery | first4=BP | year=2007 | title=Numerical Recipes: The Art of Scientific Computing | edition=3rd | publisher=Cambridge University Press |  publication-place=New York | isbn=978-0-521-88068-8 | chapter=Section 20.7. Spectral Methods | chapter-url=http://apps.nrbook.com/empanel/index.html#pg=1083}}

{{DEFAULTSORT:Pseudo-Spectral Method}}
{{数值偏微分方程}}
[[Category:数值分析]]