Convergence analysis of modified Newton-HSS method for solving systems of nonlinear equations

Hermitian and skew-Hermitian splitting(HSS) method has been proved quite successfully in solving large sparse non-Hermitian positive definite systems of linear equations. Recently, by making use of HSS method as inner iteration, Newton-HSS method for solving the systems of nonlinear equations with non-Hermitian positive definite Jacobian matrices has been proposed by Bai and Guo. It has shown that the Newton-HSS method outperforms the Newton-USOR and the Newton-GMRES iteration methods. In this paper, a class of modified Newton-HSS methods for solving large systems of nonlinear equations is discussed. In our method, the modified Newton method with R-order of convergence three at least is used to solve the nonlinear equations, and the HSS method is applied to approximately solve the Newton equations. For this class of inexact Newton methods, local and semilocal convergence theorems are proved under suitable conditions. Moreover, a globally convergent modified Newton-HSS method is introduced and a basic global convergence theorem is proved. Numerical results are given to confirm the effectiveness of our method.     

On the convergence of inexact Newton methods for discrete-time algebraic Riccati equations

In this paper, we present a convergence analysis of the inexact Newton method for solving Discrete-time algebraic Riccati equations (DAREs) for large and sparse systems. The inexact Newton method requires, at each iteration, the solution of a symmetric Stein matrix equation. These linear matrix equations are solved approximatively by the alternating directions implicit (ADI) or Smith?s methods. We give some new matrix identities that will allow us to derive new theoretical convergence results for the obtained inexact Newton sequences. We show that under some necessary conditions the approximate solutions satisfy some desired properties such as the d-stability. The theoretical results developed in this paper are an extension to the discrete case of the analysis performed by Feitzinger et al. (2009) [8] for the continuous-time algebraic Riccati equations. In the last section, we give some numerical experiments.     

A Level-Value Estimation Method and Stochastic Implementation for Global Optimization

In this paper, we propose a new method, namely the level-value estimation method, for finding global minimizer of continuous optimization problem. For this purpose, we define the variance function and the mean deviation function, both depend on a level value of the objective function to be minimized. These functions have some good properties when Newton’s method is used to solve a variance equation resulting by setting the variance function to zero. We prove that the largest root of the variance equation equals the global minimal value of the corresponding optimization problem. We also propose an implementable algorithm of the level-value estimation method where importance sampling is used to calculate integrals of the variance function and the mean deviation function. The main idea of the cross-entropy method is used to update the parameters of sample distribution at each iteration. The implementable level-value estimation method has been verified to satisfy the convergent conditions of the inexact Newton method for solving a single variable nonlinear equation. Thus, convergence is guaranteed. The numerical results indicate that the proposed method is applicable and efficient in solving global optimization problems.     

一类非线性方程组的Newton-PSS迭代法

正定反Hermite分裂(PSS)方法是求解大型稀疏非Hermite正定线性代数方程组的一类无条件收敛的迭代算法.将其作为不精确Newton方法的内迭代求解器,我们构造了一类用于求解大型稀疏且具有非Hermite正定Jacobi矩阵的非线性方程组的不精确Newton-PSS方法,并对方法的局部收敛性和半局部收敛性进行了详细的分析.数值结果验证了该方法的可行性与有效性.     

Convergence of a generalized Newton and an inexact generalized Newton algorithms for solving nonlinear equations with nondifferentiable terms

In this paper, we consider two versions of the Newton-type method for solving a nonlinear equations with nondifferentiable terms, which uses as iteration matrices, any matrix from B-differential of semismooth terms. Local and global convergence theorems for the generalized Newton and inexact generalized Newton method are proved. Linear convergence of the algorithms is obtained under very mild assumptions. The superlinear convergence holds under some conditions imposed on both terms of equation. Some numerical results indicate that both algorithms works quite well in practice.      

一类变形的牛顿法求解矩阵平方根

提出一些改进的方法来计算矩阵A的平方根,也就是应用一些牛顿法的变形来解决二次矩阵方程．研究表明,改进的方法比牛顿算法和一些已有的牛顿算法的变形效果要好．通过迭代方法,举出一些数值例子说明改进的方法的性能．     

Convergence rates for Kaczmarz-type algorithms

By making use of the normal and skew-Hermitian splitting (NSS) method as the inner solver for the modified Newton method, we establish a class of modified Newton-NSS method for solving large sparse systems of nonlinear equations with positive definite Jacobian matrices at the solution points. Under proper conditions, the local convergence theorem is proved. Furthermore, the successive-overrelaxation (SOR) technique has been proved quite successfully in accelerating the convergence rate of the NSS or the Hermitian and skew-Hermitian splitting (HSS) iteration method, so we employ the SOR method in the NSS iteration, and we get a new method, which is called modified Newton SNSS method. Numerical results are given to examine its feasibility and effectiveness.     

