Proving a matrix iteration converges

Question

Consider the sequence $x_{n + 1} = Mx_{n} + b$. Suppose the matrix $M$ is symmetric and for any $x \neq 0$,

$$-1 < \frac{x^{T}Mx}{x^{T}x} < 1$$

holds. Prove that $x_{k}$ converges.

I know that a matrix iteration converges if $||M|| < 1$ for any subordinate norm. Also, I know that it converges if all eigenvalues have modulus less than or equal to $1$.

So, since $M$ is symmetric, all of its eigenvalues are real. I think that I need to use the fact that convergence follows from all eigenvalues having absolute value less than or equal to $1$. But how can I show this? I know, by the definition of an eigenvalue, we have

$$Mx = \lambda x$$

So can I just plug in an eigenvalue and get

$$-1 < \lambda \cdot \frac{x^{T}x}{x^{T}x} < 1, $$

which implies $|\lambda| < 1$?

Answer 1

$M$, being symmetric with real entries has real eigenvalues $\lambda_{min} \leq \cdots \leq \lambda_{max}$.

Function defined by :

$$r(x):=\frac{x^{T}Mx}{x^{T}x}$$

is called the Rayleigh quotient associated with symmetric matrix $M$.

A theorem says that the range of (set of values taken by) Rayleigh quotient is exactly $[\lambda_{min},\lambda_{max}]$, bounds included.

The hypothesis indicates that $-1<\lambda_{min}$ and $\lambda_{max}<1$. Thus all eigenvalues $\lambda$ of $M$ are such that $|\lambda|<1$. This is known to be sufficient condition of convergence for an affine sequence $x_{n + 1} = Mx_{n} + b.$

Answer 2

Hint: It suffices to show that there exists a vector $x^*$ such that we can rewrite the recursion in the form $$ (x_{n+1} - x^*) = M(x_n - x^*). $$ We can do so using the fact that every eigenvalue of $M$ has absolute value less than $1$.