Deturck, Wilf - Lecture Notes on Numerical Analysis (523142), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

For one example of the differencethat makes, see section 2.2. For another, a linear equation solver might be described bysaying“This program solves a system of simultaneous equations. To use it, put theright-hand sides into the vector B, put the coefficients into the matrix A and callthe routine. The answer will be returned in X.”We are, however, urging the reader to do it this way:“This program solves the equations AX=B, where A is an N-by-N matrix and Bis an N-vector.”Observe that the second description is shorter, only about half as long, and yet moreinformative. We have found out not only what the program does, but how that functionrelates to the global variables of the subroutine. This was done by using a judicious sprinkling of symbols in the documentation, along with the words.

Don’t use only symbols, oronly words, but weave them together for maximum information.Notice also that the ambiguous term “right-hand side” that appeared in the first formhas been done away with in the second form. The phrase was ambiguous because exactlywhat ends up on the right-hand side and what on the left is an accident of how we happento write the equations, and your audience may not do it the same way you do.(B) How is it done?This is usually the easy part of program documentation because it is not the purpose ofthis documentation to give a course in mathematics or algorithms or anything else. Hencemost of the time a reference to the literature is enough, or perhaps if the method is astandard one, just give its name. Often though, variations on the standard method havebeen chosen, and the user must be informed about those:“. .

. is solved by Gaussian elimination, using complete positioning for size. . . ”“. . . the input array A is sorted by the Quicksort method (see D.E. Knuth, TheArt of Computer Programming, volume 3). . . ”36The Numerical Solution of Differential Equations“. . . the eigenvalues and vectors are found by the Jacobi method, using Corbató’s method of avoiding the search for the largest off-diagonal element (see,for instance, the description in D.R.

Wilson, A First Course in MathematicalSoftware).”“. . . is found by the Simplex method, except that Charnes’ selection rule (seeF.A. Ficken, The Simplex Method. . . ) is not programmed, and so. . . ”(C) Describe the global variablesNow it gets hard again. The global variables are the ones through which the subroutinecommunicates with the user.

Generally speaking, the user doesn’t care about variablesthat are entirely local to your subroutine, but is vitally concerned with the communicatingvariables.First the user has to know exactly ho each of the global variables is related to theproblem that is being solved. This calls for a brief verbal description of the variable, andwhat it has to do with the functioning of the program.“A[i] is the ith element of the input list that is to be sorted, i=1..N”“WHY is set by the subroutine to TRUE unles the return is because of overflow,and then it will be set to FALSE.”“B[i,j] is the coefficient of X[j] in the ith one of the input equations BX=C.”“option is set by the calling program on input.

Set it to 0 if the output is tobe rounded to the nearest integer, else set it to m if the output is to be roundedto m decimal places (m ≤ 12).”It is extremely important that each and every global variable of the subroutine shouldget such a description. Just march through the parentheses in the subroutine or procedureheading, and describe each variable in turn.Next, the user will need more information about each of the global variables than just itsdescription as above.

Also required is the “type” of the variable. Some computer languagesforce each program to declare the types of their variables right in the opening statement.Others declare types by observing various default rules with exceptions stated.

In any case,a little redundancy never hurts, and the program documentation should declare the type ofeach and every global variable.It’s easy to declare along with the types of the variables, their dimensions if they arearray variables. For instance we may have asolver:=proc(A,X,n,ndim,b);2.4 How to document a program37in which the communicating variables have the following types:AXnndimbndim-by-ndim array of floating point numbersvector of floating point numbers of length nintegerintegervector of floating point numbers of length nThe best way to announce all of these types and dimensions of global variables to theuser is simply to list them, as above, in a table.Now surely we’ve finished taking the pulse, blood pressure, etc. of the global variables,haven’t we? Well, no, we haven’t.

There’s still more vital data that a user will need toknow about these variables. There isn’t any standard name like “type” to apply to thisinformation, so we’ll call it the “role” of the variable.First, for some of the global variables of the subroutine, it may be true that their valuesat the time the subroutine is called are quite irrelevant to the operation of the subroutine.This would be the case for the output variables, and in certain other situations.

For someother variables, the values at input time would be crucial. The user needs to know which arewhich. Just for one example, if the value at input time is irrelevant, then the user can feelfree to use the same storage for other temporary purposes between calls to the subroutine.Second, it may happen that certain variables are returned by the subroutine with theirvalues unchanged. This is particularly true for “implicitly passed” global variables, i.e.,variables whose values are used by the subroutine but which do not appear explicitly in theargument list.

In such cases, the user may be delighted to hear the good news. In othercases, the action of a subroutine may change an input variable, so if the user needs to usethose quantities again it will be necessary to save them somewhere else before calling thesubroutine. In either case, the user needs to be informed.Third, it may be that the computation of the value of a certain variable is one of themain purposes of the subroutine.

