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     

一个阶为2+\sqrt{6}的Newton改进算法

针对非线性方程求单根问题,提出了一种新的Newton预测-校正格式.通过每步迭代增加计算一个函数值和一阶导数值,使得每步迭代需要估计两个函数值和两个一阶导数值.与标准的Newton算法的二阶收敛速度相比,新算法具有更高阶的收敛速度2+\sqrt{6}.通过测试函数对新算法进行测试, 与相关算法比较,表明算法在迭代次数、运算时间及最优值方面都具有较明显的优势. 最后,将这种新格式推广到多维向量值函数, 采用泰勒公式证明了其收敛性,并给出了两个二维算例来验证其收敛的有效性.     

关于Katz指标的二级分裂迭代方法

本文研究复杂网络中计算Katz指标的迭代法,基于网络拓扑结构,在快速Katz指标算法的基础上,运用二级分裂迭代思想,提出了具有两个参数的二级分裂迭代法,并研究了该方法的收敛性.基于该方法的收缩因子的计算公式,讨论了迭代参数可能的选择,通过参数的选择能有效提高二级迭代法的收敛效率.最后通过数值实例验证了此方法的有效性.     

求複數根的舗D法

<正> 一. 引言 代數方程f(x)=0的實數根的逐步接近法已有多種,其中計算簡單收斂最快的是用牛頓公式     

Construction of Newton-like iteration methods for solving nonlinear equations

In this paper, we present a simple, and yet powerful and easily applicable scheme in constructing the Newton-like iteration formulae for the computation of the solutions of nonlinear equations. The new scheme is based on the homotopy analysis method applied to equations in general form equivalent to the nonlinear equations. It provides a tool to develop new Newton-like iteration methods or to improve the existing iteration methods which contains the well-known Newton iteration formula in logic; those all improve the Newton method. The orders of convergence and corresponding error equations of the obtained iteration formulae are derived analytically or with the help of Maple. Some numerical tests are given to support the theory developed in this paper.     

一种新的修正SR1更新公式及其算法收敛性

SR1更新公式对比其他的拟牛顿更新公式,会更加简单且每次迭代需要更少的计算量。但是一般SR1更新公式的收敛性质是在一致线性无关这一很强的条件下证明的。基于前人的研究成果,提出了一种新的修正SR1公式,并分别证明了其在一致线性无关和没有一致线性无关这两个条件下的局部收敛性,最后通过数值实验验证了提出的更新公式的有效性,以及所作出假设的合理性。根据实验数据显示,在某些条件下基于所提出更新公式的拟牛顿算法会比基于传统的SR1更新公式的算法收敛效果更好一些。     

Quasi Newton techniques generate identical points II: The proofs of four new theorems

This report contains the proofs of four new theorems relating to the behaviour of Broyden's [1] family of variable metric formula for solving unconstrained minimisation problems. In particular, it is shown that if the linear search at each iteration is perfect, then the sequence of points that is generated is independent of the member of the family used at each iteration, provided the matrix remains nonsingular. This result extends Powell's [14] proof of convergence for the original formula on any convex function to all members of the family.     

Analyzing the convergence factor of residual inverse iteration

We will establish here a formula for the convergence factor of the method called residual inverse iteration, which is a method for nonlinear eigenvalue problems and a generalization of the well-known inverse iteration. The formula for the convergence factor is explicit and involves quantities associated with the eigenvalue to which the iteration converges, in particular the eigenvalue and eigenvector. Residual inverse iteration allows for some freedom in the choice of a vector w _k and we can use the formula for the convergence factor to analyze how it depends on the choice of w _k . We also use the formula to illustrate the convergence when the shift is close to the eigenvalue. Finally, we explain the slow convergence for double eigenvalues by showing that under generic conditions, the convergence factor is one, unless the eigenvalue is semisimple. If the eigenvalue is semisimple, it turns out that we can expect convergence similar to the simple case.     

Solving nonlinear equations by a new derivative free iterative method

We develop a new simple iteration formula, which does not require any derivatives of f(x), for solving a nonlinear equation f(x) = 0. It is proved that the convergence order of the new method is quadratic. Furthermore, the new method can approximate complex roots. By several numerical examples we show that the presented method will give desirable approximation to the root without a particularly good initial approximation and be efficient for all cases, regardless of the behavior of f(x).     

Zeno Product Formula Revisited

We introduce a new product formula which combines an orthogonal projection with a complex function of a non-negative operator. Under certain assumptions on the complex function the strong convergence of the product formula is shown. Under more restrictive assumptions even operator-norm convergence is verified. The mentioned formula can be used to describe Zeno dynamics in the situation when the usual non-decay measurement is replaced by a particular generalized observables in the sense of Davies.     

A new finitely convergent algorithm for systems of nonlinear inequalities

In this work, combining the generalized projection techniques with the idea of a strongly sub-feasible direction method, a new algorithm for solving systems of nonlinear inequalities is presented. At each iteration of the proposed algorithm, the search direction is yielded by just one new explicit formula. The proposed algorithm is proved not only to possess global and strong convergence but also to be able to produce a solution in a finite number of iterations. Finally, some interesting numerical results are reported.     

