A new efficient parametric family of iterative methods for solving nonlinear systems

ABSTRACT

A bi-parametric family of iterative schemes for solving nonlinear systems is presented. We prove for any value of parameters the sixth-order of convergence of any members of the class. The efficiency and computational efficiency indices are studied for this family and compared with that of the other known schemes with similar structure. In the numerical section, we solve, after discretizating, the nonlinear boundary problem described by the Fisher's equation. This numerical example confirms the theoretical results and show the performance of the proposed schemes.     

High-order finite difference schemes for the solution of second-order BVPs

We introduce new methods in the class of boundary value methods (BVMs) to solve boundary value problems (BVPs) for a second-order ODE. These formulae correspond to the high-order generalizations of classical finite difference schemes for the first and second derivatives. In this research, we carry out the analysis of the conditioning and of the time-reversal symmetry of the discrete solution for a linear convection–diffusion ODE problem. We present numerical examples emphasizing the good convergence behavior of the new schemes. Finally, we show how these methods can be applied in several space dimensions on a uniform mesh.     

GENERAL DIFFERENCE SCHEMES WITH INTRINSIC PARALLELISM FOR SEMILINEAR PARABOLIC SYSTEMS OFDIVERGENCE TYPE

1.IntroductionIn[1]and[2]thegeneralfinitedifferenceschemeshavingtheintrinsiccharacterofparallelismfortheboundaryvalueproblemsofthenonlinearparabolicsystemofgeneralform(i.e.,non-divergencetype)arediscussedundertheassumptionthatthereisanuniquesmoothsol...     

Monotone schemes for a class of nonlinear elliptic and parabolic problems

We construct monotone numerical schemes for a class of nonlinear PDE for elliptic and initial value problems for parabolic problems. The elliptic part is closely connected to a linear elliptic operator, which we discretize by monotone schemes, and solve the nonlinear problem by iteration. We assume that the elliptic differential operator is in the divergence form, with measurable coefficients satisfying the strict ellipticity condition, and that the right-hand side is a positive Radon measure. The numerical schemes are not derived from finite difference operators approximating differential operators, but rather from a general principle which ensures the convergence of approximate solutions. The main feature of these schemes is that they possess stencils stretching far from basic grid-rectangles, thus leading to system matrices which are related to M-matrices.     

Numerical methods for fourth‐order nonlinear elliptic boundary value problems

The aim of this article is to present several computational algorithms for numerical solutions of a nonlinear finite difference system that represents a finite difference approximation of a class of fourth‐order elliptic boundary value problems. The numerical algorithms are based on the method of upper and lower solutions and its associated monotone iterations. Three linear monotone iterative schemes are given, and each iterative scheme yields two sequences, which converge monotonically from above and below, respectively, to a maximal solution and a minimal solution of the finite difference system. This monotone convergence property leads to upper and lower bounds of the solution in each iteration as well as an existence‐comparison theorem for the finite difference system. Sufficient conditions for the uniqueness of the solution and some techniques for the construction of upper and lower solutions are obtained, and numerical results for a two‐point boundary‐value problem with known analytical solution are given. © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17:347–368, 2001     

A full multigrid method for semilinear elliptic equation

A full multigrid finite element method is proposed for semilinear elliptic equations. The main idea is to transform the solution of the semilinear problem into a series of solutions of the corresponding linear boundary value problems on the sequence of finite element spaces and semilinear problems on a very low dimensional space. The linearized boundary value problems are solved by some multigrid iterations. Besides the multigrid iteration, all other efficient numerical methods can also serve as the linear solver for solving boundary value problems. The optimality of the computational work is also proved. Compared with the existing multigrid methods which need the bounded second order derivatives of the nonlinear term, the proposed method only needs the Lipschitz continuation in some sense of the nonlinear term.     

A Class of Explicit Exponential General Linear Methods

In this paper, we consider a class of explicit exponential integrators that includes as special cases the explicit exponential Runge–Kutta and exponential Adams–Bashforth methods. The additional freedom in the choice of the numerical schemes allows, in an easy manner, the construction of methods of arbitrarily high order with good stability properties. We provide a convergence analysis for abstract evolution equations in Banach spaces including semilinear parabolic initial-boundary value problems and spatial discretizations thereof. From this analysis, we deduce order conditions which in turn form the basis for the construction of new schemes. Our convergence results are illustrated by numerical examples. AMS subject classification (2000) 65L05, 65L06, 65M12, 65J10     

Q-learning and policy iteration algorithms for stochastic shortest path problems

