For Ax=B, where all variables are matrixes, If A is constant, and B'=1.05B, does x'=1.05x for Ax'=B'?

Question

I feel like the answer to this is is quite a simple yes, but I was asked to prove it on a MATLAB script by solving for x on matrices of increasing sizes, and to my surprise, it was never exactly a 5% difference, and it seems the discrepancy grows as the number of elements in the array increases. What's going on here? Is it some sort of computing estimation quirk or is my understanding incorrect?

Taking the question further, I also tested if all elements in B were given a maximum of a 5% error, multiplying them by random values between 0.95 and 1.05. My thought was that the error in x would be bounded by 5% as well, because a sort of weighted average of every error in B would be bounded between 1.05 and 0.95, but the error in this test grew exponentially with the size of the matrix, much faster than the previous test. Any explanation about what's going on here would be very appreciated.

Answer 1

We can see that if $\det(A)=0$ then $X'=1.05X$ is not the only solution and there are solutions arbitrarily far away from $X$.

If instead $\det(A)\neq0$ then as 5xum shows $X'=1.05X$ is a solution and by the invertablilty of $A$ it is the unique solution.

Regarding the second part of your question, it is clear that we cannot bound the error if $\det(A)=0$ so we will assume $\det(A)\neq0$.

As $\det(A)\neq0$ $A$ is invertible.

Assume $B'=B+E$ for some error $E$.

We see that $$AX'=B'$$ $$X'=A^{-1}B'$$ $$X'=A^{-1}(B+E)$$ $$X'=X+A^{-1}E$$

so $X'$ has error $F=A^{-1}E$ relative to $X$.

Define $\|M\|_{\infty}=\max(|M_{ij}|)$ and define

$\|M\|_{op}=\max(\frac{\|MX\|_{\infty}}{\|X\|_{\infty}} for X\neq0)$

Then

$$\frac{\|F\|_{\infty}}{\|E\|_{\infty}}=\frac{\|A^{-1}E\|_{\infty}}{\|E\|_{\infty}}\leq\|A^{-1}\|_{op}$$

$$\|F\|_{\infty}\leq\|A^{-1}\|_{op}\|E\|_{\infty}$$

Now if the relative error in $B'$ is bounded by $\alpha$ we have

$$\|E\|_{\infty}\leq\alpha\|B\|_{\infty}$$

so we have

$$\|F\|_{\infty}\leq\alpha\|A^{-1}\|_{op}\|B\|_{\infty}$$

Dividing by $\|X\|_{\infty}$ we have

$$\frac{\|F\|_{\infty}}{\|X\|_{\infty}}\leq\alpha\|A^{-1}\|_{op}\frac{\|B\|_{\infty}}{\|X\|_{\infty}}=\alpha\|A^{-1}\|_{op}\frac{\|AX\|_{\infty}}{\|X\|_{\infty}}\leq\alpha\|A^{-1}\|_{op}\|A\|_{op}$$

Now assume $min(|X_{ij}|)\neq0$ and define $\hat{X}=\frac{max(|X_{ij}|)}{min(|X_{ij}|)}$. Then,

$$\frac{max(|F_{ij}|)}{min(|X_{ij}|)}=\frac{\|F\|_{\infty}}{\|X\|_{\infty}}\hat{X}\leq\alpha\|A^{-1}\|_{op}\|A\|_{op}\hat{X}$$

and so the relative error of $X'$ is bounded by $\alpha\|A^{-1}\|_{op}\|A\|_{op}\hat{X}$

I suspect a better bound exists, however if $min(|X_{ij}|)=0$ there exist systems where a bounded relative error in $B'$ gives unbounded relative error in $X'$.

Hopefully that answers your question, feel free to let me know if anything is unclear.

Answer 2

If

1. We know that $Ax=b$ for some matrix $A$ and some vector $b$,
2. $\alpha$ is any scalar
3. We define $x'=\alpha x$ and $b' = \alpha b$,

then

$$Ax' = A(\alpha \cdot x) = \alpha(\cdot Ax) = \alpha b = b'$$

where the first equality is by definition, the second comes from linearity of $A$, the third comes from existing assumptions, and the last is again definition.