3
$\begingroup$

Suppose we have a square $n\times n$ real matrix $A$ of full rank such that the squares of the elements in each row sum to 1, an $n\times 1$ vector of variables $x$, and an $n\times 1$ real vector $a$, such that $A\cdot x = a$. We can of course take the inverse of $A$ to solve uniquely for $x$.

My question is as follows: suppose we do not know $a$ exactly, but only up to additive error epsilon: that is, we know $a'$ such that $a' = a + error$, where $error$ is a real $n\times 1$ vector with each component in the range $[-\epsilon,\epsilon]$. Vector $x$ is no longer uniquely determined. However, we can solve for some $x'$ such that $x' = x + error'$. My question is, what can we say about the magnitude of the components of $error'$, and how they relate to $\epsilon$?

Improve this question
$\endgroup$
1
  • $\begingroup$ I think you can't say anything if you only assume that $A$ is invertible. For example, if the first row of $A$ is $(1/\sqrt{2},1/\sqrt{2})$, while the second row of $A$ is $(\sqrt{1/2-\delta},\sqrt{1/2+\delta})$, then the inverse of $A$ has ``large'' entries. For an appropriately signed error, you can make error' as large as you want by decreasing $\delta$. I think you'll have to make assumptions on things like the condition number of $A$. In general, Golub and van Loan could be a good reference. $\endgroup$
    – user2734
    Jan 27, 2010 at 22:44

2 Answers 2

Reset to default
2
$\begingroup$

To be a little more precise, the assumption here is that $\| error \|_\infty \le \epsilon$ and it seems you want to bound $\| error' \|_\infty$. So from $error' = A^{-1} error$ it follows that $\| error'\|_\infty \le \| A^{-1} \|_\infty \epsilon$. Here $\| A^{-1} \|_\infty$ is the operator norm of $A^{-1}$ induced by the $\infty$-norm on $\mathbb{R}^n$, which is easily expressed in terms of the entries of $A^{-1}=[b_{ij}]$: $$\| A^{-1} \|_\infty = \max_{1\le i\le n} \sum_{j=1}^n |b_{ij}|.$$

Improve this answer
$\endgroup$
4
$\begingroup$

See the numerical analysis literature on condition numbers. For a start, see http://en.wikipedia.org/wiki/Condition_number, which links to other references.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Although that's the right literature to look at, for this specific question the condition number isn't the right quantity to look at, since only the norm of A^{-1} (and not the norm of A itself) plays a role. $\endgroup$
    – Mark Meckes
    Jan 28, 2010 at 3:44
  • $\begingroup$ It's because usually one speaks about relative condition numbers, while OP looks for an absolute condition number (i.e., the error on $x$ is measured as $\|\tilde{x}-x\|$ rather than $\frac{\|\tilde{x}-x\|}{\|x\|}$). But it still fits in the theory. $\endgroup$
    – Federico Poloni
    Jan 9, 2018 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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