Editing Newton's method (section)

====Interval Newton's method====
{{cite check|section|date=February 2019}}
Combining Newton's method with [[interval arithmetic]] is very useful in some contexts. This provides a stopping criterion that is more reliable than the usual ones (which are a small value of the function or a small variation of the variable between consecutive iterations). Also, this may detect cases where Newton's method converges theoretically but diverges numerically because of an insufficient [[floating-point arithmetic|floating-point precision]] (this is typically the case for polynomials of large degree, where a very small change of the variable may change dramatically the value of the function; see [[Wilkinson's polynomial]]).<ref>Moore, R. E. (1979). ''Methods and applications of interval analysis'' (Vol. 2). Siam.</ref><ref>Hansen, E. (1978). Interval forms of Newtons method. ''Computing'', 20(2), 153–163.</ref>

Consider {{math|{{var|f}} → {{mathcal|C}}{{sup|1}}({{var|X}})}}, where {{mvar|X}} is a real interval, and suppose that we have an interval extension {{mvar|{{prime|F}}}} of {{mvar|{{prime|f}}}}, meaning that {{mvar|{{prime|F}}}} takes as input an interval {{math|{{var|Y}} ⊆ {{var|X}}}} and outputs an interval {{math|{{var|{{prime|F}}}}({{var|Y}})}} such that:

<math display="block">\begin{align}
    F'([y,y]) &= \{f'(y)\}\\[5pt]
    F'(Y) &\supseteq \{f'(y)\mid y \in Y\}.
\end{align}</math>

We also assume that {{math|0 ∉ {{var|{{prime|F}}}}({{var|X}})}}, so in particular {{mvar|f}} has at most one root in {{mvar|X}}.
We then define the interval Newton operator by:

<math display="block">N(Y) = m - \frac{f(m)}{F'(Y)} = \left\{\left.m - \frac{f(m)}{z} ~\right|~ z \in F'(Y)\right\}</math>

where {{math|{{var|m}} ∈ {{var|Y}}}}. Note that the hypothesis on {{mvar|{{prime|F}}}} implies that {{math|{{var|N}}({{var|Y}})}} is well defined and is an interval (see [[interval arithmetic]] for further details on interval operations). This naturally leads to the following sequence:

<math display="block">
\begin{align}
X_0 &= X\\
X_{k+1} &= N(X_k) \cap X_k.
\end{align}
</math>

The [[mean value theorem]] ensures that if there is a root of {{mvar|f}} in {{math|{{var|X}}{{sub|{{var|k}}}}}}, then it is also in {{math|{{var|X}}{{sub|{{var|k}} + 1}}}}. Moreover, the hypothesis on {{mvar|F′}} ensures that {{math|{{var|X}}{{sub|{{var|k}} + 1}}}} is at most half the size of {{math|{{var|X}}{{sub|{{var|k}}}}}} when {{mvar|m}} is the midpoint of {{mvar|Y}}, so this sequence converges towards {{math|[{{var|x*}}, {{var|x*}}]}}, where {{mvar|x*}} is the root of {{mvar|f}} in {{mvar|X}}.

If {{math|{{var|{{prime|F}}}}({{var|X}})}} strictly contains 0, the use of extended interval division produces a union of two intervals for {{math|{{var|N}}({{var|X}})}}; multiple roots are therefore automatically separated and bounded.