# Solving a noisy set of linear equations.

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

-
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

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