Nash - Compact Numerical Methods for Computers

HomeNextCOMPACT NUMERICALMETHODSFOR COMPUTERSlinear algebra andfunction minimisationSecond EditionJ C NASHAdam Hilger, Bristol and New YorkCopyright © 1979, 1990 J C NashAll rights reserved. No part of this publication may be reproduced, stored in a retrieval systemor transmitted in any form or by any means, electronic, mechanical, photocopying orotherwise, without the prior permission of the publisher. Multiple copying is only permittedunder the terms of the agreement between the Committee of Vice-Chancellors and Principalsand the Copyright Licensing Agency.British Library Cataloguing in Publication DataNash, J. C.Compact numerical methods for computers: linear algebraand function minimisation - 2nd ed.1!.

Numerical analysis. Applications of microcomputer &minicomputer systems. AlgorithmsI. Title519.4ISBNISBNISBNISBN0-85274-318-10-85274-319-X (pbk)0-7503-0036-1 (5¼" IBM disc)0-7503-0043-4 (3½" IBM disc)Library of Congress Cataloging-in-Publication Data are availableFirst published, 1979Reprinted, 1980Second edition, 1990Published under the Adam Hilger imprint by IOP Publishing LtdTechno House, Redcliffe Way, Bristol BSl 6NX, England335 East 45th Street, New York, NY 10017-3483, USAFilmset by Bath Typesetting Ltd, Bath, AvonPrinted in Great Britain by Page Bros (Norwich) LtdCONTENTSixxiPreface to the Second EditionPreface to the First Edition1.

A STARTING POINT1.1. Purpose and scope1.2. Machine characteristics1.3. Sources of programs1.4. Programming languages used and structured programming1.5. Choice of algorithms1.6. A method for expressing algorithms1.7. General notation1.8. Software engineering issues113911131517172.

FORMAL PROBLEMS IN LINEAR ALGEBRA2.1. Introduction2.2. Simultaneous linear equations2.3. The linear least-squares problem2.4. The inverse and generalised inverse of a matrix2.5. Decompositions of a matrix2.6. The matrix eigenvalue problem191919212426283. THE SINGULAR-VALUE DECOMPOSITION AND ITS USETO SOLVE LEAST-SQUARES PROBLEMS3.1. Introduction3.2. A singular-value decomposition algorithm3.3. Orthogonalisation by plane rotations3.4. A fine point3.5. An alternative implementation of the singular-value decomposition3.6.

Using the singular-value decomposition to solve least-squaresproblems303031323538404. HANDLING LARGER PROBLEMS4.1. Introduction4.2. The Givens’ reduction4.3. Extension to a singular-value decomposition4.4. Some labour-saving devices4.5. Related calculations4949495454635. SOME COMMENTS ON THE FORMATION OF THE CROSSPRODUCTS MATRIX ATA66vviCompact numerical methods for computers6.

LINEAR EQUATIONS-A DIRECT APPROACH6.1. Introduction6.2. Gauss elimination6.3. Variations on the theme of Gauss elimination6.4. Complex systems of equations6.5. Methods for special matrices7272728082837. THE CHOLESKI DECOMPOSITION7.1. The Choleski decomposition7.2. Extension of the Choleski decomposition to non-negative definite matrices7.3. Some organisational details84848.

THE SYMMETRIC POSITIVE DEFINITE MATRIX AGAIN8.1. The Gauss-Jordan reduction8.2. The Gauss-Jordan algorithm for the inverse of a symmetricpositive definite matrix94949. THE ALGEBRAIC EIGENVALUE PROBLEM9.1. Introduction9.2. The power method and inverse iteration9.3. Some notes on the behaviour of inverse iteration9.4. Eigensolutions of non-symmetric and complex matrices10. REAL SYMMETRIC MATRICES10.1.

The eigensolutions of a real symmetric matrix10.2. Extension to matrices which are not positive definite10.3. The Jacobi algorithm for the eigensolutions of a real symmetricmatrix10.4. Organisation of the Jacobi algorithm10.5. A brief comparison of methods for the eigenproblem of a realsymmetric matrix11. THE GENERALISED SYMMETRIC MATRIX EIGENVALUEPROBLEM86909710210210210811011911912112612813313514212.

OPTIMISATION AND NONLINEAR EQUATIONS12.1. Formal problems in unconstrained optimisation and nonlinearequations12.2. Difficulties encountered in the solution of optimisation andnonlinear-equation problems14213. ONE-DIMENSIONAL PROBLEMS13.1. Introduction13.2. The linear search problem13.3. Real roots of functions of one variable148148148160146Contents14. DIRECT SEARCH METHODS14.1. The Nelder-Mead simplex search for the minimum of afunction of several parameters14.2. Possible modifications of the Nelder-Mead algorithm14.3. An axial search procedure14.4. Other direct search methodsvii16816817217818215.

