Darboux' theorem on the convergence of Newton's method

Question

I've only found the text in French, which I just don't read well enough to understand what is going on. Any pointers to a clear proof in English?

The paper is Darboux, "Sur la méthode d'approximation de Newton", Nouvelles annales de mathématiques: journal des candidats aux écoles polytechnique et normale, serie 2, vol 8 (1869), pp.17-27

Could you give a link here to Darboux's theorem in any language, French or otherwise? Some of us may have heard of proofs about convergence of Newton's method but not known it by that particular name. For example, the named proof I've heard of is attributed to Kantorovich. — KCd, Feb 27 '20 at 02:05

score 3 · Answer 1 · answered Feb 27 '20 at 04:13

3

In fact, concerning Newton method, Darboux theorem is quite simple and, at the same time, extremely impotant in numerical analysis.

To make the story short, what it says is that starting iterations at $x_0$,there will be one overshoot of the solution if $$f(x_0)\, f''(x_0) < 0$$ and none of them if $$f(x_0)\, f''(x_0) > 0$$ This is why we need to test this condition before starting iterations.

answered Feb 27 '20 at 04:13

Claude Leibovici

260,315

Other conditions surely are required, like only one root only at the relevant side of $x_0$. – vonbrand Mar 01 '20 at 04:35
I do not think so. I have Darboux's paper in front of me. – Claude Leibovici Mar 01 '20 at 04:37
1

Dear @ClaudeLeibovici the paper from Darboux starts with the assumption that there is only one root between a and b -- so, there are conditions for Darboux theorem to hold – Daniel S. Apr 15 '20 at 04:01
1

@DanielS.. I totally agree with you (for sure !) – Claude Leibovici Apr 15 '20 at 04:05
@ClaudeLeibovici another question: when you say "there will be one overshoot of the solution", you mean AT MOST one? or exactly one? – Daniel S. Apr 15 '20 at 04:07
1

@DanielS. Normally, exactly one. – Claude Leibovici Apr 15 '20 at 04:10
@ClaudeLeibovici in that case, the overshoot occurs at the first iteration? can we predict the iteration at which the overshoot will occur? – Daniel S. Apr 15 '20 at 04:12
1

@DanielS. At the first. – Claude Leibovici Apr 15 '20 at 04:50
1

@ClaudeLeibovici I've read Darboux paper, but I did not find any claim about one overshoot of the solution. I just found observations about the other case, f f'' > 0 there. Please, do you have any reference about the case f f'' < 0 ? Is this result obvious from the paper? – Daniel S. Apr 16 '20 at 02:16
1

@DanielS. Read page 23 of the paper – Claude Leibovici Apr 16 '20 at 02:28
1

@ClaudeLeibovici but we have a numerical example there? sorry for not being able to find it ... – Daniel S. Apr 16 '20 at 02:41
1

@ClaudeLeibovici I've followed this discussion here https://math.stackexchange.com/questions/3627728/global-convergence-for-newtons-method-in-one-dimension-number-of-overshoots – Daniel S. Apr 16 '20 at 03:28

Darboux' theorem on the convergence of Newton's method

1 Answers1

Linked