Splineapproximationen von beliebigem Defekt zur numerischen Lösung gewöhnlicher Differentialgleichungen. Teil III

Summary In the first part [1] a general procedure is presented to obtain polynomial spline approximations for the solutions of initial value problems for ordinary differential equations; furthermore a divergence theorem is proved there. Sufficient conditions for convergence of the method are given in the second part [2]. The remaining case which has not been considered in [1] and [2] is treated in the present paper. In this special case the procedure is equivalent to an unstable two-step method with special initial values; nevertheless, convergence can be proved. Finally,A ₀-stability of the method as well as the influence of rounding errors are investigated.

     

Extrapolation applied to certain discretization methods solving the initial value problem for hyperbolic differential equations

Summary The procedurediwiex presented in this paper provides an approximate solution to Cauchy's initial value problem for general hyperbolic systems of first order. The procedurecharex can be applied to the initial value problem for a hyperbolic system of quasi-linear differential equations. This second method is a kind of method of characteristics. It produces a solution for the whole domain of determinancy. Both procedures use extrapolation to the limit. Editor's Note. In this fascile, prepublication of algorithms from the Approximations 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     

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.

     

Average linking with complex subspaces

We generalize Banchoff–Pohl?s isoperimetric inequality to complex affine space.     

Runge–Kutta methods and viscous wave equations

We study the numerical time integration of a class of viscous wave equations by means of Runge–Kutta methods. The viscous wave equation is an extension of the standard second-order wave equation including advection–diffusion terms differentiated in time. The viscous wave equation can be very stiff so that for time integration traditional explicit methods are no longer efficient. A-Stable Runge–Kutta methods are then very good candidates for time integration, in particular diagonally implicit ones. Special attention is paid to the question how the A-Stability property can be translated to this non-standard class of viscous wave equations.      

A capacitance matrix method for Dirichlet problem on polygon region

Summary An efficient algorithm for the solution of linear equations arising in a finite element method for the Dirichlet problem is given. The cost of the algorithm is proportional toN ²log₂ N (N=1/h) where the cost of solving the capacitance matrix equations isNlog₂ N on regular grids andN ^3/2log₂ N on irregular ones.     

The Chebyshev solution of certain matrix equations

Summary The problem of approximating ann x m matrixC by matrices of the formX A+B Y whereA, B, X andY are of appropriate size is considered. The measure of error is the supremum of the absolute values of the individual entries in the error matrix. The problem is closely related to that of approximating a bivariate functionf by sums of functions of the formxh+gy wherex andg are functions of the first variable alone andh andy are functions of the second variable. An old algorithm for constructing best approximations is described, and some of the properties of its convergence are discussed.     

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.     

Spectral approximation of the periodic-nonperiodic Navier-Stokes equations

Summary In order to approximate the Navier-Stokes equations with periodic boundary conditions in two directions and a no-slip boundary condition in the third direction by spectral methods, we justify by theoretical arguments an appropriate choice of discrete spaces for the velocity and the pressure. The compatibility between these two spaces is checked via an infsup condition. We analyze a spectral and a collocation pseudo-spectral method for the Stokes problem and a collocation pseudo-spectral method for the Navier-Stokes equations. We derive error bounds of spectral type, i.e. which behave likeM ^– whereM depends on the number of degrees of freedom of the method and represents the regularity of the data.     

On the convergence of multistep methods for nonlinear stiff differential equations

Summary Convergence estimates are given forA()-stable multistep methods applied to singularly perturbed differential equations and nonlinear parabolic problems. The approach taken here combines perturbation arguments with frequency domain techniques.     

The Euler Maclaurin expansion for the Cauchy Principal Value integral

Summary The classical Euler Maclaurin Summation Formula expresses the difference between a definite integral over [0, 1] and its approximation using the trapezoidal rule with step lengthh=1/m as an asymptotic expansion in powers ofh together with a remainder term. Many variants of this exist some of which form the basis of extrapolation methods such as Romberg Integration. in this paper a variant in which the integral is a Cauchy Principal Value integral is derived. The corresponding variant of the Fourier Coefficient Asymptotic Expansion is also derived. The possible role of the former in numerical quadrature is discussed.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under contract W-31-109-Eng-38     

The hierarchical basis multigrid method

Summary We derive and analyze the hierarchical basis-multigrid method for solving discretizations of self-adjoint, elliptic boundary value problems using piecewise linear triangular finite elements. The method is analyzed as a block symmetric Gauß-Seidel iteration with inner iterations, but it is strongly related to 2-level methods, to the standard multigridV-cycle, and to earlier Jacobi-like hierarchical basis methods. The method is very robust, and has a nearly optimal convergence rate and work estimate. It is especially well suited to difficult problems with rough solutions, discretized using highly nonuniform, adaptively refined meshes.     

