A method of characteristics solving the initial-boundary value problem of a hyperbolic differential equation of second order

Summary The ALGOL-procedure¹ char2 presented in this paper can be applied to the initial or initial-boundary value problem of a quasilinear hyperbolic differential equation of second order. A method of characteristics is combined with extrapolation to the limit. Thus, the results are very accurate. The same accuracy can also be obtained if the initial values are only piecewise smooth.Editor's Note: In this fascile, prepublication of algorithms from the Approximation series of the Handbook for Automatic Computation is continued. Algorithms are published in ALGOL 60 reference language as approved by the IFIP. Contributions in this series should be styled after the most recently published ones     

An algorithm for the computation of the exponential spline

Summary Procedures for the calculation of the exponential spline (spline under tension) are presented in this paper. The procedureexsplcoeff calculates the second derivatives of the exponential spline. Using the second derivatives the exponential spline can be evaluated in a stable and efficient manner by the procedureexspl. The limiting cases of the exponential spline, the cubic spline and the linear spline are included. A proceduregenerator is proposed, which computes appropriate tension parameters. The performance of the algorithm is discussed for several examples.Editor's Note: In this fascile, prepublication of algorithms from the Approximation series of the Handbook for Automatic Computation is continued. Algorithms are published in ALGOL 60 reference language as approved by the IFIP. Contributions in this series should be styled after the most recently published ones     

Approximation with frequency filter for backward parabolic equations

Summary. We propose a numerical method for the initial (and boundary) value problem for the equation of the form where A is an unbounded, selfadjoint operator with negative spectrum. Roundoff errors in the numerical solution of such problem may generate a parasite term growing very quickly with time. To eliminate this parasite term, we apply a special finite difference equation with r free parameters. Similar ideas may be useful also for another numerically difficult differential problems. Received October 6, 1997 / revised version received November 26, 1998 / Published online October 16, 2000     

Spectral methods for initial boundary value problems with nonsmooth data

Summary. In this paper we consider hyperbolic initial boundary value problems with nonsmooth data. We show that if we extend the time domain to minus infinity, replace the initial condition by a growth condition at minus infinity and then solve the problem using a filtered version of the data by the Galerkin-Collocation method using Laguerre polynomials in time and Legendre polynomials in space, then we can recover pointwise values with spectral accuracy, provided that the actual solution is piecewise smooth. For this we have to perform a local smoothing of the computed solution. Received August 1, 1995 / Revised version received August 19, 1997     

A finite volume scheme for nonlinear parabolic equations derived from one-dimensional local dirichlet problems

In this paper, we propose a new method to compute the numerical flux of a finite volume scheme, used for the approximation of the solution of the nonlinear partial differential equation u_t+div(qf(u))−ΔΦ(u)=0 in a 1D, 2D or 3D domain. The function Φ is supposed to be strictly increasing, but some values s such that Φ′(s)=0 can exist. The method is based on the solution, at each interface between two control volumes, of the nonlinear elliptic two point boundary value problem (qf(υ)+(Φ(υ))′)′=0 with Dirichlet boundary conditions given by the values of the discrete approximation in both control volumes. We prove the existence of a solution to this two point boundary value problem. We show that the expression for the numerical flux can be yielded without referring to this solution. Furthermore, we prove that the so designed finite volume scheme has the expected stability properties and that its solution converges to the weak solution of the continuous problem. Numerical results show the increase of accuracy due to the use of this scheme, compared to some other schemes.     

Compact difference methods applied to initial-boundary value problems for mixed systems

Summary. An initial--boundary value problem to a system of nonlinear partial differential equations, which consists of a hyperbolic and a parabolic part, is taken into consideration. The problem is discretised by a compact finite difference method. An approximation of the numerical solution is constructed, at which the difference scheme is linearised. Nonlinear convergence is proved using the stability of the linearised scheme. Finally, a computational experiment for a noncompact scheme is presented. Received May 20, 1995     

Numerical solution of a two-dimensional hyperbolic transmission problem

An initial boundary value problem for a two-dimensional hyperbolic equation in two disjoint rectangles is investigated. The existence and uniqueness and a priori estimates for weak solutions in appropriate Sobolev-like spaces are proved. Few finite difference schemes approximating this problem are proposed and analyzed.     

Convergence of the Lambert-McLeod trajectory solver and of the celf method

Summary A trajectory problem is an initial value problemd y/dt=f(y),y(0)= where the interest lies in obtaining the curve traced by the solution (the trajectory), rather than in finding the actual correspondanc between values of the parametert and points on that curve. We prove the convergence of the Lambert-McLeod scheme for the numerical integration of trajectory problems. We also study the CELF method, an explicit procedure for the integration in time of semidiscretizations of PDEs which has some useful conservation properties. The proofs rely on the concept of restricted stability introduced by Stetter. In order to show the convergence of the methods, an idea of Strang is also employed, whereby the numerical solution is compared with a suitable perturbation of the theoretical solution, rather than with the theoretical solution itself.     

