Next: Oblique Projection Methods.
Up: Basic Ideas Y. Saad
Previous: Basic Ideas Y. Saad
  Contents
  Index
Orthogonal Projection Methods.
Let
be an
complex matrix and
be an
-dimensional subspace of
and consider the eigenvalue
problem of finding
belonging to
and
belonging to
such that
![\begin{displaymath}
A u\ = \ \lambda u .
\end{displaymath}](img676.png) |
(7) |
An orthogonal projection technique onto the subspace
seeks an
approximate eigenpair
to the above
problem, with
in
and
in
. This approximate
eigenpair is obtained by imposing the
following Galerkin condition:
![\begin{displaymath}
A \tlu - \tilde \lambda \tlu \ \bot\ \KK ,
\end{displaymath}](img678.png) |
(8) |
or, equivalently,
![\begin{displaymath}
v^{\ast} ( A \tlu - \tilde \lambda \tlu )\ =\ 0 \ \ \ \forall \ v \in \KK.
\end{displaymath}](img679.png) |
(9) |
In order to translate this into a matrix problem,
assume that an orthonormal basis
of
is available. Denote by
the matrix with column vectors
, i.e.,
.
Because we seek a
, it can be written as
![\begin{displaymath}
\tlu\ =\ V y .
\end{displaymath}](img684.png) |
(10) |
Then, equation eq:4.16 becomes
Therefore,
and
must satisfy
![\begin{displaymath}
B_m y\ =\ \tilde \lambda y
\end{displaymath}](img687.png) |
(11) |
with
B_m = V^ A V .
The approximate eigenvalues
resulting from the projection process are
all the eigenvalues of the matrix
. The associated eigenvectors
are the vectors
in which
is an eigenvector of
associated
with
.
This procedure for numerically computing the Galerkin
approximations to the eigenvalues/eigenvectors of
is known as the
Rayleigh-Ritz procedure.
RAYLEIGH-RITZ PROCEDURE
- Compute an orthonormal basis
of the subspace
.
Let
.
- Compute
.
- Compute the eigenvalues of
and select the
desired ones
, where
(for
instance the largest ones).
- Compute the eigenvectors
, of
associated with
, and the
corresponding approximate eigenvectors of
,
.
In implementations of this approach, one often does not compute the eigenpairs
of
for each set of generated basis vectors.
The values
computed from this procedure are referred to as
Ritz values and the vectors
are the associated
Ritz vectors.
The numerical solution of the
eigenvalue problem in steps 3
and 4 can be treated by standard library subroutines such as those in
LAPACK [12].
Another important note is that in step 4 one can replace
eigenvectors by Schur vectors to get approximate Schur vectors
instead of approximate eigenvectors.
Schur vectors
can be obtained in a numerically stable way and,
in general, eigenvectors are more sensitive to rounding errors
than are Schur vectors.
Next: Oblique Projection Methods.
Up: Basic Ideas Y. Saad
Previous: Basic Ideas Y. Saad
  Contents
  Index
Susan Blackford
2000-11-20