home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / numanal / 2612 < prev    next >
Encoding:
Internet Message Format  |  1992-09-01  |  2.1 KB
  1. Path: sparky!uunet!ogicse!das-news.harvard.edu!das-news!smith
  2. From: smith@minerva.harvard.edu (Steven Smith)
  3. Newsgroups: sci.math.num-analysis
  4. Subject: Re: Newton Raphsons iteration method
  5. Message-ID: <SMITH.92Sep1154327@minerva.harvard.edu>
  6. Date: 1 Sep 92 20:43:27 GMT
  7. Article-I.D.: minerva.SMITH.92Sep1154327
  8. References: <1992Sep1.094300.2414@nuscc.nus.sg>
  9. Sender: usenet@das.harvard.edu (Network News)
  10. Organization: Harvard Robotics Lab, Harvard University
  11. Lines: 38
  12. In-Reply-To: suresh@papaya.iss.nus.sg's message of Tue, 1 Sep 1992 09:43:00 GMT
  13.  
  14. suresh@papaya.iss.nus.sg (Suresh Thennarangam - Research Scholar) writes:
  15.  
  16. > Newton-Raphson's method can handle non-linear n-dimensional equations
  17. > with reasonable results given a good starting point. What happens
  18. > if the system of equations is over-determined ? i.e. M equations in
  19. > N unknowns where M > N. 
  20. > 
  21. > I used the routine mnewt() from Numerical Recipes ... with SVD as the 
  22. > backbone linear equation solver. It always converged when M <= N but 
  23. > refused to converge when M > N.
  24. > 
  25. > Any comments about this ? Can NR handle M > N at all or does the 
  26. > algorithm have to modified to make it work ?
  27.  
  28. Let g: R^n -> R^n.  Newton's method is used to determine a point at
  29. which g vanishes, i.e., it solves the equation g(x) = 0.
  30.  
  31. Note that if det g' != 0, then the number of points in R^n satisfying
  32. g(x) = 0 must be finite.
  33.  
  34. If you have g: R^n -> R^m, m < n, g' full rank, then the equation
  35. g(x) = 0 determines some subset of dimension n - m in R^n.  Newton's
  36. method may (or may not) converge to any point in this subset.  I
  37. believe that NR gets around the degeneracy of g as map into
  38. R^m subset R^n by simply not inverting the small singular values
  39. of g'.
  40.  
  41. In case m > n, the equation g(x) = 0 may not have a solution.
  42. Consider, e.g., the map t -> (1+t, 1-t) from R to R^2.  Of course
  43. Newton's method, even the Numerical Recipes version, could not
  44. converge in such instances.
  45.  
  46. These ideas are all encapsulated by the implicit function theorem.
  47.  
  48. Nevertheless, there are methods to minimize the norm of g.  See, e.g.,
  49. Fletcher's _Practical Methods of Optimization_.
  50.  
  51. Steven Smith
  52.