Conditions such that $f(x)= AB^{-1}x$ is a contraction mapping

50 Views Asked by At

Consider the function $y = f(x) = AB^{-1}x$, where $x,y$ are vectors, and $A,B$ are matrices. I wish to show that $f(X)$ is a contraction mapping.

Question: What are the conditions on $A$ and $B$ such that $f(x)$ is a contraction mapping?

Attempt/Ideas: Is it sufficient to show that the spectral radius of $AB^{-1}$ is less than $1$? If we were dealing with scalars $a$ and $b$ instead of matrices then we would just show that $b$ is bigger than $a$. Does the same intuition hold for matrices?

3

There are 3 best solutions below

0
On

No, it doesn't. For instance take $$ A=\begin{bmatrix} 0&2\\ 0&0\end{bmatrix},\ \ \ B=I_2. $$ Then $AB^{-1}=A$ has $\|AB^{-1|\|=2$, while its spectral radius is zero.

I don't think in general you can get conditions on $A$ and $B$, and less they are very strong: for instance if you require $\|A\|<1$ and $\|B^{-1}\|<1$ you will get a contraction, obviously. But you can prescribe both the spectral radius and the norm of $A$ and $B$, and still it is easy to construct an example that will not be a contraction.

0
On

The answer depends upon what you mean by contraction.

If contraction means that there exists a norm $\|.\|$ such that $\|f(x)\|\leq q\|x\|$ for all $x$ with some positive $q<1$, then the answer is that the spectral radius must be smaller than 1. It is well known that for any $\epsilon>0$ there exists a norm $\|.\|$ such that $\|AB^{-1}\|\leq \rho(AB^{-1})+\epsilon$.

If contraction means that for some prescribed vector norm $\|.\|$ you have $\|f(x)\|\leq q\|x\|$ for all $x$ with some positive $q<1$ then the answer is that the correponding matrix norm of $AB^{-1}$ that I also denote by $\|AB^{-1}\|$ must be smaller than 1. This matrix norm is defined by $\|AB^{-1}\|=\max_{\|x\|\leq1}\|AB^{-1}x\|$. The condition on the spectral radius is not sufficient in this case. See here and here for details.

Observe that for every $\epsilon>0$ and every norm $\|.\|$ there exist a $K>0$ such that for all $x$ and all $n$, we have $\|f^n(x)\|=\|f(f(\cdots(f(x)\cdots)\|\leq K(\rho(AB^{-1})+\epsilon)^n \|x\|$. So, the question whether $f^n(x)\to0$ does not depend upon the norm chosen as it must be, because all norms in a finite dimensional vector space are equivalent. The question whether we have a contraction or not does depend upon the norm chosen.

0
On

A sufficient condition for the funtion $$ f: \mathbb{R}^n \rightarrow \mathbb{R}^n, \quad x \mapsto AB^{-1}x,$$ to be a contraction in $(\mathbb{R}^n, \lVert\rVert)$ is given by $$\max_{z \in \mathbb{R}^n, \ \lVert z \rVert = 1} \lVert AB^{-1}z \lVert <1.$$ To see this, realize, that, for all $x,y \in \mathbb{R}^n$ with $x \neq y$, it holds that $$ \lVert f(x) - f(y)\rVert = \lVert AB^{-1}(x-y)\rVert = \lVert AB^{-1} \frac{(x-y)}{\lVert x-y \rVert} \lVert \lVert x-y \rVert \leq \max_{z \in \mathbb{R}^n, \ \lVert z \rVert = 1} \lVert AB^{-1}z \rVert \lVert x-y \rVert. $$