A fast iterative method for solving stationary heat conduction problems on regions partitioned into rectangles

Summary The paper deals with some finite element approximation of stationary heat conduction problems on regions which can be partitioned into rectangular subregions. By a special superelement-technique employing fast elimination of the inner nodal parameters, the original finite element problem is reduced to a smaller problem, which is only connected with the nodes on the boundary of the superelements. To solve the reduced system of finite element equations, an efficient iterative algorithm is proposed. This algorithm is based either on the conjugate gradient method or the Tshebysheff method, using a special matrix by vector multiplication procedure. The explicit form of the matrix is not used. The presented numerical method is asymptotically optimal with respect to the memory requirement as well as to the operation count.     

An algorithm for calculating one subgradient of a convex function of two variables

Summary We present an algorithm which enables us to calculate one particular subgradient of a convex functionf: ² at a given point. Such a calculation is required in many existing numerical methods for convex nondifferentiable optimization. The novelty of our approach lies in the assumption that only the values off are computable and no analytical formula for the subdifferential is known. We include some numerical examples.     

Finite elements for parabolic equations backwards in time

Summary Several regularization methods for parabolic equations backwards in time together with the usual additional constraints for their solution are considered. The error of the regularization is estimated from above and below. For a boundary value problem in time-method, finite elements as well as a time discretization are introduced and the error with respect to the regularized solution is estimated, thus giving an overall error of the discrete regularized problem. The algorithm is tested in simple numerical examples.     

On orthogonal linear ℓ1 approximation

Summary The problem is considered of orthogonal ₁ fitting of discrete data. Local best approximations are characterized and the question of the robustness of these solutions is considered. An algorithm for the problem is presented, along with numerical results of its application to some data sets.     

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.     

High orderP-stable formulae for the numerical integration of periodic initial value problems

Summary Recently there has been considerable interest in the approximate numerical integration of the special initial value problemy=f(x, y) for cases where it is known in advance that the required solution is periodic. The well known class of Störmer-Cowell methods with stepnumber greater than 2 exhibit orbital instability and so are often unsuitable for the integration of such problems. An appropriate stability requirement for the numerical integration of periodic problems is that ofP-stability. However Lambert and Watson have shown that aP-stable linear multistep method cannot have an order of accuracy greater than 2. In the present paper a class of 2-step methods of Runge-Kutta type is discussed for the numerical solution of periodic initial value problems.P-stable formulae with orders up to 6 are derived and these are shown to compare favourably with existing methods.     

On the integration of stiff systems of O.D.E.s using extended backward differentiation formulae

Summary A class of extended backward differentiation formulae suitable for the approximate numerical integration of stiff systems of first order ordinary differential equations is derived. An algorithm is described whereby the required solution is predicted using a conventional backward differentiation scheme and then corrected using an extended backward differentiation scheme of higher order. This approach allows us to developL-stable schemes of order up to 4 andL()-stable schemes of order up to 9. An algorithm based on the integration formulae derived in this paper is illustrated by some numerical examples and it is shown that it is often superior to certain existing algorithms.     

On the computation of multi-dimensional solution manifolds of parametrized equations

Summary A new algorithm is presented for computing vertices of a simplicial triangulation of thep-dimensional solution manifold of a parametrized equationF(x)=0, whereF is a nonlinear mapping fromR ⁿ toR ^m ,p=n–m>1. An essential part of the method is a constructive algorithm for computing moving frames on the manifold; that is, of orthonormal bases of the tangent spaces that vary smoothly with their points of contact. The triangulation algorithm uses these bases, together with a chord form of the Gauss-Newton process as corrector, to compute the desired vertices. The Jacobian matrix of the mapping is not required at all the vertices but only at the centers of certain local triangulation patches. Several numerical examples show that the method is very efficient in computing triangulations, even around singularities such as limit points and bifurcation points. This opens up new possibilities for determining the form and special features of such solution manifolds.Dedicated to Professor Ivo Babuka on the occasion of his sixtieth birthdayThis work was supported in part by the National Science Foundation under Grant DCR-8309926, the Office of Naval Research under contract N-00014-80-C-9455, and the Air Force Office of Scientific Research under Grant 84-0131     

Tracking poles and representing Hankel operators directly from data

Summary We propose and analyse a method of estimating the poles near the unit circleT of a functionG whose values are given at a grid of points onT: we give an algorithm for performing this estimation and prove a convergence theorem. The method is to identify the phase for an estimate by considering the peaks of the absolute value ofG onT, and then to estimate the modulus by seeking a bestL ² fit toG over a small arc by a first order rational function. These pole estimates lead to the construction of a basis ofL ² which is well suited to the numerical representation of the Hankel operator with symbolG and thereby to the numerical solution of the Nehari problem (computing the bestH , analytic, approximation toG relative to theL norm), as analysed in [HY]. We present the results of numerical tests of these algorithms.Partially supported by grants from the AFOSR and NSF     

Produktintegration mit nicht-äquidistanten Stützstellen

Summary For the numerical evaluation of , 0<<1 andx smooth, product integration rules are applied. It is known that high-order rules, e.g. Gauss-Legendre quadrature, become normal-order rules in this case. In this paper it is shown that the high order is preserved by a nonequidistant spacing. Furthermore, the leading error terms of this product integration method and numerical examples are given.

     

