Show that for a nonHermitian matrix A element Cm times m the

Show that for a non-Hermitian matrix A element C^m times m, the Rayleigh quotient r(x) gives an eigenvalue estimate whose accuracy is generally linear, not quadratic. Explain what convergence rate this suggests for the Rayleigh quotient iteration applied to non-Hermitian matrices.

Solution

Definition

Let A C ^m×m, x R ^m. The quantity r(x) = x ^T Ax /x^T x R is called a Rayleigh quotient.

Note If x is an eigenvector of A, then Ax = x and r(x) = x ^Tx/ x^Tx = .

But generally wecan show that _min r(x) _max.

Note : that the Rayleigh quotient is that it forms the least squares best approximation to the eigenvalue corresponding to x. Consider x Ax.

This is similar to the standard least squares problem Ax b.

But we can ask to find such that

||Ax x||₂ is minimized. The associated normal equations (cf. A^T Ax = A^T b) are given by x ^Tx = x ^T Ax (or)

= x ^T Ax /x^Tx = r(x). There fore, the Rayleigh quotient provides an optimal estimate for the eigenvalue. In fact,

r(x) r(qJ ) | {z } =J = O(||x q_J || ²₂ ) as x q_J .

Here q_J is the eigenvector associated with _J , and the estimate shows that the convergence rate of r(x) to the eigenvalue is quadratic.

In order to prove this fact we need the first-order (multivariate) Taylor expansion of r about x = qJ :

r(x) = r(qJ ) + (x qJ ) ^T r(qJ ) + O(||x qJ||_²2 ).

If we can show that the linear term is not present, then this identity will imply the quadratic convergence result we wish to prove. We will show that r(qJ ) = 0. First, r(x) = [ r(x)/ x₁ , r(x) /x₂ , . . . , r(x) x_m] .

One of these partials can be computed using the quotient rule as r(x) xj = xj x ^T Ax x^Tx = xj (x ^T Ax)x ^Tx x ^T Ax xj x ^Tx (x^Tx) 2 . Here xj (x ^T Ax) = xj (x ^T )Ax + x ^T xj (Ax)