Analysis of general quadrature methods for integral equations of the second kind

Summary This paper is concerned with a class of approximation methods for integral equations of the form , wherea andb are finite,f andy are continuous and the kernelk may be weakly singular. The methods are characterized by approximate equations of the form ; such methods include the Nyström method and a variety of product-integration methods. A general convergence theory is developed for methods of this type. In suitable cases it has the feature that its application to a specific method depends only on a knowledge of convergence properties of the underlying quadrature rule. The theory is used to deduce convergence results, some of them new, for a number of specific methods.Work supported by the U.S. Department of Energy     

Contractivity preserving explicit linear multistep methods

Summary We investigate contractivity properties of explicit linear multistep methods in the numerical solution of ordinary differential equations. The emphasis is on the general test-equation , whereA is a square matrix of arbitrary orders1. The contractivity is analysed with respect to arbitrary norms in thes-dimensional space (which are not necessarily generated by an inner product). For given order and stepnumber we construct optimal multistep methods allowing the use of a maximal stepsize.This research has been supported by the Netherlands organisation for scientific research (NWO)     

On quasi degree quadrature rules

Summary In this paper we examine quadrature rules for the integral which are exact for all with +d. We specify three distinct families of solutions which have properties not unlike the standard Gauss and Radau quadrature rules. For each integerd the abscissas of the quadrature rules lie within the closed integration interval and are expressed in terms of the zeros of a polynomialq _d(y). These polynomialsq _d(y), (d=0, 1, ...), which are not orthogonal, satisfy a three term recurrence relation of the type Q_d+1(y)=(y+_d+1)q_d(y)–_d+1yq_d–1(y) and have zeros with the standard interlacing property.This work was supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38     

Numerical stability of the cyclic Richardson iteration

Summary The success of the cyclic Richardson iteration depends on the proper ordering of the acceleration parameters. We give a rigorous error analysis to show that, with the proper ordering, the relative error in the iterative method, when properly terminated, is not larger than the error incurred in stable direct methods such as Cholesky factorization. For both the computed approximation tou=L ^–1f satisfies cond (L)u2^–t and this bound is attainable. We also show that the residual norm is bounded by L cond . This bound is attainable for a small cycle lengthN. Our analysis suggests that for a larger cycle lengthN the residuals are bounded by . We construct a theoretical example in which this bound is attainable. However we observed in all numerical tests that ultimately the residual norms were of order . We explain why in practice even the factor is never encountered. Therefore the residual stopping criterion for the Richardson iteration appears to be very reliable and the method itself appears to be stable.The author gratefully acknowledges partial support from ONR Contract N00014-85-K-0180On leave from the University of Krakow, Poland, during the spring semester 1989     

Stochastic Partial Differential Equations on Manifolds~II. Nonlinear Filtering

The conditional law of an unobservable component x(t) of a diffusion (x(t),y(t)) given the observations {y(s):s[0,t]} is investigated when x(t) lives on a submanifold of . The existence of the conditional density with respect to a given measure on is shown under fairly general conditions, and the analytical properties of this density are characterized in terms of the Sobolev spaces used in the first part of this series.     

Circulant integral operators as preconditioners for Wiener-Hopf equations

In this paper, we study the solutions of finite-section Wiener-Hopf equations by the preconditioned conjugate gradient method. Our main aim is to give an easy and general scheme of constructing good circulant integral operators as preconditioners for such equations. The circulant integral operators are constructed from sequences of conjugate symmetric functions {C }. Letk(t) denote the kernel function of the Wiener-Hopf equation and be its Fourier transform. We prove that for sufficiently large if {C } is uniformly bounded on the real lineR and the convolution product of the Fourier transform ofC with uniformly onR, then the circulant preconditioned Wiener-Hopf operator will have a clustered spectrum. It follows that the conjugate gradient method, when applied to solving the preconditioned operator equation, converges superlinearly. Several circulant integral operators possessing the clustering and fast convergence properties are constructed explicitly. Numerical examples are also given to demonstrate the performance of different circulant integral operators as preconditioners for Wiener-Hopf operators.Research supported in part by HKRGC grant no. 221600070.     

On rates of acceleration of extrapolation methods for oscillatory infinite integrals

The purpose of this work is to complement and expand our knowledge of the convergence theory of some extrapolation methods for the accurate computation of oscillatory infinite integrals. Specifically, we analyze in detail the convergence properties of theW- and -transformations of the author as they are applied to three integrals, all with totally different behavior at infinity. The results of the analysis suggest different convergence and acceleration of convergence behavior for the above mentioned transformations on the different integrals, and they improve considerably those that can be obtained from the existing convergence theories.     

Incomplete factorizations of singular linear systems

Recent works have shown that, whenA is a Stieltjes matrix, its so-called modified incomplete factorizations provide effective preconditioning matrices for solvingAx=b by polynomially accelerated iterative methods. We extend here these results to the singular case with the conclusion that the latter techniques are able to solve singular systems at the same speed as regular systems.Research supported by the Fonds National de la Recherche Scientifique (Belgium) — Aspirant.     

Evolution inclusions governed by subdifferentials in reflexive Banach spaces

The existence, uniqueness and regularity of strong solutions for Cauchy problem and periodic problem are studied for the evolution equation: where is the so-called subdifferential operator from a real Banach space V into its dual V*. The study in the Hilbert space setting (V = V* = H: Hilbert space) is already developed in detail so far. However, the study here is done in the V–V* setting which is not yet fully pursued. Our method of proof relies on approximation arguments in a Hilbert space H. To assure this procedure, it is assumed that the embeddings are both dense and continuous.     

The Convergence Rate of Block Preconditioned Systems Arising from LMF-based ODE Codes

