Skip to main content

Subsection 6.1.1 Whose problem is it anyway?

Ponder This 6.1.1.1.

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

Solution

  • If

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

    is small, then we cannot necessarily conclude that

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

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

  • If

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

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

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

    where

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

    is small.

So, \(\| b - A \widehat x \|/\| b \| \) being small is a necessary condition, but not a sufficient condition. If \(\| b - A \widehat x \|/\| b \| \) is small, then \(\widehat 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.

Homework 6.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 \(\widehat x \text{,}\) and somehow you determine that

\begin{equation*} \| x - \widehat 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: \(\| \widehat x - x \| \) is large but the relative error \(\| \widehat x - x \| / \| x \| \) is small.

Solution

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

login