Monotone convergence of Newton-like methods for M-matrix algebraic Riccati equations

For the algebraic Riccati equation whose four coefficient matrices form a nonsingular M-matrix or an irreducible singular M-matrix K, the minimal nonnegative solution can be found by Newton’s method and the doubling algorithm. When the two diagonal blocks of the matrix K have both large and small diagonal entries, the doubling algorithm often requires many more iterations than Newton’s method. In those cases, Newton’s method may be more efficient than the doubling algorithm. This has motivated us to study Newton-like methods that have higher-order convergence and are not much more expensive each iteration. We find that the Chebyshev method of order three and a two-step modified Chebyshev method of order four can be more efficient than Newton’s method. For the Riccati equation, these two Newton-like methods are actually special cases of the Newton–Shamanskii method. We show that, starting with zero initial guess or some other suitable initial guess, the sequence generated by the Newton–Shamanskii method converges monotonically to the minimal nonnegative solution.We also explain that the Newton-like methods can be used to great advantage when solving some Riccati equations involving a parameter.     

Split Newton iterative algorithm and its application

Inspired by some implicit-explicit linear multistep schemes and additive Runge-Kutta methods, we develop a novel split Newton iterative algorithm for the numerical solution of nonlinear equations. The proposed method improves computational efficiency by reducing the computational cost of the Jacobian matrix. Consistency and global convergence of the new method are also maintained. To test its effectiveness, we apply the method to nonlinear reaction-diffusion equations, such as Burger’s-Huxley equation and fisher’s equation. Numerical examples suggest that the involved iterative method is much faster than the classical Newton’s method on a given time interval.     

解非线性不适定算子方程的一种正则化Newton迭代法

本文探讨一种求解非线性不适定算子方程的正则化Newton迭代法.本文讨论了这种迭代法在一般条件下的收敛性以及其他的一些性质.这种迭代法结合确定迭代次数的残差准则有局部收敛性.     

A modified quasi‐Newton diagonal update algorithm for total variation denoising problems and nonlinear monotone equations with applications in compressive sensing

In this paper, we present a new algorithm to accelerate the Chambolle gradient projection method for total variation image restoration. The new proposed method considers an approximation of the Hessian based on the secant equation. Combined with the quasi‐Cauchy equations and diagonal updating, we can obtain a positive definite diagonal matrix. In the proposed minimization method model, we use the positive definite diagonal matrix instead of the constant time stepsize in Chambolle's method. The global convergence of the proposed scheme is proved. Some numerical results illustrate the efficiency of this method. Moreover, we also extend the quasi‐Newton diagonal updating method to solve nonlinear systems of monotone equations. Performance comparisons show that the proposed method is efficient. A practical application of the monotone equations is shown and tested on sparse signal reconstruction in compressed sensing. Copyright © 2015 John Wiley & Sons, Ltd.     

Global convergence and the Powell singular function

The Powell singular function was introduced 1962 by M.J.D. Powell as an unconstrained optimization problem. The function is also used as nonlinear least squares problem and system of nonlinear equations. The function is a classic test function included in collections of test problems in optimization as well as an example problem in text books. In the global optimization literature the function is stated as a difficult test case. The function is convex and the Hessian has a double singularity at the solution. In this paper we consider Newton’s method and methods in Halley class and we discuss the relationship between these methods on the Powell Singular Function. We show that these methods have global but linear rate of convergence. The function is in a subclass of unary functions and results for Newton’s method and methods in the Halley class can be extended to this class. Newton’s method is often made globally convergent by introducing a line search. We show that a full Newton step will satisfy many of standard step length rules and that exact line searches will yield slightly faster linear rate of convergence than Newton’s method. We illustrate some of these properties with numerical experiments.     

一类弱非线性方程组的Picard-MHSS迭代方法

修正的Hermite/反Hermite分裂(MHSS)迭代方法是一类求解大型稀疏复对称线性代数方程组的无条件收敛的迭代算法.基于非线性代数方程组的特殊结构和性质,我们选取Picard迭代为外迭代方法,MHSS迭代作为内迭代方法,构造了求解大型稀疏弱非线性代数方程组的Picard-MHSS和非线性MHSS-like方法.这两类方法的优点是不需要在每次迭代时均精确计算和存储Jacobi矩阵,仅需要在迭代过程中求解两个常系数实对称正定子线性方程组.除此之外,在一定条件下,给出了两类方法的局部收敛性定理.数值结果证明了这两类方法是可行、有效和稳健的.     

A new single-step iteration method for solving complex symmetric linear systems

