Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My knowledge of Newton's Method is partial. I am trying to understand what guarantees this method can give on the solution of systems of non-linear equations.

Specifically, I have a set of non-linear equations that are easily twice differentiable. What additional conditions do I need to fulfill in order to guarantee that Newton's Method finds a good solution? How important is the starting point? if it is important, how can I guarantee that I find a good starting point?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

The items below should help you to look up further details of Newton's Method for system of nonlinear equations.

Advantages:

  • Q-quadratically convergent from good starting guesses if the Jacobian $J(x_*)$ is nonsingular
  • Exact solution in one iteration for an affine $F$ (exact at each iteration for any finite component functions of $F$)

Disadvantages:

  • Not globally convergent for many problems
  • Requires $J(x_k)$ at each iteration
  • Each iteration requires the solution of a system of linear equations that may be singular or ill-conditioned

References:

Notes

  • For Newton's method, you would choose a tolerance and use some vector norm to test that the result is good enough.
  • If you choose a bad starting value, all bets are off.
  • You might also want to look into quasi-Newton methods.
  • For good starting values, you want to look into the Steepest Descent method, which is used to find accurate starting approximations for the Newton-based techniques.
  • As an aside, you probably also want to look at and understand "Constrained" versus "Unconstrained" methods.
share|improve this answer
1  
Nice summary! This is really a nice resource. –  amWhy Apr 24 '13 at 1:33
    
Agreed, so bored I am actually looking a series solution method for a DEQ (yuck!) :-) –  Amzoti Apr 24 '13 at 2:36
    
Thanks! One point which is still not clear to me is how do I know if I reached the global solution for a specific problem, if I can tell that a starting point was good only in retrospect? For what classes of problems is global convergence guaranteed (convergence rate is less important to me)? –  Bitwise Apr 24 '13 at 2:39
    
@Bitwise: For Newton's method, you would choose a tolerance and use some vector norm to test that it is good enough. If you choose a bad starting value, all bets are off. You might also want to look into quasi-Newton methods. For good starting values, you want to look into Steepest Descent method, which is used to find accurate starting approximations for the Newton-based techniques. –  Amzoti Apr 24 '13 at 2:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.