A B j jDJ

1 Modified formula improves convergence

2

X1

Y1

X2

Y2

3

D.01000

3.560449

1

-0.59733

4

0.85777

-0.59226

0.01

3.560449

5

0.73686

-0.55142

0.01

1.780224

. g

Q. 56496

-0.41636

0.01

0.890112

7

0.38810

-0.13669

0.01

0.445056

6

0.29926

0.092106

0.3881

-0.13669

9

0.33503

-0.00974

0^29926

0.092106

to

0.33161

-0.00G62

0 29926

0.046053

11

□.33117

0000538

0.33161

-6E-04

12

0 33137

-2.5E-07

0.33117

5E-04

13

0 33137

-9.9E-11

0.33117

3E-04

14

0.33137

9.93E-11

0.33137

-1E-10

15

0.33137

-1.9E-15

0.33137

1E-10

Figure 8-9. Modifying the Regula Falsi method to handle slow convergence, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Regula Falsi (3)')

Figure 8-9. Modifying the Regula Falsi method to handle slow convergence, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Regula Falsi (3)')

The Newton-Raphson Method

The preceding methods require manual selection of a pair of starting values with opposite signs. The Newton-Raphson method (sometimes referred to simply as Newton's method) requires only a single function value as the starting value, and is therefore self-starting. The Newton-Raphson method is a classic exercise from freshman calculus—it uses the first derivative of the function (the slope of the curve) at the initial estimate, jti, and extrapolates this tangent line to the x axis to obtain an improved value, x2. The process is repeated to obtain further approximations to the root, as illustrated in Figure 8-10, until the desired convergence level is reached.

Figure 8-10. The Newton-Raphson method for obtaining a root of a function.

The slope of the curve at x\ is the first derivative of the function, dy/dx. The improved estimate can be calculated by rearranging the expression for the slope, m = (y2 -y{)l(x2-x\), and settings = 0. This results in the equation x2 = (mxi -yi)/m (8-5)

In pencil-and-paper calculations the slope would be obtained by calculating the first derivative using calculus, but in spreadsheet calculations you can use numerical differentiation (see Chapter 6, "Differentiation"). Increase x by a small amount Ax, which increases the y value by a small amount Ay. If you make Ax small enough, Ay /Ax will be a good approximation to the first derivative dy/dx. In the following example, x + Ax was obtained by multiplying x by 1.00000001. (See "The Newton Quotient" in Chapter 6.)

The calculations of the Newton-Raphson method are illustrated in Figure 811. The function for which a root is sought is the regular polynomial y = 3x3 + 2.5x2 - 5x - 11 (8-7)

A

B

C

Ë i

F

G. . J_ H J

1

Newton-Raphson Method

2

delta «

1 .O0E-08

3

H1

Y1

X2

Y2

m

new X1

4

5

401,5

5.0O0Q000S

401.50001

245

3.36122451 -i ;

5

I

6

I

3.36122451

114.36208

3.36122454

114.36209

113.48659

2.35351003

7

2.35351003

30.188317

2,35351005

30.188318

56.618838

1.82032311

a

1.82032311

6.277663

1.82032313

6.2776637

33,923802

1.63527123

9

1.63527123

0.6276192

1.63527125

0.6276196

27,243364

1.61223373

10

1.61223373

0.0091011

1.61223374

0.0091015

26.454847

1.6118S970

11

1.61168970

2.G13E-06

1.61188972

2.439E-06

28.443144

1.61188983

12

1.61188963

1 068E-13

1.61186964

4.262E-07

26.443142

1 6118B963

Figure 8-11. Calculation of a root of a function by the Newton-Raphson method. The formulas in row 6 were filled down until convergence was observed, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet "Newton-Raphson Method')

Figure 8-11. Calculation of a root of a function by the Newton-Raphson method. The formulas in row 6 were filled down until convergence was observed, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet "Newton-Raphson Method')

The starting value, in this case 5, was entered in cell B4. The formulas in cells C4, D4, E4, F4 and G4 are, respectively,

D4: =B4+0.0000001 *B4 (increment x by a small amount Ax)

Then the formula =G4 was entered in cell B6, so as to use the improved x value as the starting value in the next row (row 5 was left empty for purposes of illustration only). The formulas in C4:G4 were copied and pasted into the corresponding cells in row 6. Finally, the formulas in cells B6:G6 were Filled Down into succeeding rows until convergence was observed in column G or a sufficiently small value of^ was obtained in column C.

Using Goal Seek...

Excel provides a built-in way to find a real root of a function. The Goal Seek... command in the Tools menu can be used to perform what is sometimes called "backsolving"; that is, it varies x in order to make y reach a specified value. Thus you can use Goal Seek... to find a value of x that makes the value of the function y become zero, or at least very close to zero. The computer code that performs the Goal Seek function probably involves the Newton-Raphson method.

As an example to illustrate the use of Goal Seek..., we'll return to the cubic equation 8-1, .y = jc3 + 0.13;c2 - 0.0005.x - 0.0009. Figure 8-12 shows a part of the data table that was used to produce the chart shown in Figure 8-1.

A

B

3

X

Y

4

-0.15

-4.65E-04 |

5

-0.14

-2.16E-04

6

-0.13

-2.50E-05

7

-0.12

1.14E-04 i

8

-0.11

2.07E-04

9

-0.10

2.60E-04

Figure 8-12. Part of a data table, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Using Goal Seek')

Figure 8-12. Part of a data table, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Using Goal Seek')

It can be seen that one of the roots of this function must lie between x = -0.13 and x = -0.12, since there is a change in sign of the function somewhere in this interval. To use Goal Seek..., enter a trial value of x in a cell and the function in another cell, as illustrated in Figure 8-13. The cell containing the value of x is referred to as the changing cell, the cell containing the function as the target cell or the objective.

A j

B |

Changing

Target

26

cell

cell

27

-0.2

-2.79E-03

Figure 8-13. Target Cell and Changing Cell for Goal Seek.

(folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Using Goal Seek')

Figure 8-13. Target Cell and Changing Cell for Goal Seek.

(folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Using Goal Seek')

Now choose Goal Seek... from the Tools menu to display the Goal Seek dialog box (Figure 8-14). (Although not necessary, it's convenient to select the target cell before beginning.)

* According to Microsoft, "Goal Seek uses an iterative process in which the source cell is incremented or decremented at varying rates until the target value is reached."

Enter a reference to the target cell in the Set Cell box (the cell reference will appear there if you selected that cell before choosing Goal Seek...). Enter 0 in the To Value box and a reference to the changing cell in the By Changing Cell box, and press OK.

set cell: To value: By changing cell:

Cancel

Figure 8-14. The Goal Seek dialog box.

After a few iteration cycles the Goal Seek Status dialog box (Figure 8-15) will be displayed. When you press OK the final values of the changing cell and target cell will be displayed in the worksheet cells, as shown in Figure 8-16.

I Goal Seek Status

Goal Seeking with Cell B27

[ OK

found a solution.

Target value; 0

Cancel

Current value: -1.66E-18

Step

Pause j

Figure 8-15. The Goal Seek Status dialog box.

A 1

B______j

Changing

Target

26

eel!

cell

„27"j

-0 1284371

-1.86E-18 ;

Figure 8-16. Obtaining a root of a function by using Goal Seek, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Using Goal Seek')

Figure 8-16. Obtaining a root of a function by using Goal Seek, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Using Goal Seek')

For scientific and engineering problems, it's critical that you set the convergence limit (the stopping parameter) of Goal Seek to suit your problem. Choose Options... from the Tools menu and choose the Calculation tab (see

Figure 8-17). The Maximum Change parameter sets the convergence limit; when the value of the target cell becomes less than this value, iteration ceases. The default value for Maximum Change is 0.001, which is suitable for this problem, but will not be suitable for many other problems. For a problem where the magnitude of the result (the changing cell value) is a very small number, you can set Maximum Change to a value such as IE-15. Alternatively, you can set it to zero, which will usually result in Goal Seek completing 100 iteration cycles before quitting.

Color | Internationa! ) Save j Error Checking j Spelling ] Security View Calculation j Edit ] General | Transition j Custom lists | Chart

Calculation-------------— ■■■■——------------

i* Automatic C Manual

C Automatic except tables F Reoalo ilab? befote ave

Cale Now (F9) j Cale Sheet r Iteration

Maximum iterations: [150 Maximum change: jle-15|

Workbook options-

P Update remote references f? Save externa! [ink values f P^cison as displayed P Accept labels in formulas r 1904 date system

OK I Cancel

Figure 8-17. The Calculation Options dialog box.

Since Goal Seek... almost certainly uses something like the Newton-Raphson method to find a root, it should be clear from Figure 8-1 that the trial value that you use will determine the root that is found. The cubic equation that we used in our example, shown in Figure 8-1, has three real roots. It is clear that if 0.01 is used as initial estimate, the largest of the three roots will be calculated, while using -0.2 as an initial estimate will result in the smallest of the three roots. Thus, to obtain a particular root, some guidance must be provided by the user.

Figure 8-18 illustrates the three roots of the function obtained by using different initial estimates.

Starting Value

Root Found

0.01

0,025701

-0.20

-0.128437

-0.01

-0.027264

Figure 8-18. Different starting values lead to different roots, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Using Goal Seek')

Figure 8-18. Different starting values lead to different roots, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Using Goal Seek')

The Secant Method

The secant method is similar to the Newton-Raphson method, except that it is not necessary to calculate the slope of the curve. Instead, the slope is approximated by using two values of x, as illustrated in Figure 8-19. Although this may be a poor approximation to the tangent to the curve, it becomes more and more accurate as the iterations approach the root. This method is not self-starting, since values of the function at two adjacent x values must be provided to begin the calculation. The calculations are illustrated in Figure 8-20, applied to the function shown in equation 8-1.

Figure 8-19. The secant method for obtaining a root of a function.

A

B I C | D i E i F |

X1 Y1 X2 Y2 m newX2

4

5 4.9

2.5251 4.9 2,2349 2,2349 4.1297963 1.1268

2.90168 1.43875

4,129796266 3.346645771

5

4.1297963

1 1268 3.3466450 i 0.3494

0.35412

0.947915289

6

3.3466458

0 8494 0.94791531 -0.6002

0.60434

1.941087368

7

0.9479153

-0.6002 1,9410874] -0.0199

0.58426

1.975206929

8

1.9410874

-0.0199 1.9752069] 0.0092

0.85302

1,964457031

9

1.9752069

0.0092 1.964457 0.0000

0 85314

1 964458545

10 fii

1.9644570 1.9644585

0.0000 1.9644585 0.0000 0.0000 1.9644585 0.0000

0.85314 0.85313

1.964458545 1.964458545

Figure 8-20. Using the secant method to obtain a root of a function, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Secant Method')

Figure 8-20. Using the secant method to obtain a root of a function, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Secant Method')

The formulas in row 3 are identical to those in Figure 8-10, except that cell C3 contains a value rather than a formula.

The Newton-Raphson Method Using Circular Reference and Iteration

The Newton-Raphson method discussed in a previous section requires the user to fill down formulas until convergence is observed visually. One can create a Newton-Raphson calculation that runs automatically by using an intentional circular reference.

A circular reference is created when a formula refers to itself, either directly or indirectly. If a circular reference occurs, Excel issues a "Cannot resolve circular references" message and displays a zero value in the cell. Usually, circular references occur because the user entered an incorrect cell reference in an equation. But occasionally a problem can be solved by intentionally creating a circular reference.

The calculation is illustrated in Figure 8-21. A single change was made to the worksheet in Figure 8-11. After entering the formulas in row 4, the initial value 5 in cell B4 was replaced by the formula =G4. In this way the improved estimate of x was entered as the start value of the process.

A

B j C i D

E

F

G

±u

1 2 3

Newton-Raphson Method with Circular Reference delta = 1E-08

X1 Y1 X2 Y2 in newX1

5 "

5 4015 5.00000005

401.5

245.0000

3,36122451

Figure 8-21. Calculation of a root of a function by the Newton-Raphson method (before creating intentional circular reference), (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet "Newton-Raphson circular')

Figure 8-21. Calculation of a root of a function by the Newton-Raphson method (before creating intentional circular reference), (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet "Newton-Raphson circular')

When you press ENTER after typing the formula in cell G4, the "Cannot resolve circular references" message is displayed, and Excel displays a zero in the cell to indicate a circular reference, as shown in Figure 8-22.

A

B

I C

D

E F

G lH

1

Newton-Raphson Method with Circular Reference

2

delta =

1E-08

3

X1

Y1

X2

Y2 m

newX1

4

r

0

401.5

5,00000005

401.5 245.0000

3.36122451 -,

5

I

Figure 8-22. Creating an intentional circular reference, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet "Newton-Raphson circular')

Figure 8-22. Creating an intentional circular reference, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet "Newton-Raphson circular')

To force Excel to evaluate the circular reference, using the results of the previous calculation cycle as start values for the next cycle, choose Options... from the Tools menu and choose the Calculation tab. Check the Iteration box and enter 0 in the Maximum Change box. (The default settings are Maximum Iterations = 100 and Maximum Change = 0.001.) When you press the OK button the circular reference will be evaluated. The results of the calculations are shown in Figure 8-23.

1 Newton-Raphson method with Circular Reference

31 XI Y1 X2 Y2 m newX1

4" 1.61188963 0 1.61188964 4.3E-07 26 4431 1.61 1389634 i

Figure 8-23. Finding a root by the Newton-Raphson method and circular reference, (folder 'Chapter 08 Examples', workbook 'Roots of Equations', worksheet 'Newton-Raphson circular')

A Newton-Raphson Custom Function

The Newton-Raphson method can also be used in the form of a custom function. The VBA code is shown in Figure 8-24.

Option Explicit

Function NewtRaph(expression, variable, Optional initial_value) 'Finds a root of a function by Newton-Raphson method. 'Expression must be a reference to a cell containing a formula. 'Variable must be a cell reference (cannot be a name). 'Initial_value can be a number, reference or omitted. 'Reference style can be either A1-style or R1C1-style.

Dim FormulaString As String, XRef As String Dim delta_x As Double, tolerance As Double Dim X1 As Double, X2 As Double, X3 As Double Dim Y1 As Double, Y2 As Double Dim m As Double

Dim I As Integer, J As Integer, NRepI As Integer Dim temp As String, T As String, dummy As String

FormulaString = expression.Formula If Left(FormulaString, 1) <> "=" _

Then NewtRaph = CVErr(xlErrNA): Exit Function XRef = variable.Address

'Convert all references to absolute

'so that only text that is a reference will be replaced.

FormulaString = Applicatlon.ConvertFormula(FormulaString, xlA1, xlA1, xIAbsolute)

'Handle initial values that cause problems If lsMissing(initial_value) Then initial_value = variable If initial_value = "" Then initial_value = variable

'Set delta_x for numerical differentiation, stopping tolerance delta_x = 0.00000001 tolerance = 0.0000000001

'Perform the Newton-Raphson procedure X1 = initial_value

For I = 1 To 100 '100 iterations maximum T = FormulaString 'Start with original formula each time thru loop 'Do substitution of all instances of x reference with value. 'Substitute reference, e.g., $A$2, 'with a number value, e.g., 0.2, followed by a space 'so that $A$25 becomes 0.2 5, which results in an error. NRepI = (Len(T) - Len(Application.Substitute(T, XRef, ""))) I Len(XRef) For J = NRepI To 1 Step -1 | temp = Application.Substitute^, XRef, X1 & " ", J)_

If lsError(Evaluate(temp)) Then GoTo pt1 T = temp pt1: Next J Y1 = Evaluate(T)

T = FormulaString 'Begin with original formula again. If X1 = 0 Then X1 =delta_x X2 = X1 + X1 * delta_x For J = NRepI To 1 Step -1 temp = Application.Substituted, XRef, X2 & " ", J) If lsError(Evaluate(temp)) Then GoTo pt2 T = temp pt2: Next J Y2 = Evaluate(T) m = (Y2-Y1)/(X1 * delta_x) X3 = X1 - Y1 I m 'Exit here if a root is found

If Abs(X3 - X1) < tolerance Then NewtRaph = X3: Exit Function X1 = X3 Next I

'Exit here with error value if no root found NewtRaph = CVErr(xlErrNA)

End Function_

Figure 8-24. VBA code for the Newton-Raphson custom function, (folder 'Chapter 08 Examples', workbook 'Newton-Raphson Function', module 'Module 1')

The syntax of the custom function is NewtRaph(express/on, variable, initial_value)

Expression is a reference to a cell that contains the formula of the function, Variable is the cell reference of the argument to be varied (the x value of F(x) or Goal Seek's changing cell) and initial_value is an optional argument that can be used to determine which root will be found.

To illustrate the use of the custom function, we will use it to find a root of the cubic equation y= -2x + 16x + 6Ox -300. A chart of the function is shown in Figure 8-25. A portion of the data table to generate the chart is shown in columns A and B of Figure 8-26. The formula in cell B7 is

=aa*A7A3+bb*A7A2+cc*A7+dd where aa, bb, cc and dd are the coefficients of the cubic.

Figure 8-25. Root of a function returned by the Newton-Raphson custom function, (folder 'Chapter 08 Examples', workbook 'Newton-Raphson Function', sheet 'Newton-Raphson')

To use the custom function, enter the function in cell C7 by typing it following the syntax above, or choose Insert->Function..., choose the User Defined category and choose the function from the list box. For the expression argument, enter a reference to a cell containing the worksheet function (e.g., cell B7 in Figure 8-26). For the variable argument, enter A7, the cell reference of the independent variable in the formula expression. If you do not enter a value for the optional initial_value argument, the value of the independent variable will be used as the starting value. When you press ENTER, a root of the function is returned, as shown in Figure 8-26.

A

J_B_____

C

D

4

X

V

root

trial value

5

-7

750

-4.79212051203765

-100

6

-6

348

3.29634999529599

0

7

-5

50

9.49577051674166

100

j:

-4

-156

-4.79212051203764

Figure 8-26. Root of a function returned by the Newton-Raphson custom function, (folder 'Chapter 08 Examples', workbook 'Newton-Raphson Function', sheet 'Newton-Raphson')

Figure 8-26. Root of a function returned by the Newton-Raphson custom function, (folder 'Chapter 08 Examples', workbook 'Newton-Raphson Function', sheet 'Newton-Raphson')

The root that is returned depends on the initial or trial value used by the Newton-Raphson procedure. In this example, if a relatively large negative value is used (e.g., -7), the root near -5 will be obtained. (See Figure 8-10 if this is not clear.) Some caution must be exercised in choosing a trial value to direct the procedure towards a particular root, as illustrated by the results for the same polynomial shown in Figure 8-27.

A

B

I ■ . 0 .______I

4

x

y

root

17

3,29634999529599

18

-479212051203765

19

9.49577051674166

Figure 8-27. The root that is returned can be very sensitive to the choice of trial value, (folder 'Chapter 08 Examples', workbook 'Newton-Raphson Function', sheet 'Newton-Raphson')

Figure 8-27. The root that is returned can be very sensitive to the choice of trial value, (folder 'Chapter 08 Examples', workbook 'Newton-Raphson Function', sheet 'Newton-Raphson')

If no root is found after 100 cycles of iteration, the function returns the #N/A error value.

The advantage of this custom function compared to Goal Seek... is, of course, that if the coefficients aa, bb, cc, or dd are changed, the value of the root is automatically updated.

Was this article helpful?

0 0

Post a comment