Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 2
Текст из файла (страница 2)
The programmermust transform the suggested algorithm into a set of unambiguous stepby-step instructions to the computer. The first step in this procedure iscalled flow charting. A flow chart is simply a set of procedures, usually inlogical block form, which the computer will follow.
It may be given ingraphical or procedural statement form. The complexity of the flow willdepend upon the complexity of the problem and the amount of detailxixii INTRODUCTIONincluded. However, it should be possible for someone other than theprogrammer to follow the flow of information from the chart. The flowchart is an effective aid to the programmer, who must translate its majorfunctions into a program, and, at the same time, it is an effective means ofcommunication to others who wish to understand what the program does.In this book we sometimes use flow charts in graphical form, but moreoften in procedural statement form.
When graphical flow charts are used,standard conventions are followed, whereas all procedural statement chartsuse a self-explanatory ALGOL-like statement language. Having produceda flow chart, the programmer must transform the indicated procedures intoa set of machine instructions. This may be done directly in machinelanguage, in an assembly language, or in a procedure-oriented language. Inthis book a dialect of FORTRAN called FORTRAN 77 is used exclusively. FORTRAN 77 is a new dialect of FORTRAN which incorporatesnew control statements and which emphasizes modern structured-programming concepts.
While FORTRAN IV compilers are available on almost allcomputers, FORTRAN 77 may not be as readily available. However,conversion from FORTRAN 77 to FORTRAN IV should be relativelystraightforward.A procedure-oriented language such as FORTRAN or ALGOL issometimes called an algorithmic language. It allows us to express amathematical algorithm in a form more suitable for communication withcomputers.
A FORTRAN procedure that implements a mathematicalalgorithm will, in general, be much more precise than the mathematicalalgorithm. If, for example, the mathematical algorithm specifies an iterative procedure for finding the solution of an equation, the FORTRANprogram must specify (1) the accuracy that is required, (2) the number ofiterations to be performed, and (3) what to do in case of nonconvergence.Most of the algorithms in this book are given in the normal mathematicalform and in the more precise form of a FORTRAN procedure.In many installations, each of these phases of problem solving isperformed by a separate person.
In others, a single person may beresponsible for all three functions. It is clear that there are many interactions among these three phases. As the program develops, more information becomes available, and this information may suggest changes in theformulation, in the algorithms being used, and in the program itself.ELEMENTARY NUMERICAL ANALYSISAn Algorithmic ApproachPrevious Home NextCHAPTERONENUMBER SYSTEMS AND ERRORSIn this chapter we consider methods for representing numbers on computers and the errors introduced by these representations. In addition, weexamine the sources of various types of computational errors and theirsubsequent propagation. We also discuss some mathematical preliminaries.1.1 THE REPRESENTATION OF INTEGERSIn everyday life we use numbers based on the decimal system.
Thus thenumber 257, for example, is expressible as257 = 2·100 + 5·10 + 7·1= 2·102 + 5·101 + 7·1000We call 10 the base of this system. Any integer is expressible as apolynomial in the base 10 with integral coefficients between 0 and 9. Weuse the notationN = (a n a n - 1 ··· a 0 ) 1 0= a n 10 n + a n-1 10 n-1 + ··· + a 0 10 0(1.1)to denote any positive integer in the base 10.
There is no intrinsic reason touse 10 as a base. Other civilizations have used other bases such as 12, 20,or 60. Modern computers read pulses sent by electrical components. Thestate of an electrical impulse is either on or off. It is therefore convenient torepresent numbers in computers in the binary system. Here the base is 2,and the integer coefficients may take the values 0 or 1.12NUMBER SYSTEMS AND ERRORSA nonnegative integer N will be represented in the binary system as(1.2)where the coefficients ak are either 0 or 1.
Note that N is again representedas a polynomial, but now in the base 2. Many computers used in scientificwork operate internally in the binary system. Users of computers, however,prefer to work in the more familiar decimal system. It is therefore necessary to have some means of converting from decimal to binary wheninformation is submitted to the computer, and from binary to decimal foroutput purposes.Conversion of a binary number to decimal form may be accomplisheddirectly from the definition (1.2). As examples we haveThe conversion of integers from a baseto the base 10 can also beaccomplished by the following algorithm, which is derived in Chap.
2.Algorithm 1.1 Given the coefficients an, . . . , a0 of the polynomial(1.3)and a numberCompute recursively the numbersThenSince, by the definition (1.2), the binary integerrepresents the value of the polynomial (1.3) at x = 2, we can use Algorithm 1.1, withto find the decimal equivalents of binary integers.Thus the decimal equivalent of (1101)2 computed using Algorithm 1.1is1.1THE REPRESENTATION OF INTEGERS3and the decimal equivalent of (10000)2 isConverting a decimal integer N into its binary equivalent can also beaccomplished by Algorithm 1.1 if one is willing to use binary arithmetic.then by the definition (1.1), N = p(10).
whereFor ifp(x) is the polynomial (1.3). Hence we can calculate the binary representation for N by translating the coefficientsinto binary integersand then using Algorithm 1.1 to evaluate p(x) at x = 10 = (1010) 2 inbinary arithmetic. If, for example, N = 187, thenand using Algorithm 1.1 and binary arithmetic,Therefore 187 = (10111011)2.Binary numbers and binary arithmetic, though ideally suited fortoday’s computers, are somewhat tiresome for people because of thenumber of digits necessary to represent even moderately sized numbers.Thus eight binary digits are necessary to represent the three-decimal-digitnumber 187. The octal number system, using the base 8, presents a kind ofcompromise between the computer-preferred binary and the people-preferred decimal system. It is easy to convert from octal to binary and backsince three binary digits make one octal digit.
To convert from octal tobinary, one merely replaces all octal digits by their binary equivalent; thusConversely, to convert from binary to octal, one partitions the binary digitsin groups of three (starting from the right) and then replaces each threegroup by its octal digit; thusIf a decimal integer has to be converted to binary by hand, it is usuallyfastest to convert it first to octal using Algorithm 1.1, and then from octalto binary. To take an earlier example,4NUMBER SYSTEMS AND ERRORSHence, using Algorithm 1.1 [with 2 replaced by 10 = (12)8, and with octalarithmetic],Therefore, finally,EXERCISES1.1-l Convert the following binary numbers to decimal form:1.1-2 Convert the following decimal numbers to binary form:82, 109, 34331.1-3 Carry out the conversions in Exercises 1.
l-l and 1.1-2 by converting first to octal form.1.1-4 Write a FORTRAN subroutine which accepts a number to the base BETIN with theNIN digits contained in the one-dimensional array NUMIN, and returns the NOUT digits ofthe equivalent in base BETOUT in the one-dimensional array NUMOUT. For simplicity,restrict both BETIN and BETOUT to 2, 4, 8, and 10.1.2 THE REPRESENTATION OF FRACTIONSIf x is a positive real number, then its integral part xI is the largest integerless than or equal to x, whileis its fractional part. The fractional part can always be written as a decimalfraction:(1.4)where each b k is a nonnegative integer less than 10. If b k = 0 for all kgreater than a certain integer, then the fraction is said to terminate.
Thusis a terminating decimal fraction, whileis not.If the integral part of x is given as a decimal integer by1.2THE REPRESENTATION OF FRACTIONS5while the fractional part is given by (1.4), it is customary to write the tworepresentations one after the other, separated by a point, the “decimalpoint”:Completely analogously, one can write the fractional part of x as abinary fraction:where each bk is a nonnegative integer less than 2, i.e., either zero or one. Ifthe integral part of x is given by the binary integerthen we writeusing a “binary point.”The binary fraction (.b1 b 2 b 3 · · · ) 2 for a given number xF betweenzero and one can be calculated as follows: IfthenHence b1 is the integral part of 2xF, whileTherefore, repeating this procedure, we find that b2 is the integral part of2(2xF)F, b3 is the integral part of 2(2(2xF)F)F, etc.If, for example, x = 0.625 = xF, thenand all further bk’s are zero.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