On the numerical treatment of a small divisor problem

Summary Quasiperiodic solutions of perturbed integrable Hamiltonian equations such as weakly coupled harmonic oscillators can be found by constructing an appropriate coordinate transformation which leads to a small divisor problem. However the numerical difficulties are not merely caused by the small divisors but rather by the appearence of ghost solutions, which appear in any reasonable discretization of the problem. Our numerical treatment, based on a Newton-type iteration, guarantees an approximation of the relevant solution of the nonlinear problem. Numerical solutions are found up to a critical value of the coupling constant, which is much larger than the coupling constants allowed by the existence theory available so far.     

A Sinc–Collocation method for the linear Fredholm integro-differential equations

A Sinc–Collocation method for solving linear integro-differential equations of the Fredholm type is discussed. The integro-differential equations are reduced to a system of algebraic equations and Q-R method is used to establish numerical procedures. The convergence rate of the method is . Numerical results are included to confirm the efficiency and accuracy of the method even in the presence of singularities and a comparison with the rationalized Haar wavelet method is made.     

On an iterative method for variational inequalities

Summary A number of numerical solutions are presented as examples of a new iterative method for variational inequalities. The iterative method is based on the reduction of variational inequalities to the Wiener-Hopf equations. For obstacle problems the convergence is guaranteed inW ^1,p spaces forp2. The examples presented are one and two dimensional obstacle problems in cases when the Greens function is known, but the method is very general.     

QMR: a quasi-minimal residual method for non-Hermitian linear systems

Summary The biconjugate gradient (BCG) method is the natural generalization of the classical conjugate gradient algorithm for Hermitian positive definite matrices to general non-Hermitian linear systems. Unfortunately, the original BCG algorithm is susceptible to possible breakdowns and numerical instabilities. In this paper, we present a novel BCG-like approach, the quasi-minimal residual (QMR) method, which overcomes the problems of BCG. An implementation of QMR based on a look-ahead version of the nonsymmetric Lanczos algorithm is proposed. It is shown how BCG iterates can be recovered stably from the QMR process. Some further properties of the QMR approach are given and an error bound is presented. Finally, numerical experiments are reported.This work was supported in part by DARPA via Cooperative Agreement NCC 2-387 between NASA and the Universities Space Research Association (USRA).     

An algorithm for best approximate solutions ofAx=b with a smooth strictly convex norm

Summary In this paper, overdetermined systems ofm linear equations inn unknowns are considered. With ^m equipped with a smooth strictly convex norm, ·, an iterative algorithm for finding the best approximate solution of the linear system which minimizes the ·-error is given. The convergence of the algorithm is established and numerical results are presented for the case when · is anl _p norm, 1<p<.Portions of this paper are taken from the author's Ph.D. thesis at Michigan State University     

Numerical integration over a semi-infinite interval,using the lognormal distribution

Summary A method is described for numerical integration over a semiinfinite interval using a Gaussian formula, with the corresponding set of orthogonal polynomials constructed from a lognormal weight function.The lognormal weight function and hence the coefficients of the polynomials are functions of two arbitrary parameters; the mean and the logarithmic variance. The method is found to be of particular use for integration of bell-shaped or sharply spiked functions. Rapidly convergent results can be obtained in these cases, since the lognormal distribution can be used to provide a good approximation to the actual function to be integrated, by suitable choice of the two arbitrary parameters. Two examples are given for integrals with known solutions.     

An improved branch and bound algorithm for minimum concave cost network flow problems

This paper formulates the minimum concave cost network flow (MCCNF) problem as a mixed integer program and solves this program using a new branch and bound algorithm. The algorithm combines Driebeek's up and down penalties with a new technique referred to as the simple bound improvement (SBI) procedure. An efficient numerical method for the SBI procedure is described and computational results are presented which show that the SBI procedure reduces both the in-core storage and the CPU time required to solve the MCCNF problem. In fact, for problems with over 200 binary decision variables, the SBI procedure reduced the in-core storage by more than one-third and the CPU time by more than 40 percent.     

The use of splines and singular functions in an integral equation method for conformal mapping

Summary We consider the integral equation method of Symm for the conformal mapping of simply-connected domains. For the numerical solution, we examine the use of spline functions of various degrees for the approximation of the source density . In particular, we consider ways for overcoming the difficulties associated with corner singularities. For this we modify the spline approximation and in the neighborhood of each corner, where a boundary singularity occurs, we approximate by a function which reflects the main singular behaviour of the source density. The singular functions are then blended with the splines, which approximate on the remainder of the boundary, so that the global approximating function has continuity of appropriate order at the transition points between the two types of approximation. We show, by means of numerical examples, that such approximations overcome the difficulties associated with corner singularities and lead to numerical results of high accuracy.     

On error behaviour of partitioned linearly implicit runge-kutta methods for stiff and differential algebraic systems

This paper studies partitioned linearly implicit Runge-Kutta methods as applied to approximate the smooth solution of a perturbed problem with stepsizes larger than the stiffness parameter. Conditions are supplied for construction of methods of arbitrary order. The local and global error are analyzed and the limiting case 0 considered yielding a partitioned linearly implicit Runge-Kutta method for differential-algebraic equations of index one. Finally, some numerical experiments demonstrate our theoretical results.