Numerical factorization of a polynomial by rational Hermite interpolation

We derive a class of iterative formulae to find numerically a factor of arbitrary degree of a polynomialf(x) based on the rational Hermite interpolation. The iterative formula generates the sequence of polynomials which converge to a factor off(x). It has a high convergence order even for a factor which includes multiple zeros. Some numerical examples are also included.     

On the fast solutions of nonlinear elliptic equations

Summary In a recent paper we described a multi-grid algorithm for the numerical solution of Fredholm's integral equation of the second kind. This multi-grid iteration of the second kind has important applications to elliptic boundary value problems. Here we study the treatment of nonlinear boundary value problems. The required amount of computational work is proportional to the work needed for a sequence of linear equations. No derivatives are required since these linear problems are not the linearized equations.     

Numerical calculation of incomplete gamma functions by the trapezoidal rule

Summary The trapezoidal rule is applied to the numerical calculation of a known integral representation of the complementary incomplete gamma function (a,x) in the regiona<–1 andx>0. Since this application of the rule is not standard, a careful investigation of the remainder terms using the Euler-Maclaurin formula is carried out. The outcome is a simple numerical procedure for obtaining values of incomplete gamma functions with surprising accuracy in the stated region.This work has been supported by the Ministero della Pubblica Istruzione and the Consiglio Nazionale delle Ricerche     

Error bounds for computed eigenvalues and eigenvectors. II

Summary In this paper, motivated by Symm-Wilkinson's paper [5], we describe a method which finds the rigorous error bounds for a computed eigenvalue ⁽⁰⁾ and a computed eigenvectorx ⁽⁰⁾ of any matrix A. The assumption in a previous paper [6] that ⁽⁰⁾,x ⁽⁰⁾ andA are real is not necessary in this paper. In connection with this method, Symm-Wilkinson's procedure is discussed, too.     

On the multi-level splitting of finite element spaces

Summary In this paper we analyze the condition number of the stiffness matrices arising in the discretization of selfadjoint and positive definite plane elliptic boundary value problems of second order by finite element methods when using hierarchical bases of the finite element spaces instead of the usual nodal bases. We show that the condition number of such a stiffness matrix behaves like O((log )²) where is the condition number of the stiffness matrix with respect to a nodal basis. In the case of a triangulation with uniform mesh sizeh this means that the stiffness matrix with respect to a hierarchical basis of the finite element space has a condition number behaving like instead of for a nodal basis. The proofs of our theorems do not need any regularity properties of neither the continuous problem nor its discretization. Especially we do not need the quasiuniformity of the employed triangulations. As the representation of a finite element function with respect to a hierarchical basis can be converted very easily and quickly to its representation with respect to a nodal basis, our results mean that the method of conjugate gradients needs onlyO(log n) steps andO(n log n) computer operations to reduce the energy norm of the error by a given factor if one uses hierarchical bases or related preconditioning procedures. Heren denotes the dimension of the finite element space and of the discrete linear problem to be solved.     

A-priori error estimates of Galerkin backward differentiation methods in time-inhomogeneous parabolic problems

Summary Backward differentiation methods up to orderk=5 are applied to solve linear ordinary and partial (parabolic) differential equations where in the second case the space variables are discretized by Galerkin procedures. Using a mean square norm over all considered time levels a-priori error estimates are derived. The emphasis of the results lies on the fact that the obtained error bounds do not depend on a Lipschitz constant and the dimension of the basic system of ordinary differential equations even though this system is allowed to have time-varying coefficients. It is therefore possible to use the bounds to estimate the error of systems with arbitrary varying dimension as they arise in the finite element regression of parabolic problems.     

Alternating proximal algorithms for linearly constrained variational inequalities: Application to domain decomposition for PDE’s

Let X,Y,Z be real Hilbert spaces, let f:X→R∪{+∞}, g:Y→R∪{+∞} be closed convex functions and let A:X→Z, B:Y→Z be linear continuous operators. Let us consider the constrained minimization problem Given a sequence (γ_n) which tends toward 0 as n→+∞, we study the following alternating proximal algorithm where α and ν are positive parameters. It is shown that if the sequence (γ_n) tends moderately slowly toward 0, then the iterates of (A) weakly converge toward a solution of (P). The study is extended to the setting of maximal monotone operators, for which a general ergodic convergence result is obtained. Applications are given in the area of domain decomposition for PDE’s.