Abstract
Authors
Keywords
?
Paper coordinates
E. Cătinaş, I. Păvăloiu, Some numerical aspects in the approximation of eigenpairs of matrices by the Newton method, Acta Technica Napocensis, Series: Applied Mathematics and Mechanics, 42 (1999) vol. 1, pp. 41-44.
??
About this paper
Print ISSN
Online ISSN
google scholar link
??
Paper (preprint) in HTML form
SOME NUMERICAL ASPECTS IN THE APPROXIMATION OF EIGENPAIRS OF MATRICES BY THE NEWTON METHOD
E. CǍTINAŞ, I. PǍVǍLOIU
Abstract. The eigenpairs of matrices may be approximated using the Newton method. The nonlinear mapping in such a case may be chosen in different ways, depending on the norming function. We investigate the difficulties of solving the linear systems from such iterations by evaluating the condition number at the solution for each of the resulted Jacobians in the case of two test matrices.
1. The eigenpairs of matrices as zeroes of nonlinear mappings
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. As in [9] we shall consider a ”norming” function and besides (1) the equation
The function may be chosen in different ways:
| (I) | ||||
| (II) |
where stands for the euclidean norm.
In the paper [2] we proposed the choice
| (III) |
Considering endowed with the norm , we are led to the nonlinear mapping
Its first components are
The last component is determined by the choice of . We get for each corresponding case:
| (I) | ||||
| (II) | ||||
| (III) |
It can be seen now that the eigenpairs of may be regarded as the solutions of the nonlinear system
For the solving of such a problem we may use the Newton method, which requires the derivative of . It is known that the first and the second order derivatives of are given by
| (I) | ||||
| (II) | ||||
| (III) |
for all , , , where is the -th vector from the canonical basis.
Some direct computations show that the norms of the second derivatives of are given by
| (I) | ||||
| (II) | ||||
| (III) |
regardless of , since is a polynomial of degree .
Different Newton-type methods for solving such nonlinear systems were studied in several papers [9], [6], [12], [14], [1], [2] and [3]. It is interesting to note that the Rayleigh quotient method is equivalent with a certain Newton method (”the scaled Newton method” [7]).
2. THE ROLE OF CERTAIN QUANTITIES IN THE CONVERGENCE OF THE NEWTON METHODS
We are interested how the different quantities specific to a nonlinear mapping influence the convergence of the Newton iterates.
The following result was obtained by Deuflhard and Potra
Theorem 1: [5] Let be a nonlinear operator defined on the convex domain . Suppose that is Fréchet differentiable on , that invertible for all , and that
, . Moreover, assume that is a solution of the nonlinear system . Let be such that and . Then the Newton iterates
remain in the open ball , converge to and satisfy
Similar but somehow weaker results were obtained by Rheinboldt [10], Dennis and Schnabel [4] and by Ortega and Rheinboldt [8].
Remark. If and for all , one can take .
As explicitly noted by Dennis and Schnabel [4], the smaller are and , the faster is the convergence of the iterates. On the other hand, as and decrease, the radius of the attraction ball becomes larger.
We see that in the case of large matrices, the choice III yields a much smaller constant compared to choice II (the choice I also yields small , but its use may theoretically not be safe [2]). Of course that taking the norming function III, the constant may grow compared to the corresponding one from II but we do not analyse here this aspect.
There is another aspect important in the practical use of the Newton method. When the iterates converge, the matrices tend to . The condition number of a nonsingular matrix , defined as , is a measure of the sensitivity of a linear system to perturbations. The larger is , the more inaccurate results one may obtain when using direct methods.
The Newton methods for eigenproblems were also considered in [13], in the context of preconditioning techniques.
The following section will be devoted to the numerical study of the condition numbers of two test matrices.
NUMERICAL ASPECTS
We shall consider two test matrices (these matrices are available from MatrixMarket at the following address: http://math.nist.gov/MatrixMarket/) in order to study the condition numbers. The programs were written in Matlab 5.0 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 plotted in fig. 1 the evaluations of the condition numbers of at the real solutions (the eigenpairs were computed by Matlab).
Fig. 1.
One can see that in this case the condition numbers are very close. At the nineth eigenvalue, the condition number of is slightly better conditioned with choice III than with choice II.
Fidap002 matrix. This real symmetric matrix of dimension arise from finite element modeling. Its eigenvalues are all simple and range from to . Figure 2 contains the plot of the difference between the condition numbers computed with choices II and III.
Fig. 2.
One can see that in this case the differences that appear between the two condition numbers are on the whole small, but for some certain few eigenpairs the differences are large in favour of choice II. However, we cannot conclude that one of the choices has better overall condition numbers.
REFERENCES
1. E. Cǎtinaş and I. Pǎvǎloiu, On the Chebyshev Method for Approximating the Eigenvalues of Linear Operators, Rev. Anal. Numér. Théor. Approx., 25 (1996) no. 1-2, pp. 43-56.
2. E. Cǎtinaş and I. Pǎvǎloiu, On a Chebyshev-Type Method for Approximating the Solutions of Polynomial Operators Equations of Degree 2, Approximation and Optimization. Proceedings of the International Conference on Approximation and Optimization, Romania (ICAOR), Cluj-Napoca, July 29 - August 1, 1996, vol. I, pp. 219-226.
3. E. Cǎtinaş and I. Pǎvǎloiu, On Approximating the Eigenvalues and Eigenvectors of Linear Continuous Operators, Rev. Anal. Numér. Théor. Approx., 26 (1997) no. 1-2, pp. 19-27.
4. J.E. Dennis, Jr. and R.B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall Series in Computational Mathematics, Englewood Cliffs, NJ, 1983.
5. P. Deuflhard and F.A. Potra, Asymptotic Mesh Independence of Newton-Galerkin Methods via a Refined Mysovskii Theorem, SIAM J. Numer. Anal., 29 (1992) no.5, pp. 1395-1412.
6. 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.
7. S.M. Grzegórski, On the Scaled Newton Method for the Symmetric Eigenvalue Problem, Computing, 45 (1990), pp. 277-282.
8. J.M. Ortega and W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970.
9. G. Peters and J.H. Wilkinson, Inverse Iteration, Ill-Conditioned Equations and Newton’s Method, SIAM Review, 21 (1979) no. 3, pp. 339-360.
10. W.C. Rheinboldt, An Adaptive Continuation Process for Solving Systems of Nonlinear Equations, Polish Academy of Science, Banach Ctr. Publ., 3 (1977), pp. 129-142.
11. 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.
12. R.A. Tapia and L.D. Whitley, The Projected Newton Method has Order for the Symmetric Eigenvalue Problem, SIAM J. Numer. Anal., 25 (1988) no. 6, pp. 1376-1382.
13. 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.
14. T. Yamamoto, Error Bounds for Computed Eigenvalues and Eigenvectors, Numer. Math. 34 (1980), pp. 189-199.
Aspecte numerice în aproximarea valorilor şi vectorilor proprii ai matricilor prin metoda lui Newton
Valorile şi vectorii proprii ai matricilor pot fi aproximaţ prin metoda lui Newton. Aplicaţia neliniarǎ în acest caz poate fi aleasǎ în mai multe moduri, depinzând de funcţia de normare. In prezenta notǎ investigǎm dificultǎţile de rezolvare a sistemelor liniare din astfel de iteraţii prin evaluarea numǎrului de condiţionare în soluţie pentru fiecare din Jacobienii rezultaţi în cazul unor matrici test.
Cerc. pr. gr. III Emil Cǎtinaş, ”T. Popoviciu” Institute of Numerical Analysis, P.O. Box 68, 3400 Cluj-Napoca, Romania (ecatinas@ictp.math.ubbcluj.ro)
Cerc. pr. gr. I Ion Pǎvǎloiu, ”T. Popoviciu” Institute of Numerical Analysis, P.O. Box 68, 3400 Cluj-Napoca, Romania (pavaloiu@ictp.math.ubbcluj.ro)