Search

A description is given of a program for computing the solution to a small number of standard numerical analysis problems to any specified accuracy, up to a limit of 2000 correct decimal places. Each computed number is bounded in an interval with a multiple precision midpoint. Arithmetic operations involving these numbers are executed according to interval arithmetic concepts, with non-significant digits automatically discarded. Details are supplied of problem specification and problem computation. [ABSTRACT FROM AUTHOR]

The article presents the procedures for computing, smoothing and interpolating natural splines. Several mathematical formulae with mathematical and numerical analyses are cited. Problems indicating the application of smoothing and interpolating are discussed. The purpose of the procedure is to determine the coefficients in the representation of a natural spline of degrees in terms of a local basis. The procedure is based on algorithms. The parameters maxit should be a positive integer specifying the maximum number of iterations desired in computing the problem. Illustrations in applying such mathematical formulae are offered.

The article explains six subprograms for curve fitting using splines under tension. The first pair, CURV1 and CURV2, solves the standard interpolation problem: determine a real-valued function that assumes values at abscissas. The second pair, KURV1 and KURV2, solves the more general problem of passing a curve through a sequence of pairs in the plane. The third pair, KURVP1 and KURVP2, solves the same problem, but the solution curve is closed. CURV1 and KURV2 require additional endpoint slope conditions to determine the solution. The user may omit the information in which case values are produced internally based upon the other input information. If three or more points are to be interpolated, these internal slope values are the slopes given by a quadratic polynomial interpolating the first three values for the initial slope and last three values for the terminal slope. If only two points are to be interpolated and no slope information is given, the resulting curve is a straight line. curve is a straight line.

The article presents a computer algorithm related to procedures for natural spline interpolation. The purpose of the procedures that have been presented is to determine the interpolating natural spline function for a set of data points. The interpolating natural spline functions are polynomials and their derivatives are continuous functions. The algorithm computes the coefficients of the natural spline for several cases. The algorithm treats the case of equidistant knots. If the knots are known to be equidistant, the use of this procedure results in considerable economy of computational effort. Since the case of a cubic natural spline is of frequent occurrence, a procedure has been given that computes the coefficients in this special case. This procedure is very much faster than either of the other procedures. The calculation of the coefficients is carried out in a numerically stable manner. For convenience of calculations, a normalizing factor has been used. The parameters that have been used in the algorithm have been described.

The article presents an algorithm for the numerical integration over a finite interval automatically. The algorithm's purpose is to automatically calculate the integral over a finite interval with relative error not exceeding a specified value. It utilizes a basic integration algorithm applied under the control of algorithms which invoke adaptive or nonadaptive subdivision of the range of integration. The subdivision processes will only normally be needed on extremely difficult integrals as the basic algorithm is sufficiently powerful.

The cubic spline approximation to the fourth-order differential equation yin + p(x)y" + q(x)y' + r(x)y = t(x) is shown to reduce to the solution of a five-term recurrence relationship. For some special cases the approximation is shown to be simply related to a finite difference representation with a local truncation error of order (1/720)δ³y)?. [ABSTRACT FROM AUTHOR]

A method for generating values of continuous symmetric random variables that is relatively fast, requires essentially no computer memory, and is easy to use is developed. The method, which uses a uniform zero-one random number source, is based on the inverse function of the lambda distribution of Tukey. Since it approximates many of the continuous theoretical distributions and empirical distributions frequently used in simulations, the method should be useful to simulation practitioners. [ABSTRACT FROM AUTHOR]

A study comparing the performance of several computer programs for integrating systems of ordinary differential equations is reported. The integration methods represented include multistep methods (predictors correctors), single-step methods (Runge-Kutta) and extrapolation methods (both polynomial and rational). The testing procedure is described together with the evaluation criteria applied. A set of test problems on which the programs were tested is included in an appendix. For the particular problems and criteria used in the investigation it was found that a program based on rational extrapolation showed the best performance. [ABSTRACT FROM AUTHOR]

The article discusses a study on the two subroutines of user information and Fortran listings namely INTRPL and CRVFIT, which implement the method of interpolation and smooth curve fitting based on local procedures. This method of interpolation is designed in such a way that the resulting curve will pass through all the given data points and appear smooth and natural. The INTRPL subroutine interpolates the values of a single-valued function y = y(x). The CRVFIT subroutine interpolates points in each interval between a pair of data points and generates a set of output points consisting of the input data points and the interpolated points.

