Condition number linear system

Question

Let $b \in \mathbb R^n$ be fixed.

Find the relative condition numbers of the following problem:

Find the solution $x \in \mathbb R^n$ of $Ax=b$ for the invertible matrix $A \in \mathbb R^{n\times n}$.

We defined the relative condition numbers as

$$\kappa_{ij}^{\mathrm{rel}}(x)=\Bigg|\frac{\partial f_i(x)}{\partial x_j}\frac{x_j}{f_i(x)}\Bigg|$$

For example if we look at the addition $y=x_1+x_2$ we have $\kappa_{\mathrm{rel}}(x_1,x_2)=|\frac{x_1}{x_1+x_2}|$ and $|\frac{x_2}{x_1+x_2}|$.

Or for the multiplication $y=x_1x_2$ we have $\kappa_{\mathrm{rel}}(x_1,x_2)=|x_2\frac{x_1}{x_1x_2}|=1$ and $|x_1\frac{x_2}{x_1x_2}|=1$

The hint was to use the implicit function theorem so maybe we need to use implicit differentiation but I don't know

Thanks!

Answer 1

In the case of linear systems, you can get direct estimates on the relative error... Assuming for simplicity that the error comes from an inexact right hand side you can reason as follows:

1. If you are solving $A \tilde x = \tilde b$ instead of $Ax = b$, by algebraic manipulation you show that $$ x -\tilde x = A^{-1}(b -\tilde b). $$

2. Taking norms you conclude that

$$ \|x -\tilde x\| \leq \|A^{-1}\| \|b -\tilde b\| \Rightarrow \frac{\|x -\tilde x\|}{\|x\|}\leq \|A^{-1}\| \frac{\|b -\tilde b\|}{\|x\|} $$

3. Taking the last expression and considering that $$ Ax = b \Rightarrow \|Ax\| = \|b\| \Rightarrow \|A\| \|x\| \ge \|b\| \Rightarrow\|x\| \ge \frac{\|b\|}{\|A\|} $$

you can conclude that $$ \frac{\|x -\tilde x\|}{\|x\|}\leq \|A^{-1}\| \|A\| \frac{\|b -\tilde b\|}{\|b\|}. $$

Answer 2

If you are asking about the sensitivity of the solution of $Ax=b$ with respect to the changes in $b$ (as usual when deriving the condition number of a matrix or, more precisely, the condition number of a system of linear equations), you need to make clear first what, in your definition of $\kappa$, is $f$ and $x$. In this case, $f$ represents solution of $Ax=b$ while $b$ is the variable in $f$.

We set hence $f(b):=A^{-1}b$, so $f_i(b)=e_i^TA^{-1}b$, where $e_i$ is the $i$th column of the identity matrix. Then $$ \frac{\partial f_i(b)}{\partial b_j}=\frac{\partial}{\partial b_j}e_i^TA^{-1}b=e_i^TA^{-1}e_j=(A^{-1})_{ij} $$ and $$ \kappa_{ij}=\left|\frac{(A^{-1})_{ij}b_j}{e_i^TA^{-1}b}\right|. $$ This quantity measures the sensitivity of the $i$th component of the linear system solution $e_i^TA^{-1}b$ with respect to the changes in the $j$th component of the right-hand side vector $b_j$.

From a more global point of view, check out this question and the answer there.