Solving Linear System with Noisy Input

Question

I have the following triangular system \begin{equation} \begin{pmatrix} 1 & & & & \\ \mu_1 & 2 & & & \\ \mu_2 & \mu_1 & 3 & \\ \vdots & \vdots &\ddots & \ddots & \\ \mu_{n-1} & \mu_{n-2} & \dots & \mu_1 & n \end{pmatrix} \begin{pmatrix} c_{n-1} \\ c_{n-2} \\ c_{n-3} \\ \vdots \\ c_0 \end{pmatrix} = \begin{pmatrix} - \mu_{1} \\ - \mu_{2} \\ - \mu_{3} \\ \vdots \\ - \mu_n \end{pmatrix} \Leftrightarrow A c = b \end{equation} For all the values $\mu_j$ I have approximations $\hat{\mu}_j$ such that $|\mu_j - \hat{\mu_j}| \leq \epsilon$. I want to compute an upper bound for the error in the solution of this system, that is a bound on $\| c - \hat{c}\|_{\infty}$.

Let's assume that we use forward substitution to solve this system.

Is it true that, assuming that all the operations are done with infinite precision, would give a solution $\hat{c}$ such that $\|c -\hat{c}\|$ would be upper bounded by the forward error of $c$ ?

To bound the forward error of the solution I found the following theorem in this book.

Let $Ax = b$ and $(A + \Delta A) y = b + \Delta b$, where $|\Delta A| \leq \epsilon E$ and $|\Delta b| \leq \epsilon f$, and assume that $\epsilon \| |A^{-1}| E \| < 1$, where $\|\cdot\|$ is an absolute norm. Then \begin{equation} \frac {\|x-y\|}{\|x\|} \leq \frac \epsilon {1 - \epsilon \| |A^{-1}| E\|} \frac {\| |A^{-1}|(E|x| + f)\|} {\|x\|} \end{equation}
and for the $\infty$-norm this bound is attainable to first order in $\epsilon$.

Since I am not sure that I have fully understood the backward-forward error concept, I am not sure whether using the above theorem with \begin{equation} E = \begin{pmatrix} 0 & & & & \\ 1 & 0 & & & \\ 1 & 1 & 0 & \\ \vdots & \vdots &\ddots & \ddots & \\ 1 & 1 & \dots & 1 & 0 \end{pmatrix},\qquad f = \begin{pmatrix} 1 \\ 1 \\ 1 \\ \vdots \\ 1 \end{pmatrix} \end{equation} will give me an upper bound for the error in my noisy system.

Answer 1

You are right. You need the forward error to answer your question. The term $\| x - y \|$ in the inequality from your book corresponds to $\| c - \hat{c} \|$ in your example. Hence, to bound $\| x - y \|$ you first multiply the inequality by $\| x \|$ to get

\begin{equation} \|x-y\| \leq \frac{\epsilon}{1 - \epsilon \| |A^{-1}| E\|} \| |A^{-1}|(E|x| + f)\| \,. \end{equation}

Then, to bound the infinity norm, you can use the inequality $\| v \|_\infty \le \| v \|_2$. Assuming the inequality from the book uses the $\ell_2$-norm, we have that \begin{equation} \|x-y\|_\infty \leq \frac{\epsilon}{1 - \epsilon \| |A^{-1}| E\|} \| |A^{-1}|(E|x| + f)\| \,. \end{equation}

This statement requires, as you mentioned, that all operations are carried out using exact arithmetic.

The problem is, that you cannot assume that the entires of $E$ and $f$ are all one. You have to assume that \begin{equation} E = \begin{pmatrix} 0 & & & & \\ * & 0 & & & \\ * & * & 0 & \\ \vdots & \vdots &\ddots & \ddots & \\ * & * & \dots & * & 0 \end{pmatrix},\qquad f = \begin{pmatrix} * \\ * \\ * \\ \vdots \\ * \end{pmatrix} \end{equation} where the stars mark arbitrary numbers with absolute value smaller or equal to one. Using the submultiplicativity of the matrix norm, i.e., $\| A B\| \le \| A \| \| B \|$, however, you can factor out the $\| E \|$. Then, your answer does just depend on $\| E \|$ and $\epsilon$.