Piecewise Polynomial Collocation for Volterra-type Integral Equations of the Second Kind

The exact solution of a given integral equation of the secondkind of Volterra type(with regular or weakly singular kernel)is projected into the space of (continuous) piecewise polynomialsof degree m 1 and with prescribed knots by using collocationtechniques. It is shown that a number of discrete methods forthe numerical solution of such equations based on product integrationtechniques or on finite-difference methods are particular discreteversions of collocation methods of the above type. The errorbehaviour of approximate solutions obtained by collocation (includingtheir discretizations) is discussed.     

Trigonometric Hermite wavelet approximation for the integral equations of second kind with weakly singular kernel

This paper is concerned with a trigonometric Hermite wavelet Galerkin method for the Fredholm integral equations with weakly singular kernel. The kernel function of this integral equation considered here includes two parts, a weakly singular kernel part and a smooth kernel part. The approximation estimates for the weakly singular kernel function and the smooth part based on the trigonometric Hermite wavelet constructed by E. Quak [Trigonometric wavelets for Hermite interpolation, Math. Comp. 65 (1996) 683–722] are developed. The use of trigonometric Hermite interpolant wavelets for the discretization leads to a circulant block diagonal symmetrical system matrix. It is shown that we only need to compute and store O(N)$\mathrm{O}(N)$ entries for the weakly singular kernel representation matrix with dimensions N²$N^2$ which can reduce the whole computational cost and storage expense. The computational schemes of the resulting matrix elements are provided for the weakly singular kernel function. Furthermore, the convergence analysis is developed for the trigonometric wavelet method in this paper.     

A Fast Galerkin Algorithm for Singular Integral Equations

A recent paper (Delves, 1977) described a variant of the Galerkinmethod for linear Fredholm integral equations of the secondkind with smooth kernels, for which the total solution timeusing N expansion functions is (N² ln N) compared with the standardGalerkin count of (N³). We describe here a modification of thismethod which retains this operations count and which is applicableto weakly singular Fredholm equations of the form where K₀(x, y) is a smooth kernel and Q contains a known singularity.Particular cases treated in detail include Fredholm equationswith Green's function kernels, or with kernels having logarithmicsingularities; and linear Volterra equations with either regularkernels or of Abel type. The case when g(x) and/or f(x) containsa known singularity is also treated. The method described yieldsboth a priori and a posteriori error estimates which are cheapto compute; for smooth kernels (Q = 1) it yields a modifiedform of the algorithm described in Delves (1977) with the advantagethat the iterative scheme required to solve the equations in(N²) operations is rather simpler than that given there.     

On the Sloan iteration applied to integral equations of the first kind

When the piecewise constant collocation method is used to solvean integral equation of the first kind with logarithmic kernel,the convergence rate is O(h) in the L₂ norm. In this note weshow that O(h³) or O(h⁵) convergence in any Sobolev norm (andthus, for example, in L) may be obtained by a simple cheap postprocessingof the original collocation solution. The construction of thepostprocessor is based on writing the first kind equation asa second kind equation, and applying the Sloan iteration tothe latter equation. The theoretical convergence rates are verifiedin a numerical example.     

A fast Fourier-Galerkin method for solving integral equations of second kind with weakly singular kernels

We propose in this paper a convenient way to compress the dense matrix representation of a compact integral operator with a weakly singular kernel under the Fourier basis. This compression leads to a sparse matrix with only ${\mathcal{O}}(n\log n)$ number of nonzero entries, where 2n+1 denotes the order of the matrix. Based on this compression strategy, we develop a fast Fourier-Galerkin method for solving second kind integral equations with weakly singular kernels. We prove that the approximate order of the truncated equation remains optimal and that the spectral condition number of the coefficient matrix of the truncated linear system is uniformly bounded. Furthermore, we develop a fast algorithm for solving the corresponding truncated linear system, which preserves the optimal order of the approximate solution with only ${\mathcal{O}}(n\log^{2}n)$ number of multiplications required. Numerical examples complete the paper.     

A quasi-wavelet algorithm for second kind boundary integral equations

In solving integral equations with a logarithmic kernel, we combine the Galerkin approximation with periodic quasi-wavelet (PQW) [4]. We develop an algorithm for solving the integral equations with only O(N log N) arithmetic operations, where N is the number of knots. We also prove that the Galerkin approximation has a polynomial rate of convergence.     

Linear Dependence Relations Connecting Equal Interval Nth Degree Splines and Their Derivatives

Present address: The Polytechnic of the South Bank, Borough Road, London, S.E.1 England. The linear dependence of the values of Nth degree spline andits pth derivatives at N successive equally spaced knots isshown and the constants associated with this linear dependencecalculated. A recurrence relation which enables the constants to be foundfor any N is also given. The results are applied to equal intervalinterpolation.     

Nystrm interpolants based on the zeros of Legendre polynomials for a non-compact integral operator equation

