Namespaces
Variants
Actions

Difference between revisions of "Chebyshev pseudo-spectral method"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (AUTOMATIC EDIT (latexlist): Replaced 38 formulas out of 39 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
Line 1: Line 1:
 +
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
 +
 +
Out of 39 formulas, 38 were replaced by TEX code.-->
 +
 +
{{TEX|semi-auto}}{{TEX|partial}}
 
A type of trigonometric pseudo-spectral method (cf. [[Trigonometric pseudo-spectral methods|Trigonometric pseudo-spectral methods]]). See also [[Fourier pseudo-spectral method|Fourier pseudo-spectral method]].
 
A type of trigonometric pseudo-spectral method (cf. [[Trigonometric pseudo-spectral methods|Trigonometric pseudo-spectral methods]]). See also [[Fourier pseudo-spectral method|Fourier pseudo-spectral method]].
  
A Chebyshev polynomial is defined as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c1300901.png" /> (cf. also [[Chebyshev polynomials|Chebyshev polynomials]]). If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c1300902.png" />, the resulting Chebyshev function is truly an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c1300903.png" />th order [[Polynomial|polynomial]] in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c1300904.png" />, but it is also a cosine function with a change of variable. Thus, a finite Chebyshev series expansion is related to a discrete cosine transform.
+
A Chebyshev polynomial is defined as $T _ { n } ( x ) = \operatorname { cos } ( n \operatorname { cos } ^ { - 1 } x )$ (cf. also [[Chebyshev polynomials|Chebyshev polynomials]]). If $x = \operatorname { cos } \theta$, the resulting Chebyshev function is truly an $n$th order [[Polynomial|polynomial]] in $x$, but it is also a cosine function with a change of variable. Thus, a finite Chebyshev series expansion is related to a discrete cosine transform.
  
 
The Chebyshev pseudo-spectral method is the most logical choice of pseudo-spectral methods for problems with non-periodic boundary conditions. This comes from the particularly nice characteristics of the Chebyshev interpolating polynomials (cf. also [[Chebyshev polynomials|Chebyshev polynomials]]).
 
The Chebyshev pseudo-spectral method is the most logical choice of pseudo-spectral methods for problems with non-periodic boundary conditions. This comes from the particularly nice characteristics of the Chebyshev interpolating polynomials (cf. also [[Chebyshev polynomials|Chebyshev polynomials]]).
  
Of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c1300905.png" />st degree polynomials, with leading coefficient <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c1300906.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c1300907.png" /> has the smallest maximum on the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c1300908.png" />. Thus, in Lagrangian interpolation (see also [[Lagrange interpolation formula|Lagrange interpolation formula]]), if the interpolation points are taken to be the zeros of this polynomial, the error is minimized. A related and possibly more useful set of interpolation points are the extrema of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c1300909.png" />: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009010.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009011.png" />, called the Gauss–Lobatto points.
+
Of all $( N + 1 )$st degree polynomials, with leading coefficient $1$, $T _ { N + 1 } / 2 ^ { N }$ has the smallest maximum on the interval $[ - 1,1 ]$. Thus, in Lagrangian interpolation (see also [[Lagrange interpolation formula|Lagrange interpolation formula]]), if the interpolation points are taken to be the zeros of this polynomial, the error is minimized. A related and possibly more useful set of interpolation points are the extrema of $T _ { N } ( x )$: $x _ { j } = \operatorname { cos } ( \pi j / N )$, $j = 0 , \dots , N$, called the Gauss–Lobatto points.
  
The trigonometric interpolation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009012.png" /> of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009013.png" /> at the Gauss–Lobatto points is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009014.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009015.png" /> is the Cardinal function
+
The trigonometric interpolation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009012.png"/> of the function $u$ at the Gauss–Lobatto points is $P _ { N } u = \sum _ { j = 0 } ^ { N } u ( x _ { j } ) C _ { j } ( x )$, where $C_{j}$ is the Cardinal function
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009016.png" /></td> </tr></table>
+
\begin{equation*} C _ { j } = ( 1 - x ^ { 2 } ) \frac { T _ { N } ^ { \prime } ( x ) ( - 1 ) ^ { j + 1 } } { [ \bar{c} _ { j } N ^ { 2 } ( x - x _ { j } ) ] }, \end{equation*}
  
with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009017.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009018.png" /> otherwise. Rearranging, the interpolation polynomial becomes a finite Chebyshev series <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009019.png" />, where the Chebyshev coefficients are
+
with $\overline { c }_ 0 = \overline { c } _ { N } = 2$, $\overline{ c }_{j}  = 1$ otherwise. Rearranging, the interpolation polynomial becomes a finite Chebyshev series $P _ { N } u ( x ) = \sum _ { n = 0 } ^ { N } a _ { n } T _ { n } ( x )$, where the Chebyshev coefficients are
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009020.png" /></td> </tr></table>
+
\begin{equation*} a _ { n } = \frac { 2 } { N } \frac { 1 } { \overline { c } _ { n } } \sum _ { j = 0 } ^ { N } u ( x _ { j } ) \frac { T _ { n } ( x _ { j } ) } { \overline { c } _ { j } }. \end{equation*}
  
Suppose the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009021.png" /> is to be solved, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009022.png" /> is a differential operator, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009023.png" /> is a given function and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009024.png" /> is an unknown function. In the Chebyshev pseudo-spectral method, the solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009025.png" /> is approximated by a Chebyshev interpolating polynomial. In the Lagrangian polynomial or  "grid-point representation" , the problem can be written as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009026.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009027.png" />. The form of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009028.png" /> can be found through differentiation of the Cardinal function: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009029.png" />,
+
Suppose the equation $L u = f$ is to be solved, where $L$ is a differential operator, $f$ is a given function and $u$ is an unknown function. In the Chebyshev pseudo-spectral method, the solution $u$ is approximated by a Chebyshev interpolating polynomial. In the Lagrangian polynomial or  "grid-point representation" , the problem can be written as $L _ { i , j } u _ { j } = f _ { i }$, where $L _ { i ,\, j } = L C _ { j } ( x ) |_ { x = x _ { i } }$. The form of $L_{i ,\, j}$ can be found through differentiation of the Cardinal function: $C _ { j } ( x _ { i } ) = \delta _ { i , j }$,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009030.png" /></td> </tr></table>
+
\begin{equation*} \frac { d C _ { j } } { d x } ( x _ { k } ) = \left\{ \begin{array} { l l } { \frac { 1 } { 6 } ( 1 + 2 N ^ { 2 } ) } &amp; { \text { for } j = k = 0 ,} \\ { - \frac { 1 } { 6 } ( 1 + 2 N ^ { 2 } ) } &amp; { \text { for } j = k = N, } \\ { - \frac { x _ { j } } { 2 ( 1 - x _ { j } ^ { 2 } ) } } &amp; { \text { for } j = k , 0 &lt; j &lt; N ,} \\ { ( - 1 ) ^ { j + k } \frac { \bar{c} _ { k } } { \bar{c} _ { j } ( x _ { k } - x _ { j } ) } } &amp; { \text { for } j \neq k, } \end{array} \right. \end{equation*}
  
and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009031.png" />. Note that derivatives require <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009032.png" /> operations.
+
and $( d ^ { k } C _ { j } / d x ^ { k } ) ( x _ { i } ) = [ ( d C _ { j } / d x ) ( x _ { i } ) ] ^ { k }$. Note that derivatives require $O ( N ^ { 2 } )$ operations.
  
Another way to find an expression for the derivative is to differentiate the Chebyshev series, which means differentiating the Chebyshev polynomials and using the recurrence relation for derivatives of Chebyshev polynomials, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009033.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009034.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009035.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009036.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009037.png" />. Thus, in coefficient representation, the derivative can be evaluated in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009038.png" /> operations while non-linear terms or multiplication by non-constant coefficients require <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130090/c13009039.png" />. The fast discrete cosine transform can be used to switch between spectral and grid point representations.
+
Another way to find an expression for the derivative is to differentiate the Chebyshev series, which means differentiating the Chebyshev polynomials and using the recurrence relation for derivatives of Chebyshev polynomials, $d ( P _ { N } u ) / d x = \sum _ { n = 0 } ^ { N } b _ { n } T _ { N } ( x )$, where $b _ { N } = 0$, $b _ { N - 1 } = 2 N a _ { N }$, $\overline{c} _ { n } b _ { n } = b _ { n + 2 } + 2 ( n + 1 ) a _ { n + 1 }$ for $0 \leq n &lt; N - 1$. Thus, in coefficient representation, the derivative can be evaluated in $O ( N )$ operations while non-linear terms or multiplication by non-constant coefficients require $O ( N ^ { 2 } )$. The fast discrete cosine transform can be used to switch between spectral and grid point representations.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.P. Boyd,  "Chebyshev and Fourier spectral methods" , Dover  (2000)  (pdf version: http://www-personal.engin.umich.edu/~jpboyd/book_spectral2000.html)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  D. Gottlieb,  S.A. Orszag,  "Numerical analysis of spectral methods: Theory and applications" , SIAM  (1977)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  C. Canuto,  M.Y. Hussaini,  A. Quarteroni,  T.A. Zang,  "Spectral methods in fluid dynamics" , Springer  (1987)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D. Gottlieb,  M.Y. Hussaini,  S.A. Orszag,  "Theory and application of spectral methods"  R.G. Voigt (ed.)  D. Gottlieb (ed.)  M.Y. Hussaini (ed.) , ''Spectral Methods for Partial Differential Equations'' , SIAM  (1984)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  B. Fornberg,  "A practical guide to pseudospectral methods" , ''Cambridge Monographs Appl. Comput. Math.'' , '''1''' , Cambridge Univ. Press  (1996)</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  J.P. Boyd,  "Chebyshev and Fourier spectral methods" , Dover  (2000)  (pdf version: http://www-personal.engin.umich.edu/~jpboyd/book_spectral2000.html)</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  D. Gottlieb,  S.A. Orszag,  "Numerical analysis of spectral methods: Theory and applications" , SIAM  (1977)</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  C. Canuto,  M.Y. Hussaini,  A. Quarteroni,  T.A. Zang,  "Spectral methods in fluid dynamics" , Springer  (1987)</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  D. Gottlieb,  M.Y. Hussaini,  S.A. Orszag,  "Theory and application of spectral methods"  R.G. Voigt (ed.)  D. Gottlieb (ed.)  M.Y. Hussaini (ed.) , ''Spectral Methods for Partial Differential Equations'' , SIAM  (1984)</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  B. Fornberg,  "A practical guide to pseudospectral methods" , ''Cambridge Monographs Appl. Comput. Math.'' , '''1''' , Cambridge Univ. Press  (1996)</td></tr></table>

Revision as of 16:59, 1 July 2020

A type of trigonometric pseudo-spectral method (cf. Trigonometric pseudo-spectral methods). See also Fourier pseudo-spectral method.

A Chebyshev polynomial is defined as $T _ { n } ( x ) = \operatorname { cos } ( n \operatorname { cos } ^ { - 1 } x )$ (cf. also Chebyshev polynomials). If $x = \operatorname { cos } \theta$, the resulting Chebyshev function is truly an $n$th order polynomial in $x$, but it is also a cosine function with a change of variable. Thus, a finite Chebyshev series expansion is related to a discrete cosine transform.

The Chebyshev pseudo-spectral method is the most logical choice of pseudo-spectral methods for problems with non-periodic boundary conditions. This comes from the particularly nice characteristics of the Chebyshev interpolating polynomials (cf. also Chebyshev polynomials).

Of all $( N + 1 )$st degree polynomials, with leading coefficient $1$, $T _ { N + 1 } / 2 ^ { N }$ has the smallest maximum on the interval $[ - 1,1 ]$. Thus, in Lagrangian interpolation (see also Lagrange interpolation formula), if the interpolation points are taken to be the zeros of this polynomial, the error is minimized. A related and possibly more useful set of interpolation points are the extrema of $T _ { N } ( x )$: $x _ { j } = \operatorname { cos } ( \pi j / N )$, $j = 0 , \dots , N$, called the Gauss–Lobatto points.

The trigonometric interpolation of the function $u$ at the Gauss–Lobatto points is $P _ { N } u = \sum _ { j = 0 } ^ { N } u ( x _ { j } ) C _ { j } ( x )$, where $C_{j}$ is the Cardinal function

\begin{equation*} C _ { j } = ( 1 - x ^ { 2 } ) \frac { T _ { N } ^ { \prime } ( x ) ( - 1 ) ^ { j + 1 } } { [ \bar{c} _ { j } N ^ { 2 } ( x - x _ { j } ) ] }, \end{equation*}

with $\overline { c }_ 0 = \overline { c } _ { N } = 2$, $\overline{ c }_{j} = 1$ otherwise. Rearranging, the interpolation polynomial becomes a finite Chebyshev series $P _ { N } u ( x ) = \sum _ { n = 0 } ^ { N } a _ { n } T _ { n } ( x )$, where the Chebyshev coefficients are

\begin{equation*} a _ { n } = \frac { 2 } { N } \frac { 1 } { \overline { c } _ { n } } \sum _ { j = 0 } ^ { N } u ( x _ { j } ) \frac { T _ { n } ( x _ { j } ) } { \overline { c } _ { j } }. \end{equation*}

Suppose the equation $L u = f$ is to be solved, where $L$ is a differential operator, $f$ is a given function and $u$ is an unknown function. In the Chebyshev pseudo-spectral method, the solution $u$ is approximated by a Chebyshev interpolating polynomial. In the Lagrangian polynomial or "grid-point representation" , the problem can be written as $L _ { i , j } u _ { j } = f _ { i }$, where $L _ { i ,\, j } = L C _ { j } ( x ) |_ { x = x _ { i } }$. The form of $L_{i ,\, j}$ can be found through differentiation of the Cardinal function: $C _ { j } ( x _ { i } ) = \delta _ { i , j }$,

\begin{equation*} \frac { d C _ { j } } { d x } ( x _ { k } ) = \left\{ \begin{array} { l l } { \frac { 1 } { 6 } ( 1 + 2 N ^ { 2 } ) } & { \text { for } j = k = 0 ,} \\ { - \frac { 1 } { 6 } ( 1 + 2 N ^ { 2 } ) } & { \text { for } j = k = N, } \\ { - \frac { x _ { j } } { 2 ( 1 - x _ { j } ^ { 2 } ) } } & { \text { for } j = k , 0 < j < N ,} \\ { ( - 1 ) ^ { j + k } \frac { \bar{c} _ { k } } { \bar{c} _ { j } ( x _ { k } - x _ { j } ) } } & { \text { for } j \neq k, } \end{array} \right. \end{equation*}

and $( d ^ { k } C _ { j } / d x ^ { k } ) ( x _ { i } ) = [ ( d C _ { j } / d x ) ( x _ { i } ) ] ^ { k }$. Note that derivatives require $O ( N ^ { 2 } )$ operations.

Another way to find an expression for the derivative is to differentiate the Chebyshev series, which means differentiating the Chebyshev polynomials and using the recurrence relation for derivatives of Chebyshev polynomials, $d ( P _ { N } u ) / d x = \sum _ { n = 0 } ^ { N } b _ { n } T _ { N } ( x )$, where $b _ { N } = 0$, $b _ { N - 1 } = 2 N a _ { N }$, $\overline{c} _ { n } b _ { n } = b _ { n + 2 } + 2 ( n + 1 ) a _ { n + 1 }$ for $0 \leq n < N - 1$. Thus, in coefficient representation, the derivative can be evaluated in $O ( N )$ operations while non-linear terms or multiplication by non-constant coefficients require $O ( N ^ { 2 } )$. The fast discrete cosine transform can be used to switch between spectral and grid point representations.

References

[a1] J.P. Boyd, "Chebyshev and Fourier spectral methods" , Dover (2000) (pdf version: http://www-personal.engin.umich.edu/~jpboyd/book_spectral2000.html)
[a2] D. Gottlieb, S.A. Orszag, "Numerical analysis of spectral methods: Theory and applications" , SIAM (1977)
[a3] C. Canuto, M.Y. Hussaini, A. Quarteroni, T.A. Zang, "Spectral methods in fluid dynamics" , Springer (1987)
[a4] D. Gottlieb, M.Y. Hussaini, S.A. Orszag, "Theory and application of spectral methods" R.G. Voigt (ed.) D. Gottlieb (ed.) M.Y. Hussaini (ed.) , Spectral Methods for Partial Differential Equations , SIAM (1984)
[a5] B. Fornberg, "A practical guide to pseudospectral methods" , Cambridge Monographs Appl. Comput. Math. , 1 , Cambridge Univ. Press (1996)
How to Cite This Entry:
Chebyshev pseudo-spectral method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Chebyshev_pseudo-spectral_method&oldid=50326
This article was adapted from an original article by Richard B. Pelz (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article