Looking for an explanation for a conditioning number inequality

Question

I need help understanding why the first (highlighted) inequality holds true. I've been able to find a proof for the second inequality but can't figure out the first one.

Answer 1

From $Ax=b$ and $(A+\delta A)(x+\delta x)=b$, we have $$ \delta x = A^{-1}\delta A(x+\delta x), $$ which gives the second inequality $$\tag{1} \frac{\|\delta x\|}{\|x+\delta x\|}\leq\mathrm{cond}(A)\frac{\|\delta A\|}{\|A\|} $$ using the triangle inequality.

Using the given assumption $\|x\|<\|\delta x\|$ and the triangle inequality again, we have $\|x+\delta x\|\leq 2\|x\|$, so $$ \frac{\|\delta x\|}{\|x\|}\leq 2\frac{\|\delta x\|}{\|x+\delta x\|}, $$ which together with (1) gives the first inequality.

Answer 2

It is possible to derive the estimate:

$$\frac{\|δx\|}{\|x\|}\leqslant \frac{\text{cond}{(A)}}{1-\|A^{-1}\|\|δA\|}\frac{\|δA\|}{\|A\|}$$

To derive that estimate one needs the condition $\|δA\|\|A^{-1}\|\leqslant 1$. That is necessary, because otherwise you might loose regularity on $A+δA$. Hence your disturbed system is not solvable.

If you were to enforce a more harsh condition like $\|δA\|\|A^{-1}\|\leqslant 1/2$, you get the desired result.

---

EDIT:

I think I need to elaborate a bit more about my statement about the regularity of $A+δA$ regularity, to make this a good answer.

There exists a small theorem that states: For a matrix $B∈ℝ^{n×n}$, with $\|B\|<1$, the matrix $I+B$ is regular and it holds $$\|(I+B)^{-1}\|\leqslant \frac{1}{1-\|B\|} \tag{1}\label{1}$$

Remembering the task, it states that there is only perturbation $A$, not in the rhs $b$. Therefore, we want to solve $Ax=b$, but actually we solve $\tilde{A}\tilde{x}=b$, with $\tilde{x} = x+δx$.
So we know:

$$(A+δA)\tilde{x} = \tilde{A}\tilde{x} = b \tag{2}\label{2}$$ and $$(A+δA)x = Ax + δAx =b+δAx \tag{3}\label{3}$$

Combining \eqref{2} and \eqref{3} leads to: $$δx = \tilde{x}-x = -[A+δA]^{-1}δAx \tag{4}\label{4}$$

Another intermediate result is $$A+δA = A[I+A^{-1}δA]. \tag{5}\label{5}$$

Using \eqref{5} in \eqref{4} leads to:

\begin{align*} \|δx\|&\leqslant\|[I+A^{-1}δA]^{-1}A^{-1}δAx\|\\ &\leqslant \|[I+A^{-1}δA]^{-1}\|\, \|A^{-1}\|\, \|δA\|\, \|x\|, \end{align*}

and because of $\|A^{-1}δA\|\leqslant\|A^{-1}\|\|δA\|\leqslant 1$ it is possible to use the theorem \eqref{1}, which leads to: \begin{align*}\|δx\|&\leqslant\frac{\|A\|^{-1}}{1-\|A^{-1}δA\|}\|δA\|\|x\| \\ &\leqslant\frac{\text{cond}(A)}{1-\|A^{-1}δA\|}\frac{\|δA\|}{\|A\|}\|x\| \end{align*}

---

The last thing we should do is to proof the theorem.

The matrix $I+B$ is regular. That can be shown, by proving that $I+B$ is an injective mapping. And that is true, because it holds $$\|(I+B)x\|\geqslant \|x\|-\|Bx\|\geqslant (1-\|B\|)\|x\|,$$ and $1-\|B\|>0$ due to the requirements of the theorem.

And the following lengthy statement finishes the proof. \begin{align*} 1 &= \|I\| = \|(I+B)(I+B)^{-1}\| = \|(I+B)^{-1} + B(I+B)^{-1}\| \\ &\geqslant\|(I+B)^{-1}\| - \|B\|\|(I+B)^{-1}\| = \|(I+B)^{-1}\|(1-\|B\|)>0 \end{align*}

---

The proof of that theorem is more or less a quote from the German lecture notes of Thomas Richter. I attended his lectures, some years ago. If you can understand German, I recommend reading his lecture notes, and the lecture notes (or now books) of Rolf Rannacher.