🚀 go-pugleaf

suresh@papaya.iss.nus.sg (Suresh Thennarangam - Research Scholar) writes:

> Newton-Raphson's method can handle non-linear n-dimensional equations
> with reasonable results given a good starting point. What happens
> if the system of equations is over-determined ? i.e. M equations in
> N unknowns where M > N. 
> 
> I used the routine mnewt() from Numerical Recipes ... with SVD as the 
> backbone linear equation solver. It always converged when M <= N but 
> refused to converge when M > N.
> 
> Any comments about this ? Can NR handle M > N at all or does the 
> algorithm have to modified to make it work ?

Let g: R^n -> R^n.  Newton's method is used to determine a point at
which g vanishes, i.e., it solves the equation g(x) = 0.

Note that if det g' != 0, then the number of points in R^n satisfying
g(x) = 0 must be finite.

If you have g: R^n -> R^m, m < n, g' full rank, then the equation
g(x) = 0 determines some subset of dimension n - m in R^n.  Newton's
method may (or may not) converge to any point in this subset.  I
believe that NR gets around the degeneracy of g as map into
R^m subset R^n by simply not inverting the small singular values
of g'.

In case m > n, the equation g(x) = 0 may not have a solution.
Consider, e.g., the map t -> (1+t, 1-t) from R to R^2.  Of course
Newton's method, even the Numerical Recipes version, could not
converge in such instances.

These ideas are all encapsulated by the implicit function theorem.

Nevertheless, there are methods to minimize the norm of g.  See, e.g.,
Fletcher's _Practical Methods of Optimization_.

Steven Smith