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 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.

In the present paper we shall study the convergence of the Chebyshev method

We shall apply this study to the approximation of the eigenpairs of the linear operators in Banach spaces, and we shall consider some numerical examples for some test matrices.

The iterative Chebyshev method for solving equation (1) consists in the successive construction of the elements of the sequence ${\left(x_k\right)}_{k\ge 0}$ given by

where ${\mathrm{\Gamma }}_k=F^{\prime }{\left(x_k\right)}^{-1}.$

Let $x_0\in X$ and $\delta >0,\beta >0$ be two real numbers. Denote $B=B_{\delta }(x_0)=\{x\in X:\Vert x-x_0\Vert \le \delta \}.$ If $K={sup}_{x\in B}\Vert F^{\prime \prime }\left(x\right)\Vert$, then ${sup}_{x\in B}\Vert F^{\prime }\left(x\right)\Vert \le \Vert F^{\prime }\left(x_0\right)\Vert +K\delta$ and

Consider the numbers

With the above notations, the following theorem holds:

Denote by $G:B\to X$ the following mapping:

where $\mathrm{\Gamma }\left(x\right)=F^{\prime }{\left(x\right)}^{-1}.$

It can be easily seen that for all $x\in B$ the following identity holds

whence we obtain

or

Similarly, using (4) and taking into account the notations we made, we get

From the hypotheses of the theorem, the inequality (6) and the fact that $F^{\prime \prime \prime }\left(x\right)={\theta }_3$, we obtain the following inequality:

Since $x_1-x_0=G\left(x_0\right)$, by (6) we have

whence it follows that $x_1\in B$.

Suppose now that the following properties hold:

• a)

  $x_i\in B$, $i=0,\mathrm{\dots },k;$

• b)

  $\Vert F\left(x_i\right)\Vert \le \mu {\Vert F\left(x_{i-1}\right)\Vert }^3,i=1,\mathrm{\dots },k.$

By the fact that $x_k\in B$, using (6) it follows

and from relation $x_{k+1}-x_k=G\left(x_k\right)$

The inequalities b) and (8) lead us to

We have that $x_{k+1}\in B$:

Now we shall prove that the sequence ${\left(x_k\right)}_{k\ge 0}$ is Cauchy. Indeed, for all $m,k\in \mathbb{N}$ we have

whence, taking into account that , it follows that ${\left(x_k\right)}_{k\ge 0}$ converges. Let $x^{\ast }={lim}_{k\to \mathrm{\infty }}{x}_k.$ Then, for $m\to \mathrm{\infty }$ in (11) it follows jv. The consequence jjj follows from (9) and (10).

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 Chebyshev method for approximating the eigenpairs. The programs were written in Matlab. As in [20], 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 modelling. Its eigenvalues (contained on the diagonal of D, after using the Matlab command [V,D]=eig(A)) are all simple and range from $-7\cdot {10}^8$ to $3\cdot {10}^6$. As in [20], we have chosen to study the smallest eigenvalue, ${\lambda }^{\ast }=$D(1,1), which is well separated. Its corresponding eigenvector V(:,1) has the Euclidean norm equal to $1$, and therefore we have $v^{\ast }=$sqrt(2) * V(:,1) for the first choice, respectively $v^{\ast }=$sqrt(2*n) * V(:,1) for the second choice.

It is interesting to note that ${\Vert F(x^{\ast })\Vert }_2=3.7e-7$ in the first case, and ${\Vert F(x^{\ast })\Vert }_2=9.1e-6$ in the second case.

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 }$ with random vectors having the components uniformly distributed on ($-\epsilon$,$\epsilon$), $\epsilon =0.3$. This lead in a relative error $\frac{\Vert x_0-x^{\ast }\Vert }{\Vert x^{\ast }\Vert }=7.0\cdot {10}^1$ in the first case, and $\frac{\Vert x_0-x^{\ast }\Vert }{\Vert x^{\ast }\Vert }=3.3\cdot {10}^0$ in the second one.

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)$.

The values of $\epsilon$ must be decreased to $0.03$ for the iterates with first choice to attain the solution at step $k=2$ (as it does with choice two), while the same $\epsilon$ may be increased to $7$ for the iterates with the second choice to attain the solution at step $k=6$.

Because of the scalings, the components of the eigenvector when taken with the second choice may be affected by larger errors than with the first choice.

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.05$ 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 initial approximations). The relative errors $\frac{\Vert x_0-x^{\ast }\Vert }{\Vert x^{\ast }\Vert }$ for the two choices were $2.65\cdot {10}^{-1}$ resp. $8.38\cdot {10}^{-3}$.

For this particular matrix and eigenvalue, the Chebyshev method has shown a strong sensitivity to the size of the perturbations: increasing $\epsilon$ leads to the loss of the convergence of the Chebyshev iterates.

As it can be seen from both examples, the second choice presents a better behavior than the first one.