Lenard, Christopher Thomas

### Description

The subject of this thesis is the numerical solution of eigenproblems from the point of view
of iterative refinement. On the whole, we will be concerned with linear, symmetric
problems, but occasionally we will make forays into non-linearity and non-symmetry.
The initial goal was to develop a better understanding of Rayleigh quotient iteration
(RQI) and its numerical performance. Along the way it was necessary to look at a variety
of methods proposed for the iterative refinement of...[Show more] eigenelements to see what relationships,
if any, they have with RQI. As a consequence we identified a natural progression from
algebraic (discrete) methods to continuous methods, some of which have direct discrete
counterparts.
Chapter 1 provides an overview of eigenproblems and some of the main methods for
their numerical solution. Particular emphasis is given to two of the key players which will
be found throughout the thesis; namely, inverse iteration and the Rayleigh quotient. In
Chapter 2, these are combined to form the Rayleigh quotient iteration; a method with
remarkable convergence properties (at least for normal, compact operators). The first part
of the chapter, Sections 1 to 4, examine RQI, what its properties are, the way it works, and
what it does in terms of minimizing naturally occuring functionals. Section 5 completes
the chapter by using Taylor’s series to show why RQI is such a special process. Not many
numerical procedures are cubically convergent, and the obvious ploy of using the first three
terms of the Taylor’s series to get such fast convergence only results in very inelegant
iterations when applied to the eigenproblem. Although it must be said that while the
evaluation of the second differential of an arbitrary (vector valued) function is in general
quite daunting, and the rewards are probably outweighed by the costs, the functions one
would expect in the eigenproblem yield second differentials which are quite simple. Chapter 3 is a bridge between inverse iteration in the first two chapters, and
continuous methods in Chapter 4. The link is established through the
Rayleigh-Schrödinger series which is the motivation behind Rayleigh-Schrödinger iteration
and its several variants. Essentially these are inverse iterations, but using generalized
inverses which come in as reduced resolvents. For the self-adjoint case, the iterations
follow a particularly nice pattern that is reminiscent of the error squaring
(superconvergence) property of the Rayleigh quotient. As with RQI, the iterations have a
natural interpretation in terms of minimizing functionals. In this chapter, Section 2 is an
inset giving a novel way of arriving at the iteration based on matrix calculus.
The derivation of the Rayleigh-Schrödinger series itself, however, is as a homotopy
method for getting from a known eigenpair of a perturbed operator to an eigenpair of the
unperturbed operator. One way of tackling homotopies is via differential equations, and so
in Chapter 4 we turn our attention to these matters.
The discussion in Chapter 4 is based on continuous analogues of discrete processes
which have their genesis in the discovery that the QR algorithm is closely related to the
Toda flow. Many discrete methods follow the solution trajectory of a differential equation,
either exactly or approximately. For example, Newton’s iteration can be thought of as
Euler’s method applied to a particular initial value problem. Other methods though, like the
QR algorithm, produce iterates that are exactly on the solution curve, so that one can think
of the continuous method as an interpolation of the discrete iteration.
Finally Chapter 5 stands apart in the sense that it does not directly continue on from
continuous methods; however, inverse iteration does plays the central role. The main idea
is to build up information from the traces of a matrix, its powers, and its inverse powers,
which can then be used to approximate eigenvalues. Here, Laguerre’s method for finding
the roots of a polynomial is shown to be connected with the (standard) method of traces
applied to matrices (or integral operators).

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.