Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Do we know anything about the matrix A? –  Manos Nov 6 '12 at 21:26
    
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. –  John Nov 6 '12 at 21:50

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.