Ritz pairs

On a symmetric matrix \(\require{physics} \vb{A}\), we can perform a . This states that there exists a real, orthogonal matrix \(\vb{Q}\) \[\begin{equation} \vb{Q} = \begin{pmatrix} \vb{q}_1 & \vb{q}_2 & \cdots & \vb{q}_n \end{pmatrix} \qquad \qquad \vb{Q}^\text{T} \vb{Q} = \vb{I}_{(n)} \end{equation}\] such that \[\begin{equation} \vb{Q}^\text{T} \vb{A} \vb{Q} = \text{diag}(\lambda_1, \cdots, \lambda_n) \thinspace . \end{equation}\] Moreover, \[\begin{equation} \vb{A} \vb{q}_k = \lambda_k \vb{q}_k \thinspace . \end{equation}\] \
Let \(\vb{Q}_1 \in \mathbb{R}^{n \times r}\) (first \(r\) rows of an orthogonal matrix) have independent columns \(\vb{Q}_1^\text{T} \vb{Q}_1 = \vb{I}_{(r)}\). For some \(\vb{S} \in \mathbb{R}^{r \times r}\), we call \[\begin{equation} \vb{A}\vb{Q}_1 - \vb{Q}_1 \vb{S} \end{equation}\] the . Then there exist \(\mu_1, \dots, \mu_r \in \lambda(\vb{A})\): \[\begin{equation} \label{eq:mu_lambda_residue} \forall k=1, \dots, r: |\mu_k - \lambda_k(\vb{S})| \leq \sqrt{2} \thinspace || \vb{A}\vb{Q}_1 - \vb{Q}_1 \vb{S} ||_F \thinspace , \end{equation}\] in which \(\lambda_k(S)\) is the \(k\)-th largest eigenvalue of \(\vb{S}\) and \(||.||_F\) represents the matrix 2-norm (or Frobenius norm). This results says that the eigenvalues of \(\vb{S}\) tend to the eigenvalues of \(\vb{A}\), with the better approximation for the smaller Frobenius norm of the residual matrix.

It is then natural to look at which \(\vb{S}\) minimizes the right-hand side of equation \(\eqref{eq:mu_lambda_residue}\). It can be shown that \[\begin{equation} \min_{\vb{S} \in \mathbb{R}^{r \times r}} || \vb{A}\vb{Q}_1 - \vb{Q}_1 \vb{S} ||_F = || (\vb{I}_{(n)} - \vb{Q}_1 \vb{Q}_1^\text{T}) \vb{A}\vb{Q}_1 ||_2 \thinspace , \end{equation}\] with the minimizer being \[\begin{equation} \label{eq:residual_frobenius_minimizer} \vb{S} = \vb{Q}_1^\text{T} \vb{A} \vb{Q}_1 \thinspace . \end{equation}\] This means that we can associate any \(r\)-dimensional subspace \(C(\vb{Q}_1)\) with a set of \(r\) “optimal” eigenvalue-eigenvector approximates. Let us Schur-decompose the minimizer (equation \(\eqref{eq:residual_frobenius_minimizer}\)) to yield \[\begin{equation} \vb{Z}^\text{T} \vb{S} \vb{Z} = \text{diag}(\theta_1, \dots, \theta_r) \thinspace , \end{equation}\] and \[\begin{equation} \vb{Q}_1 \vb{Z} = \begin{pmatrix} \vb{y}_1 & \vb{y}_2 & \cdots & \vb{y}_r \end{pmatrix} \thinspace . \end{equation}\] The tuple \((\theta_k, \vb{y}_k)\) is then called a , with \(\theta_k\) being the and \(\vb{y}_k\) begin the , which are the optimal eigensystem approximates of the symmetric matrix \(\vb{A}\) in the \(r\)-dimensional subspace \(C(\vb{Q}_1)\).

Let’s say we have a current (subscript \(c\)) approximation \(\qty{\lambda_c, \vb{x}_c}\) to the symmetric eigenvalue problem. Denoting the correction to the eigenvalue by \(\delta\lambda\) and the correction to the eigenvector by \(\boldsymbol{\delta} \vb{x}\), we then want \[\begin{equation} \label{eq:approximation_eigenequation} \vb{A} (\vb{x}_c + \boldsymbol{\delta} \vb{x}) = (\lambda_c + \delta\lambda)(\vb{x}_c + \boldsymbol{\delta} \vb{x}) \end{equation}\] to hold. By introducing the current \[\begin{equation} \vb{r}_c = \vb{A} \vb{x}_c - \lambda_c \vb{x}_c \thinspace , \end{equation}\] we can rewrite equation \(\eqref{eq:approximation_eigenequation}\) as \[\begin{equation} \label{eq:residual_vector_equation} \qty(\vb{A} - \lambda_c \vb{I}_{(n)}) \boldsymbol{\delta} \vb{x} - (\delta\lambda) \vb{x}_c = - \vb{r}_c \thinspace . \end{equation}\] Unfortunately, this is an underdetermined system of equations.