A practical strategy to improve performance of Newton's method in solving nonlinear equations

1.   Introduction

In real-world applications, a great number of nonlinear equations cannot be solved with exact solutions. The common strategy to solve such complicated problems is to obtain its approximate solution using an appropriate procedure known as 'numeric approach' or 'numeric computation'. There are many different established numeric methods for solving various nonlinear equations. Newton's method is a popular approach among the numeric methods due to its simplicity and quadratic convergence. Hence, it has been widely presented in many mathematics textbooks [1,2,3,4,5,6] and books of numeric computation [7,8,9].

According to [10], Newton's method was originally presented as an immature form by Newton as a special case of the method in the 1670s, which was actually different from the current method. After a number of attempts by other mathematicians since then, Joseph Raphson found a simplified expression for this method in 1690, from which Thomas Simpson formulated the method as an iterative process to solve general nonlinear equations using the derivative of a function. This iterative process became the current formula of Newton's method, sometimes also called the Newton-Raphson method, but Simpson was missed in the brand of the modern method he formulated.

Despite the simplicity of Newton's method in iterative numeric computation through computer or calculator programs with a general quadratic convergence [9], a number of difficulties have been noticed over the years. For example, there is no guarantee that the solution (or root) for the nonlinear equation is unique in a given range [a, b] even the process is certain to be convergent. A chosen initial point, usually a or b, does not ensure the process converging to the root for special cases where the derivative at the initial point is zero. In other instances, the process fails in progression where the derivative at the initial point does not exist.

Given the diverse causes behind the difficulties, there has been no concrete strategy proposed to effectively deal with the difficulties mentioned in most mathematics textbooks. For instance, the 'normal cases' were used to demonstrate the iterative process for Newton's method in [4,7] to avoid addressing any of the difficult situations. For the circumstances where the derivative at the initial point is zero or does not exist, a new initial point should be chosen as suggested in [1,2,8,9], but no concrete strategies were offered for how to choose the new initial point. Using graphs was suggested to choose a new initial point in [3,5] when encountering divergence in the iterative process or the derivative at the initial point is zero or does not exist. This works but also means a halt in automatic processing of iteration when the execution is through a computer program.

In this note, based on the classroom experience in teaching solving nonlinear equations using Newton's method to preservice secondary-school mathematics teachers at Central Queensland University (CQU) of Australia in recent years, a practical strategy for choosing the initial point to the iterative process for both the normal and special cases is shared with the mathematics teaching and learning communities around the world.

2.   Fundamentals of Newton's method

Solving an equation f(x) = 0 within [a, b] is equivalent to finding the point x = x_r (∈ [a, b]) where f(x) intersects the x-axis (Figure 1). Such a point x = x_r is called the root for f(x) = 0 if it exists. It is not easy to judge if any root exists for a general equation f(x) = 0, but in a situation where f(a) and f(b) have opposite signs, such point (or points) indeed exists. This is because for a continuous and differentiable function f(x) defined within [a, b], the curve of the function must cross the x-axis at least once so that f(a) and f(b) have opposite signs.

Newton's method uses a sequence of x-intercepts of the tangent lines from an initial point x₀ (usually either a or b) to approximate the root for equation f(x) = 0 within [a, b]. Suppose the initial point to be x₀ = b (Figure 1). The tangent line on f(x) at (x₀, f(x₀)) crosses the x-axis at x₁ and the tangent of this line is the derivative of f(x) at x₀ = b, i.e.,

This means that x₁ can be determined by the values of x, y and y′ at the initial point x₀. The new point x₁, closer to x_r compared to x₀, can be used to find a new x-intercept x₂ in a similar way as follows

Obviously x₂ is even closer to x_r compared to x₁. Repeating this process will take the consecutive x-intercepts approaching the root of the equation. This iterative procedure is captured by the following recurrent relation, called Newton's method:

The iteration terminates when the difference of two consecutive x-intercepts is smaller than a pre-set error limit, i.e., $\left| {{x_{i + 1}} - {x_i}} \right| < \varepsilon$, which indicates how close the approximate value of x_i is to the root x_r. If such condition is met after the ith iteration, an acceptable approximate solution is found for f(x) = 0, i.e., x_r ≈ x_i+1. Note that i begins from 0.

3.   Solving nonlinear equations by Newton's method: Examples

This section presents different examples of nonlinear equations solved using Newton's method to demonstrate some difficulties in using this method.

Example 1: Solve equation $f(x) = \frac{1}{x} - \ln x = 0$ in [1,3] using Newton's method with ε = 0.001.

Since f(a) = f(1) = 1 and f(b) = f(3) = 1/3 – ln3 ≈ –0.7653, Newton's method can be used to solve this nonlinear equation.

Formula (1) becomes

Let x₀ = a = 1.

Since $\left| {{x_1} - {x_0}} \right| = \left| {1.5 - 1} \right| = 0.5 > \varepsilon = 0.001,$ let x₁ = 1.5.

Since $\left| {{x_2} - {x_1}} \right| = \left| {1.7351 - 1.5} \right| = 0.2351 > \varepsilon = 0.001,$ let x₂ = 1.7351.

