Nash - Scientific Computing with PCs (523165), страница 42
Текст из файла (страница 42)
This13: PROBLEM FORMULATION119should be a part of any ODE package. We recommend graphing the solutions. As with quadrature, wewill want to learn as much as possible about the problem. Partial differential equations and integrodifferential equations bring additional difficulties, and we have too little direct experience of these tocomment on their solution or its testing.QuadratureThe most difficult aspect of quadrature is that there may be singularities or other irregularities in thefunction that pass undetected at the evaluation points of the function.
Comparison of several quadraturemethods may be a partial aid, but the best approach is to learn as much as possible about the problemand its solution. Symbolic integration tools let us carry out parts of the problem analytically.Function minimizationRestart(s) of the minimization process at random points near the supposed minimum allow for possibledetection of a false convergence. Furthermore, it is possible to compute the approximate curvature of thesurface to verify the minimum conditions on the gradient and Hessian (second derivative matrix).13.7 Using Known Techniques on Unknown ProblemsSometimes, the world presents a computational problem for which no adequate method exists.
The PCpractitioner must then be inventive and devise some way to approximate a solution. This is the way inwhich all existing methods were devised.First, it is worth some effort to write down all the conditions (as in Section 13.1) and pose the possiblesolvable problems that arise as one or more conditions are relaxed. One can then "try it and see" orattempt some forcing mechanism or transformation that ensures the relaxed condition is met. Second,graphical or handwaving "solutions" may be used as models leading to a mix or extension of existingmethods.
Third, many mathematical problems are solvable in terms of some minimum principle, so thata function minimization program may be a route to a crude solution. Fourth, simulation techniques mayprovide a mechanism to explore aspects of the problem.Only when all else fails should one consider developing a new technique.
In such cases, a very thoroughsearch should be made to determine if someone else has already considered the problem.Previous Home Next120Copyright © 1984, 1994 J C & M M NashNash Information Services Inc., 1975 Bel Air Drive, Ottawa, ON K2C 0X1 CanadaSCIENTIFIC COMPUTING WITH PCsCopy for:Dr. Dobb’s JournalPart IV: ExamplesThe next four chapters present examples to illustrate the ideas we have been developingso far.
We follow these examples with a timing study showing how minor differencesin program code may alter running time and other program characteristics, underliningour recommendation to time and test programs. We conclude our illustrations with acase study in the use of graphical tools for analyzing program performance.
Thisachieves two goals — we illustrate how to analyze performance while demonstratingsome graphical tools to assist in the analysis.Chapter 14The Internal Rate of Return Problem14.114.214.314.414.514.6Problem statementFormulationsMethods and AlgorithmsPrograms or PackagesSome solutionsAssessmentThis chapter presents the internal rate of return (IRR) problem as a case study of problem formulation andsolution.14.1 Problem StatementA common calculation to help measure the value of investments is the internal rate of return. While notdirectly a scientific computation, it illustrates many characteristics of computational problems but haseasily understood origins.
We invest various amounts I(t) in different time periods t= 0, 1, 2, . . . ,nand these investments (or costs) return revenues R(t) in the corresponding time periods. The net revenuein each period is then(14.1.1)N(t) = R(t) - I(t)fort = 0,1,2, . . . ,n.The "zero’th" period allows for initial investments. The net value of the investment is the sum of the netrevenues, but to take account of the time value of money, we discount each net revenue appropriately.The later the net revenue is received, the less it is worth. Given a discount rate r, we create Table 14.1.1.14: EXAMPLE: INTERNAL RATE OF RETURN PROBLEM121Table 14.1.1Schematic layout of costs and revenues for the internal rate of return problem.PeriodInvestmentRevenueNet RevenueDiscounted0I(0)R(0)N(0)=R(0)-I(0)N(0)1I(1)R(1)N(1)=R(1)-I(1)N(1)/(1+r)2I(2)R(2)N(2)=R(2)-I(2)N(2)/(1+r)2tI(t)R(t)N(t)=R(t)-I(t)N(t)/(1+r)(t-1)The sum of the discounted net revenues, or cash flows, is called the net present value (NPV) of theinvestment at the beginning of the investment sequence.
The IRR is the value of r such that this NPV iszero. This rate can be compared with interest rates offered by other investments. Uncertainties imply thathigh precision is not needed in our calculation.14.2 FormulationsThe mathematical formulation of the IRR problem is:Find the discount rate, r, such that the NPV of the revenue stream(14.2.1)Letting(14.2.2)NPV(r) = 0 =( R(t)-I(t) ) / (1+r)N(t), t=0, 1, 2, . . . , n is zero.t1/(1+r) = x, we have(R(t)-I(t)) xt=N(t) xt= 0This is the polynomial root finding problem, since the last summation simply defines a polynomial. Apolynomial with n coefficients N(t) is said to be of degree (n-1) and has (n-1) roots. Not all the rootsof the polynomial need to be real; complex-conjugate pairs are possible.
However, the answers for the rateof return must be real. We don’t have imaginary deposit rates! It is useful in some approaches to multiplyn(14.1.3) by (1+r) ,(14.2.3)N(t) (1+r)(n-t)= 0The problem can be simplified if we look for just one root between reasonable limits. Clearly a NPV thatis negative when r=0 means that the investment is a poor one. It is losing money even when there is no"interest" on the investment. So r=0 may be chosen as a lower limit to the root. A 50% return per annum(r=0.5) is generally considered extremely good, so would be a reasonable upper limit. If the return is lessthan 50%, then NPV(0.5) should be negative — revenues late in the sequence of cash flows don’t countas much.
However, it is possible that there are multiple roots that arise to confuse the whole situation.It is wise to calculate and plot the NPV for several likely values of r. This gives us a picture of the NPVat various discount rates and errors in a purely automatic solution. Such graphical checks of calculationsshould always be performed if possible.122Copyright © 1984, 1994 J C & M M NashSCIENTIFIC COMPUTING WITH PCsNash Information Services Inc., 1975 Bel Air Drive, Ottawa, ON K2C 0X1 CanadaCopy for:Dr. Dobb’s JournalWe can perform tests other than a plot of the function.
A positive return on the investment, meansNPV(0) > 0, as mentioned. If we are to have just one root, NPV to decline with increasing r, so the firstderivative of NPV(r) with respect to r should be negative at r=0. This is easily calculated. We use thechain rule to find:(14.2.4)d NPV(r) / dr = -N(t) t / (1+r)(t+1)For illustrative purposes, we will use two sets of cash flows. Figure 14.2.1a presents a straightforwardproblem; data in Figure 14.2.1b includes some of the potentially tricky features mentioned above.As suggested in Chapters 12 and 13, we have formulated our problem in two main ways, and have listedsome side conditions on the problem and some reality checks for suggested solutions.
Our twoformulations are:•Find all the roots of a polynomial and select the one that is appropriate;•Search for just one root in a restricted range with tests on the applicability of the search.Figure 14.2.1 Two cash flow streams for the IRR problem;a. a straightforward problem,b. a problem with multiple roots.Problem IRR2A -a straightforward problem witha simple root (discount rate)Period======01234567Invest======6000002000000Revenue=======030025060000455666Cash Flow=========-600300250600-20000455666IRR3 -problem withmultiple rootsPeriod======01234567Cash Flow=========-64000275200-299520-18969641913641376-218528-2305614.3 Methods and algorithmsThe main formulations suggest that we need either•A method for finding all the roots (or zeros) of a polynomial, or•A general root-finding technique for one root in a specified interval.Both methods can be found in the literature.
Many methods exist for the polynomial roots problem. SeeRalston, 1965, Chapter 8 for a historical overview. Unfortunately, most methods have weaknesses, and fewwill compute all the roots. The method of Jenkins and Traub (Jenkins, 1975) is considered by manyworkers to be definitive. An alternative approach is to compute the eigenvalues of the companion matrixof the polynomial (Mathworks, 1992, p. 394ff).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
