Sensitivity Analysis In this problem, we consider a real, non-singular \(n\times n\) matrix \(A\) and vectors \(b,x\in \mathbb {R}^n\). We are concerned with the error in solving the linear system \(Ax=b\). It turns out that the numerical solution \(\hat {x}\) is only an approximate solution to this equation. However, it satisfies a perturbed equation \(\hat {A}\hat {x}=b\) exactly, where \(\hat {A}=A+\delta A\). Let the error be defined as \(\delta x=\hat {x}-x\); we are interested in bounding \(\lVert \delta x\rVert \) in terms of \(\lVert \delta A\rVert \lVert A^{-1}\rVert \), or \(\lVert \delta A\rVert \lVert \hat {A}^{-1}\rVert \), and \(\lVert x\rVert \), or \(\lVert \hat {x}\rVert \), where \(\lVert \cdot \rVert \) is some suitable norm, and we proceed as follows:
a) First prove the identity \[ A^{-1}-\hat {A}^{-1}=A^{-1}\cdot \delta A\cdot \hat {A}^{-1}, \] and hence deduce that \[ \lVert A^{-1}-\hat {A}^{-1}\rVert \le \lVert A^{-1}\rVert \cdot \lVert \delta A\rVert \cdot \lVert \hat {A}^{-1}\rVert . \]
b) Assuming that \(\hat {\delta }=\lVert \delta A\rVert \lVert \hat {A}^{-1}\rVert <1\), show that \[ \lVert A^{-1}\rVert \le \frac {1}{1-\hat {\delta }}\lVert \hat {A}^{-1}\rVert ,\qquad \lVert A^{-1}-\hat {A}^{-1}\rVert \le \frac {\hat {\delta }}{1-\hat {\delta }}\lVert \hat {A}^{-1}\rVert . \]
c) By comparing the equations \(Ax=b\) and \((A+\delta A)(x+\delta x)=b\), show that \[ \lVert \delta x\rVert \le \frac {\hat {\delta }}{1-\hat {\delta }}\lVert \hat {x}\rVert . \] Similarly, show that if \(\delta =\lVert \delta A\rVert \lVert A^{-1}\rVert <1\), \[ \lVert \delta x\rVert \le \frac {\delta }{1-\delta }\lVert x\rVert . \]