Two‐step Newton‐type methods for solving inverse eigenvalue problems

In this paper, we apply the two‐step Newton method to solve inverse eigenvalue problems, including exact Newton, Newton‐like, and inexact Newton‐like versions. Our results show that both two‐step Newton and two‐step Newton‐like methods converge cubically, and the two‐step inexact Newton‐like method is super quadratically convergent. Numerical implementations demonstrate the effectiveness of new algorithms.     

BEC类非线性特征值问题的平移对称高阶幂法（英文）

We consider the nonlinear eigenvalue problem(NEP) originated from Bose-Einstein Condensation(BEC)(BEC-like NEP for short).We extend the shifted symmetric higher-order power method(SS-HOPM) proposed by Kolda and Mayo for symmetric tensor eigenvalue to BEC-like NEP.We have shown that given a proper shift term,the Algorithm SS-HOPM is convergent theorically and numerically.We also analyze the influence of data disturbance on eigenvalues theoretically and numerically.     

Cubically convergent methods for selecting the regularization parameters in linear inverse problems

We present three cubically convergent methods for choosing the regularization parameters in linear inverse problems. The detailed algorithms are given and the convergence rates are estimated. Our basic tools are Tikhonov regularization and Morozov's discrepancy principle. We prove that, in comparison with the standard Newton method, the computational costs for our cubically convergent methods are nearly the same, but the number of iteration steps is even less. Numerical experiments for an elliptic boundary value problem illustrate the efficiency of the proposed algorithms.     

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.     

A variant of Newton’s method based on Simpson’s three-eighths rule for nonlinear equations

We propose a new variant of Newton’s method based on Simpson’s three-eighth rule. It can be shown that the new method is cubically convergent.     

Third-order modification of Newton's method

In this paper, we present a new modification of Newton's method for solving non-linear equations. Analysis of convergence shows that the new method is cubically convergent. Numerical examples show that the new method can compete with the classical Newton's method.     

A locally and cubically convergent algorithm for computing 𝒵‐eigenpairs of symmetric tensors

This paper is concerned with computing $\mathrm{??}$‐eigenpairs of symmetric tensors. We first show that computing $\mathrm{??}$‐eigenpairs of a symmetric tensor is equivalent to finding the nonzero solutions of a nonlinear system of equations, and then propose a modified normalized Newton method (MNNM) for it. Our proposed MNNM method is proved to be locally and cubically convergent under some suitable conditions, which greatly improves the Newton correction method and the orthogonal Newton correction method recently provided by Jaffe, Weiss and Nadler since these two methods only enjoy a quadratic rate of convergence. As an application, the unitary symmetric eigenpairs of a complex‐valued symmetric tensor arising from the computation of quantum entanglement in quantum physics are calculated by the MNNM method. Some numerical results are presented to illustrate the efficiency and effectiveness of our method.     

The solution methods for the largest eigenvalue (singular value) of nonnegative tensors and convergence analysis

In this paper we study two solution methods for finding the largest eigenvalue (singular value) of general square (rectangular) nonnegative tensors. For a positive tensor, one can find the largest eigenvalue (singular value) based on the properties of the positive tensor and the power-type method. While for a general nonnegative tensor, we use a series of decreasing positive perturbations of the original tensor and repeatedly recall power-type method for finding the largest eigenvalue (singular value) of a positive tensor with an inexact strategy. We prove the convergence of the method for the general nonnegative tensor. Under a certain assumption, the computing complexity of the method is established. Motivated by the interior-point method for the convex optimization, we put forward a one-step inner iteration power-type method, whose convergence is also established under certain assumption. Additionally, by using embedding technique, we show the relationship between the singular values of the rectangular tensor and the eigenvalues of related square tensor, which suggests another way for finding the largest singular value of nonnegative rectangular tensor besides direct power-type method for this problem. Finally, numerical examples of our algorithms are reported, which demonstrate the convergence behaviors of our methods and show that the algorithms presented are promising.     

Tensor eigenvalue complementarity problems

This paper studies tensor eigenvalue complementarity problems. Basic properties of standard and complementarity tensor eigenvalues are discussed. We formulate tensor eigenvalue complementarity problems as constrained polynomial optimization. When one tensor is strictly copositive, the complementarity eigenvalues can be computed by solving polynomial optimization with normalization by strict copositivity. When no tensor is strictly copositive, we formulate the tensor eigenvalue complementarity problem equivalently as polynomial optimization by a randomization process. The complementarity eigenvalues can be computed sequentially. The formulated polynomial optimization can be solved by Lasserre’s hierarchy of semidefinite relaxations. We show that it has finite convergence for generic tensors. Numerical experiments are presented to show the efficiency of proposed methods.     

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.     

A family of root finding methods

Summary A one parameter family of iteration functions for finding roots is derived. The family includes the Laguerre, Halley, Ostrowski and Euler methods and, as a limiting case, Newton's method. All the methods of the family are cubically convergent for a simple root (except Newton's which is quadratically convergent). The superior behavior of Laguerre's method, when starting from a pointz for which |z| is large, is explained. It is shown that other methods of the family are superior if |z| is not large. It is also shown that a continuum of methods for the family exhibit global and monotonic convergence to roots of polynomials (and certain other functions) if all the roots are real.This research was supported by the National Science Foundation under grant number NSF-DCR-74-10042.     

