Skip to main content
2 of 2
added 1 character in body
vkonton
  • 175
  • 6

Solving Linear System with Noisy Input

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][1] 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. [1]: http://epubs.siam.org/doi/book/10.1137/1.9780898718027

vkonton
  • 175
  • 6