I am writing a computer program that solves a fixed-point system and I need to determine the convergence criteria. I am implementing an algorithm from a journal article, and the author states the following:
...we suggest to cast [the] system as a fixed-point system, u=g(u), with the requirement for convergence being that the eigenvalue of $ G = [∂g_i/∂u_j]$ of the largest modulus must satisfy $|λ_i|<1$.
The author cites the book Iterative Solutions of Nonlinear Equations in Several Variables by Ortega and Rheinboldt.
I am an engineer, not a mathematician, and I am really out of my depth here. I found a copy of the Ortega text, but it's a very dense book and since I don't know what page is being cited it has not been much of a help.
I have the Jacobian and have calculated its eigenvalues.
I am confused because I have replicated the example the author gives in the paper, and the system takes several iterations to converge - but at each iteration, even the first, $|λ_i|<1$! I am unable to reconcile this with the excerpt from the article I posted above.
I suppose what I am asking is this: is there something special about the largest absolute value of an eigenvalue being less than 1 when solving a fixed point system? I have found several 'oblique' references to this idea, but nothing concrete. It may just be the case that I lack the vocabulary to search properly. Or is it possible that, depending on the application, another convergence criterion may be necessary and that $|λ_i|<1$ does not necessarily guarantee convergence?
In case anyone is curious, the paper is A Note on the Analytical Solution of Cubic Equations of State in Process Simulation by Rosendo Monroy-Loperena, 2012.
When you are solving a system of $n$ equations in the form $x = G(x)$, Banach's fixed point theorem in $\mathbb{R}^n$ states that if $G$ is contractive in some norm (all norms in a finite-dimensional space are equivalent), the fixed point method will converge. When $G$ is differentiable, the contractivity can be analysed in terms of the norm of the Jacobian matrix.
So, why the eigenvalues? When you consider a matrix norm induced by some vector norm, you have that $$ \|A\| = \sup_{x\ne 0} \dfrac{\|Ax \|}{\|x\|}. $$
If $\lambda$ is an eigenvalue of $A$ and $v\ne 0$ is an associated eigenvector, you have that $A v = \lambda v$ and so, $$ \|A\| = \sup_{x\ne 0}\dfrac{\|A x\|}{\|x\|} \ge \dfrac{\|Av\|}{\|v\|} = \dfrac{\|\lambda v\|}{\|v\|} = |\lambda|$$ This way you see that the absolute value of any eigenvalue is a lower bound for any matrix norm. When all eigenvalues are smaller than 1 (in absolute value), there is some matrix norm for which $\|J_G\|<1$ and, as a consequence, the fixed point method will converge.