Nash - Compact Numerical Methods for Computers (523163), страница 7
Текст из файла (страница 7)
This has the following justification.(i) Pascal allows comments to be placed anywhere in the code, so that theoriginal style for the algorithms, except for the typographic conventions, could bekept.(ii) Turbo Pascal is available for many machines and is relatively inexpensive. Itis used as a teaching tool at many universities and colleges, including the Universityof Ottawa. Version 3.01a of the Turbo Pascal system was used in developing thecodes which appear here.
I intend to prepare versions of the codes to run under laterversions of this programming environment.(iii) The differences between Turbo and Standard Pascal are unlikely to beimportant for the methods, so that users of other Pascal compilers can also use thesecodes.(iv) Pascal is ‘close enough’ to many other programming languages to allow forstraightforward translation of the codes.A particular disadvantage of Turbo Pascal for my development work is that I haveyet to find a convenient mechanism allowing automatic compilation and execution ofcodes, which would permit me to check a complete set of code via batch execution.From the perspective of the physical length of the listings, the present algorithms arealso longer than I would like because Pascal requires program headings anddeclarations.
In the procedural parts of the codes, ‘begin’ and ‘end’ statements alsoadd to the line count to some extent.From the user perspective, the requirement that matrix sizes be explicitly specifiedcan be a nuisance. For problems with varying matrix sizes it may be necessary tocompile separate versions of programs.A starting point17Section 1.8 notes some other details of algorithm expression which relate to theease of use of the codes.1.7.
GENERAL NOTATIONI have not attempted to avoid re-use of symbols within this work since this wouldhave required an over-large set of symbols. In fact, I have used greek letters aslittle as possible to save my typists’ and typesetters’ effort. However, withinchapters and within a subject area the symbols should be consistent. There followsome brief general points on notation.(i) Absolute value is denoted by vertical bars about a quantity, | |.(ii) The norm of a quantity is denoted by double vertical bars, || ||.
The form ofthis must be found, where necessary, from the context.(iii) A closed interval [u, v] comprises all points x such that u < x < v. An openinterval (u, v) comprises all points x such that u < x < v.(iv) The exponents of decimal numbers will be expressed using the symbol E as in1·234 * 10-5 = 1·234E-5and6·78 * 102 = 678 = 6·78E2.This notation has already appeared in §1.2.1.8.
SOFTWARE ENGINEERING ISSUESThe development of microcomputer software for users who are not trained incomputer science or related subjects has given rise to user interfaces which are muchmore sophisticated and easy to use than were common when the first editionappeared. Mathematical software has not escaped such developments, but sourcecode collections have generally required the user to consolidate program units, adddriver and user routines, and compile and run the programs. In my experience, thelack of convenience implied by this requirement is a major obstacle to users learningabout software published in source code form. In our nonlinear estimation software(Nash and Walker-Smith 1987), we were careful to include batch command files toallow for easy consolidation and execution of programs.
This philosophy is continued here, albeit adapted to Turbo Pascal.1. All driver programs include code (from the fragment in file startup.pas) toallow the user to specify a file from which the program control input and theproblem data are to be input. We refer to this as a ‘control input file’. It has aname stored in the global string variable infname, and is referred to by theglobal text variable infile. Algorithms which need input get it by read or readlnstatements from infile.
The input file can be ‘con’, the console keyboard.WARNING: errors in input control files may cause source code files to be destroyed. Ibelieve this is a ‘bug’ in Turbo Pascal 3.01a, the version used to develop the codes.18Compact numerical methods for computersThe use of an include file which is not a complete procedure or function is notpermitted by Turbo Pascal 5.0.2. The same program code (startup.pas) allows an output file to be specified sothat all output which appears on the console screen is copied to a file. The namefor this file is stored in the global variable confname, and the file is referred to inprograms by the global text variable confile. Output is saved by the crude buteffective means of duplicating every write(.
. .) and writeln(. . .) statement withequivalent write(confile, . . .) and writeln(confile, . . .) statements.3. To make the algorithms less cluttered, these write and writeln statements toconfile do not appear in the listings. They are present in the files on diskette.4. To discourage unauthorised copying of the diskette files, all commentary anddocumentation of the algorithm codes has been deleted.5. To allow for execution of the programs from operating system commands (atleast in MS-DOS), compiler directives have been included at the start of alldriver programs.
Thus, if a compiled form of code dr0102.pas exists asdr0102.com, and a file dr0102x contains text equivalent to the keyboard inputneeded to correctly run this program, the commanddr0102 < dr0102xwill execute the program for the given data.Previous Home NextChapter 2FORMAL PROBLEMS IN LINEAR ALGEBRA2.1.
INTRODUCTIONA great many practical problems in the scientific and engineering world give riseto models or descriptions of reality which involve matrices. In consequence, a verylarge proportion of the literature of numerical mathematics is devoted to thesolution of various matrix equations. In the following sections, the major formalproblems in numerical linear algebra will be introduced.
Some examples areincluded to show how these problems may arise directly in practice. However, theformal problems will in most cases occur as steps in larger, more difficultcomputations. In fact, the algorithms of numerical linear algebra are the keystones of numerical methods for solving real problems.Matrix computations have become a large area for mathematical and computational research. Textbooks on this subject, such as Stewart (1973) and Strang(1976), offer a foundation useful for understanding the uses and manipulations ofmatrices and vectors.
More advanced works detail the theorems and algorithms forparticular situations. An important collection of well-referenced material is Goluband Van Loan (1983). Kahaner, Moler and Nash (1989) contains a very readabletreatment of numerical linear algebra.2.2. SIMULTANEOUS LINEAR EQUATIONSIf there are n known relationshipsAilx1 + Ai2x2 +. . .+ Ainxn = bii = 1, 2, . . . , n(2.1)between the n quantities xj with the coefficients Aij and right-hand side elementsbi, i = 1, 2, .
. . , n, then (2.1) is a set of n simultaneous linear equations in nunknowns xj, j = 1, 2, . . . , n. It is simpler to write this problem in matrix formAx = b(2.2)where the coefficients have been collected into the matrix A, the right-hand side isnow the vector b and the unknowns have been collected as the vector x. A furtherway to write the problem is to collect each column of A (say the jth) into a columnvector (i.e. aj). Then we obtain(2.3)Numerous textbooks on linear algebra, for instance Mostow and Sampson(1969) or Finkbeiner (1966), will provide suitable reading for anyone wishing to1920Compact numerical methods for computerslearn theorems and proofs concerning the existence of solutions to this problem.For the purposes of this monograph, it will suffice to outline a few basic propertiesof matrices as and when required.Consider a set of n vectors of length n, that isa1, a2, .
. . , an.(2.4)These vectors are linearly independent if there exists no set of parametersxj, j = 1, 2, . . . , n (not all zero), such that(2.5)where 0 is the null vector having all components zero. If the vectors aj are nowassembled to make the matrix A and are linearly independent, then it is alwayspossible to find an x such that (2.2) is satisfied.
Other ways of stating thecondition that the columns of A are linearly independent are that A has full rankorrank(A) = n(2.6)or that A is non-singular,If only k < n of the vectors are linearly independent, thenrank(A) = k(2.7)and A is singular. In general (2.2) cannot be solved if A is singular, thoughconsistent systems of equations exist where b belongs to the space spanned by{aj: j = 1, 2, . . . , n}.In practice, it is useful to separate linear-equation problems into two categories.(The same classification will, in fact, apply to all problems involving matrices.)(i) The matrix A is of modest order with probably few zero elements (dense).(ii) The matrix A is of high order and has most of its elements zero (sparse).The methods presented in this monograph for large matrices do not specificallyrequire sparsity.
The question which must be answered when computing on a smallmachine is, ‘Does the matrix fit in the memory available?’Example 2.1. Mass - spectrograph calibrationTo illustrate a use for the solution of a system of linear equations, consider thedetermination of the composition of a mixture of four hydrocarbons using a massspectrograph. Four lines will be needed in the spectrum. At these lines theintensity for the sample will be bi, i = 1, 2, 3, 4. To calibrate the instrument,intensities Aij for the ith line using a pure sample of the j th hydrocarbon aremeasured.
Assuming additive line intensities, the composition of the mixture isthen given by the solution x ofAx = b.Example 2.2. Ordinary differential equations: a two-point boundary-value problemLarge sparse sets of linear equations arise in the numerical solution of differentialFormal problems in linear algebra21equations. Fröberg (1965, p 256) considers the differential equationy" + y/(1+x 2 ) = 7x(2.8)with the boundary conditionsy= 02{for x = 0for x = 1.(2.9)(2.10)To solve this problem numerically, Fröberg replaces the continuum in x on theinterval [0, 1] with a set of (n + 1) points, that is, the step size on the grid ish = 1/n.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
