Let $F:X\to X$ be a nonlinear mapping, where $(X,\parallel \cdot \parallel )$ is a Banach space, and consider the equation

We shall assume that $F$ is a polynomial operator of degree $2$, i.e., it is indefinitely differentiable on $X$, with $F^{\left(i\right)}\left(x\right)={\theta }_i$, for all $x\in X$ and $i\ge 3$, where ${\theta }_i$ is the $i$-linear null operator.

Besides (1) we shall also consider another equation, equivalent with it

where $G:X\to X$. More exactly, we shall assume that the solutions of (1) coincide with the solutions of (2) and viceversa.

In [15] it was shown that the following iterations

have the convergence order with one order higher than the convergence order of the iterates $x_{k+1}=G\left(x_k\right).$

Obviously, if we take as $G$ the Newton operator, i.e.,

then we obtain a method with the convergence order at least $3$.

In the present paper we shall study the convergence of the iterations (3), with $G$ given by (4), i.e.,

in order to solve the polynomial equation (1).

By (5), for some known approximation $x_k$, the next approximation $x_{k+1}$ may be determined as

We notice that at each iteration step we need to solve two linear equations, but for the same linear operator, $F^{\prime }\left(x_k\right)$. The iterations may be viewed as being given by the Newton method in which the Jacobian is evaluated at every two steps.

A possible advantage of the above method over the Chebyshev method

which has the same convergence order, is that it does not require the second derivative of $F$, which may have a complicate form.

The study of such methods for second degree polynomial equations is important, since such equations often arise in practice. We mention the eigenvalue problem (see, e.g., [21], [20]), some integral equations (see, e.g., [2], [8]), etc.

We shall apply this study to the approximation of the eigenpairs of the matrices, and we shall consider some numerical examples for some test matrices. We shall also compare the method (5) to the Chebyshev method.

Since $F$ is a second degree polynomial, one can easily show that

Assuming that $F^{\prime }{\left(x\right)}^{-1}$ exists, denote by $\phi \left(x\right)$ the following expression:

Taking into account (6), we get

For the given norm $\parallel \cdot \parallel$, by (6)–(8) it follows that

Analogously, by (7) and (8), we get for all $x\in X$

Since the bilinear operator $F^{\prime \prime }\left(x\right)$ does not depend on $x$, denote $K=\Vert F^{\prime \prime }\left(x\right)\Vert$.

Let $x_0\in X,$ $r>0$, denote ${\beta }_0=\Vert F^{\prime }{\left(x_0\right)}^{-1}\Vert$, and assume that . Using the Banach lemma, it easily follows that for all $x\in {\overline{B}}_r\left(x_0\right)=\{x\in X:\Vert x-x_0\Vert \le r\}$, there exists $F^{\prime }{\left(x\right)}^{-1}$, and

With the above notations, by (9) and (10) it follows for any $x\in {\overline{B}}_r\left(x_0\right)$ that

Now take

From (12), taking into account (5) and (6), we get

Relations (5) and (13) imply

We obtain the following result regarding the convergence of (5).

We shall study this method when applied to approximate the eigenpairs of matrices.

Denote $V={𝕂}^n$ and let $A\in$ ${𝕂}^{n\times n}$, where $𝕂=ℝ$ or $ℂ.$ For computing the eigenpairs of $A$ one may consider a norming function $G:V\to 𝕂$ with $G\left(0\right)\ne 1.$ The eigenvalues $\lambda \in$ $𝕂$ and eigenvectors $v\in V$ of $A$ are the solutions of the nonlinear system

where $x=\left(\genfrac{}{}{0.0pt}{}{v}{\lambda }\right)\in V\times 𝕂={𝕂}^{n+1},$ $(x^{\left(1\right)},x^{\left(2\right)},\mathrm{\dots },x^{\left(n\right)})=v$ and $x^{\left(n+1\right)}=\lambda$. The first $n$ components of $F$, $F_i$, $i=1,\mathrm{\dots },n$, are given by

The standard choice for $G$ is

with $\alpha =\frac{1}{2}$. We have proposed in [4] (see also [7]), the choice $\alpha =\frac{1}{2n}$, which has shown a better behavior for the iterates than the standard choice.

In both cases we can write

The first and the second order derivatives of $F$ are given by

and

where $x={\left(x^{\left(i\right)}\right)}_{i=1,n+1},h={\left(h^{\left(i\right)}\right)}_{i=1,n+1},k={\left(k^{\left(i\right)}\right)}_{i=1,n+1}\in {𝕂}^{n+1}.$

We shall consider two test matrices from the Harwell Boeing collection¹¹1These matrices are available from MatrixMarket at the following address: http://math.nist.gov/MatrixMarket/. in order to study the behavior of the method (5) and of the Chebyshev method for approximating the eigenpairs. The programs were written in Matlab. As in [21], we used the Matlab operator ’$\backslash$’ for solving the linear systems.

Fidap002 matrix. This real symmetric matrix of dimension $n=441$ arises from finite element modeling. Its eigenvalues are all simple and range from $-7\cdot {10}^8$ to $3\cdot {10}^6$. As in [21], we have chosen to study the smallest eigenvalue, which is well separated. The initial approximations were taken ${\lambda }_0={\lambda }^{\ast }+{10}^2=-\mathrm{6.999\hspace{0.17em}6}\cdot {10}^8+100$, and for the initial vector $v_0$ we perturbed the solution $v^{\ast }$ (computed by Matlab and then properly scaled to fulfill the norming equation) with random vectors having the components uniformly distributed on (-$\epsilon$,$\epsilon$), $\epsilon =0.5$. The following results are typical for the runs made (we have considered a common perturbation vector); Table 1 contains the norms of the vectors $F(x_k)$. For the choice I, we took $a=\frac{1}{2}$ in $G$, while for the choice II, $a=\frac{1}{2n}$.

It is interesting to note that the norm of $F$ (even at the computed solution) does not decrease below ${10}^{-8}$.

Sherman1 matrix. This matrix arises from oil reservoir simulation. It is real, unsymmetric, of dimension 1000 and all its eigenvalues are real. We have chosen to study the smallest eigenvalue ${\lambda }^{\ast }=-5.0449$, which is not well separated (the closest eigenvalue is $-4.9376$). The initial approximation was taken ${\lambda }_0={\lambda }^{\ast }-0.002$ and for the initial vector $v_0$ we considered $\epsilon =0.01$.

The following results are typical for the runs made (we have considered again a same random perturbation vector for the four initial approximations).

For this particular matrix and eigenvalue, the Chebyshev method has shown a greater sensitivity to the size of the perturbations than method (5). Increasing $\epsilon$ leads to the loss of the convergence of the Chebyshev iterates, while method (5) still converge.

Though for the Sherman1 matrix method (5) displayed a better behavior than the Chebyshev method, some extensive tests must be performed before affirming that the first method is superior. In any case, the choice II has shown again that is more advantageous to use.