In Matrix Computations (4th edition) by Gene H. Golub and Charles F. Van Loan, Problem 3.5.3 asks the following problem (and citing Kahan, William. "Numerical linear algebra." Canadian Math. Bulletin 9.757-801 (1966): 103.):
The system $Ax=b$ where $$A=\begin{pmatrix}2&-1&1\\-1&10^{-10}&10^{-10}\\1&10^{-10}&10^{-10}\end{pmatrix} \qquad b=\begin{pmatrix}2(1+10^{-10})\\-10^{-10}\\10^{-10}\end{pmatrix}$$ has solution $x=(10^{-10}, -1, 1)^T$. Show that if $(A+E)y=b$ and $|E|\le 10^{-8}|A|$, then $|x-y|\le 10^{-7}|x|$.
After several failures of trying, I went to look at Kahan's original paper. However, his paper only gives the conclusion without any proof. I've also looked at Nick Higham's Accuracy and Stability of Numerical Algorithms (section 7.2), and it just shows that $\operatorname{cond}(A,x)$ is small, which still applied to some normwise analysis.
I've also done some experiments with Mathematica (using rational numbers and symbolic computations to avoid rounding errors). It turns out that the componentwise result is true. So I'm wondering how can one actually prove this.
Thanks!
First, we have from $$\tag{1} Ax=b\quad\text{and}\quad(A+E)y=b $$ that $$ A(x-y)=Ey\quad\Rightarrow\quad x-y=A^{-1}Ey\quad\Rightarrow\quad |x-y|\leq|A^{-1}|\,|E|\,|y|. $$ Assuming that $|E|\leq\epsilon|A|$, $$\tag{2} |x-y|\leq\epsilon\,|A^{-1}|\,|A|\,|y|. $$ Let $\|\,|A^{-1}|\,|E|\,\|<1$ for a suitable matrix norm. Then the matrix $I-A^{-1}E$ is nonsingular and (1) gives $$ y=(I-A^{-1}E)^{-1}x. $$ Since$\color{red}{^*}$ $$\tag{3} |(I-A^{-1}E)^{-1}|\leq(I-\epsilon|A^{-1}|\,|A|)^{-1}, $$ we have from (2) that $$\tag{4} |x-y|\leq\epsilon\,|A^{-1}|\,|A|(I-\epsilon|A^{-1}|\,|A|)^{-1}|x|=:G|x|. $$ The result follows from the "special" form of $G$; substituting $\epsilon=10^{-8}$, we have $$ G=\pmatrix{10^{-8}&10^{-18}&10^{-18}\\50&10^{-8}&10^{-8}\\50&10^{-8}&10^{-8}}. $$ Plugging this to (4), $$ \begin{split} (|x-y|)_1&\leq 3\cdot 10^{-18}=3\cdot 10^{-8}(|x|)_1\leq 10^{-7}(|x|)_1, \\ (|x-y|)_2&\leq 2.5\cdot 10^{-8}\leq 10^{-7}(|x|)_2, \\ (|x-y|)_3&\leq 2.5\cdot 10^{-8}\leq 10^{-7}(|x|)_3, \end{split} $$ which altogether gives $|x-y|\leq 10^{-7}|x|$.
$\color{red}{^*}$From $$(I-A^{-1}E)^{-1}=I+A^{-1}E(I-A^{-1}E)^{-1},$$ we have $$|(I-A^{-1}E)^{-1}|\leq I+|A^{-1}|\,|E|\,|(I-A^{-1}E)^{-1}| \leq I+\epsilon|A^{-1}|\,|A|\,|(I-A^{-1}E)^{-1}|,$$ and hence $$ (I-\epsilon |A^{-1}||A|)|(I-A^{-1}E)^{-1}|\leq I, $$ which implies (3).