next up previous contents
Next: Epilogue Up: AliasingResolution and (weak) Previous: Weighted -stability

Algebraic stability and weak tex2html_wrap_inline11009-instability

In this section we turn our attention to the behavior of the Fourier method (weighted.6) in terms of the tex2html_wrap_inline11009-norm. Table 3.1 suggests that when measured with respect to the standard (weight-free) tex2html_wrap_inline11009-norm, the Fourier approximation may grow linearly with the number of gridpoints N.

Table 3.1: Amplification of at t=10,

The main result of this section asserts that this is indeed the case.


The right hand side of (weak-in.1) tells us that the Fourier method may amplify the tex2html_wrap_inline11009-size of its initial data by an amplification factor -- that is , the Fourier method is algebraically stable. The left hand side of (weak-in.1) asserts that this estimate is sharp in the sense that there exist initial data for which this amplification is attained -- that is, the Fourier method is weakly tex2html_wrap_inline11009- unstable.

We turn to the . Let denote the solution of the Fourier method (weighted.6) subject to arbitrary initial data, . We claim that we can bound the ratio in terms of the condition number, , of the weighting matrix H, . Indeed
Here, the first and last equalities are Parseval's identities; the second and forth inequalities are straightforward by the definition of a weighted norm; and the third is a manifestation of the weighted tex2html_wrap_inline11009-stability stated in Theorem 3.1.

The estimate (weak-in.2) requires to upper-bound the condition number of the weighting matrix H. We recall that the weighting matrix H is the direct sum of the matrices given in (weighted.21a)-(weighted.21b), whose tex2html_wrap_inline11009-norms equal the squared tex2html_wrap_inline11009-norms of the corresponding Jordan blocks, Inserting this into (weak-in.2) we arrive at
Thus it remains to upper bound the condition number of the Jordan blocks, . For the sake of completeness we include a brief calculation of the latter. The inverse of are upper-triangular Toeplitz matrices,
for which we have,
This means that , and together with the straightforward upper-bound, , the right hand side of the inequality (weak-in.1) now follows with .

The above -algebraic stability is essentially due to the upper-bound on the size of the inverses of Jordan blocks stated in (weak-in.4b). Can this upper-bound be improved? an affirmative answer to this question depends on the regularity of the data, as shown by the estimate

which yields an bound for -data,

Noting that the rest of the arguments in the proof of algebraic stability are invariant with respect to the -norm (-- in particular, the weighted -stability stated above), we conclude the following extension of the right inequality in (weak-in.1).


Corollary 3.1 tells us how the smoothness of the initial data is related to the possible algebraic growth; actually, for -initial data with , there is no tex2html_wrap_inline11009-growth. However, for arbitrary tex2html_wrap_inline11009 data () we remain with the upper bound (weak-in.4b), and this bound is indeed sharp for, say, . (In fact, the latter is reminiscent of the unstable oscillatory boundary wave we shall meet later in (weak-in.20)).

These considerations lead us to the question whether the linear tex2html_wrap_inline11009-growth upper-bound offered by the right hand side of (weak-in.1) is sharp. To answer this question we return to take a closer look at the real and imaginary parts of our system (weighted.7a).

We recall that according to (weighted.9a) the real part, , satisfies,

Summing by parts against we find

The boundary conditions (weighted.9b), , imply that the second term on the right is positive; using Cauchy-Schwartz to upper bound the first term yields , which in turn implies that the real part of the system (weighted.7a) is tex2html_wrap_inline11009-stable

Figure 3.1: Fourier Solution of .

In contrast to the tex2html_wrap_inline11009-bounded real part, it will be shown below that the imaginary part of our system experiences an tex2html_wrap_inline11009 linear growth, which is responsible for the algebraically weak tex2html_wrap_inline11009-instability of the Fourier method.

The imaginary part of our system, , satisfies the same recurrence relations as before
the only difference lies in the augmenting boundary conditions which now read
Trying to repeat our argument in the real case, we sum by parts against ,
but unlike the previous case, the judicious minus sign in the augmenting boundary conditions (weak-in.6b) leads to the lower bound
This lower bound indicates (but does not prove!) the possible tex2html_wrap_inline11009-growth of the imaginary part. Figure 3.1 confirms that unlike the tex2html_wrap_inline11009-bounded real part, the behavior of the imaginary part is indeed markedly different -- it consists of binary oscillations which form a growing modulated wave as . These binary oscillations suggest to consider , in order to gain a better insight into the growth of the underlying modulated wave. Observe that (weak-in.6a)-(weak-in.6b) then recasts into the centered difference scheme
which is augmented with first order homogeneous extrapolation at the 'right' boundary
We note in passing that {i} The 's, and hence the 's, are symmetric -- in this case they have an odd extension for ; {ii} No additional boundary condition is required at the left characteristic boundary ; and finally, {iii} Though (weak-in.9a)-(weak-in.9b) are independent of the frequency spacing -- in fact any will do, yet the choice of will greatly simplify the formulae obtained below. These simplifications will be advantageous throughout the rest of this section.

