1
$\begingroup$

As we know, the convergence criterion of scalar fixed point iteration, e.g. $x^{k+1}=f(x^k)$, is that $|f^{\prime}(x^*)|<1$.

For the vector variable version, it has been proved in the case when $f$ is an affine function, i.e. $\textbf{x}^{k+1}=f(\textbf{x}^{k})=\textbf{A}\textbf{x}^k+\textbf{b}$, the criterion is that $\rho(\textbf{A})<1$, where $\rho(\textbf{A})$ is the spectral radius (maximum eigenvalue) of $\textbf{A}$.

Here comes the question, i.e., when $f$ is not an affine function, what is the convergence criterion for such fixed point iteration?

I have read something saying that it is about $||J_f(\textbf{x})||<\rho<1$, where the norm is some natural matrix norm. However, I don't know if the norm can be any norm or some specific norm. Or there is other interpretation?

$\endgroup$
  • $\begingroup$ Of the Jacobian: en.wikipedia.org/wiki/Jacobian_matrix_and_determinant $\endgroup$ – Yiannis Galidakis Mar 26 '16 at 17:34
  • $\begingroup$ @YiannisGalidakis Thanks. But I know what Jacobian is. My confusion is that I don't know what norm should be used for the Jacobian matrix in the inequality. $\endgroup$ – Mafen Mar 26 '16 at 17:36
  • $\begingroup$ Any matrix norm that comes from a vector norm is valid. If $\|J_f\|\le\rho < 1$ everywhere, then $f$ is a contraction with respect to this norm (vector-valued version of mean value theorem). $\endgroup$ – Friedrich Philipp Mar 26 '16 at 17:45
  • $\begingroup$ @FriedrichPhilipp Thanks a lot! So this is actually only a (strong) sufficient condition, right? (Since there are some functions that are not contraction function but result in convergent iteration, as I observe.) Do you know any other (weaker) sufficient condition? $\endgroup$ – Mafen Mar 26 '16 at 18:00
  • $\begingroup$ @Mafen No, sorry, I don't. This is actually not my field I am working/experienced in. I don't know so much about fixed point theorems. $\endgroup$ – Friedrich Philipp Mar 26 '16 at 18:02

Your Answer

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

Browse other questions tagged or ask your own question.