Excercise 17, Page 173

Why does Newton’s Method fail in finding a root of f(x) = x^3 − 3x^2 + x + 3 when x0 = 1?

Introduction

Newton’s Method is an iterative technique for finding the roots (zeros) of a real-valued function. The formula for the method is given by: \[\begin{equation} x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \end{equation}\] where \(x_n\) is the current guess, \(f(x_n)\) is the function value at \(x_n\), and \(f'(x_n)\) is the derivative of the function at \(x_n\). The formula essentially finds the x-intercept of the tangent line to the curve at \(x_n\), which is used as the next guess \(x_{n+1}\).

Illustration to show failure of Newton’s Method

# Define the Function and Its Derivative
f <- function(x) x^3 - 3*x^2 + x + 3
df <- function(x) 3*x^2 - 6*x + 1

#  implement Newton's Method to see the iteration process from x0 = 1
newton_method <- function(f, df, initial_guess, max_iter = 20) {
  x <- numeric(max_iter + 1)
  x[1] <- initial_guess
  for (i in 1:max_iter) {
    x[i+1] <- x[i] - f(x[i]) / df(x[i])
  }
  x
}

# Perform iterations
iterations <- newton_method(f, df, 1)
iterations
##  [1] 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1

Visualize the result

x_vals <- seq(0, 3, length.out = 300)
y_vals <- f(x_vals)

# Create the plot
plot(x_vals, y_vals, type = 'l', col = 'blue', lwd = 2, ylab = "f(x)", xlab = "x", main = "Function f(x) = x^3 - 3x^2 + x + 3")
points(iterations, f(iterations), col = 'red', pch = 19, cex = 1.5)
text(iterations, f(iterations), labels = paste0("x", 0:length(iterations)-1), pos = 4, col = 'red')

# Adding tangent lines at each iteration
for (i in 1:length(iterations)) {
  # Tangent line approximation: y = f'(iterations[i]) * (x - iterations[i]) + f(iterations[i])
  tangent_line <- function(x) df(iterations[i]) * (x - iterations[i]) + f(iterations[i])
  lines(x_vals, tangent_line(x_vals), col = 'green', lty = 2)
}

Failure Analysis of Newton’s Method

Newton’s Method is known for its robust capability in finding roots through iterative approximations. However, in the case of the function \(f(x) = x^3 - 3x^2 + x + 3\) with an initial guess \(x_0 = 1\), the method fails due to oscillation between points. This phenomenon is explained as follows:

Oscillation Between Points

The process begins at \(x_0 = 1\), where the tangent line’s intersection with the x-axis points to \(x_1 = 2\). Iteratively, \(x_1 = 2\) leads back to \(x_0 = 1\). This cyclical pattern causes the method to oscillate between these two values without converging towards a root. This specific behavior can be summarized by the following equations and observations: \[\begin{align*} x_0 &= 1, \\ x_1 &= 2, \\ x_2 &= 1, \\ x_3 &= 2, \\ &\vdots \end{align*}\]

Influence of the Derivative

The derivative of the function, \(f'(x) = 3x^2 - 6x + 1\), impacts the updates significantly:

  • At \(x_1 = 2\), the derivative does not lead toward the root but instead directs the guess back to \(x_0 = 1\).
  • At \(x_0 = 1\), the derivative again points back to \(x_1 = 2\), forming a loop.

This cycle is exacerbated by the steepness or shallowness of the tangent slopes at these points, which are not effective in progressing toward any true roots.

The primary failure of Newton’s Method in this scenario is linked to the inappropriate initial guess which is exacerbated by the function’s derivative dynamics at the starting and subsequent points. The plot illustrates the iterative failures: * The red points represent the iteration locations. * Green lines represent the tangent at each iteration.

Recommendations

Adjusting the initial guess could potentially overcome these issues, ensuring more reliable root-finding in complex function landscapes.