Relative error in solution when the matrix is perturbed Suppose that $A \in \mathbb{R}^{n \times n}$ is an invertible matrix and that $Ax=b$ for some $x,b \in \mathbb{R}^{n}$. If $\kappa(A)$ denotes the condition number of $A$, it is well known that if $b$ is perturbed by $\Delta b$, then $x$ gets perturbed by $\Delta x$ which satisfies
$$
\frac{\|\Delta x \|}{\|x\|} \leq \kappa(A) \frac{\|\Delta b\|}{\|b\|}.
$$
If in addition $A$ is also perturbed to $A+\Delta A$, which is invertible, I am wondering if it is possible to say something along the similar lines such as
$$
\frac{\|\Delta x \|}{\|x\|} \leq \kappa(A) \left( \frac{\|\Delta A\|}{\|A\|}+ \frac{\|\Delta b\|}{\|b\|} \right).
$$
In other words, by changing both $A,b$ to $A+\Delta A, b+\Delta b$, how do we control the change is the solution $x$ to $x+\Delta x$?

Yes, something like that is true. You can find the proof, e.g., in this book and can go around these lines.
We have $Ax=b$ and $(A+\Delta A)(x+\Delta x)=b+\Delta b$. This gives
$(A+\Delta A)\Delta x=\Delta b-\Delta Ax$.
If $A+\Delta A$ is invertible, we have $\Delta x=(A+\Delta A)^{-1}(\Delta b-\Delta Ax)$. Taking a norm and using $\|b\|=\|Ax\|\leq\|A\|\|x\|$ gives
$$
\frac{\|\Delta x\|}{\|x\|}
\leq
\|(A+\Delta A)^{-1}\|\|A\|\left(\frac{\|\Delta b\|}{\|b\|}+\frac{\|\Delta A\|}{\|A\|}\right).
\tag{$\star$}
$$
It remains to bound the norm of the inverse of $A+\Delta A$.
From $I=(A+\Delta A)^{-1}(A+\Delta A)$ we have $(A+\Delta A)^{-1}=A^{-1}-(A+\Delta A)^{-1}\Delta A A^{-1}.$
Taking the norm gives
$$
\|(A+\Delta A)^{-1}\|\leq \|A^{-1}\| + \|(A+\Delta A)^{-1}\|\|\Delta AA^{-1}\|.
$$
so if $\|\Delta AA^{-1}\|<1$
then
$$
\|(A+\Delta A)^{-1}\|\leq\frac{\|A^{-1}\|}{1-\|\Delta AA^{-1}\|}.
$$
Substituting to ($\star$) gives that 

If ($\ast$) holds, then 
  $$ 
\frac{\|\Delta x\|}{\|x\|} \leq
\frac{\kappa(A)}{1-\|\Delta AA^{-1}\|}\left(\frac{\|\Delta b\|}{\|b\|}+\frac{\|\Delta A\|}{\|A\|}\right). 
$$

From $\|\Delta AA^{-1}\|\leq\|\Delta A\|\|A^{-1}\|$ you can get a bit more "neat" statement.

If 
  $$
\frac{\|\Delta A\|}{\|A\|}<\frac{1}{\kappa(A)}
$$
  then
  $$ 
\frac{\|\Delta x\|}{\|x\|} \leq
\frac{\kappa(A)}{1-\frac{\|\Delta A\|}{\|A\|}\kappa(A)}\left(\frac{\|\Delta b\|}{\|b\|}+\frac{\|\Delta A\|}{\|A\|}\right)
$$
  and if $\|\Delta A\|\leq\epsilon\|A\|$ and $\|\Delta b\|\leq\epsilon\|b\|$ then
  $$
\frac{\|\Delta x\|}{\|x\|} \leq
\frac{2\epsilon\kappa(A)}{1-\epsilon\kappa(A)}.
$$

You can of course remove the "annoying" denominator using a stronger assumption. For example, if $\epsilon\kappa(A)<1/2$, then
$$
\frac{\|\Delta x\|}{\|x\|} \leq
4\epsilon\kappa(A).
$$
