Rayleigh Quotient

Rewrite for minimizing 02/22/15, by maximizing x'Bx over x'Ax=1.

We go back to maximizing the Rayleigh quotient $\lambda(x)=\frac{x'Ax}{x'Bx},$ where we now assume that both $A$ and $B$ are positive definite. Maximizing $\lambda$ is equivalent to maximizing $\sqrt{x'Ax}$ on the condition that $\sqrt{x'Bx}=1$. By Cauchy-Schwartz $\sqrt{x'Ax}\geq\frac{1}{\sqrt{y'Ay}}x'Ay,$ and thus for the majorization we maximize $x'Ay$ over $x'Bx=1.$ This defines an algorithmic map which sets the update of $x$ proportional to $B^{-1}Ax,$ i.e. we have a shown global convergence of the power method to compute the largest generalized eigenvalue.

We can also establish the linear convergence rate quite easily, using \ref{T:ostrow}. For definiteness we normalize in each iteration, and set $$\mathcal{A}(\omega)=\frac{B^{-1}A\omega}{\|B^{-1}A\omega\|}.$$ At a point $\omega$ which has $B^{-1}A\omega=\lambda_1\omega,$ and $\omega'\omega=1$ we have $$\mathcal{M}(\omega)=\frac{1}{\lambda_1}(I-\omega\omega')B^{-1}A.$$ It follows that $\mathcal{M}$ has eigenvalues $0$ and $\frac{\lambda_s}{\lambda_1}$, with $\lambda_s$ the ``remaining'' eigenvalues of $B^{-1}A.$ Thus if $\lambda_1$ is the largest eigenvalue, we find a linear rate of $\rho=\frac{\lambda_1}{\lambda_2}.$

There are several things in this analysis which may go wrong, and they are all quite instructive.