We consider two different Nystrm interpolants for the numericalsolution fo the following singular integral equation arising from a problem of determining the distribution of stressin a thin elastic plate in the vicinity of a cruciform crack.These interpolants originate from the discretization of theintegral by two different quadrature formulas of interpolatorytype based on the zeros of Legendre orthogonal polynomials.The first quadrature is of product type and integrates exactlythe kernel; the second one is the well-known Gauss-Legendreformula. First we derive uniform convergence estimates for the two basicquadrature rules. Then by properly modifying the interpolantassociated with the Gauss-Legendre rule we prove its stabilityand derive for it a uniform error estimate of the type O(n^–4+),>0 as small as we like. We also show that if we had beenable to prove the stability of the first (modified) interpolantwe would have obtained a similar convergence estimate. Finally,for the Gauss-Legendre interpolant we prove that in any closedsubinterval [ 1] (0, 1] the rate of convergence is at leastO(n^–6+). Some numerical results which show the accuracy of our approximantsare also presented.     

Modified Euler’s method with a graded mesh for a class of Volterra integral equations with weakly singular kernel

A modified Euler’s method applied on a graded mesh is considered for numerical solution of a class of Volterra integral equations with weakly singular kernel which depends on a parameter μ > 0. It is shown that the convergence rate of the considered method is higher than those of earlier ones for the case when μ ≤ 1. The convergence rate is also obtained in the case μ > 1. Using some numerical examples, we illustrate the theoretical results.     

Analytical Behaviour of Solutions of Boundary Integral Equations for a Nonsmooth Region

The Dirichlet problem for Helmholtz's equation in a domain exterior to some bounded smooth boundary in two dimensionsmay be solved by means of a combined potential of the singleand double layers. In this paper, the problem arising from allowingcorner points on the boundary is investigated. The resultingnoncompact operator is effectively split into singular and compactparts. By using the Mellin transforms, the equation can be convertedinto some Cauchy-type singular integral equations. Consequently,the singular form of the solution is found in terms of r^ßat a corner with 0>ß>1. As a first step towarddeveloping new numerical methods for the problem, one typicalexample is presented to demonstrate the slow convergence ofexisting methods without any modifications. Then the mesh-gradingtechnique designed for singular equations is successfully implementedto restore the order of convergence.     

Numerical Solution of Sigular Integral Equations Using Gauss-type Formulae I: I: Quadrature and Collocation on Chebyshev Nodes

Permanent address: Department of Applied Mathematics and Statistics, State University of New York at Stony Brook, Stony Brook, NY 11794. Of concern here are the Gauss—Chebyshev formulae for numericalsolution of singular integral equations of the Cauchy-type.The coefficient matrix of the linear sustem of algebraic equationscorresponding to the dominant term term is shown to have aninverse, which is expressed in a neat, closed form. Using thenorm of the inverse matrix, the effect of quadrature errorson the computed solution is estimated. Using Jackson's theoremson "best approximation", convergence of the procedure is provedunder favourable conditions. In the course of analysis, a numberof identities involving the zeros of Chebyshev polynomials offirst and second kind is obtained. ^*Dedicated to Professor I. N. Sneddon on his sixty-third birthday.     

On the Structure of the Moving Finite-element Equations

Address from 1st April 1985, School of Mathematics, Universityof Bristol, University Walk, Bristol BS8 1TW. The morning finite-element method for evolutionary partial differentialequations leads to a coupled non-linear system of ordinary differentialequations in time, with a coefficien matrix A, say, for thetime derivaties, We show for linear elements in any number ofdimensions, A can be written in the form M^TCM, where the matrixC depends solely on the mesh geometry and the matrix M on thegradient of the section, As a simple consequence we show thatA is singular only in the cases (i) element degeneracy () and (ii) collinearity of nodes (M not out of fullrank). We give constructions for the inversion of A in all cases. In one dimension, if A is non-singular, it has a simple explicitinverse. If A is singular we replace it by reduced matrix A^*.It can be shown that every case the spectral radius of the Jacobiiteration matrix ia ?and that A or A^* can be efficiently invertedby conjugate gradient methods. Finally, we discuss the applicability of these arguments tosystem of equations in any number of dimensions.     

On the L2 convergence of collocation for the generalized airfoil equation

In this paper we establish the L₂ convergence of a polynomial collocation method for the solution of a class of Cauchy singular linear integral equations, which we term the generalized airfoil equation. Previous numerical results have shown that if the right hand side is smooth then convergence is rapid, with 6 decimal accuracy achievable using 8–10 basis elements. Practical problems in aerodynamics dictate that this equation be solved for discontinuous data. The convergence rate is numerically demonstrated to be $\text{O(}\text{1}\text{N}\text{)}$, where N is the number of basis elements used. Simple extrapolation is shown to be effective in accelerating the convergence, 4–5 decimal accuracy being achieved using 16 basis elements.     

Stationary Critical Points of the Heat Flow in Spaces of Constant Curvature

