2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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} $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But if $k$ is large and negative $|\delta_1-k\delta_2|\ge|\delta_1|+|\delta_2|$, right? $\endgroup$ – user261210 Aug 11 '15 at 2:43
  • $\begingroup$ 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| )$$ $\endgroup$ – Tryss Aug 11 '15 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.