## Unit6.1.1Whose problem is it anyway?

###### Ponder This6.1.1.1.

What if we solve $A x = b$ on a computer and the result is an approximate solution $\hat x$ due to roundoff error that is incurred. If we don't know $x \text{,}$ how do we check that $\hat x$ approximates $x$ with a small relative error? Should we check the residual $b - A \hat x \text{?}$

Solution
• If

\begin{equation*} \frac{\| b - A \hat x \|}{\| b \|} \end{equation*}

is small, then we cannot necessarily conclude that

\begin{equation*} \frac{\| \hat x - x \| }{\| x \|} \end{equation*}

is small (in other words: that $\hat x$ is relatively close to $x$).

• If

\begin{equation*} \frac{\| b - A \hat x \|}{\| b \|} \end{equation*}

is small, then we can conclude that $\hat x$ solves a nearby problem, provided we trust whatever routine computes $A \hat x \text{.}$ After all, it solves

\begin{equation*} A \hat x = \hat b \end{equation*}

where

\begin{equation*} \frac{\| b - \hat b \|}{\| b \|} \end{equation*}

is small.

So, $\| b - A \hat x \|/\| b \|$ being small is a necessary condition, but not a sufficient condition. If $\| b - A \hat x \|/\| b \|$ is small, then $\hat x$ is as good an answer as the problem warrants, since a small error in the right-hand side is to be expected either because data inherently has error in it or because in storing the right-hand side the input was inherently rounded.

In the presence of roundoff error, it is hard to determine whether an implementation is correct. Let's examine a few scenerios.

###### Homework6.1.1.2.

You use some linear system solver and it gives the wrong answer. In other words, you solve $A x = b$ on a computer, computing $\hat x \text{,}$ and somehow you determine that

\begin{equation*} \| x - \hat x \| \end{equation*}

is large. Which of the following is a possible cause (identify all):

• There is a bug in the code. In other words, the algorithm that is used is sound (gives the right answer in exact arithmetic) but its implementation has an error in it.

• The linear system is ill-conditioned. A small relative error in the right-hand side can amplify into a large relative error in the solution.

• The algorithm you used accumulates a significant roundoff error.

• All is well: $\| \hat x - x \|$ is large but the relative error $\| \hat x - x \| / \| x \|$ is small.

Solution

All are possible causes. This week, we will delve into this.