Discusses computer methods for transforming uniformly distributed random numbers into exponentially and normally distributed quantities. Conversion of Taylor series expansions directly into sampling steps; Acceptance-rejection technique for continuous distributions.

The problem considered is that of evaluating a rational expression to within any desired tolerance on a computer which performs variable-precision floating-point arithmetic operations. For example, the expression might be π/ (π + ½ - e) √2), which is rational in the data π, e, √2. An automatic error analysis technique is given for determining, directly from the results of a trial low-precision interval arithmetic calculation, just how much precision and data accuracy are required to achieve a desired final accuracy. The techniques given generalize easily to the evaluation of many nonrational expressions. [ABSTRACT FROM AUTHOR]

This article discusses professor George E. Forsythe's contributions to the establishment of computer science as a recognized discipline. It is generally agreed that he, more than any other man, is responsible for the rapid development of computer science in the world's colleges and universities. His foresight, combined with his untiring efforts to spread the gospel of computing, have had a significant and lasting impact; one might almost regard him as the Martin Luther of the Computer Reformation. His early training and research in numerical analysis was a good blend of theory and practice. Starting in 1948 he worked for the National Bureau of Standards' Institute for Numerical Analysis in Los Angeles, California, where he did extensive programming for the SWAC computer. In 1954 this Institute became part of U.C.L.A. and he put a great deal of energy into the teaching of mathematics and numerical analysis. He also worked on non-numerical problems, such as the tabulation of all possible semi-groups on four elements; at this time, he considered such combinatorial algorithms to be a part of numerical analysis and he regarded automatic programming as another branch. He began to foresee the less obvious implications of programming.

Numerical mathematics is viewed as the analysis of continuous algorithms. Four of the components of numerical mathematics are discussed. These are: foundations (finite precision number systems, computational complexity), synthesis and analysis of algorithms, analysis of error, programs and program libraries. [ABSTRACT FROM AUTHOR]

Setting the Reynolds number equal to zero, in a method for solving the Navier-Stokes equations numerically, results in a fast numerical method for biharmonic problems. The equation is treated as a system of two second order equations and a simple soothing process is essential for convergence. An application is made to a crack-type problem. [ABSTRACT FROM AUTHOR]

In a companion paper to this, "I Methodology and Experiences," the automatic Clenshaw-Curtis quadrature scheme was described and how each quadrature formula used in the scheme requires a cosine transformation of the integrand values was shown. The high cost of these cosine transformations has been a serious drawback in using Clenshaw-Curtis quadrature. Two other problems related to the cosine transformation have also been troublesome. First, ... conventional computation of the cosine transformation by recurrence relation is numerically unstable, particularly at the low frequencies which have the largest effect upon the integral. Second, in case the automatic scheme should require refinement of the sampling, storage is required to save the integrand values after the cosine transformation is computed. This second part of the paper shows how the cosine transformation can be computed by a modification of the fast Fourier transform and all three problems overcome. The modification is also applicable in other circumstances requiring cosine or sine transformations, such as polynomial interpolation through the Chebyshev points. [ABSTRACT FROM AUTHOR]

Clenshaw-Curtis quadrature is a particularly important automatic quadrature scheme for a variety of reasons, especially the high accuracy obtained from relatively few integrand values. However, it has received little use because it requires the computation of a cosine transformation, and the arithmetic cost of this has been prohibitive. This paper is in two parts; a companion paper, "II Computing the Cosine Transformation," shows that this objection can be overcome by computing the cosine transformation by a modification of the fast Fourier transform algorithm. This first part discusses the strategy and various error estimates, and summarizes experience with a particular implementation of the scheme. [ABSTRACT FROM AUTHOR]

Let f have n continuous derivatives on a closed interval [a, b] and let L be a linear functional. The attempt is made to approximate L (f) with L (Q) where Q is a polynomial, approximating f. Algorithms are developed for rapid computation of L (Q) for a wide class of selections of Q which includes the Lagrangian and Hermitian rules as special cases. [ABSTRACT FROM AUTHOR]

In this paper the Ritz-Trefftz algorithm is applied to the computer solution of the state regulator problem. The algorithm represents a modification of the Ritz direct method and is designed to improve the speed of solution and the storage requirements to the point where real-time implementation becomes feasible. The modification is shown to be more stable computationally than the traditional Ritz approach. The first concern of the paper is to describe the algorithm and establish its properties as a valid and useful numerical technique. In particular such useful properties as definiteness and reasonableness of condition are established for the method. The second part of the paper is devoted to a comparison of the new techniques with the standard procedure of numerically integrating a matrix Riccati equation to determine a feedback matrix. The new technique is shown to be significantly faster for comparable accuracy. [ABSTRACT FROM AUTHOR]

