Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Edit: If any information is missing, please tell me and I'll edit the question. Thanks again!

The conjugate gradient (cg) method was applied to a positive definite Matrix $A$. It is only known that $||e||_A=1$ and $||e^{10}||_A=2^{-9}$ (where $e$ is the error $||e^k||_A= ||x-x^k||_A$). Calculate with this information a lower bound for $κ(A)$ (where $κ$ is the condition number) and compare it with the equation $$k \geq \frac{1}{2}(\sqrt{κ(A)}\ln(2/ε))$$ where ε is the factor by which the error is reduced, defined as $$||e^k||_A= ||x-x^k||_A \leq ε||e^0||_A$$

Here's what I have so far. If I have understood it correctly $ε=2^{-9}/1=2^{-9}$. I however don't understand how only from that can I calculate the condition number. Doesn't the condition number require knowing the matrix and it's inverse? $κ=||A||||A^{-1}||$

I have calculated what $κ$ should be using the equation $k \geq \frac{1}{2}(\sqrt{κ(A)}\ln(2/ε))$ and I got $$10 \geq \frac{6.93}{2}(\sqrt{κ(A)})$$ $$2.89 \geq \sqrt{κ(A)}$$ $$8.33 \geq κ(A)$$

How can I move forward? Thanks in advance!

share|improve this question

1 Answer 1

up vote 2 down vote accepted
+100

My attempt ... i'm not a math guy so feel free to throw it in the trash!

I think you should use the relationship between the convergence rate of CG and the condition number of the $A$-matrix. Check these lecture notes for the full details, I refer specifically to formula (52) on page 36

$$ \lvert\lvert e_{(i)}\rvert\rvert_A\leq % 2\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^i% \lvert\lvert e_{(0)}\rvert\rvert_A $$

where $e_{(0)}=x_{(0)}-x$ is the initial error. In your case $\lvert\lvert e_{(0)}\rvert\rvert_A=1$ and $i=10$

$$ \frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\geq% \left(\frac{\lvert\lvert e_{(10)}\rvert\rvert_A}{2}\right)^{1/10}=\frac{1}{2} $$

the latter equation can be solved easily noting that $f(\kappa)=(\sqrt{k}-1)/(\sqrt{\kappa}+1)$ is a monotonically increasing function in $[1,\infty)$, therefore if $f(\bar{\kappa})= 1/2 \Rightarrow$ then $f(\kappa > \bar{\kappa})\geq 1/2$, implying the lower bound $\kappa\geq\bar{\kappa}$. The value of $\bar{\kappa}$ is obtained solving

$$ \frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}=\frac{1}{2}\Rightarrow\bar{\kappa}=3^2=9 $$

Therefore the lower bound should be $\kappa\geq 9$. Now, on the lecture notes I have used, the direction of your inequality is reversed, so you should be computing a lower bound also... but i'm not sure about that! Cheers!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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