# Solving system of nonlinear equations

Dear all, Can anyone tell me all the algorithms that are available for finding all solutions of a system of nonlinear equations?

I am particularly interested in solving problems of the form:

X1=f1(X1,X2,...,Xn),
X2=f2(X1,X2,...,Xn),

...

Xn=fn(X1,X2,...,Xn),

where f1, f2,..., fn are nonlinear functions of their arguments and X1,X2,...,Xn are matrices.

Thanks, Pat.

-
Is your system known to have a solution? That, in fact matters. What are the properties of $f_n$? That matters as well. Finally, do you want an algorithm that 1. approximates a solution? 2. computes a solution? 3. approximates and proves that a solution exists. – Rabee Tourky Oct 13 '12 at 2:22
"Can anyone tell me all the algorithms?" -- I strongly doubt it. This question strikes me as far too vague; see mathoverflow.net/howtoask I suspect that you don't want to consider all possible non-linear functions, but rather some subclass such as noncommutative polynomials... – Yemon Choi Oct 13 '12 at 2:23
Hi, Depending on the parameterization of f, the system may not have a solution. In my case, f has the form fi(X1,X2,...,Xn)=inv(E0i+E1iX1+...+EniXn)*Hi, where E0i,...Eni and Hi are matrices. There are potentially many ways in which one can get a solution to the system above. An obvious one is successive approximation. This method may fail to produce a solution even when a solution exists. The ideal algorithm would characterize all possible solutions and show how to construct a particular solution. Thanks, Pat. – Pat M Oct 13 '12 at 10:02
Look, if your nonlinear function is the square root function, how are you proposing to define the square root of a matrix? – Yemon Choi Oct 14 '12 at 4:00
@David: This problem is not solve in undergraduate numerical analysis texts, unless I am mistaken. @Yemon: I do not have a square root function in my problem. – Pat M Oct 18 '12 at 8:41

You can use Newton's method to solve $f(X)-X=0$: in your case, it means simply to study the recursively defined sequence $$X_{k+1}=f(X_k),\quad\text{along with a clever choice for X_0.}$$ Of course here $X_k\in \mathbb R^n$. Assuming that you know that you have a solution $f(Y)=Y$ at which $f'(Y)=0$. Then $$X_{k+1}-Y=f(X_{k})-f(Y)=\int_0^1(1-\theta)f''(Y+\theta(X_k-Y))d\theta (X_k-Y)^2$$ so that assuming for instance that $f''$ is a bounded quadratic form (this could be only a local assumption) you get the so-called quadratic convergence to $Y$ (very fast convergence) $$\Vert X_{k+1}-Y\Vert\le C\Vert X_{k}-Y\Vert^2\Longrightarrow \Vert X_{k}-Y\Vert\le C^{2^k-1}\Vert X_{0}-Y\Vert^{2^k}.$$ To make only a local hypothesis, you must choose $X_0$ not too far from $Y$, which in practice is not so difficult to achieve.
On the other hand, to solve $\Phi(X)=0$, Newton's method requires only that at a solution $\Phi(Y)=0$ the differential $\Phi'(Y)$ is invertible: then your equation becomes $$\Phi(X)=0\Longleftrightarrow -\Phi'(Y)^{-1}\Phi(X)+X=X\Longleftrightarrow f(X)=X$$ with $f(X)=-\Phi'(Y)^{-1}\Phi(X)+X$, $f(Y)=Y$, $f'(Y)=0$ and you are back to the previous setting.
A simple 1D example is $$f(x)=\frac{x}{2}+\frac{a}{2x},\quad\text{a>0, x_{k+1}=f(x_k) converging to \sqrt{a}}$$ an excellent algorithm to compute the square root, anyhow much faster than the high-school tedious method of extraction. Try your hand with $a=2$, you will see how accurate is the approximation of $\sqrt 2$for simply $k=2$, starting with $x_0=2$.
Yes: the method devised by Newton solves the equation $\Phi(X)=0$ at simple zeroes. Somehow these zeroes are stable by small perturbation and are much easier to find than the zeroes at which the differential is vanishing. – Bazin Oct 24 '12 at 21:56