university-logo

Newton’s method

Tsung-Ming Huang

Department of Mathematics National Taiwan Normal University, Taiwan

September 27, 2010

university-logo

Suppose that f : ℝ → ℝ and f ∈ C^{2}[a, b], i.e., f′′ exists and is continuous. If f (x^{∗}) = 0 and x^{∗} = x + h where h is small, then by Taylor’s theorem

0 = f (x^{∗}) = f (x + h)
= f (x) + f′(x)h + \frac{1}{2}f′′(x)h^{2} + \frac{1}{3!}f′′′(x)h^{3} + ⋯
= f (x) + f′(x)h + O(h^{2}).

Since h is small, O(h^{2}) is negligible. It is reasonable to drop O(h^{2}) terms. This implies

f (x) + f′(x)h ≈ 0 and h ≈ −\frac{f (x)}{f′(x)}, if f′(x) ≠ 0.

Hence

x + h = x − \frac{f (x)}{f′(x)}

is a better approximation to x^{∗}.

university-logo

This sets the stage for the Newton-Rapbson’s method, which starts with an initial approximation x_{0} and generates the sequence {x_{n}}_{n=0}^{∞} defined by

x_{n+1} = x_{n} − \frac{f (x_{n})}{f′(x_{n})}.

Since the Taylor’s expansion of f (x) at x_{k} is given by

f (x) = f (x_{k}) + f′(x_{k})(x − x_{k}) + \frac{1}{2}f′′(x_{k})(x − x_{k})^{2} + · · · .

At x_{k}, one uses the tangent line

y = ℓ(x) = f (x_{k}) + f′(x_{k})(x − x_{k})

to approximate the curve of f (x) and uses the zero of the tangent line to approximate the zero of f (x).

university-logo

Newton’s Method

Given x_{0}, tolerance TOL, maximum number of iteration M. Set i = 1 and x = x_{0} − f (x_{0})/f′(x_{0}). While i ≤ M and |x − x_{0}| ≥ TOL

Set i = i + 1, x_{0} = x and x = x_{0} − f (x_{0})/f′(x_{0}). End While

university-logo

Problem

The equation f (x) ≡ x^{2} − 10 cos x = 0 has two solutions ±1.3793646. Use Newton’s method to approximate the solutions with initial values ±25.

Requirements

1 Write two MATLAB functions, said fun f and fun df, to compute the

values of f and f′, respectively. 2 Implement the Newton’s algorithm as a MATLAB function:

▶ Input arguments: fun f, fun df, initial value

▶ Output arguments: approximated solution of the equation