Problem 8 - A First Course in Numerical Methods

Question

It is known that the order of convergence of the secant method is \(p=\frac{1+\sqrt{5}}{2}=1.618 \ldots\) and that of Newton's method is \(p=2\). Suppose that evaluating \(f^{\prime}\) costs approximately \(\alpha\) times the cost of approximating \(f\). Determine approximately for what values of \(\alpha\) Newton's method is more efficient (in terms of number of function evaluations) than the secant method. You may neglect the asymptotic error constants in your calculations. Assume that both methods are starting with initial guesses of a similar quality.

Step-by-Step Solution

Answer

Given that Newton's method is more efficient when the cost of evaluating the derivative (α) is less than 0.118, provide a short answer explaining in your own words when to choose Newton's method over the secant method. Answer: Newton's method should be chosen over the secant method when the cost of evaluating the derivative of the function is relatively low (α < 0.118) compared to the cost of evaluating the function itself. In such cases, Newton's method will be more efficient in terms of the number of function evaluations required to achieve a desired level of accuracy.

Step 1: Express the efficiency of the two methods in terms of the number of iterations required

We will first express both methods' efficiency through the number of iterations required to achieve a certain level of accuracy, considering the given orders of convergence (\(p_{sec} = 1.618\) for the secant method, and \(p_{newt} = 2\) for Newton's method). The number of iterations required to achieve a desired level of accuracy is proportional to the inverse of the order of convergence. In other words, if the accuracy doubles, the number of iterations of the secant method increases by a factor of \(1 / p_{sec} = 1/1.618\) and the Newton's method by a factor of \(1 / p_{newt} = 1/2\).

Step 2: Formulate an inequality comparing the efficiency of both methods using the given α

We are given that evaluating \(f'\) costs approximately α times the cost of approximating \(f\). The total cost of Newton's method can be represented as the sum of the cost of evaluating the function and the cost of evaluating its derivative, while for the secant method, it only involves evaluating the function. Let \(C_N\) be the total cost of Newton's method and \(C_S\) the total cost of the secant method in terms of \(f\) evaluations. We want to find the values of α for which \(C_N < C_S\). Since Newton's method has order of convergence 2, and we are also evaluating the derivative, the cost of Newton's method is: $$C_N = \frac{1}{2} + \alpha$$ For the secant method, with order of convergence 1.618, the cost is: $$C_S = \frac{1}{1.618}$$

Step 3: Determine the values of α for which Newton's method is more efficient

We are required to solve the inequality: $$\frac{1}{2} + \alpha < \frac{1}{1.618}$$ To find the values of α for which Newton's method is more efficient, we first solve for α: $$\alpha < \frac{1}{1.618} - \frac{1}{2}$$ Now, calculating the value gives: $$\alpha < 0.118033...$$ So, Newton's method is more efficient (in terms of the number of function evaluations) for values of α less than approximately 0.118.

Key Concepts

Secant Method

The Secant Method is a numerical technique used to find the roots of a function. Unlike Newton's method, it does not require the calculation of the derivative of the function. Instead, it uses two initial guesses to approximate the derivative. The main idea is to draw a secant line through two points on the graph of the function, and use the intersection of this line with the x-axis as an improved guess.
The process is iterated, continually updating the two points used for the secant line to get closer to the actual root. The method's efficiency largely depends on these initial guesses. If they are close to the actual root, the method can converge quite rapidly.

Calculating the Next Iteration

To calculate the next point, the formula used is:
\[ x_{n+1} = x_n - f(x_n)\frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})} \]
This process will be repeated until the result satisfies the desired level of accuracy. The efficiency of this method compared to others like Newton's method, particularly in terms of number of function evaluations, is a crucial aspect to consider when choosing an appropriate method for solving equations numerically.

Newton's Method

Newton's Method, also known as the Newton-Raphson method, is a powerful algorithm to find successively better approximations to the roots (or zeroes) of a real-valued function. To use it, one starts with an initial guess which is reasonably close to the true root, and then the function is approximated by its tangent line.
In each iteration, the x-intercept of this tangent line (which involves the calculation of both the function and its derivative) becomes the next approximation to the root. The formula for this iteration process is given by:
\[ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \]
The efficiency of Newton's method is directly linked to the computation of the derivative, which can be expensive in terms of computational resources. However, it generally converges very rapidly, with a quadratic order of convergence, if the initial guess is good, and if the function satisfies certain conditions near the root.

Order of Convergence

The Order of Convergence is a key concept in numerical analysis that helps us to understand and predict how quickly an iterative method approaches the solution to a given problem. It is a measure of the rate at which the sequence of approximate solutions converges to the exact solution.
Mathematically, for a sequence \({x_n}\) converging to a limit \(x\), if there exists a constant \(C\) and a number \(p > 0\) such that:
\[ \lim_{n \to \infty} \frac{|x_{n+1} - x|}{|x_n - x|^p} = C \]
then the sequence is said to have an order of convergence \(p\). The larger the value of \(p\), the faster the sequence converges. For example, the secant method has an order of convergence of approximately 1.618 (related to the golden ratio), while Newton's method has an order of convergence of 2, indicating that under ideal conditions, Newton's method would converge faster than the secant method.
However, in practice, the efficiency of a method also depends on other factors like the computational cost of function evaluations, which is why the order of convergence is just one aspect to consider when comparing the efficiency of numerical methods.