Since $\left| {{x_3} - {x_2}} \right| = \left| {1.7629 - 1.7351} \right| = 0.0278 > \varepsilon = 0.001,$ let x₃ = 1.7629.

Since $\left| {{x_4} - {x_3}} \right| = \left| {1.7631 - 1.7629} \right| = 0.0002 < \varepsilon = 0.001,$ the approximate solution is x ≈ x₄ = 1.7631.

The iterative process above can also be realized using Excel as a table shown below.

Of course, if choosing x₀ = b = 3, the similar iterative process should lead to the same solution for this case as shown in the table below. Note this choice takes one more iteration to reach the same root. This is a 'normal case' where choosing any of the two end points ensures convergence of iteration to the same root where the curve of f(x) crosses the x-axis showing in Figure 2.

Example 2: Solve equation ${x^3} - 2x + 2 = \sqrt {x + 2}$ in [0, 1] using Newton's method with ε = 0.001.

We first rearrange ${x^3} - 2x + 2 = \sqrt {x + 2}$ to $f(x) = {x^3} - 2x + 2 - \sqrt {x + 2} .$ Solving the equation becomes solving equation $f(x) = {x^3} - 2x + 2 - \sqrt {x + 2} = 0.$ Since $f(a) = f(0) = 2 - \sqrt 2 \approx 0.5858$ and $f(b) = f(1) = 1 - 2 + 2 - \sqrt 3 \approx - 0.7321$, Newton's method can be used to solve this nonlinear equation.

Formula (1) becomes

Let x₀ = a = 0. The iterative process using the formula above is tabulated in the following table.

If choosing x₀ = b = 1, however, the similar iterative process produces a different solution of x = 1.3713 outside of the range [0, 1] after 6 iterations showing in the table below. If we plot f(x) beyond the range [0, 1], it shows that x = 1.3713 is another root of this equation (Figure 3). This is an 'abnormal case' or a special case for using Newton's method. This non-uniqueness is simply because the right end x = b = 1 is located closer to the root on its right and sharing the same ascending tendency in tangent to the right side of the curve. That is, the tangent of the left section is negative and approaches to root x = 0.2573 whereas the tangent of the right section is positive and approaches to the other root x = 1.3713.

Example 3: Solve equation $\cos x - \sqrt x = 0$ in [0, 1] with ε = 0.001 using Newton's method.

Since f(a) = $\cos 0 - \sqrt 0 = 1$ and f(b) = ${\cos _r}(1) - \sqrt 1 \approx 0.5403 - 1 = - 0.4597$, Newton's method can be used to solve this nonlinear equation.

We can see the derivative at the left end x = a = 0 does not exist. Still using Formula (1),

Let x₀ = a = 0.

This means that the iteration does not progress if choosing the left endpoint as the initial point where $f'(0)$ does not exist.

However, by choosing the right endpoint as the initial point, i.e., x₀ = b = 1, the iteration converges to x ≈ x₅ = 0.6419 showing in the table below. Note that the input value for trigonometric functions should be in radians.

Example 4: Solve equation $f(x) = {x^2} - \sin x = 0$ in [0.5, 1] using Newton's method with ε = 0.001.

Since f(a) = f(0.5) = 0.25 – sin_r0.5 ≈ 0.25 – 0.4794 = –0.2294 and f(b) = f(1) = 1 – sin_r1 ≈ 1 – 0.8415 = 0.1585, Newton's method can be used to solve this nonlinear equation.

Formula (1) becomes

Letting x₀ = b = 1, it takes 3 iterations to find an acceptable root x ≈ x₃ = 0.8767 shown in the table below.

The same solution can be reached by choosing x₀ = a = 0.5. However, the convergence of the process would be much slower by taking 6 iterations to find the first acceptable root x ≈ x₆ = 0.8767 shown in the table below. It can be clearly seen in the plot of this function (Figure 4) that the left endpoint x₀ = a = 0.5 is near a local minimum on the curve where the tangent line is almost horizontal (green line) and its x-intercept is far beyond the right endpoint b = 1. In contrast, the tangent line from the right endpoint (blue line) x₀ = b = 1 has a larger value for the gradient (or the derivative of the function), leading to an x-intercept closer to the root. Hence, it reaches the root faster than beginning from the left endpoint.

This example is still a normal case for using Newton's method. However, it demonstrates that the speed of convergence in iteration heavily depends on the choice of the initial point.

Example 5: Solve equation $\sin x - \frac{1}{{x + 1}} = 0$ in [0, 1.5] with ε = 0.001 using Newton's method.

Since $f(a) = f(0) = \sin 0 - \frac{1}{{0 + 1}} = - 1$ and $f(b) = f(1.5) = {\sin _r}1.5 - \frac{1}{{1.5 + 1}} \approx 0.5975$, Newton's method can be used to solve this nonlinear equation.

By formula (1) and choosing x₀ = a = 0, it takes 4 iterations to find the first acceptable root x ≈ x₄ = 0.6508 shown in the table below.

