How can you explain the following bound on the inner product?

Question

I am reading a paper on stability of CG, and I came across the following statement:

\begin{equation} \frac{\|A\|\,\|p\|^2}{\langle p,Ap\rangle} \leq \kappa(A) \end{equation} where $\kappa(\cdot)$ is the condition number and $\langle \cdot, \cdot \rangle$ the inner product.

Can you, please, help me understand this bound? I cannot see how it was derived. The authors simply state this as a fact. What obvious fact am I missing? $p$ is the search direction vector, and $A$ is the SPD matrix.

Thank you!

• here is the paper: http://www.cs.cas.cz/tichy/download/public/StTi2004.pdf The statement is on page 13, at the bottom, on the first line after equation 4.27: "Using (4.5)–(4.8) and ...."

Answer 1

The bound is a consequence of the following three facts:

1. The condition number is defined as the ratio of the largest eigenvalue $\lambda_\textrm{max}$ and the smallest eigenvalue $\lambda_\textrm{min}$.

2. The spectral norm $\|A\|_2$ of a symmetric positive definite matrix is $\lambda_\textrm{max}$ (since, as Arnold Neumaier pointed out, it is the square root of the largest singular value).

3. By the Courant-Fischer theorem, the smallest eigenvalue of a symmetric matrix $A$ satisfies $$ \lambda_\textrm{min} = \min_{x\neq 0} \frac{\langle x,Ax\rangle}{\langle x,x\rangle}. $$

Putting this together, we have for any $p\neq 0$ that $$ \kappa(A) = \frac{\lambda_\textrm{max}}{\lambda_\textrm{min}} = \frac{\|A\|}{\min_x \frac{\langle x,Ax\rangle}{\|x\|^2}} \geq \frac{\|A\|}{\frac{\langle p,Ap\rangle}{\|p\|^2}} = \frac{\|A\|\|p\|^2}{\langle p,Ap\rangle} $$ since the fraction can only become smaller for any $p$ that is not the minimizer of the denominator.

Answer 2

This assumes that the matrix $A$ is symmetric. Transform it to diagonal form, and observe that the singular values are the absolute values of the eigenvalues. THen the derivation essentially reduces to the definition of the condition number as the quotient of the extreme singular values.