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.

The following paper http://benisrael.net/Newton-MP.pdf provides a way to solve a system of equations using Newton's method. (The theorem begins at the end of page 2)

I can't understand the assumptions made in the proof : enter image description here

Basically, what I want to know is , how does the author get to this assumption? :

$$ \frac{M}{2}*||T_{u}|| + N < K < 1 $$ where M is the Lipschitz constant, $T_{u}$ is the pseudo-inverse of the jacobian at u, and N comes from (11).

Based on these assumptions , the rest of the proof is clear to me. But the basic assumptions aren't. Any help would be greatly appreciated! :)

share|improve this question

1 Answer 1

Constants:

  • $\alpha$ tells something about the initial residual (or the first Newton step)
  • $N$ is the Lipschitz constant of $u \mapsto T_u$
  • $K$ yields an uniform upper bound on the pseudo-inverses

Assumptions:

  • $h=\alpha K<1$: the initial residual is small compared to the bounds of the inverses
  • $\frac12 M \|T_u\|+N<K<1$ is most likely the right form of an inequality as later used in the proof ;)

These assumptions seem pretty standard for Newton-Kantorovich results.

share|improve this answer
    
Thanks for answering, but I need some more help! " $\frac12 M \|T_u\|+N<K<1$ is most likely the right form of an inequality as later used in the proof ;)" Can you be more clear about what this assumption exactly means, and when is this valid? Even providing some reference article would do! :) –  Ojas Jun 26 at 5:54
    
The inequality means that the norm of the pseudoinverses is small compared to other quantities. If you have a concrete problem then you can try to check whether this assumption is valid. That is the problem with proofs like this: there are assumptions that cannot be checked. –  daw Jun 26 at 8:06
    
I always thought that if you have a good enough initial guess for the problem, then Newton's method should converge to a solution. Does this mean that the norm of the pseudo-inverse is small near the solution? –  Ojas Jun 26 at 8:54
    
You need a good initial guess of course. However, here 'good' does not mean close to a given solution, but something else. Note that the theorem does not assume the existence of a solution in the given ball, rather the existence comes as an extra conclusion. That is the difference between the 'standard' Newton method proof and this so-called Newton-Kantorovich theorem. –  daw Jun 26 at 8:58
    
I understand that. But can we reason in the opposite direction? Existence of a solution implies $||T_u||$ is small? –  Ojas Jun 26 at 9:04

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.