Editing Newton's method (section)

===Proof of quadratic convergence for Newton's iterative method===
According to [[Taylor's theorem]], any function {{math|{{var|f}}({{var|x}})}} which has a continuous second derivative can be represented by an expansion about a point that is close to a root of {{math|{{var|f}}({{var|x}})}}. Suppose this root is {{mvar|α}}. Then the expansion of {{math|{{var|f}}({{var|α}})}} about {{math|{{var|x}}{{sub|{{var|n}}}}}} is:
{{NumBlk2|:|<math>f(\alpha) = f(x_n) + f'(x_n)(\alpha - x_n) + R_1 \,</math>|1}}

where the [[Lagrange remainder|Lagrange form of the Taylor series expansion remainder]] is

<math display="block">R_1 = \frac{1}{2!}f''(\xi_n)\left(\alpha - x_n\right)^{2} \,,</math>

where {{math|{{var|ξ}}{{sub|{{var|n}}}}}} is in between {{math|{{var|x}}{{sub|{{var|n}}}}}} and {{mvar|α}}.

Since {{mvar|α}} is the root, ({{EquationNote|1}}) becomes:

{{NumBlk2|:|<math>0 = f(\alpha) = f(x_n) + f'(x_n)(\alpha - x_n) + \tfrac12f''(\xi_n)\left(\alpha - x_n\right)^2 \,</math>|2}}

Dividing equation ({{EquationNote|2}}) by {{math|{{var|{{prime|f}}}}({{var|x}}{{sub|{{var|n}}}})}} and rearranging gives

{{NumBlk2|:|<math> \frac {f(x_n)}{f'(x_n)}+\left(\alpha-x_n\right) = \frac {- f'' (\xi_n)}{2 f'(x_n)}\left(\alpha-x_n\right)^2 </math>|3}}

Remembering that {{math|{{var|x}}{{sub|{{var|n}} + 1}}}} is defined by

{{NumBlk2|:|<math> x_{n+1} = x_{n} - \frac {f(x_n)}{f'(x_n)} \,,</math>|4}}

one finds that

<math display="block"> \underbrace{\alpha - x_{n+1}}_{\varepsilon_{n+1}} = \frac {- f'' (\xi_n)}{2 f'(x_n)} {(\,\underbrace{\alpha - x_n}_{\varepsilon_{n}}\,)}^2 \,.</math>

That is,

{{NumBlk2|:|<math> \varepsilon_{n+1} = \frac {- f'' (\xi_n)}{2 f'(x_n)} \cdot \varepsilon_n^2 \,.</math>|5}}

Taking the absolute value of both sides gives

{{NumBlk2|:|<math> \left| {\varepsilon_{n+1}}\right| = \frac {\left| f'' (\xi_n) \right| }{2 \left| f'(x_n) \right|} \cdot \varepsilon_n^2 \,. </math> |6}}

Equation ({{EquationNote|6}}) shows that the [[order of convergence]] is at least quadratic if the following conditions are satisfied:

# {{math|{{var|{{prime|f}}}}({{var|x}}) ≠ 0}}; for all {{math|{{var|x}} ∈ {{var|I}}}}, where {{mvar|I}} is the interval {{math|[{{var|α}} − {{abs|{{var|ε}}{{sub|0}}}}, {{var|α}} + {{abs|{{var|ε}}{{sub|0}}}}]}};
# {{math|{{var|{{prime|f|c=&Prime;}}}}({{var|x}})}} is continuous, for all {{math|{{var|x}} ∈ {{var|I}}}};
# {{math|{{var|M}} {{abs|{{var|ε}}{{sub|0}}}} < 1}}

where {{mvar|M}} is given by

<math display="block"> M = \frac12 \left( \sup_{x \in I} \vert f'' (x) \vert \right) \left( \sup_{x \in I} \frac {1}{ \vert f'(x) \vert } \right) . \,</math>

If these conditions hold,

<math display="block"> \vert \varepsilon_{n+1} \vert \leq M \cdot \varepsilon_n^2 \,. </math>