Abstract
We consider a square matrix \(A\) with real or complex elements. We denote \(\mathbb{K}=\mathbb{R}\) or \(\mathbb{C}\) and we are interested in computing \(\lambda \in \mathbb{K}\) such that there exists \(v\in \mathbb{K}^{n}\) such that \(Av-\lambda v=0\), i.e. we are interested in computing the eigenpairs (eigenvalue +eigenvector) of the matrix \(A\). In this sense, we consider the nonlinear system of equations \(F(x) =0\), where \(F(x) =\)\({Av-\lambda v}\choose{Gv-1}\), where \(G\) is a convenient mapping.
In order to solve this system we consider the Newton and the Chebyshev methods, and at each iteration step, the order 1 derivative is approximated by the Schultz method; such an approach does not require the solving of a linear system at each step.
We conditions for local convergence and errors evaluations for the r-convergence order.
Authors
Keywords
eigenvalue and eigenvector of square matrix; eigenpair; Newton method; Chebyshev method; Schultz method; local convergence theorem; error estimation; linear systems solving-free iterative methods; r-convergence order.
Cite this paper as:
I. Păvăloiu, E. Cătinaş, Remarks on some Newton and Chebyshev-type methods for approximation eigenvalues and eigenvectors of matrices, Comput. Sci. J. Mold., 7 (1999) no. 1, pp. 3-15.
Latex version of the paper (soon).
About this paper
Publisher Name
Paper on the journal website
Print ISSN
1561-4042
Online ISSN
Not available yet.
Print ISSN
1561-4042
Online ISSN
Not available yet.
Google Scholar citations
[1] M.P. Anselone and L.B. Rall, The solution of characteristic value-vector problems by Newton method, Numer. Math., 11 (1968), pp. 38-45.
[2] E. Catinas and I. Pavaloiu, On the Chebyshev method for approximating the eigenvalues of linear operators, Rev. Anal. Numer. Theor. Approx. 25 (1996) 1-2, pp. 43-56.
Post
[3] E. Catinas and I. Pavaloiu, On the Chebyshev Method for Approximating the Eigenvalues of Linear Operators, Proceedings of International Conference on Approximation and Optimization, ClujNapoca, July 29 – August 1, 1996, Vol. 1, pp. 219-226.
[4] E. Catinas and I. Pavaloiu, On Approximating the Eigenvalues and Eigenvectors of Linear Continuous Operators, Rev. Anal. Numer. Theor. Approx. 25 (1996) 1-2, pp. 43-56.
post
[5] F. Chatelin, Valeurs propres de matrices, Mason, Paris, 1988.
[6] L. Collatz, Functionalanalysis und Numerische Mathematik, Springer-Verlag, Berlin, 1964.
[7] A. Diaconu and I. Pavaloiu, Sur quelque methodes iteratives pour la resolution des equations operationelles, Rev. Anal. Numer. Theor. Approx. 1, 1 (1972), pp. 45-61.
[8] A. Diaconu, On the Convergence of an Iterative Method of Chebyshev Type, Rev. Anal. Numer. Theor. Approx., 24 (1995) 1-2, pp. 91-102.
[9] J.J. Dongarra, C.B. Moler and J.H. Wilkinson, Improving the Accuracy of the Computed Eigenvalues and Eigenvectors, SIAM J. Numer. Anal., 20 (1983) no. 1, pp. 23-45.
[10] S.M. Grzegorski, On the Scaled Newton Method for the Symmetric Eigenvalue Problem, Computing, 45 (1990), pp. 277-282.
[11] V. S. Kartisov and F. L. Iuhno, O nekotorıh Modifikatiah Metoda Niutona dlea Resenia Nelineinoi Spektralnoi Zadaci, J. Vicisl. matem. i matem. fiz. 33 (1973) 9, pp. 1403-1409.
[12] J.M. Ortega and W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970.
[13] I. Pavaloiu, Sur les procedes iteratifs a un ordre eleve de convergence, Mathematica (Cluj) 12 (35) (1970) 2, pp. 309-324.
[14] I. Pavaloiu, Introduction to the Approximation Theory for the Solutions of Equations, Ed. Dacia, Cluj-Napoca, 1986 (in Romanian).
[15] I. Pavaloiu, Observations concerning some Approximation Methods for the Solutions of Operator Equations, Rev. Anal. Numer. Theor. Approx., 23 (1994) 2, pp. 185-196.
[16] G. Peters and J.H. Wilkinson, Inverse Iteration, Ill-Conditioned Equations and Newton’s Method, SIAM Review, 21 (1979) no. 3, pp. 339-360.
[17] M.C. Santos, A Note on the Newton Iteration for the Algebraic Eigenvalue Problem, SIAM J. Matrix Anal. Appl., 9 (1988) no. 4, pp. 561-569.
[18] R.A. Tapia and L.D. Whitley, The Projected Newton Method has Order 1 + √2 for the Symmetric Eigenvalue Problem, SIAM J. Numer. Anal., 25 (1988) 6, pp. 1376-1382.
[19] S. Ul’m, On the Iterative Method with Simultaneous Approximation of the Inverse of the Operator, Izv. Acad. Nauk. Estonskoi S.S.R., 16 (1967) 4, pp. 403-411.
[20] K. Wu, Y. Saad and A. Stathopoulos, Inexact Newton Preconditioning Techniques for Eigenvalue Problems, Lawrence Berkeley National Laboratory report number 41382 and Minnesota Supercomputing Institute report number UMSI 98-10, 1998.
[21] T. Yamamoto, Error Bounds for Computed Eigenvalues and Eigenvectors, Numer. Math. 34 (1980), pp. 189-199.
Paper (preprint) in HTML form
Remarks on Some Newton and Chebyshev-type Methods for Approximating the Eigenvalues and Eigenvectors of Matrices
1 Introduction
It is well known that the Newton and the Chebyshev methods for nonlinear systems require the solving of a linear system at each iteration step. In this note we shall study two modified methods which avoid the solving of the linear systems by using the Schultz method to approximate the inverses of the Fréchet derivatives. At the same time we shall use the particularities of the nonlinear systems arising from eigenproblems, since the Fréchet derivatives of order higher than two are the null multilinear operators. Some numerical examples will be provided in the end of this note.
Denote and let , where or . We recall that the scalar is an eigenvalue of if there exists , such that
| (1) |
The vector is called an eigenvector corresponding to the eigenvalue . Since for an eigenvalue the eigenpair is not uniquely determined, it is necessary to impose a supplementary condition. Different Newton-type methods were studied in the papers [1]-[4], [6], [9]-[11], [16]-[18], [20], [21]. It is worth mentioning that the Rayleigh quotient method is equivalent with a certain Newton method (”the scaled Newton method” [10]).
We shall consider a ”norming” function and besides (1) the equation
The function may be chosen in different ways (see [16] and [3]):
We shall consider in the theoretical results hereafter the choice II.
Let and for take
where the norm on is one of the usual norms.
Consider the system
| (2) |
with the mapping given by
Denoting and then the system (2) can be written explicitly
It can be easily seen that the Fréchet derivatives of are given by the following relations:
for all , , .
Since the Fréchet derivative of order does not depend on it is obvious that the derivatives of order higher than an the null multilinear operators, so for any fixed
| (3) |
It is easy to verify that when we use the norm on and is given by choice II
The following result concerning the invertibility of at a solution hold.
Lemma 1
Let be an eigenpair of a given matrix . Then the eigenvalue is simple if and only if the Jacobian is nonsingular.
Proof. The corresponding result for the choice I of was proved by Yamamoto [21], for which
The stated affirmation follows immediately observing that the two matrices differ by a nonzero factor in the last row.
2 Some Newton and Chebyshev-type methods
We shall study first the convergence of the sequences and generated by the following Newton-type process applied to the nonlinear system (2), initially proposed by Ul’m [19] and studied by Diaconu and Pǎvǎloiu [7]:
| (4) | ||||
and being given.
We shall need the following preliminary result.
Lemma 2
[4] If the sequences and of real positive numbers satisfy
| (5) | ||||
with for some , then the following inequalities are true:
Denoting we can state the following result.
Theorem 3
Assume that the operator and the elements , and satisfy the following conditions
- a)
-
there exists and
- b)
-
- c)
-
denoting , and , suppose
- d)
-
Proof. It can be easily seen that in our hypotheses the derivatives are invertible for all .
Using the inequality
and applying the Banach lemma we get
Denote and . If we take in (3) then an elementary reasoning shows that
whence, by lemma 2 it follows that .
It can be easily proved by induction that the following relations hold for
-
•
-
•
-
•
-
•
.
From the above properties it results that the sequence is Cauchy and therefore there exists such that . The last inequality above implies that for all
which leads to the first estimation from the enounce.
The convergence of the sequence is infered from the inequalities
which lead to the second stated estimation.
As we can see, the Newton-type method (4) has the -convergence order at least 2. The conditions from the above theorem assure that the eigenvalue is simple, according to lemma 1.
We shall consider now the following sequences given by the Chebyshev-type method, initially proposed by Diaconu [8]
| (6) | ||||
where and are given.
For the study of the above method we need the following auxilliary result.
Lemma 4
[3] If the sequences of real positive numbers and satisfy
where for some , then the following relation holds:
As for the previous method, we shall consider the elements and the ball .
Theorem 5
Assume that the operator and the elements , satisfy:
- a)
-
there exists and
- b)
-
- c)
-
denoting , , and , suppose
- d)
-
.
Then the sequences , , converge and . Denoting ,,, then and . Moreover, the following estimations hold:
Proof. From a), b) and the Banach lemma it easily follows that for any the Jacobian of is invertible and
For the norms of and , taking into account the hypotheses, we get
and
so .
Denoting and taking into account the inequality
it follows
By lemma 4 the above inequalities imply that .
Assume now that the following properties hold:
-
•
-
•
and .
It easily follows that and
From the above formula it follows that :
Denoting and , the following relations are obtained in the same manner as for and :
whence, by lemma 4, we get that and the induction is proved.
We will show now that is a Cauchy sequence. Indeed,
for all , which implies that converges. Denoting we obtain
The convergence of is obtained from the third relation of (6):
Denoting it easily follows that and that
The proof is completed.
3 Numerical examples
We shall consider two test matrices111These matrices are available from MatrixMarket at the following address: http://math.nist.gov/MatrixMarket/. in order to study the behavior of the considered methods. The programs were written in Matlab222MATLAB is a registered trademark of the MathWorks, Inc. and were run on a PC.
Pores1 matrix. This matrix arise from oil reservoir simulation. It is real, unsymmetric, of dimension 30 and has 20 real eigenvalues. We have chosen to study the largest eigenvalue . The initial approximation was taken ; for the initial vector we perturbed the solution (computed by Matlab and then properly scaled to fulfill the norming equation) with random vectors having the components uniformly distributed on (-,), . The following results are typical for the runs made (we have considered here the same vector for the four initial approximations).
| Choice I | Choice II | |||
|---|---|---|---|---|
| 0 | 7.8042e-01 | 5.5828e+06 | 7.8042e-01 | 5.5828e+06 |
| 1 | 1.4111e-01 | 3.9355e-01 | 2.3565e-02 | 3.0227e-01 |
| 2 | 1.8788e-02 | 5.1300e-02 | 4.6685e-05 | 9.6691e-04 |
| 3 | 3.7663e-04 | 6.3248e-04 | 5.7799e-10 | 9.0156e-09 |
| 4 | 1.4161e-07 | 2.1373e-07 | ||
| 5 | 4.5991e-10 | 5.0482e-10 | ||
Table 1. Newton-type method for Pores1.
| Choice I | Choice II | |||
|---|---|---|---|---|
| 0 | 7.8042e-01 | 5.5828e+06 | 7.8042e-01 | 5.5828e+06 |
| 1 | 5.6679e-02 | 1.0406e-01 | 1.5461e-03 | 1.2236e-02 |
| 2 | 2.8973e-06 | 4.0907e-06 | 5.6407e-10 | 5.5530e-09 |
| 3 | 4.5959e-10 | 6.5014e-10 | ||
Table 2. Chebyshev-type method for Pores1.
Fidap002 matrix. This real symmetric matrix of dimension arise from finite element modeling. Its eigenvalues are all simple and range from to . We have chosen to study the smallest eigenvalue, which is well separated. The initial approximation was taken ; for the initial vector we perturbed the solution with random vectors having the components uniformly distributed on (-,), . The following results are typical for the runs made (we have considered a common vector ).
| Choice I | Choice II | |||
|---|---|---|---|---|
| 0 | 1.0000e+3 | 8.5068e+8 | 1.0000e+3 | 8.5068e+8 |
| 1 | 2.3611e+2 | 1.5730e+3 | 3.3415e+0 | 1.2195e+3 |
| 2 | 2.5528e+2 | 8.8353e+2 | 8.4714e-3 | 1.0600e+0 |
| 3 | 4.3758e+1 | 8.2481e+1 | 5.9605e-7 | 4.1725e-6 |
| 4 | 1.3141e+0 | 2.0458e+0 | ||
| 5 | 9.9051e-4 | 1.4631e-3 | ||
| 6 | 5.9605e-7 | 1.0662e-7 | ||
Table 3. Newton-type method for Fidap002.
| Choice I | Choice II | |||
|---|---|---|---|---|
| 0 | 1.0000e+3 | 8.5068e+8 | 1.0000e+3 | 8.5068e+8 |
| 1 | 3.9756e+2 | 9.4690e+2 | 8.5282e-1 | 2.5509e+1 |
| 2 | 4.6275e-1 | 6.5442e-1 | 7.1526e-7 | 5.0390e-6 |
| 3 | 4.7684e-7 | 3.1597e-7 | ||
Table 4. Chebyshev-type method for Fidap002.
If was increased to then the Newton-type method with choice I has not converged for some of the initial approximations, even if we took for . The Newton-type method with choice II and the Chebyshev-type method converged as above. The explanation seem to reside in the fact that the eigenvector has a larger norm with choice II than with choice I, the relative error of with the second choice being much smaller than of with the first choice.
References
- [1] M.P. Anselone and L.B. Rall, The Solution of Characteristic Value-Vector Problems by Newton Method, Numer. Math., 11 (1968), pp. 38-45.
- [2] E. Cǎtinaş and I. Pǎvǎloiu, On the Chebyshev Method for Approximating the Eigenvalues of Linear Operators, Rev. Anal. Numér. Théorie Approximation 25 (1996) 1-2, pp. 43-56.
- [3] E. Cătinaş and I. Păvăloiu, On the Chebyshev Method for Approximating the Eigenvalues of Linear Operators, Proceedings of International Conference on Approximation and Optimization, Cluj-Napoca, July 29 - August 1, 1996, Vol. 1, pp. 219-226.
- [4] E. Cǎtinaş and I. Pǎvǎloiu, On Approximating the Eigenvalues and Eigenvectors of Linear Continuous Operators, Rev. Anal. Numér. Théorie Approximation 25 (1996) 1-2, pp. 43-56.
- [5] F. Chatelin, Valeurs propres de matrices, Mason, Paris, 1988.
- [6] L. Collatz, Functionalanalysis und Numerische Mathematik, Springer-Verlag, Berlin, 1964.
- [7] A. Diaconu and I. Pǎvǎloiu, Sur quelque méthodes itératives pour la résolution des équations opérationelles, Rev. Anal. Numér. Théorie Approximation 1, 1 (1972), pp. 45-61.
- [8] A. Diaconu, On the Convergence of an Iterative Method of Chebyshev Type, Rev. Anal. Numér. Théorie Approximation, 24 (1995) 1-2, pp. 91-102.
- [9] J.J. Dongarra, C.B. Moler and J.H. Wilkinson, Improving the Accuracy of the Computed Eigenvalues and Eigenvectors, SIAM J. Numer. Anal., 20 (1983) no. 1, pp. 23-45.
- [10] S.M. Grzegórski, On the Scaled Newton Method for the Symmetric Eigenvalue Problem, Computing, 45 (1990), pp. 277-282.
- [11] V. S. Kartîşov and F. L. Iuhno, O nekotorîh Modifikaţiah Metoda Niutona dlea Resenia Nelineinoi Spektralnoi Zadaci, J. Vîcisl. matem. i matem. fiz. 33 (1973) 9, pp. 1403-1409.
- [12] J.M. Ortega and W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970.
- [13] I. Pǎvǎloiu, Sur les procédés itératifs à un ordre élevé de convergence, Mathematica (Cluj) 12 (35) (1970) 2, pp. 309-324.
- [14] I. Pǎvǎloiu, Introduction to the Approximation Theory for the Solutions of Equations, Ed. Dacia, Cluj-Napoca, 1986 (in romanian).
- [15] I. Pǎvǎloiu, Observations concerning some Approximation Methods for the Solutions of Operator Equations, Rev. Anal. Numér. Théorie Approximation, 23 (1994) 2, pp. 185-196.
- [16] G. Peters and J.H. Wilkinson, Inverse Iteration, Ill-Conditioned Equations and Newton’s Method, SIAM Review, 21 (1979) no. 3, pp. 339-360.
- [17] M.C. Santos, A Note on the Newton Iteration for the Algebraic Eigenvalue Problem, SIAM J. Matrix Anal. Appl., 9 (1988) no. 4, pp. 561-569.
- [18] R.A. Tapia and L.D. Whitley, The Projected Newton Method has Order for the Symmetric Eigenvalue Problem, SIAM J. Numer. Anal., 25 (1988) 6, pp. 1376-1382.
- [19] S. Ul’m, On the Iterative Method with Simultaneous Approximation of the Inverse of the Operator, Izv. Acad. Nauk. Estonskoi S.S.R., 16 (1967) 4, pp. 403-411.
- [20] K. Wu, Y. Saad and A. Stathopoulos, Inexact Newton Preconditioning Techniques for Eigenvalue Problems, Lawrence Berkeley National Laboratory report number 41382 and Minnesota Supercomputing Institute report number UMSI 98-10, 1998.
- [21] T. Yamamoto, Error Bounds for Computed Eigenvalues and Eigenvectors, Numer. Math. 34 (1980), pp. 189-199.
”T. Popoviciu” Institute of Numerical Analysis
P.O. Box 68
3400 Cluj-Napoca 1
Romania
e-mail: pavaloiu@ictp.math.ubbcluj.ro
ecatinas@ictp.math.ubbcluj.ro