www.vandenberg.info

Root Finding

Search Algorithms

Suppose you have the following equation and are asked to solve it for X. You could solve it analytically by using algebra and probably is the best way for this equation. But if the equation was significantly more complicated it might not be.

79 = 10 + 12X

Equation 1

But suppose you have the following equation to solve. Now it becomes more difficult to do it analytically

-985 =

75

(1+ X)1

+

120

(1+ X)2

+

100

(1+ X)3

+

1200

(1+ X)4

Equation 2

This X would be called the internal rate of return in finance. HIRR returns such a value assuming the half year convention. The built in IRR function returns X without assuming the half year convention.

In order to solve these types or equations a numerical technique is frequently used. It involves guessing at the answer and then seeing how wrong the answer is and guessing again until you find the right answer. There are a variety of techniques that you can use to improve the guess so that they are not just random.

One technique is called the binary search. All techniques start with a value, the solution is sometimes dependent on the starting value, but in many cases it is not. To solve Equation 1 let try a first guess that X is 1. Unless we are lucky we need to compute the error and then correct our guess and try again.

Strategy Double the last guess until we go over

Guess:

Guess:

Guess:

Guess:

X = 1

X = 2

X = 4

X = 8

Equation

=10 + 12*(1)

=10 + 12*(2)

=10 + 12*(4)

=10 + 12*(8)

=

Computed

22

34

58

106

Needed Answer

79

79

79

79

'We now know that answer for X lies between and 4 and 8. The average is:

Strategy guess middle until we get an acceptable solution

Guess:

X = 6

Equation

=10 + 12*(6)

=

Computed

82

Needed Answer

79

'We now know that answer for X lies between and 4 and 6. The average is:

Guess:

X = 5

=10 + 12*(5)

=

70

79

'We now know that answer for X lies between and 5 and 6. The average is:

Guess:

X = 5.5

=10+ 12*(5.5)

=

76

79

'We now know that answer for X lies between and 5.5 and 6. The average is:

Guess:

X = 5.75

=10+ 12*(5.75)

We now know the answer is 5.75

=

79

79

Error = Needed - Computed

57

45

21

-27

6

Error = Needed - Computed

-3

5

9

5.5

3

5.75

0

In fact once you have the answer bracketed you can hone in very fast. Suppose you know the number you are guessing is whole and is between 1 and 128. After each guess you will be told whether you are high or low. How many guess will it take? ( Answer is only 7, or less--you might get lucky.) Why? Because 27 is 128. Your first guess should be 64. Then if you are high, guess 32 or low guess 96. Etc.

Spreadsheets have these routines installed. There are two versions in Excel one is called Goal Seek and the other is called Solver. Solver is much more powerful. But even with its power it won't always find an answer. Or it may not find an answer if you don't give a good place to start looking.

Sometimes the guess does not go quite so well. Particularly if you have a complex equation. Or the equation is peculiar. Try to find the answer to the following equation: (a value of X that makes the equation true.)

0 = 10X2 + 5X + 50

Good Luck

Therefore the BSVOPM and HIRR function might not always find an answer. Since it is a numerical routine and will have problems sometimes in getting an answer.

[FinPak] [Getting FinPak] [Installation] [Help] [Fin Functions] [Simulation] [The Greeks] [Array Functions] [Root Finding]

Copyright 2009 Pieter A. Vandenberg All rights reserved.