Nash - Compact Numerical Methods for Computers (523163), страница 2
Текст из файла (страница 2)
I would very much appreciate hearing from anyone who discoversfaults and will do my best to respond to such queries by maintaining an erratasheet. In addition to the inevitable typographical errors, my own included, Ianticipate that some practitioners will take exception to some of the choices Ihave made with respect to algorithms, convergence criteria and organisation ofcalculations. Out of such differences, I have usually managed to learn somethingof value in improving my subsequent work, either by accepting new ideas or bybeing reassured that what I was doing had been through some criticism and hadsurvived.There are a number of people who deserve thanks for their contribution to thisbook and who may not be mentioned explicitly in the text:(i) in the United Kingdom, the many members of the Numerical AlgorithmsGroup, of the Numerical Optimization Centre and of various university departments with whom I discussed the ideas from which the algorithms have condensed;xixiiCompact numerical methods for computers(ii) in the United States, the members of the Applied Mathematics Division of theArgonne National Laboratory who have taken such an interest in the algorithms,and Stephen Nash who has pointed out a number of errors and faults; and(iii) in Canada, the members of the Economics Branch of Agriculture Canada forpresenting me with such interesting problems to solve, Kevin Price for careful anddetailed criticism, Bob Henderson for trying out most of the algorithms, RichardWang for pointing out several errors in chapter 8, John Johns for trying (andfinding errors in) eigenvalue algorithms, and not least Mary Nash for a host ofcorrections and improvements to the book as a whole.It is a pleasure to acknowledge the very important roles of Neville Goodmanand Geoff Amor of Adam Hilger Ltd in the realisation of this book.J.
C. NashOttawa, 22 December 1977Previous Home NextChapter 1A STARTING POINT1.1. PURPOSE AND SCOPEThis monograph is written for the person who has to solve problems with (small)computers. It is a handbook to help him or her obtain reliable answers to specificquestions, posed in a mathematical way, using limited computational resources.To this end the solution methods proposed are presented not only as formulae butalso as algorithms, those recipes for solving problems which are more than merelya list of the mathematical ingredients.There has been an attempt throughout to give examples of each type ofcalculation and in particular to give examples of cases which are prone to upsetthe execution of algorithms.
No doubt there are many gaps in the treatmentwhere the experience which is condensed into these pages has not been adequateto guard against all the pitfalls that confront the problem solver. The process oflearning is continuous, as much for the teacher as the taught. Therefore, the userof this work is advised to think for him/herself and to use his/her own knowledge andfamiliarity of particular problems as much as possible.
There is, after all, barely aworking career of experience with automatic computation and it should not seemsurprising that satisfactory methods do not exist as yet for many problems. Throughout the sections which follow, this underlying novelty of the art of solving numericalproblems by automatic algorithms finds expression in a conservative design policy.Reliability is given priority over speed and, from the title of the work, spacerequirements for both the programs and the data are kept low.Despite this policy, it must be mentioned immediately and with someemphasis that the algorithms may prove to be surprisingly efficient from acost-of-running point of view. In two separate cases where explicit comparisonswere made, programs using the algorithms presented in this book cost less torun than their large-machine counterparts.
Other tests of execution times foralgebraic eigenvalue problems, roots of a function of one variable and functionminimisation showed that the eigenvalue algorithms were by and large ‘slower’than those recommended for use on large machines, while the other test problemswere solved with notable efficiency by the compact algorithms. That ‘small’programs may be more frugal than larger, supposedly more efficient, ones basedon different algorithms to do the same job has at least some foundation in the waytoday’s computers work.Since the first edition of this work appeared, a large number and variety ofinexpensive computing machines have appeared.
Often termed the ‘microcomputerrevolution’, the widespread availability of computing power in forms as diverse asprogrammable calculators to desktop workstations has increased the need for12Compact numerical methods for computerssuitable software of all types.
including numerical methods. The present work isdirected at the user who needs, for whatever reason, to program a numerical methodto solve a problem. While software packages and libraries exist to provide for thesolution of numerical problems, financial, administrative or other obstacles mayrender their use impossible or inconvenient. For example, the programming toolsavailable on the chosen computer may not permit the packaged software to be used.Firstly, most machines are controlled by operating systems which control (andsometimes charge for) the usage of memory, storage, and other machine resources.
Inboth compilation (translation of the program into machine code) and execution, asmaller program usually will make smaller demands on resources than a larger one.On top of this, the time of compilation is usually related to the size of the sourcecode.Secondly, once the program begins to execute, there are housekeeping operationswhich must be taken care of:(i) to keep programs and data belonging to one task or user separate from thosebelonging to others in a time-sharing environment, and(ii) to access the various parts of the program and data within the set ofresources allocated to a single user.Studies conducted some years ago by Dr Maurice Cox of the UK NationalPhysical Laboratory showed that (ii) requires about 90% of the time a computerspends with a typical scientific computation.
Only about 10% of the effort goes toactual arithmetic. This mix of activity will vary greatly with the machine and problemunder consideration. However, it is not unreasonable that a small program can usesimpler structures, such as address maps and decision tables, than a larger routine. Itis tempting to suggest that the computer may be able to perform useful work with asmall program while deciding what to do with a larger one. Gathering specificevidence to support such conjectures requires the fairly tedious work of benchmarking. Moreover, the results of the exercise are only valid as long as the machine,operating system, programming language translators and programs remainunchanged.
Where performance is critical, as in the case of real-time computations,for example in air traffic control, then benchmarking will be worthwhile. In othersituations, it will suffice that programs operate correctly and sufficiently quickly thatthe user is not inconvenienced.This book is one of the very few to consider algorithms which have very lowstorage requirements. The first edition appeared just as programmable calculatorsand the first microcomputers were beginning to make their presence felt. Thesebrought to the user’s desk a quantum improvement in computational power.Comparisons with the earliest digital computers showed that even a modest microcomputer was more powerful.
It should be noted, however, that the programmer didnot have to handle all the details of arithmetic and data storage, as on the earlycomputers, thanks to the quick release of programming language translators. Thereis unfortunately still a need to be vigilant for errors in the floating-point arithmeticand the special function routines. Some aids to such checking are mentioned later in§1.2.Besides the motivation of cost savings or the desire to use an available andA starting point3possibly under-utilised small computer, this work is directed to those who sharemy philosophy that human beings are better able to comprehend and deal withsmall programs and systems than large ones.
That is to say, it is anticipated thatthe costs involved in implementing, modifying and correcting a small program willbe lower for small algorithms than for large ones, though this comparison willdepend greatly on the structure of the algorithms. By way of illustration, Iimplemented and tested the eigenvalue/vector algorithm (algorithm 13) in underhalf an hour from a 10 character/second terminal in Aberystwyth using a XeroxSigma 9 computer in Birmingham.
The elapsed time includes my instruction in theuse of the system which was of a type I had not previously encountered. I amgrateful to Mrs Lucy Tedd for showing me this system. Dr John Johns of theHerzberg Institute of Astrophysics was able to obtain useful eigensolutions fromthe same algorithm within two hours of delivery of a Hewlett-Packard 9825programmable calculator.
He later discovered a small error in the prototype ofthe algorithm.The topics covered in this work are numerical linear algebra and functionminimisation. Why not differential equations? Quite simply because I have hadvery little experience with the numerical solution of differential equations exceptby techniques using linear algebra or function minimisation. Within the two broadareas, several subjects are given prominence. Linear equations are treated inconsiderable detail with separate methods given for a number of special situations.The algorithms given here are quite similar to those used on larger machines. Thealgebraic eigenvalue problem is also treated quite extensively, and in this edition, amethod for complex matrices is included.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
