1
$\begingroup$

I m trying to analyse the stability against perturbations for a specific system of linear equations $Ax=b$.

For this, i use the standard condition number $||A||_{\infty}||A^{-1}||_{\infty}$.

Here is an exemple for an instance of my problem :

$A = \begin{pmatrix} 1 & -1 & 0 & 0 \\ -0.5 & 1 & -0.3 & -0.2 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$

$b =\begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \\ \end{pmatrix}$

If $n$ is the size of the square matrix, matrix $A$ is such :

  1. $A(i,i) = 1$ for all $i = 1 \cdots n$ (all on-diagonal elements are equals to 1);
  2. $A(i,j) \in [-1,0]$ for all $i \neq j$ (all off-diagonal elements are negative and are between 0 and -1 inclusively);
  3. $\sum_{j=1,j \neq i}^{n} |A(i,j)| \in \{0,1\}$, for all $i = 1 \cdots n$ (for a given row, all aboslute value of off-diagonal elements must sum up to 0 or 1);
  4. $\exists i | \sum_{j=1,j \neq i}^{n} |A(i,j)| = 1$, in other cases the problem would be trivial.
  5. $\exists i | \sum_{j=1,j \neq i}^{n} |A(i,j)| = 0$,
  6. $b(i) \in \{0,1\} $,
  7. if $b(i) = 1 \Rightarrow \sum_{j=1,j \neq i}^{n} |A(i,j)| = 0 $,
  8. $A$ is non-singular ($A^{-1}$ exist and the system $Ax=b$ admit one solution)

Obviously, my matrices are diagonaly dominant but not strictly which means i could not use the varga bound. My matrices are z-matrix and maybe m-matrix with all the nice properties such that the inverse elements are all positives.

It's easy to see that $||A||_{\infty}=2$, i wanna determine un upper bound for $||A^{-1}||_{\infty}$.

For the exemple given, the inverse matrix is : $A^{-1} = \begin{pmatrix} 2 & 2 & 0.6 & 0.4 \\ 1 & 2 & 0.6 & 0.4 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$

And $||A^{-1}||_{\infty}=5$.

Any help will be very helpfull.

$\endgroup$
6
  • 1
    $\begingroup$ So far your conditions do not prevent $A$ from being degenerate or as close to it as it wants: take (a small perturbation of) $\begin{bmatrix}1&-1&0\\-1&1&0\\0&0&1\end{bmatrix}$. So, can you state exactly what you are looking for? (I mean, one can get some bounds in terms of matrix entries, but that makes sense only if you have large sizes and want to compute your bound way quicker than to just invert the matrix and look at the result). $\endgroup$
    – fedja
    May 22, 2014 at 18:15
  • $\begingroup$ Yes fedja, I want the bound in terms of $n$, the size of $A$ (something like $||A^{-1}||_{\infty} \leq 3n$ because i can have large matrix and calcute the inverse cost much. $\endgroup$ May 22, 2014 at 18:30
  • $\begingroup$ I m pretty sure also that the matrix $A$ is a non-singular matrix.In your exemple, it's not the case. $\endgroup$ May 22, 2014 at 18:37
  • $\begingroup$ --- I m pretty sure also that the matrix A is a non-singular matrix.In your exemple, it's not the case. --- ??? Have you read the text in parentheses in my comment?. $\endgroup$
    – fedja
    May 23, 2014 at 1:41
  • $\begingroup$ yes, that's what i want i mean. one can get some bounds in terms of matrix entries, but that makes sense only if you have large sizes and want to compute your bound way quicker than to just invert the matrix and look at the result $\endgroup$ May 23, 2014 at 13:35

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.