The solution of ordinary an partial differential equations using implicit linear multi-step formulas (LMF)is considered. More precisely, boundary value methods (BVMs), a class of methods based on implicit formulas will be taken into account in this paper. These methods require the solution of large and sparse linear systems x = b. Block-circulant preconditioners have been propose to solve these linear systems. By investigating the spectral condition number of , we show that the conjugate gradient method, when applied to solving the normalize preconditioned system, converges in at most O(log s) steps, where the integration step size is O(1/s). Numerical results are given to illustrate the effectiveness of the analysis.This revised version was published online in October 2005 with corrections to the Cover Date.     

On monotone extensions of boundary data

Summary A functionf C (), is called monotone on if for anyx, y the relation x – y ₊ ^s impliesf(x)f(y). Given a domain with a continuous boundary and given any monotone functionf on we are concerned with the existence and regularity ofmonotone extensions i.e., of functionsF which are monotone on all of and agree withf on . In particular, we show that there is no linear mapping that is capable of producing a monotone extension to arbitrarily given monotone boundary data. Three nonlinear methods for constructing monotone extensions are then presented. Two of these constructions, however, have the common drawback that regardless of how smooth the boundary data may be, the resulting extensions will, in general, only be Lipschitz continuous. This leads us to consider a third and more involved monotonicity preserving extension scheme to prove that, when is the unit square [0, 1]² in ², strictly monotone analytic boundary data admit a monotone analytic extension.Research supported by NSF Grant 8922154Research supported by DARPA: AFOSR #90-0323     

A note on approximate controllability for semilinear one-dimensional heat equation

The one-dimensional semilinear heat equation is considered. It is shown that if the nonlinear functionF(y) is uniformly bounded then the system is approximately controllable for every given terminal timeT>0 under some ordinary condition onb. The results may be extended to the general one-dimensional semilinear heat equation with one-dimensional control or to a boundary control heat system with semilinear boundary condition.     

AnO(nL) infeasible-interior-point algorithm for LCP with quadratic convergence

The Mizuno-Todd-Ye predictor-corrector algorithm for linear programming is extended for solving monotone linear complementarity problems from infeasible starting points. The proposed algorithm requires two matrix factorizations and at most three backsolves per iteration. Its computational complexity depends on the quality of the starting point. If the starting points are large enough, then the algorithm hasO(nL) iteration complexity. If a certain measure of feasibility at the starting point is small enough, then the algorithm has iteration complexity. At each iteration, both feasibility and optimality are reduced exactly at the same rate. The algorithm is quadratically convergent for problems having a strictly complementary solution, and therefore its asymptotic efficiency index is . A variant of the algorithm can be used to detect whether solutions with norm less than a given constant exist.This work was supported in part by the National Science Foundation under grant DMS-9305760.     

Approaching a vertex in a shrinking domain under a nonlinear flow

We consider here the homogeneous Dirichlet problem for the equation , in a noncylindrical domain in space-time given by . By means of matched asymptotic expansion techniques we describe the asymptotics of the maximal solution approaching the vertex x=0, t=T, in the three different cases p>1/2, p=1/2(vertex regular), p<1/2 (vertex irregular).     

Das asymptotische Verhalten der Peanokerne einiger interpolatorischer Quadraturverfahren

Summary Interpolatory quadrature formulae consist in replacing by wherep _f denotes the interpolating polynomial off with respect to a certain knot setX. The remainder may in many cases be written as wherem=n resp. (n+1) forn even and odd, respectively. We determine the asymptotic behaviour of the Peano kernelP _X (t) forn for the quadrature formulae of Filippi, Polya and Clenshaw-Curtis.

     

Multiple equilibria,periodic solutions and a priori bounds for solutions in superlinear parabolic problems

Consider the Dirichlet problem for the parabolic equation in , where $\Omega$ is a bounded domain in and f has superlinear subcritical growth in u. If f is independent of t and satisfies some additional conditions then using a dynamical method we find multiple (three, six or infinitely many) nontrivial stationary solutions. If f has the form where m is periodic, positive and m,g satisfy some technical conditions then we prove the existence of a positive periodic solution and we provide a locally uniform bound for all global solutions.     

Heavy Transversals and Indecomposable Hypergraphs

A weighted hypergraph is a hypergraph H = (V, E) with a weighting function , where R is the set of reals. A multiset S V generates a partial hypergraph H ^S with edges , where both the cardinality and the total weight w(S) are counted with multiplicities of vertices in S. The transversal number of H is represented by (H). We prove the following: there exists a function f(n) such that, for any weighted n-Helly hypergraph H, (H ^B ) 1, for all multisets B V if and only if (H ^A ) 1, for all multisets A V with . We provide lower and upper bounds for f(n) using a link between indecomposable hypergraphs and critical weighted n-Helly hypergraphs.* On leave from Computing and Automation Research Institute, Hungarian Academy of Sciences.     

On shooting methods for the discrete Helmholtz equation with constant coefficients

Summary The paper is concerned with shooting solvers for the Helmholtz equation with constant coefficients in two dimensions using finite differences for the discretization. Dirichlet boundary conditions are treated though other conditions are possible. Beginning with a single shooting method some recursive multiple shooting methods are developed. It will be shown that the performance of the algorithms may be improved considerably by a redundance-free recursion. The number of operations required for one solution will be computed, but without preparing some matrices which do not depend on the boundary conditions and the inhomogenity. For a square withn×n points the number is of the orderO(n ²⁺⁽ⁿ⁾) with . The method will be compared with a multi-grid program and finally — as an example—a Stokes-solver and some numerical results with the shooting method are given.     

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.     

Uniformly convergent difference schemes for singularly perturbed parabolic diffusion-convection problems without turning points

We consider first the initial-boundary value problem for the parabolic equation