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

Question

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?

Answer 1

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