Nash - Compact Numerical Methods for Computers (523163), страница 6
Текст из файла (страница 6)
CHOICE OF ALGORITHMSThe algorithms in this book have been chosen for their utility in solving a variety ofimportant problems in computational mathematics and their ease of implementationto short programs using relatively little working storage. Many topics are left out,despite their importance, because I feel that there has been insufficient development indirections relevant to compact numerical methods to allow for a suitable algorithmto be included. For example, over the last 15 years I have been interested in methodsfor the mathematical programming problem which do not require a tableau to bedeveloped either explicitly or implicitly, since these techniques are generally quitememory and code intensive.
The appearance of the interior point methods associatedwith the name of Karmarkar (1984) hold some hope for the future, but currently theprograms are quite complicated.In the solution of linear equations, my exposition has been confined to Gausselimination and the Choleski decomposition. The literature on this subject is,however, vast and other algorithms exist. These can and should be used if specialcircumstances arise to make them more appropriate.
For instance, Zambardino(1974) presents a form of Gauss elimination which uses less space than the onepresented here. This procedure, in ALGOL, is called QUARTERSOLVE because onlyn 2/4 elements are stored, though an integer vector is needed to store pivotinformation and the program as given by Zambardino is quite complicated.Many special methods can also be devised for matrices having special structuressuch as diagonal bands. Wilkinson and Reinsch (1971) give several such algorithms for both linear equations and the eigenvalue problem.
The programmerwith many problems of a special structure should consider these. However, I havefound that most users want a reliable general-purpose method for linear equations14Compact numerical methods for computersbecause their day-to-day problems vary a great deal. I have deliberately avoidedincluding a great many algorithms in this volume because most users will likely betheir own implementors and not have a great deal of time to spend choosing,coding, testing and, most of all, maintaining programs.Another choice which has been made is that of only including algorithms whichare relatively ‘small’ in the sense that they fit into the machine all at once.
Forinstance, in the solution of the algebraic eigenvalue problem on large computers,conventionally one reduces the matrix to a special form such as a tridiagonal or aHessenberg matrix, solves the eigenproblem of the simpler system then backtransforms the solutions. Each of the three phases of this procedure could befitted into a small machine.
Again, for the practitioner with a lot of matrices tosolve or a special requirement for only partial solution, such methods should beemployed. For the one-at-a-time users, however, there is three times as muchprogram code to worry about.The lack of double-precision arithmetic on the machines I used to develop thealgorithms which are included has no doubt modified my opinions concerningalgorithms. Certainly, any algorithm requiring inner products of vectors, that is(1.10)cannot be executed as accurately without extended-precision arithmetic (Wilkinson 1963).
This has led to my abandonment of algorithms which seek to find theminimum of a function along a line by use of gradient information. Suchalgorithms require the derivative along the line and employ an inner product tocompute this derivative. While these methods are distinctly unreliable on amachine having only a single, low-precision arithmetic, they can no doubt be usedvery effectively on other machines.From the above discussion it will be evident that the principles guidingalgorithm selection have been:(i) shortness of program which results from implementation and low storagerequirement, and(ii) general utility of the method and importance of the problem which it solves.To these points should be added:(iii) proven reliability in a number of tests(iv) the ease and speed with which a user can obtain useful results from thealgorithms.The third point is very important.
No program should be considered acceptable untilit has been tested fairly extensively. If possible, any method which gives solutionsthat can be checked by computing diagnostics should compute such informationroutinely. For instance, I have had users of my eigenvalue/eigenvector programs callme to say, ‘Your program doesn’t work!’ In all cases to date they have beenpremature in their judgement, since the residuals computed as a routine adjunct tothe eigensolution formation have shown the output to be reasonable even though itmight be very different from what the user expected.
Furthermore, I have savedA starting point15myself the effort of having to duplicate their calculation to prove the correctness ofthe results. Therefore, if at all possible, such checks are always built into myprograms.The fourth point is important if users are to be able to try out the ideas presentedin this book. As a user myself, I do not wish to spend many hours mastering thedetails of a code. The programs are to be treated as tools, not an end in themselves.These principles lead to the choice of the Givens’ reduction in algorithm 4 as amethod for the solution of least-squares problems where the amount of data is toogreat to allow all of it to be stored in the memory at once.
Similarly, algorithms 24and 25 require the user to provide a rule for the calculation of the product of amatrix and a vector as a step in the solution of linear equations or the algebraiceigenproblem. However, the matrix itself need not be stored explicitly. Thisavoids the problem of designing a special method to take advantage of one type ofmatrix, though it requires rather more initiative from the user as it preserves thismeasure of generality.In designing the particular forms of the algorithms which appear, a consciouseffort has been made to avoid the requirement for many tolerances.
Somemachine-dependent quantities are unfortunately needed (they can in some casesbe calculated by the program but this does lengthen the code), but as far aspossible, and especially in determining when iterative algorithms have converged,devices are used which attempt to ensure that as many digits are determined asthe machine is able to store. This may lead to programs continuing to execute longafter acceptable answers have been obtained. However, I prefer to sin on the sideof excess rather than leave results wanting in digits. Typically, the convergencetest requires that the last and present iterates be identical to the precision of themachine by means of a test such asif x + delta + offset = x + offset then halt;where offset is some modest number such as 10.
On machines which have anaccumulator with extra digits, this type of test may never be satisfied, and must bereplaced byy: = x + delta + offset;z: = x + offset;if y = z then halt;The ‘tolerance’ in this form of test is provided by the offset: within the computer therepresentations of y and z must be equal to halt execution. The simplicity of this typeof test usually saves code though, as mentioned, at the possible expense of executiontime.1.6.
A METHOD FOR EXPRESSING ALGORITHMSIn the first edition of this work, algorithms were expressed in step-and-descriptionform. This allowed users to program them in a variety of programming languages.Indeed, one of the strengths of the first edition was the variety of implementations.At the time it appeared, a number of computers had their own languages or dialects,16Compact numerical methods for computerand specialisation to one programming language would have inhibited users of thesespecial machines.
Now, however, computer users are unlikely to be willing to type incode if a machine-readable form of an algorithm exists. Even if the programminglanguage must be translated. having a workable form is useful as a starting point.The original codes for the first edition were in BASIC for a Data General NOVA.Later these codes were made to run on a North Star Horizon. Some were made towork on a Hewlett-Packard 9830A.
Present BASIC versions run on various commonmicrocomputers under the Microsoft BASIC dialect; however, since I have used veryconservative coding practices, apart from occasional syntactic deviations, theyconform to IS0 Minimal BASIC (IS0 6373-1984).Rather than proof-reading the algorithms for the first edition, I re-coded them inFORTRAN.
These codes exist as NASHLIB, and were and are commercially availablefrom the author. I have not, however, been particularly satisfied that the FORTRANimplementation shows the methods to advantage, since the structure of the algorithms seems to get lost in the detail of FORTRAN code. Also, the working parts of thecodes are overshadowed by the variable definitions and subroutine calls. Compactmethods are often best placed in-line rather than called as standard subprograms as Ihave already indicated.In the current edition, I want to stay close to the original step-and-descriptionform of the algorithms, but nevertheless wish to offer working codes which could bedistributed in machine-readable form. I have chosen to present the algorithms inBorland Turbo Pascal.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
