An Improvement of Ostrowski’s and King’s Techniques with Optimal Convergence Order Eight

In this paper, we first establish a new class of three-point methods based on the two-point optimal method of Ostrowski. Analysis of convergence shows that any method of our class arrives at eighth order of convergence by using three evaluations of the function and one evaluation of the first derivative per iteration. Thus, this order agrees with the conjecture of Kung and Traub (J. ACM 643–651, 1974) for constructing multipoint optimal iterations without memory. We second present another optimal eighth-order class based on the King’s fourth-order family and the first attained class. To support the underlying theory developed in this work, we examine some methods of the proposed classes by comparison with some of the existing optimal eighth-order methods in literature. Numerical experience suggests that the new classes would be valuable alternatives for solving nonlinear equations.     

Nonlinear Schwarz iterations with reduced rank extrapolation

Extrapolation methods can be a very effective technique used for accelerating the convergence of vector sequences. In this paper, these methods are used to accelerate the convergence of Schwarz iterative methods for nonlinear problems. A new implementation of the reduced-rank-extrapolation (RRE) method is introduced. Some convergence analysis is presented, and it is shown numerically that certain extrapolation methods can indeed be very effective in accelerating the convergence of Schwarz methods.     

Generalized Qualification and Qualification Levels for Spectral Regularization Methods

The concept of qualification for spectral regularization methods (SRM) for inverse ill-posed problems is strongly associated to the optimal order of convergence of the regularization error (Engl et al. in Regularization of inverse problems. Mathematics and its applications, vol. 375, Kluwer Academic, Dordrecht, 1996; Mathé in SIAM J. Numer. Anal. 42(3):968–973, 2004; Mathé and Pereverzev in Inverse Probl. 19(3):789–803, 2003; Vainikko in USSR Comput. Math. Math. Phys. 22(3): 1–19, 1982). In this article, the definition of qualification is extended and three different levels are introduced: weak, strong and optimal. It is shown that the weak qualification extends the definition introduced by Mathé and Pereverzev (Inverse Probl. 19(3):789–803, 2003), mainly in the sense that the functions associated with orders of convergence and source sets need not be the same. It is shown that certain methods possessing infinite classical qualification (e.g. truncated singular value decomposition (TSVD), Landweber’s method and Showalter’s method) also have generalized qualification leading to an optimal order of convergence of the regularization error. Sufficient conditions for a SRM to have weak qualification are provided and necessary and sufficient conditions for a given order of convergence to be strong or optimal qualification are found. Examples of all three qualification levels are provided and the relationships between them as well as with the classical concept of qualification and the qualification introduced in Mathé and Pereverzev (Inverse Probl. 19(3):789–803, 2003) are shown. In particular, SRMs having extended qualification in each one of the three levels and having zero or infinite classical qualification are presented. Finally, several implications of this theory in the context of orders of convergence, converse results and maximal source sets for inverse ill-posed problems, are shown. This work was supported by DARPA/SPO, NASA LaRC and the National Institute of Aerospace under Grant VT-03-1, 2535, by AFOSR Grants F49620-03-1-0243 and FA9550-07-1-0273, by Consejo Nacional de Investigaciones Científicas y Técnicas, CONICET, and by Universidad Nacional del Litoral, U.N.L., Argentina, through Project CAI+D 2006, P.E. 236.     

A Loss function approach to identifying environmental exceedances

A frequent problem in environmental science is the prediction of extrema and exceedances. It is well known that Bayesian and empirical-Bayesian predictors based on integrated squared error loss (ISEL) tend to overshrink predictions of extrema toward the mean. In this paper, we consider a geostatistical extension of the weighted rank squared error loss function (WRSEL) of Wright et al. (2003), which we call the integrated weighted quantile squared error loss (IWQSEL), as the basis for prediction of exceedances and their spatial location. The loss function is based on an ordering of the underlying spatial process using a spatially averaged cumulative distribution function. We illustrate this methodology with a Bayesian analysis of surface-nitrogen concentrations in the Chesapeake Bay and compare the new IWQSEL predictor with a standard ISEL predictor. We also give a comparison to predicted extrema obtained from a “plug-in” goestatistical analysis. AMS 2000 Subject Classification Primary—62M30; Secondary—62H11     

Dual extrapolation and its applications to solving variational inequalities and related problems

