Global extrapolation with a parallel splitting method

Extrapolation with a parallel splitting method is discussed. The parallel splitting method reduces a multidimensional problem into independent one-dimensional problems and can improve the convergence order of space variables to an order as high as the regularity of the solution permits. Therefore, in order to match the convergence order of the space variables, a high order method should also be used for the time integration. Second and third order extrapolation methods are used to improve the time convergence and it was found that the higher order extrapolation method can produce a more accurate solution than the lower order extrapolation method, but the convergence order of high order extrapolation may be less than the actual order of the extrapolation. We also try to show a fact that has not been studied in the literature, i.e. when the extrapolation is used, it may decrease the convergence of the space variables. The higher the order of the extrapolation method, the more it decreases the convergence of the space variables. The global extrapolation method also improves the parallel degree of the parallel splitting method. Numerical tests in the paper are done in a domain of a unit circle and a unit square.Supported by the Academy of Finland.     

On the approximation of derivatives using divided difference operators preserving the local convergence order of iterative methods

A development of an inverse first-order divided difference operator for functions of several variables is presented. Two generalized derivative-free algorithms built up from Ostrowski’s method for solving systems of nonlinear equations are written and analyzed. A direct computation of the local order of convergence for these variants of Ostrowski’s method is given. In order to preserve the local order of convergence, any divided difference operator is not valid. Two counterexamples of computation of a classical divided difference operator without preserving the order are presented. A rigorous study to know a priori if the new method will preserve the order of the original modified method is presented. The conclusion is that this fact does not depend on the method but on the systems of equations and if the associated divided difference verifies a particular condition. A new divided difference operator solving this problem is proposed. Furthermore, a computation that approximates the order of convergence is generated for the examples and it confirms in a numerical way that the order of the methods is well deduced. This study can be applied directly to other Newton’s type methods where derivatives are approximated by divided differences.     

Continuous-discontinuous finite element method for convection-diffusion problems with characteristic layers

We study convergence properties of a numerical method for convection-diffusion problems with characteristic layers on a layer-adapted mesh. The method couples standard Galerkin with an h-version of the nonsymmetric discontinuous Galerkin finite element method with bilinear elements. In an associated norm, we derive the error estimate as well as the supercloseness result that are uniform in the perturbation parameter. Applying a post-processing operator for the discontinuous Galerkin method, we construct a new numerical solution with enhanced convergence properties.     

Analysis of the quasi-Laguerre method

The quasi-Laguerre's iteration formula, using first order logarithmic derivatives at two points, is derived for finding roots of polynomials. Three different derivations are presented, each revealing some different properties of the method. For polynomials with only real roots, the method is shown to be optimal, and the global and monotone convergence, as well as the non-overshooting property, of the method is justified. Different ways of forming quasi-Laguerre's iteration sequence are addressed. Local convergence of the method is proved for general polynomials that may have complex roots and the order of convergence is . Received June 30, 1996 / Revised version received August 12, 1996     

A fictitious domain approach to the numerical solution of PDEs in stochastic domains

We present an efficient method for the numerical realization of elliptic PDEs in domains depending on random variables. Domains are bounded, and have finite fluctuations. The key feature is the combination of a fictitious domain approach and a polynomial chaos expansion. The PDE is solved in a larger, fixed domain (the fictitious domain), with the original boundary condition enforced via a Lagrange multiplier acting on a random manifold inside the new domain. A (generalized) Wiener expansion is invoked to convert such a stochastic problem into a deterministic one, depending on an extra set of real variables (the stochastic variables). Discretization is accomplished by standard mixed finite elements in the physical variables and a Galerkin projection method with numerical integration (which coincides with a collocation scheme) in the stochastic variables. A stability and convergence analysis of the method, as well as numerical results, are provided. The convergence is “spectral” in the polynomial chaos order, in any subdomain which does not contain the random boundaries.     

A characteristics-mixed covolume method for a convection-dominated transport problem

