Nash - Scientific Computing with PCs (523165), страница 8
Текст из файла (страница 8)
However, there are some linear algebra problems that come aboutwhen other problems are approximated, for example, differential equations problems. In such cases, thelinear algebraic problems need not be solved using arrays of numbers.Iterative methods build up a solutions by applying corrections to some initial guess to it. These methodsare particularly suitable for sparse matrix problems. For the linear equation problem, the solution vectorx satisfies Equation 3.3.2. An iterative method begins with some vector(3.3.16)x(0)Each iteration computes a correction(3.3.17)d(i), so the new approximation to the solution isx(i+1) = x(i) + d(i)We repeat the process until the vector1987d).x(i) satisfies some convergence or termination criterion (Nash J C,Most methods that use matrices implicitly need to use the information that would be recorded in a matrixeither piecemeal, for example a row at a time, or as the product of the matrix multiplied by some vector.In either case the whole array does not have to be stored in the computer memory.
Instead it can be readinto memory in pieces from backing store (disk). Alternatively, only the non-zero elements of the matrixneed to be stored if these are relatively few in number (see Section 7.8). Finally, we may be able togenerate the matrix elements from a formula.Clearly, methods that use matrices implicitly are very useful in situations where an array cannot be storedin memory.
These methods were first developed for early computers that had minuscule memories bytoday’s standards. However, the problem sizes have generally increased over the years, so that problemsof the order (n) of several thousand solution elements are now common. Simply put, there are alwaysproblems too big to fit in memory.Modern PCs can employ these methods easily.
The principal obstacle to their easy implementation is, onceagain, the diversity of problem types. Methods abound for various specific matrix structures andproperties, and these implicit methods add yet another dimension of choice, e.g., the generation of matrixelements by formula, or row or column-wise access to stored values. Thus it is likely that a user musttailor existing programs to his or her exact problem. Getting a particular program running may behindered by small but awkward differences in the way a compiler handles integer and real numbers orhow it accesses memory to manipulate sparse matrices.Special Functions and Random Number GenerationMathematical methods for many types of scientific problems result in solutions expressed as specialfunctions.
Most scientists and engineers take for granted the availability of trigonometric, logarithmic andexponential functions. However, statistical distribution functions such as the error function, Student’st-distribution, chi-squared or Fisher’s F statistic are not usually part of a traditional programminglanguage, though they are commonly included in statistical packages (see Myrvold, 1991). Similarly, thefunctions derived from classical differential equations may need to be specially coded, e.g., Bessel3: COMPUTATIONAL CAPABILITIES OF PCs19functions, hypergeometric functions, elliptic integrals. Some of these special functions may be present inpackages such as MATLAB or GAUSS, or in symbolic manipulation systems like DERIVE or Maple.In this area of computation, the major limitations are:•Finding a method that computes the answer to the needed precision;•Fitting that method into the framework for the rest of our problem, e.g., in an appropriateprogramming language or package.The first of the above difficulties may be overcome by a diligent search of the literature (see Sections 13.3and 13.5) but the second obstacle can require considerably more expense or ingenuity.
We may chooseto replace the programming language compiler or interpreter, or to buy or program machine code routinesthat carry out the calculations to a sufficient number of digits, or to develop some modification of thenumerical methods that works satisfactorily in the available precision.A particular class of special functions is pseudo-random number generators. Many programming languagecompilers or interpreters include a function that allows a more or less random sequence of numbers tobe produced. Unfortunately, many generators are unique to the particular programming languagecompiler or interpreter, so that results are awkward to repeat across different computing environments.Worse, the properties of such generators are rarely documented by the producers of compilers orinterpreters.Pseudo-random number generators use totally deterministic processes that produce sequences of numbersthat seem "random" according to some property such as the correlation of each number with its nearneighbors in the sequence.
However, truly random sequences will show no discernible correlation betweennumbers that are 1,2,3 or 100 places apart in the sequence. Most of the common generators used forproducing pseudo-random sequences have weaknesses, particularly in this last property. This may be veryimportant in some applications where pairs, triples or quadruples of random numbers are needed, suchas some methods for approximation of multiple integrals (Lyness, 1986).Another difficulty of some pseudo-random number generators embedded in compilers, interpreters, orpackaged software is that the user may be unable to select the point in the pseudo-random sequencewhere he or she wishes to begin. This is very important for simulation and related techniques whererepeatability of calculations is needed.
For games, the user will usually want the sequence to begin atsome chance location.There is no particular reason the user cannot program his PC to provide the wanted generator. With alittle effort, this can usually be quickly accomplished. Again, the capability of the PC is not in question,but ease of use is a serious issue. Realistically, this is also a difficulty on any machine, though mostcomputing centers will have several random number subroutines in their program libraries.Thus, the capabilities of PCs for calculating special functions, including random numbers, are quiteadequate to such tasks.
With floating-point co-processors (such as the Intel 80x87) now widely available,PCs are better suited than conventional mainframes for such applications as lengthy simulations, whereovernight or over-weekend "runs" are possible. The ease of implementation will continue to depend onuser access to suitable software.Interpolation and Numerical DifferentiationInterpolation and numerical differentiation are classical problems in numerical analysis. Primarily theyare a part of more elaborate numerical methods. The methods use various formulas involving differencesbetween tabulated values of a quantity of interest.
A serious problem may arise if the precision of floatingpoint arithmetic is too short to allow the differences to retain enough information. For example, if afunction is tabulated to six figures but changes only in the last two digits, the difference will have onlytwo digits of information. This may or may not be adequate, depending on the application. Worse, limitedprecision may also affect the reliability of the calculation of the original function values.
These difficulties20Copyright © 1984, 1994 J C & M M NashNash Information Services Inc., 1975 Bel Air Drive, Ottawa, ON K2C 0X1 CanadaSCIENTIFIC COMPUTING WITH PCsCopy for:Dr. Dobb’s Journalare common to all computing systems.Because interpolation and numerical differentiation algorithms are small, they can be easily implementedon PCs. An experienced practitioner can program and run an interpolation or differentiation more quicklythan he can access a library routine. Indeed the sub-program "CALL" may involve almost as muchprogram code as the actual calculations.Summation and Quadrature — Numerical IntegrationIn summation, PCs are only handicapped when data files are too large to be handled. Programs forsummation, e.g., in computing the mean and variance of data, are modest in length, even if one is cautiousto preserve accuracy (Nash J C, 1981f; Chan et al., 1979; Nash J C, 1991a).Programs for the summation of mathematical series are also generally quite small, for example in theapproximation of special functions, the evaluation of integrals or the calculation of areas of surfaces.
Sinceprograms tailored specifically to special functions on a particular machine architecture must usually becustom programmed, mainframe and PC users have until recently faced the same tasks. Somecontributions to mathematical software collections (see Section 13.5) have attempted to be independentof computing platform.Because so few functions are integrable, that is, because no analytic function exists for the integral of mostfunctions, a classical problems of numerical analysis is quadrature or numerical integration.
Students ofelementary calculus are probably familiar with the simplest of numerical integration methods called thetrapezoid rule. This uses the value of the function at a number of points,(3.3.18)withfori = 0, 1, 2, . . ., nx0 = a and xn = b, then sums the areas(3.3.19)forf(xi)Ai = 0.5 (xi - xi-1) [f(xi) + f(xi-1)]i = 1, 2, . . ., n, to give the approximation(3.3.20)Clearly this can be coded as a simple, straightforward program.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
