Solving system of nonlinear equations

2012-10-13T02:14:52Z

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.

Answer by Bazin for Solving system of nonlinear equations

2012-10-13T16:10:28Z

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

Solving system of nonlinear equations - MathOverflow

Solving system of nonlinear equations

Answer by Bazin for Solving system of nonlinear equations