In this paper, we propose a characteristics-mixed covolume method for approximating the solution to a convection dominated transport problem. The method is a combination of characteristic approximation to handle the convection term in time and mixed covolume method spatial approximation to deal with the diffusion term. The velocity and press are approximated by the lowest order Raviart-Thomas mixed finite element space on rectangles. The projection of a mixed covolume element is introduced. We prove its first order optimal rate of convergence for the approximate velocities in the L² norm as well as for the approximate pressures in the L² norm.     

A Zienkiewicz-type finite element applied to fourth-order problems

This paper deals with convergence analysis and applications of a Zienkiewicz-type (Z-type) triangular element, applied to fourth-order partial differential equations. For the biharmonic problem we prove the order of convergence by comparison to a suitable modified Hermite triangular finite element. This method is more natural and it could be applied to the corresponding fourth-order eigenvalue problem. We also propose a simple postprocessing method which improves the order of convergence of finite element eigenpairs. Thus, an a posteriori analysis is presented by means of different triangular elements. Some computational aspects are discussed and numerical examples are given.     

Nonlinear scheme with high accuracy for nonlinear coupled parabolic-hyperbolic system

A nonlinear finite difference scheme with high accuracy is studied for a class of two-dimensional nonlinear coupled parabolic-hyperbolic system. Rigorous theoretical analysis is made for the stability and convergence properties of the scheme, which shows it is unconditionally stable and convergent with second order rate for both spatial and temporal variables. In the argument of theoretical results, difficulties arising from the nonlinearity and coupling between parabolic and hyperbolic equations are overcome, by an ingenious use of the method of energy estimation and inductive hypothesis reasoning. The reasoning method here differs from those used for linear implicit schemes, and can be widely applied to the studies of stability and convergence for a variety of nonlinear schemes for nonlinear PDE problems. Numerical tests verify the results of the theoretical analysis. Particularly it is shown that the scheme is more accurate and faster than a previous two-level nonlinear scheme with first order temporal accuracy.     

On some one-point hybrid iterative methods

When we choose an iterative process for solving a nonlinear equation, the region of accessibility of the iterative process is certainly useful. We know that the higher the order of convergence of the iterative process, the smaller the region of accessibility. In this paper, we present a simple modification of the classic third-order iterative processes, so as to consider, for each of them, the same region of accessibility as that of the Newton method, that is to say a method of order of convergence two.     

A supraconvergent scheme for the Korteweg-de Vries equation

Summary A finite-difference method for the integration of the Korteweg-de Vries equation on irregular grids is analyzed. Under periodic boundary conditions, the method is shown to be supraconvergent in the sense that, though being inconsistent, it is second order convergent. However, such a convergence only takes place on grids with an odd number of points per period. When a grid with an even number of points is used, the inconsistency of the method leads to divergence. Numerical results backing the analysis are presented.     

Optimization of parameters for curve interpolation by cubic splines

In this paper, we present an interpolation method for curves from a data set by means of the optimization of the parameters of a quadratic functional in a space of parametric cubic spline functions. The existence and the uniqueness of this problem are shown. Moreover, a convergence result of the method is established in order to justify the method presented. The aforementioned functional involves some real non-negative parameters; the optimal parametric curve is obtained by the suitable optimization of these parameters. Finally, we analyze some numerical and graphical examples in order to show the efficiency of our method.     

Block iterative solvers for higher order finite volume methods

Recently, new higher order finite volume methods (FVM) were introduced in [Z. Cai, J. Douglas, M. Park, Development and analysis of higher order finite volume methods over rectangles for elliptic equations, Adv. Comput. Math. 19 (2003) 3-33], where the linear system derived by the hybridization with Lagrange multiplier satisfying the flux consistency condition is reduced to a linear system for a pressure variable by an appropriate quadrature rule. We study the convergence of an iterative solver for this linear system. The conjugate gradient (CG) method is a natural choice to solve the system, but it seems slow, possibly due to the non-diagonal dominance of the system. In this paper, we propose block iterative methods with a reordering scheme to solve the linear system derived by the higher order FVM and prove their convergence. With a proper ordering, each block subproblem can be solved by fast methods such as the multigrid (MG) method. The numerical experiments show that these block iterative methods are much faster than CG.     

