I'm studying the basic theory of fixed-point iteration. The proof of convergence involves the theory of contractive mapping:
$$|f(t,y2) − f(t,y1)| ≤ K |y2 −y1|$$
I'm wondering how can I specify the Lipschitz constant $K$, if there exist the value $K$, can I get the range of it?
In my application, function $f$ is a matrix. I have the iteration
$$x = Tx$$
$T$ is a matrix. I know that if $T$ is a Markov Transition matrix, it must converge. What if $T$ is a normal matrix? How can I get the Lipschitz constant of it?
The Lipschitz constant of the linear transformation $y=Tx$ is the induced matrix norm $$\|T\| = \sup_{x\ne 0}\frac{\|Tx\|}{\|x\|}$$ Indeed, $\|Tx-Ty\| = \|T(x-y)\| \le \|T\|\|x-y\|$ by construction.
The value of $\|T\|$ depends on the vector norm used above. For the Euclidean norm $\|x\|_2 = \sqrt{\sum |x_i|^2}$ it is equal to the largest singular value of $T$, which is also $\max \sqrt{|\lambda_j|}$ where $\lambda_j$ are the eigenvalues of $T^*T$. This is hard to compute explicitly; one has to use numerics.
But for the $1$-norm the induced matrix norm is easy to compute: sum the absolute values of the entries in each column, and take the maximum of these sums. For the $\infty$-norm, the same but for rows instead of columns.