The paper considers stationary critical points of the heat flowin sphere S^N and in hyperbolic space H^N, and proves severalresults corresponding to those in Euclidean space R^N which havebeen proved by Magnanini and Sakaguchi. To be precise, it isshown that a solution u of the heat equation has a stationarycritical point, if and only if u satisfies some balance lawwith respect to the point for any time. In Cauchy problems forthe heat equation, it is shown that the solution u has a stationarycritical point if and only if the initial data satisfies thebalance law with respect to the point. Furthermore, one point,say x₀, is fixed and initial-boundary value problems are consideredfor the heat equation on bounded domains containing x₀. It isshown that for any initial data satisfying the balance law withrespect to x₀ (or being centrosymmetric with respect to x₀)the corresponding solution always has x₀ as a stationary criticalpoint, if and only if the domain is a geodesic ball centredat x₀ (or is centrosymmetric with respect to x₀, respectively).     

A Fast Direct Method for the Least Squares Solution of Slightly Overdetermined Sets of Linear Equations

Noble (1969) has described a method for the solution of N+Mlinear equations in N unknowns, which is based on an initialpartitioning of the matrix A, and which requires only the solutionof square sets of equations. He assumed rank (A) = N. We describehere an efficient implementation of Noble's method, and showthat it generalizes in a simple way to cover also rank deficientproblems. In the common case that the equation is only slightlyoverdetermined (M << N) the resulting algorithm is muchfaster than the standard methods based on M.G.S. or Householderreduction of A, or on the normal equations, and has a very similaroperation count to the algorithm of Cline (1973). Slightly overdetermined systems arise from Galerkin methodsfor non-Hermitian partial differential equations. In these systems,rank (A) = N and advantage can be taken of the structure ofthe matrix A to yield a least squares solution in (N²) operations.     

The gradient iteration for approximation in reproducing kernel Hilbert spaces

Consider the bounded linear operator, L: F Z, where Z R^N andF are Hilbert spaces defined on a common field X. L is madeup of a series of N bounded linear evaluation functionals, L_i:F R. By the Riesz representation theorem, there exist functionsk(x_i, ^·) F : L_if = f, k(x_i, ^·)_F. The functions,k(x_i, ^·), are known as reproducing kernels and F is areproducing kernel Hilbert space (RKHS). This is a natural frameworkfor approximating functions given a discrete set of observations.In this paper the computational aspects of characterizing suchapproximations are described and a gradient method presentedfor iterative solution. Such iterative solutions are desirablewhen N is large and the matrix computations involved in thebasic solution become infeasible. This is also exactly the casewhere the problem becomes ill-conditioned. An iterative approachto Tikhonov regularization is therefore also introduced. Unlikeiterative solutions for the more general Hilbert space setting,the proofs presented make use of the spectral representationof the kernel.     

Product integration methods for solving a system of nonlinear Volterra integral equations

In this paper the technique of subtracting out singularities is used to derive explicit and implicit product Euler schemes with order one convergence and a product trapezoidal scheme with order two convergence for a system of Volterra integral equations with a weakly singular kernel. The convergence proofs of the numerical schemes are presented; these are nonstandard since the nonlinear function involved in the integral equation system does not satisfy a global Lipschitz condition.     

A Fast Method for the Solution of Fredholm Integral Equations

Methods described to date for the solution of linear Fredholmintegral equations have a computing time requirement of O(N³),where N is the number of expansion functions or discretizationpoints used. We describe here a Tchebychev expansion method,based on the FFT, which reduces this time to O(N² ln N), andreport some comparative timings obtained with it. We give alsoboth a priori and a posteriori error estimates which are cheapto compute, and which appear more reliable than those used previously.     

Perfect and Acyclic Subgroups of Finitely Presentable Groups

Acyclic groups of low dimension are considered. To indicatethe results simply, let G' be the nontrivial perfect commutatorsubgroup of a finitely presentable group G. Then def(G)1. Whendef(G)=1, G' is acyclic provided that it has no integral homologyin dimensions above 2 (a sufficient condition for this is thatG' be finitely generated); moreover, G/G' is then Z or Z². Naturalexamples are the groups of knots and links with Alexander polynomial1. A further construction is given, based on knots in S²x S¹.In these geometric examples, G' cannot be finitely generated;in general, it cannot be finitely presentable. When G is a 3-manifoldgroup it fails to be acyclic; on the other hand, if G' is finitelygenerated it has finite index in the group of a Q-homology 3-sphere.     

Locking-free DGFEM for elasticity problems in polygons

The h-version of the discontinuous Galerkin finite element method(h-DGFEM) for nearly incompressible linear elasticity problemsin polygons is analysed. It is proved that the scheme is robust(locking-free) with respect to volume locking, even in the absenceof H²-regularity of the solution. Furthermore, it is shown thatan appropriate choice of the finite element meshes leads torobust and optimal algebraic convergence rates of the DGFEMeven if the exact solutions do not belong to H².