# solving linear equations whose matix is strictly diagonally dominant and element values decrease rapidly as they locate far from the pivots

For a certain problem I am modeling, I have a set of linear equations whose matrix $M$ is symmetric and strictly diagonally dominant ($M_{ii}=1$, for all $i$). In addition, for the upper triangular part, the elements $M_{ij}>M_{in}$ for $j<n$ as well as $M_{ij}>M_{mj}$ for $i>m$, which means the values of matrix elements decrease (in fact, rapidly) as they locate far away the pivots. I intend to neglect these elements below certain threshold (for instant $10^{-3}$) and set them to be zero. Numerical results show the accuracy but I need to prove it from equations. Could anybody give me a clue to estimate the error?

-
actually you do not have to neglect them, if the matrix is strictly diagonal dominant, you can apply preconditioner or use iteration method to find the solution, it will converge exponentially if your matrix has a dominant diagonal. – Yimin Feb 20 '13 at 18:07
Thanks Yimin. In fact, I want to do this because the approximated linear equations can get the almost-accurate results and it saves me time to generate the matrix. Hence I want to know what's the criteria to chose the threshold and what's the correspondence error. – Tony Dong Feb 20 '13 at 18:18

For example, if your matrix $A$ is extremely diagonal dominant, then we simply try to see how about the accuracy by only using the matrix $\tilde{A}$.

Say your problem is to solve $Ax = y$, you are going to approximate $x$ by solving $\tilde{A}\tilde{x} = y$ the accuracy is given by $\|A^{-1}y-\tilde{A}^{-1}y\|$.

$\|A^{-1}y-\tilde{A}^{-1}y\|\le \|A^{-1}-\tilde{A}^{-1}\|\|y\|\le\|\tilde{A}^{-1}\|\|A-\tilde{A}\|\|A^{-1}\|\|y\|$

If every elements of the difference matrix $A-\tilde{A}$ are small enough, as you said $\epsilon = 10^{-3}$.Then $\|A-\tilde{A}\|\le C \epsilon$, C is constant dependent on dimension. And $\|A^{-1}\|$ and $\|\tilde{A}^{-1}\|$ are close and bounded by $M$, which is not too large, which means the condition number is not too large.

Then error of $x$ is bounded by $M^2C\epsilon\|y\|$.

For relative error, you may see it this way,

$\dfrac{\|x-\tilde{x}\|}{\|x\|} = \dfrac{\|(I-\tilde{A}^{-1}A)A^{-1}y\|}{\|A^{-1}y\|}\le\|I-\tilde{A}^{-1}A\|\le\|\tilde{A}^{-1}\|\|\tilde{A}-A\|$

-
Thanks @Yimin. I got your deduction and I think it works for the absolute error. How about the relative error? I don't think it is convinced to take the maximum relative error to be $MC\epsilon$ – Tony Dong Feb 20 '13 at 19:23
I have added some notes on relative error. – Yimin Feb 20 '13 at 20:30
Thanks @Yimin. That's good, now we can say the maximum relative error is $MC\epsilon$. – Tony Dong Feb 20 '13 at 20:59