Second-order iterations with guaranteed convergence

Recent results on optimal extrapolations of first-order stationary iterations have shown that they are necessarily divergent in a wide class of problems. This paper examines a second-order iterative process which is guaranteed to converge — in particular when applied to the solution of an arbitrary equation system. A general convergence theory for semi-iterative techniques is established at the same time.     

On the guaranteed convergence of new two-point root-finding methods for polynomial zeros

We presented new two-point methods for the simultaneous approximation of all n simple (real or complex) zeros of a polynomial of degree n. We proved that the R-order of convergence of the total-step version is three. Moreover, computationally verifiable initial conditions that guarantee the convergence of one of the proposed methods are stated. These conditions are stated in the spirit of Smale’s point estimation theory; they depend only on available data, the polynomial coefficients, polynomial degree n and initial approximations \(x_{1}^{(0)},\ldots ,x_{n}^{(0)}\) , which is of practical importance. Using the Gauss-Seidel approach we state the corresponding single-step version and consequently its prove that the lower bound of its R-order of convergence is at least 2 + y _n > 3, where y _n ∈ (1, 2) is the unique positive root of the equation y ⁿ ? y ? 2 = 0. Two numerical examples are given to demonstrate the convergence behavior of the considered methods, including global convergence.     

An infinite precision bracketing algorithm with guaranteed convergence

The computational cost of a bracketing algorithm in the bit model of computation is analyzed, when working with a finite arithmetic of unbounded accuracy. The complexity measure used here is the number of bit operations, seen as a function of the required absolute error of the result. In this model the convergence of the classical bisection method (as well as that of any bracketing method which requires the function sign) is not ensured when no information on the behaviour of the function is available. A modified bisection algorithm with guaranteed convergence is proposed and an upper bound to its computational cost is given.     

Line search methods with guaranteed asymptotical convergence to an improving local optimum of multimodal functions

This paper considers line search optimization methods using a mathematical framework based on the simple concept of a v-pattern and its properties. This framework provides theoretical guarantees on preserving, in the localizing interval, a local optimum no worse than the starting point. Notably, the framework can be applied to arbitrary unidimensional functions, including multimodal and infinitely valued ones. Enhanced versions of the golden section, bisection and Brent’s methods are proposed and analyzed within this framework: they inherit the improving local optimality guarantee. Under mild assumptions the enhanced algorithms are proved to converge to a point in the solution set in a finite number of steps or that all their accumulation points belong to the solution set.     

A new general form of conjugate gradient methods with guaranteed descent and strong global convergence properties

Although the study of global convergence of the Polak–Ribière–Polyak (PRP), Hestenes–Stiefel (HS) and Liu–Storey (LS) conjugate gradient methods has made great progress, the convergence of these algorithms for general nonlinear functions is still erratic, not to mention under weak conditions on the objective function and weak line search rules. Besides, it is also interesting to investigate whether there exists a general method that converges under the standard Armijo line search for general nonconvex functions, since very few relevant results have been achieved. So in this paper, we present a new general form of conjugate gradient methods whose theoretical significance is attractive. With any formula β _k  ≥ 0 and under weak conditions, the proposed method satisfies the sufficient descent condition independently of the line search used and the function convexity, and its global convergence can be achieved under the standard Wolfe line search or even under the standard Armijo line search. Based on this new method, convergence results on the PRP, HS, LS, Dai–Yuan–type (DY) and Conjugate–Descent–type (CD) methods are established. Preliminary numerical results show the efficiency of the proposed methods.     

Interval arithmetic for guaranteed bounds in linear programming

In this note, we show how interval arithmetic can be used to give a solution to the linear programming problem which is guaranteed to be on the safe side of the true solution, where roundoff error is taken into account.This research was supported in part by the National Research Council of Canada.     

Ostrowski-type theorems for harmonic functions

Ostrowski showed that there are intimate connections between the gap structure of a Taylor series and the behaviour of its partial sums outside the disk of convergence. This paper investigates the corresponding problem for the homogeneous polynomial expansion of a harmonic function. The results for harmonic functions display new features in the case of higher dimensions.     

Multiplier convergence in trust-region methods with application to convergence of decomposition methods for MPECs

We study piecewise decomposition methods for mathematical programs with equilibrium constraints (MPECs) for which all constraint functions are linear. At each iteration of a decomposition method, one step of a nonlinear programming scheme is applied to one piece of the MPEC to obtain the next iterate. Our goal is to understand global convergence to B-stationary points of these methods when the embedded nonlinear programming solver is a trust-region scheme, and the selection of pieces is determined using multipliers generated by solving the trust-region subproblem. To this end we study global convergence of a linear trust-region scheme for linearly-constrained NLPs that we call a trust-search method. The trust-search has two features that are critical to global convergence of decomposition methods for MPECs: a robustness property with respect to switching pieces, and a multiplier convergence result that appears to be quite new for trust-region methods. These combine to clarify and strengthen global convergence of decomposition methods without resorting either to additional conditions such as eventual inactivity of the trust-region constraint, or more complex methods that require a separate subproblem for multiplier estimation.      

