On the Neumann Problem for some Linear and Non-linear Uniformly Elliptic Difference Equations

In this paper we obtain a priori bounds on difference quotientsto the solution of the second boundary value problem for somelinear uniformly elliptic difference equations over rectangularregions. These results are applied to the constructive solutionof mildly non-linear and mildly quasi-linear uniformly ellipticdifference equations.     

More on Graph Perturbations

Various modifications of a connected graph G are regarded asperturbations of an adjacency matrix A of G. Several resultsconcerning the resulting changes to the largest eigenvalue ofA are obtained by solving intermediate eigenvalue problems ofthe second type.     

High-accuracy P-stable Methods for y' = f(t, y)

We obtain a one-parameter family of sixth-order P-stable methodsfor the numerical integration of periodic or near-periodic differentialequations that are defined by initial-value problems of theform: y^" = f(t, y), y(t₀)= y₀, y^'(t₀)= y^’₀. Our P-stablemethods are symmetric and involve three function evaluationsper step (periteration, in case f(t, y) is non-linear in y).For non-linear problems, starting values for the solution ofthe implicit equations by modified Newton's method are suggestedand illustrated by an example.     

Domain decomposition preconditioners of Neumann-Neumann type for hp-approximations on boundary layer meshes in three dimensions

We develop and analyse Neumann–Neumann methods for hpfinite-element approximations of scalar elliptic problems ongeometrically refined boundary layer meshes in three dimensions.These are meshes that are highly anisotropic where the aspectratio typically grows exponentially with the polynomial degree.The condition number of our preconditioners is shown to be independentof the aspect ratio of the mesh and of potentially large jumpsof the coefficients. In addition, it only grows polylogarithmicallywith the polynomial degree, as in the case of p approximationson shape-regular meshes. This work generalizes our previousone on two-dimensional problems in Toselli & Vasseur (2003a,submitted to Numerische Mathematik, 2003c to appear in Comput.Methods Appl. Mech. Engng.) and the estimates derived here canbe employed to prove condition number bounds for certain typesof FETI methods.     

A transform method for linear evolution PDEs on a finite interval

We study initial boundary value problems for linear scalar evolutionpartial differential equations, with spatial derivatives ofarbitrary order, posed on the domain {t > 0, 0 < x <L}. We show that the solution can be expressed as an integralin the complex k-plane. This integral is defined in terms ofan x-transform of the initial condition and a t-transform ofthe boundary conditions. The derivation of this integral representationrelies on the analysis of the global relation, which is an algebraicrelation defined in the complex k-plane coupling all boundaryvalues of the solution. For particular cases, such as the case of periodic boundaryconditions, or the case of boundary value problems for even-orderPDEs, it is possible to obtain directly from the global relationan alternative representation for the solution, in the formof an infinite series. We stress, however, that there existinitial boundary value problems for which the only representationis an integral which cannot be written as an infinite series.An example of such a problem is provided by the linearized versionof the KdV equation. Similarly, in general the solution of odd-orderlinear initial boundary value problems on a finite intervalcannot be expressed in terms of an infinite series.     

Positive Solutions of Nonlocal Boundary Value Problems: A Unified Approach

We give a unified approach for studying the existence of multiplepositive solutions of nonlinear differential equations of theform where g, f are non-negativefunctions, subject to various nonlocal boundary conditions.We study these problems via new results for a perturbed integralequation, in the space C[0, 1], of the form where [u], ß[u] are linear functionalsgiven by Stieltjes integrals but are not assumed to be positivefor all positive u. This means we actually cover many more differentialequations than the simple equation written above. Previous resultshave studied positive functionals only, but even for positivefunctionals our methods give improvements on previous work.The well-known m-point boundary value problems are special casesand we obtain sharp conditions on the coefficients, which allowssome of them to have opposite signs. We also use some optimalassumptions on the nonlinear term.     

Triple-deck Flows over Wavy Surfaces

Sinusoidally perturbed laminar flow over a flat plate is considered,in which the amplitude and wave number bear the triple-deckrelation to the Reynolds number R. To find the resulting flowfield and in particular the surface shear stress and pressureit is necessary to solve the non-linear lower-deck equation.Analytic solutions of the linearized equations are obtainedand the behaviour of the stresses near the leading edge of thewaviness is examined. As regions further downstream are consideredit is found that the linearized results predict the same surfacestress phase shifts as those derived by Benjamin (1959) forboundary-layer flows over wavy surfaces of amplitude and wavenumberindependent of R. For larger amplitudes, the full non-linearequations are solved numerically via a modification of the spectralmethod of Burggraf & Duck (1981). This modification is shownto significantly increase both the speed and accuracy of theoriginal method for lower-deck problems in general. Specialattention is paid to the problems associated with the semi-infiniteextent of the surface perturbation. The results of these non-linearcalculations of the stresses are examined to determine the effectsof increasing amplitude h and of increasing distance downstream.It is found that the surface stress extrema are phase-shifteddownstream with respect to the surface perturbation both asthe amplitude is increased and as regions further downstreamof the leading edge are considered. Moreover, the stress profilesbecome considerably distorted from sinusoidal as h increases.It is found that separation occurs at higher values of h thanpredicted by linear theory. Finally, differences between resultsfor positive and negative h are examined.     

