Eigenvalues and eigenvectors of symmetric matrices

Abstract

In any area of applied science, symmetric matrices arise quite often, mostly for their prominent implications and key properties. Solving problems involving symmetric matrices often requires computing their eigenvalues and eigenvectors, since these quantities are inherently linked to the structure of the matrix. In the 19th century, it was shown (by Abel and Galois) that for polynomial equations of degree n ≥ 5, there is no general solution in terms of radicals. Classical root finding methods such as the Newton-Raphson method can be used to determine real roots of a high degree polynomial. However, it is impractical and numerically expensive for matrices of higher order, in obtaining all eigenvalues. Although, such methods suffice quite well for small matrices, they are not recommended for general use, as they tend to become quickly problematic, lacking in efficiency and performance to acquire specific eigenvalues, of both moderate or large size matrices. This reveals that every method has to advance forward through sequential approximations. The dissertation focuses on fast and efficient iterative techniques for computing eigenvalues and eigenvectors of symmetric matrices. The methods discussed include the Classical Jacobi and its serial variant, Householder transformations for tridiagonalisation, the Sturm Sequence bisection method, and the QR-iteration. In particular, tridiagonalisation plays a central role in reducing computational complexity, especially for large sparse or banded matrices. The final part of this study examines the Inverse Iteration (INVIT) method, which provides eigenvector approximations given an estimated eigenvalue. The content of this dissertation is mainly based on chapter 5 of the book, An Introduction to Numerical Analysis by Endre Süli and David Mayers, with exception to the first portion of the last chapter being explored further in detail via the book, The Algebraic Eigenvalue Problem by James Hardy Wilkinson and the two original papers published by John G. F. Francis in 1961-62, along with supplementary sources gathered in the References section.