3
$\begingroup$

If $A$ has eigenvalue $\lambda_A$ $$B = I - c\frac{I-rA}{I-\bar{r}A}$$

How to derive the eigenvalue $\lambda_B$? $$\lambda_B=1-c\frac{1-r\lambda_A}{1-\bar{r}\lambda_A}$$

where $c, r, \bar{r}$ are constants.

This formula occurs at the derivation of speedup modified Newton iteration in solving DAE. There are no details in the paper for the derivation of this linear algebra piece.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Is this a homework problem? If so, you should indicate that in your post. What have you tried so far to show this relationship? $\endgroup$ – Bill Greene Oct 10 '18 at 10:34
  • $\begingroup$ no it's not homework, it's the spectral radius of iterative function in solving ODE, c is use to speed up the newton iteration, I just want to know how to derive it $\endgroup$ – Chen Ziv Oct 10 '18 at 10:34
  • $\begingroup$ Have a look at Higham's Functions of Matrices (my.siam.org/books/ot104/OT104HighamChapter1.pdf), there are several ways to properly define functions of matrices like your $B=B(A)$, and when $B$ is an analytic function as here, the eigenvalues will be $B(\lambda)$. The easiest way to do this without functions of matrices I think is to diagonalize $A=XDX^{-1}$ and expand everything, you get $X(I-c(1-r D)(1-\bar r D)^{-1})X^{-1}$, where the eigenvalues can be computed easily. $\endgroup$ – Kirill Oct 10 '18 at 21:33
  • 1
    $\begingroup$ @WolfgangBangerth Can you clarify what you mean? The matrices $I-r A$ and $(I-\tilde r A)^{-1}$ commute, as far as I can tell. $\endgroup$ – Kirill Oct 11 '18 at 8:42
  • 1
    $\begingroup$ Even if they commute it's rather bad style to write matrix-over-matrix. $\endgroup$ – Wolfgang Bangerth Oct 11 '18 at 22:09
5
$\begingroup$

It's just some easy matrix algebra. If $Av=\lambda_A v$ then $(I-rA)v= (1-r\lambda_A)v$ and (multiplying by inverses on both sides) $(I-rA)^{-1}v= (1-r\lambda_A)^{-1}v$, which is valid also if you replace $r$ with $\bar{r}$.

Then you just expand $Bv = (I-c(I-rA)(I-\bar{r}A)^{-1})v=\dots$

[EDIT: wim's answer carries out this computation in more detail.]

Improve this answer
$\endgroup$
4
$\begingroup$

Let $(\lambda,x)$ be an eigenpair of matrix $A$, so $A x=\lambda x$. Now we compute $B x$, and see if it is equal to $\left(1-c\frac{1-r\lambda}{1-\bar{r}\lambda}\right)x$.

$$ \begin{align} B x & = \left( I - c\frac{I-rA}{I-\bar{r}A} \right) x\\ & = x - c\frac{x-rAx}{I-\bar{r}A} = x - c\frac{x-r \lambda x}{I-\bar{r}A}\\ & = x - c\frac{1-r \lambda }{I-\bar{r}A}x\\ & = x - c\frac{1-r \lambda }{I-\bar{r}A} \, \frac{I-\bar{r}\lambda}{I-\bar{r}\lambda}x\\ & = x - c\frac{1-r \lambda }{I-\bar{r}A} \, \frac{x-\bar{r}Ax}{I-\bar{r}\lambda}\\ & = x - c\frac{1-r \lambda }{I-\bar{r}A} \, \frac{I-\bar{r}A}{I-\bar{r}\lambda}x\\ & = \left( 1 - c\frac{1-r \lambda }{I-\bar{r}\lambda}\right)x\\ \end{align} $$

Hence, we may conclude that following relationship between the eigenvalues of $A$ and $B$ holds: $$\lambda_B = 1 - c\frac{1-r \lambda_A }{I-\bar{r}\lambda_A} ,$$

as long as $I-\bar{r}A$ is invertible. Note that it is not necessary that $A$ is diagonalizable.

In the comments there has been some discussion whether or not $(I-\alpha A)^{-1}$ commutes with $I-\beta A$. If we assume that $I-\alpha A$ is invertible, then

$$ \begin{align} (I-\alpha A)^{-1}(I-\beta A) & = (I-\alpha A)^{-1}(I-\beta A)(I-\alpha A)(I-\alpha A)^{-1}\\ & = (I-\alpha A)^{-1}(I-\beta A -\alpha A +\alpha \beta A^2)(I-\alpha A)^{-1}\\ & = (I-\alpha A)^{-1}(I-\alpha A)(I-\beta A)(I-\alpha A)^{-1}\\ & = (I-\beta A)(I-\alpha A)^{-1} ,\\ \end{align} $$ which shows that indeed $(I-\alpha A)^{-1}$ commutes with $I-\beta A$. Therefore we can write $\frac{I-\beta A}{I-\alpha A}$ instead of $(I-\alpha A)^{-1}(I-\beta A)$ or $(I-\beta A)(I-\alpha A)^{-1}$.

Improve this answer
$\endgroup$
2
$\begingroup$

From a quick look at your problem, it seems to me that this should follow by writing $(I - \bar{r} A)^{-1}$ as a geometric series, expanding its product with $I - r A$, and then applying the Spectral Mapping Theorem (which says that if $p$ is a polynomial/power series, then the eigenvalues of $B = p(A)$ are the eigenvalues of $A$ transformed by $p$).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Aren't you assuming that $\|rA\|<1$ to get the power series to converge? $\endgroup$ – Kirill Oct 10 '18 at 21:29
  • $\begingroup$ Yes, of course. Otherwise the expansion does not hold. $\endgroup$ – Juan M. Bello-Rivas Oct 10 '18 at 23:41
  • 1
    $\begingroup$ But the formula is valid in general, so there’s a gap in the proof, isn’t there? $\endgroup$ – Kirill Oct 10 '18 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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