Hamming - Numerical Methods for Scientists and Engineers

Numerical Methods for Scientists and Engineers

SECOND EDITION

R. W. HAMMING

Adjunct Professor of Computer Science,
Naval Postgraduate School

Dover Publications, Inc. New York

Copyright 1962, 1973 by R. W. Hamming.

All rights reserved.

This Dover edition, first published in 1986, is an unabridged republication of the second edition (1973) of the work first published by McGraw-Hill, Inc., New York, in 1962.

Library of Congress Cataloging-in-Publication Data

Hamming, R. W. (Richard Wesley), 1915

Numerical methods for scientists and engineers.

Reprint. Originally published: New York: McGraw-Hill, 1973.

Bibliography: p.

Includes index.

1. Numerical analysisData processing. I. Title.

[QA297.H281987] 519.4 86-16226

ISBN-13: 978-0-486-65241-2

ISBN-10: 0-486-65241-6

Manufactured in the United States by Courier Corporation
65241617
www.doverpublications.com

THE PURPOSE OF COMPUTING
IS INSIGHT, NOT NUMBERS

To study, and when the occasion arises to put what one has
learned into practiceis that not deeply satisfying?

Confucius, Analects 1.1.1

PREFACE

There has been much progress in the 10 years since the first edition was written, but of the many books that have appeared on the topic none has put the emphasis on the frequency approach and its use in the solution of problems. For these reasons, a second edition seems necessary.

The material has been extensively rearranged, rewritten, and added to, so that in some respects it is a new book; however, the main aims, style, and motto have not changed.

As always, the author is greatly indebted to others for much that is in the book. Most important are his management and colleagues at the Bell Telephone Laboratories. Professor Roger Pinkham has over the years been a constant source of stimulation and inspiration. It would take a list of at least 100 names to thank all who have contributed to some extent, and at the top of this list would be M. P. Epstein. My thanks also go to all the unmentioned people on the list and to A. Ralston for many helpful suggestions. Thanks also to Mrs. Jeannie Waddel for typing and helping to organize the manuscript.

R. W. HAMMING

PART I

Fundamentals and Algorithms

AN ESSAY ON NUMERICAL METHODS

1.1 THE FIVE MAIN IDEAS

Numerical methods use numbers to simulate mathematical processes, which in turn usually simulate real-world situations. This implies that there is a purpose behind the computing. To cite the motto of the book, The Purpose of Computing Is Insight, Not Numbers. This motto is often thought to mean that the numbers from a computing machine should be read and used, but there is much more to the motto. The choice of the particular formula, or algorithm, influences not only the computing but also how we are to understand the results when they are obtained. The way the computing progresses, the number of iterations it requires, or the spacing used by a formula, often sheds light on the problem. Finally, the same computation can be viewed as coming from different models, and these different views often shed further light on the problem. Thus computing is, or at least should be, intimately bound up with both the source of the problem and the use that is going to be made of the answersit is not a step to be taken in isolation from reality.

Much of the knowledge necessary to meet this goal comes from the field of application and therefore lies outside a general treatment of numerical methods. About all that can be done is to supply a rich assortment of methods and to comment on their relevance in general situations. This art of connecting the specific problem with the computing is important, but it is best taught in connection with a field of application.

The second main idea is a consequence of the first. If the purpose of computing is insight, not numbers, as the motto states, then it is necessary to study families and to relate one family to another when possible, and to avoid isolated formulas and isolated algorithms. In this way a sensible choice can be made among the alternate ways of doing the problem, and once the computation is done, alternate ways of viewing the results can be developed. Thus, hopefully, the insight can arise. For these reasons we tend to concentrate on systematic methods for finding formulas and avoid the isolated, cute result. It is somewhat more difficult to systematize algorithms, but a unifying principle has been found.

This is perhaps the place to discuss some of the differences between numerical methods and numerical analysis (as judged by the corresponding textbooks). Numerical analysis seems to be the study in depth of a few, somewhat arbitrarily selected, topics and is carried out in a formal mathematical way devoid of relevance to the real world. Numerical methods, on the other hand, try to meet the need for methods to cope with the potentially infinite variety of problems that can arise in practice. The methods given are generally chosen for their wide applicability in creating formulas and algorithms as well as for the particular result being found at that point.

The third major idea is roundoff error. This effect arises from the finite nature of the computing machine which can only deal with finitely represented numbers. But the machine is used to simulate the mathematicians number system which uses infinitely long representations. In the machine the fraction - becomes the terminated decimal 0.333...3 with the obvious roundoff effect. At first this approximation does not seem to be very severe since usually a minimum of eight decimal places are carried at every step, but the incredible number of arithmetic operations that can occur in a problem lasting only a few seconds is the reason that roundoff plays an important role. The greatest loss of significance in the numbers occurs when two numbers of about the same size are subtracted so that most of the leading digits cancel out, and unless care is taken in advance, this can happen almost any place in a long computation.

Most books on computing stress the estimation of roundoff, especially the bounding of roundoff, but we shall concentrate on the avoidance of roundoff. It seems better to avoid roundoff than to estimate what did not have to occur if common sense and a few simple rules had been followed before the problem was put on the machine.

The fourth main idea is again connected with the finite nature of the machine, namely that many of the processes of mathematics, such as differentiation and integration, imply the use of a limit which is an infinite process. The machine has finite speed and can only do a finite number of operations in a finite length of time. This effect gives rise to the truncation error of a process.

We shall generally first give an exact expression for the truncation error and deduce from it various bounds. A moments thought should reveal that if we had an exact expression, then it would be practically useless because to know the exact error is to know the exact answer. However, the exact-error expression is very useful in studying families of formulas, and it provides a starting point for a variety of error bounds.

The fifth main idea is feedback, which means, as its name implies, that numbers produced at one stage are fed back into the computer to be processed again and again; the program has a loop which uses the output of one cycle as the input for the next cycle. This feedback situation is very common in computing, as it is a very powerful tool for solving many problems.