THE U N I VER S I T Y OF MICHIGAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Department of Mathematics Technical Report No. 1 ABSTRACTS OF FOUR THESES IN NUMERICAL ANALYSIS Norman Schryer Charles Crawford Alan K. Cline David Kammler ORA Project 027750 under contract with: OFFICE OF NAVAL RESEARCH DEPARTMENT OF THE NAVY CONTRACT NO. N00014-67-A-0181-0023 WASHINGTON, D.C. administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR February 1972 Approved for public release; distribution unlimited.

ABSTRACTS OF FOUR THESES IN NUMERICAL ANALYSIS This report consists of the abstracts of the four Ph. D. theses which have been written at the University of Michigan with partial support from the office of Naval Research. The theses themselves are too lengthy to be circulated in any quantity, but interested parties are invited to contact Professor Cleve Moler, Mathematics Department, University of Michigan, or the authors themselves for further information. The authors' current addresses are: Norman Schryer Bell Telephone Laboratories Murray Hill, NJ Charles Crawford Erindale Campus University of Toronto Toronto, Ontario, CANADA Alan Kaylor Cline National Center for Atmospheric Research Boulder, CO David Kammler Mathematics Department Southern Illinois University Carbondale, IL This research was supported in part by the Office of Naval Research under Contract N00014-67-0181-0023, NR 044-377. Reproduction in whole or in part is permitted for any purpose of the United States Government. ii

ABSTRACT SYMBOLIC COMPUTER SOLUTION OF ELLIPTIC BOUNDARY VALUE PROBLEMS by Norman Loren Schryer We study the elliptic boundary value problem: Lu = Au +a(x, y)u + b(x,y)u + c(x,y)u = 0 with c(x,y) < 0 on a simply connected domain D and u = f given on AD Under the assumption that the coefficients a, b, and c are analytic functions of x and y, and following ideas of Stefan Bergman and of I. N. Vekua, a system of particular solutions, Pk(x, y), of Lu = 0 is constructed. Each p is given by an infinite series whose elements are defined recursively in terms of a, b, and c. These solutions are independent of the domain D and represent generalizations of the harmonic k k polynomials Re (x + iy) and Im (x + iy) for the equation An = 0. Let k, T be defined by truncating the series expansion of k after T terms. For any vector s =(sl,, N) let N u(z,s)= SkPk, T (z). k= l Given boundary values f, a compact subset, SN, of R is constructed that contains the necessary coefficients for convergence to the solution u.