We consider the stochastic shortest path problem, a classical finite-state Markovian decision problem with a termination state, and we propose new convergent Q-learning algorithms that combine elements of policy iteration and classical Q-learning/value iteration. These algorithms are related to the ones introduced by the authors for discounted problems in Bertsekas and Yu (Math. Oper. Res. 37(1):66-94, 2012). The main difference from the standard policy iteration approach is in the policy evaluation phase: instead of solving a linear system of equations, our algorithm solves an optimal stopping problem inexactly with a finite number of value iterations. The main advantage over the standard Q-learning approach is lower overhead: most iterations do not require a minimization over all controls, in the spirit of modified policy iteration. We prove the convergence of asynchronous deterministic and stochastic lookup table implementations of our method for undiscounted, total cost stochastic shortest path problems. These implementations overcome some of the traditional convergence difficulties of asynchronous modified policy iteration, and provide policy iteration-like alternative Q-learning schemes with as reliable convergence as classical Q-learning. We also discuss methods that use basis function approximations of Q-factors and we give an associated error bound.     

A quadrature finite element method for semilinear second‐order hyperbolic problems

In this work we propose and analyze a fully discrete modified Crank–Nicolson finite element (CNFE) method with quadrature for solving semilinear second‐order hyperbolic initial‐boundary value problems. We prove optimal‐order convergence in both time and space for the quadrature‐modified CNFE scheme that does not require nonlinear algebraic solvers. Finally, we demonstrate numerically the order of convergence of our scheme for some test problems. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2008     

解一类半线性外边值问题的自然边界元与有限元耦合法

In this paper, we combine a finite element approach with the natural boundary element method to stduy the weak solvability and Galerkin approximations of a class of semilinear exterior boundary value problems. Our analysis is mainly based on the variational formulation with constraints. We discuss the error estimate of the finite element solution and obtain the asymptotic rate of convergence O（h^n) Finally, we also give two numerical examples.     

Convergence properties of a class of boundary element approximations to linear diffusion problems with localized nonlinear reactions

We consider a boundary element (BE) Algorithm for solving linear diffusion desorption problems with localized nonlinear reactions. The proposed BE algorithm provides an elegant representation of the effect of localized nonlinear reactions, which enables the effects of arbitrarily oriented defect structures to be incorporated into BE models without having to perform severe mesh deformations. We propose a one-step recursion procedure to advance the BE solution of linear diffusion localized nonlinear reaction problems and investigate its convergence properties. The separation of the linear and nonlinear effects by the boundary integral formulation enables us to consider the convergence properties of approximations to the linear terms and nonlinear terms of the boundary integral equation separately. For the linear terms we investigate how the degree of piecewise polynomial collocation in space and the size of the spatial mesh relative to the time step affects the accumulation of errors in the one-step recursion scheme. We develop a novel convergence analysis that combines asymptotic methods with Lax's Equivalence Theorem. We identify a dimensionless meshing parameter θ whose magnitudé governs the performance of the one-step BE schemes. In particular, we show that piecewise constant (PWC) and piecewise linear (PWL) BE schemes are conditionally convergent, have lower asymptotic bounds placed on the size of time steps, and which display excess numerical diffusion when small time steps are used. There is no asymptotic bound on how large the tie steps can be–this allows the solution to be advanced in fewer, larger time steps. The piecewise quadratic (PWQ) BE scheme is shown to be unconditionally convergent; there is no asymptotic restriction on the relative sizes of the time and spatial meshing and no numerical diffusion. We verify the theoretical convergence properties in numerical examples. This analysis provides useful information about the appropriate degree of spatial piecewise polynomial and the meshing strategy for a given problem. For the nonlinear terms we investigate the convergence of an explicit algorithm to advance the solution at an active site forward in time by means of Caratheodory iteration combined with piecewise linear interpolation. We consider a model problem comprising a singular nonlinear Volterra equation that represents the effect of the term in the BE formulation that is due to a single defect. We prove the convergence of the piecewise linear Caratheodory iteration algorithm to a solution of the model problem for as long as such a solution can be shown to exist. This analysis provides a theoretical justification for the use of piecewise linear Caratheodory iterates for advancing the effects of localized reactions.     

A fast BIE iteration method for an arbitrary body in a flow of incompressible inviscid fluid

The paper is concerned with the new iteration algorithm to solve boundary integral equations arising in boundary value problems of mathematical physics. The stability of the algorithm is demonstrated on the problem of a flow around bodies placed in the incompressible inviscid fluid. With a discrete numerical treatment, we approximate the exact matrix by a certain Töeplitz one and then apply a fast algorithm for this matrix, on each iteration step. We illustrate the convergence of this iteration scheme by a number of numerical examples, both for hard and soft boundary conditions. It appears that the method is highly efficient for hard boundaries, being much less efficient for soft boundaries.     

On the coupled NBEM and FEM for a class of nonlinear exterior Dirichlet problem in R 2