Some results on the regularization of LSQR for large-scale discrete ill-posed problems

LSQR, a Lanczos bidiagonalization based Krylov subspace iterative method, and its mathematically equivalent conjugate gradient for least squares problems (CGLS) applied to normal equations system, are commonly used for large-scale discrete ill-posed problems. It is well known that LSQR and CGLS have regularizing effects, where the number of iterations plays the role of the regularization parameter. However, it has long been unknown whether the regularizing effects are good enough to find best possible regularized solutions. Here a best possible regularized solution means that it is at least as accurate as the best regularized solution obtained by the truncated singular value decomposition (TSVD) method. We establish bounds for the distance between the k-dimensional Krylov subspace and the k-dimensional dominant right singular space. They show that the Krylov subspace captures the dominant right singular space better for severely and moderately ill-posed problems than for mildly ill-posed problems. Our general conclusions are that LSQR has better regularizing effects for the first two kinds of problems than for the third kind, and a hybrid LSQR with additional regularization is generally needed for mildly ill-posed problems. Exploiting the established bounds, we derive an estimate for the accuracy of the rank k approximation generated by Lanczos bidiagonalization. Numerical experiments illustrate that the regularizing effects of LSQR are good enough to compute best possible regularized solutions for severely and moderately ill-posed problems, stronger than our theory predicts, but they are not for mildly ill-posed problems and additional regularization is needed.     

Schur complement preconditioners for anisotropic problems

We present two new variants of Schur complement domain decompositionpreconditioners suitable for 2D anisotropic problems. Thesevariants are based on adaptations of the probing idea, describedby Chan et al (1992 Fifth Int. Symp. on Domain DecompositionMethods for Partial Differential Equations, Philadelphia: SIAM,pp 236-249), used in conjunction with a coarse grid approximationas introduced by Bramble et al (1986 Math. Comput. 47, 103-134).The new methods are specifically designed for situations wherethe coupling between neighbouring interfaces is stronger thanthe coupling within an interface. Taking into account this strongcoupling, one variant uses a multicolour probing technique toavoid distortion in the probe approximations that appear whenusing the method proposed by Chan et al. The second techniqueuses additional probe matrices to approximate not only the couplingwithin the interfaces but also the coupling between interfacepoints across the subdomains. This latter procedure looks somewhatlike an alternating line relaxation method for anisotropic problems,see Brandt (1977 Math. Comput.. 31, 333-390). To assess therelevance of the new preconditioners, we compare their numericalbehaviour with well known robust preconditioners such as thebalanced Neumann-Neumann method proposed by Mandel (1993 Commun.Numer. Methods Eng.. 9, 233-241).     

Convergence rates for the coupling of FEM and collocation BEM

We prove convergence of the coupling of finite and boundaryelements where Galerkin's methd is used for finite elementsand collocation for boundary elements. We consider linear ellipticboundary value problems in two dimensions, in particular problemsin elasticity. The mesh width k of the boundary elements andthe mesh width h of the finite elements are required to satisfykßh with suitable ß. Asymptotic error estimatesin the energy norm and in the L²-norm are derived. Numericalexamples are included.     

A Sequential Algorithm for an Inventory Selection Problem

Assume that we have m finished products in an inventory. Eachfinished product is characterized by two measurements P andQ. A customer specifies a purchase order by the requirementsof characteristics P and Q. A product is qualified to satisfya purchase order if and only if it possesses better measurementsof both P and Q than the customer requires. For a given batchof n purchase orders, the inventory selection problem is tochoose n finished products from the inventory to satisfy allpurchase orders with a minimum cost. This problem can be formulatedas a large-scale transportation problem. When the cost functionof selecting a product to satisfy an order exhibits certainstructure, we develop a fast sequential algorithm to solve thisproblem. Possible extensions and related problems are also discussedin this paper.     

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

An unfitted finite-element method for elliptic and parabolic interface problems

Bhupen Deka Department of Mathematics, Assam University, Silchar-788011, India ^{A finite-element discretization, independent of the locationof the interface, is proposed and analysed for linear ellipticand parabolic interface problems. We establish error estimatesof optimal order in the H1-norm and almost optimal order inthe L2-norm for elliptic interface problems. An extension toparabolic interface problems is also discussed and an optimalerror estimate in the L2(0, T;H1())-norm and an almost optimalorder estimate in the L2(0, T;L2())-norm are derived for thespatially discrete scheme. A fully discrete scheme based onthe backward Euler method is analysed and an optimal order errorestimate in the L2(0, T;H1())-norm is derived. The interfacesare assumed to be of arbitrary shape and smooth for our purpose.}     

