7.2 Newton’s Method
181
What Is the Difference Between Linear and Nonlinear Equations?
You know how to solve linear equations ax + b = 0: x = −b/a. All other
types of equations f (x) = 0, i.e., when f (x) is not a linear function of x,
are called nonlinear. A typical way of recognizing a nonlinear equation is to
observe that x is “not alone” as in ax, but involved in a product with itself,
such as in x 3 + 2x 2 − 9 = 0. We say that x 3 and 2x 2 are nonlinear terms. An
equation like sin x + e x cos x = 0 is also nonlinear although x is not explicitly
multiplied by itself, but the Taylor series of sin x, e x , and cos x all involve
polynomials of x where x is multiplied by itself.
7.2 Newton’s Method
Newton’s method, also known as Newton-Raphson’s method, is a very famous and
widely used method for solving nonlinear algebraic equations. 1 Compared to the
other methods presented in this chapter, i.e., secant and bisection, it is generally the
fastest one (although computational speed rarely is an issue with a single equation
on modern laptops). However, it does not guarantee that an existing solution will be
found.
A fundamental idea of numerical methods for nonlinear equations is to construct
a series of linear equations (since we know how to solve linear equations) and hope
that the solutions of these linear equations bring us closer and closer to the solution
of the nonlinear equation. The idea will be clearer when we present Newton’s
method and the secant method.
7.2.1 Deriving and Implementing Newton’s Method
Figure 7.1 shows the f (x) function in our model equation x 2 − 9 = 0. Numerical
methods for algebraic equations require us to guess at a solution first. Here, this
guess is called x 0 . The fundamental idea of Newton’s method is to approximate
the original function f (x) by a straight line, i.e., a linear function, since it is
straightforward to solve linear equations. There are infinitely many choices of how
to approximate f (x) by a straight line. Newton’s method applies the tangent of f (x)
at x 0 , see the rightmost tangent in Fig. 7.1. This linear tangent function crosses the x
axis at a point we call x 1 . This is (hopefully) a better approximation to the solution
of f (x) = 0 than x 0 . The next fundamental idea is to repeat this process. We find
the tangent of f at x 1 , compute where it crosses the x axis, at a point called x 2 ,
and repeat the process again. Figure 7.1 shows that the process brings us closer and
closer to the left. It remains, however, to see if we hit x = 3 or come sufficiently
close to this solution.
1 Read more about Newton’s method, e.g., on https://en.wikipedia.org/wiki/Newton%27s_method.
181
What Is the Difference Between Linear and Nonlinear Equations?
You know how to solve linear equations ax + b = 0: x = −b/a. All other
types of equations f (x) = 0, i.e., when f (x) is not a linear function of x,
are called nonlinear. A typical way of recognizing a nonlinear equation is to
observe that x is “not alone” as in ax, but involved in a product with itself,
such as in x 3 + 2x 2 − 9 = 0. We say that x 3 and 2x 2 are nonlinear terms. An
equation like sin x + e x cos x = 0 is also nonlinear although x is not explicitly
multiplied by itself, but the Taylor series of sin x, e x , and cos x all involve
polynomials of x where x is multiplied by itself.
7.2 Newton’s Method
Newton’s method, also known as Newton-Raphson’s method, is a very famous and
widely used method for solving nonlinear algebraic equations. 1 Compared to the
other methods presented in this chapter, i.e., secant and bisection, it is generally the
fastest one (although computational speed rarely is an issue with a single equation
on modern laptops). However, it does not guarantee that an existing solution will be
found.
A fundamental idea of numerical methods for nonlinear equations is to construct
a series of linear equations (since we know how to solve linear equations) and hope
that the solutions of these linear equations bring us closer and closer to the solution
of the nonlinear equation. The idea will be clearer when we present Newton’s
method and the secant method.
7.2.1 Deriving and Implementing Newton’s Method
Figure 7.1 shows the f (x) function in our model equation x 2 − 9 = 0. Numerical
methods for algebraic equations require us to guess at a solution first. Here, this
guess is called x 0 . The fundamental idea of Newton’s method is to approximate
the original function f (x) by a straight line, i.e., a linear function, since it is
straightforward to solve linear equations. There are infinitely many choices of how
to approximate f (x) by a straight line. Newton’s method applies the tangent of f (x)
at x 0 , see the rightmost tangent in Fig. 7.1. This linear tangent function crosses the x
axis at a point we call x 1 . This is (hopefully) a better approximation to the solution
of f (x) = 0 than x 0 . The next fundamental idea is to repeat this process. We find
the tangent of f at x 1 , compute where it crosses the x axis, at a point called x 2 ,
and repeat the process again. Figure 7.1 shows that the process brings us closer and
closer to the left. It remains, however, to see if we hit x = 3 or come sufficiently
close to this solution.
1 Read more about Newton’s method, e.g., on https://en.wikipedia.org/wiki/Newton%27s_method.