> <\body> > <\itemize> : <\eqnarray*> f(x)>||-f|2n\x>>>|f|\x>\|>>||\\f>>|>|||(m-n)!(m+n)!>.>>>> : <\equation*> PPW=|k\x>\2 : <\equation*> \=> : Leading term of the relative error. Often <\equation*> PE(p,\)\C\|PPW>. : <\equation*> W=2m*\PPW\t>, where . : As above with \>. Demand exactness for trig. polynomial >. Find coefficients by comparing with Fourier series for x>. Rearranging the sum gives <\equation*> u|\x>\|>=(-1)sin|N+1>(j-i)|\>>u. Assume ]\\> periodic. <\itemize> even. : <\eqnarray*> >|>|:\|n\|\N/2}N+1.>>|>|>|\sinxN.>>>> <\itemize> : <\eqnarray*> u(x)>||>>e,>>|>||>>f(x)e\x.>>>> Special cases: <\itemize> real>=>>, even>only cosines, odd>only sines. :\ <\itemize> >>\|\|\\>>u|L|>\0>. >>\|\|\\>>u|L>|>\0>. m-1)>> (viewed periodically) is continuous, \L>>\|\(1/n)>. : C>>>> decays faster than any power of . \=\\>. Projection and differentiation commute. (start with expansion above, carry out both.) : \(Id-\)=0>. <\itemize> : <\eqnarray*> >||u|L|2>\>>\|\|(1+\|n\|).>>>> Parseval's Identity: <\equation*> \|\|=>>\|u\|. . H>: <\equation*> u|L|>\C*h|L|>. Proof: Parseval, consider tail, smuggle in an \>>. analytic: <\equation*> u|L|>\C*e|> Proof: |L|>\C*q!|>>,Stirling's Formula: qe>, N>. H>: <\equation*> u|H|>\C*h|H|>. Proof: Parseval, \)|N>>. C>, 1/2>: <\equation*> u|L>|>\h|L|>. Proof: u\|>, smuggle in >, CSU. > a constant coefficient differential operator>: <\equation*> \u=au|\x>. <\equation*> u-\\u|H|>\h|>. <\itemize> =2\j/N>, N-1>. ( points) : Periodic case: Trapezoidal rule is Gau˙ quadrature. <\equation*> u\:>>u(x)=u(x) Proof: Evaluate geometric series. : <\equation*> =>e>u(x), where =1+\> to compensate for =>.> coefficients, quadrature points. : <\eqnarray*> u(x)>||N/2>e.>>|||g(x)u(x)>>>> with <\equation*> g(x)=sinN|2>cot|2>. <\itemize> :L\>. u(x)=u(x)>. (rewrite sums, geometric series) Two different ways to differentiate: go through mode space--or don't. Differentiation matrix is . consequences: <\itemize> |\x>\D\> (/\x:\>) \D>. Spatial discretization does not cause phase error deterioration. <\itemize> =2\j/(N+1)> N>. ( points) : Periodic case: Trapezoidal rule is Gau˙ quadrature. <\equation*> u\:>>u(x)=u(x). : <\equation*> =u(x)e>. : <\eqnarray*> u(x)>||N/2>e>>|||u(x)h(x)>>>> with <\equation*> h(x)=*(x-x)|sin(x-x)>=e)>. <\itemize> :L\>. u(x)=u(x)>. May also be viewed as : Same differentiation matrix as >-order FD. |\x>=\\>. <\itemize> H>, 1/2>: <\equation*> =+\,m\0> Proof: Substitute continuous into discrete, exchange sums because of absolute convergence, smuggle+CSU. : <\equation*> \u\-. H>, 1/2>: <\equation*> u|L|>\h|L|>. Proof: smuggle, CSU. H>, 1/2>: <\equation*> u|L|>\h|L|>. Proof: Error = aliasing+truncation. H>, 1/2>: <\equation*> u|H|>\h|>. H>, 1/2>: <\eqnarray*> u|H|>>|>||>,>>|u-\\u|H|>>|>||>.>>>> Consider =\u>. <\itemize> : <\equation*> R=\u-\u\. : Calculate residual, project onto >, set to zero. <\itemize> Multiplication (for nonlinear problems) becomes convolution. (e.g. Burgers) More complicated nonlinearities: no way. Very efficient for linear, constant-coefficient problems with periodic BCs. <\itemize> > semi-bounded>: <\equation*> \+\>\2\Id >stability. : Integrate by parts.\ Examples: <\itemize> =a(x)\> =\b(x)\> > semi-bounded>Fourier-Galerkin stable>. Proof: show =\>> by u|v||>=u|\v||>>. Then =\\\> semi-bounded. <\itemize> : <\equation*> R\|>=0 : Collocation points }>>Quadrature points }>. (we won't do that) : Expand with Lagrange interpolation polynomial. Obtain residual. Set to zero at collocation points>simply replace derivatives by application of the differentiation matrix. <\itemize> \\>>, so Fourier Galerkin proof breaks. : <\equation*> =f(x))|\> |N|>=|L|>> for odd expansion. |N|>\|L|>> for even expansion. =a(x)u(x)>, 1/k\\|a(x)\|\k>: <\itemize> (t)|N|>\k(0)||>>. Proof: Multiply by /a>, obtain /\t(u)>. Use exactness of quad. formula, periodicity to get /\t=0>. Exploit boundedness of . |\>=A*D*\>: Use > as a change of variables, then bound =e\> by saying D*A> is skew-symmetric. Proof remains valid for |\>=D*A\>, =-a(x)>, > =a(x)u(x)> with changing sign, but \|/2\\> uniformly <\itemize> \ <\equation*> \u=a*u+(a*u)-au to get |N|>\et>|N|>>: Proof: Multiply by >, get /\tu>. Integrate (exact) by parts in the second term, only third term left over, yields bound. skew-symmetric equation can be written <\eqnarray*> u|\t>+\a\u+\\[a*u]-\(au)>>||>|u|\t>+\a\u+\\[a*u]-\\(a*u)-\a\u>||>|u|\t>+\a\u+\\[a*u]-\\(a*u)|\>\>>||>>> <\equation*> |L|>\h|L|> (it's because > contains derivatives). This motivates the... <\equation*> |~>u=\u+(-1)|N>\u. Stable if >>some constant . Proof: Add > on both sides, integrate |A|N|>> by parts, |L|>>. Bound superviscosity term by same norm, bound for u|N|>> involving \|> shows up. Using Fourier Galerkin, see that superviscosityfiltering. =b(x)\u>, 0>: <\itemize> matrix method: Define =D>, note \\>, \\>, use skew-hermiticity. integral method: \\\\\\>, then rewrite as integral. =f(U)>: <\itemize> Spectral viscosity method <\equation*> \u+\\f(u)=\(-1)\[Q\\u] where > is a filter Superspectral viscosity method <\equation*> \u+\\f(u)=\(-1)\u. <\itemize> \span{x:0\n\N}>. Fourier methods achieve exponential accuracy only if is periodic. : <\equation*> \\=\p\\)+q\=\w\ 0>, q\M>, the weight function. : <\equation*> |>=\,\=|\||>,=>|L|>. Estimate decay of > by plugging in eigenvalue problem, using selfadjointness of operator. : vanishes at boundary. <\equation*> \\|\|\C>|w>u|L|>. >spectral decay for >> functions with zero BCs. (Regular problem: only for periodic problems, otherwise boundary causes error.) : ,\)>>, ,\\-1> <\equation*> p(x)=(1-x)+1>(1+x)+1>,w(x)=(1-x)>(1+x)>,q(x)=c*w. : <\equation*> (1-x)>(1+x)>P,\>(x)=n!>\(1-x)+n>(1+x)+n>. : <\equation*> |\x>P,\)>=+\+1|2>P+1,\+1)>(x). : <\equation*> P,\)>=(-1)P,\)>(-x). , ,\)>=1>, ,\)>=(\+\+2)x+(\-\)/2>. : =\=0>, 1>, called > : >>, , . =cos(n*arccos(x))>. <\equation*> x*T=T+T. Chebyshev is best approximation to > among polynomials of degree . : =\>. PPW for polynomials: 4>. (Gegenbauer expansion, decay of the Bessel function) <\itemize> Can somewhat easily differentiate and integrate, requires three-term stuff and its inverse. : both endpoints part of the quadrature. Exact for >. : one endpoint part of the quadrature. Exact for >. : no endpoints part of the quadrature. Exact for >. Each different kind of polynomial has a different set of quadrature points and weights because each has a different weight function. Chebyshev Quadrature: <\equation*> |>|||>||=-cos\>|=-cos\>|=-cos\>|,N>>||=|cN>>|=|c>\>|=|N+1>>|>>>> with <\equation*> c=1+\+\. ,\]> denotes discrete inner product, |N,w|>> discrete norm. : not exact for , but equivalent. : <\equation*> \u(x)=P)>(x),=|~>>u(x)P)>(x)w . Proof: Plug coefficient terms into expansion, exchange sums to find <\equation*> l(x)=w|~>>P)>(x)P)>(x) is the Lagrange interpolation polynomial. Differentiation matrices are nilpotent. (Decrease in order) GL Differentiation matrix is centro-antisymmetric. =D>. : Wild behavior of polynomials near interval boundaries. C[-1,1]>, }> interpolation nodes. Then <\equation*> u|\|>\\|1+\\|>|\|>, where >> is the best-approximating polynomial and <\equation*> \=max\,\=>l(x). \C*log(N+1)+C>. : <\equation*> u(x)-\u(x)=(\)|(N+1)!>(x-x). Grid points should cluster quadratically near the boundary. <\itemize> : Residual orthogonal to >. : <\equation*> S=>\\\w\x. : <\equation*> M=>\\w\x, positive definite because >-norm is a norm. Formulation: <\equation*> |\>=MS\. Basis constructed as a linear combination of )>> to ensure BCs are kept. =\u>. If > is semi-bounded (+\>\2\Id>), then the Galerkin method is stable. Linear hyperbolic equation well-posed in Jacobi norm for \0>, \0>, but not for Chebyshev. (Consider >. Norm blows up, because Cheb weights blow up.) <\itemize> : Residual orthogonal to >, where is the number of BCs, demand that it is zero. BC coefficients can be obtained once PDE-discretizing coefficients are computed. Mass matrix remains diagonal. Usable for elliptic problems, allows efficient preconditioners. Burgers: Product once again becomes convolution-like term. <\itemize> : Residual zero at interpolation/quadrature nodes. Stability: Usual go-to-integral stuff. <\itemize> : <\equation*> Q(x)=(x)|2P(-1)>=|>||\-1.>>>>> <\equation*> u|\t>+au|\x>=-\a*Q(x)(u(-1)-BC) Consistent because exact solution satisfies scheme exactly. Stable: go back to integral, gives boundary values, tweak > to be bigger than corresponding weight. <\initial> <\collection> <\references> <\collection> > > > > > > > > > > > > > > > > > > > > > <\auxiliary> <\collection> <\associate|toc> |math-font-series||1High order FD> |.>>>>|> |math-font-series||2Trigonometric Polynomial Approximation> |.>>>>|> |2.1Continuous Expansion |.>>>>|> > |2.1.1Approximation Theory for the Continuous Expansion |.>>>>|> > |2.2Discrete Expansion |.>>>>|> > |2.2.1Discrete Even Expansion |.>>>>|> > |2.2.2Discrete Odd Expansion |.>>>>|> > |2.2.3Approximation Theory for Discrete Expansions |.>>>>|> > |math-font-series||3Fourier Spectral Methods> |.>>>>|> |3.1Fourier Galerkin |.>>>>|> > |3.1.1Stability |.>>>>|> > |3.2Fourier Collocation |.>>>>|> > |3.2.1Stability |.>>>>|> > |math-font-series||4Orthogonal Polynomials> |.>>>>|> |math-font-series||5Polynomial Expansions> |.>>>>|> |math-font-series||6Polynomial Spectral Methods & Stability> |.>>>>|> |6.1Galerkin |.>>>>|> > |6.2Tau |.>>>>|> > |6.3Collocation |.>>>>|> > |6.4Penalty Method for Boundary Conditions |.>>>>|> >