Finding the Maximum Eigenvalue of Essentially Nonnegative Symmetric Tensors via Sum of Squares Programming

Finding the maximum eigenvalue of a tensor is an important topic in tensor computation and multilinear algebra. Recently, for a tensor with nonnegative entries (which we refer it as a nonnegative tensor), efficient numerical schemes have been proposed to calculate its maximum eigenvalue based on a Perron–Frobenius-type theorem. In this paper, we consider a new class of tensors called essentially nonnegative tensors, which extends the concept of nonnegative tensors, and examine the maximum eigenvalue of an essentially nonnegative tensor using the polynomial optimization techniques. We first establish that finding the maximum eigenvalue of an essentially nonnegative symmetric tensor is equivalent to solving a sum of squares of polynomials (SOS) optimization problem, which, in its turn, can be equivalently rewritten as a semi-definite programming problem. Then, using this sum of squares programming problem, we also provide upper and lower estimates for the maximum eigenvalue of general symmetric tensors. These upper and lower estimates can be calculated in terms of the entries of the tensor. Numerical examples are also presented to illustrate the significance of the results.     

A new zero-finder for Tikhonov regularization

Tikhonov regularization with the regularization parameter determined by the discrepancy principle requires the computation of a zero of a rational function. We describe a cubically convergent zero-finder for this purpose. AMS subject classification (2000)  65F22, 65H05, 65R32     

Computing the generalized eigenvalues of weakly symmetric tensors

Tensor is a hot topic in the past decade and eigenvalue problems of higher order tensors become more and more important in the numerical multilinear algebra. Several methods for finding the Z-eigenvalues and generalized eigenvalues of symmetric tensors have been given. However, the convergence of these methods when the tensor is not symmetric but weakly symmetric is not assured. In this paper, we give two convergent gradient projection methods for computing some generalized eigenvalues of weakly symmetric tensors. The gradient projection method with Armijo step-size rule (AGP) can be viewed as a modification of the GEAP method. The spectral gradient projection method which is born from the combination of the BB method with the gradient projection method is superior to the GEAP, AG and AGP methods. We also make comparisons among the four methods. Some competitive numerical results are reported at the end of this paper.     

求解右定两参数特征值问题的精化Jacobi-Davidson方法(英文)

在文献[1]中,作者M E Hochstenbach和B Plestenjak认为精化的方法不适合两参数特征值问题,原因是求解两参数特征值问题的精化方法存在着三个问题:即精化Ritz向量收敛性差,运算量大,不能计算多个特征值.本文指出,事实并非如此.针对右定两参数特征值问题,本文提出了一种有效的精化数值方法.并通过理论证明和数值实验说明了Ritz值的收敛性,以及精化Ritz向量具有比通常的Ritz向量更好的收敛性.     

An always convergent algorithm for the largest eigenvalue of an irreducible nonnegative tensor

In this paper we propose an iterative method to calculate the largest eigenvalue of a nonnegative tensor. We prove this method converges for any irreducible nonnegative tensor. We also apply this method to study the positive definiteness of a multivariate form.     

An explicit cubic iteration for π

Using the theory of the cubic modular equation we have discovered a remarkably simple class of cubically convergent algebraic iterations for .     

实正规阵乘幂法的改进

本文对实正规阵乘幂法予以改进，给出了一个容易求复特征值的收敛格式     

On the global and cubic convergence of a quasi-cyclic Jacobi method

Summary In this paper we consider the global and the cubic convergence of a quasi-cyclic Jacobi method for the symmetric eigenvalue, problem. The method belongs to a class of quasi-cyclic methods recently proposed by W. Mascarenhas. Mascarenhas showed that the methods from his class asymptotically converge cubically per quasi-sweep (one quasi-sweep is equivalent to 1.25 cyclic sweeps) provided the eigenvalues are simple. Here we prove the global convergence of our method and derive very sharp asymptotic convergence bounds in the general case of multiple eigenvalues. We discuss the ultimate cubic convergence of the method and present several numerical examples which all well comply with the theory.This work was supported in part by the University of Minnesota Army High Performance Computing Research Center and the U.S Army Contract DAAL03-89-C-0038. The paper was partly written while this author was a visiting faculty in the Department of Mathematics, University of Kansas, Lawrence, Kansas. The first version of this paper was made in July 1990 while this author was visiting AHPCRC.     

An Iterative Method for Finding the Least Solution to the Tensor Complementarity Problem

In this paper, we are concerned with finding the least solution to the tensor complementarity problem. When the involved tensor is strongly monotone, we present a way to estimate the nonzero elements of the solution in a successive manner. The procedure for identifying the nonzero elements of the solution gives rise to an iterative method of solving the tensor complementarity problem. In each iteration, we obtain an iterate by solving a lower-dimensional tensor equation. After finitely many iterations, the method terminates with a solution to the problem. Moreover, the sequence generated by the method is monotonically convergent to the least solution to the problem. We then extend this idea for general case and propose a sequential mathematical programming method for finding the least solution to the problem. Since the least solution to the tensor complementarity problem is the sparsest solution to the problem, the method can be regarded as an extension of a recent result by Luo et al. (Optim Lett 11:471–482, 2017). Our limited numerical results show that the method can be used to solve the tensor complementarity problem efficiently.