Iterative Improvement For System of Linear Equations Consider the system of linear equations $Ax = b$ where $A$ is an n x n matrix and $x$ and $b$ are n x 1 column vectors.
Let $\bar x$ be an approximate solution to the system.  
The relative error in the solution is $\frac{||x-\bar x||}{||x||}$  
The relative error in the residual is $\frac{||b-A\bar x||}{||b||}$
Let $k(A)$ be the condition number of A.   
Then the bound on the relative error in the solution is given by:   
$\quad \frac{||x-\bar x||}{||x||} \le k(A) \frac{||b-A\bar x||}{||b|| }$
I understand that from the equation that a small relative error in the residual does not necessarily mean that the relative error in the solution will be small since $k(A)$ may be large.
I'm using Gaussian Elimination with pivoting and iterative improvement to try to improve the initial solution.
In my computation, I'm seeing an iteration reduce the relative error in the residual but I'm seeing an increase in the relative error in the solution.
If an iteration decreases the relative error in the residual does it necessarily mean that we should expect a decrease in the relative error in the solution?  
 A: Briefly, the answer is no.
Let $A = U\Sigma V^T$ denote the singular value decomposition and let $x = \sum_{j=1} r_j v_j$ denote the solution of the linear system $$Ax = b,$$ expressed as a linear combination of the (right) singular vectors of $A$. Let $$\bar{x} = \sum_{j=1} s_j v_j$$ denote an approximation of $x$. Then the error is $$e = x - \bar{x} = \sum_{j=1}^n (r_j - s_j) v_j$$ and the normwise relative error is $$\frac{\|e\|_2}{\|x\|_2} = \frac{\sqrt{\sum_{j=1}^n (r_j - s_j)^2}}{\sqrt{\sum_{j=1}^n r_j^2}}.$$ The residual is
$$ b - A \bar{x} = A (x - \bar{x}) = \sum_{j=1} \sigma_j (r_j-s_j) u_j,$$ and the normwise relative residual is
$$ \frac{\|b-A\bar{x}\|_2}{\|b\|_2} = \frac{\sqrt{\sum_{j=1}^n \sigma_j^2 (r_j-s_j)^2} }{\sqrt{\sum_{j=1}^n \sigma_j^2 r_j^2}}.$$
The difference between these two expressions for the normwise relative error and the normwise relative error gives us all the wiggle room that we need. To be extremely clear, let us consider the case where $$r_j = s_j = 0, \quad j = 2,3,\dotsc,n-1,$$
i.e. the only thing that matters is the largest and the smallest singular value. Then $$\frac{\|e\|_2^2}{\|x\|_2^2} = \frac{(r_1-s_1)^2+(r_n-s_n)^2}{r_1^2+r_n^2},$$
while
$$\frac{\|b-Ax\|_2^2}{\|b\|_2^2}= \frac{\sigma_1^2(r_1-s_1)^2+\sigma_n^2(r_n-s_n)^2}{\sigma_1^2r_1^2+\sigma_n^2r_n^2}.$$
Now suppose futher that $r_n = 0$ and $\sigma_1 = 1$. Then
$$\frac{\|e\|_2^2}{\|x\|_2^2} = \frac{(r_1-s_1)^2+s_n^2}{r_1^2},$$
while
$$\frac{\|b-Ax\|_2^2}{\|b\|_2^2}= \frac{(r_1-s_1)^2+\sigma_n^2 s_n^2}{r_1^2}.$$
If $\sigma_n$ is huge, then it is clear that you can experience a significant reduction in the normwise relative residual, while increasing the normwise relative error. Simply reduce $s_n$ while move $s_1$ away from $r_1$.
I am confident that the application of the SVD to your specific test matrices is the key to under-standing what happened. 
