# Bound of perturbation in solution of linear equation

Let $A$ be the matrix $\begin{bmatrix}1&k\\0&1\end{bmatrix}$. The norm (1-norm and maximum norm is $1+k$ and the condition number is $(1+k)^2$ which grows large for large $k$.

Consider the equation $Ax=b$ with $b=\begin{bmatrix}1\\1\end{bmatrix}$. The solution is $x=\begin{bmatrix}1-k\\1\end{bmatrix}$. If we perturb only $b$ by non-zero $\delta_1, \delta_2$ so that $b+\delta b=\begin{bmatrix}1+\delta_1\\1+\delta_2\end{bmatrix}$, the change in $x$ is $\delta x=\begin{bmatrix}\delta_1-k\delta_2\\\delta_2\end{bmatrix}$.

Find a bound on $\frac{||\delta x||}{||x||}$ in terms of $\frac{||\delta b||}{||b||}$ using either the 1-norm or the maximum norm to show that this problem is well-conditioned, despite the large condition number of $A$.

Attempt at solution:

I started out by using the 1-norm and writing out $\frac{||\delta b||}{||b||}=\frac{|\delta_1|+|\delta_2|}{2}$ and $\frac{||\delta x||}{||x||}=\frac{|\delta_1-k\delta_2|+|\delta_2|}{|1-k|+1}$. Using the triangle inequality on the numerator of the $x$ term, we get $\frac{||\delta x||}{||x||}\le\frac{|\delta_1|+|k||\delta_2|+|\delta_2|}{|1-k|+1}$.

Then, noting that we're letting $|k|$ grow large, the denominator will grow large, so for $|k|\gg 1$, $\frac{||\delta x||}{||x||}\le\frac{|\delta_1|+|k||\delta_2|+|\delta_2|}{2}$. (I made the denominator 2 to match $\frac{||\delta b||}{||b||}$, but the exact number doesn't matter too much.)

I don't see much more bounding that I can do and, in fact, the numerator grows quite large with $k$, although it is linear while the condition number of $A$ grows quadratically with $k$. Is there any more simplification that can be done, or is the answer supposed to be $\frac{||\delta x||}{||x||}\le\frac{||\delta b||}{||b||}+\frac{|k\delta_2|}{2}$?

Thanks for the help.

You have

$$\frac{\|\delta b\|_1}{\|b\|_1} = \frac{|\delta_1| +|\delta_2|}{2}$$

And for $k > 1$,

$$\frac{\|\delta x\|_1}{\|x\|_1} = \frac{|\delta_1-k\delta_2| +|\delta_2|}{k}$$

So

$$\frac{\|\delta x\|_1}{\|x\|_1} \leq \frac{|\delta_1| +|\delta_2|}{k} + |\delta_2|$$

So clearly,

$$\frac{\|\delta x\|_1}{\|x\|_1} \leq 4 \frac{\|\delta b\|_1}{\|b\|_1}$$

• But if $k$ is large and negative $|\delta_1-k\delta_2|\ge|\delta_1|+|\delta_2|$, right? – user261210 Aug 11 '15 at 2:43
• If $k < -1$ then $\| x \|_1 = |k|+2$, so $$\frac{\|\delta x\|_1}{\|x\|_1 }= \frac{ | \delta_1 - k \delta_2 |+|\delta_2|}{|k|+2} \leq \frac{ | \delta_1| + |\delta_2|+ |k| |\delta_2 |}{|k|+2} = \frac{ | \delta_1| + |\delta_2|}{|k|+2}+ \frac{|k|}{|k|+2} |\delta_2 | \leq 2 ( | \delta_1| + |\delta_2| )$$ – Tryss Aug 11 '15 at 13:58