Choosing x₀ = b = 1.5, however, the process does not converge. Each iteration produced x-intercept outside the confined range [0, 1.5] shown in the table below.

Observing the curve of this function (red line) and the tangent line crossing the right end (1.5, 0.5975) shown as the blue line in Figure 5, its initial x-intercept projects to the negative half outside of the range, further away from the solution around x = 0.65. The divergence of the iterative process is caused by the small gradient of the tangent line at the right endpoint. If choosing another inner point, for instance x₀ = 1, the gradient of the line crossing this point is larger (green line) and the process will converge to the same root after 4 iterations shown in the table below.

4.   A practical strategy to improve performance of Newton's method

The examples presented in Section 3 were all from the worked samples and exercises in the tailored textbook, Essentials and Examples of Applied Mathematics (2^nd ed) [6], for the preservice secondary-school mathematics teachers at CQU. Many of the problems with Newton's method were gradually exposed by either the teacher (also the author of the textbook) or students since 2020. The advice provided to students for dealing with those special issues was initially the same as the general suggestions made in other books, such as 'choosing the other endpoint if one endpoint did not work' or 'choosing a new point close to the endpoint if the end point did not work', or 'using a graph of the function to help choose the initial point'.

However, a conversation on the matters of using Newton's method with one talented student in 2022 triggered further thinking about a general but practical strategy for dealing with such matters in using Newton's method. The student simply augured that any other method could be equally effective to find the acceptable root if we choose the initial point close enough to the 'true root' on the graph of the nonlinear equation or function within the range. If so, why should we still stick with Newton's method with the assistance of a graph?

There are still difficulties in proving if a general rule exists as a specific guide to the users when encountering some of the difficulties in using Newton's method. Instead, a practical strategy is shared below to guide students and other users to choose the initial point to avoid encountering the difficulties exposed in Section 3 with Newton's method without plotting the nonlinear equation or function. This strategy is stated as follows:

By meeting the condition that the continuous and differentiable nonlinear function f(x) within the range [a, b] has values at the two endpoints with opposite signs, it is recommended to choose the middle point of the range as the initial point to start the iterative process of Newton's method, i.e., x₀ = (a + b)/2.

The check of the values at the two endpoints with opposite signs ensures existence of at least one root within the given range [a, b] for a continuous and differentiable function. Of course, the smaller the range, the better the chance to find a unique root within the range. For example, in Example 2, only one root x = 0.2573 would be found if the range is defined as [0, 0.5].

Strictly proving the correctness of this simple strategy is beyond the author's capability. However, ten problems, including the five questions presented in Section 3, have been solved by Newton's method using this strategy with a smaller error limit ε = 0.0001, along with the results from starting the process at the two endpoints as comparisons in the performances of Newton's method for solving these questions. The performance data in term of the number of iterations for all questions are summarized in Table 1. All the questions, the iterative processes and outcomes are detailed in Appendix A.

5.   Discussion and conclusion

A few observations can be made from the data in Table 1. First, by choosing the middle point as the initial point, the iterative process of solving the ten nonlinear equations by Newton's method converged to the desired root within the range without the assistance of the graph of a function. Using the middle point to initiate the process, there is no difficult to find the desired root within the range for the four special cases where an endpoint did not work as expected for Newton's method.

Second, in most cases, beginning with the middle point reaches the desired root with fewer iterations, or no slower than beginning from any of the two endpoints. This is because the middle point should be closer to the root than the endpoints in most cases, which in turn leads to reaching the root with fewer iterations. However, in cases where the solution is located near any of the two endpoints, like Example 2 where the root x = 0.2573 is near the left endpoint x = 0 and far away from the right endpoint x = 1.5, using the middle point as the initial point may be slightly slower than using the near endpoint in approaching the root.

Hence, choosing the middle point of a defined range to initiate the iterative process for Newton's method seems a general and practical strategy to avoid the difficulties encountered in using the method to solve nonlinear equations. However, more work needs to be done to prove how far this strategy could be extended in dealing with various special cases in using Newton's method in the future.

Appendix A

The ten nonlinear equations to which Newton's method was applied. The error limit is ε = 0.0001 for all questions.

1. Solve equation $f(x) = \frac{1}{x} - \ln x = 0$ in [1,3].

2. Solve equation ${x^3} - 2x + 2 = \sqrt {x + 2}$ in [0, 1].

3. Solve equation $\cos x - \sqrt x = 0$ in [0, 1].

4. Solve equation $f(x) = {x^2} - \sin x = 0$ in [0.5, 1].

5. Solve equation $\sin x - \frac{1}{{x + 1}} = 0$ in [0, 1.5].

6. Solve equation ${e^x} - x - 3 = 0$ in [1,2].

7. Solve equation ${x^3} - 4{x^2} + x - 7 = 0$ in [3.5, 4.5].

8. Solve equation $x{e^x} = {x^2} + 1$ in [0, 1].

9. Solve equation $\sqrt[3]{x} - \frac{1}{{\sqrt {x + 1} }} = 0$ in [0, 1].

10. Solve equation $2\sin x + 1 = 2\cos x$ in [0, π/2].