Third order nonoscillatory central scheme for hyperbolic conservation laws

Summary. A third-order accurate Godunov-type scheme for the approximate solution of hyperbolic systems of conservation laws is presented. Its two main ingredients include: 1. A non-oscillatory piecewise-quadratic reconstruction of pointvalues from their given cell averages; and 2. A central differencing based on staggered evolution of the reconstructed cell averages. This results in a third-order central scheme, an extension along the lines of the second-order central scheme of Nessyahu and Tadmor \cite{NT}. The scalar scheme is non-oscillatory (and hence – convergent), in the sense that it does not increase the number of initial extrema (– as does the exact entropy solution operator). Extension to systems is carried out by componentwise application of the scalar framework. In particular, we have the advantage that, unlike upwind schemes, no (approximate) Riemann solvers, field-by-field characteristic decompositions, etc., are required. Numerical experiments confirm the high-resolution content of the proposed scheme. Thus, a considerable amount of simplicity and robustness is gained while retaining the expected third-order resolution. Received April 10, 1996 / Revised version received January 20, 1997     

On the stability of the unsmoothed Fourier method for hyperbolic equations

Summary. It has been a long open question whether the pseudospectral Fourier method without smoothing is stable for hyperbolic equations with variable coefficients that change signs. In this work we answer this question with a detailed stability analysis of prototype cases of the Fourier method. We show that due to weighted -stability, the -degree Fourier solution is algebraically stable in the sense that its amplification does not exceed . Yet, the Fourier method is weakly -unstable in the sense that it does experience such amplification. The exact mechanism of this weak instability is due the aliasing phenomenon, which is responsible for an amplification of the Fourier modes at the boundaries of the computed spectrum. Two practical conclusions emerge from our discussion. First, the Fourier method is required to have sufficiently many modes in order to resolve the underlying phenomenon. Otherwise, the lack of resolution will excite the weak instability which will propagate from the slowly decaying high modes to the lower ones. Second -- independent of whether smoothing was used or not, the small scale information contained in the highest modes of the Fourier solution will be destroyed by their amplification. Happily, with enough resolution nothing worse can happen. Received December 14, 1992/Revised version received March 1, 1993     

Spectral element methods for parabolic problems

A spectral element method for solving parabolic initial boundary value problems on smooth domains using parallel computers is presented in this paper. The space domain is divided into a number of shape regular quadrilaterals of size h and the time step k   is proportional to h²$h^2$. At each time step we minimize a functional which is the sum of the squares of the residuals in the partial differential equation, initial condition and boundary condition in different Sobolev norms and a term which measures the jump in the function and its derivatives across inter-element boundaries in certain Sobolev norms. The Sobolev spaces used are of different orders in space and time. We can define a preconditioner for the minimization problem which allows the problem to decouple. Error estimates are obtained for both the h and p versions of this method.     

Maximale Konvergenzordnung bei der numerischen Lösung von Anfangswertproblemen mit Splines

Summary In [10] a general procedureV is presented to obtain spline approximations by collocation for the solutions of initial value problems for first order ordinary differential equations. In this paper the attainable order of convergence with respect to the maximum norm is characterized in dependence of the parameters involved inV; in particular the appropriate choice of the collocation points is considered.

---

Maximale Konvergenzordnung bei der numerischen Lösung von Anfangswertproblemen mit Splines

Zusammenfassung In [10] ist ein allgemeines VerfahrenV beschrieben, das die Lösungen von Anfangswertproblemen bei gewöhnlichen Differentialgleichungen erster Ordnung durch Splines approximiert. Die Konstruktion der Splines erfolgt hierbei mittels Kollokation. In dieser Arbeit wird die maximal erreichbare Konvergenzordnung vonV bezüglich der Maximumnorm in Abhängigkeit aller Parameter vonV charakterisiert, insbesondere wird auf die geeignete Wahl der Kollokationsknoten eingegangen.

     

Extrapolation to the limit for numerical solutions of hyperbolic equations

Summary The application of extrapolation to the limit requires the existence of an asymptotic expansion in powers of the step size. In this paper one-and multi-step methods for the solution of hyperbolic systems of first order are considered. Conditions are formulated that ensure the asymptotic expansion. Methods of characteristics for quasilinear systems with two independent variables are included in this presentation. If a rectangular grid is used, also non-quasilinear systems are admissible. The main part of this paper deals with initial value problems. But it is shown that in some exceptional cases asymptotic expansions hold for initial-boundary problems, too.This paper is chiefly based on the author's doctoral thesis [7], written under the direction of Professor R. Bulirsch     

Contractivity of Runge-Kutta methods

