Condition numbers: Find vector pair for which the equality holds

Question

I have that $Ax = b$. I would like to find a vector pair $(b, \delta b)$ for which the following equality holds:

$$\frac{||\delta x||_2}{||x||_2} = \kappa_2(A) \frac{||\delta b||_2}{||b||_2},$$

where $\kappa_2(A)$ = $\frac{\sigma_1}{\sigma_m}$

Generally we have LHS $\leq $ RHS, but there should exist some $b$ and $\delta b$ for which equality is achieved. I am supposed to express the vectors $(b, \delta b)$ in terms of left singular vectors.

So far I have (or at least think I have) that $b$ is a multiple of the first column of $U$, where $A = U \Sigma V^T$. But that's as far as I've come.

I have been trying to somehow show that $||b||_2 = \sigma_1 ||x||_2$ and that $||\delta b ||_2 = \frac{||\delta x||_2}{\sigma_m},$ because then the equality would follow, but I haven't succeeded.

Answer 1

If $u$ and $v$ are left and right singular vectors of $A$, with $\|u\|=\|v\|=1$ and singular value $\sigma$, then $$Av = \sigma u$$ $$\|Av\| = \sigma \|u\| = \sigma = \sigma \|v\|.$$

Does that help?

Answer 2

Take $\delta b = -\epsilon \|b\|_2 w$, with $\|w\|_2 = 1$, and $\|A^{-1}w\|_2 = \|A^{-1}\|_2$. Then $\delta x = \epsilon \|b\|_2 A^{-1}w$ and $$\|\delta x\|_2 = \epsilon \|b\|_2 \|A^{-1}w\|_2 = \epsilon \|b\|_2 \|A^{-1}\|_2 = \epsilon \|A^{-1}\|_2\|Ax\|_2$$

Take $x$ such that $\|Ax\|_2 = \|A\|_2\|x\|_2$. Then $$\frac{\|\delta x\|_2}{\|x\|_2} = \frac{\epsilon \|A^{-1}\|_2\|A\|_2\|x\|_2}{\|x\|_2} = \kappa_2(A)\epsilon = \kappa_2(A)\frac{\|\delta b\|_2}{\|b\|_2}$$

Let $u_i$, $v_i$ denote left and right singular vector associated with $i$-th singular value $\sigma_i$ of $A$, that is $Av_i = \sigma_i u_i$ and $\|u_i\|_2 = \|v_i\|_2 = 1$. Additionally, if $A$ is invertible, $A^{-1} u_i = \sigma_i^{-1} v_i$.

As $x$ we may take $v_1$ since $Av_1 = \sigma_1 u_1 = \|A\|_2u_1$ and $\|Ax\|_2 = \|A\|_2 = \|A\|_2\|x\|_2$. Then $b = Ax = \sigma_1 u_1$. As $w$ we may take $u_m$ since $A^{-1}u_m = \sigma_m^{-1}v_m = \|A^{-1}\|_2 v_m$ and $\|A^{-1}w\|_2 = \|A^{-1}\|_2$.