This page is intended to be a part of the Numerical Analysis section of Math Online. Similar topics can also be found in the Linear Algebra section of the site.

Error in Solutions to Systems of Linear Equations

Recall that if we had a system of $n$ linear equations in $n$ unknowns represented in matrices as $Ax = b$, and provided that a solution exists, then we could obtain such a solution by either applying Gaussian Elimination to get $A$ into an upper triangular matrix $U$ and apply backwards substitution, or provided pivoting wasn't an issue, we could factor $A$ into two triangular matrices $L$ (which is lower triangular) and $U$ (which is upper triangular), and solve the simpler systems $Lg = b$ by forward substitution and then $Ux = g$ by backwards substitution to obtain the solution $x$. In either manner, if we have a computer doing the work, we will generally be applying many additions and multiplications, etc… and the computer's solution will likely vary due to the accumulation of various errors that can arise in the process.

Consider the system of equations $Ax = b$ again, where $A$ is an $n \times n$ matrix, and assume that a unique solution $x$ exists. Let $\hat{x}$ denote the solution obtained by a computer. Furthermore, let $r = b - A\hat{x}$. This value tells us the error between the value of $b$ and the value of $A \hat{x}$ ($A$ times our approximate solution) and has an important name which we define below.

Definition: If an $n \times n$ system of linear equations $Ax = b$ has a unique solution $x$ and if $\hat{x}$ is a computer solution, then the Residual $r$ is the difference between $b$ and the matrix $A$ multiplied by our computed solution $\hat{x}$, that is $r = b - A\hat{x}$. The Error in $\hat{x}$ is $e = x - \hat{x}$.

It should be noted that both the residual $r$ and error of in $\hat{x}$ are matrices. Also note that if $x = \hat{x}$, that is, our computed solution is exact, then $\hat{x}$ has no error and further more, the residual $r = b - A \hat{x} = b - Ax = 0$.

One way we can perceive the residual and error in $\hat{x}$ is as follows:

(1)

\begin{align} \quad r = b - A \hat{x} \\ \quad r = Ax - A\hat{x} \\ \quad r = A(x - \hat{x}) \\ \quad r = Ae \end{align}

Thus we can see that $Ae = r$ and so the error in $\hat{x}$ is the solution to the linear system with $b$ replaced with $r$, that is with the $n \times 1$ matrix $b$ being replaced with the residual $r$. Thus, in finding the error $e$, all we need to do is solve the system $Ae = r$, which should not be too much of a hassle if we used an $LU$ decomposition for $A$ since we can use that same $LU$ decomposition in solving $Ae = r$.

Unfortunately, some problems may arise when trying to determine the error between the computed solution $\hat{x}$ and the actual solution $x$. If the program implemented is very good, then the entries of the residual will be very close to zero, that is, for $j = 1, 2, ..., n$:

(2)

\begin{align} \quad r_j = b_j - \sum_{j=1}^{n} a_{ij} \hat{x_j} \approx 0 \end{align}

We've seen earlier that this could lead to loss of significance errors when working with the residual $r$.

Another issue that can arise is in solving the system $Ae = r$. Note that $e$ represents the error between $\hat{x}$ and $x$ in solving the system $Ax = b$. Thus solving $Ae = r$ will produce similar errors to that of when we originally solved $Ax = b$, and so we will only obtain an approximation $\hat{e}$ or our error $e$.