The article focuses on the use of subroutines in differential equations. Subroutine integrates a set of up to N ordinary differential equations one step of length H, where H may be specified by the user, but is controlled by the subroutine to control the estimated error within a specified tolerance. A multistep predictor corrector method is used whose order is automatically chosen by the subroutine as the integration proceeds. Either an Adams' method or methods suitable for stiff equations can be selected. The starting procedure is automatic and the information retained by the program about previous steps is stored in such a way as to make the interpolation to a nonmesh point straightforward. The programs may call on up to three subroutines. They are DIFFUN, PEDERV and MATINV. The first, DIFFUN, must be provided always, and it must evaluate the derivatives of the dependent variables Y with respect to the independent variable T and place the results in DY. MATINV must be provided if stiff methods are requested. It should invert the matrix PW which is of size N by N. PERDERV is another optional subroutine called only if the method flag MF is set to 1.

Three cyphers allegedly authored by Thomas Jefferson Beale in 1822 have been the subject of intensive study for over 100 years. Generations of cryptanalysts have expended untold man-years, thus far without success, attempting to decode them; vast armies of fortune hunters and treasure seekers have devoted Herculean labors to digging up the rolling hills of Virginia trying to locate the promised bonanza. The history of pertinent activities would fill volumes, yet serious students of cryptography have always had nagging doubts about the cyphers' authenticity. It has been alleged that the "known solution" to Cypher Number Two; 115, 73, 24, 818, 37, 52, 49,… ("I have deposited in the County of Bedford about four miles from Buford's in an excavation or vault…") with the aid of an unsanitized version of the Declaration of Independence was merely a superb, imaginative, and grandiose hoax perpetrated ages ago for whatever reasons. Modern computer technology could obviously perform signature analyses on the Beale cyphers and could also, in fact, simulate the process of encoding itself so as to yield new clues and deeper insights into their construction. For the benefit of the uninitiated, the encoding method used in the second cypher employs a specified document whose words are simply numbered consecutively, and first letters of these words are sought out at random to match the letters of the cleartext or message. The sequence of numbers corresponding to these matches is then written down as the final code. While primitive, the process has the advantage of relative security until the source document becomes known; at that moment the cypher can be decoded even by second graders. The work now completed with the help of our UNIVAC 1108 includes numerous analytical studies of the Beale cyphers and various types of simulations. For example, we have turned the entire process of simulated encoding by various schemes over to the machine and analyzed the signatures of these synthetic codes; we hove also encoded various messages by hand, using different texts and a variety of methods to obtain their signatures. These simulations provide convincing evidence that the signatures are both process and data dependent; they indicate also very strongly that Mr. Beale's cyphers are for real and that it is merely a matter of time before someone finds the correct source document and locates the right vault in the Commonwealth of Virginia. [ABSTRACT FROM AUTHOR]

Proposes a simple procedure for constructing cubic splines on uniform numerical meshes. Cardinal spline representation using special cubic arcs; Application of the procedure in computer graphics.

Numerical Analysis is the study of methods and procedures used to obtain "approximate solutions" to mathematical problems. Much of the emphasis is on scientific calculation. The difficulties of education in such a broad area center around the question of background and emphasis. The Numerical Analysis program in the Computer Science Department should emphasize an awareness of the problems of computer implementation and experimental procedures. Nevertheless, there is a need for a solid background in applied mathematics. [ABSTRACT FROM AUTHOR]

An algorithm for Filon quadrature is described. Considerable attention has been devoted to an analysis of the round-off and truncation errors. The algorithm includes an automatic error control feature. [ABSTRACT FROM AUTHOR]

The solution of the nonlinear differential equation Y" = F(x, Y, Y') with two-point boundary conditions is opproximated by a quintic or cubic spline function y(x). The method is well suited to nonuniform mesh size and dynamic mesh size allocation. For uniform mesh size h, the error in the quintic spline y(x) is O(h4), with typical error one-third that from Numerov's method. Requiring the differential equation to be satisfied at the mesh points results in a set of difference equations, which are block tridiagonal and so are easily solved by relaxation or other standard methods. [ABSTRACT FROM AUTHOR]

