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."

0 0

Post a comment