On the approximation of nonlinear singular self-adjoint second order boundary value problems

We investigate the approximation of the solutions of a class of nonlinear second order singular boundary value problems with a self-adjoint linear part. Our strategy involves two ingredients. First, we take advantage of certain boundary condition functions to obtain well behaved functions of the solutions. Second, we integrate the problem over an interval that avoids the singularity. We are able to prove a uniform convergence result for the approximate solutions. We describe how the approximation is constructed for the various values of the deficiency index associated with the differential equation. The solution of the nonlinear problem is obtained by a globally convergent iterative method.     

Energy-conserved splitting FDTD methods for Maxwell’s equations

In this paper, two new energy-conserved splitting methods (EC-S-FDTDI and EC-S-FDTDII) for Maxwell’s equations in two dimensions are proposed. Both algorithms are energy-conserved, unconditionally stable and can be computed efficiently. The convergence results are analyzed based on the energy method, which show that the EC-S-FDTDI scheme is of first order in time and of second order in space, and the EC-S-FDTDII scheme is of second order both in time and space. We also obtain two identities of the discrete divergence of electric fields for these two schemes. For the EC-S-FDTDII scheme, we prove that the discrete divergence is of first order to approximate the exact divergence condition. Numerical dispersion analysis shows that these two schemes are non-dissipative. Numerical experiments confirm well the theoretical analysis results.     

On an iterative algorithm with superquadratic convergence for solving nonlinear operator equations

We study an iterative method with order for solving nonlinear operator equations in Banach spaces. Algorithms for specific operator equations are built up. We present the received new results of the local and semilocal convergence, in case when the first-order divided differences of a nonlinear operator are Hölder continuous. Moreover a quadratic nonlinear majorant for a nonlinear operator, according to the conditions laid upon it, is built. A priori and a posteriori estimations of the method’s error are received. The method needs almost the same number of computations as the classical Secant method, but has a higher order of convergence. We apply our results to the numerical solving of a nonlinear boundary value problem of second-order and to the systems of nonlinear equations of large dimension.     

A Runge–Kutta type modified Landweber method for nonlinear ill-posed operator equations

In this paper, we investigate the convergence behavior of a Runge–Kutta type modified Landweber method for nonlinear ill-posed operator equations. In order to improve the stability and convergence of the Landweber iteration, a 2-stage Gauss-type Runge–Kutta method is applied to the continuous analogy of the modified Landweber method, to give a new modified Landweber method, called R–K type modified Landweber method. Under some appropriate conditions, we prove the convergence of the proposed method. We conclude with a numerical example confirming the theoretical results, including comparisons to the modified Landweber iteration.     

A uniformly convergent scheme for a system of reaction–diffusion equations

In this work a system of two parabolic singularly perturbed equations of reaction–diffusion type is considered. The asymptotic behaviour of the solution and its partial derivatives is given. A decomposition of the solution in its regular and singular parts has been used for the asymptotic analysis of the spatial derivatives. To approximate the solution we consider the implicit Euler method for time stepping and the central difference scheme for spatial discretization on a special piecewise uniform Shishkin mesh. We prove that this scheme is uniformly convergent, with respect to the diffusion parameters, having first-order convergence in time and almost second-order convergence in space, in the discrete maximum norm. Numerical experiments illustrate the order of convergence proved theoretically.     

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.     

Runge-Kutta methods without order reduction for linear initial boundary value problems

Summary. It is well-known the loss of accuracy when a Runge–Kutta method is used together with the method of lines for the full discretization of an initial boundary value problem. We show that this phenomenon, called order reduction, is caused by wrong boundary values in intermediate stages. With a right choice, the order reduction can be avoided and the optimal order of convergence in time is achieved. We prove this fact for time discretizations of abstract initial boundary value problems based on implicit Runge–Kutta methods. Moreover, we apply these results to the full discretization of parabolic problems by means of Galerkin finite element techniques. We present some numerical examples in order to confirm that the optimal order is actually achieved. Received July 10, 2000 / Revised version received March 13, 2001 / Published online October 17, 2001