1
$\begingroup$

Consider $X$ and $Y$, two invertible matrices which are nearly the inverse of each other.

Feel free to ascribe any meaning to that... maybe $||X Y - I||_2 < \epsilon$ or maybe $||X^{-1} - Y||_2 < \epsilon$, if it makes a difference.

Consider the iterative scheme $$ \begin{align} X_0 &=& X \\\\ Y_0 &=& Y \\\\ X_{i+1} &=& (3 I - X_i Y_i) X_i / 2 \\\\ Y_{i+1} &=& (3 I - Y_i X_i) Y_i / 2 \end{align} $$

I'm under the impression that in the limit $X_n Y_n \rightarrow I$. My intuition for the following is that it's accurate to the first order with scalars, and that if $X$ and $Y$ are near inverse, they nearly commute so the intuition from scalar carries over, and it looks a lot like a Newton iteration, but this is handwavy to say the least.

  • Does it work, or under which conditions does it work? Is there a proof?
  • Is there a better scheme?

This shows up in a differential equation for matrices where it's useful to update both the matrix and its inverse without having to recompute the inverse, whilst avoiding those two variables to drift too far from being the inverse of each other.

$\endgroup$

1 Answer 1

4
$\begingroup$

Note that $$ X_{i+1} Y_{i+1} = (9 X_i Y_i - 6 (X_i Y_i)^2 + (X_i Y_i)^3)/4$$ so $$ X_{i+1} Y_{i+1} - I = \frac{(X_i Y_i - 4 I)(X_i Y_i - I)^2}{4} $$ and for any submultiplicative matrix norm $$ \|X_{i+1} Y_{i+1} - I \| \le \frac{(3 + \|X_i Y_i - I\|) \|X_i Y_i - I\|^2}{4} $$ Thus if $\|X_i Y_i - I\|$ is in the basin of attraction of the fixed point $0$ of the function $f(t) = (3+t) t^2/4$ on $\mathbb R$, $\|X_i Y_i - I\| \to 0$ as $i \to \infty$.

The fixed points of $f$ are $-4$, $0$ and $1$, and there are no real $2$-cycles; the basin of attraction is the interval $(-4,1)$. Thus $\|X_i Y_i - I\| \to 0$ if $\|X_0 Y_0 - I\| < 1$.

$\endgroup$
4
  • $\begingroup$ Ah clever. Do you see a way to make it globally convergent? The trick I suppose is once a good rational function is found, to turn it into an update scheme for X and Y so that the product remains a rational function of the product. $\endgroup$
    – Arthur B.
    May 16 at 7:05
  • $\begingroup$ Still limited convergence radius, but this is a good recipe for getting higher order convergent stuff, e.g. $X \leftarrow (15 X -10 X Y X + 3 (X Y)^2 X)/8$ $\endgroup$
    – Arthur B.
    May 16 at 11:23
  • $\begingroup$ (Though that has a worse convergence radius and takes twice as many multiplications without converging twice as fast.) $\endgroup$
    – Arthur B.
    May 16 at 11:39
  • $\begingroup$ I don't think you need to invoke the submultiplicative norm by the way... you can assume $X Y$ is diagonalisable walog because of density, and then just look at the effect of $f(t) = (9t - 6t^2 + t^3)/4$ on the eigenvalues of $X_i Y_i$, which remain all diagonalisable in the same basis $\endgroup$
    – Arthur B.
    May 16 at 15:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .