3
$\begingroup$

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!

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.