Clearly, the centered difference scheme (weak-in.9a) could be viewed as a consistent approximation to the linear wave equation

The essential point is that is an inflow boundary in this case, and that the boundary condition (weak-in.9b) is inflow-dependent in the sense that it is consistent with the interior inflow problem. Such inflow-dependent boundary condition renders the related constant coefficient approximation unstable.

To show that there is an -growth in this case requires a more precise study, which brings us to the . We decompose the imaginary components, , as the sum of two contributions -- a stable part, , associated with the evolution of the initial data; and an unstable part, , which describes the unstable binary oscillations propagating from the boundaries into the interior domain,

Here, is governed by an outflow centered difference scheme which is complemented by stable boundary extrapolation,
As before, we exploit symmetry to confine our attention to the 'right half' of the problem, .

A straightforward tex2html_wrap_inline11009-energy estimate confirms that this part of the imaginary components is tex2html_wrap_inline11009-stable, . In fact, the scheme (weak-in.10) retains high-order stability in the sense that
We close our discussion on the so called "s"-part by noting that (weak-in.10) is a second-order accurate approximation to the initial-value problem
Observe that the initial condition is nothing but a trigonometric interpolant in the frequency -space', which coincides with the initial value of the imaginary components, . Using the explicit solution of this initial value problem, we end up with a second order convergence statement which readsgif

We now turn our attention to the unstable oscillatory part, . It is governed by an inflow centered difference scheme,
which is coupled to the previous stable "s"-part (weak-in.10), through the boundary condition
The boundary condition (weak-in.14b) is the first-order accurate extrapolation we met earlier in (weak-in.9b) -- but this time, with the additional inhomogeneous boundary data. And as before, a key ingredient in the tex2html_wrap_inline11009-instability is the fact that such boundary treatment is inflow-dependent.

Specifically, we claim: the inflow-dependent extrapolation on the left of (weak-in.14b) reflects the boundary values on the right of (weak-in.14b), which 'inflow' into the interior domain with an amplitude amplified by a factor of order .
To prove this claim we proceed as follows. Forward differencing of (weak-in.14a) implies that satisfy the stable difference scheme
Clearly, this difference scheme is consistent with, and hence convergent to the solution of the initial-boundary value problem

Observe that describes a boundary wave which is prescribed on the boundary of the computed spectrum, , and propagates into the interior domain of lower frequencies ,
We conclude that the forward differences, , form a second-order accurate approximation of this boundary wave,

Returning to the original variables, , the latter equality reads
which confirms our above claim regarding the amplification of a boundary wave by a factor of .

The a priori estimates (weak-in.11) and (weak-in.18) provide us with precise information on the behavior of the imaginary components, : their initial value at t=0 propagate by the stable "s"-part and reaches the boundary of the computed spectrum at with the approximate boundary values of (weak-in.13), ; the latter propagate into the interior spectrum as a boundary wave of the form (weak-in.17), , whose primitive in (weak-in.18) describes the unstable oscillatory ""-part of the solution. Added all together we end up with
Thus, the unstable ""-part contributes a wave which is modulated by binary oscillations; the amplitude of these oscillations start with amplification near the boundary of the computed spectrum, , and decreases as they propagate into the interior domain of lower frequencies. Moreover, for any fixed t >0, only those modes with wavenumber k such that , are affected by the unstable "" part. Put differently, we state this as


There are two different cases to be considered, depending on the smoothness of the initial data.

