# Solving an overdetermined system of nonlinear equations

I'm wondering what the "best" way to approach solving a system of the following form would be:

$A_1X + Be^{CY} = A_2$

$A_3X + Be^{CY} = A_4$

$A_5X + Be^{CY} = A_6$

etc.

EDIT: Coefficients $A_i, B, C$ are all real numbers - X and Y are unknowns.

With this system it looks like I could take the log of both sides and then use least squares to fit a line to the log of the data. What would be the best way to go about it in the more general case if it were not possible to linearize the equation in that way? Apply Newton's method?

-
You might want to mention that/whether the variables here are matrices/vectors or numbers. I'm guessing that the $A_i$, B$, and$C$are matrices, but it's far from clear. – Arturo Magidin Jun 18 '11 at 5:21 What are known and what are unknown (in the A's B's and C's)? – ziyuang Jun 18 '11 at 5:29 Sorry! In this case they're just real numbers, not matrices. – Bitrex Jun 18 '11 at 5:29 X and Y are the unknowns. I've edited my post to clarify things. – Bitrex Jun 18 '11 at 5:32 If B and C are givens then you can just define$ Y' = B e^{CY} $and solve for Y later. Then you can get the system as a 2 column matrix times the vector (X,Y') equaling some vector, for which you can use the Moore-Penrose inverse to get a 'best-fit' solution. (If you know a single solution exists definitively, then you can just chop off all of the equations but two of them, so long as you don't select two equivalent ones, and solve with typical linear algebra.) – anon Jun 18 '11 at 5:40 ## 2 Answers If your system were linear (for instance, because of the change of variables suggested by @anon), then the right way to go would be to solve the system in the least-squares sense. In general, an over-determined system has no solution, so you want to get "as close as possible", i.e., minimize the squared$\ell_2\$-norm of the residual. To do this, you can use a multitude of methods (see for example the excellent book by Lawson and Hanson: http://www.ec-securehost.com/SIAM/CL15.html). If your coefficient matrix is anywhere near large and sparse I'd recommend Mike Saunders' LSQR or MINRES: http://www.stanford.edu/group/SOL/software).

Now you can also attack your nonlinear system directly using a nonlinear least-squares method such as that of Levenberg and Marquardt (I believe Matlab has an implementation of it, as does MINPACK: http://www.netlib.org/minpack), Gauss-Newton or NL2SOL (http://dl.acm.org/citation.cfm?id=355966). The basic idea is similar to Newton's method but at each iteration, a linear least-squares problem is solved.

-

I made this tutorial article about linear and nonlinear least-squares, including Levenberg-Marquardt method.

The Newton's method is explained there as well. It may work well with your equations, but you have to try. Sometimes it is quite sensitive on initialization.

-