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
    Commented 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
    Commented 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
    Commented Jan 9, 2018 at 17:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .