Approaches to the problem of approximating the eigenvalues of linear operators by the Newton method have been done in a series of papers ([1], [3], [4], [5]). There is a special interest in using the Newton method because the operatorial equation to be solved has a special form, as we shall see. We shall study in the following the convergence of the Chebyshev method attached to this problem and we shall apply the results obtained for the approximation of an eigenvalue and of a corresponding eigenvector for a matrix of real or complex numbers. It is known that the convergence order of Newton method is usually 2 and the convergence order of Chebyshev method is usually 3. Taking into account as well the number of operations made at each step, we obtain that the Chebyshev method is more efficient than the Newton method.

Let $E$ be a Banach space over $K$, where $K=ℝ$ or $K=ℂ$, and $T:E\to E$ a linear operator. It is well known that the scalar $\lambda$ is an eigenvalue of $T$ if the equation

has at least one solution $\overline{x}\ne \theta$, where $\theta$ is the null element of the space $E$. The elements $x\ne \theta$ that satisfy equation (1) are called eigenvectors of the operator $T$, corresponding to the eigenvalue $\lambda$.

For the simultaneously determination of the eigenvalues and eigenvectors of $T$ we can proceed in the following way.

We attach to the equation (1) an equation of the form

where $G$ is a linear functional $G:E\to K.$

Consider the real Banach space $F=E\times K$, with the norm given by

In this space we consider the operator $f:F\to F$ given by

If we denote by ${\theta }_1=\left(\genfrac{}{}{0pt}{}{\theta }{0}\right)$ the null element of the space $F$, then the eigenvalues and the corresponding eigenvectors of the operator $T$ are solutions of the equation

Obviously, $f$ is not a linear operator.

It can be easily seen that the first order Fréchet derivative of $f$ has the following form [4]:

where $u_0=\left(\genfrac{}{}{0pt}{}{x_0}{{\lambda }_0}\right)$ and $h=\left(\genfrac{}{}{0pt}{}{h_1}{{\lambda }_1}\right).$ For the second order derivative of $f$ we obtain the expression

where $k=\left(\genfrac{}{}{0pt}{}{h_2}{{\lambda }_2}\right).$

The Fréchet derivatives of order higher than $2$ of $f$ are null.

Considering the above forms of the Fréchet derivatives of $f$, in the following we shall study the convergence of the Chebyshev method for the operators having the third order Fréchet derivative the null operator.

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

where ${\mathrm{\Gamma }}_n={\left[f^{\prime }\left(u_n\right)\right]}^{-1}.$

Let $u_0\in F$ and $\delta >0,b>0$ be two real numbers. Denote $S=\{u\in F:$$\parallel u-u_0\parallel \le \delta \}.$ If

then

Consider the numbers

With the above notations, the following theorem holds:

In the following we shall apply the previously studied method to the approximation of eigenvalues and eigenvectors of matrices with elements real or complex numbers.

Let $p\in \mathbb{N}$ and the matrix $A={\left(a_{ij}\right)}_{i,j=\overline{1,p}}$, where $a_{ij}\in K$, $i,j=\overline{1,p}$.

Using the above notations, we shall consider $E=K^p$ and $F=K^p\times K$. Any solution of equation

$i_0\in \{1,\mathrm{\dots },p\}$ being fixed, where $x=(x_1,\mathrm{\dots },x_p)\in K^p$ and $\theta =(0,\mathrm{\dots },0)\in K^p,$ will lead us to an eigenvalue of $A$ and to a corresponding eigenvector. For the sake of simplicity denote $\lambda =x_{p+1}$, so that equation 19 is represented by the system

where

and

Denote by $P$ the mapping $P:K^{p+1}\to K^{p+1}$ defined by relations (21) and (22).

Let ${\overline{x}}_n=(x_1^n,\mathrm{\dots },x_{p+1}^n)\in K^{p+1}$. Then the first order Fréchet derivative of the operator $P$ at ${\overline{x}}_n$ has the following form

where $\overline{h}=(h_1,\mathrm{\dots },h_{p+1})\in K^{p+1}.$ If we write $\overline{k}=(k_1,\mathrm{\dots },k_{p+1})\in K^{p+1}$ then for the second order Fréchet derivative we get

Denote by $\mathrm{\Gamma }\left({\overline{x}}_n\right)$ the inverse of the matrix attached to the operator $P^{\prime }\left(x_n\right)$ and ${\overline{u}}_n=$ $\mathrm{\Gamma }\left({\overline{x}}_n\right)P\left({\overline{x}}_n\right)=(u_1^n,u_2^n,\mathrm{\dots },u_{p+1}^n).$ Let ${\overline{v}}_n=P^{\prime \prime }\left({\overline{x}}_n\right){\left(\mathrm{\Gamma }\left({\overline{x}}_n\right)P\left({\overline{x}}_n\right)\right)}^2=P^{\prime \prime }\left({\overline{x}}_n\right)$ ${\overline{u}}_n^2.$ We obtain the following representation

From this relation we can easily deduce the equalities

Denoting ${\overline{w}}_n=(w_1^n,w_2^n,\mathrm{\dots },w_{p+1}^n)=\mathrm{\Gamma }\left(x_n\right){\overline{v}}_n$ and supposing that ${\overline{x}}_n$ is an approximation of the solution of system (20), then the next approximation ${\overline{x}}_{n+1}$ given by method (8) is obtained by

Consider $K^p$ with the norm of an element $x=(x_1,\mathrm{\dots },x_p)$ given by the equality

and consequently

