0
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$ Oct 13, 2012 at 2:22
  • 2
    $\begingroup$ "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... $\endgroup$
    – Yemon Choi
    Oct 13, 2012 at 2:23
  • $\begingroup$ 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. $\endgroup$
    – Pat M
    Oct 13, 2012 at 10:02
  • $\begingroup$ Look, if your nonlinear function is the square root function, how are you proposing to define the square root of a matrix? $\endgroup$
    – Yemon Choi
    Oct 14, 2012 at 4:00
  • $\begingroup$ @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. $\endgroup$
    – Pat M
    Oct 18, 2012 at 8:41

1 Answer 1

1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Pat M
    Oct 18, 2012 at 8:37
  • $\begingroup$ This certainly won't give all solutions. $\endgroup$ Oct 22, 2012 at 4:00
  • $\begingroup$ 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. $\endgroup$
    – Bazin
    Oct 24, 2012 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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