Math 441

Newton’s Method cont.

Newton’s Method

Suppose \(f \in \mathcal{C}^2([a,b])\) and \(f(p) = 0\) for some \(p \in (a,b)\).

Given \(p_n \in (a,b)\) such that \(f'(p_n) \neq 0\), define

\[p_{n+1} = p_n - \frac{f(p_n)}{f'(p_n)}.\]

If \(f'(p) \neq 0\) and \(p_0\) is chosen close enough to \(p\), then the sequence \(p_n\) generated by the Newton’s method converges to \(p\), and

\[\lim_{n \to \infty}\frac{p = p_{n+1}}{(p - p_n)^2} = -\frac{f''(p)}{2f'(p)}.\]

Newton’s method has a quadratic convergence.

More properties

• Needs both \(f\) and \(f'\).
• Two function evaluations per iteration
  • One \(f(p_n)\)
  • One \(f'(p_n)\)
• Convergence depends on the initial guess, is not guaranteed.
• In best circumstances, convergence is quadratic.

Getting rid of the \(f'\) requirement

• The geometry of Newton’s method is based on tangent lines.
• We can use secant lines instead of tangent lines.
• We need two points for a secant line.
• We start with \(p_0\) and \(p_1\). Use them to calculate \(p_2\).
• Then use \(p_1\) and \(p_2\) to calculate \(p_3\).
• …
• \[p_{n+2} = p_{n+1} - \frac{p_{n+1} - p_n}{f(p_{n+1}) - f(p_n)}f(p_{n+1})\]

Questions:

• How many function evaluations per iteration?
• How fast is the convergence?