Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
2  
"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+E1i*X1+...+Eni*Xn)*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
show 2 more comments

1 Answer

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$.

share|improve this answer
    
Hi Bazin, writing down the Newton for the problem I want to solve is rather complicated and expensive. In addition, the newton algorithm would be sensitive to the starting value and might deliver a different answer for every start value. The reason I am interested in an algorithm that could possibly give me all solutions is that I do not know in advance which solution I am computing. –  Pat M Oct 18 '12 at 8:37
    
This certainly won't give all solutions. –  David Ketcheson Oct 22 '12 at 4:00
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.