一种新的迭代收敛阶数的证明与推广

迭代方法是求解非线性方程近似根的重要方法.本文基于隐函数存在定理,提出了一种新的迭代方法收敛性和收敛阶数的证明方法,并分别对牛顿(Newton)和柯西(Cauchy)迭代方法迭代收敛性和收敛阶数进行了证明.最后,利用本文提出的证明方法,证明了基于三次泰勒(Taylor)展式构成的迭代格式是收敛的,收敛阶数至少为4,并提出猜想,基于n次泰勒展式构成的迭代格式是收敛的,收敛阶数至少为(n+1).     

关于解椭圆型问题的多子域D-N交替算法

构造一个求解椭圆型边值问题的多子域D—N交替算法，导出对应的容度方程和等价的迭代法，证明算法的收敛性。     

Recurrence Relations for Chebyshev-Type Methods

The convergence of new second-order iterative methods are analyzed in Banach spaces by introducing a system of recurrence relations. A system of a priori error bounds for that method is also provided. The methods are defined by using a constant bilinear operator A , instead of the second Fréchet derivative appearing in the defining formula of the Chebyshev method. Numerical evidence that the methods introduced here accelerate the classical Newton iteration for a suitable A is provided. Accepted 23 October 1998     

Convergence results of Landweber iterations for linear systems

The Landweber scheme is a method for algebraic image reconstructions. The convergence behavior of the Landweber scheme is of both theoretical and practical importance. Using the diagonalization of matrix, we derive a neat iterative representation formula for the Landweber schemes and consequently establish the convergence conditions of Landweber iteration. This work refines our previous convergence results on the Landweber scheme.     

A cubically convergent Newton-type method under weak conditions

Under weak conditions, we present an iteration formula to improve Newton's method for solving nonlinear equations. The method is free from second derivatives, permitting f^′(x)=0 in some points and per iteration it requires two evaluations of the given function and one evaluation of its derivative. Analysis of convergence demonstrates that the new method is cubically convergent. Some numerical examples illustrate that the algorithm is more efficient and performs better than classical Newton's method.     

Complex-extrapolated MHSS iteration method for singular complex symmetric linear systems

In this paper, by extrapolating the modified Hermitian and skew-Hermitian splitting (MHSS) iteration method with a complex relaxation parameter, a complex-extrapolated MHSS (CMHSS) iteration method is present for solving a class of complex singular symmetric of linear equations. We study the semi-convergence properties of the CMHSS iteration method and the extent of the optimal iterative parameters. Furthermore, the convergence conditions also hold for solving nonsingular complex systems. Numerical experiments are given to verify the effectiveness of the CMHSS iteration method for solving both singular and nonsingular complex symmetric systems.     

On a Chebyshev accelerated splitting iteration method with application to two‐by‐two block linear systems

The Chebyshev accelerated preconditioned modified Hermitian and skew‐Hermitian splitting (CAPMHSS) iteration method is presented for solving the linear systems of equations, which have two‐by‐two block coefficient matrices. We derive an iteration error bound to show that the new method is convergent as long as the eigenvalue bounds are not underestimated. Even when the spectral information is lacking, the CAPMHSS iteration method could be considered as an exponentially converging iterative scheme for certain choices of the method parameters. In this case, the convergence rate is independent of the parameters. Besides, the linear subsystems in each iteration can be solved inexactly, which leads to the inexact CAPMHSS iteration method. The iteration error bound of the inexact method is derived also. We discuss in detail the implementation of CAPMHSS for solving two models arising from the Galerkin finite‐element discretizations of distributed control problems and complex symmetric linear systems. The numerical results show the robustness and the efficiency of the new methods.     

Efficient methods for the inclusion of polynomial zeros

Using a suitable zero-relation and the inclusion isotonicity property, new interval iterative methods for the simultaneous inclusion of simple complex zeros of a polynomial are derived. These methods produce disks in the complex plane that contain the polynomial zeros in each iteration, providing in this manner an information about upper error bounds of approximations. Starting from the basic method of the fourth order, two accelerated methods with Newton’s and Halley’s corrections, having the order of convergence five and six respectively, are constructed. This increase of the convergence rate is obtained without any additional operations, which means that the methods with corrections are very efficient. The convergence analysis of the basic method and the methods with corrections is performed under computationally verifiable initial conditions, which is of practical importance. Two numerical examples are presented to demonstrate the convergence behavior of the proposed interval methods.     

关于PageRank的广义二级分裂迭代方法

本文研究计算PageRank的迭代法,在Gleich等人提出的内/外迭代方法的基础上,提出了具有三个参数的广义二级分裂迭代法,该方法包含了内/外迭代法和幂迭代法,并研究了该方法的收敛性.基于该方法的收缩因子的计算公式,讨论了迭代参数可能的选择,通过参数的选择能有效提高内/外迭代法的收敛效率.