Relative error bound for Ax=b

792 Views Asked by At

I have the matrix $A= \begin{pmatrix} 4-\alpha & 12+\alpha \\ 2-\alpha & 6+\alpha \end{pmatrix}$, a pair $\delta x,\delta b\in\mathbb{R^2}\backslash\{0\}$ satisfying $A\delta x=\delta b$, and a pair $x,b\in\mathbb{R^2}$ satisfying $Ax=b$. I also have that $\alpha\in(0,1)$.

I am being asked to show that $\frac{{\|\delta x\|}_\infty}{{\|x\|}_\infty}\leq \frac{{\|\delta b\|}_\infty}{{\|b\|}_\infty}$ but cannot make any progress at all. I have tried using $\|\delta x\|\leq\|A^{-1}\|_{\infty}\|\delta b\|_{\infty}$ and $\|A\|_{\infty}\|x\|_{\infty}\geq\|\delta b\|_{\infty}$ with no success. This also leads to the inequality $\frac{{\|\delta x\|}_\infty}{{\|x\|}_\infty}\leq \kappa_{\infty}(A)\frac{{\|\delta b\|}_\infty}{{\|b\|}_\infty}$, with $\kappa_{\infty}(A)$ being the condition number, but since $\kappa_{\infty}(A)=\frac{36}{\alpha}+4$ and $\alpha>0$, I can't use this to get a finite upper bound on the condition number.

1

There are 1 best solutions below

0
On

This problem seems strange. Usually, we consider two cases of solving $Ax=b$, one is small perturbation of $b$ with the change of solution $x$, the other is small perturbation of matrix $A$ with the change of solution $x$. For sufficiently small $\alpha$, we will get a ill-conditioned matrix $A$.


Theorem
Assume $A$ is invertible, $b \neq 0$, and $$A(x+\delta x) = b + \delta b,$$ then we have $$\frac{\|\delta x\|}{\|x\|}\leq\|A^{-1}\|\|A\|\frac{\|\delta b\|}{\|b\|}.$$


According to this theorem, if $\alpha \to 0$, the matrix $A$ will approach to singular, which meets the result of $\kappa_\infty (A) = \frac{36}{\alpha}+4$. In fact, we get an upper bound with parameter $\alpha$, for fixed $\alpha \in(0,1)$, we will get a finite upper bound.

I think your results is right.