Algebraic and transcendental equations

27.1 ALGEBRAIC AND TRANSCENDENTAL EQUATIONS
errors introduced as a result of approximations made in setting up the numerical
procedures (truncation errors). For this scale of application, books specifically
devoted to numerical analysis, data analysis and computer programming should
be consulted.
So far as is possible, the method of presentation here is that of indicating
and discussing in a qualitative way the main steps in the procedure, and then
of following this with an elementary worked example. The examples have been
restricted in complexity to a level at which they can be carried out with a pocket
calculator. Naturally it will not be possible for the student to check all the
numerical values presented, unless he or she has a programmable calculator or
computer readily available, and even then it might be tedious to do so. However,
it is advisable to check the initial step and at least one step in the middle of
each repetitive calculation given in the text, so that how the symbolic equations
are used with actual numbers is understood. Clearly the intermediate step should
be chosen to be at a point in the calculation at which the changes are still
sufficiently large that they can be detected by whatever calculating device is
used.
Where alternative methods for solving the same type of problem are discussed,
for example in finding the roots of a polynomial equation, we have usually
taken the same example to illustrate each method. This could give the mistaken
impression that the methods are very restricted in applicability, but it is felt by
the authors that using the same examples repeatedly has sufficient advantages, in
terms of illustrating the relative characteristics of competing methods, to justify
doing so. Once the principles are clear, little is to be gained by using new
examples each time, and, in fact, having some prior knowledge of the ‘correct
answer’ should allow the reader to judge the efficiency and dangers of particular
methods as the successive steps are followed through.
One other point remains to be mentioned. Here, in contrast with every other
chapter of this book, the value of a large selection of exercises is not clear cut.
The reader with sufficient computing resources to tackle them can easily devise
algebraic or differential equations to be solved, or functions to be integrated
(which perhaps have arisen in other contexts). Further, the solutions of these
problems will be self-checking, for the most part. Consequently, although a
number of exercises are included, no attempt has been made to test the full range
of ideas treated in this chapter.
27.1 Algebraic and transcendental equations
The problem of finding the real roots of an equation of the form f(x) = 0, where
f(x) is an algebraic or transcendental function of x, is one that can sometimes
be treated numerically, even if explicit solutions in closed form are not feasible.
985
NUMERICAL METHODS
f(x)
14
12
10
f(x) = x5 − 2x2 − 3
8
6
4
2
0
−2
x
0.2 0.4 0.6 0.8 1.0 1.2 1.4 1.6 1.8
−4
Figure 27.1 A graph of the function f(x) = x5 − 2x2 − 3 for x in the range
0 ≤ x ≤ 1.9.
Examples of the types of equation mentioned are the quartic equation,
ax4 + bx + c = 0,
and the transcendental equation,
x − 3 tanh x = 0.
The latter type is characterised by the fact that it contains, in effect, a polynomial
of infinite order on the LHS.
We will discuss four methods that, in various circumstances, can be used to
obtain the real roots of equations of the above types. In all cases we will take as
the specific equation to be solved the fifth-order polynomial equation
f(x) ≡ x5 − 2x2 − 3 = 0.
(27.1)
The reasons for using the same equation each time were discussed in the introduction to this chapter.
For future reference, and so that the reader may follow some of the calculations
leading to the evaluation of the real root of (27.1), a graph of f(x) in the range
0 ≤ x ≤ 1.9 is shown in figure 27.1.
Equation (27.1) is one for which no solution can be found in closed form, that
is in the form x = a, where a does not explicitly contain x. The general scheme to
be employed will be an iterative one in which successive approximations to a real
root of (27.1) will be obtained, each approximation, it is to be hoped, being better
than the preceding one; certainly, we require that the approximations converge
and that they have as their limit the sought-for root. Let us denote the required
986
27.1 ALGEBRAIC AND TRANSCENDENTAL EQUATIONS
root by ξ and the values of successive approximations by x1 , x2 , . . . , xn , . . . . Then,
for any particular method to be successful,
lim xn = ξ,
n→∞
where f(ξ) = 0.
(27.2)
However, success as defined here is not the only criterion. Since, in practice,
only a finite number of iterations will be possible, it is important that the values
of xn be close to that of ξ for all n > N, where N is a relatively low number;
exactly how low it is naturally depends on the computing resources available and
the accuracy required in the final answer.
So that the reader may assess the progress of the calculations that follow, we
record that to nine significant figures the real root of equation (27.1) has the
value
ξ = 1.495 106 40.
(27.3)
We now consider in turn four methods for determining the value of this root.
27.1.1 Rearrangement of the equation
If equation (27.1), f(x) = 0, can be recast into the form
x = φ(x),
(27.4)
where φ(x) is a slowly varying function of x, then an iteration scheme
xn+1 = φ(xn )
(27.5)
will often produce a fair approximation to the root ξ after a few iterations,
as follows. Clearly, ξ = φ(ξ), since f(ξ) = 0; thus, when xn is close to ξ,
the next approximation, xn+1 , will differ little from xn , the actual size of the
difference giving an order-of-magnitude indication of the inaccuracy in xn+1
(when compared with ξ).
In the present case, the equation can be written
x = (2x2 + 3)1/5 .
(27.6)
Because of the presence of the one-fifth power, the RHS is rather insensitive
to the value of x used to compute it, and so the form (27.6) fits the general
requirements for the method to work satisfactorily. It remains only to choose a
starting approximation. It is easy to see from figure 27.1 that the value x = 1.5
would be a good starting point, but, so that the behaviour of the procedure at
values some way from the actual root can be studied, we will make a poorer
choice, x1 = 1.7.
With this starting value and the general recurrence relationship
xn+1 = (2x2n + 3)1/5 ,
987
(27.7)
NUMERICAL METHODS
n
1
2
3
4
5
6
7
8
xn
1.7
1.544
1.506
1.497
1.495
1.495
1.495
1.495
18
86
92
78
27
14
12
f(xn )
5.42
1.01
2.28 × 10−1
5.37 × 10−2
1.28 × 10−2
3.11 × 10−3
7.34 × 10−4
1.76 × 10−4
Table 27.1 Successive approximations to the root of (27.1) using the method
of rearrangement.
n
1
2
3
4
5
6
An
1.0
1.2973
1.4310
1.4762
1.4897
1.4936
f(An )
−4.0000
−2.6916
−1.0957
−0.3482
−0.1016
−0.0289
Bn
1.7
1.7
1.7
1.7
1.7
1.7
f(Bn )
5.4186
5.4186
5.4186
5.4186
5.4186
5.4186
xn
1.2973
1.4310
1.4762
1.4897
1.4936
1.4947
f(xn )
−2.6916
−1.0957
−0.3482
−0.1016
−0.0289
−0.0082
Table 27.2 Successive approximations to the root of (27.1) using linear
interpolation.
successive values can be found. These are recorded in table 27.1. Although not
strictly necessary, the value of f(xn ) ≡ x5n − 2x2n − 3 is also shown at each stage.
It will be seen that x7 and all later xn agree with the precise answer (27.3) to
within one part in 104 . However, f(xn ) and xn − ξ are both reduced by a factor
of only about 4 for each iteration; thus a large number of iterations would be
needed to produce a very accurate answer. The factor 4 is, of course, specific
to this particular problem and would be different for a different equation. The
successive values of xn are shown in graph (a) of figure 27.2.
27.1.2 Linear interpolation
In this approach two values, A1 and B1 , of x are chosen with A1 < B1 and
such that f(A1 ) and f(B1 ) have opposite signs. The chord joining the two points
(A1 , f(A1 )) and (B1 , f(B1 )) is then notionally constructed, as illustrated in graph
(b) of figure 27.2, and the value x1 at which the chord cuts the x-axis is determined
by the interpolation formula
xn =
An f(Bn ) − Bn f(An )
,
f(Bn ) − f(An )
988
(27.8)
27.1 ALGEBRAIC AND TRANSCENDENTAL EQUATIONS
(a)
(b)
6
6
x1
4
4
x2
2
2
x3
1.0
1.2
1.6
1.4
ξ
−2
−4
1.0
(c)
4
4
2
2
x1 x3 x4
1.0
1.6
1.4
ξ
x2
x3
(d)
6
−4
x1
−4
6
−2
1.2
−2
1.2
1.4
x2 1.6
ξ
ξ
1.0
−2
1.2
1.4 x 1.6
3
x2
x1
−4
Figure 27.2 Graphical illustrations of the iteration methods discussed in
the text: (a) rearrangement; (b) linear interpolation; (c) binary chopping;
(d) Newton–Raphson.
with n = 1. Next, f(x1 ) is evaluated and the process repeated after replacing
either A1 or B1 by x1 , according to whether f(x1 ) has the same sign as f(A1 ) or
f(B1 ), respectively. In figure 27.2(b), A1 is the one replaced.
As can be seen in the particular example that we are considering, with this
method there is a tendency, if the curvature of f(x) is of constant sign near
the root, for one of the two ends of the successive chords to remain unchanged.
Starting with the initial values A1 = 1 and B1 = 1.7, the results of the first
five iterations using (27.8) are given in table 27.2 and indicated in graph (b) of
figure 27.2. As with the rearrangement method, the improvement in accuracy,
as measured by f(xn ) and xn − ξ, is a fairly constant factor at each iteration
(approximately 3 in this case), and for our particular example there is little to
choose between the two. Both tend to their limiting value of ξ monotonically,
from either higher or lower values, and this makes it difficult to estimate limits
within which ξ can safely be presumed to lie. The next method to be described
gives at any stage a range of values within which ξ is known to lie.
989
NUMERICAL METHODS
n
1
2
3
4
5
6
7
8
An
1.0000
1.3500
1.3500
1.4375
1.4813
1.4813
1.4922
1.4922
f(An )
−4.0000
−2.1610
−2.1610
−0.9946
−0.2573
−0.2573
−0.0552
−0.0552
Bn
1.7000
1.7000
1.5250
1.5250
1.5250
1.5031
1.5031
1.4977
f(Bn )
5.4186
5.4186
0.5968
0.5968
0.5968
0.1544
0.1544
0.0487
xn
1.3500
1.5250
1.4375
1.4813
1.5031
1.4922
1.4977
1.4949
f(xn )
−2.1610
0.5968
−0.9946
−0.2573
0.1544
−0.0552
0.0487
−0.0085
Table 27.3 Successive approximations to the root of (27.1) using binary
chopping.
27.1.3 Binary chopping
Again two values of x, A1 and B1 , that straddle the root are chosen, such that
A1 < B1 and f(A1 ) and f(B1 ) have opposite signs. The interval between them is
then halved by forming
xn = 12 (An + Bn ),
(27.9)
with n = 1, and f(x1 ) is evaluated. It should be noted that x1 is determined
solely by A1 and B1 , and not by the values of f(A1 ) and f(B1 ) as in the linear
interpolation method. Now x1 is used to replace either A1 or B1 , depending on
which of f(A1 ) or f(B1 ) has the same sign as f(x1 ), i.e. if f(A1 ) and f(x1 ) have the
same sign then x1 replaces A1 . The process isthen repeated to obtain x2 , x3 , etc.
This has been carried through in table 27.3 for our standard equation (27.1)
and is illustrated in figure 27.2(c). The entries have been rounded to four places
of decimals. It is suggested that the reader follows through the sequential replacements of the An and Bn in the table and correlates the first few of these with
graph (c) of figure 27.2.
Clearly, the accuracy with which ξ is known in this approach increases by only
a factor of 2 at each step, but this accuracy is predictable at the outset of the
calculation and (unless f(x) has very violent behaviour near x = ξ) a range of x
in which ξ lies can be safely stated at any stage. At the stage reached in the last
row of table 27.3 it may be stated that 1.4949 < ξ < 1.4977. Thus binary chopping
gives a simple approximation method (it involves less multiplication than linear
interpolation, for example) that is predictable and relatively safe, although its
convergence is slow.
27.1.4 Newton–Raphson method
The Newton–Raphson (NR) procedure is somewhat similar to the interpolation
method, but, as will be seen, has one distinct advantage over the latter. Instead
990
27.1 ALGEBRAIC AND TRANSCENDENTAL EQUATIONS
n
1
2
3
4
5
6
xn
1.7
1.545
1.498
1.495
1.495
1.495
01
87
13
106 40
106 40
f(xn )
5.42
1.03
7.20 × 10−2
4.49 × 10−4
2.6 × 10−8
—
Table 27.4 Successive approximations to the root of (27.1) using the Newton–
Raphson method.
of (notionally) constructing the chord between two points on the curve of f(x)
against x, the tangent to the curve is notionally constructed at each successive
value of xn , and the next value, xn+1 , is taken as the point at which the tangent
cuts the axis f(x) = 0. This is illustrated in graph (d) of figure 27.2.
If the nth value is xn , the tangent to the curve of f(x) at that point has slope
f (xn ) and passes through the point x = xn , y = f(xn ). Its equation is thus
y(x) = (x − xn )f (xn ) + f(xn ).
(27.10)
The value of x at which y = 0 is then taken as xn+1 ; thus the condition y(xn+1 ) = 0
yields, from (27.10), the iteration scheme
xn+1 = xn −
f(xn )
.
f (xn )
(27.11)
This is the Newton–Raphson iteration formula. Clearly, if xn is close to ξ then xn+1
is close to xn , as it should be. It is also apparent that if any of the xn comes close
to a stationary point of f, so that f (xn ) is close to zero, the scheme is not going
to work well.
For our standard example, (27.11) becomes
xn+1 = xn −
x5n − 2x2n − 3
4x5 − 2x2 + 3
= n 4 n
.
4
5xn − 4xn
5xn − 4xn
(27.12)
Again taking a starting value of x1 = 1.7, we obtain in succession the entries
in table 27.4. The different values are given to an increasing number of decimal
places as the calculation proceeds; f(xn ) is also recorded.
It is apparent that this method is unlike the previous ones in that the increase
in accuracy of the answer is not constant throughout the iterations but improves
dramatically as the required root is approached. Away from the root the behaviour
of the series is less satisfactory, and from its geometrical interpretation it can be
seen that if, for example, there were a maximum or minimum near the root then
the series could oscillate between values on either side of it (instead of ‘homing
in’ on the root). The reason for the good convergence near the root is discussed
in the next section.
991