In this paper we present necessary and sufficient conditions for Runge-Kutta methods to be contractive. We consider not only unconditional contractivity for arbitrary dissipative initial value problems, but also conditional contractivity for initial value problems where the right hand side function satisfies a circle condition. Our results are relevant for arbitrary norms, in particular for the maximum norm.For contractive methods, we also focus on the question whether there exists a unique solution to the algebraic equations in each step. Further we show that contractive methods have a limited order of accuracy. Various optimal methods are presented, mainly of explicit type. We provide a numerical illustration to our theoretical results by applying the method of lines to a parabolic and a hyperbolic partial differential equation.Research supported by the Netherlands Organization for Scientific Research (N.W.O.) and the Royal Netherlands Academy of Arts and Sciences (K.N.A.W.)     

A singular perturbation of the heat equation with memory

In this paper we consider a hyperbolic equation, with a memory term in time, which can be seen as a singular perturbation of the heat equation with memory. The qualitative properties of the solutions of the initial boundary value problems associated with both equations are studied. We propose numerical methods for the hyperbolic and parabolic models and their stability properties are analyzed. Finally, we include numerical experiments illustrating the performance of those methods.     

Error growth analysis via stability regions for discretizations of initial value problems

This paper deals with numerical methods for the solution of linear initial value problems. Two main theorems are presented on the stability of these methods. Both theorems give conditions guaranteeing a mild error growth, for one-step methods characterized by a rational function ϕ(z). The conditions are related to the stability regionS={z:z∈ℂ with |ϕ(z)|≤1}, and can be viewed as variants to the resolvent condition occurring in the reputed Kreiss matrix theorem. Stability estimates are presented in terms of the number of time stepsn and the dimensions of the space. The first theorem gives a stability estimate which implies that errors in the numerical process cannot grow faster than linearly withs orn. It improves previous results in the literature where various restrictions were imposed onS and ϕ(z), including ϕ′(z)≠0 forz∈σS andS be bounded. The new theorem is not subject to any of these restrictions. The second theorem gives a sharper stability result under additional assumptions regarding the differential equation. This result implies that errors cannot grow faster thann ^β, with fixed β<1. The theory is illustrated in the numerical solution of an initial-boundary value problem for a partial differential equation, where the error growth is measured in the maximum norm.     

Marching schemes for inverse acoustic scattering problems

Summary For the numerical solution of inverse Helmholtz problems the boundary value problem for a Helmholtz equation with spatially variable wave number has to be solved repeatedly. For large wave numbers this is a challenge. In the paper we reformulate the inverse problem as an initial value problem, and describe a marching scheme for the numerical computation that needs only n² log n operations on an n × n grid. We derive stability and error estimates for the marching scheme. We show that the marching solution is close to the low-pass filtered true solution. We present numerical examples that demonstrate the efficacy of the marching scheme.     

On one approach to a posteriori error estimates for evolution problems solved by the method of lines

Summary. In this paper, we describe a new technique for a posteriori error estimates suitable to parabolic and hyperbolic equations solved by the method of lines. One of our goals is to apply known estimates derived for elliptic problems to evolution equations. We apply the new technique to three distinct problems: a general nonlinear parabolic problem with a strongly monotonic elliptic operator, a linear nonstationary convection-diffusion problem, and a linear second order hyperbolic problem. The error is measured with the aid of the -norm in the space-time cylinder combined with a special time-weighted energy norm. Theory as well as computational results are presented. Received September 2, 1999 / Revised version received March 6, 2000 / Published online March 20, 2001     

Runge-Kutta methods without order reduction for linear initial boundary value problems

Summary. It is well-known the loss of accuracy when a Runge–Kutta method is used together with the method of lines for the full discretization of an initial boundary value problem. We show that this phenomenon, called order reduction, is caused by wrong boundary values in intermediate stages. With a right choice, the order reduction can be avoided and the optimal order of convergence in time is achieved. We prove this fact for time discretizations of abstract initial boundary value problems based on implicit Runge–Kutta methods. Moreover, we apply these results to the full discretization of parabolic problems by means of Galerkin finite element techniques. We present some numerical examples in order to confirm that the optimal order is actually achieved. Received July 10, 2000 / Revised version received March 13, 2001 / Published online October 17, 2001     

The method of lines for nonlinear parabolic differential equations with mixed derivatives

Summary By the so-called longitudinal method of lines the first boundary value problem for a parabolic differential equation is transformed into an initial value problem for a system of ordinary differential equations. In this paper, for a wide class of nonlinear parabolic differential equations the spatial derivatives occuring in the original problem are replaced by suitable differences such that monotonicity methods become applicable. A convergence theorem is proved. Special interest is devoted to the equationu _t=f(x,t,u,u _x,u _xx), if the matrix of first order derivatives off(x,t,z,p,r) with respect tor may be estimated by a suitable Minkowski matrix.