1

How would you solve this excersize? I have tried it but I am not posting my calculations since it is wrong and I would spend a lot of time writing it in latex.

The problem. Find the condition number with respect to $\Vert \cdot \Vert_{\infty}$ of \begin{equation*} \begin{pmatrix} 1 & d \\ d & 1 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \end{equation*} supposing $d \neq \pm 1$. It should be $K_{\infty}(A) = \left\vert\frac{\left\vert d\right\vert + 1}{\left\vert d\right\vert - 1}\right\vert$. I found two different values depending on $\left\vert d\right\vert < 1$ or $\left\vert d\right\vert > 1$, more specifically if $\left\vert d\right\vert < 1$ I found \begin{equation*} \left\vert \frac{2d}{1-d}\right\vert \end{equation*} while if $\left\vert d\right\vert > 1$ I found \begin{equation*} \left\vert \frac{2}{1-d}\right\vert. \end{equation*}

EDIT In the two solutions given you use $K(A) = \Vert A^{-1} \Vert \Vert A \Vert$.

My result is different because I used a different definition of $K$ i.e.
$K(d) = \left\Vert G'(d)\right\Vert \frac{\left\Vert d\right\Vert}{\left\Vert G(d)\right\Vert}$ where $G$ is the function $d \mapsto x(d)$ which gives the unique solution depending on the parameter $d$.

In the case in which I want to solve $A x = b$ and $d$ it is contained only in $b$ we have $$x = A^{-1}b$$ so $$G(d) = A^{-1}b \quad \text{and} \quad G'(d) = A^{-1}.$$ We so obtain $$K(d) = \left\Vert A^{-1}\right\Vert \frac{\left\Vert b\right\Vert}{\left\Vert A^{-1}b\right\Vert} = \left\Vert A^{-1}\right\Vert \frac{\left\Vert Ax\right\Vert}{\left\Vert x\right\Vert} \leq \left\Vert A^{-1}\right\Vert \left\Vert A\right\Vert.$$ But I don't understand why in the case in which it is $A$ (not $b$) depending of $d$ we can still use the defintion $K(d) = \left\Vert A^{-1}\right\Vert \left\Vert A\right\Vert$.

Nisba
  • 777
  • The standard condinition number only depends on the matrix $A$ and is indepent of $b.$ If you define your own condinition number you should not be surprised if it is different to the standard. – gammatester Aug 26 '16 at 08:48
  • This is not my definition. My book defines the condition number of the problem as the definition I have given (to be more precise that is the definition of the first order condition number, we works always with that), the exercise asks me to find it. In the case in which only $b$ is varying it turns out that (see my calculations above) the definition of the condition number of the matrix $A$ can be used to give an upper bound to the condition number of the problem (for practical purposes it is sufficient to have an upper bound). – Nisba Aug 26 '16 at 08:55
  • I think I have understood. I interpreted the text of the exercise as if d is the given data that can vary and so I obtained different results from the ones that follows interpreting d as a constant. So I will mark as best answer the one given chronologically first. – Nisba Aug 26 '16 at 09:25
  • I cannot follow your EDIT arguments. IMO $G(d)$ is the vector $$G(d) = \Big (\frac{1}{1-d^2}, -\frac{d}{1-d^2}\Big)$$ and therefore $G'(d)$ is not $A^{-1}$ but $$G'(d) = \Big (\frac{2d}{(1-d^2)^2}, -\frac{1+d^2}{(1-d^2)^2}\Big)$$ – gammatester Aug 26 '16 at 09:31
  • you are right, I should have written $G(b)$ and regard $d$ only as a constant. In that case $A^{-1}$ coincides with the Jacobean of the transformation $b \mapsto A^{-1}b$. I should have omitted to write the dependence from $d$ from everywhere. – Nisba Aug 26 '16 at 12:54

2 Answers2

0

I have never delved into this material, but I did some wikipedia-ing.

$$\kappa(A) = ||A^{-1}||\cdot ||A||$$

We first find $A^{-1}$:

$$A^{-1} = \begin{pmatrix} \dfrac{1}{1-d^2} & \dfrac{-d}{1-d^2} \\ \dfrac{-d}{1-d^2} & \dfrac{1}{1-d^2}\end{pmatrix}$$

Since the rows contain the same entries for both $A$ and $A^{-1}$,

$$||A^{-1}|| = \left|\dfrac{1}{1-d^2}\right| + \left|\dfrac{-d}{1-d^2}\right| = \dfrac{1+|d|}{|1-d^2|} = \dfrac{1+|d|}{|(1+|d|)(1-|d|)|} = \dfrac{1}{|1-|d||}$$

and

$$||A|| = \left|1\right| + \left|d\right| = 1+|d|$$

So

$$ \kappa(A) = ||A^{-1}||\cdot ||A|| = \dfrac{1 + |d|}{|1-|d||}$$

David P
  • 12,320
  • Thank you, but please see my edit in the question. – Nisba Aug 26 '16 at 08:41
  • It turns out the same. $$||A^{-1}||\cdot \dfrac{||b||}{||A^{-1}b||} = \dfrac{1}{|1-|d||}\cdot \dfrac{|1-d^2|}{1-|d|} = \dfrac{1+|d|}{|1-|d||}$$ – David P Aug 26 '16 at 09:32
  • what you have written is it always in the case that only $b$ is perturbed. My erroneous interpretation of the problem was that $A$ is perturbed. In that case your calculation is correct. – Nisba Aug 26 '16 at 12:51
0

The relevant definitions are $$K_{\infty}(A)=||A||_{\infty}||A^{-1}||_{\infty}$$ and $$||A||_{\infty}=\max_{i=1,2}\sum_{j=1}^2|a_{ij}|$$ Since $$A^{-1} = \frac{1}{1-d^2} \begin{pmatrix} 1 & -d \\ -d & 1 \end{pmatrix}$$ you have $||A||_{\infty}=1+|d|$ and $$||A^{-1}||_{\infty} = \frac{1}{|1-d^2|}(1+|d|)= \frac{1}{|1-|d|^2|}(1+|d|) = \frac{1+|d|}{|(1-|d||)(1+|d|)|} = \frac{1}{|1-|d||} $$ and therefore $$K_{\infty}(A)=||A||_{\infty}||A^{-1}||_{\infty}=\frac{1+|d|}{|1-|d||}$$

gammatester
  • 18,827