6
$\begingroup$

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!

1 Answers 1

2

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!