next up previous contents
Next: The Pseudospectral Fourier Approximation Up: The Spectral Fourier Approximation Previous: The Spectral Fourier Approximation

Stability and convergence

We now raise the question of convergence. That is, whether the accumulation of spectrally small errors while integrating (meth_spec.27) rather than (meth_spec.29), give rise to an approximate solution which is only spectrally away from the exact projection . We already know that the distance between and the exact solution u(x,t) - due to the spectrally small initial error - is spectrally small as we have seen in the previous constant coefficient case.

To answer this convergence question we have to require the stability of the approximate model (meth_spec.27). That is, we say that the approximation (meth_spec.27) is if it satisfies an a priori energy estimate analogous to the one we have for the differential equation
Clearly, such a stability estimate is necessary in any computational model. Otherwise, the evolution model does not depend continuously on the (initial) data, and small rounding errors can render the computed solution useless. On the positive side we will show that the stability implies the spectral convergence of an approximate solution .gif Indeed the error equation for takes the form
Let denote the evolution operator solution associated with this approximate model. By the stability estimate (meth_spec.34),
Hence, by (meth_spec.36) together with Duhammel's principle we get for the inhomogeneous error equation (meth_spec.35)
In our case , and the truncation error is spectrally small; hence
where the constant depends on and , i.e., restricted solely by the smoothness of the data. In the particular case of analytic data we have exponential convergence
Adding to this the error between and u(t) (- which is due to the spectrally small error in the initial data between and f) we end up with
To summarize, we have shown that our spectral Fourier approximation converges spectrally to the exact solution, provided the approximation (meth_spec.27) is stable.

Is the approximation (meth_spec.27) stable? That is, do we have the a priori estimate (meth_spec.34)? To show this we try to follow the steps that lead to the analogue estimate in the differential case, compare (meth_spec.20). Thus, we multiply (meth_spec.27) by and integrate over the tex2html_wrap_inline11001-period, obtaining
But is orthogonal to so adding this to the right-hand side of (meth_spec.41) we arrive at
and we continue precisely as before to conclude, similarly to (meth_spec.22a)-(meth_spec.22b), that the stability estimate (meth_spec.34) holds

In the constant coefficient case the Fourier method amounts to a system of (2N + 1) decoupled ODE's for the Fourier coefficients of which were integrated explicitly. Let's see what is the case with problems having variable coefficients say, for simplicity, . Fourier transform (meth_spec.22a)-(meth_spec.22b) we obtain for - the kth-Fourier coefficient of ,
In this case we have a coupled system of ODE's written in the matrix-vector form, consult (app_ps.46)
We can solve this system explicitly (since a was assumed not to depend on time)
that is, we obtain an explicit representation of the solution operator
where denote the spectral Fourier projection
We note that in view of Parseval's identity (modulo factorization factor), hence, stability amounts to having the a priori estimate on the discrete symbol , requiring
The essential point of stability here, lies in having a uniform bound for the RHS of (meth_spec.49) -- a bound which is independent of the order of the system; for example, the 'naive' straightforward estimate of the form
will not suffice for that purpose because . The essence of the a priori estimate we obtained in (meth_spec.22a)-(meth_spec.22b), and likewise in (meth_spec.42), was that the (unbounded) operator is semi-bounded, i.e.,

namely, (compare (hyper.26))

and likewise for . In the present form this is expressed by the sharper estimate of the matrix exponent,gif compare (meth_spec.50)
This time, like the , is bounded. Indeed, , and since a(x,t) is real (hyperbolicity!) then , i.e.,
Thus, is a (possibly complex-valued) Toeplitz matrix, namely its (k,j) entry depends solely on its distance from the main diagonal k-j; we leave it as an exercise (utilizing our previous study on circulant matrices in (app_ps.43)) - to see that its norm does not exceed the sum of the absolute values along the, say, zeroth (j = 0) row, i.e.,
which is bounded, uniformly with respect to N, provided a(x,t) is sufficiently smooth, e.g., we can take the exponent M to be
which is only slightly worse than what we obtained in (meth_spec.43).

A similar analysis shows the convergence of the spectral-Fourier method for hyperbolic systems. For example, consider the symmetric hyperbolic problem
We note that if the system is not in this symmetric form, then (in the 1-D case) we can bring it to the symmetric form by a change of variables, i.e., the existence of a smooth symmetric H(x,t) such that H(x,t)A(x,t) is symmetric, implies that for with we have, compare (hyper.15)
where is symmetric, and . The spectral Fourier approximation of (meth_spec.55a) takes the form
Its stability follows from integration by parts, for by orthogonality
and hence
The approximation (meth_spec.56) is spectrally accurate with (meth_spec.55a) and hence spectral convergence follows. The solution of (meth_spec.56) is carried out in the Fourier space, and takes the form
which form a coupled system of ODE's for the (2N+1)-vectors of Fourier coefficients .

There are two difficulties in carrying out the calculation with the spectral Fourier method. First, is the time integration of (meth_spec.59); even in the constant coefficient case, it requires to the computation of the exponent which is expensive, and in the time-dependent case we must appeal to approximate numerical methods for time integration. Second, to compute the RHS of (meth_spec.59) we need to multiply an matrix, by the Fourier coefficient vector which requires operations. Indeed, since is a Toeplitz matrix and is diagonal, we can still carry out this multiplication efficiently, i.e., using two FFT's which requires operations. Yet, it still necessitates carrying out the calculation in the Fourier space. We can overcome the last difficulty with the pseudospectral Fourier method.

Before leaving the spectral method, we note that its spectral convergence equally applies to any PDE
with semi-bounded operator P(x,t,D), e.g., the symmetric hyperbolic as well as the parabolic operators. Indeed, the spectral approximation of (meth_spec.60) reads
Multiply by and integrate - by orthogonality and semi-boundedness we have
Hence stability follows and the method converges spectrally.

next up previous contents
Next: The Pseudospectral Fourier Approximation Up: The Spectral Fourier Approximation Previous: The Spectral Fourier Approximation

Eitan Tadmor
Thu Jan 22 19:07:34 PST 1998