LAX CONSTRAINTS IN SEMISIMPLE LIE GROUPS

Instead of studying Lax equations as such, a solution Z of aLax equation is assumed to be given. Then Z is regarded as defininga constraint on a non-autonomous linear differential equationassociated with the Lax equation. In generic cases, quadratureand sometimes algebraic formulae in terms of Z are then provedfor solution x of the linear differential equation, and examplesare given where these formulae lead to new results in higher-ordervariational problems for curves in general semisimple Lie groupsG, extending results previously obtained by different methodsfor the case where G has dimension 3. The new construction isexplored in detail for G = SU(m).     

Duality, triality and complementary extremum principles in non-convex parametric variational problems with applications

This paper presents a reasonably complete duality theory anda nonlinear dual transformation method for solving the fullynonlinear, non-convex parametric variational problem inf{W(u- µ) - F(u)}, and associated nonlinear boundary valueproblems, where is a nonlinear operator, W is either convexor concave functional of p = u, and µ is a given parameter.Detailed mathematical proofs are provided for the complementaryextremum principles proposed recently in finite deformationtheory. A method for obtaining truly dual variational principles(without a dual gap and involving the dual variable p* of uonly) in n-dimensional problems is proposed. It is proved thatfor convex W(p), the critical point of the associated LagrangianL_µ(u, p*) is a saddle point if and only if the so-calledcomplementary gap function is positive. In this case, the systemhas only one dual problem. However, if this gap function isnegative, the critical point of the Lagrangian is a so-calledsuper-critical point, which is equivalent to the Auchmuty'sanomalous critical point in geometrically linear systems. Wediscover that, in this case, the system may have more than oneprimal-dual set of problems. The critical point of the Lagrangianeither minimizes or maximizes both primal and dual problems.An interesting triality theorem in non-convex systems is proved,which contains a minimax complementary principle and a pairof minimum and maximum complementary principles. Applicationsin finite deformation theory are illustrated. An open problemleft by Hellinger and Reissner is solved completely and a purecomplementary energy principle is constructed. It is provedthat the dual Euler-Lagrange equation is an algebraic equation,and hence, a general analytic solution for non-convex variational-boundaryvalue problems is obtained. The connection between nonlineardifferential equations and algebraic geometry is revealed.     

On the Approximate Solution of a Diffusion Problem by Galerkin Methods

Discrete-time Galerkin methods are considered for the approximatesolution of a parabolic initial boundary value problem whicharises, for example, in problems involving the diffusion ofa solute into a solid from a stirred solution of fixed volume.Optimal error estimates in the L² and H¹ norms are derived forthe Crank-Nicolson Galerkin method. For the one space variablecase optimal L estimates are also obtained. Results of numericalexperiments are presented and comparisons with finite differenceapproximations are made.     

Quadratic Termination Properties of Minimization Algorithms I. Statement and Discussion of Results

There is a family of gradient algorithms (Broyden, 1970) thatincludes many useful methods for calculating the least valueof a function F(x), and some of these algorithms have been extendedto solve linearly constrained problems (Fletcher, 1971). Somenew and fundamental properties of these algorithms are given,in the case that F(x) is a positive definite quadratic function.In particular these properties are relevant to the case whenonly some of the iterations of an algorithm make a completelinear search. They suggest that Goldfarb's (1969) algorithmfor linearly constrained problems has excellent quadratic terminationproperties, and it is proved that these properties are betterthan has been stated in previously published papers. Also anew technique is identified for unconstrained minimization withoutlinear searches.     

Minima of Trigonometric Polynomials

Let 0<n₁<n₂<...<n_N be N distinct integers, and leta₁, a₂, ..., a_N be complex numbers. We set [formula] and [formula] There are two well-known problems concerning the case a₁=a₂=...=a_N=1.1991 Mathematics Subject Classification 42A05.     

A Numerical Method for the Solution of the Double Eigenvalue Problem

A generalization of the Rayleigh quotient iterative method,called the Minimum Residual Quotient Iteration (MRQI), is derivedfor the numerical solution of the 2-parameter eigenvalue problem;i.e. to find scalars µ and a corresponding vector x satisfyingthe following equations, Ax = B₁x + µB₂x, ||x|| = 1, f(x) = 0, where A and B are nxn real matrices, ||.|| denotes the l₂ normand f is a real functional. The method is applied to doubleeigenvalue problems for ordinary differential equations andcomputational results are presented.     

Generalized mildly nonlinear complementarity problems for fuzzy mappings

In this paper, we introduce and study a new class of generalized mildly nonlinear complementarity problems for fuzzy mappings. We use the change of variables technique to establish the equivalence between the generalized mildly nonlinear complementarity problems and the Wiener-Hopf equations. This equivalence is used to suggest and analyze a number of iterative algorithm for solving the generalized mildly nonlinear complementarity problems.