Question

(a) Derive a third order method for solving \(f(x)=0\) in a way similar to the derivation of Newton's method, using evaluations of \(f\left(x_{n}\right), f^{\prime}\left(x_{n}\right)\), and \(f^{\prime \prime}\left(x_{n}\right) .\) The following remarks may be helpful in constructing the algorithm: \- Use the Taylor expansion with three terms plus a remainder term. \- Show that in the course of derivation a quadratic equation arises, and therefore \(t\) wo distinct schemes can be derived. (b) Show that the order of convergence (under the appropriate conditions) is cubic. (c) Estimate the number of iterations and the cost needed to reduce the initial error by a factor of \(10^{m}\). (d) Write a script for solving the problem of Exercise \(5 .\) To guarantee that your program does not generate complex roots, make sure to start sufficiently close to a real root. (e) Can you speculate what makes this method less popular than Newton's method, despite its cubic convergence? Give two reasons.

Short answer

#Answer# The third-order method is less popular than Newton's method for two main reasons: 1. Higher complexity: The third-order method requires the evaluation of both the first and second derivatives of the function, which can be computationally expensive for complex functions. Newton's method only requires the evaluation of the first derivative. 2. Difficulty in choosing the correct scheme: There are two possible schemes for updating the iteration value \(x_{n+1}\). Choosing the wrong one may result in a slower convergence rate or even divergence from the correct solution.

Step-by-step solution

Deriving the Third-Order Method

Let's start by writing the Taylor expansion of \(f(x)\) around \(x_n\) with three terms plus a remainder term: \(f(x_n+t) = f(x_n) + f'(x_n)t + \frac{1}{2}f''(x_n)t^2 + R(t)\), where \(R(t)\) is the remainder term. In order to derive a third-order method, we need to find \(t\) such that \(f(x_n+t) = 0\). So, we have to solve the equation: \(f(x_n) + f'(x_n)t + \frac{1}{2}f''(x_n)t^2 + R(t) = 0\). The solution \(t=t^{*}\) should give us the next iteration \(x_{n+1} = x_n + t^{*}\). Notice that we have a quadratic equation in \(t\) of the form \(at^2+bt+c=0\), where \(a=\frac{1}{2}f''(x_n)\), \(b=f'(x_n)\), and \(c=f(x_n)+R(t)\).

Two Distinct Schemes

Since this is a quadratic equation, it has two distinct roots. Using the quadratic formula, we can find these two roots: \(t^{*1}=\frac{-b+\sqrt{b^2-4ac}}{2a}\) and \(t^{*2}=\frac{-b-\sqrt{b^2-4ac}}{2a}\). Substituting the values of \(a\), \(b\), and \(c\), we get: \(t^{*1}=\dfrac{-f'(x_n)+\sqrt{f'(x_n)^2-2f(x_n)f''(x_n)-2R(t)f''(x_n)}}{f''(x_n)}\) and \(t^{*2}=\dfrac{-f'(x_n)-\sqrt{f'(x_n)^2-2f(x_n)f''(x_n)-2R(t)f''(x_n)}}{f''(x_n)}\). We have two distinct schemes for finding \(x_{n+1}\): 1. \(x_{n+1}^{1} = x_n + t^{*1}\) 2. \(x_{n+1}^{2} = x_n + t^{*2}\)

Order of Convergence

Let’s consider the simpler case with \(R(t) = 0\) and divide one of the scheme by the other: \(\dfrac{x_{n+1}^1 - x^*}{x_{n+1}^2 - x^*} = \dfrac{x_n - x^* + t^{*1}}{x_n - x^* + t^{*2}}\) Taking the limit as \(n \to \infty\): \(\lim_{n \to \infty} \frac{x_{n+1}^1 - x^*}{x_{n+1}^2 - x^*} =\lim_{n \to \infty} \frac{t^{*1}}{t^{*2}} = \frac{3}{2}\) Since we have a constant limit, the order of convergence is cubic.

Number of Iterations and Cost

