3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ To solve the linear system $Ax=B$ it is necessary to invert $A$ so depending on the size of $\det(A)$ we can have serious numerical problems and naturally, discrepancies. $\endgroup$
    – Cesareo
    Mar 4, 2022 at 12:20

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Surely this does not answer the question as for example if A=B=0 then X and X' can take any values and so we do not have X'=1.05X. It is true if A is non singular but otherwise it seems false that X'=1.05X in general, although as you have shown 1.05X does always satisfy the equation. $\endgroup$
    – Fishbane
    Mar 4, 2022 at 13:01
  • $\begingroup$ @Fishbane The question, as I understand it, says: "If $Ax=b$ and if $b'=1.05b$, then dose $x'=1.05x$ satisfy the equation $Ax'=b'$"? and the answer to that question, as shown in my post, is "yes". Clearly, the OP also agrees that my answer is what they needed, so I don't really see a basis for your claim that "this does not answer the question"... $\endgroup$
    – 5xum
    Mar 4, 2022 at 14:21
  • $\begingroup$ Fair enough, I read it as asking if x' is a solution to Ax'=b' then is x'=1.05x, and based on the rest of their post it seems reasonable to interpret it this way. However yes under the interpretation you use you have answered the question. $\endgroup$
    – Fishbane
    Mar 4, 2022 at 14:27

You must log in to answer this question.

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