3
$\begingroup$

Consider the system of linear equations (A+D)x=b, where D is a positive semidefinite diagonal matrix. In my particular case of interest, D has the form D = blkdiag(0,M) for some positive diagonal matrix M. So, a subset of the diagonal entries of A are being perturbed.

Are there any off-the-shelf theorems that characterize how the components of the solution x change as the elements of D change? Assuming you don't lose full rank, intuitively as M increases in size, the bottom elements of x should shrink. Coupling through A should then also shrink the top elements a little bit.

Thanks -John

  • 0
    It's full rank and indefinite, so for arbitrary D as I've written it, the matrix A+D is potentially singular. But let's say we restrict our attention to sufficiently small or large D such that this isn't a problem.2012-11-06

1 Answers 1

2

Depends on the bookshelf of whom ;-D

On my bookshelf, there is a copy of Stewart and Sun, Matrix Perturbation Theory, Academic Press Inc., San Diego, 1990. By Theorem 2.11 (p.124), if your $D$ is small enough and $Ax=(A+D)\hat{x}=b$, then the relative difference between $\hat{x}$ and $x$ is bounded as follows: $ \frac{\|\hat{x}-x\|}{\|x\|}\le\frac{\kappa(A)\frac{\|D\|}{\|A\|}}{1-\kappa(A)\frac{\|D\|}{\|A\|}}, $ where $\kappa(A)$ is the condition number of $A$.

The above theorem deals with the overall relative or absolute change in $x$ rather than the change in any particular entry of $x$, so I am not sure if it suits your needs or not. At any rate, your intuition that the bottom elements of $x$ might shrink is wrong. For instance, consider the simple case where $A=\begin{pmatrix}1\\&-1\end{pmatrix},\ b=\begin{pmatrix}1\\-1\end{pmatrix},\ x=\begin{pmatrix}1\\1\end{pmatrix}$ and $D=\begin{pmatrix}0\\&\epsilon\end{pmatrix}$ with $\epsilon>0$. The solution to $(A+D)\hat{x}=b$, or equivalently, $\begin{pmatrix}1\\&-1+\epsilon\end{pmatrix}\hat{x} = \begin{pmatrix}1\\-1\end{pmatrix}$, is given by $\hat{x}=\begin{pmatrix}1\\ \frac{1}{1-\epsilon}\end{pmatrix}$. When $\epsilon$ increases, the bottom element of $x$ becomes larger, while the top element remains unchanged.