On Newton-type methods with cubic convergence

Recently, there has been some progress on Newton-type methods with cubic convergence that do not require the computation of second derivatives. Weerakoon and Fernando (Appl. Math. Lett. 13 (2000) 87) derived the Newton method and a cubically convergent variant by rectangular and trapezoidal approximations to Newton's theorem, while Frontini and Sormani (J. Comput. Appl. Math. 156 (2003) 345; 140 (2003) 419 derived further cubically convergent variants by using different approximations to Newton's theorem. Homeier (J. Comput. Appl. Math. 157 (2003) 227; 169 (2004) 161) independently derived one of the latter variants and extended it to the multivariate case. Here, we show that one can modify the Werrakoon–Fernando approach by using Newton's theorem for the inverse function and derive a new class of cubically convergent Newton-type methods.     

超平方收敛的2步法公式

给出3个求解非线性方程的迭代公式,它们均是2步法计算公式,就函数值的计算量来看,它们和Newton法一样,但它们却具有超平方收敛性,其中2个公式的收敛阶约为2．414,另一个公式的收敛阶约为2．732．     

Interval vortex methods

By means of the integral version of vortex equation, the technique of Green's function, and the vorticity‐to‐velocity map, a new kind of interval methods for solving the initial‐periodic boundary value problem of two‐dimensional incompressible Navier–Stokes equation is introduced, which consists of both an approximate scheme and a set of pointwise intervals covering the exact solution. The convergence theorem corresponding to the scheme is proved, and the order of error width for the two‐sided bounds is also considered. Finally, a simple numerical example illustrates our corroboration. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 1368–1396, 2014     

Three-step iterative methods with optimal eighth-order convergence

In this paper, based on Ostrowski’s method, a new family of eighth-order methods for solving nonlinear equations is derived. In terms of computational cost, each iteration of these methods requires three evaluations of the function and one evaluation of its first derivative, so that their efficiency indices are 1.682, which is optimal according to Kung and Traub’s conjecture. Numerical comparisons are made to show the performance of the new family.     

Adaptive boundary element methods with convergence rates

This paper presents adaptive boundary element methods for positive, negative, as well as zero order operator equations, together with proofs that they converge at certain rates. The convergence rates are quasi-optimal in a certain sense under mild assumptions that are analogous to what is typically assumed in the theory of adaptive finite element methods. In particular, no saturation-type assumption is used. The main ingredients of the proof that constitute new findings are some results on a posteriori error estimates for boundary element methods, and an inverse-type inequality involving boundary integral operators on locally refined finite element spaces.     

Interval methods for fixed-point problems

Interval analysis is applied to the fixed-point problem x=?(x) for continuous ?:S→S, where the space S is constructed from Cartesian products of the set R of real numbers, with componentwise definitions of arithmetic operations, ordering, and the product topology. With the aid of an interval inclusion φ:IS → IS in the interval space IS corresponding to S, interval iteration is used to establish the existence or nonexistence of a fixed point x^? of ? in the initial interval X₀. Each step of the interval iteration provides lower and upper bounds for fixed points of ? in the initial interval, from which approximate values and guaranteed error bounds can be obtained directly. In addition to interval iteration, operator equation and dissection methods are considered briefly.

The theory of interval iteration applies directly when only finite subsets of S, IS are used, so this method is adaptable immediately to actual computation. A numerical example is given of the use of interval iteration for the computational solution of a nonlinear integral equation of radiative transfer. It is shown that numerical results with acceptable, guaranteed accuracy can be obtained with a modest amount of computation for an extended range of the parameter involved.     

Interval methods of Adams-Bashforth type with variable step sizes

Numerical Algorithms - In a number of our previous papers, we have proposed interval versions of multistep methods (explicit and implicit), including interval predictor-corrector methods, in which...     

Untypical methods of convergence acceleration

Iterated Aitken’s method is one of classical procedures which permit to accelerate series or sequences convergence. It may be a starting point of constructing better methods in some classes of series whose important parameters are known. Such untypical modifications are here proposed and investigated. They based on a common idea and refer to two kinds of series; cf. Section 2 (series with rational coefficients, hypergeometric series and many others) and Section 3 (so-called quasi-geometric series). The second kind of series is associated with a class of infinite products whose convergence may be also accelerated. Behaviour of Levin’s and Weniger’s methods depends on a parameter β. In Section 4 its role is investigated and possibility of an improvement of their initial steps is showed.     

The convergence of shooting methods

Shooting methods for nonlinear boundary value problems are examined. It is shown that the methods converge whenever the problem is well posed in the sense that the solution to be computed is isolated.     

Local convergence of tensor methods

Mathematical Programming - In this paper, we study local convergence of high-order Tensor Methods for solving convex optimization problems with composite objective. We justify local superlinear...