A well-posed shooting method for transferable DAE's

Summary Consider a TPBVP for transferable nonlinear DAE's. In general the shooting equation has a singular Jacobian. A multiple shooting method which has a nonsingular Jacobian and also produces consistent initial values for the integration is presented. The estimation of the condition of the Jacobian shows the well-posedness of the method. Some illustrative examples are given     

On CSCS-based iteration methods for Toeplitz system of weakly nonlinear equations

For Toeplitz system of weakly nonlinear equations, by using the separability and strong dominance between the linear and the nonlinear terms and using the circulant and skew-circulant splitting (CSCS) iteration technique, we establish two nonlinear composite iteration schemes, called Picard-CSCS and nonlinear CSCS-like iteration methods, respectively. The advantage of these methods is that they do not require accurate computation and storage of Jacobian matrix, and only need to solve linear sub-systems of constant coefficient matrices. Therefore, computational workloads and computer storage may be saved in actual implementations. Theoretical analysis shows that these new iteration methods are local convergent under suitable conditions. Numerical results show that both Picard-CSCS and nonlinear CSCS-like iteration methods are feasible and effective for some cases.     

Stiffness of ODEs

It is argued that even for a linear system of ODEs with constant coefficients, stiffness cannot properly be characterized in terms of the eigenvalues of the Jacobian, because stiffness is a transient phenomenon whereas the significance of eigenvalues is asymptotic. Recent theory from the numerical solution of PDEs is adapted to show that a more appropriate characterization can be based upon pseudospectra instead of spectra. Numerical experiments with an adaptive ODE solver illustrate these findings.Supported by a Dundee University Research Initiatives Grant.Supported by NSF Grant DMS-9116110.     

PICARD ITERATION FOR NONSMOOTH EQUATIONS

1. IntroductionConsider the following nonsmooth equationsF(x) = 0 (l)where F: R" - R" is LipsChitz continuous. A lot of work has been done and is bellg doneto deal with (1). It is basicly a genera1ization of the cIassic Newton method [8,10,11,14],Newton-lthe methods[1,18] and quasiNewton methods [6,7]. As it is discussed in [7], the latter,quasiNewton methods, seem to be lindted when aPplied to nonsmooth caJse in that a boundof the deterioration of uPdating matrir can not be maintained w…     

Analysis of the dynamics of local error control via a piecewise continuous residual

Positive results are obtained about the effect of local error control in numerical simulations of ordinary differential equations. The results are cast in terms of the local error tolerance. Under theassumption that a local error control strategy is successful, it is shown that a continuous interpolant through the numerical solution exists that satisfies the differential equation to within a small, piecewise continuous, residual. The assumption is known to hold for thematlab ode23 algorithm [10] when applied to a variety of problems. Using the smallness of the residual, it follows that at any finite time the continuous interpolant converges to the true solution as the error tolerance tends to zero. By studying the perturbed differential equation it is also possible to prove discrete analogs of the long-time dynamical properties of the equation—dissipative, contractive and gradient systems are analysed in this way. Supported by the Engineering and Physical Sciences Research Council under grants GR/H94634 and GR/K80228. Supported by the Office of Naval Research under grant N00014-92-J-1876 and by the National Science Foundation under grant DMS-9201727.     

Local error control inSDIRK-methods

This paper describes some problems that are encountered in the implementation of a class of Singly Diagonally Implicit Runge-Kutta (SDIRK) methods. The contribution to the local error from the local truncation error and the residual error from the algebraic systems involved are analysed. A section describes a special interpolation formula. This is used as a prediction stage in the iterative solution of the algebraic equations. A strategy for computing a starting stepsize is presented. The techniques are applied to numerical examples.     

Adaptive version of Simpler GMRES

In this paper we propose a stable variant of Simpler GMRES. It is based on the adaptive choice of the Krylov subspace basis at a given iteration step using the intermediate residual norm decrease criterion. The new direction vector is chosen as in the original implementation of Simpler GMRES or it is equal to the normalized residual vector as in the GCR method. We show that such an adaptive strategy leads to a well-conditioned basis of the Krylov subspace and we support our theoretical results with illustrative numerical examples.     

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.)     

Efficient fourth orderP-stable formulae

