🚀 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

In <SMITH.92Sep1154327@minerva.harvard.edu> smith@minerva.harvard.edu (Steven Smith) writes:

>Let g: R^n -> R^n.  [...]

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

	Not so.  The solutions of the equation are isolated (implicit
function theorem) but there may be infinitely many.  Let

	g(x,y) = (exp(x)cos(y)-1, exp(x) sin(y)).  

Then det g' = exp(2x) != 0 anywhere, but g(0,2*Pi*n) = 0 for every
integer n.

-- 
*_________________*  "Faculty members encourage the free pursuit of       
 Roger Alexander  | learning in their students and protect academic          
 alex@iastate.edu | freedom of students." --ISU Faculty Handbook
*_________________* [official statement of policies & procedures]

alex@iastate.edu (Roger Alexander) writes:

>          Not so.  The solutions of the equation are isolated (implicit
> function theorem) but there may be infinitely many.  Let
>
>          g(x,y) = (exp(x)cos(y)-1, exp(x) sin(y)).
>
> Then det g' = exp(2x) != 0 anywhere, but g(0,2*Pi*n) = 0 for every
> integer n.

Yes, I posted before I thought.  The example x -> sin x works too.
The zero set of an analytic function !==0 is at most countable.

Steven Smith

In <SMITH.92Sep2103757@minerva.harvard.edu> smith@minerva.harvard.edu (Steven Smith) writes:

>alex@iastate.edu (Roger Alexander) writes:

>>          Not so.  The solutions of the equation are isolated (implicit
>> function theorem) but there may be infinitely many.  Let
>>
>>          g(x,y) = (exp(x)cos(y)-1, exp(x) sin(y)).
>>
>> Then det g' = exp(2x) != 0 anywhere, but g(0,2*Pi*n) = 0 for every
>> integer n.

>			[...]  The example x -> sin x works too.

This function is not an example because the derivative has a zero.
-- 
*_________________*  "Faculty members encourage the free pursuit of       
 Roger Alexander  | learning in their students and protect academic          
 alex@iastate.edu | freedom of students." --ISU Faculty Handbook
*_________________* [official statement of policies & procedures]

alex@iastate.edu (Roger Alexander) writes:

> >			[...]  The example x -> sin x works too.
> 
> This function is not an example because the derivative has a zero.

I don't understand what you mean.  The zero set of sin x is the
integers multiplied by pi.  The derivative of sin x at these points is
+- unity.  Newton's method works like a dream this instance.

Steven Smith

In article <1992Sep1.094300.2414@nuscc.nus.sg> 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 ?

Don't be surprised about errors or deficiencies in NR.  The authors
are physicists, not numerical analysts.  They have usually just
cobbled together something that seems to work on one of their
special problems, and made a leap of faith to generalize to all
superficially similar problems.

For nonlinear least squares problems, get nl2sol from netlib.
netlib is a network library server operated by Eric Grosse at AT&T
and Jack Dongarra at Oak Ridge National Laboratory.  Start by sending
"send help" and "send index" to netlib@ornl.gov.

-- 
vsnyder@jato.Jpl.Nasa.Gov   vsnyder@math.Jpl.Nasa.Gov  <-- preferred
ames!elroy!jato!vsnyder     ames!elroy!math!vsnyder
vsnyder@jato.uucp