DESCENT TO A MINIMUM I: VARIABLE METRICALGORITHMS15.1. Descent methods for minimisation15.2. Variable metric algorithms15.3. A choice of strategies18618618719016. DESCENT TO A MINIMUM II: CONJUGATE GRADIENTS16.1. Conjugate gradients methods16.2. A particular conjugate gradients algorithm17.

MINIMISING A NONLINEAR SUM OF SQUARES17.1. Introduction17.2. Two methods17.3. Hartley’s modification17.4. Marquardt’s method17.5. Critique and evaluation17.6. Related methods19719719820720720821021121221518. LEFT-OVERS18.1. Introduction18.2. Numerical approximation of derivatives18.3. Constrained optimisation18.4. A comparison of function minimisation and nonlinear leastsquares methods21821821822119.

THE CONJUGATE GRADIENTS METHOD APPLIED TOPROBLEMS IN LINEAR ALGEBRA19.1. Introduction19.2. Solution of linear equations and least-squares problems byconjugate gradients19.3. Inverse iteration by algorithm 2419.4. Eigensolutions by minimising the Rayleigh quotient226234234235241243APPENDICES1. Nine test matrices2. List of algorithms3. List of examples4. Files on the software diskette253253255256258BIBLIOGRAPHY263INDEX271PREFACE TO THE SECOND EDITIONThe first edition of this book was written between 1975 and 1977. It may come as asurprise that the material is still remarkably useful and applicable in the solution ofnumerical problems on computers.

This is perhaps due to the interest of researchersin the development of quite complicated computational methods which requireconsiderable computing power for their execution. More modest techniques havereceived less time and effort of investigators. However, it has also been the case thatthe algorithms presented in the first edition have proven to be reliable yet simple.The need for simple, compact numerical methods continues, even as softwarepackages appear which relieve the user of the task of programming. Indeed, suchmethods are needed to implement these packages. They are also important whenusers want to perform a numerical task within their own programs.The most obvious difference between this edition and its predecessor is that thealgorithms are presented in Turbo Pascal, to be precise, in a form which will operateunder Turbo Pascal 3.01a. I decided to use this form of presentation for the followingreasons:(i) Pascal is quite similar to the Step-and-Description presentation of algorithmsused previously;(ii) the codes can be typeset directly from the executable Pascal code, and thevery difficult job of proof-reading and correction avoided;(iii) the Turbo Pascal environment is very widely available on microcomputersystems, and a number of similar systems exist.Section 1.6 and appendix 4 give some details about the codes and especially thedriver and support routines which provide examples of use.The realization of this edition was not totally an individual effort.

My researchwork, of which this book represents a product, is supported in part by grants fromthe Natural Sciences and Engineering Research Council of Canada. The Mathematics Department of the University of Queensland and the Applied MathematicsDivision of the New Zealand Department of Scientific and Industrial Researchprovided generous hospitality during my 1987-88 sabbatical year, during which agreat part of the code revision was accomplished. Thanks are due to Mary WalkerSmith for reading early versions of the codes, to Maureen Clarke of IOP PublishingLtd for reminders and encouragement, and to the Faculty of Administration of theUniversity of Ottawa for use of a laser printer to prepare the program codes.

MaryNash has been a colleague and partner for two decades, and her contribution to thisproject in many readings, edits, and innumerable other tasks has been a large one.In any work on computation, there are bound to be errors, or at least programixxCompact numerical methods for computersstructures which operate in unusual ways in certain computing environments. Iencourage users to report to me any such observations so that the methods may beimproved.J. C. NashOttawa, 12 June 1989PREFACE TO THE FIRST EDITIONThis book is designed to help people solve numerical problems. In particular, it isdirected to those who wish to solve numerical problems on ‘small’ computers, thatis, machines which have limited storage in their main memory for program anddata. This may be a programmable calculator-even a pocket model-or it maybe a subsystem of a monster computer.

The algorithms that are presented in thefollowing pages have been used on machines such as a Hewlett-Packard 9825programmable calculator and an IBM 370/168 with Floating Point Systems ArrayProcessor. That is to say, they are designed to be used anywhere that a problemexists for them to attempt to solve. In some instances, the algorithms will not beas efficient as others available for the job because they have been chosen anddeveloped to be ‘small’. However, I believe users will find them surprisinglyeconomical to employ because their size and/or simplicity reduces errors andhuman costs compared with equivalent ‘larger’ programs.Can this book be used as a text to teach numerical methods? I believe it can.The subject areas covered are, principally, numerical linear algebra, functionminimisation and root-finding.

Interpolation, quadrature and differential equations are largely ignored as they have not formed a significant part of my ownwork experience. The instructor in numerical methods will find perhaps too fewexamples and no exercises. However, I feel the examples which are presentedprovide fertile ground for the development of many exercises. As much aspossible, I have tried to present examples from the real world. Thus the origins ofthe mathematical problems are visible in order that readers may appreciate thatthese are not merely interesting diversions for those with time and computersavailable.Errors in a book of this sort, especially in the algorithms, can depreciate itsvalue severely.