In this paper, a family of fourth orderP-stable methods for solving second order initial value problems is considered. When applied to a nonlinear differential system, all the methods in the family give rise to a nonlinear system which may be solved using a modified Newton method. The classical methods of this type involve at least three (new) function evaluations per iteration (that is, they are 3-stage methods) and most involve using complex arithmetic in factorising their iteration matrix. We derive methods which require only two (new) function evaluations per iteration and for which the iteration matrix is a true real perfect square. This implies that real arithmetic will be used and that at most one real matrix must be factorised at each step. Also we consider various computational aspects such as local error estimation and a strategy for changing the step size.     

The error norm of Gauss-Lobatto quadrature formulae for weight functions of Bernstein-Szegö type

Summary In certain spaces of analytic functions the error term of the Gauss-Lobatto quadrature formula relative to a (nonnegative) weight function is a continuous linear functional. Here we compute the norm of the error functional for the Bernstein-Szegö weight functions consisting of any of the four Chebyshev weights divided by an arbitrary quadratic polynomial that remains positive on [–1, 1]. The norm can subsequently be used to derive bounds for the error functional. The efficiency of these bounds is illustrated with some numerical examples.Work supported in part by a grant from the Research Council of the Graduate School, University of Missouri-Columbia.     

Corrected sequential linear programming for sparse minimax optimization

We present a new algorithm for nonlinear minimax optimization which is well suited for large and sparse problems. The method is based on trust regions and sequential linear programming. On each iteration a linear minimax problem is solved for a basic step. If necessary, this is followed by the determination of a minimum norm corrective step based on a first-order Taylor approximation. No Hessian information needs to be stored. Global convergence is proved. This new method has been extensively tested and compared with other methods, including two well known codes for nonlinear programming. The numerical tests indicate that in many cases the new method can find the solution in just as few iterations as methods based on approximate second-order information. The tests also show that for some problems the corrective steps give much faster convergence than for similar methods which do not employ such steps.Research supported partly by The Nordic Council of Ministers, The Icelandic Science Council, The University of Iceland Research Fund and The Danish Science Research Council.     

Convergence of finite volume schemes for triangular systems of conservation laws

We consider non-strictly hyperbolic systems of conservation laws in triangular form, which arise in applications like three-phase flows in porous media. We device simple and efficient finite volume schemes of Godunov type for these systems that exploit the triangular structure. We prove that the finite volume schemes converge to weak solutions as the discretization parameters tend to zero. Some numerical examples are presented, one of which is related to flows in porous media. The research of K. H. Karlsen was supported by an Outstanding Young Investigators Award from the Research Council of Norway.     

Time-stepping and preserving orthonormality

Certain applications produce initial value ODEs whose solutions, regarded as time-dependent matrices, preserve orthonormality. Such systems arise in the computation of Lyapunov exponents and the construction of smooth singular value decompositions of parametrized matrices. For some special problem classes, there exist time-stepping methods that automatically inherit the orthonormality preservation. However, a more widely applicable approach is to apply a standard integrator and regularly replace the approximate solution by an orthonormal matrix. Typically, the approximate solution is replaced by the factorQ from its QR decomposition (computed, for example, by the modified Gram-Schmidt method). However, the optimal replacement—the one that is closest in the Frobenius norm—is given by the orthonormal polar factor. Quadratically convergent iteration schemes can be used to compute this factor. In particular, there is a matrix multiplication based iteration that is ideally suited to modern computer architectures. Hence, we argue that perturbing towards the orthonormal polar factor is an attractive choice, and we consider performing a fixed number of iterations. Using the optimality property we show that the perturbations improve the departure from orthonormality without significantly degrading the finite-time global error bound for the ODE solution. Our analysis allows for adaptive time-stepping, where a local error control process is driven by a user-supplied tolerance. Finally, using a recent result of Sun, we show how the global error bound carries through to the case where the orthonormal QR factor is used instead of the orthonormal polar factor. This work was supported by Engineering and Physical Sciences Research Council grants GR/H94634 and GR/K80228.     

Convergence of Newton's method for convex best interpolation

