Chapter Roots of Equations
Many problems in science and engineering can be expressed in the form of an equation in a single unknown, i.e., y = F(x). A value of x that makes y = 0 is called a root of the function; often the solution to a scientific problem is a root of a function. If the function to be solved is a quadratic equation, there is a familiar formula to find the two roots of the expression. But for almost all other functions, similar formulas aren't available; the roots must be obtained by successive approximations, beginning with an initial estimate and then refining it. This chapter presents a number of methods for obtaining the roots or zeroes of a function.
A Graphical Method
As a preliminary step in finding the roots of a complicated or unfamiliar function, it is helpful to make a chart of the function, in order to get preliminary estimates of the roots, and indeed to find out how many roots there are. A cubic equation such as the one shown in equation 8-1 and Figure 8-1, y = x3 + 0.13x2- 0.0005* - 0.0009 (8-1)
always has three roots, either three real roots as in Figure 8-1, or one real and two imaginary roots. Figure 8-27 later in this chapter shows an example of the latter case.
- Figure 8-1. A regular polynomial with three real roots.
But the number of roots of other functions, such as y = -1.04 In x - 1.26 cos * + 0.0307 e* (8-2)
may not be obvious. A chart of the function is useful to show the number and approximate value of the roots of the function. The chart in Figure 8-2 shows that the function shown in equation 8-2 has two real roots.
- Figure 8-2. A function with two real roots.
|
A |
B | |
|
1 |
X |
Y |
|
15 |
1.4 |
-0.4396 |
|
16 |
1.5 |
-0.37322 |
|
17 |
1.6 |
-0.29995 |
|
18 |
1.7 |
-0.2214E |
|
19 |
1.8 j -0.1393! | |
|
21 |
1.9 -0.05493 2 0 0.030316 | |
|
22 |
2,1 |
0115193 |
|
23 |
2.2 |
0.198584 |
|
24 |
2.3 |
0.27949 |
|
25 |
2.4 |
0.35704! |
Figure 8-3. Portion of data table of x and y values showing the pair of values that bracket a root of the function shown in Figure 8-2. (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Graphical Method')
Figure 8-3. Portion of data table of x and y values showing the pair of values that bracket a root of the function shown in Figure 8-2. (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Graphical Method')
Once a chart has been created, it is very easy to expand the scales of the axes to examine the crossing region at higher and higher magnification. Figure 8-3 shows part of the data table used to create Figure 8-2; the formula in column B is the function shown in equation 8-1. The two values that bracket one of the roots of the function are highlighted.
- Figure 8-4. Expanded chart of a function, for graphical estimation of a root, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Graphical Method')
The expanded portion of the chart, shown in Figure 8-4, was created by selecting the four cells A20:B21, creating a chart and changing the x- and >>-axis scales. From the figure, one can estimate that the root that lies between x = 1.9 and x = 2.0 has the value 1.96446. This is probably adequate for most purposes. Remember to choose the Smoothed Lines option in the Chart Wizard.
The Interval-Halving or Bisection Method
This method and the one that follows make use of the fact that, as can be seen for example in Figure 8-3, a real root of a function lies between two adjacent x values for which y exhibits a change in sign. In order to obtain a root of a function by this method, you need to create a table of x values and the corresponding y values of the function, and identify two adjacent y values, one positive and the other negative. These and the corresponding x values will be the starting values for a binary search.
Once you have obtained the two starting x values, xt and x2, the midpoint of the interval between them, x3, is an approximation to the root. Now choose the pair of x values with opposite signs, either x\ and x3 or x2 and x3 and bisect the interval between them to get a further improvement. Repeat the process until a desired level of accuracy is attained. Figure 8-5 illustrates the application of this method, using equation 8-2. Only a portion of the table is shown; 34 rows were required to reach convergence at the IE-10 level, at which point x = 1.96445854473859.
|
A |
B |
C |
P. I | |
|
1 |
Interval-Halving Method | |||
|
2 |
X1 |
Y |
X2 |
Y |
|
3 |
5 |
2.525054 |
1 |
-0,59733 |
|
4 |
3 |
0.72146 |
1 |
-0.59733 |
|
5 |
2 |
0.030316 |
-0,59733 | |
|
6 |
1.5 |
-0.37322 |
2 |
0 030316 |
|
7 |
1,75 |
-0,18074 |
2 |
0.030316 |
|
6 |
1.875 |
-0.07615 |
2 |
0.030316 |
|
9 |
1.9375 |
-0.02299 |
2 |
0.030316 |
|
10 |
1.9G875 |
0.003661 |
1.9375 |
-0.02299 |
|
11 |
1.953125 |
-0.00967 |
1.96875 |
0.003661 |
|
12 |
1.9609375 |
-0.003 |
1.96875 |
0.003661 |
|
13 |
1.96484375 |
0.000329 |
1.9609375 |
-0.003 |
|
14 |
1.962890625 |
-0.00134 |
1.96484375 |
0.000329 |
|
15 |
1,9638671B8 |
-0.0005 |
1.96484375 |
0.000329 |
|
16 |
1.964355469 |
-8.8E-05 |
1.96404375 |
0.000329 |
|
17 |
1 964599609 |
0.00012 |
1.964355469 |
-8.8E-05 |
Figure 8-5. Using the binary search method to find a real root of a function, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Binary Search Method')
Figure 8-5. Using the binary search method to find a real root of a function, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Binary Search Method')
To construct the worksheet of Figure 8-5, the initial values x\ and x2 were entered in cells A3 and C3, respectively, and the formula for the function in cells B3 and D3. Next, the formulas that perform the binary search were entered in row 4; the formula in cell A4 calculates the midpoint value between the x values in the previous row
and the formula in cell C4 selects the y value that has the opposite sign to the value in the previous row.
Cells B4 and D4 contain the formula for the function. Finally, the formulas in A4:D4 were filled down into subsequent rows. Each row constitutes an iteration cycle; convergence was observed visually.
Although unsophisticated, this method will always find a root.
The Interval Method with Linear Interpolation (the Regula Falsi Method)
The interval-halving method can be made much more efficient in the following way. Instead of simply bisecting the difference between the two estimates of the root, you can obtain a better estimate of the root by using linear interpolation, as illustrated in Figure 8-6.
- Figure 8-6. The binary search method with linear interpolation (the Regula Falsi method)
The equation for linear interpolation is either
Again, two starting values of x must be obtained, for which the y values have opposite signs.
When applied to the same function as in the preceding example, this method converges efficiently to a root, as illustrated in Figure 8-7.
Again, cells A3 and C3 contain the initial values for xx and x2, respectively, and cells B3 and D3 contain the formula for the function. Cell A4 contains the linear interpolation formula:
and cell C4 contains the same formula as used in the previous example to select the y value that has the opposite sign to the value in the previous row:
|
A |
8 |
C |
D | |
|
2 |
Interval Method with Linear Interpolation X1 Yl X2 Y2 | |||
|
3 |
5 2.525054 1 |
-0.59733 | ||
|
5 |
1.765222575 1.967236444 |
-0.1682 0.00237 |
1.765222575 |
2.525054 -0.1582 |
|
e |
1.964429524 |
-2.5E-05 |
1.967235444 |
0.00237 0.00237 0.00237 -1.2E-15 |
|
7 6 9 |
1.964458545 1.964458545 1.964458545 |
-1.6E-10 -1.2E-15 0 |
1.967236444 1,967236444 1,964458545 | |
Figure 8-7. Using the Regula Falsi method to find a real root of a function, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Regula Falsi Method')
Figure 8-7. Using the Regula Falsi method to find a real root of a function, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Regula Falsi Method')
In general this method converges more efficiently to the root than does the binary search method, although unfavorable situations can occur, as illustrated in Figure 8-8. In this example, one end of the interval is "stuck," and even after 19 cycles of iteration, convergence has only reached the 1E-03 level.
|
A |
B |
c |
D | |
|
1 |
Slow convergence | |||
|
2 |
X1 |
Y1 |
X2 |
Y2 |
|
3 |
0 01000 |
3.560449 |
1 |
-0.59733 |
|
4 |
0.85777 |
-0.59226 |
0.01 |
3.560449 |
|
5 |
0.73686 |
-0.55142 |
0.01 |
3.560449 |
|
6 |
0.63939 |
-0.48778 |
001 |
3.560449 |
|
7 |
0.56355 |
-0.41478 |
001 |
3.560449 |
|
8 |
0 50579 |
-0.34243 |
001 |
3.560449 |
|
9 |
0.46229 |
-0.27658 |
001 |
3.560449 |
|
10 |
0.42969 |
-0.2198 |
0.01 |
3.560449 |
|
11 |
0.40529 |
-0.1726 |
0.01 |
3.560449 |
|
12 |
0.38701 |
-0.13433 |
0.01 |
3.560449 |
|
13 |
0.37330 |
-0.10385 |
0.01 |
3.560449 |
|
14 |
0.36301 |
-0.07989 |
0.01 |
3.560449 |
|
15 |
0.35526 |
-0.06123 |
0.01 |
3 560449 |
|
16 |
0.34942 |
-0.04679 |
0.01 |
3.580449 |
|
17 |
0.34502 |
-0.03568 |
0.01 |
3.560449 |
|
18 |
0.34170 |
-0.02717 |
0.01 |
3.560449 |
|
19 |
0.33919 |
-0.02066 |
0.01 |
3.560449 |
|
20 |
0.33729 |
-0 0157 |
0.01 |
3 560449 |
|
21 |
0.33585 |
-0 01192 |
0.01 |
3.560449 |
|
22 |
0.33476 |
-0.00904 |
0.01 |
3.560449! |
Figure 8-8. A case with slow convergence of the Regula Falsi method, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Regula Falsi (2)')
Figure 8-8. A case with slow convergence of the Regula Falsi method, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Regula Falsi (2)')
The Regula Falsi Method with Correction for Slow Convergence
The preceding example shows that an unlucky choice of starting values can lead to slow convergence. By examination of the example in Figure 8-7, it can be seen that the ideal situation for rapid convergence occurs when, in almost every cycle, there is a change in the value of both x\ and x2, y\ and y2 or in the sign ofj>i or y2. Any one of these can be used to test for slow convergence.
The slow-convergence situation in Figure 8-8 was remedied by changing the interpolation calculation so that if the value of x2 does not change from one cycle to the next, the value of y2 used in the interpolation is halved. The performance of the modified formula is illustrated in Figure 8-9. The only change is the formula in cell D4
=IF(C4=C3,D3/2,-1,04*LN(C4)-1,26*COS(C4)+0.0307*EXP(C4))
This formula divides the value of y2 by 2 if there has been no change in x2 in the preceding two iteration cycles (this has occurred in rows 5, 6 and 7, for example). Otherwise the function is calculated by means of the usual formula.
A nested IF could be used to handle the case where either xi orjc2 is "stuck."
Post a comment