Two recent papers, one by Hansen and one by Hansen and R. R. Smith, have shown how interval Arithmetic (I.A.) can be used effectively to bound errors in matrix computations. In the present paper a method proposed by Hansen and R. R. Smith is compared with straightforward use of I.A. in determinant evaluation. Computational results show the accuracy and running times that can be expected when using I.A. for determinant evaluation. An application using I.A. determinants in a program to test a set of functions to see if they form a Chebyshev system is then presented. [ABSTRACT FROM AUTHOR]

In the numerical integration of an improper integral of the first kind, it is customary to truncate the integral when the change yielded by the last iteration is less than some predetermined constant. The efficiency of such integration schemes can often be improved by use of recent advances in the theory of nonlinear transformations; however, for several important integrals, e.g. integrals whose integrands are rational polynomials these transformations fail to yield much improvement. In this paper, several methods of convergence improvement are developed which greatly improve convergence of some improper integrals, including the integrals of rational polynomials. [ABSTRACT FROM AUTHOR]

It is common to need to integrate numerically functions that diverge somewhere outside the range of integration. Even if the divergence occurs quite far away, integration formulas like Simpson's, that depend on fining a polynomial, usually will be inaccurate: near a pole they will be very bad. A method is described that gives formulas that will integrate functions of this kind accurately if the orders and positions of the poles are known. Explicit formulas are given that are easy to use on an automatic computer. It is shown that they can be used for some other singularities as well as poles. If the integral converges, integration can be carried to the singularity. The accuracy of the integration with a pole of second order is discussed, and, as an example, the new formula is compared with Simpson's in the computation of ∫ 0X sec2 π ξ d ξ, 0 < X < 0.5. In this case the new formula is more accurate for X > 0.1, being 30 times as accurate as Simpson's at X = 0.3, 400 times at X = 0.4 and 104 times at X = 0.47. Thus, the new formulas are useful even far from the pole, while near the pole their advantage is overwhelming. [ABSTRACT FROM AUTHOR]

The method of nested multiplication is commonly used in function evaluation routines to evaluate approximation polynomials. New polynomial evaluation methods have been developed in recent years which require fewer multiplications than nested multiplication and may therefore be preferable for use in function evaluation routines. Although some of these methods do not appear to be practically useful because of rounding-error difficulties, several methods of evaluating low-degree polynomials have been found to be satisfactory. Three such methods are described and illustrated. [ABSTRACT FROM AUTHOR]

Any region can be regarded as a union of maximal neighborhoods of its points, and can be specified by the centers and radii of these neighborhoods; this set is a sort of "skeleton" of the region. The storage required to represent a region in this way is comparable to that required when it is represented by encoding its boundary. Moreover, the skeleton representation seems to have advantages when it is necessary to determine repeatedly whether points are inside or outside the region, or to perform set-theoretic operations on regions. [ABSTRACT FROM AUTHOR]

A procedure is given for continuously computing and monitoring the step size to be used by a self-starting, pth-order numerical integration method to solve an initial value problem. The procedure uses an estimate of the truncation error to calculate the step size. [ABSTRACT FROM AUTHOR]

An algorithm for finding the symbolic factors of multivariate polynomial with integer coefficients is presented. The algorithm is an extension of a technique used by Kronecker in a proof that the prime factoring of any polynomial may be found in a finite number of steps. The algorithm consists of factoring single-variable instances of the given polynomial by Kronecker's method and introducing the remaining variables by interpolation. Techniques for implementing the algorithm and several examples are discussed. The algorithm promises sufficient power to be used efficiently in an online system for symbolic mathematics. [ABSTRACT FROM AUTHOR]

The generalized inverse of a matrix is important in analysis because it provides an extension of the concept of an inverse which applies to all matrices. It also has many applications in numerical analysis, but it is not widely used because the existing algorithms are fairly complicated and require considerable storage space. A simple extension has been found to the conventional orthogonalization method for inverting nonsingular matrices, which gives the generalized inverse with little extra effort and with no additional storage requirements. The algorithm gives the generalized inverse for any m by n matrix A, including the special case when m = n and A is nonsingular and the case when m > n and rank (A) = n. In the first case the algorithm gives the ordinary inverse of A. In the second case the algorithm yields the ordinary least squares transformation matrix [ATA)-1AT and has the advantage of avoiding the loss of significance which results in forming the product AT explicitly. [ABSTRACT FROM AUTHOR]

A process for fitting a curve to approximate data and the problem it creates for the engineer-programmer is defined. An approach has also been defined and a system has been written for the SRU 1107 to mechanize a major portion of this process. The techniques developed to accomplish the mechanization are largely empirical, and are dependent for their information only on the actual data points. [ABSTRACT FROM AUTHOR]