It can be easily seen that $\Vert P^{\prime \prime }\left({\overline{x}}_n\right)\Vert =2,$ for all ${\overline{x}}_n\in K^{p+1}.$ Let ${\overline{x}}_0\in K^{p+1}$ be an initial approximation of the solution of system (20). Consider a real number $r>0$ and the set $\overline{S}=\{x\in K^{p+1}\mid \Vert x-x_0\Vert \le r\}$. Denote by

where $\overline{b}={sup}_{x\in \overline{S}}\Vert \mathrm{\Gamma }\left(x\right)\Vert ,\mathrm{\Gamma }\left(x\right)$ being the inverse of the matrix attached to the operator $P^{\prime }\left(x\right)$.

Taking into account the results obtained in Section 2, the following consequence holds:

Note that if in (27) we neglect the term $-\frac{1}{2}{\overline{w}}_n$, then we get the Newton method:

In order to compare the Newton method and the Chebyshev method, we shall consider that the linear systems which appear in both methods are solved by the Gauss method.

While the Newton method require at each step the solving of a system $Ax=b$, the Chebyshev method require the solving of two linear systems $Ax=b,Ay=c$ with the same matrix $A$ and the vector $c$ depending on the solution $x$ of the first system. So, we shall adapt the Gauss method in order to perform as few as possible multiplications and divisions. When comparing the two methods we shall neglect the number of addition and subtraction operations.

The solving of a given linear system $Ax=b,A\in M_m\left(K\right),b,x\in K^m$, (where we have denoted $m=p+1$) using the Gauss method consists in two stages. In the first stage, the given system is transformed into an equivalent one but with the matrix of the coefficients being upper triangular. In the second stage the unknowns ${\left(x_i\right)}_{i=1,m}$ are determined by backward substitution.

The first stage. There are performed $m-1$ steps, at each one vanishing the elements on the same column below the main diagonal.

We write the initial system in the form

Suppose that $a_{11}^1\ne 0,a_{11}^1$ being called the first pivote. The first line in the system is multiplied by $\alpha =-\frac{a_{21}^1}{a_{11}^1}$ and is added to the second one, which becomes $0,a_{22}^2,a_{23}^2,\mathrm{\dots },a_{2m}^2,b_2^2,$ after performing $m+1$ multiplication or division $\left(M/D\right)$ operations. After $m-1$ such transformations the system becomes

Hence at the first step there were performed $\left(m-1\right)\left(m+1\right)$ $M/D$ operations.

In the same manner, at the $k$-th step we have the system

Supposing the $k$-th pivote $a_{kk}^k\ne 0$ and performing $\left(m-k\right)\left(m-k+2\right)$ $M/D$ operations we get

At each step $k$, the elements below the $k$-th pivote vanish, so they are not needed any more in the solving of the system.

The corresponding memory in the computer is used keeping in it the coefficients

which, of course, will be needed only for solving another system $Ay=c$, with $c$ depending on $x$, the solution of $Ax=b$.

At the first stage there are performed

The second stage. Given the system

the solution $x$ is computed in the following way:

At this stage there are performed $1+2+\mathrm{\dots }+m=\frac{m\left(m+1\right)}{2}M/D$ operations. In the both stages, there are totally performed

In the case when we solve the systems $Ax=b,Ay=c$, where the vector $c$ depends on the solution $x$, we first apply the Gauss method for the system $Ax=b$ and at the first stage we keep below the main diagonal the coefficients by which the pivotes were multiplied.

Then we apply to the vector $c$ the transformations performed to the vector $b$ when solving $Ax=b$.

Denote $c={(c_i^1)}_{i=1,m}.$

At the first step

At the $k$-th step

At the $m$-th step

There were performed $m-1+m-2+\mathrm{\dots }+1=\frac{m\left(m-1\right)}{2}M/D$operations.

Now the second stage of the Gauss method is applied to

In addition to the case of a single linear system, in this case were performed $\frac{m\left(m-1\right)}{2}M/D$operations, getting

and taking into account $\left(3.8\right)$ we add $\left(m-1\right)$ more $M/D$ operations, obtaining

Remark. At the first stage, if for some $k$ we have $a_{kk}^k\approx 0$, then an element $a_{i_0,k}^k\ne 0,i_0\in \{k+1,\mathrm{\dots },m\}$ must be find, and the lines $i_0$ and $k$ in $A$ and $b$ be swapped.

In order to avoid the error accumulations, a partial or total pivote strategy is recommended even if $a_{kk}^k\ne 0$ for $k=\overline{1,m-1}$.

For partial pivoting, the pivote is chosen such that $a_{i_0,k}^k={\max }_{i=\overline{k,m}}|a_{ik}^k|.$

The interchange of lines can be avoided by using a permutation vector $p={\left(p_i\right)}_{i=1,m}$, which is first initialized so that $p_i=i$. The elements in $A$ and $b$ are then referred to as $a_{ij}:=a_{p\left(i\right),j}$ and $b_i:=b_{p\left(i\right)}$, and swapping the lines $k$ and $i_0$ is done by swapping the $k$-th and $i_0$-th elements in $p$.

For the Chebyshev method, the use of the vector $p$ cannot be avoided by the very interchanging of the lines, because we must keep track for the permutations made, in order to apply them in the same order to the vector $c$.

Moreover, we need two extra vectors $t$ and $q$. In $t$ we store the transpositions applied to the lines in $Ax=b,$ which are then successively applied to $q$. At the first stage of the Gauss method, when the $k$-th pivote is $a_{i_0,k}^k$ and $i_0\ne k$, the $k$-th and $i_0$-th elements in $p$ are swapped, and we assign $t_k:=i_0$ to indicate that at the $k$-th step we applied to $p$ the transposition $(k,i_0)$.