1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Since we assume that $|\Delta A| \leq \epsilon E$ why can't I assume that $E$ contains only $1$'s ? $\endgroup$ – vkonton Jul 26 '17 at 16:23
  • $\begingroup$ Why should you? You are looking for the matrix $E$ that produces the worst case error. At least for me it is not clear that the matrix of all ones produces the worst case error. $\endgroup$ – H. Rittich Jul 27 '17 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.