For solving a class of complex symmetric linear systems, we introduce a new single-step iteration method, which can be taken as a fixed-point iteration adding the asymptotical error (FPAE). In order to accelerate the convergence, we further develop the parameterized variant of the FPAE (PFPAE) iteration method. Each iteration of the FPAE and the PFPAE methods requires the solution of only one linear system with a real symmetric positive definite coefficient matrix. Under suitable conditions, we derive the spectral radius of the FPAE and the PFPAE iteration matrices, and discuss the quasi-optimal parameters which minimize the above spectral radius. Numerical tests support the contention that the PFPAE iteration method has comparable advantage over some other commonly used iteration methods, particularly when the experimental optimal parameters are not used.     

A nonmonotone Jacobian smoothing inexact Newton method for NCP

In this paper we propose Jacobian smoothing inexact Newton method for nonlinear complementarity problems (NCP) with derivative-free nonmonotone line search. This nonmonotone line search technique ensures globalization and is a combination of Grippo-Lampariello-Lucidi (GLL) and Li-Fukushima (LF) strategies, with the aim to take into account their advantages. The method is based on very well known Fischer-Burmeister reformulation of NCP and its smoothing Kanzow’s approximation. The mixed Newton equation, which combines the semismooth function with the Jacobian of its smooth operator, is solved approximately in every iteration, so the method belongs to the class of Jacobian smoothing inexact Newton methods. The inexact search direction is not in general a descent direction and this is the reason why nonmonotone scheme is used for globalization. Global convergence and local superlinear convergence of method are proved. Numerical performances are also analyzed and point out that high level of nonmonotonicity of this line search rule enables robust and efficient method.     

Local convergence analysis of several inexact Newton-type algorithms for general nonlinear eigenvalue problems

We study the local convergence of several inexact numerical algorithms closely related to Newton’s method for the solution of a simple eigenpair of the general nonlinear eigenvalue problem $T(\lambda )v=0$ . We investigate inverse iteration, Rayleigh quotient iteration, residual inverse iteration, and the single-vector Jacobi–Davidson method, analyzing the impact of the tolerances chosen for the approximate solution of the linear systems arising in these algorithms on the order of the local convergence rates. We show that the inexact algorithms can achieve the same order of convergence as the exact methods if appropriate sequences of tolerances are applied to the inner solves. We discuss the connections and emphasize the differences between the standard inexact Newton’s method and these inexact algorithms. When the local symmetry of $T(\lambda )$ is present, the use of a nonlinear Rayleigh functional is shown to be fundamental in achieving higher order of convergence rates. The convergence results are illustrated by numerical experiments.     

二次四元数系统正定解的迭代法

二次四元数系统XAX?BX=P是离散型Lyapunov方程正定解反问题的推广形式.本文在四元数体上讨论它的正定解存在性及迭代求解方法.利用等价二次方程的系数矩阵的极大极小特征值,获得其正定解的存在区间,并针对系数矩阵的不同情况构建出三种收敛的迭代格式.同时根据每种迭代的特点,给出了迭代初始矩阵的选取方法.最后通过四元数矩阵复算子实现Matlab环境下求解.数值算例验证了所给方法的有效及可行性.     

Multigrid method for nonlinear integral equations

In this paper, we introduce a multigrid method for solving the nonliear Urysohn integral equation. The algorithm is derived from a discrete resolvent equation which approximates the continuous resolvent equation of the nonlinear Urysohn integral equation. The algorithm is mathematically equivalent to Atkinson’s adaptive twogrid iteration. But the two are different computationally. We show the convergence of the algorithm and its equivalence to Atkinson’s adaptive twogrid iteration. In our numerical example, we compare our algorithm to other multigrid methods for solving the nonliear Urysohn integral equation including the nonlinear multigrid method introduced by Hackbush.     

A variable metric Proximal-Descent Algorithm for monotone operators

In this paper, we discuss a variable metric Proximal-Descent Algorithm for finding a zero of any given maximal monotone operator. At each iteration, it first implements a proximal step and then a descent step to locate the new iterate. In the proximal step, we have replaced the regularization parameter by some positive definite matrix, which may vary from iteration to iteration. Under standard assumptions, we prove its global convergence without the matrix??s symmetry. Some key aspects of the algorithm??s applications are discussed. Preliminary numerical experiments show the efficiency in practical implementations.     

Residual methods for the large-scale matrix pth root and some related problems

The problem of finding the pth root of a matrix has received special attention in the last few years. Standard approaches for this problem include and combine some variations of Newton’s method, which in turn involve matrix factorizations that, in general, are not suitable for large-scale problems. Motivated by some recently developed low-cost iterative schemes for nonlinear problems, we consider and analyze specialized residual methods that only require a few matrix-matrix products per iteration, and hence are suitable for the large-scale case. As a by-product we also discuss the advantages of residual methods for general nonlinear problems whose variables separate. Preliminary and encouraging numerical results are presented for computing pth roots of large-scale symmetric and positive definite matrices, for different values of p.