6

Consider the fixed-point iteration process in $\mathbb{R}^n$.

Given a sufficiently smooth function $f:\mathbb{R}^n\to\mathbb{R}^n$ and an initial value $x_0\in\mathbb{R}^n$, define the iteration sequence $x_{k+1}=f(x_k)$. Suppose that $$\lim_{k\to\infty}x_k=x^*,$$ then apparently $x^*$ is a fixed point of $f(x)$. I'm familiar with the case in $\mathbb{R}^1$ where the sequence is (generally) linearly convergent with rate $$\lim_{k\to\infty}\frac{|x_{k+1}-x^*|}{|x_k-x^*|}=|f'(x^*)|<1.$$ And I thought the analogy of this constant $|f'(x^*)|$ in $\mathbb{R}^n$ case would be $\|J_f(x^*)\|$, where $J_f(x^*)$ denotes the Jacobian matrix $(\partial f_i(x^*)/\partial x_j)_{n\times n}$ and $\|\cdot\|$ the operator norm induced by vector norm.

But the results of my numerical experiments proved me wrong, and I found the following claim on some website: $$\lim_{k\to\infty}\frac{\|x_{k+1}-x^*\|}{\|x_k-x^*\|}=\rho(J_f(x^*))<1,$$ where $\rho$ the spectral radius of a matrix. Indeed the claim fits well my experiment results.

It does surprise me that the rate of convergence is independent of the vector norm, but I could not find a proper proof either by myself or by online materials.

Any help or link on its proof would be appreciated.

Niwatori
  • 61
  • +1 I asked something similar not too long ago--the only response I received was a comment saying "you want the Mean Value Inequality to hold in order to infer that a contraction mapping has a fixed point. It seems to me that you need to know that $|Tv|\leq |T||v|$ The operator norm or Euclidean (Hilbert-Schmidt) norm will work." I am guessing by $T$ they meant the Jacobian of the given mapping: https://math.stackexchange.com/questions/4728816/multivariate-analog-of-condition-for-fixed-points – Nap D. Lover Sep 24 '23 at 20:22

1 Answers1

1

As in many similar situations in higher dimensional spaces, it helps to look at the simplest case where the function can be decoupled. That is, the function requires no interaction between the variables. For two dimensions this is $f(x,y) =(f_1(x),f_2(y))$. For even more simplicity, assume $f(x,y) = (ax,by)$. Now the rate of convergence is obviously dominated by $\max(|a|,|b|)$ which corresponds to the spectral radius.

Somos
  • 35,251
  • 3
  • 30
  • 76