Summary. In this paper, we consider the problem of finding a convex function which interpolates given points and has a minimal norm of the second derivative. This problem reduces to a system of equations involving semismooth functions. We study a Newton-type method utilizing Clarke's generalized Jacobian and prove that its local convergence is superlinear. For a special choice of a matrix in the generalized Jacobian, we obtain the Newton method proposed by Irvine et al. [17] and settle the question of its convergence. By using a line search strategy, we present a global extension of the Newton method considered. The efficiency of the proposed global strategy is confirmed with numerical experiments. Received October 26, 1998 / Revised version received October 20, 1999 / Published online August 2, 2000     

Order conditions for Rosenbrock type methods

Summary Based on the theory of Butcher series this paper developes the order conditions for Rosenbrock methods and its extensions to Runge-Kutta methods with exact Jacobian dependent coefficients. As an application a third order modified Rosenbrock method with local error estimate is constructed and tested on some examples.     

High-order adaptive finite element-singly implicit Runge-Kutta methods for parabolic differential equations

We describe an adaptive mesh refinement finite element method-of-lines procedure for solving one-dimensional parabolic partial differential equations. Solutions are calculated using Galerkin's method with a piecewise hierarchical polynomial basis in space and singly implicit Runge-Kutta (SIRK) methods in time. A modified SIRK formulation eliminates a linear systems solution that is required by the traditional SIRK formulation and leads to a new reduced-order interpolation formula. Stability and temporal error estimation techniques allow acceptance of approximate solutions at intermediate stages, yielding increased efficiency when solving partial differential equations. A priori energy estimates of the local discretization error are obtained for a nonlinear scalar problem. A posteriori estimates of local spatial discretization errors, obtained by order variation, are used with the a priori error estimates to control the adaptive mesh refinement strategy. Computational results suggest convergence of the a posteriori error estimate to the exact discretization error and verify the utility of the adaptive technique.This research was partially supported by the U.S. Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR-90-0194; the U.S. Army Research Office under Contract Number DAAL 03-91-G-0215; by the National Science Foundation under Grant Number CDA-8805910; and by a grant from the Committee on Research, Tulane University.     

Minimum residual methods for augmented systems

For large systems of linear equations, iterative methods provide attractive solution techniques. We describe the applicability and convergence of iterative methods of Krylov subspace type for an important class of symmetric and indefinite matrix problems, namely augmented (or KKT) systems. Specifically, we consider preconditioned minimum residual methods and discuss indefinite versus positive definite preconditioning. For a natural choice of starting vector we prove that when the definite and indenfinite preconditioners are related in the obvious way, MINRES (which is applicable in the case of positive definite preconditioning) and full GMRES (which is applicable in the case of indefinite preconditioning) give residual vectors with identical Euclidean norm at each iteration. Moreover, we show that the convergence of both methods is related to a system of normal equations for which the LSQR algorithm can be employed. As a side result, we give a rare example of a non-trivial normal(1) matrix where the corresponding inner product is explicitly known: a conjugate gradient method therefore exists and can be employed in this case. This work was supported by British Council/German Academic Exchange Service Research Collaboration Project 465 and NATO Collaborative Research Grant CRG 960782     

On the monotonity of incomplete factorization

Summary The Meijerink, van der Vorst type incomplete decomposition uses a position set, where the factors must be zero, but their product may differ from the original matrix. The smaller this position set is, the more the product of incomplete factors resembles the original matrix. The aim of this paper is to discuss this type of monotonity. It is shown using the Perron Frobenius theory of nonnegative matrices, that the spectral radius of the iteration matrix is a monotone function of the position set. On the other hand no matrix norm of the iteration matrix depends monotonically on the position set. Comparison is made with the modified incomplete factorization technique.     

Efficient sixth order methods for nonlinear oscillation problems

A class of two-step (hybrid) methods is considered for solving pure oscillation second order initial value problems. The nonlinear system, which results on applying methods of this type to a nonlinear differential system, may be solved using a modified Newton iteration scheme. From this class the author has derived methods which are fourth order accurate,P-stable, require only two (new) function evaluations per iteration and have a true real perfect square iteration matrix. Now, we propose an extension to sixth order,P-stable methods which require only three (new) function evaluations per iteration and for which the iteration matrix is a true realperfect cube. This implies that at most one real matrix must be factorised at each step. These methods have been implemented in a new variable step, local error controlling code.