Problem 39 - Calculus: Early Transcendentals

Question

In Section 4.8 we considered Newton's method for approximating a root \( r \) of the equation \( f(x) = 0, \) and from an initial approximation \( x_1 \) we obtained successive approximations \( x_2, x_3, . . . . , \) where \( x_{n + 1} = x_n - \frac {f (x_n)}{f' (x_n)} \) Use Taylor's Inequality with \( n = 1, a = x_n \) and \( x = r \) to show that if \( f''(x) \) exists on an interval \( I \) containing \( r, x_n, \) and \( x_{n + 1}, \) and \( \mid f''(x) \mid \le M, \mid f'(x) \mid \ge K \) for all \( x \in I, \) then \( \mid x_{n + 1} - r \mid \le \frac {M}{2K} \mid x_n - r \mid^2 \) [This means that if \( x_n \) is accurate to \( d \) decimal places, then \( x_{n + 1} \) is accurate to about \( 2d \) decimal places. More precisely, if the error at stage \( n \) is at most \( 10^{-m}, \) then the error at stage \( n + 1 \) is at most \( (M/2K)10^{-2m}. \)]

Step-by-Step Solution

Answer

Using Taylor's inequality, we derive that the error in Newton's method is bounded by \( \frac{M}{2K} |x_n - r|^2 \).

Step 1: Expand f(r) using Taylor's series

By Taylor's theorem, we can write the function as follows around the point \( x_n \):\[f(r) = f(x_n) + f'(x_n)(r-x_n) + \frac{f''(c)}{2}(r-x_n)^2\]where \( c \) is some point in the interval between \( x_n \) and \( r \). Here, \( f(r) = 0 \) because \( r \) is the root.

Step 2: Relate Taylor's expansion to Newton's update formula

We have \( x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \). Therefore, substituting for \( f(x_n) \) from the Taylor expansion, we have:\[0 = f(x_n) + f'(x_n)(r-x_n) + \frac{f''(c)}{2}(r-x_n)^2\]Rearrange this to focus on \((r-x_n)\):\[f(x_n) = -f'(x_n)(r-x_n) - \frac{f''(c)}{2}(r-x_n)^2\]

Step 3: Derive the approximation for x_{n+1} - r

Substitute the expression for \( f(x_n) \) into the update formula for Newton's method:\[x_{n+1} = x_n - \frac{-f'(x_n)(r-x_n) - \frac{f''(c)}{2}(r-x_n)^2}{f'(x_n)}\]Simplifying this:\[x_{n+1} = x_n + (r-x_n) + \frac{f''(c)}{2f'(x_n)}(r-x_n)^2\]Therefore, \( x_{n+1} - r = \frac{f''(c)}{2f'(x_n)}(r-x_n)^2 \).

Step 4: Apply the inequality constraints

According to the given bounds, we have:\[\left| \frac{f''(c)}{2f'(x_n)} \right| \le \frac{M}{2K}\]Then, combine this with the previous result:\[\left| x_{n+1} - r \right| \le \frac{M}{2K} |x_n - r|^2\]This is the desired inequality that bounds the error of the Newton's method.

Key Concepts

Taylor's Inequality

Taylor's Inequality is a powerful tool used to understand how well a Taylor series approximates a function. It provides a bound on the error of this approximation. In the context of Newton's method, we use Taylor's theorem to express a function near a point of interest. For a function with a second derivative, the expansion can be written as follows:

• For a point \( x_n \) near the root \( r \), we have:
  \[ f(r) = f(x_n) + f'(x_n)(r-x_n) + \frac{f''(c)}{2}(r-x_n)^2 \] where \( c \) is some point in the interval between \( x_n \) and \( r \).

Substituting this expansion in Newton's method helps us relate the function's behavior and the iterative process of finding a root. Here, Taylor's Inequality comes into play, providing an upper bound for the approximation error:

• Given the error constraint \( \mid f''(x) \mid \le M \) and \( \mid f'(x) \mid \ge K \), the inequality \( \mid x_{n+1} - r \mid \le \frac{M}{2K} \mid x_n - r \mid^2 \) demonstrates how error reduces with each iteration, ensuring faster convergence when the conditions are satisfied.

Root Approximation

Newton's method is a popular iterative technique to approximate the root of an equation. The goal is to find a value \( x \) such that \( f(x) = 0 \). Starting with an initial guess \( x_1 \), the method uses successive iterations to get closer to the actual root \( r \). The iterative formula is:

• \( x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \)

This formula is derived from the tangent line to the curve \( y = f(x) \) at the point \( (x_n, f(x_n)) \). By finding where this tangent line intersects the x-axis, we approximate the root. The primary advantage of Newton's method is its quadratic convergence, meaning that the error shrinks rapidly after each iteration if certain conditions are met.

• It becomes notably effective when the initial guess is close to the actual root, leading to very accurate approximations over few iterations.

Error Analysis

Error analysis in numerical methods, like Newton's method, helps us understand the deviation from the actual solution. It involves examining how closely an approximation matches the true value, in this case, the actual root \( r \).
For Newton's method, the error after each iteration can be expressed as:

• \( \mid x_{n+1} - r \mid \le \frac{M}{2K} \mid x_n - r \mid^2 \)

This quadratic error bound is crucial because it shows that the error decreases as the square of the previous error. Consequently, if the initial approximation \( x_n \) has an error of \( 10^{-m} \), the next approximation \( x_{n+1} \) potentially has an error of \( (M/2K) \times 10^{-2m} \).

• This significant reduction means each iteration could yield approximately double the number of correct decimal places, showcasing the efficiency of Newton's method when conditions are favorable.

Convergence of Iterative Methods

Iterative methods, such as Newton's method, involve repeated cycles to gradually approach a solution. A key aspect of these methods is convergence, which refers to the approach towards an accurate solution as iterations continue.
For Newton's method, convergence is influenced by several factors:

• Quadratic Convergence: If the method converges, it typically does so quadratically. This means that the number of correct decimals doubles with each iteration, provided the initial guess is sufficiently close to the true root.
• Condition Constraints: Convergence is ensured if \( \mid f'(x) \mid \ge K \) and \( \mid f''(x) \mid \le M \) on an interval containing the initial guess and the root. These conditions prevent division by very small numbers or excessive function curvature.

Understanding these factors helps predict the efficiency and reliability of the method in practical applications. Successful application of Newton's method often hinges on a good initial guess and properly satisfying the convergence conditions.