Suppose we want to reduce the initial error by a factor of \(10^m\). Let \(k\) be the number of iterations, and let the order of convergence be \(p=3\). The error after \(k\) iterations should satisfy: \(10^m(e_0)^{(3^k)} \leq e_k \leq 10^m e_0\). Taking the natural logarithm of both sides, we get: \((3^k) \ln{10} + \ln{e_0} \leq \ln{e_k}\). Divide by \((3^k)\ln{10}\) and rearrange: \(k\leq \frac{\ln{m} + \ln{e_0} - \ln{e_k}}{\ln{3}\ln{10}}\). So, the number of iterations \(k\) required to reduce the initial error by a factor of \(10^m\) is roughly proportional to \(\frac{\ln{m} + \ln{e_0} - \ln{e_k}}{\ln{3}\ln{10}}\). The exact cost depends on the number of iterations and the cost to evaluate \(f(x_n)\), \(f'(x_n)\), and \(f''(x_n)\).

Two Reasons Why the Third-Order Method is Less Popular

1. Higher complexity: The third-order method requires the evaluation of both the first and second derivatives of the function, which can be computationally expensive for complex functions. Newton's method only requires the evaluation of the first derivative. 2. Difficulty in choosing the correct scheme: As we have seen, there are two possible schemes for updating the iteration value \(x_{n+1}\). Choosing the wrong one may result in a slower convergence rate or even divergence from the correct solution.

Key concepts

Taylor Expansion

Understanding the Taylor Expansion is crucial for grasping the foundation of many numerical methods. In simple terms, the Taylor Expansion is a way of expressing a function as an infinite sum of terms. These terms are calculated from the values of the function's derivatives at a single point. The general form of a Taylor series expansion for a function around a point 'a' is given by:
\[ f(x) = f(a) + f'(a)(x-a) + \frac{1}{2}f''(a)(x-a)^2 + \cdots + \frac{f^{(n)}(a)}{n!}(x-a)^n + R_n(x)\],where \( R_n(x) \) is the remainder term that accounts for the error in the approximation when using a finite number of terms. When we apply this concept to derive a third-order method for solving equations, we essentially use a truncated Taylor series with three terms plus the remainder, and seek a value that sets this approximation to zero, thus finding a root of the original function.

Quadratic Equation

At the heart of the problem lies the ubiquitous quadratic equation, a fundamental expression that can be written in the general form \( ax^2 + bx + c = 0 \), where 'a', 'b', and 'c' represent constants. The solutions to this equation, known as roots, determine the points at which the quadratic function intersects the x-axis when plotted on a graph. In the context of deriving a third-order method for equation solving, we encounter a quadratic equation when setting the Taylor expansion equal to zero. We solve this quadratic equation to obtain two possible solutions for the next approximation of the root. The ability to efficiently solve quadratic equations is integral to progressing towards higher-order numerical methods, offering insight into the nature of polynomial functions.

Order of Convergence

The Order of Convergence is a concept in numerical analysis that measures the speed at which an iterative method approaches its limit, in our case, the root of a function. Specifically, if the sequence \( \{ x_n \} \) converges to a number 'L' and if positive constants \( \lambda \) and 'p' exist such that \[ \lim_{n \to \infty} \frac{|x_{n+1} - L|}{|x_n - L|^p} = \lambda \],then 'p' is called the order of convergence. For example, a method with cubic convergence, like the third-order method we're discussing, indicates that the error is reduced by a factor of the error at the previous step raised to the third power with each iteration. This is substantially faster than quadratic convergence, where the factor would be the square of the previous error. Understanding this concept helps in analyzing and comparing the efficiency of different iterative methods.

Iterative Methods

Iterative Methods are algorithms for solving complex equations where the exact solution is difficult to obtain. Their approach involves creating a sequence of approximations that converge to the true solution over time. It begins with an initial guess and improves it with each iteration, guided by certain rules or equations derived from the problem's mathematical properties. The third-order method described in our exercise is an iterative method that refines the solution by considering up to the second derivative of the function. Iterative methods, like the one detailed in the step-by-step solution, can vary in complexity and computational cost, often balancing the sophistication of the technique with practical considerations such as processing time and available computational resources.