Such variables are the outputs of the program, and theuser needs to know which these are (whether they are explicit in heading or the returnstatement, or are “implicit”).Although some high-level computer languages require type declarations immediatelyin the opening instruction of a subroutine, none require the descriptions of the roles ofthe variables (well, Pascal requires the VAR declaration, and Maple separates the inputvariables from the output ones, but both languages allow implicit passing and changingof global variables). These are, however, important for the user to know, so let’s inventa shorthand for describing them in the documentation of the programs that occur in thisbook.First, if the value at input time is important, let’s say that the role of the variable is I,otherwise it is I’.Second, if the value of the variable is changed by the action of the subroutine, we’ll saythat its role is C, else C’.Finally, if the computation of this variable is one of the main purposes of the subroutine,38The Numerical Solution of Differential Equationsit’s role is O (as in output), else O’.In the description of each communicating variable, all three of these should be specified,.Thus, a variable X might have role IC’O’, or a variable why might be of role I’CO, etc.To sum up, the essential features of program documentation are a description of thatthe program does, phrased in terms of the global variables, a statement of how it gets thejob done, and a list of all of the global variables, showing for each one its name, type,dimension (or structure) if any, its role, and a brief verbal description.Refer back to the short program in section 2.2, that searches for the largest element ina row of a matrix.

Here is the table of information about its global variables:NameAijwinTypefloating point matrixintegerintegerRoleIC’O’IC’O’I’CODescriptionThe input matrixWhich row to searchColumn containing largest elementExercises 2.4Write programs that perform each of the jobs stated below. In each case, after testingthe program, document it with comments. Give a complete table of information about theglobal variables in each case.(a) Find and print all of the prime numbers between M and N .(b) Find the elements of largest and smallest absolute values in a given linear array(vector), and their positions in the array.(c) Sort the elements of a given linear array into ascending order of size.(d) Deal out four bridge hands (13 cards each from a standard 52-card deck – This oneis not so easy!).(e) Solve a quadratic equation (any quadratic equation!).2.5The midpoint and trapezoidal rulesEuler’s formula is doubtless the simplest numerical integration procedure for differentialequations, but the accuracy that can be obtained with it is insufficient for most applications.In this section and those that follow, we want to introduce a while family of methods forthe solution of differential equations, called the linear multistep methods, in which the usercan choose the degree of precision that will suffice for the job, and then select a member ofthe family that will achieve it.Before describing the family in all of its generality, we will produce two more of itsmembers, which illustrate the different sorts of creatures that inhabit the family in question.2.5 The midpoint and trapezoidal rules39Recall that we derived Euler’s method by chopping off the Taylor series expansion of thesolution after the linear term.

To get a more accurate method we could, of course, keep thequadratic term, too. However, that term involves a second derivative, and we want to avoidthe calculation of higher derivatives because our differential equations will always be writtenas first-order systems, so that only the first derivative will be conveniently computable.We can have greater accuracy without having to calculate higher derivatives if we’rewilling to allow our numerical integration procedure to involve values of the unknown function and its derivative at more than one point. In other words, in Euler’s method, the nextvalue of the unknown function, at x + h, is gotten from the values of y and y 0 at just onebackwards point x. In the more accurate formulas that we will discuss next, the new valueof y depends in y and y 0 at more than one point, for instance, at x and x − h, or at severalpoints.As a primitive example of this kind, we will now discuss the midpoint rule.

We beginonce again with the Taylor expansion of the unknown function y(x) about the point xn :y(xn + h) = y(xn ) + hy 0 (xn ) + h2y 00 (xn )y 000 (xn )+ h3+ ···.26(2.5.1)Now we rewrite equation (2.5.1) with h replaced by −h to gety(xn − h) = y(xn ) − hy 0 (xn ) + h2y 00 (xn )y 000 (xn )− h3+ ···26(2.5.2)and then subtract these equations, obtainingy(xn + h) − y(xn − h) = 2hy 0 (xn ) + 2h3y 000 (xn )+ ···.6(2.5.3)Now, just as we did in the derivation of Euler’s method, we will truncate the right sideof (2.5.3) after the first term, ignoring the terms that involve h3 , h5 , etc. Further, let’suse yn to denote the computed approximate value of y(xn ) (and yn+1 for the approximatey(xn+1 ), etc.). Then we haveyn+1 − yn−1 = 2hyn0 .(2.5.4)If, as usual, we are solving the differential equation y 0 = f (x, y), then finally (2.5.4) takesthe formyn+1 = yn−1 + 2hf (xn , yn )(2.5.5)and this is the midpoint rule.

Характеристики

Список файлов книги