\documentclass[12pt,titlepage]{article} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} \usepackage{mathtools} \usepackage{graphicx} \usepackage{color} \usepackage{ucs} \usepackage[utf8x]{inputenc} \usepackage{xparse} \usepackage{hyperref} %----Macros---------- % % Unresolved issues: % % \righttoleftarrow % \lefttorightarrow % % \color{} with HTML colorspec % \bgcolor % \array with options (without options, it's equivalent to the matrix environment) % Of the standard HTML named colors, white, black, red, green, blue and yellow % are predefined in the color package. Here are the rest. \definecolor{aqua}{rgb}{0, 1.0, 1.0} \definecolor{fuschia}{rgb}{1.0, 0, 1.0} \definecolor{gray}{rgb}{0.502, 0.502, 0.502} \definecolor{lime}{rgb}{0, 1.0, 0} \definecolor{maroon}{rgb}{0.502, 0, 0} \definecolor{navy}{rgb}{0, 0, 0.502} \definecolor{olive}{rgb}{0.502, 0.502, 0} \definecolor{purple}{rgb}{0.502, 0, 0.502} \definecolor{silver}{rgb}{0.753, 0.753, 0.753} \definecolor{teal}{rgb}{0, 0.502, 0.502} % Because of conflicts, \space and \mathop are converted to % \itexspace and \operatorname during preprocessing. % itex: \space{ht}{dp}{wd} % % Height and baseline depth measurements are in units of tenths of an ex while % the width is measured in tenths of an em. \makeatletter \newdimen\itex@wd% \newdimen\itex@dp% \newdimen\itex@thd% \def\itexspace#1#2#3{\itex@wd=#3em% \itex@wd=0.1\itex@wd% \itex@dp=#2ex% \itex@dp=0.1\itex@dp% \itex@thd=#1ex% \itex@thd=0.1\itex@thd% \advance\itex@thd\the\itex@dp% \makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}} \makeatother % \tensor and \multiscript \makeatletter \newif\if@sup \newtoks\@sups \def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}% \def\reset@sup{\@supfalse\@sups={}}% \def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else% \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}% \else \append@sup#2 \@suptrue \fi% \expandafter\mk@scripts\fi} \def\tensor#1#2{\reset@sup#1\mk@scripts#2_/} \def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2% \reset@sup\mk@scripts#3_/} \makeatother % \slash \makeatletter \newbox\slashbox \setbox\slashbox=\hbox{$/$} \def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$} \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa \copy\slashbox \kern-\@tempdima \box\@tempboxa} \def\slash{\protect\itex@pslash} \makeatother % math-mode versions of \rlap, etc % from Alexander Perlis, "A complement to \smash, \llap, and lap" % http://math.arizona.edu/~aprl/publications/mathclap/ \def\clap#1{\hbox to 0pt{\hss#1\hss}} \def\mathllap{\mathpalette\mathllapinternal} \def\mathrlap{\mathpalette\mathrlapinternal} \def\mathclap{\mathpalette\mathclapinternal} \def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}} \def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}} \def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}} % Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2} \let\oldroot\root \def\root#1#2{\oldroot #1 \of{#2}} \renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}} % Manually declare the txfonts symbolsC font \DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n} \SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n} \DeclareFontSubstitution{U}{txsyc}{m}{n} % Manually declare the stmaryrd font \DeclareSymbolFont{stmry}{U}{stmry}{m}{n} \SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n} % Manually declare the MnSymbolE font \DeclareFontFamily{OMX}{MnSymbolE}{} \DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n} \SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n} \DeclareFontShape{OMX}{MnSymbolE}{m}{n}{ <-6> MnSymbolE5 <6-7> MnSymbolE6 <7-8> MnSymbolE7 <8-9> MnSymbolE8 <9-10> MnSymbolE9 <10-12> MnSymbolE10 <12-> MnSymbolE12}{} % Declare specific arrows from txfonts without loading the full package \makeatletter \def\re@DeclareMathSymbol#1#2#3#4{% \let#1=\undefined \DeclareMathSymbol{#1}{#2}{#3}{#4}} \re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46} \re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12} \re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64} \re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6} \re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77} \re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77} \makeatother % \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE \makeatletter \def\Decl@Mn@Delim#1#2#3#4{% \if\relax\noexpand#1% \let#1\undefined \fi \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}} \def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}} \def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}} \Decl@Mn@Open{\llangle}{mnomx}{'164} \Decl@Mn@Close{\rrangle}{mnomx}{'171} \Decl@Mn@Open{\lmoustache}{mnomx}{'245} \Decl@Mn@Close{\rmoustache}{mnomx}{'244} \makeatother % Widecheck \makeatletter \DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}} \def\@widecheck#1#2{% \setbox\z@\hbox{\m@th$#1#2$}% \setbox\tw@\hbox{\m@th$#1% \widehat{% \vrule\@width\z@\@height\ht\z@ \vrule\@height\z@\@width\wd\z@}$}% \dp\tw@-\ht\z@ \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@ \setbox\tw@\hbox{% \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box \tw@}}}% {\ooalign{\box\tw@ \cr \box\z@}}} \makeatother % \mathraisebox{voffset}[height][depth]{something} \makeatletter \NewDocumentCommand\mathraisebox{moom}{% \IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{% \IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}% }{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}% \mathpalette\@temp{#4}} \makeatletter % udots (taken from yhmath) \makeatletter \def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.} \mkern2mu\raise4\p@\hbox{.}\mkern1mu \raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}} \makeatother %% Fix array \newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}} %% \itexnum is a noop \newcommand{\itexnum}[1]{#1} %% Renaming existing commands \newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}} \newcommand{\widevec}{\overrightarrow} \newcommand{\darr}{\downarrow} \newcommand{\nearr}{\nearrow} \newcommand{\nwarr}{\nwarrow} \newcommand{\searr}{\searrow} \newcommand{\swarr}{\swarrow} \newcommand{\curvearrowbotright}{\curvearrowright} \newcommand{\uparr}{\uparrow} \newcommand{\downuparrow}{\updownarrow} \newcommand{\duparr}{\updownarrow} \newcommand{\updarr}{\updownarrow} \newcommand{\gt}{>} \newcommand{\lt}{<} \newcommand{\map}{\mapsto} \newcommand{\embedsin}{\hookrightarrow} \newcommand{\Alpha}{A} \newcommand{\Beta}{B} \newcommand{\Zeta}{Z} \newcommand{\Eta}{H} \newcommand{\Iota}{I} \newcommand{\Kappa}{K} \newcommand{\Mu}{M} \newcommand{\Nu}{N} \newcommand{\Rho}{P} \newcommand{\Tau}{T} \newcommand{\Upsi}{\Upsilon} \newcommand{\omicron}{o} \newcommand{\lang}{\langle} \newcommand{\rang}{\rangle} \newcommand{\Union}{\bigcup} \newcommand{\Intersection}{\bigcap} \newcommand{\Oplus}{\bigoplus} \newcommand{\Otimes}{\bigotimes} \newcommand{\Wedge}{\bigwedge} \newcommand{\Vee}{\bigvee} \newcommand{\coproduct}{\coprod} \newcommand{\product}{\prod} \newcommand{\closure}{\overline} \newcommand{\integral}{\int} \newcommand{\doubleintegral}{\iint} \newcommand{\tripleintegral}{\iiint} \newcommand{\quadrupleintegral}{\iiiint} \newcommand{\conint}{\oint} \newcommand{\contourintegral}{\oint} \newcommand{\infinity}{\infty} \newcommand{\bottom}{\bot} \newcommand{\minusb}{\boxminus} \newcommand{\plusb}{\boxplus} \newcommand{\timesb}{\boxtimes} \newcommand{\intersection}{\cap} \newcommand{\union}{\cup} \newcommand{\Del}{\nabla} \newcommand{\odash}{\circleddash} \newcommand{\negspace}{\!} \newcommand{\widebar}{\overline} \newcommand{\textsize}{\normalsize} \renewcommand{\scriptsize}{\scriptstyle} \newcommand{\scriptscriptsize}{\scriptscriptstyle} \newcommand{\mathfr}{\mathfrak} \newcommand{\statusline}[2]{#2} \newcommand{\tooltip}[2]{#2} \newcommand{\toggle}[2]{#2} % Theorem Environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{prop}{Proposition} \newtheorem{cor}{Corollary} \newtheorem*{utheorem}{Theorem} \newtheorem*{ulemma}{Lemma} \newtheorem*{uprop}{Proposition} \newtheorem*{ucor}{Corollary} \theoremstyle{definition} \newtheorem{defn}{Definition} \newtheorem{example}{Example} \newtheorem*{udefn}{Definition} \newtheorem*{uexample}{Example} \theoremstyle{remark} \newtheorem{remark}{Remark} \newtheorem{note}{Note} \newtheorem*{uremark}{Remark} \newtheorem*{unote}{Note} %------------------------------------------------------------------- \begin{document} %------------------------------------------------------------------- \section*{Spectral methods for PDEs} [[!redirects Spectral methods]] [[!redirects Spectral methods]] [[!redirects spectral methods]] \hypertarget{contents}{}\section*{{Contents}}\label{contents} \noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak \noindent\hyperlink{details}{Details}\dotfill \pageref*{details} \linebreak \noindent\hyperlink{introduction_for_pure_functional_analysts}{Introduction for Pure Functional Analysts}\dotfill \pageref*{introduction_for_pure_functional_analysts} \linebreak \noindent\hyperlink{approximation_with_orthonormal_functions_in_hilbert_space}{Approximation with Orthonormal Functions in Hilbert Space}\dotfill \pageref*{approximation_with_orthonormal_functions_in_hilbert_space} \linebreak \noindent\hyperlink{difference_of_spectral_and_finite_element_methods}{Difference of Spectral and Finite Element Methods}\dotfill \pageref*{difference_of_spectral_and_finite_element_methods} \linebreak \noindent\hyperlink{choice_of_basis_functions}{Choice of Basis Functions}\dotfill \pageref*{choice_of_basis_functions} \linebreak \noindent\hyperlink{examples}{Examples}\dotfill \pageref*{examples} \linebreak \noindent\hyperlink{one_dimensional_boundary_problem}{One Dimensional Boundary Problem}\dotfill \pageref*{one_dimensional_boundary_problem} \linebreak \noindent\hyperlink{burgers_equation}{Burgers' Equation}\dotfill \pageref*{burgers_equation} \linebreak \noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak \hypertarget{idea}{}\subsection*{{Idea}}\label{idea} \textbf{Spectral methods} are [[discrete approximation schemes]] for [[partial differential equations]]. They are important for the solution of the [[Navier-Stokes equations]] in [[meteorology]] and in [[climate models]]. The basic idea of spectral methods is to choose a finite set of functions and calculate the optimal approximation of the exact solution by these functions. These basis functions are often part of an orthonormal basis of a Hilbert space, and more specifically trigonometric functions, hence the name ``spectral'' methods. In contrast to [[finite elements]], spectral methods usually refer to an approximation with basis functions that don't have a restricted support, but are ``globally nontrivial''. For parabolic equations with a notion of time, spectral methods are usually used to discretize the spatial dimensions only, not the time dimension. \hypertarget{details}{}\subsection*{{Details}}\label{details} \hypertarget{introduction_for_pure_functional_analysts}{}\subsubsection*{{Introduction for Pure Functional Analysts}}\label{introduction_for_pure_functional_analysts} The following paragraph is meant as an introduction to the method for pure mathematicians with a background in functional analysis. For illustrative purposes we will make some simplifying assumptions. Let's assume that we have an infinite topological vector space T, its topological dual $T^*$ and a (closable densely defined differential) operator \begin{displaymath} A: D \subset T \to T \end{displaymath} with a unique solution of the equation \begin{displaymath} A(f) = 0 \end{displaymath} We omit initial and boundary conditions for the moment. In order to calculate an approximation to the exact solution $f$, we need to turn the infinite dimensional problem to a finite dimensional one. The basic idea of spectral methods is to choose a finite dimensional subspace $T_g$ of T spanned by a given set of functions $\{g_1, ..., g_n \}$, which are called in this context \textbf{trial, expansion or approximation functions}. We are looking for the projection of the exact solution $f$ to the subspace $T_g$, but since we don't know $f$, we cannot calculate the exact expansion \begin{displaymath} f = \sum_{k = 1}^n \alpha_k g_k \end{displaymath} But we can test the goodness of a given approximation $f_{\alpha} := \sum_{k = 1}^n \alpha_k g_k$ by testing $M(f_{\alpha})$ for ``smallness''. This function is sometimes called the \textbf{residual function}. Different spectral methods differ mainly in their interpretation of ``smallness'' and their strategy to determine the best approximation. One particular ``smallness'' test in spectral methods is done via a choice of a finite dimensional subspace $T^*_h$ of the dual space $T^*$ spanned by the elements $\{h_1, ..., h_n \}$, we then demand that \begin{displaymath} \langle \; M(f_{\alpha}), \; h_i \; \rangle = 0 \end{displaymath} should hold for all $h_i \in T^*_h$. The ``functions'' $h_i$ are called \textbf{test or weight functions}. Due to the choice of finite dimensional subspaces the problem is reduced to a finite set of (linear) algebraic equations. \hypertarget{approximation_with_orthonormal_functions_in_hilbert_space}{}\subsubsection*{{Approximation with Orthonormal Functions in Hilbert Space}}\label{approximation_with_orthonormal_functions_in_hilbert_space} Often the function space is a \href{http://en.wikipedia.org/wiki/Hilbert_space}{Hilbert space} and the approximation functions elements of an orthonormal base. This is the case for example if one uses [[Fourier series]]. In some cases it is possible to show that the expansion coefficients of, for example, a smooth function in an orthonormal basis decay exponentially fast. This is sometimes called \textbf{exponential} or \textbf{spectral accuracy} in the literature. \hypertarget{difference_of_spectral_and_finite_element_methods}{}\subsubsection*{{Difference of Spectral and Finite Element Methods}}\label{difference_of_spectral_and_finite_element_methods} The only difference of spectral and [[finite element]] methods is that spectral methods use approximation functions that are not local, while finite elements uses approximation functions with support restricted to certain simple subsets of the domain of the equation one would like to solve. As a consequence, finite elements can only handle bounded domains. It is possible to combine both approaches and get, for example, the \href{http://en.wikipedia.org/wiki/Hp-FEM}{hp-FEM}. \hypertarget{choice_of_basis_functions}{}\subsubsection*{{Choice of Basis Functions}}\label{choice_of_basis_functions} Basis functions should be easy to evaluate, both numerically or with pen-and-paper if a step of the overall calculation can and should be performed by hand. Basis functions should be complete in the sense that the approximation gets ``arbitrarily good'' with increasing number of approximation functions. To make the latter precise, one needs a measure of closeness which will usually be a norm of a Banach space of functions $\| \cdot \|$. Then we would like to have a relation like \begin{displaymath} \lim_{n \to \infty} \| u - u_n \| = 0 \end{displaymath} where $n$ is the number of approximation functions (or, to be more precise, the dimension of the subspace of the topological vector space spanned by the approximation functions). For practical problems, it would be nice to know that the approximation converges with a certain rate, that it is exponential, for example: \begin{displaymath} \| u - u_n \| = O(\exp(-n)) \end{displaymath} With regard to boundary conditions, there are two possibilites: \begin{itemize}% \item One can choose approximation functions that fulfill the boundary conditions element-wise, \item one imposes additional constraints on the approximation such that the approximation will fulfill the boundary conditions, even though the approximation functions do not. \end{itemize} The most commonly used approximation functions are \begin{itemize}% \item trigonometric functions (i.e. [[Fourier series]]), \item [[Chebyshev polynomials]] \end{itemize} \hypertarget{examples}{}\subsection*{{Examples}}\label{examples} \hypertarget{one_dimensional_boundary_problem}{}\subsubsection*{{One Dimensional Boundary Problem}}\label{one_dimensional_boundary_problem} We will have a look at an ordinary differential equation on the interval $[-1, 1]$ with boundary conditions: \begin{displaymath} u_{xx} - (x^6 + 3 x^2) u = 0 \end{displaymath} where we have written $u_{xx}$ for $\frac{d^2 u}{d x^2}$. The boundary conditions are: \begin{displaymath} u(-1) = u(1) = 0 \end{displaymath} This problem has an exact solution which is: \begin{displaymath} u(x) = \exp{(\frac{1}{4} (x^4 - 1))} \end{displaymath} The first step to calculate an approximate solution using the spectral method is to choose the approximation functions, in this example we choose the polynomials $1, x, x^2$. With this choice, the approximation functions themselves don't satisfy the boundary conditions, therefore we make another choice and choose as approximation \begin{displaymath} u_a := 1 + (1 - x^2) (a_0 + a_1 x + a_2 x^2) \end{displaymath} This way, the boundary conditions are satisfied independently of the approximation coefficients $a_0, a_1, a_2$. The residual function is of course \begin{displaymath} R(a_0, a_1, a_3; x) = \frac{d^2 u_a}{d x^2} - (x^6 + 3 x^2) u_a \end{displaymath} We choose as test functions three Dirac delta functions, which is equivalent to choosing three points $(x_0, x_1, x_2)$ such that the residual function vanishes at these points. This choice has its own name, it is called the \textbf{collocation} or \textbf{pseudospectral method}. Choosing as collocation points the tuple $(- \frac{1}{2}, 0, \frac{1}{2})$ leads to a system of three linear equations for the approximation coefficients, with the solution: \begin{displaymath} a_0 = a_2 = - \frac{784}{3807} \; \text{and} \; a_1 = 0 \end{displaymath} The resulting approximation may seem to be crude at first sight, but the following graphic shows that it is actually quite close to the exact solution already: [[example\_1.png:pic]] The choice of the approximation functions and of the test functions are completely arbitrary, so the follow-up question to this example is if there is any way to determine what a good choice would be. We could have known that $a_2$ would turn out to be zero, for example, because the problem is symmetric with respect to reflection along the y-axis. Without using this knowledge, we spent some computational effort to determine $a_2$, which did not help in making the approximation any better. \hypertarget{burgers_equation}{}\subsubsection*{{Burgers' Equation}}\label{burgers_equation} More examples can be found on the page [[Burgers' equation]]. \hypertarget{references}{}\subsection*{{References}}\label{references} \begin{itemize}% \item \href{http://en.wikipedia.org/wiki/Spectral_methods}{Spectral methods}, Wikipedia \end{itemize} A two volume introduction to the theory of the method, starting with the basics: \begin{itemize}% \item Claudio Canuto, M. Yousuff Hussaini, Alfio Quarteroni, Thomas A. Zang: \emph{Spectral methods. Fundamentals in single domains.} (Springer 2006, \href{http://www.zentralblatt-math.org/zmath/en/advanced/?q=an:1093.76002&format=complete}{ZMATH}) \end{itemize} \ldots{} and continuing with the explanation of how complex boundary conditions should be handled, with applications to [[CFD]]: \begin{itemize}% \item Claudio Canuto, M. Yousuff Hussaini, Alfio Quarteroni, Thomas A. Zang: \emph{Spectral methods. Evolution to complex geometries and applications to fluid dynamics.} (Springer 2007, \href{http://www.zentralblatt-math.org/zmath/en/advanced/?q=an:1121.76001&format=complete}{ZMATH}) \end{itemize} Based on the preceding introduction to the theory, the following volume concentrated on the task of implementing concrete algorithms: \begin{itemize}% \item David A. Kopriva: \emph{Implementing spectral methods for partial differential equations. Algorithms for scientists and engineers.} (Springer 2009, \href{http://www.zentralblatt-math.org/zmath/en/advanced/?q=an:1172.65001&format=complete}{ZMATH}) \end{itemize} An elementary introduction with special emphasis on spherical coordinates (important for [[GCM]]s): \begin{itemize}% \item John P. Boyd: \emph{Chebyshev and Fourier spectral methods. 2nd rev. ed.} (Dover 2001, \href{http://www.zentralblatt-math.org/zmath/en/advanced/?q=an:0994.65128&format=complete}{ZMATH}) \end{itemize} For an application of spectral methods to global weather and climate models see: \begin{itemize}% \item T.N. Krishnamurti, H.S. Bedi, V. Hardiker, Leela Watson-Ramaswamy: \emph{An Introduction to Global Spectral Modeling} (Springer, 2nd edition 2010) \end{itemize} category: mathematical methods [[!redirects spectral methods]] [[!redirects spectral method]] \end{document}