A study has been made to determine which methods of numerical integration require the least computation time for a given amount of truncation error when applied to a particular system of ordinary differential equations where function evaluations are relatively trivial. Recent methods due to Butcher and Gear are compared with classic Runge-Kutta Kutta-Nyström and Adams methods. Some of the newer one-step methods due to Butcher are found to be slightly superior, but no one method is found to have any great advantage over the others in the application to this particular problem. [ABSTRACT FROM AUTHOR]

An ALGOL procedure is given for automatically generating formulas for matrix elements arising in the variational solution of the Schrödinger equation for many-electron systems. [ABSTRACT FROM AUTHOR]

The article discusses various algorithms along with their derivation procedure and comments on each algorithm. It tests the 153 GOMORY algorithm and presents an improved version of it after testing, and submitting remarks on the previous algorithm. It evaluates a function by polynomial interpolation, through Neville's process in a table of values and attempts to find out precedence functions with the help of algorithms. It also presents an algorithm on generating pseudo-random numbers from random numbers.

A large class of problems leading to digital computer processing can be formulated in terms of the numerical solution of systems of ordinary differential equations. Powerful methods are in existence for the solution of such systems. A good general purpose routine for the solution of such systems furnishes a powerful tool for processing many problems. This is true from the point of view of ease of programming, ease of debugging, and minimization of computer time. A number of examples are discussed in detail. [ABSTRACT FROM AUTHOR]

A method which finds simultaneously all the zeros of a polynomial, developed by H. Rutishauser, has been tested on a number of polynomials with real coefficients. This slowly converging method (the Quotient-Difference (Q-D) algorithm) provides starting values for a Newton or a Bairstow algorithm for more rapid convergence. Necessary and sufficient conditions for the existence of the Q-D scheme ore not completely known; however, failure may occur when zeros have equal, or nearly equal magnitudes. Success was achieved, in most of the cases tried, with the failures usually traceable to the equal magnitude difficulty. In some cases, computer roundoff may result in errors which spoil the scheme. Even if the Q-D algorithm does not give all the zeros, it will usually find a majority of them. [ABSTRACT FROM AUTHOR]

The article offers information on the Self-Judgment Method of curve fitting including computational and mathematical procedures used to eliminate bias in the Self-Judgment Principle (SJP). Also discussed are the inadequacies that occur in the statistical and graphical methods and the concept of Self-Judgment Method, SJP, instrument reliability factors, maximum permitted deviation, set of conjugate data, maximum permitted error, set of conjugate information, error zone, and actual error. The new method presented in the study is comprised of eight programs that are integrated into a single system for processing and communicating numerical experimental information.

The article presents an analysis about game of solitaire and some variations and transformations. The present several versions of solitaire are on sale in the country under various trade names with some pegs that are moved from hole to hole and some with marbles that rest in circular depressions. The advanced students of solitaire have gone to fantastic length in setting themselves unusual tacks.

The article presents a kind of entertainment that involves the calculus of finite differences. It is a branch of mathematics that at times could be highly useful, even if it is not known too well. The calculus of finite differences originated in the Methodus Incrementorum which is a treatise published by an English mathematician. Students of recreational mathematics could avail of the elementary procedures in the calculus of finite differences that may be useful in the future.

The article presents an imaginary dialogue on mathematic tricks based on mathematical principles published in the August 1960 issue of "Scientific American."

The article presents mathematical games involving problems of probability and ambiguity using geometrical solutions. One problem illustrated here is the probability of putting together a stick which was broken at random into three pieces to form a triangle. The second problem pertains to the probability of the length of the side of a chord drawn at random inside a triangle. The last problem drawn involves a randomizing procedure to find the correct data.

The article focuses on the Monte Carlo method, used to predict the outcome of a series of events, each of which has its own probability. This method is a probability theory, which is developed from studies of gambling games. It tries to use probability to find an answer to a physical question often having no relation to probability. Mathematicians who originated the probability theory derived their equations from theoretical questions based on the phenomenon of chance.

This article focuses on the comprehensive stock value tables, which are of especial interest to managers of trust and other institutional funds, as well as to private investors. In practical use the tables of stock values are designed to provide information similar to that given by tables of values for bonds. As practical tools, these tables can also help aid the security analyst in making explicit conclusions regarding the future prospects of a stock being analyzed. The time span covered is from one to any greater number of years, and the repetitive use of the tables, or interpolation will permit the user to make calculations for any desired number of years.