LIBRARY OF THE
UNIVERSITY OF ILLINOIS
AT URBANA-CHAMPAIGN
5I0.84
y^o.8l-90
"PsiNEEm^
AUG 51976
I'he person charging this material is re- sponsible for its return to the hbrary from which it was withdrawn on or before the Latest Date stamped below.
Theft, mutilation, and underlining of books are reasons for disciplinary action and may result in dismissal from the University.
UNIVERSITY OF ILLINOIS LIBRARY AT URBAfclA-CHAMPAIGN
lllli
•iwa^isil^S'
i^yy^ii
L161 — O-1096
Digitized by the Internet Archive
in 2012 with funding from
University of Illinois Urbana-Champaign
http://archive.org/details/computationalmat90belf
510.81; U63c no. 90
EnKin.
FERENCE ROOM
ENGWSERING UBRARy mmRsljy OF ILLINOIS
ed Computa
UNlVERSlW OF ItLINOrS At URBANA-CHAMPAIGN
URBANA. ILLINOIS 61801
BIBLIOGRAPHIC DATA SHEET
1. Report No.
UIUC-CAC-DN-T3-90
3. Recipient's Accession No.
4. Title and Subtitle
COMPUTATIONAL MATHEMATICS ABSTRACTS
7. Author(s) Edited Dy: (ieneva Bej.rora, jonatnan Lermit, George Purdy, and Ahmed Sameh
5. Report Date
October 1973
8. Performing Organization Rept.
No. CAC-90
9. Performing Organization Name and Address
Center for Advanced Computation University of Illinois at Urbana-Champaign Urbana, 111. 618OI
10. Project/Task/Work Unit No.
11. Contract/Grant No.
DAHCOU-72-C-OOOI
12. Sponsoring Organization Name and Address
U.S. Army Research Office
Duke Station
Durham, North Carolina
13. Type of Report & Period Covered
Re search- interim
14.
15. Supplementary Notes
16. Abstracts
None
17. Key Words and Document Analysis. 17a. Descriptors
Numerical Analysis Graph Theory Mathematical Programming
17b. Identifiers/Open-Ended Terms
17c. COSATI Field/Group
18. Availability Statement ^^ restriction On distribution
ft-vailable from the National Technical Information Service.
FORM NTIS-3S (REV. 3-72)
19. Security Class (This Report)
VNCLASSIFIED
20. Security Class (This Page
UNCLASSIFIED
21. No. of Paees
^
22. Price
USCOMM-DC 14952-P72
CAC DocTjment No. 90
Computat lonal Matheinatics Abstracts
Edited by
Geneva Belford Jonathan Lermit George Purdy Ahmed Sameh
Applied Mathematics Group Center for Advanced Computation University of Illinois at Urban a- Champaign Urbana, Illinois 618OI
October 1973
This work was supported in part by the Advanced Research Projects Agency of the Department of Defense and was monitored by the U.S. Array Research Office-Durham under Contract No. DAHC0U-T2-C-0001.
!^iii^^^^
TABLE OF CONTENTS
Page
ERROR ANALYSIS 1
FUNCTION EVALUATION AND COMPLEXITY THEORY k
APPROXIMATION 6
LINEAR ALGEBRA. 10
NONLINEAR EQUATIONS , 15
QUADRATURE - l6
ORDINARY DIFFERENTIAL EQUATIONS l8
PARTIAL DIFFERENTIAL EQUATIONS 21
FUNCTIONAL EQUATIONS 22
OPTIMIZATION 22
ROOT FINDING , 25
GRAPH ALGORITHMS. 26
MISCELLANEOUS 27
KEY TO REPORT SOURCES 29
ERROR MALYSIS
An Error Analysis of a Method for Solving Matrix Equations by C. C. Paige
Let B = [L 0]Q be a decomposition of the m by n matrix B of rank m such that L is lower triangular and Q is orthonormal. It is possible to solve Bx, = b using L but not Q in the following manner: solve Ly = b , solve L'^w = y , and form x = B w. It is shown that the numerical stability of this method is comparable to that of the method which uses Q. This is important for some methods used in mathematical programming where B is very large and sparse and Q is discarded to save storage.
STAN-CS-T2-29T June 1972
Rundungsfehleranalyse einiger Verfahren zur Summation endlicher Summen by Arnold Neumaier
Der bei einer Summation auftretende Rundungsfehler kann als Mag fur die Gute des verwendeten Verfahrens gelten. Im folgenden werden fllr mehrere Suiranierungs verfahren, unter anderem fur das "ubliche" und das Kahan-Babuska-Verfahren, a-priori-Schranken fur diese Rundungsfehler S'^gegeben und miteinander verglichen.
PRAK 73/1 1973 28 pages
Fehlerabschatzung bei nichtlinearen Gleichungssystemen by Rudolf Krawczyk
Fiir eine Losimg x* eines nichtlinearen Gleichungssystems f(x) = 0 wird eine Fehlerabschatzung bezuglich einer Halbordn\mg angegeben. Gleichzeitig kann auch eine Aussage uber die Eindeutigkeit der Losung gemacht werden. Die Ergebnisse werden auf Differenzengleichxmgen und auf ein algebraisches Eigenwert problem angewandt .
PRAK 73/3 1973 ik pages
Komplexe Kreisarithmetik by Norbert Krier
In dieser Arbeit werden Kreise der Gau3schen Zahlenebene als kom- plexe Fehlerschrankenzahlen betrachtet. Da aus arithmetischen Verkniipfungen solcher Kreise Mengen hervorgehen, die im allgemeinen keine Kreise sind, werden diese Verkniipfungsmengen diirch Kreise abgeschatzt. Es wird eine opt imal-abs chat zende Kreisarithmetik entwickelt sowie eine auf dem Permanenzprinzip aufbauende, zentrierte Kreisarithmetik angegeben.
Um auch mit Mengen reeller oder imaginarer Zahlen rechnen zu kbnnen, wird die Menge der komplexen Kreise eiveitert, indem Intervalle der reellen sowie der imaginaren Achse als spezielle Kreiszahlen aufgefasst werden. Dadiorch kann ausserdem eine fiir achsenparallele Rechtecke der komplexen Ebene erklarte Intervallrechnung mit Kreiszahlen nachvollzogen werden.
PEAK 73/2 1973 117 pages
Approximation durch Intervallfunktionen by R. Krawczyk
Die bekannte Appro ximat ions aufgabe, eine gegebene Funktion f(x) mit Hilfe eines Fimktionensystems zu approximleren, wird erweitert. Es wird eine Intervall funktion (Funktion mit Intervallkoeffizienten) derart bestimmt, dass die zu appro ximierende Funktion in dem diirch die Intervall funktion definierten Streifen liegt. Diese Methode wird anschliessend auf den diskreten Fall der Ausgleichung von n gegebenen F-unktionswerten angewandt, und zwar 1. mit Hilfe eines Intervallpolynoms , 2. durch eine trigonometrische Intervall funktion. Insbesondere wird fur den Spezialfall der Interpolation die Fehlerabhangigkeit \intersucht . Ftir eine Anzahl von Beispielen wird derjenige Grad der Ausgleichs funktion ermittelt, fur welchen der entsprechende Streifen am schmalsten ist .
KARL 69/7 1969 12 pages
On the Computation of Rigorous Boirnds for the Solutions of Linear Integral Equations with the Aid of Interval Arithmetic by C. W. Cryer
A method is given for approximately solving linear Fredholm integral equations of the second kind with non-negative kernels. The basis of the method is the construction of piecewise-polynomial degenerate kernels which bound the given kernel. The method is a generalization of a method suggested by Gerberich. When implemented on a computer, interval arithmetic is used so that rigorous bounds for the solution of the integral equations are obtained.
The method is applied to two problems: the equation considered by Gerberich; and the equation of Love which arises in connection with the problem of determining the capacity of a circular plate condenser.
WIS 70 1969 ^0 pages
Iterationsverfahren in halbgeordneten Raumen by R. Krawczyk
In der vorliegenden Arbeit werden Iterationsverfahren zur Berechnung einer Folge von Intervallen in halbgeordneten linearen Raumen
"behandelt. Es verden atstrakte Satze ziir Einschliessung xind Existenz einer Losung einer Operatorgleich-ung imd zur Konvergenz der Intervallfolgen formuliert. Im zvelten Tell dieser Arbeit warden diese Satze aui* eine Anzahl von Beispielen: Losung einer Gleichimg, N-ullstellenbestiimnung einer analytischen F-unktion, Eigenvert- und Eigenvektorbestimmung von Matrizen, Integralgleichung angewandt.
KARL 70/2 April 1970 30 pages
Bibliography on Proving the Correctness of Computer Programs — Addition No. 1 by Ralph L. London
The continued research activity in proving the correctness of computer programs and the widespread interest in my previous program proving bibliography (London 1970a) encourage me to compile these additional updating citations. The selection criteria remain essentially unchanged; only the form of the citation is trivially changed. As before, I wo"uld be most interested in learning of corrections and additional citations to update matters.
WIS-10i| December 1970 8 pages
FUNCTION EVALUATION AND COMPLEXITY THEORY
Computational Complexity of One-Point and Multipoint Iteration by H. T. Kung and J. F. Traub
Let (|) "be an iteration for ^proximating the solution of a problem f. We define a new efficiency measure e((|), f). For a given problem f, we define the optimal efficiency E(f) and establish lower and upper boimds for E(f) with respect to different families of iterations. We conjecture an upper bound on E(f) for any iteration without memory.
CMU No # April 1973
Fast Evaluation and Interpolation by H. T. Kung
A method for dividing a polynomial of degree (2n - l) by a pre- computed nth degree polynomial in 0(n log n) arithmetic operations is given, This is used to prove that the evaluation of an nth degree polynomial at n+1 arbitrary points can be done in 0(n log n) arithmetic operations, and consequently, its dual problem, interpolation of an nth degree polynomial from n+1 arbitrary points can be performed in 0(n log n) arithmetic operations. The best previously known algorithms required 0(n log n) arithmetic operations.
CMU Wo # January 1973
Optimal Order of One-Point and Multipoint Iteration by H. T. Kung and J. F. Traub
The problem is to calculate a simple zero of a non-linear function f by iteration. We exhibit a family of iterations of order 2 which use
n evaluations of f and no derivative evaluations, as well as a second family of iterations of order 2 based on n - 1 evaluations of f and one of f.
In particular, with four evaluations we construct an iteration of eighth order. The best previous result for four evaluations was fifth order.
We prove that the optimal order of one general class of multipoint iterations is 2 and that an upper bound on the order of a multipoint
iteration based on n evaluations of f (no derivatives) is 2 .
CONJECTURE. A multipoint iteration without memory based on n evaluations has optimal order 2
CMU No # February 1973
The Computational Complexity of Algebraic Numbers by H. T. Kung
Let {x.} be a sequence approximating an algebraic n-umber a of
degree r, and let x. ,^ = tf)(x.,x. ^,...,x. -,.,), for some rational fimction 4 " 1+1 1 1-1 i-d+1 ^
with integral coefficients. Let M denote the number of miiltipli cat ions or divisions needed to compute (^ and let M denote the number of multiplications
or divisions, except by constants, needed to compute <^. Define the multipli-
loggP loggP
cation efficiency measure of {x. } as E({x })= — — — or as E({x. }) = — - — ,
1 1 ' M 1 M
where p is the order of convergence of {x.}. Kung [l] showed that E({x. }) <_ 1 or equivalently, M >_ log p. In this paper we show that (i) M >_ log2[r([pl-l) + 1] - 1; (ii) if E({x.}) = 1 then a is a rational number; (iii) if E({x.}) = 1 then a is a rational or quadratic irrational niimber. This settles the question of when the multiplication efficiency E({x.}) or E({x.}) achieves its optimal value of unity.
CMU No # March 1973
Diagonal Theorems for Random Access Machines by Stephen A. Cook and Robert A. Reckhow
Turing Machines have often been criticized for not being good models for real computing machines. In this report we describe the RAM, an abstract model of a (fixed-program) random access computer. A unique featvire of the RAM is that the execution time of an instruction depends on the size of the numbers being manipulated. We then describe- RAM-ALGOL, an ALGOL 60-like programming language for RAM's. This language helps to clarify constructive proofs of theorems involving RAM's. Using RAM-ALGOL programs we show that the computing speeds of fixed-program and stored-program random access machines and Turing Machines are not too widely divergent.
Our main result states that if T2(n) is a function such that there is a RAM that computers T2(n) in time 0(T2(n) j, and if T-]_(n) is any function
inf ^1^^) such that 7;r-7 — r = 0 , then there is a set S that can be recognized by
n-x» T2(n) ' ?= j'
some RAM in time 0(T2(n)) but no RAM recognizes S in time 0(T-j_(n)). This is a sharper diagonal res\ilt than has been obtained for Tioring Machines.
TOR-1+2 J-une 1972 ll^l
pages
APPROXIMATION
Korovkin Sets (Sets of Convergence) by G. G. Lorentz
This report treats sets of convergence of positive operators, and of contractions, on the space of continuoTis fiinctions, and on other Banach function spaces. Chapter 3 of the report is entirely new, while the other two chapters present the existing theory in a new and more general setting.
CNA-59 September 1972
An Application of the Theory of Approximation by Families with a Fixed Point by G. G. Belford
Recently developed theorems characterizing best uniform approximations from a family with a fixed point are shown to be useful in the estimation of errors in computational techniques for solving linear algebraic equations. Specifically, a gap in the proof of a published theorem is filled in.
CAC TM No. 11 May 1973 6 pages
Simultaneous Fitting of Exponential Decay Curves by G. G. Belford
This paper deals with characterization of best approximations to vector-valued functions. The approximations are themselves vector-valued functions with components depending nonlinearly on the approximation para- meters. The constraint is imposed that certain of the parameters should be identical for all components. An application to exponential approximation is discussed in some detail.
CAC No. 6l April 1, 1973 30 pages
The Cholesky Factorization for Derivative-Free Nonlinear Least Squares by Richard H. Bartels
In a previous technical report the author presented an algorithm for minimizing sums of squares of nonlinear functions in several variables without the use of derivatives. A subsection of this algorithm required that the least-squares solution to an overdetermined linear system be found. The implementation which was presented in the report accomplished this via the QR factorization of the system's matrix. However, if the number of functions in a nonlinear least-squares problem greatly exceeds the number of variables involved, the matrix Q of the factorization requires a disproportionate amount of storage space. To overcome this we present an alternate imple-
mentation In which the linear least-squares subproblem is solved via the Cholesky factorization of the normal equation. A FORTRAN program -with test results is included.
CM-6i| March 1973 Program Incl.
Constructive Aspects of Discrete Polynomial Spline Functions by L. L. Schumaker
Discrete polynomial splines are vectors consisting of pieces of polynomials tied together on knot intervals. They arise in optimal siammation formulae and are expected to have applications to approximate solution of discrete operator equations. Here ve obtain representations and local Support bases (with recursions for them), discuss the total posit ivity of a fundamental Green's function, and give certain basic interpolation resiilts.
CNA-62 January 1973 I8 pages
On the Convergence of Cubic Interpolating Splines by Tom Lyche and L. L. Schumaker
Given a sequence of partitions A = (O = x <x^<...<x = l) and a
n o 1 n
corresponding sequence of cubic spline projections P , we find properties of
A which guarantee that f - P f -K) as n->°° for arbitrary continuous n ' ' n ' '
functions on [O, l]. Results are obtained for cubic natural and cubic Type-I spline interpolation.
CNA-61 September 1972
Computation of g-Splines Via a Factorization Method by Harold D. Eidson and L. L. Schumaker
Fortran subroutines are presented for the purpose of computing and evaluating g-splines interpolating Hermit e-Birkhoff data. The subroutines are based on a factorization method for computing g-splines discussed by Munteanu and Schumaker (CNA 25, Center for Numerical Analysis, UT Austin, 1971)
CNA-60 September 1972 Program Incl.
Uber A-usgleichs-Splines by Klaus Bohmer
Combining the intrinsic properties of splines and the method of least squares we discuss an extremal problem. We-show the existence -of a
solution and give the conditions for the uniqueness. For g -^ 0 resp. g ->-
we receive the usual interpolation spline resp. a solution of a problem
minimizing a sum of squares. We conclude in characterizing the solutions for EHB- Interpolation problems.
KARL 71/5 September 1971 11 pages
On Best Simultaneoiis Approximation in Normed Linear Spaces by D. S. Goel, A.S.B. Holland, C. Nasim, and B. N. Sahney
Let S be a non-empty family of real valued continuous functions on [a, 3]. Diaz and McLaughlin [l], [2], and Dunham [3] have considered the problem of simultaneously approximating two continuous functions f and f by elements of S. If | | • | | denotes the supremum norm, then the problem is to find an element s* e S, if it exists, for which
max ( I I f - s* I I , I I f - s* I I ) = inf max ( | | f - s | | , | | f - s | | ) .
s e S The above problem is studied in general normed linear spaces.
CAL-186 March 1973 7 pages
Best Approximation by a Saturation Class of Polynomial Operators by D. S. Goel, A.S.B. Holland, C. Nasim and B. N. Sahney
In this paper we prove that a method of summation involving Norlund operators is saturated with the order Pn and related resiolts.
Pn
CAL-191 June 1973 10 pages
Characterisation of an Element of Best 1 -Simultaneous Approximation by D. S. Goel, A.S.B. Holland, C Nasim, and B. N. Sahney
Let X be a normed linear space and K a subset of X. In CAL-186 we have considered the problem of best simiiltaneous approximation of two elements xi,X2 e X from the elements of K.
The object of the present paper is to give a characterisation of an element of best simultaneous approximation under a more general definition of simultaneous approximation.
CAL-188 May 1973 6 pages
Splines with Non-Negative B-Spline Coefficients "by C. de Boor and James W. Daniel
We consider the question of the approximation of non-negative functions by non-negative splines of order k (degree < k) compared with approximation by that subclass of non-negative splines of order k consisting of all those whose B-spline coefficients are non-negative; while approximation by the former gives errors of order h-^, the latter may yield only h^. These results are related to certain facts about quasi-interpolants.
CNA-65 March 1973 5 pages
The Continuity of Metric Projections as Functions of the Data by James W. Daniel
Let X be a Hilbert space, and consider the point xq minimizing, for a given f in X, the distance | |x - f | | as x ranges over a polyhedral set C defined by a finite niomber of real -valued equalities and inequalities. We w^sh to see how xq varies when f and C vary. It is easy to see that xq is Holder continuous with exponent 1/2 in its dependence on these parameters; this estimate is in general sharp. We show, however, that in certain cases XQ is actually Lipschitz continuoiis in its dependence on the parameters which are used to define the set C.
CNA-68 April 1973 9 pages
LINEAR ALGEBRA.
A Fast Method for Solving a Class of Tri-Diagonal Linear Systems "by Michael A. Malcolm and John Palmer
The solution of linear systems having real, symmetric, diagonally dominant, tri diagonal coefficient matrices vith constant diagonals is considered. It is proved that the diagonals of the LU decomposition of the coefficient matrix rapidly converge to full floating-point precision. It is also proved that the computed LU decomposition converges when floating- point arithmetic is used and that the limits of the LU diagonals using floating point are roughly within machine precision of the limits using real arithmetic. This fact is exploited to reduce the niimber of floating-point operations required to solve a linear system from 8n-7 to 5n+2k-3, where k is much less than n, the order of the matrix. If the elements of the sub- and super diagonals are 1, then only i+n+2k-3 operations are needed. The entire LU decomposition takes k words of storage, and considerable savings in array subscripting are achieved. Upper and lower boxinds on k are obtained in terms of the ratio of the coefficient matrix diagonal constants and para- meters of the floating-point number system.
Various generalization of these results are discussed.
STAU-CS-T2-323 November 1972 l6 pages
Iterative Solution of Tridi agonal Systems on Parallel or Vector Computers by J. F. Traub
We study the iterative solution of a tridiagonal linear system of size m on a parallel or vector computer. Such systems arise commonly in the numerical solution of partial differential equations.
The Gauss algorithm takes time linear in m. We introduce a Parallel Gauss iteration and show it can be used to solve a tridiagonal system in time independent of m. Furthermore, the error norm is reduced at each iteration step. A Parallel LP decomposition is also defined.
Parallel Gauss is based on "multiplicative splitting". We intro- duce parallel algorithms based on "additive splitting". These are Jacobi, JOR, Parallel Gauss-Seidel, and Parallel SOR.
We compare these parallel algorithms on a model problem and conclude that JOR, Gauss-Seidel, and SOR are not competitive. Jacobi is best if there is a "large amount" of diagonal dominance while Parallel Gauss is best if there is only "limited" diagonal dominance.
CMU No # January 1973 ^2 pages
10
Methods for Modifying Matrix Factorizations
ty P. E. Gill, G. H. Golub, ¥. Murray, and M. A. Saunders
In recent years several algorithms have appeared for modifying the factors of a matrix following a rank-one change. These methods have always been given in the context of specific applications and this has probably inhibited their use over a wider field. In this report several methods are described for modifying Cholesky factors. Some of these have been published previously while others appear for the first time. In addition, a new algorithm is presented for modifying the complete orthogonal factor- ization of a general matrix, from which the conventional QR factors are obtained as a special case. A uniform notation has been used and emphasis has been placed on illustrating the similarity between different methods.
STAN-CS-72-322 November 1972
Modifying Pivot Elements in Gaussian Elimination by G. ¥. Stewart
The rounding-error analysis of Gaussian elimination shows that the method is stable only when the elements of the matrix do not grow excessively in the course of the reduction. Usually such growth is prevented by inter- changing rows and columns of the matrix so that the pivot element is acceptably large. In this paper the alternative of simply altering the pivot element is examined. The alteration, which amounts to a rank one modification of the matrix, is undone at a later stage by means of the well-known formula for the inverse of a modified matrix. The technique should prove useful in applications in which the pivoting strategy has been fixed, say to preserve Spars eness in the reduction.
CMU No # March 1973
The SAC-1 Polynomial Linear Algebra System by G. E. Collins and M. T. McClellan
This system is the tenth in a series of subsystems comprising the SAC-1 System for Symbolic and Algebraic Calculation. The present sub- system consists of programs implementing modular algorithms for linear equations solution, matrix inversion, determinant calculation, null space basis generation, and matrix miiltipli cation, all for matrices with integer or polynomial entries. For each program in the system is given a fimctional specification, an algorithm description, an analytical computing time, and a Fortran program listing. Empirically observed computing times for some of the key programs are presented. Also, a test program is supplied as an aid in implementing the system and to illustrate its use.
WIS-15^ April 1972 Program Incl .
11
A Determinant Theorem with Application to Parallel Algorithms "by Don Heller
We state and pix)ve an expansion theorem for the determinant of any Hessenherg matrix. The expansion is expressed as a vector-matrix-vector product which can he efficiently evaluated on a parallel machine. We con- sider the computation of the first N terms of a sequence defined by a general linear recurrence. On a sequential machine this problem is 0(N'^), with N processors it is 0(N), and with 0(N ) processors it is O(log^N) using our expansion. Other applications include locating roots of analytic functions and proving doubling formulas for linear reciorrences with constant coefficients.
CMU No # March 1973
On a Characterization of the Best I Scaling of a Matrix by G. H. Golub and J. M. Varah
This paper is concerned with best two-sided scaling of a general square matrix, and in particular with a certain characterization of that best scaling: namely that the first and last singular vectors (on left and right) of the scaled matrix have components of equal modulus. Necessity, sufficiency, and its relation with other characterizations are discussed. Then the problem of best scaling for rectangular matrices is introduced and a conjecture made regarding a possible best scaling. The conjectiore is verified for some special cases.
STAN-CS-T2-319 October 1972
The LU-Factorization of Totally Positive Matrices by Colin W. Cryer
An n X n real matrix A is an STP (strictly totally positive) matrix if all its minors are strictly positive. An n x n real triangular matrix A is a ASTP matrix if all its non-trivial minors are strictly positive. It is proved that A is an STP matrix iff A = LU where L is a lower triangular matrix, U is an upper triangiolar matrix, and both L and U are ASTP matrices. Several related results are proved. These results lead to simple proofs of many of the determinantal properties of STP matrices.
WIS-131 December 1971 23 pages
Convergent Generalized Monotone Splitting of Matrices by 0. L. Mangasarian
Let B and T be n x n real matrices and r an n-vector and consider the system u = BTu + r. A new sufficient condition is given for the existence
12
of a solution and convergence of a monotone process to a solution. The mono- tone process is a generalization of the Collatz-Schroder procedure.
WIS-105
December 1970
11 pages
Monotone Splitting of Matrices hy 0.- L. Mangasarian
Given the iterative scheme x = BT x + r where B, T are fixed
n X n real matrices, r a fixed real n-vector and x a real n-vector we
investigate the convergence and monotonicity of schemes of the type
V
i+1
w
i+1
|
•^ |
||
|
B |
0 |
|
|
0 |
B |
|
-\ |
— • — < |
r ~] |
||
|
^11 |
-^12 |
1 V |
+ |
r |
|
^21 |
S22_ |
i w |
r |
where S. , are n x n real matrices related to T. The n-vector iterates v ,w bracket in a certain sense solutions x of x = BTx+r. We also give necessary and sufficient conditions for the monotonicity of the original iterative scheme itself x = BTx + r. This leads to monotonicity results for classicial Iterative schemes such as the Jacobi, Gauss-Seidel and successive overrelaxation methods.
WIS-106
December 1970
19 pages
Zeros of X-Matrices, A Survey by Jon Rokne
We present a survey of results for computing zeros of X-matrices and matrix polynomials. Most of the results are not new, except for the results in section 3. The results that are collected here do not seem to "be known to a large audience, however.
CAL-181
March 1973
17 pages
13
Characterizations of Real Matrices of Monotone Kind by 0. L. Mangasarian
An m by n real matrix A is said to be of monotone kind if
(l) Ax ^ 0 ■ ■> x^O .
Collatz treats square matrices of monotone kind and shows that for such matrices the above implication is equivalent to: A exists and A~l >_ 0.
It is the piorpose of this note to generalize Collatz 's result to rectangular matrices, and also to show that, for the general rectangular case, a matrix of monotone kind can be further characterized as one for which the convex conical hull of the rows contains the nonnegative orthant.
WIS-15 February 1968 8 pages
A Linear Programming Implementation by Jonathan Lermit
This document discusses the implementation of a recently developed version of the simplex method for linear programming using Cholesky factorization (where the basis is expressed as a product of a lower tri- angular and an orthogonal matrix) rather than the more usual product form of the inverse. Storage schemes for the resulting lower triangular matrix suitable for an array processor (the orthogonal matrix is not retained) and necessaiy adaptations to the algorithm when the constraint matrix is expressed as a linear operator are also discussed.
CAC No. h6 May 7, 1973 30 pages
Fehlerabs chat z long reeller Eigenwerte und Eigenvektoren von Matrizen by R. Krawczyk
Reelle einfache Eigenwerte und die dazugehorigen reellen Eigen- vektoren einer quadratischen Matrix werden mit Hilfe einer Intervallarithmetik \anter Berucksichtigung aller Run dungs fehler abgeschatzt. Fur diese Fehler- abschatzTing benbtigt man als Daten die Nah e rungs we rte eines Eigenwertes und des entsprechenden Eigenvektors , welche man sich nach irgendeinem numerischen Verfahren verschafft hat. Als ergebnis erhalt man ein Intervall und einen Intervallvektor, welche den exakten Eigenwert bzw. den exakten Eigenvektor, enthalten. Gleichzeitig ergibt sich daraus auch die Existenz eines reellen Eigenwertes .
KARL 68/5 March 1968 15 pages
Verbesserung von Schranken fur Eigenwerte und Eigenvektoren von Matrizen by R. Krawczyk
Es wird ein Verfahren beschrieben, wie man die Fehlerschranken eines Eigenwertes und des zugeordneten Eigenvektors einer Matrix mit Hilfe
lU
elner Intervallarithmetik verbessern kann. Dabei wird dem komplexen Eigen- wertproblem n-ter Ordnung ein reelles nichtlineares Gleichungssystem der OrdnTong n+2 zugeordnet, so dass nur ein geringer Mehraufwand an Rechenarbeit im Vergleich zur Einschliessung reeller Eigenwerte erforderlich ist. Die Konvergenz der Iterationsfolge hangt im wesentllchen von den Anfangs-Schranken des Eigenwertes imd nicht von den Schranken des Eigenvektors ab.
KARL 69/5 April I969 8 pages
Einschrankung von Eigenwerten reellsymmetrischer Matrizen by Oswald Kreg
Im folgenden wird ein Algorithmus angegeben, der ausgehend von einem Einschliegungssatz von Collatz die Einschliegung von Eigenwerten einer reellsymmetrischen Matrix A leistet.
Ntunerische Schwierigkeiten , die auftreten konnen, wenn die vorge- gebene Waherung z fur einen Eigenvektor Komponenten enthalt , die Null oder sehr klein sind, werden durch eine Ahnlichkeitstransformation beseitigt.
KARL 70/10 August 19T0 2U pages
NONLINEAR EQUATIONS
The Convergence of Multipoint Iterations to Multiple Zeros "by G. W. Stewart
This paper fills a gap in the theory of multipoint iteration func- tion exemplified by the question: how does the secant method converge to a mioltiple zero. A general theory of the linear convergence of multipoint iterations is developed, and it is shown that two broad classes of iterative methods fit this theory- The results of numerical investigations based on the theoiy suggest that Muller's method applied to a multiple zero will inevitably produce complex iterates.
CMU No.# Januaiy 1973
Some Iterations for Factoring a Polynomial II. A Generalization of the Secant Method by G. ¥. Stewart
This paper describes an iterative method for factoring a polynomial that bears the same relation to Bairstow's method as the secant method in a
15
single variable bears to Newton's method. Like the secant method, the generalized secant method requires only one function evaluation for each iteration, and like the secant method it converges to a simple factor with order (l+/5")/2.
CMU No. # February 1973
A Quadratically Convergent Lagrangian Algorithm for Nonlinear Constraints by J. B. Rosen and J. L. Kreuser
An algorithm for the nonlinearly constrained optimization problem is presented. The algorithm consists of a sequence of major iterations generated by linearizing each nonlinear constraint about the current point, and adding to the objective function a linear penalty for each nonlinear constraint. The resulting fimction is essentially the Lagrangian. A Kantorovich-type theorem is given, showing quadratic convergence in terms of major iterations. This theorem insures quadratic convergence if the starting point (or any subsequent point) satisfies a condition which can be tested using computable bounds on the objective and constraint functions.
WIS-166 November 1972 33 pages
QUADRATURE
Computing Integrals Involving B-Splines by Means of Specialized Gaussian
Quadrature R-uLes
by J. L. Phillips and R. J. Hanson
In this paper a technique and algorithm are given to efficiently compute integrals involving products of splines and general functions.
Using the B-Splines as weighting functions, we show how to gener- ate Gaussian quadrature rules for approximating the integrals.
Tables of abscissas and weights, together with procedures for their use, are given for the important special case in which the interval breakpoints of the B-Splines are equally spaced.
WSU-73001 1973
16
On Weight Functions for Chebyshev Quadrature by K. Salkauskas
The Chebyshev quadrature problem is to determine real k and real,
distinct t^ ,...,t in [0, l] such that l,n n,n
(1.1) / w(t)f(t)dt = k I f(t. ^), V f e P^, n = 1,2,... . 0 1=1 '
1
I 0
Here w is a given weight function that is normally taken to be non-negative
on [0, l]. It is well known that if w = 1, the problem cajinot be solved with
real {t }^ when n = 8 or n > 9. On the other hand, for (l.l) transfomied l,n 1=1
to the Interval [-1, l], Ullman [5] has found a one-parameter family of weight functions of the form
f^\ 1 1 + 2at 111
w(t) = 2"Y72 ' 2 ' 1^' -h •>
with the property that the problem has solutions for all n. When a = 0, one recovers the classical Chebyshev weight function, for which the Gauss and Chebyshev quadrature formulas coincide.
The purpose of this paper is to show that weight functions for which the Chebyshev problem is solvable are scarce in a probabilistic sense.
CAL-1T5 January 1973 9 pages
IT
ORDINARY DIFFERENTIAL EQUATIONS
Necessary and Sufficient Criteria for A-Statility of Linear Mijlti-Step Integration Formulae by Colin W. Cryer
k . k
Let p(^) = 2 o' . S and a(5) = I 3 . C "be the characteristic j=0 ^ j=0 J
polynomials of a linear multi-step method for the n-umerical solution of an
initial value problem for ordinary differential equations. It is shown
that the method is A-stable iff all the following conditions hold:
(i) & ^ 0; (il) Re[p(C)a(?)J >_ 0 for |c| =1; (iii) P and a satisfy the
root condition, that is, their zeros lie inside or on the unit circle and
any zeros on the unit circle are simple. For the case when p and a have
integer coefficients, a program has been developed which uses the SAC-1
system (system for Symbolic and Algebraic Calculations, version (l))
determine whether the multi-step method (p,a) is A-stable.
WIS-IUT March 1972 36 pages
18
A Proof of the Instability of Backward-Difference Multistep Methods for the Numerical Integration of Ordinary Differential Equations by Colin ¥. Cryer
It is shown that the backward difference m\iltistep method
I i V"^ y = hf m=l ^ P P
for the numerical integration of y'(x) = f(x,y) is stable in the sense of Dahlquist iff 1 <_ q <_ 6.
WIS-llT May 1971 52 pages
A Note on the Non-Exist ence of Mult lvalue A-Stable Methods of Order Greater than Two by C. ¥. Gear
It is shown that the Dahlquist result limiting the order of A-stable multistep methods also applies to multivalue methods.
UIUC-R-73-569 March 1973 7 pages
The Effect of Variable Mesh Size on the Stability of Multistep Methods by C. W. Gear and K. W. Tu
The effects of two different techniques for implementing variable mesh sizes in multistep formiiLas are investigated. It is proved that one is more stable than the other for some cases, but that both are stable when the step changes are small. The practical implications of these results are discussed.
UIUC-R- 73-570 April 1973 35 pages
Stability and Convergence of Variable Order Multistep Methods by C. W. Gear and D. S. Watanabe
The variable step Adam's method is shown to be stable for any order changing scheme. The Nordsieck form of Adam's method, however, is shown to be stable only if the step size and order are fixed for p steps following a change to an r-step method, where p is r or r+1 depending on the algorithm used to interpolate the necessary high derivatives. Finally, general consistent and strongly stable multistep and multivalue methods are shown to be stable if the method is fixed for a certain number of steps following each method change and step size changes are small. This number is independent of the differential equation and the step sizes.
UIUC-R-73-571 May 1973 31 pages
19
Solutions of a Differential Equation Arising in Chemical Reactor Processes "by Seymour V. Parter
Consider the boundaiy value problem y" + — y' + Bf(y) = 0,
y'(0) = 0, y( x) = T where B >_ 0, t >_ 0. The function f(y) satisfies certain
properties which generalize the properties of '^^(j) = exp (- -i — r) . We are
concerned with the number of solutions in various regions of the t, 3 plane.
WIS-162 January 1973 5^ pages
Zxir numerischen Losimg von gewohnlichen Differentialgleichungen zweiter Ordnung "by Manfred Heidt
In dieser Arbeit wird ein Verfahren zur numerischen Berechnving einer Faherungslosving zusammen mit einer Fehlerabschatzung fiir das An f an gswert problem
y"(x) = f(x,y(x),y'(x)), y(x^) = y^ , y'(x^) = y '^
einer gewohnlichen expliziten Differentialgleichung zweiter Ordnung angegeben. Es handelt sich hierbei um ein Einschritt verfahren. Die Differentialgleichung wird bei jedem Integrationsschritt lokal linearisiert , die linearisierte Differentialgleichung analytisch gelost , diese Losung mit einem Storansatz abgespalten und nur noch eine relativ "harmlose" Rest- differentialgleich-ung numerisch gelost. Mit Hilfe einer Defektabschatzung werden anschliessend Fehlerschranken dieser Naherung berechnet.
Das Verfahren liefert fur eine KLasse linearer Differential- gleichungen die exakte Losung. Das Phanomen der numerischen Instabilitat , wie es bei den meisten Faheriingsverfahren selbst bei stabilen Anfangswert- problemen zu beobachten ist, tritt hierbei kaum mehr auf.
KARL 71/6 1971 122 pages
Investigation of One-Step Methods for Integro -Differential Equations t»y Geneva G. Belford and Surender Kumar Kenue
One-step methods for solving integro-differential equations are studied from the point of view of desiring that the method give good accuracy when the true solution asymptotically goes to zero. A test equation is proposed and absolute stability is investigated.
CAC No. 75 May 1973 11 pages
20
High Order Finite Difference Solution of Differential Equations by Victor Pereyra
These seminar notes give a detailed treatment of finite difference approximations to smooth nonlinear tvo-point "boiindary value problems for second order differential equations. Consistency, stability, convergence, and asymptotic expansions are discussed. Most results are stated in such a way as to indicate extensions to more general problems. Successive extrapolations and deferred corrections are described and their implementations are explored thoroughly. A very general deferred correction generator is developed and it is employed in the implementation of a variable order, variable (uniform) step method. Complete FORTRAN programs and extensive numerical experiments and comparisons are included together with a set of U8 references.
STAN-CS-T3-3^8 April 1973 86 pages Program Incl.
PARTIAL DIFFERENTIAL EQUATIONS
A Conjugate Gradient Approach to Nonlinear Elliptic Boundary Value Problems
in Irreg-ular Regions
by Richard Bart els and James W. Daniel
A version of the conjugate gradient method is proposed for solving 'discrete approximations to nonlinear elliptic boundary value problems over irregular regions. The convergence rate is usually independent of the discretization, but each step requires the solution of a Poisson equation on the region; thus a fast Poisson solver yields a fast method for the general problem. Details are given for the standard 5-point approximation to the differential equation, with the Poisson equations being solved by the Buneman algorithm after some preprocessing; numerical examples are given.
CNA-63
Niomerical Studies of Discrete Vibrating Strings by A. B. Schubert and D. Greenspan
Discrete string vibrations are studied by means of a new two dimensional model. Linear and nonlinear wave motions are constructed with equal ease. Conditions and problem in which horizontal motion is particularly noticeable are emphasized. A large variety of computer examples are given.
WIS-158 November 1972 76 pages
21
FIMC TIONAL EQUATIONS
The Nimierical Solution of Boundary Value Problems for Second Order Functional Differential Equations by Finite Differences by Colin W. Cryer
In the present paper we consider numerical methods for computing the solution of the boundaiy value problem
x(t) = g(t,x(t)) + (Fx)(t), 0 < t < 1,
x(0) = x(l) = 0, where, F:C[0, l] ^ C[0, l], and g:R ^ R . WIS-127 June 1971 57 pages Program Incl.
OPTIMIZATION
Least Squares Computations with Two Algorithms for the Two-Multiply, Two-Add Givens Rotation by R. J. Hanson
Two numerically stable algorithms for the implementation of the two-multiply, two-add Givens transformation are discussed. An application of the use of these algorithms is given for the problem of accumulating and deleting rows of data from a least squares problem in a stable manner.
The construction of either transformation requires essentially the same amount of work. The first method (which is not due to the author) requires no square roots but may require rescaling to avoid underflow and overflow. The second method requires one square root per transformation but will need rescaling less than half as often as the first method.
WSU-73002 1973
Second and Higher Order Duality in Nonlinear Programming by 0. L. Mangasarian
A d-ual problem associated with a primal nonlinear programming problem is presented that involves second derivatives of the functions con- stituting the primal problem. Duality results are derived for this pair of problems. More general dual problems are also presented, and duality results for these problems are also given.
WIS-159 October 1972 20 pages
22
Einschliepung des Minimalpunktes einer streng konvexen F-unktion auf elnem n- dimensional en Quader by Rainer Dussel
Gegeben sei eine Funktion <^: R -> R. Sie sei streng konvex in R und es gelte (f)eC2(R^). Weiterhin sei ein n-dimensionaler achsenparalleler Quader QOR^ gegeben durch Q := ( [a_ ,sr ], . . . , [a ,a" ]).
Gesucht ist derjenige Punkt xeQ, fur den gilt
(j)(x) = Min (t)(x) . xeQ
Man nennt xeQ den Minimalpunkt von (f) bezuglich Q. Existenz und Eindeutigkeit eines solchen Minimalpunktes sind unter den getroffenen Voraussetzimgen trivial (siehe dazu Satz 3).
Anzugeben ist ein Verfahren zur numerischen Bestimmung von x und damit von (j)(x). Da ein solches Verfahren in der Praxis nach endlich vielen Schritten abgebrochen verden mu3 und da i. a. die Komponenten von x und die Zaiil ^(x) in einem Computer nicht exakt darstellbar sind, stellt sich ■weiterhin die Frage nach Fehlerschranken fur eine mit diesem Verfahren bestimmte Naheriing x zu x. Man kann damit das oben genannte Problem umformulieren zu:
Gesucht ist ein numerischer Algorithmus zur Angabe eines "mog- lichst kleinen" Quaders
[x] e I^(R) mit [x]CQ und xe:[x]
und eines "moglichst kleinen" Intervalls
$el(R) mit (|)(x)e$ . KARL 72/2 July 1972 69 pages
Stability of the Solution of Definite Quadratic Programs by James W. Daniel
This paper studies how the solution of the problem of minimizing Q(x) = jx^Kx - k^x subject to Gx £ g and Dx = d behaves when K, k, G,^g, D, and d are perturbed, say by terms~of size e, assioming that K is positive definite. It is shown that in general the solution moves by roughly e if G, g, D, and d are not perturbed; when G, g, D, and d are in fact perturbed,
23
much stronger hypotheses allow one to show that the solution moves "by roughly e. Many of these results can be extended to more general, non- quadratic, functionals.
CNA-58 September 1972
The Quadratic Assignment Problem by George B. Purdy
In this report we discuss some seemingly reasonable approaches to the quadratic assignment problem, and we give some evidence from automata theoiy that the problem is insoluble.
CAC No. 71 February 1973 1^+ pages
Die Anwendung der Methode "Branch and Bound" auf ein verallgemeinertes Knaps ackpr obi em by Rudolf Krawczyk
Fur ein verallgemeinertes Knaps ackproblem mit gegebener Zielfunktion und Restriktionen, dessen Lbsung durch boolesche Variable dargestellt werden kann, wird eine Losungsmethode nach dem "Branch and Bound" — Prinzip angegeben. Diese Methode wird mit Hilfe eines LSsungsbaumes veranschaulicht und an einem Beispiel ausprobiert. Augerdem wird ein Algorithmus zu diesem Verfahren be- schrieben und in der algorithmischen Sprache ALGOL programmiert .
KARL 71/1 January 1971 21 pages Program Incl.
21+
ROOT FINDING
Fehlerschranken zu Naherixngswerten von Polynomwurzeln by Karl Nickel
Gegeben seien ein Polynom n-ten Grades und n komplexe Nahe- runsverte zu den (unbekannten) Polynomwurzeln. Es vlrd ein Algorithmus beschrieben, der zu jedem Naherungsvert' eine Fehlerabschatzung liefert. Das Verfahren ist "konvergent" und besitzt eine gevisse (schwache) Optimalitat. Es benbtigt keinerlei zus'atzliche Informationen uber die exakten Nullstellen und versagt nie, auch night im Falle von mehrfachen Nullstellen oder von Wurzelhaufen. Der Algorithmus wird durch ein Triplex- ALGOL 60-Programm verwirklicht , vomit auch noch die unvermeidlichen Runkungsfehler berucksichtigt "werden.
KARL 69/6 June 1969 22 pages Program Incl.
Abbruchkriterien und Numerishche Konvergenz by K. Nickel and K. Ritter
Es sei X -> X eine von einem Verfahren erzeugte Folge zur
Approximation der reellen Zahl x. Es sei x (L) ein mit einer L-ziffrigen
Maschine gewonnener Naherungsvert zu x mit lim x (L) = x . Es wird em
" n , n n
L-x»
Abbrechkriterium N(L) angegeben derart, da3 es geniigt, bei fester Ziffer-
nanzahl L allein die Werte x (Lj, x-^ (L) , . . . ,31^/^ v (L) zu berechnen und
da6 unter sehr schvachen Voraussetzungen
L->o° ist, d.h. da3 x^^/_s(L) "numerisch konvergiert ".
KARL 70/6 May 1970 11 pages
Abbrechkirterium fur Iterationsverfahren tiy Rudolf Kravczyk
Die unendliche Folge x des allgemeinen Iterationsverfahrens zur Losung einer Operatorgleichung x = Tx in einem metrischen Raum vird haufig durch eine endliche Folge x approximiert, velche von der benutzten Rechen- anlage abhangt. Es vird ein Abbrechkriterium angegeben, velches die "numerische Konvergenz" im Sinne von [3] garantiert.
Dieses Abbrechkriteritim wird auf das NEWTONsche Verfahren zur Los-ung einer Gleichung im Reellen und auf eine Lineare Integral gleichung angevandt .
KARL 70/12 September 1970 11 pages
25
GRAPH ALGORITHMS
Two Upper Bounds for the Weighted Path Length of Binary Trees "by Jean Louis Pradels
Rooted binary trees with weighted nodes are structures encountered in many areas, such as coding theory, searching and sorting, information storage and retrieval. The path length is a meaningful quantity which gives indication about the expected time of a search or the length of a code for example. In this paper, two sharp boimds for the total path length of general weighted node trees are derived.
UIUC-R- 73-565 January 1973 1^ pages
An Efficient Implementation of Edmonds ' Maximum Matching Algorithm by Harold Gabow
A matching in a graph is a collection of edges, no two of which share a vertex. A maximum matching contains the greatest number of edges possible. This paper presents an efficient implementation of Edmonds' algorithm for finding maximum matchings. The computation time is proportional to v3, where V is the number of vertices; previous algorithms have computation time proportional to V^. The implementation avoids Edmonds' blossom reduction by using pointers to encode the structure of alternating paths.
STAN-CS-72-328 June 1972 68 pages Program Incl.
Finding the Cliques of a Graph by George B. Purdy
Auguston and Minker [l] presented a version of the Bierstone algorithm for finding the set of cliques of a finite undirected graph. (A clique is a maximal complete subgraph). However they gave no proof that their algorithm worked, and indeed Mulligan and Cornell [2] pointed out that it was wrong. Mulligan in [3] described his PL/I implementation of their modified version of the algorithm, but it is referred to there as a heuristic. For our algorithm we include a proof that it works.
This algorithm is clearly well suited for use on an array pro- cessor, or an array of processors, which the other algorithms are not.
CAC m No. 5 December 1972 8 pages Program Inc.
26
MISCELLANEOUS
A Universal Random Number Generator
"by Michael A. Malcolm and Cleve B. Moler
A subroutine for generating uniformly-distrituted floating-point numbers in the interval [O, l) is presented in ANSI standard Fortran. The subroutine , URAND, is designed to be relatively machine independent. URAND has undergone minimal testing on various machines and is thought to work properly on any machine having binary integer number representation, integer multiplication modulo m and integer addition either modulo m or yielding at least £og (m) significant bits, where m is some integral power of 2 .
Upon the first call of UMND, the value of m is automatically determined and appropriate constants for a linear congruential generator are computed following the suggestions of D. E. Knuth, Volume 2. URAND is guaranteed to have a full-length cycle. Readers are invited to apply their favorite statistical tests to URAND, using any binary machine, and report the results to the authors.
STAN-CS-T3-33^ January 1973 Program Incl.
Computation of the Stationary Distribution of an Infinite Markov Matrix by G. Golub and E. Seneta
An algorithm is presented for computing the -unique stationary distribution of an infinite stochastic matrix possessing at least one coliimn whose elements are bounded away from zero. Elementwise convergence rate is discussed by means of two examples.
STAN-CS-73-335 Januaiy 1973
Calc\iIation of GFSR Pseudorandom Number Binary Starting Matrix by W. H. Payne
The generalized feedback shift register pseudorandom niimber algorithm produces the same floating-point sequence of pseudorandom numbers on any computer. The algorithm requires a binary initialization matrix. A matrix, given both in octal and hexadecimal, for primitive polynomial, modulo 2, x98 + x27 + i is listed.
UIUC-R-73-567 March 1973 1^+ pages Program Incl.
27
The SAC-1 Modular Arithmetic System
by G. E. Collins, L. E. Heindel, E. Horowitz, M. T. McClellan and D. R. Musser
This is a reprinting of the original report of June I969, with correction of a few minor errors. The SAC-1 Modular Arithmetic System is the fifth of the ten SAC-1 subsystems which are now available. It provides subprograms for the arithmetic operations in a prime finite field GF(p), for any single-precision prime p, and for various operations on polynomials in several variables with coefficients in GF(p). Besides the arithmetic operations on such polynomials there are included subprograms for the Chinese remainder theorem, evaluation and interpolation. For invariate polynomials, subprograms are included for greatest common divisor calculation and Berlekamp's factorization algorithm.
¥IS-l65 November 1972 50 pages Program Incl.
Gleichungen in halbgeordneten Raumen "by R. Krawczyk
Im ersten Teil dieser Arbeit wird eine Operatorgleichung Tx = 9 in eine Operatorgleichung x = Sx transformiert . Darauf werden Fixpunksatze angewendet und Fehlerabschatzungen fiir eine Losung durchgefuhrt . Das allgemeine Iterationsverfahren entspricht bei variablem S dem WEWTONschen Verfahren in normierten Raumen, ohne da3 eine Norm benotigt wird. Anstelle der Frechet-Ableitung des Operators T tritt eine allgemeine Lips chit zbeding\mg mit linearen Operatoren. Im zweiten Teil werden die abstrakten SStze des ersten Teils auf einfache Beispiele: Gleichungen, nichtlineare Gleichungssysteme, algebraische Eigenwertprobleme angewendet.
KARL TO/3 April 1970 16 pages
Das Prae-Euler'sche Limit ierungs verfahren by Karl Nickel
Es sei {a } eine vollmonoton fallende Nullfolge. Es wird ein n Limit ierungs verfahren zur Kbnvergenzverbesserimg der alternierenden Reihe
I (-1) a angegeben und durch ein Triplex-ALGOL 60-Programm realisiert.
v=o
Es werden apriori-Fehlerschranken angegeben, die Stabilitat wird untersucht, die Rundungsfehler fvor eine Klasse "idealer" Komputer werden abgeschatzt \md es wird gezeigt, dass das Verfahren in dieser Klasse sogar "n-umerisch konvergiert" . Beispiele zeigen die praktische Brauchbarkeit der Methode.
KARL 70/7 July 1970 ill pages Program Incl.
28
KEY TO REPORT SOURCES
ANL - Argonne National Laboratory Argonne, Illinois 60^39
BTL - Bell Telephone Laboratories, Inc. Murray Hill, New Jersey 079 71
CAC
Center for Advanced Computation
University of Illinois, Urbana, Illinois 618OI
CAL - Department of Mathematics
Statistics and Computing Science University of Calgary, Calgary
Alberta, Canada
CMU
CNA
Carnegie-Mellon University Computer Science Department Pittsbiorgh, Pennsylvania 15213
Center for Numerical Analysis
University of Texas, Austin, Texas 78712
KARL - Inst i tut Fiir Informatik Universitat Karlsruhe Englerstrasse 2, Postfach 638O D 75 Karlsriohe 1, Germany
MAC
MRC
Massachusetts Institute of Technology
Project MAC
Cambridge, Massachusetts 02139
Mathematics Research Center
University of Wisconsin, Madison, Wisconsin 53706
PRAK - Institut fur Praktische Mathematik Universitat Karlsruhe Englerstrasse 2, Postfach 638O D 75 Karlsruhe 1, Germany
STAN - Computer Science Department
Stanford University, Stanford, California 9^305
TOR
Department of Computer Science University of Toronto, Ontario, Canada
UAE - Department of Computing Science
University of Alberta, Edmonton, Alberta, Canada
UBC
Department of Computer Science
University of British Coliombia, Vancouver, B. C, Canada
29
UMINF -
UIUC -
WIS
Department of Information Processing University of Umea, Umea, Sweden
Department of Computer Science University of Illinois, Urbana, Illinois
Computer Sciences Department The University of Wisconsin 1210 West Dayton Street Madison, Wisconsin 53T06
61801
WSU - Computer Science Department Washington State University Pullman, Washington 99l63
YORK - T. J. Watson Research Center
Yorktown Heights, New York IO598
30
UNCLASSIFIED
|
SECURITY CL ASSinCATIOhi OF THIS PAGE (i*'hrn Data |
Fnfer^d) |
|
|
REPORT DOCUMENTATION PAGE |
RliAD INSTRUCTIONS BEFORE COMPLETING FORM |
|
|
1. REPORT NUMQER CAC Document No, 90 |
2. GOVT ACCESSION NO. |
3. RECIPIENT'S CATALOG NUMBER |
|
4. TITLE (end Subtllle) Computational Mathematics Abstracts |
5. TYPE OF REPORT & PERIOD COVERED Bibliographical Abstracts |
|
|
6. PERFORMING ORG. REPORT NUMBER |
||
|
7. AUTHORCs; Edited "by: Geneva Belford, Jonathan Lermit, George Purdy, and Ahmed Sameh |
8. CONTRACT OR GRANT NUMBER(-»; DAHCOJ+-72-C-OOOI |
|
|
9. PERFORMING ORGANIZATION NAME AND ADDRESS Center for Advanced Computation University of Illinois at Urhana-Champaign Urhana, Illinois 618OI |
10. PROGRAM ELEMENT. PROJECT, TASK AREA 4 WORK UNIT NUMBERS AEPA Order No. l899 |
|
|
»l. CONTROLLING OFFICE NAME AND ADDRESS U.S. Army Research Office-Durham Duke Station, Durham, North Carolina |
12. REPORT DATE October 1973 |
|
|
13. NUMBER OF PAGES 32 |
||
|
U. MONITORING AGENCY NAME A ADDRESSf// dlllerent from Controlling Oflice) |
15. SECURITY CLASS, (oi thia report) UNCLASSIFIED |
|
|
15«. DECLASSIFICATION/ DOWNGRADING SCHEDULE |
||
|
16. DISTRIBUTION ST ATEM EN T Co/ <h<s Repor (; |
Copies may be requested from the i\[ational Technical Information Service, Springfield, Virginia 22151
17. DISTRIBUTION STATEMENT (ol the abstract entered In Block 20, II dlllerent Irom Report)
t8. SUPPLEMENTARY NOTES
19. KEY WORDS (Continue on reverse aide II necessary and Identlly by block number)
Numerical Analysis Graph Theory Mathematical Programming
20. ABSTRACT (Continue on reverse side II necessary and Idenlily by block number)
NONE
DD 1 JAN 73 1473 EDITION OF 1 NOV 65 IS OBSOLETE
UNCLASSIFIED
SECURITY CLASSIFICATION OF THIS PAGE fWTien Data Entered)
m