Figure 3.9: Fourier solution of .

  1. . If the initial data are sufficiently smooth, then are rapidly decaying as , and hence -- by the -stability of the "s"-part in (weak-in.11), this rapid decay is retained later in time for . This implies that the discrete boundary wave -- governed by the stable scheme (weak-in.15), is negligibly small, , because its boundary values are, . We conclude that in the smooth case, remains of the same size as its initial data, .

    Figure 3.2 demonstrates this result for a prototype case of smooth initial data in Besov -- in this case, initial data with cubically decaying imaginary components, . As told by (weak-in.19), the temporal evolution of these components should include an amplified oscillatory boundary wave, , consult Remark 3 below. This amplification is confirmed by the quadratic decay of the boundary amplitudes, . Note that despite this amplification, the boundary wave and hence the whole Fourier solution remain tex2html_wrap_inline11009 bounded in this smooth case.

    Figure: Fourier solution of .

  2. . We consider initial data with very low degree of smoothness beyond their mere tex2html_wrap_inline11009-integrability, e.g., for , the corresponding components of , are square summable but slowly decaying as . Since b(0) serves as initial data for the stable "s"-part in (weak-in.10), the components of will remain square summable for t >0, but will remain slowly decaying as . In particular, this means that can be used to create the boundary wave dictated by (weak-in.16). According to (weak-in.18), the amplified primitive of this boundary wave, , will serve as the leading order term of the unstable part. We conclude that the imaginary part will be amplified by a factor of relative to the size of its nonsmooth initial data , which confirms the left hand side of the inequality (weak-in.1).

    Figure 3.3 demonstrates this result for a prototype case of nonsmooth initial data with imaginary components given by, , that is, initial data represented by a strongly peaked dipole at . According to (weak-in.19), the evolution of these components in time yields
    In this case the oscillatory boundary wave, , is added to the -initial conditions, , which is responsible for the tex2html_wrap_inline11009-growth of order . This linear tex2html_wrap_inline11009-growth is even more apparent with the 'rough' initial data we met earlier in Figure 3.1.

1. . The last Theorem confirms the tex2html_wrap_inline11009-instability indicated previously by the lower bound (weak-in.8),

By the same token, summation by parts of the imaginary part (weak-in.7), leads to the upper bound

which shows that had the boundary values of the computed spectrum -- which in this case consist of the last single mode , were to remain relatively small, then the imaginary part - and consequently the whole Fourier approximation would have been tex2html_wrap_inline11009-stable. For example, the rather weak a priori bound will suffice
What we have shown (in the second part of Theorem 3.2) is that such an a priori bound does not hold for general nonsmooth tex2html_wrap_inline11009-initial data, where according to (weak-in.19), .

Figure: Fourier solution of .

We recall that there are various procedures which enforce stability of the Fourier method, without sacrificing its high order accuracy. One possibility is to use the skew-symmetric formulation - consult §3.4 below. Another possibility is based on the observation that the current instability is due to the inflow-dependent boundary conditions (weak-in.9b) -- or equivalently (weak-in.6b), and the origin of the latter could be traced back to the aliasing relations (app_ps.7). We can therefore de-alias and hence by (weak-in.21) stabilize the Fourier method by setting , or more generally, . De-aliasing could be viewed as a robust form of high-frequency smoothing. This issue is dealt in §3.5 below. Figure 3.4a shows how the de-aliasing procedure (-- setting ), stabilizes the Fourier method which otherwise experiences the unstable linear growth in Figure 3.4b. With (weak-in.21) in mind, we may interpret these procedures as a mean to provide the missing a priori decaying bounds on the highest mode(s) of the computed spectrum, which in turn guarantee the stability of the whole Fourier approximation.

2.  . The situation described in the previous remark is a special case of the following assertion: Assume that a(x) consists of a finite number, say m modes. Then the corresponding Fourier approximation (meth_ps.17) is tex2html_wrap_inline11009-stable, provided the last m modes were filtered so that the following a priori bound holds

It should be noted that our present discussion of a(x) with m=1 modes is a prototype case for the behavior of the Fourier method, as long as the corresponding Fourier approximation is based on an odd number of 2N+1 gridpoints; otherwise the case of an even number of gridpoints is tex2html_wrap_inline11009-stable. The unique feature of this tex2html_wrap_inline11009-stability is due to the fact that Fourier differentiation matrix in this case, -- being even order antisymmetric matrix, must have zero as a double eigenvalue, which in turn inflicts a 'built-in' smoothing of the last mode in this case, namely,
Table 3.2 confirms the usual linear weak tex2html_wrap_inline11009-instability already for a 2-wave coefficient.

Table 3.2: Amplification of at t=5 with even number of gridpoints.

3. . Consider the case of sufficiently smooth initial data so that the imaginary components decay of order tex2html_wrap_inline11109,

In this case, we may approximate the corresponding initial interpolant , and (weak-in.19) tells us the Fourier approximation takes the approximate form

Observe that , (with ), where as . This lower bound is found to be in complete agreement with the -stability statement of Corollary 3.1 (apart from the factor for ) -- an enjoyable sharpness.

next up previous contents
Next: Epilogue Up: AliasingResolution and (weak) Previous: Weighted -stability

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