Nash - Scientific Computing with PCs (523165), страница 40
Текст из файла (страница 40)
See, forexample, Watts and Penner (1991). It is important to obtain a statement of the original problem along withits context rather than the processed (and altered) problem sometimes presented. The original problemwith its possibly critical side conditions allows us the maximum range of formulations.A proper mathematical formulation may allow us to decompose the mathematical problem.Decomposition is a practical and important principle in the solution of mathematical problems.
Each subproblem is in some way "smaller" and more likely to be solvable with more limited computationalresources. We can use known techniques on these partial problems and verify our progress at every stage.Good formulations allow general methods to be applied to problems. This may sacrifice machine time tohuman convenience, and fail to give an acceptable solution, but the nature of the problem may be betterrevealed. Applying a general function minimizing program to a linear least squares problem can indicatethe shape of the sum of squares surface.A hindrance to progress may be the traditional or historical approaches taken to solve problems. We havecome to regard some "usual" methods that are popular in many scientific fields as confirming Nash’saxiom:The user (almost) always chooses the least stable mathematical formulation for his problem.Several examples spring to mind. The use of the determinant of a matrix via Cramer’s Rule is rarely thecorrect approach to solving linear equations.
The roots of a polynomial resulting from secular equations114Copyright © 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 Journalgenerally lead to unstable methods for finding parameters in orbit or structural vibration problems. In fact,the original eigenproblem is usually more stable; good methods for polynomial roots use eigenproblemideas. Similarly, general rootfinding methods applied over a restricted range work more efficiently for theinternal rate of return problem (Chapter 14) than polynomial rootfinders. Newton’s method, the basis formany methods for solving nonlinear equations and minimizing functions, often does not work welldirectly. In our experience, better progress is usually possible using the ideas within a differentframework, for example, quasi-Newton, truncated Newton and conjugate gradient methods.
Similarly, thesteepest descents method for minimization, despite its name, is slow.13.2 Mathematical versus Real-World ProblemsPerhaps the toughest part of any problem solving job is deciding what kind of mathematical problem bestfits the real world problem. This part of the job is often mired in the mud of tradition and unoriginalthinking.Consider econometric modelling. Despite the obvious flaws that observations on all the variables are tosome extent in error, that there may be a systematic bias in figures that is much larger than randomfluctuations and that occasional deviations from the true values may be extreme, econometricians continueto use ordinary least squares (OLS) estimation as a primary work-horse of their trade.
There is nounchallengeable reason why the square of the error (L2 loss function) should be more suitable than theabsolute value (L1) or even the minimum maximum error (L-infinity). However, OLS and its extensionsfor the simultaneous estimation of several equations (Johnson, 1972) do provide measures of precision ofthe estimates if one is prepared to believe that a set of fairly strong assumptions are obeyed.The least squares criterion and its relations result in mathematical problems that can be solved by linearalgebraic tools such as matrix decompositions.
The L1 and L-infinity criteria, however, result inmathematical programming problems that are, in general, tedious to set up and solve, particularly on aPC. While derivative-free function minimization methods such as the Nelder-Mead polytope (or Simplex)method (Nash J C 1990d, Algorithm 20) or the Hooke and Jeeves Pattern Search (Nash J C 1982c; NashJ C 1990d, Algorithm 27; Kowalik and Osborne, 1968) could be used, they are not recommended for morethan a few parameters and may be extremely slow to converge for such econometric problems. Worse,they may not converge at all to correct solutions (Torczon, 1991).
The choice of model of the real worldin these econometric problems is driven, at least in part, by the availability of methods to solve themathematical problem representing the real world.Mathematical representations of real problems may have solutions that are not solutions to the realproblem. A simple example is finding the length of the side of a square whose surface area is 100 squarecentimeters. Clearly the answer is 10 cm. But the mathematical problem(13.2.1)S2 = 100has solutions S = +10 and S = -10. A length of -10 cm.
has no reality for us. Here the task of discardingsuch artifacts of the representation is obvious, but in complicated problems it may be difficult todistinguish the desired solution from the inadmissible ones.The point of this section is that we should remain aware of the different possibilities for mathematicallyformulating real-world problems. Traditional formulations may be the most suitable, but there are alwaysoccasions when a new approach is useful (Mangel, 1982).13.3 Using a Standard ApproachProper formulation of our problem permits us to take advantage of work already reported by others.
Wecan use known methods for which the properties are (hopefully) well understood. These "known" methods13: PROBLEM FORMULATION115may, unfortunately, not be familiar to us. We must find them, and they must be usable on our particularcomputing environment. Useful pieces of software may not be indexed or listed under the headings usersexpect.
Correct formulation helps the creator of software provide index keywords for which users arelikely to search.To find "known" methods, we can try several routes. First, we may have a very good idea of thetraditional solution methods, especially if the problem is a common one in our field of work. There willbe textbooks, review articles, and computer programs or packages already available for the task.
Thesemay or may not be suitable to our particular problem and computing environment, but for all their faultsand weaknesses, methods that are widely used carry with them the benefit of the accumulated experienceof their users. In particular, methods and computer programs in widespread use are like a trail that iswell-trodden. There will be signs for dangers either built into programs or documented in manuals,newsletters, or reviews. Guidance may be obtained from other users and possibly from consultants.
Forvery popular methods, there may be books to explain their intricacies or foibles in comprehensiblelanguage.PC users originally had few choices of packages for numerical problems (Battiste and Nash J C, 1983),often having to write our own programs.
A different job now faces users. Sometimes there are too manypossible programs to allow a thorough investigation of each. When there are too few or too many choices,we should use programs we already know.A common dilemma for users is the awkward balance between familiarity and experience with awell-known computational method and the lack of suitability of that method for the task at hand.
As anextreme example, we may have a simple and effective general function minimizer, such as the Hooke andJeeves Pattern Search (Nash J C 1990d). This can solve a least squares fitting problem by minimizing theobjective function 12.1.4 with respect to the parameters bj, j=1, 2, . . ., n. However, as we have alreadyseen in Sections 12.1 and 12.2, a method for solving linear least squares problems is "better": startingvalues for the parameters b are not needed, nor is possible false convergence of the program a worry. Onthe other hand, it is very easy to add constraints to the Hooke and Jeeves objective function by use ofsimple barrier functions. That is, whenever a constraint is violated, the program is given a very largenumber instead of the value S defined by Equation 12.1.4.
Again, one may need to be concerned with falseconvergence, but the modifications to the method and computer program are almost trivial. The price paidmay be very large execution times to achieve a solution.13.4 Help from OthersColleagues can aid in the search for methods. Asking questions of co-workers may seem a haphazard trainof clues to a good solution method, but rarely a waste of time.
Talking to colleagues will frequentlysuggest alternate views of the problem we wish to solve. This opens up new terms, keywords and possibleformulations for our consideration. Sometimes we know program librarians and scientific programmerswhose job it is to help others in their calculations, though it is rare to find such information resourcesoutside large government, industrial or academic institutions. How can we find free advice and assistancefrom such sources?Knowing what we want to do — that is, having a correct problem formulation — allows us to seek helpand advice intelligently, so a good attempt should be made in this direction first.
Keep requests as shortas possible. Nobody likes to have their time occupied unnecessarily. Offer what you can in return. Mostworkers who try to develop software are interested in test problems, so giving the data in return foradvice may be a fair exchange. Other aids to the advice-giver are timing and performance information forthe solutions obtained. Organize your requests. Many questions that arise do not concern the problem butthe PC and can be answered by those upon whom the user has a legitimate claim for assistance.If you are going to make money with the result, some financial consideration for the assistance is due.Payment of another kind is always due, and that is an acknowledgement of the assistance.
"Thank you"116Copyright © 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 Journalnotes, clear mention in any written reports, or comments during a presentation, recognize those who havegiven time and effort. Most workers can benefit either directly or indirectly from such appreciation inpromoting their careers or businesses, and this is one way "free" advice can be repaid. Journal editorsnever delete such acknowledgements.13.5 Sources of SoftwareA difficult task for any author or consultant in the personal computer field is recommending sources ofsoftware.
It is easy to list names of software packages, but difficult to be sure of the quality of programs,level of support, and business practices of suppliers. Many vendors of excellent products are no longerin the software business, while poor products continue in widespread use despite their deficiencies. Thissection will concentrate on long-term "sources", those that are likely to remain useful for some years tocome, even if they do not provide software that is perfectly adapted to the user’s needs.For mathematical software, the Collected Algorithms of the Association for Computing Machinery (ACM)is a solid mine of information.
New programs and methods are described (but not listed completely) inthe ACM Transactions on Mathematical Software. Unfortunately the ACM algorithms are presentedprimarily in FORTRAN, though some earlier contributions are in Algol 60 and more recent entriessometimes in C. The major target has been large machines. The programs usually have very rudimentaryuser interfaces. Most programs are available on the NETLIB facility described below.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
