Newton-Noda iteration for finding the Perron pair of a weakly irreducible nonnegative tensor

Abstract

We present a Newton-Noda iteration (NNI) for computing the Perron pair of a weakly irreducible nonnegative mth-order tensor A, by combining the idea of Newton's method with the idea of the Noda iteration. The method requires the selection of a positive parameter theta(k) in the kth iteration, and produces a scalar sequence approximating the spectral radius of A and a positive vector sequence approximating the Perron vector. We propose a halving procedure to determine the parameters theta(k), starting with theta(k) for each k, such that the scalar sequence is monotonically decreasing. Convergence of this sequence to the spectral radius of A (and convergence of the vector sequence to the Perron vector) is guaranteed for any initial positive unit vector, as long as the sequence {theta(k)} so chosen is bounded below by a positive constant. In this case, we always have theta(k) = 1 near convergence and the convergence is quadratic. Very often, the halving procedure will return theta(k)(= 1 i.e., no halving is actually used) for each k. If the tensor is semisymmetric, m >= 4, and theta(k) = 1, then the computational work in the kth iteration of NNI is roughly the same as that for one iteration of the Ng-Qi-Zhou algorithm, which is linearly convergent for the smaller class of weakly primitive tensors.