In this paper we suggest new dual methods for solving variational inequalities with monotone operators. We show that with an appropriate step-size strategy, our method is optimal both for Lipschitz continuous operators ( $O({1 \over \epsilon})In this paper we suggest new dual methods for solving variational inequalities with monotone operators. We show that with an appropriate step-size strategy, our method is optimal both for Lipschitz continuous operators ( iterations), and for the operators with bounded variations ( iterations). Our technique can be applied for solving non-smooth convex minimization problems with known structure. In this case the worst-case complexity bound is iterations. The research results presented in this paper have been supported by a grant “Action de recherche concertè ARC 04/09-315” from the “Direction de la recherche scientifique, Communautè fran?aise de Belgique”. The scientific responsibility rests with its author(s).     

On the local convergence of adjoint Broyden methods

The numerical solution of nonlinear equation systems is often achieved by so-called quasi-Newton methods. They preserve the rapid local convergence of Newton’s method at a significantly reduced cost per step by successively approximating the system Jacobian though low-rank updates. We analyze two variants of the recently proposed adjoint Broyden update, which for the first time combines the classical least change property with heredity on affine systems. However, the new update does require, the evaluation of so-called adjoint vectors, namely products of the transposed Jacobian with certain dual direction vectors. The resulting quasi-Newton method is linear contravariant in the sense of Deuflhard (Newton methods for nonlinear equations. Springer, Heidelberg, 2006) and it is shown here to be locally and q-superlinearly convergent. Our numerical results on a range of test problems demonstrate that the new method usually outperforms Newton’s and Broyden’s method in terms of runtime and iterations count, respectively. Partially supported by the DFG Research Center Matheon “Mathematics for Key Technologies”, Berlin and the DFG grant WA 1607/2-1.     

A General Approach to Convergence Properties of Some Methods for Nonsmooth Convex Optimization

Based on the notion of the ε -subgradient, we present a unified technique to establish convergence properties of several methods for nonsmooth convex minimization problems. Starting from the technical results, we obtain the global convergence of: (i) the variable metric proximal methods presented by Bonnans, Gilbert, Lemaréchal, and Sagastizábal, (ii) some algorithms proposed by Correa and Lemaréchal, and (iii) the proximal point algorithm given by Rockafellar. In particular, we prove that the Rockafellar—Todd phenomenon does not occur for each of the above mentioned methods. Moreover, we explore the convergence rate of {||x _k || } and {f(x _k ) } when {x _k } is unbounded and {f(x _k ) } is bounded for the non\-smooth minimization methods (i), (ii), and (iii). Accepted 15 October 1996     

Analysis of a class of nonlinear subdivision schemes and associated multiresolution transforms

This paper is devoted to the convergence and stability analysis of a class of nonlinear subdivision schemes and associated multiresolution transforms. As soon as a nonlinear scheme can be written as a specific perturbation of a linear and convergent subdivision scheme, we show that if some contractivity properties are satisfied, then stability and convergence can be achieved. This approach is applied to various schemes, which give different new results. More precisely, we study uncentered Lagrange interpolatory linear schemes, WENO scheme (Liu et al., J Comput Phys 115:200–212, 1994), PPH and Power-P schemes (Amat and Liandrat, Appl Comput Harmon Anal 18(2):198–206, 2005; Serna and Marquina, J Comput Phys 194:632–658, 2004) and a nonlinear scheme using local spherical coordinates (Aspert et al., Comput Aided Geom Des 20:165–187, 2003). Finally, a stability proof is given for the multiresolution transform associated to a nonlinear scheme of Marinov et al. (2005).     

Quiver Grassmannians associated with string modules

We provide a technique to compute the Euler–Poincaré characteristic of a class of projective varieties called quiver Grassmannians. This technique applies to quiver Grassmannians associated with “orientable string modules”. As an application we explicitly compute the Euler–Poincaré characteristic of quiver Grassmannians associated with indecomposable pre-projective, pre-injective and regular homogeneous representations of an affine quiver of type [(A)\tilde]_p,1\tilde{A}_{p,1}. For p=1, this approach provides another proof of a result due to Caldero and Zelevinsky (in Mosc. Math. J. 6(3):411–429, 2006).     

Linear convergence of epsilon-subgradient descent methods for a class of convex functions

This paper establishes a linear convergence rate for a class of epsilon-subgradient descent methods for minimizing certain convex functions on ℝ ⁿ . Currently prominent methods belonging to this class include the resolvent (proximal point) method and the bundle method in proximal form (considered as a sequence of serious steps). Other methods, such as a variant of the proximal point method given by Correa and Lemaréchal, can also fit within this framework, depending on how they are implemented. The convex functions covered by the analysis are those whose conjugates have subdifferentials that are locally upper Lipschitzian at the origin, a property generalizing classical regularity conditions. Received March 29, 1996 / Revised version received March 5, 1999? Published online June 11, 1999     

On local convergence of sequential quadratically-constrained quadratic-programming type methods,with an extension to variational problems

We consider the class of quadratically-constrained quadratic-programming methods in the framework extended from optimization to more general variational problems. Previously, in the optimization case, Anitescu (SIAM J. Optim. 12, 949–978, 2002) showed superlinear convergence of the primal sequence under the Mangasarian-Fromovitz constraint qualification and the quadratic growth condition. Quadratic convergence of the primal-dual sequence was established by Fukushima, Luo and Tseng (SIAM J. Optim. 13, 1098–1119, 2003) under the assumption of convexity, the Slater constraint qualification, and a strong second-order sufficient condition. We obtain a new local convergence result, which complements the above (it is neither stronger nor weaker): we prove primal-dual quadratic convergence under the linear independence constraint qualification, strict complementarity, and a second-order sufficiency condition. Additionally, our results apply to variational problems beyond the optimization case. Finally, we provide a necessary and sufficient condition for superlinear convergence of the primal sequence under a Dennis-Moré type condition. Research of the second author is partially supported by CNPq Grants 300734/95-6 and 471780/2003-0, by PRONEX–Optimization, and by FAPERJ.     

Full asymptotics of spline Petrov–Galerkin methods for some periodic pseudodifferential equations

In this paper we study the existence of a formal series expansion of the error of spline Petrov–Galerkin methods applied to a class of periodic pseudodifferential equations. From this expansion we derive some new superconvergence results as well as alternative proofs of already known weak norm optimal convergence results. As part of the analysis the approximation of integrals of smooth functions multiplied by splines by rectangular rules is analyzed in detail. Finally, some numerical experiments are given to illustrate the applicability of Richardson extrapolation as a means of accelerating the convergence of the methods.     

One-dimensional chemotaxis kinetic model

In this paper, we study a variation of the equations of a chemotaxis kinetic model and investigate it in one dimension. In fact, we use fractional diffusion for the chemoattractant in the Othmar–Dunbar–Alt system (Othmer in J Math Biol 26(3):263–298, 1988). This version was exhibited in Calvez in Amer Math Soc, pp 45–62, 2007 for the macroscopic well-known Keller–Segel model in all space dimensions. These two macroscopic and kinetic models are related as mentioned in Bournaveas, Ann Inst H Poincaré Anal Non Linéaire, 26(5):1871–1895, 2009, Chalub, Math Models Methods Appl Sci, 16(7 suppl):1173–1197, 2006, Chalub, Monatsh Math, 142(1–2):123–141, 2004, Chalub, Port Math (NS), 63(2):227–250, 2006. The model we study here behaves in a similar way to the original model in two dimensions with the spherical symmetry assumption on the initial data which is described in Bournaveas, Ann Inst H Poincaré Anal Non Linéaire, 26(5):1871–1895, 2009. We prove the existence and uniqueness of solutions for this model, as well as a convergence result for a family of numerical schemes. The advantage of this model is that numerical simulations can be easily done especially to track the blow-up phenomenon.     

Anderson acceleration of the alternating projections method for computing the nearest correlation matrix

In a wide range of applications it is required to compute the nearest correlation matrix in the Frobenius norm to a given symmetric but indefinite matrix. Of the available methods with guaranteed convergence to the unique solution of this problem the easiest to implement, and perhaps the most widely used, is the alternating projections method. However, the rate of convergence of this method is at best linear, and it can require a large number of iterations to converge to within a given tolerance. We show that Anderson acceleration, a technique for accelerating the convergence of fixed-point iterations, can be applied to the alternating projections method and that in practice it brings a significant reduction in both the number of iterations and the computation time. We also show that Anderson acceleration remains effective, and indeed can provide even greater improvements, when it is applied to the variants of the nearest correlation matrix problem in which specified elements are fixed or a lower bound is imposed on the smallest eigenvalue. Alternating projections is a general method for finding a point in the intersection of several sets and ours appears to be the first demonstration that this class of methods can benefit from Anderson acceleration.     

非Hermitian正定线性方程组的外推的HSS迭代方法

为了高效地求解大型稀疏非Hermitian正定线性方程组，在白中治、Golub和Ng提出的Hermitian和反Hermitian分裂（HSS）迭代法的基础上，通过引入新的参数并结合迭代法的松弛技术，对HSS迭代方法进行加速，提出了一种新的外推的HSS迭代方法（EHSS），并研究了该方法的收敛性.数值例子表明：通过参数值的选择，新方法比HSS方法具有更快的收敛速度和更少的迭代次数，选择了合适的参数值后，可以提高HSS方法的收敛效率.     

Nonlinear hybrid procedures and fixed point iterations

Let (x_n) and (?_n) be two vector sequences converging to a common limit. First, we shall define nonlinear hybrid procedures which consist of constructing a new vector sequence (y_n) with better convergence properties than (x_n) and (?_n). Then, this procedure is used for accelerating the convergence of a given sequence and applied to the construction of fixed point methods. New methods are derived. Finally, the connection between fixed point iterations and methods for the numerical integration of differential equations is also exploited. Numerical results are given.     

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     

On a class of secant-like methods for solving nonlinear equations

We provide a semilocal convergence analysis for a certain class of secant-like methods considered also in Argyros (J Math Anal Appl 298:374–397, 2004, 2007), Potra (Libertas Mathematica 5:71–84, 1985), in order to approximate a locally unique solution of an equation in a Banach space. Using a combination of Lipschitz and center-Lipschitz conditions for the computation of the upper bounds on the inverses of the linear operators involved, instead of only Lipschitz conditions (Potra, Libertas Mathematica 5:71–84, 1985), we provide an analysis with the following advantages over the work in Potra (Libertas Mathematica 5:71–84, 1985) which improved the works in Bosarge and Falb (J Optim Theory Appl 4:156–166, 1969, Numer Math 14:264–286, 1970), Dennis (SIAM J Numer Anal 6(3):493–507, 1969, 1971), Kornstaedt (1975), Larsonen (Ann Acad Sci Fenn, A 450:1–10, 1969), Potra (L’Analyse Numérique et la Théorie de l’Approximation 8(2):203–214, 1979, Aplikace Mathematiky 26:111–120, 1981, 1982, Libertas Mathematica 5:71–84, 1985), Potra and Pták (Math Scand 46:236–250, 1980, Numer Func Anal Optim 2(1):107–120, 1980), Schmidt (Period Math Hung 9(3):241–247, 1978), Schmidt and Schwetlick (Computing 3:215–226, 1968), Traub (1964), Wolfe (Numer Math 31:153–174, 1978): larger convergence domain; weaker sufficient convergence conditions, finer error bounds on the distances involved, and a more precise information on the location of the solution. Numerical examples further validating the results are also provided.     

On the Vector ε-Algorithm for Solving Linear Systems of Equations

The four vector extrapolation methods, minimal polynomial extrapolation, reduced rank extrapolation, modified minimal polynomial extrapolation and the topological epsilon algorithm, when applied to linearly generated vector sequences are Krylov subspace methods and it is known that they are equivalent to some well-known conjugate gradient type methods. However, the vector -algorithm is an extrapolation method, older than the four extrapolation methods above, and no similar results are known for it. In this paper, a determinantal formula for the vector -algorithm is given. Then it is shown that, when applied to a linearly generated vector sequence, the algorithm is also a Krylov subspace method and for a class of matrices the method is equivalent to a preconditioned Lanczos method. A new determinantal formula for the CGS is given, and an algebraic comparison between the vector -algorithm for linear systems and CGS is also given.     

Revisit of Jarratt method for solving nonlinear equations

In this paper, some sixth-order modifications of Jarratt method for solving single variable nonlinear equations are proposed. Per iteration, they consist of two function and two first derivative evaluations. The convergence analyses of the presented iterative methods are provided theoretically and a comparison with other existing famous iterative methods of different orders is given. Numerical examples include some of the newest and the most efficient optimal eighth-order schemes, such as Petkovic (SIAM J Numer Anal 47:4402–4414, 2010), to put on show the accuracy of the novel methods. Finally, it is also observed that the convergence radii of our schemes are better than the convergence radii of the optimal eighth-order methods.