Rayleigh-Ritz, Background:

Let's consider more generally the case for $A$ an $n \times$ Hermitian matrix and ${\bf x}$ is an $n-$dimensional vector. We indicate ``hermitian'' as $\dagger$, which means that the complex conjugate of the transpose of $A$ is the same as $A$. So, for short, $A^\dagger = A$. If $A$ is a real matrix, $A^{T} = A$. These matrices often arise from self-adjoint continuous operators which model some physical process. The complex version appears often in the context of quantum mechanics and acoustics.

We will indicate by an overbar the operation of taking the conjugate transpose. If $A$ and ${\bf x}$ were real, this operation would simply involve the transpose.

Since $A^\dagger = A$ the eigenvalues are real and can be organized as

$$\lambda_{min}\equiv\lambda_1 \le \lambda_2 \le \lambda_3 \cdots \le \lambda_n \equiv \lambda_{max}.$$

We will see that the smallest and largest eigenvalues may be thought of as the solution to a constrained minimum and maximum problem.

Theorem (Rayleigh-Ritz): Let $A$ as above and the eigenvalues ordered as above. Then

$$\lambda_1 \overline{\bf x} {\bf x} \le \overline{\bf x} A ... ...line{\bf x} {\bf x}, \qquad \mbox{for all} {\bf x} \in C^{n}.$$

Furthermore,

$$\lambda_{max} = \max_{{\bf x} \ne 0} \frac{ \overline{\bf x}... ...x}} {\overline{\bf x} {\bf x}} = \max_{\vert{\bf x}\vert^2=1},$$

and

$$\lambda_{min} = \min_{{\bf x} \ne 0} \frac{ \overline{\bf x}... ... x}} {\overline{\bf x} {\bf x}}= \min_{\vert{\bf x}\vert^2=1}.$$

Proof: Since $A=A^\dagger$ then there exists a unitary matrix $U$ such that $A=U \Lambda U^{\dagger}$, with $\Lambda = diag(\lambda_1, \lambda_2, \ldots, \lambda_n)$. For any ${\bf x} \in C^n$ we have

$$\overline{\bf x} A {\bf x} = \overline{\bf x} U \Lambda U^{... ...}) = \sum_{i=1}^n \lambda_i \vert(U^\dagger {\bf x})_i\vert^2.$$

Since $\vert(U^\dagger {\bf x})_i\vert^2$ is non-negative, then

$$\lambda_{min} \sum_{i=1}^n \lambda_i \vert(U^\dagger {\bf x}... ...max} \sum_{i=1}^n \lambda_i \vert(U^\dagger {\bf x})_i\vert^2.$$

Because $U$ is unitary

$$\sum_{i=1}^n \lambda_i \vert(U^\dagger {\bf x})_i\vert^2 = \sum_{i=1}^n \vert{\bf x}_i\vert^2 = \overline{\bf x} {\bf x}.$$

Hence,

$$\lambda_1 \overline{{\bf x}} {\bf x} = \lambda_{min} \overli... ...rline{{\bf x}} {\bf x} = \lambda_n \overline{{\bf x}} {\bf x}.$$

These are sharp inequalities. If ${\bf x}$ is an eigenvector of $A$ associated with $\lambda_1$, then

$$\overline{\bf x} A {\bf x} = \lambda_1 \overline{\bf x} {\bf x}.$$

Same sort of argument holds for $\lambda_n$.

Furthermore, if ${\bf x} \ne 0$ then

$$\frac{ \overline{\bf x} A {\bf x}}{\overline{\bf x} {\bf x}} \le \lambda_n.$$

so

$$\max_{{\bf x} \ne 0} \frac{ \overline{\bf x} A {\bf x}}{\overline{\bf x} {\bf x}} = \lambda_n.$$ (85)

Finally, since ${\bf x} \ne 0$, then

$$\frac{ \overline{\bf x} A {\bf x}}{\overline{\bf x} {\bf x}}... ... x}{\bf x}}}}A \frac{{\bf x}}{\sqrt{\overline{\bf x}{\bf x}}}$$

and

$$\overline{ \frac{{\bf x}}{\sqrt{\overline{\bf x}{\bf x}}}} \frac{{\bf x}}{\sqrt{\overline{\bf x}{\bf x}}} = 1.$$

Hence, (86) is equivalent to

$$\max_{\vert{\bf x}\vert^2=1 } \overline{\bf x} A {\bf x} = \lambda_n.$$

Same sort of arguments hold for $\lambda_1$, in the context of the minimum. $\Box$

Algorithm

Now we will revert to the case of $A$ an $n\times n$ symmetric real matrix for the presentation of the algorithm.

Let ${\bf x}$ be an $n-$dimensional real vector. Choose some initial guess $x^{(0)}$, and compute

$$x^{(m+1)}=A x^{(m)}$$

then

$$\lambda_1^{(m+1)}=\frac{(x^{m+1}, x^{(m)})}{(x^{(m)}, x^{(m)})}\quad m\ge 0$$

where $(w,z)=\sum^n_{i=1}w_iz_i\quad w, z\in {\mathbb{R}}^n$ is the inner product.

In fact, by writing $x^{(m)}=\sum^n_{j=1}\alpha^{(m)}_j u_j$ then

$$\lambda_1 = \frac{\sum^n_{j=1}\vert\alpha^{(m+1)}_j\vert^{2}... ...m+1}}{ \sum^n_{j=1}\vert\alpha^{(m)}_j\vert^{2}\lambda_j^{2m}}$$

hence, it is easy to see that

$$\lambda_1^{(m+1)}= \lambda_1\left[1+\mathcal{O}\left(\left[\frac{\lambda_2}{\lambda_1}\right]^ {2m}\right)\right],$$

which is quadratic convergence, an improvement over the previous method. $\Box$