To find these coefficients, we choose points zl *, NM which are uniformly distributed around a D. Define s N T to be a solution of the linear approximation problem min max | f(z.) - u(z, s) se SN j=l, *, M Then UNM(, ()=u(z s ) is a best fit to u at z Na,, MT 1M Our principal result is that lim [ lim max u(z) - N MT() ]= 0 N-oco M,T- oo D VaD The truncated solutions Pk T may be constructed exactly, but they are not exact solutions of Lu = 0. A computable a posteriori error bound is given for | u - uN, M, T I n terms of how well UN M T satisfies the boundary conditions and the differential equation Lu = 0. An alogorithm similar to the above is given for solving the inhomogeneous equation Lu = g for analytic coefficients a, b, c, and g. Several examples are given and numerical results presented for the special case where a, b, and c are polynomials in x and y 2

ABSTRACT UNIFORM APPROXIMATION AS A LIMIT L APPROXIMATIONS by Alan Kaylor Cline Let X be a compact Hausdorff space, and G be a finite dimensional Haar subspace of C(X), the space of continuous, complex valued functions on X. For a fixed f s C(X) we seek to find the unique g* ~ G which best approximates f in the uniform sense (i. e., i f- g* II < 11 f g I for all g e Gt{O} ). In the thesis of Charles L. Lawson an algorithm was given for determining g* as the limit of a sequence { k1} k0 of weighted least square approximateions to f, where the weight at the k+lst step is proportional to the error | f - k at the kth step. Lawson's work assumed X was a finite set; the results of this thesis allow X to be any compact, Hausdorff space for which C(X) is separable. 5

Specifically, a set of unit, Baire measures on X which induce L norms on the subspace of C(X) spanned by G and f is considered and denoted by S. An initial measure LO0 is selected from S and o, the best I| I approximation from G to f, is determined (i. e., g satisfies ( flf -'go dlo)l 2 < (f f- gl2 do) 1/2 X X for all g~ G {g} For k 0 1, ' *, the measure k+l is defined by the relation Js f-gk dpLk A 1k+l (A) = fJ f-" k' dk X for each Baire subset A. of X. Pk+l is shown to be an element of S and the best || ' 1 approximation is determined and 'k+1 denoted by k+l Sufficient conditions are given to guarantee the sequence { gk} k= converges uniformly to g* on X Furthermore, the rate of such convergence is explored and the computer results of several attempts to accelerate the convergence are discussed. A technique is presented for directly determining g* when X is a set containing exactly one more point than the dimension of G. This technique is employed in an exchange algorithm for determining g* on more general sets X. 4

ABSTRACT THE NUMERICAL SOLUTION OF THE GENERALIZED EIGENVALUE PROBLEM by Charles Raymond Crawford This paper considers the eigenvalue problem Ax = XBx where A and B are symmetric and B is positive definite, or equivalently the T problem of finding the zeroes of p(i) = det (A - )SB). If B = SS and C = S AS then the generalized eigenvalues are the eigenvalues of C T The Cholesky decomposition of B = LL where L is lower-triangular -1 -T is easily obtained for positive definite B. Thus computing C = L AL and then finding the eigenvalues of C is the best general method, called here the Cholesky-Wilkinson method for solving the generalized eigenvalue problem. To find the effect of perturbations of A and B on the generalized eigenvalues, we prove first an analogue of a result of Weyl. Let U, V and T W be real matrices with U symmetric and W = VUV and V nonsingular. Let {xi} ' {Pi} and { bi} be the real eigenvalues of T U, W and VV respectively. Then n X < p < nX for X > 0 and n1, x < F < Tl X for X < 0 m -m - n m m5

Furthermore if {xi} are redefined as the generalized eigenvalues of A and B and {Xi} those of A+ H and B + F then | - x < (B + F)I|'1 ( |I F IF ] |m + || H I ) Round-off error analysis of the Cholesky decomposition and computation -1 -T of L AL reveals, as indicated by the perturbation theory, that the stability of the Cholesky-Wilkins on method depends on the condition of B or, more precisely, on the square of the condition of the computed Cholesky factor. In case A and B have band structure, that is for some m a.. b.. = 0 whenever i - j > m, the matrix L AL willin 13 13 general be full. An algorithm is described which takes advantage of the T-l -T band structure to produce a matrix C = T L AL T where T is orthogonal and C has the same bandwidth as A and B. The algorithm begins with the Cholesky decomposition B = LL and a factorization of L into elementary matrices L = L L2 * L where q = n/m 12~~m oq then A 1 = A -1 -T T Ak= TkLk AkLk Tk where the Tk are chosen so that Ak+l retails the band structure and -1 -T A is orthogonally similar to L AL 6

The error analysis of the band algorithm indicates that the effect of the round-off error depends on the product nm rather than n as in the full matrix Cholesky-Wilkinson method. Numerical examples are included to compare the band algorithm with the full matrix method as well as with the Sturm sequence method of Peters and Wilkinson. Running times and error estimates are given for problems with a range of orders and bandwidths. These results confirm the natural expectation that the band algorithm is more efficient for large order problems with the bandwidth significantly smaller than the order. 7

ABS TRACT EXISTENCE, CHARACTERIZATION, AND COMPUTATION OF BEST APPROXIMATIONS BY SUMS OF EXPONENTIALS by David William Kammler Let V (S) denote the set of all solutions of all n-th order linear n homogeneous differential equations with constant coefficients for which the roots of the corresponding auxiliary polynomial all lie in S C C. Given 1 < p < oo and f E L [0, 1], we show that there is a best p II - I approximation to f from V (S) provided S is closed, thus p extending the work of Rice, Hobby, and de Boor who establish this result when S =IR. An element of V (C) may be specified by giving the n initial conditions and the n coefficients of an n-th order differential operator which annihilates it. The tangential manifold corresponding to this parametric form does not suffer a loss of dimension when the roots of the auxiliary polynomial coalesce as is the case when one uses the roots of the auxiliary polynomial as parameters. In general, a best || |J - approximation need not be unique and there may be troublesome local best I|| | - approximations as we illustrate by means of various example. In particular, neither V (IR) nor V (C) can n n be parametrized in such a manner as to fall within Rice's theory of varisolvent functions as was formerly believed. 8

Fundamental first order necessary (but not sufficient) conditions which a best || || - approximation must satisfy are presented, and p sufficient conditions are given. Using the basic necessary conditions, we derive generalizations of the previously known necessary conditions of Hobby and Rice, and of Braess which were formulated in V (IR) Conditions for a best || || - approximation to f from V (IR) to be expressable as a simple sum of exponentials with positive coefficients are derived independently of the Decartes sign rule used by Braesso The use and limitations of these theorems are illustrated by means of carefully chosen examples. When f E Cn[O, 1], the distance of f(n) from the linear space spanned by f, f', *., f ) is used to bound the error | f - y | in a best | | - approximation to f from V (C), and from this error p n bound we devise two simple procedures for constructing remarkably good initial estimates of f from V (G). For the construction of best || || approximations, we also present an iterative procedure which has been found to be quite effective in the early stages of the iterative process when the parameters are not particularly close to their optimum values. Numerical results are given for several examples to illustrate these procedures. 9

Unclassified Department of Mathematics Unclas sified 4. DESCRIPTIVE NOTES (Typ o Ot report and inclusive dates) Technical Report, January 1972 1 5. AU THORIS) (First name, middle initial, last name) Norman Schryer Alan K. Cline Charles Crawford David Kamrnler. 16REPORT DATE 7a. TOTtNO. OF PAGES 7b. NQ EFS January 197. 8a. CON TRAC T OR GRANT NO. g9. ORIGINATOR'S REPORT NUMBER(S) N00014- 67-A-0181-0023. N00014-67-A01810 Technical Report Noa. 1 I, gb. OTHER REPORT NO(S) (Any other numbeis thait may be assianed Norman Virginn 22217 M i 4813 - b. RPOR C T DAT L NO. - l this report) 10. DISTRI BUTION STA T EMENT.. Approved for public release; distribution unlimited. 11. SUPPLEMENTARY NOTES 12. SPONSORING MILITARY ACTIVITY Mathematics Program Office of Naval Research Arlington, Virginia 22217 13. ABSTRACT This report consists of the abstracts of four Ph. D. theses which have been written at the University of Michigan. The theses themselves are too lengthy to be circulated in any quantity. The specific topics covered are numerical solution of elliptic partial differential equations, approximation theory, and matrix computations. i: ~ rov~, ( AGE 1) j 1 NOV 65 '/^ (A 1): N 12 Unclas sified S/N 0101.80 7-660 1 Security Classification

Unclassified I symbolic computation elliptic differential equations I uniform approximation approximation theory |i g matrix eigenvalues i " eigenvalues exponential approximation i.'iI NOVJ 1 1 4732 (BACK) (AE 2SeuiyCasisfct (PAGE 2) Security Classification