In this paper, based on the natural boundary reduction advanced by Feng and Yu, we couple the finite element approach with the natural boundary element method to study the weak solvability and Galerkin approximation of a class of nonlinear exterior boundary value problems. The analysis is mainly based on the variational formulation with constraints. We prove the error estimate of the finite element solution and obtain the asymptotic rate of convergence. Finally, we also give a numerical example.

     

A Parameter-Uniform B-Spline Collocation Method for Singularly Perturbed Semilinear Reaction-Diffusion Problems

We consider a Dirichlet boundary value problem for a class of singularly perturbed semilinear reaction-diffusion equations. A  B-spline collocation method on a piecewise-uniform Shishkin mesh is developed to solve such problems numerically. The convergence analysis is given and the method is shown to be almost second-order convergent, uniformly with respect to the perturbation parameter ε in the maximum norm. Numerical results are presented to validate the theoretical results.     

Accelerating the cubic regularization of Newton’s method on convex problems

In this paper we propose an accelerated version of the cubic regularization of Newton’s method (Nesterov and Polyak, in Math Program 108(1): 177–205, 2006). The original version, used for minimizing a convex function with Lipschitz-continuous Hessian, guarantees a global rate of convergence of order \(O\big({1 \over k^2}\big)\), where k is the iteration counter. Our modified version converges for the same problem class with order \(O\big({1 \over k^3}\big)\), keeping the complexity of each iteration unchanged. We study the complexity of both schemes on different classes of convex problems. In particular, we argue that for the second-order schemes, the class of non-degenerate problems is different from the standard class.     

Das Differenzenverfahren für singuläre Rand-Eigenwertaufgaben gewöhnlicher Differentialgleichungen

Summary The boundary value problem for a class of singular second order differential operators is defined. Using the standard three point discretisation for the differential equation and taking care of the limits involved in the boundary conditions in a natural way, finite difference approximations to the boundary value problems are defined and their convergence properties are investigated. The rate of convergence is given in terms of the data. It turns out that for problems of the first kind extrapolation is possible up to an arbitrary order after a suitable change of the independent variable, whereas for problems of the second kind neither theoretical nor numerical results indicate the possibility of extrapolation. Corresponding results hold for the eigenvalue problems. Some numerical examples show that the convergence rates given in the paper are best possible and demonstrate the effect of extrapolation.     

Multisplitting Iteration Schemes for Solving a Class of Nonlinear Complementarity Problems

We consider several synchronous and asynchronous multisplitting iteration schemes for solving aclass of nonlinear complementarity problems with the system matrix being an H-matrix.We establish theconvergence theorems for the schemes.The numerical experiments show that the schemes are efficient forsolving the class of nonlinear complementarity problems.     

Galerkin-Chebyshev spectral method and block boundary value methods for two-dimensional semilinear parabolic equations

In this paper, we present a high-order accurate method for two-dimensional semilinear parabolic equations. The method is based on a Galerkin-Chebyshev spectral method for discretizing spatial derivatives and a block boundary value methods of fourth-order for temporal discretization. Our formulation has high-order accurate in both space and time. Optimal a priori error bound is derived in the weighted \(L^{2}_{\omega }\)-norm for the semidiscrete formulation. Extensive numerical results are presented to demonstrate the convergence properties of the method.     

Numerical methods for coupled systems of quasilinear elliptic equations with nonlinear boundary conditions

This paper is concerned with numerical solutions of a coupled system of arbitrary number of quasilinear elliptic equations under combined Dirichlet and nonlinear boundary conditions. A finite difference system for a transformed system of the quasilinear equations is formulated, and three monotone iterative schemes for the computation of numerical solutions are given using the method of upper and lower solutions. It is shown that each of the three monotone iterations converges to a minimal solution or a maximal solution depending on whether the initial iteration is a lower solution or an upper solution. A comparison result among the three iterative schemes is given. Also shown is the convergence of the minimal and maximal discrete solutions to the corresponding minimal and maximal solutions of the continuous system as the mesh size tends to zero. These results are applied to a heat transfer problem with temperature dependent thermal conductivity and a Lotka-Volterra cooperation system with degenerate diffusion. This degenerate property leads to some interesting distinct property of the system when compared with the non-degenerate semilinear systems. Numerical results are given to the above problems, and in each problem an explicit continuous solution is constructed and is used to compare with the computed solution     

Piecewise polynomial collocation for linear boundary value problems of fractional differential equations

We consider a class of boundary value problems for linear multi-term fractional differential equations which involve Caputo-type fractional derivatives. Using an integral equation reformulation of the boundary value problem, some regularity properties of the exact solution are derived. Based on these properties, the numerical solution of boundary value problems by piecewise polynomial collocation methods is discussed. In particular, we study the attainable order of convergence of proposed algorithms and show how the convergence rate depends on the choice of the grid and collocation points. Theoretical results are verified by two numerical examples.