Solving system of nonlinear equations - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T19:34:42Z http://mathoverflow.net/feeds/question/109506 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109506/solving-system-of-nonlinear-equations Solving system of nonlinear equations Pat M 2012-10-13T02:14:52Z 2012-10-13T16:10:28Z <p>Dear all, Can anyone tell me all the algorithms that are available for finding all solutions of a system of nonlinear equations?</p> <p>I am particularly interested in solving problems of the form: </p> <p>X1=f1(X1,X2,...,Xn),<br> X2=f2(X1,X2,...,Xn),</p> <p>... </p> <p>Xn=fn(X1,X2,...,Xn), </p> <p>where f1, f2,..., fn are nonlinear functions of their arguments and X1,X2,...,Xn are matrices.</p> <p>Thanks, Pat.</p> http://mathoverflow.net/questions/109506/solving-system-of-nonlinear-equations/109540#109540 Answer by Bazin for Solving system of nonlinear equations Bazin 2012-10-13T16:10:28Z 2012-10-13T16:10:28Z <p>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. </p> <p>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.</p> <p>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$.</p>