Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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. –  user2734 Jan 27 '10 at 22:44

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer

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

share|improve this answer
    
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. –  Mark Meckes Jan 28 '10 at 3:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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