Iterative methods for solving linear equations

This paper presents some of the original versions of the conjugate-gradient method for solving a system of linear equations of the formAx=k.This paper originally appeared as NAML Report No. 52-9, 1951. Its preparation was supported in part by the Office of Naval Research.     

A posteriori error estimation with finite element methods of lines for one-dimensional parabolic systems

Summary Consider the solution of one-dimensional linear initial-boundary value problems by a finite element method of lines using a piecewiseP ^th -degree polynomial basis. A posteriori estimates of the discretization error are obtained as the solutions of either local parabolic or local elliptic finite element problems using piecewise polynomial corrections of degreep+1 that vanish at element ends. Error estimates computed in this manner are shown to converge in energy under mesh refinement to the exact finite element discretization error. Computational results indicate that the error estimates are robust over a wide range of mesh spacings and polynomial degrees and are, furthermore, applicable in situations that are not supported by the analysis.This research was partially supported by the U.S. Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR 90-0194; by the U.S. Army Research Office under Contract Number DAAL03-91-G-0215; and by the National Science Foundation under Institutional Infrastructure Grant Number CDA-8805910     

Approximations and computational methods for Optimal Stopping and Stochastic Impulsive Control problems

The paper treats a computational method for the Optimal Stopping and Stochastic Impulsive Control problem for a diffusion. In the latter problem control acts only intermittently since there is a basic positive transaction cost to be paid at each instant that the control acts. For eachh > 0, a controlled Markov chain is constructed, whose continuous time interpolations are a natural approximation to the diffusion, for both the optimal stopping and impulsive control situations. The solutions to the optimal stopping and impulsive control problems for the chains are relatively easy to obtain by using standard procedures, and they converge to the solutions of the corresponding problems for the diffusion models ash0.Research was supported in part by the Air Force Office of Scientific Research AF-AFOSR 71-2078C, in part by the National Science Foundation GK 40493X and in part by the Office of Naval Research NONR N00014-67-A-0191-001804.     

Projection method for unconstrained optimization

A method of conjugate directions, the projection method, for solving unconstrained minimization problems is presented. Under the assumption of uniform strict convexity, the method is shown to converge to the global minimizer of the unconstrained problem and to have an (n – 1)-step superlinear rate of convergence. With a Lipschitz condition on the second derivatives, the rate of convergence is shown to be a modifiedn-step quadratic one.This research was supported in part by the Army Research Office, Contract No. DAHC 19-69-C-0017, and the Office of Naval Research, Contract No. N00014-71-C-0116(NR-047-099).     

The treatment of nonhomogeneous Dirichlet boundary conditions by thep-version of the finite element method

Summary The paper addresses the problem of the implementation of nonhomogeneous essential Dirichlet type boundary conditions in thep-version of the finite element method.Partially supported by the Office of Naval Research under Grant N-00014-85-K-0169Research partially supported by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR 85-0322     

Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

Locking effects in the finite element approximation of elasticity problems

Summary We consider the finite element approximation of the 2D elasticity problem when the Poisson ratiov is close to 0.5. It is well-known that the performance of certain commonly used finite elements deteriorates asv0, a phenomenon calledlocking. We analyze this phenomenon and characterize the strength of the locking androbustness of varioush-version schemes using triangular and rectangular elements. We prove that thep-andh-p versions are free of locking with respect to the error in the energy norm. A generalization of our theory to the 3D problem is also discussed.The work of this author was supported in part by the Office of Naval Research under Naval Research Grant N00014-90-J-1030The work of this author was supported in part by the Air Force Office of Scientific Research, Air Force Systems Command, U.S. Air Force, under grant AFOSR 89-0252     

Approximation properties of the Generalized Finite Element Method

In this paper, we have obtained an approximation result in the Generalized Finite Element Method (GFEM) that reflects the global approximation property of the Partition of Unity (PU) as well as the approximability of the local approximation spaces. We have considered a GFEM, where the underlying PU functions reproduce polynomials of degree l. With the space of polynomials of degree k serving as the local approximation spaces of the GFEM, we have shown, in particular, that the energy norm of the GFEM approximation error of a smooth function is O(h ^l + k ). This result cannot be obtained from the classical approximation result of GFEM, which does not reflect the global approximation property of the PU.     

Asymptotic behavior ofL-statistics for a large class of time series

In this paper we derive the asymptotic normality ofL-statistics with unbounded scores for a large class of time series. To handle the dependence structure, we use the concept ofm(n)-decomposability as an alternative to classical mixing concepts.Research supported by the Office of Naval Research Contract N00014-91-J-1020.Part of this work was done while the author was at the Department of Mathematics, KUN, Nijmegen, The Netherlands.     

Methods of conjugate directions versus quasi-Newton methods

It is shown that algorithms for minimizing an unconstrained functionF(x), x E ⁿ , which are solely methods of conjugate directions can be expected to exhibit only ann or (n–1) step superlinear rate of convergence to an isolated local minimizer. This is contrasted with quasi-Newton methods which can be expected to exhibit every step superlinear convergence. Similar statements about a quadratic rate of convergence hold when a Lipschitz condition is placed on the second derivatives ofF(x). Research was supported in part by Army Research Office, Contract Number DAHC 19-69-C-0017 and the Office of Naval Research, Contract Number N00014-71-C-0116 (NR 047-99).     

Edge-clique graphs

The edge-clique graphK(G) of a graphG is that graph whose vertices correspond to the edges ofG and where two vertices ofK(G) are adjacent whenever the corresponding edges ofG belong to a common clique. It is shown that every edge-clique graph is a clique graph, and that ifG is either an interval graph or a line graph, then so too isK(G). An algorithm is provided for determining whether a graph is an edge-clique graph. A new graph called the STP graph is introduced and a relationship involving this graph, the edge-clique graph, and the line graph is presented. The STP graphs are also characterized.Research supported in part by Office of Naval Research Contract N00014-88-K-0018.Research supported in part by Office of Naval Research Contract N00014-88-K-0163.     

Maximal order for quadratures usingn evaluations

The problem is to find approximationsI (f; h) to the integralI(f; h)= ₀ ^h f. Such an approximation has local orderp ifI(f; h)–I (f; h)=O(h ^p ) ash0. Let(n) denote the maximal local order possible for a method usingn evaluations of a function or its derivatives. We show that (n)=2n+1 if the information used is Hermitian. This is conjectured to be true in general. The conjecture is established for all methods using three or fewer evaluations.This research was supported in part by the National Science Foundation under Grant MCS75-222-55 and the Office of Naval Research under Contract N00014-76-C-0370, NR 044-422. Numerical results reported in this paper were obtained through the computing facilities of the University of Maryland.     

L 2 error estimates for finite elements with interpolated boundary conditions

Summary TheL ² error in the nearly zero quadratic approximate solution to Poisson's equation is shown to be of optimal order. The same method of proof can be used to show that theL ² error with a space of cubics developed by Ridgway Scott is optimal.This work was supported by the Office of Naval Research under Contract Number ONR NR-044-453 and by the Naval Ordnance Laboratory Independent Research Fund.     

On iterative methods for solving nonlinear least squares problems over convex sets

Nonlinear least squares problems over convex sets inR ⁿ are treated here by iterative methods which extend the classical Newton, gradient and steepest descent methods and the methods studied recently by Pereyra and the author. Applications are given to nonlinear least squares problems under linear constraint, and to linear and nonlinear inequalities. Part of the research underlying this report was undertaken for the Office of Naval Research, Contract Nonr-1228(10), Project NR047-021, and for the U.S. Army Research Office — Durham, Contract No. DA-31-124-ARO-D-322 at Northwestern University. Reproduction of this paper in whole or in part is permitted for any purpose of the United States Government.     

Universally consistent conditionalU-statistics for absolutely regular processes and its applications for hidden Markov models

A general class of conditionalU-statistics was introduced by W. Stute as a generalization of the Nadaraya-Watson estimates of a regression function. It was shown that such statistics are universally consistent. Also, universal consistentcies of the window andk _n -nearest neighbor estimators (as two special cases of the conditionalU-statistics) were proved. In this paper, we extend these results from the independent case to dependent case. The result is applied to verify the Bayes risk consistency of the corresponding discrimination rules. Research supported by the Office of Naval Research Contract N00014-91-J-1020.     

Error analysis of the finite-strip method for parabolic equations

The finite-strip method (FSM) is a hybrid technique which combines spectral and finite-element methods. Finite-element approximations are made for each mode of a finite Fourier series expansion. The Galerkin formulated method is set apart from other weighted-residual techniques by the selection of two types of basis functions, a piecewise linear interpolating function and a trigonometric function. The efficiency of the FSM is due in part to the orthogonality of the complex exponential basis: The linear system which results from the weak formulation is decoupled into several smaller systems, each of which may be solved independently. An error analysis for the FSM applied to time-dependent, parabolic partial differential equations indicates the numerical solution error is O(h² + M^?r). M represents the Fourier truncation mode number and h represents the finite-element grid mesh. The exponent r ≥ 2 increases with the exact solution smoothness in the respective dimension. This error estimate is verified computationally. Extending the result to the finite-layer method, where a two-dimensional trigonometric basis is used, the numerical solution error is O(h² + M^?r + N^?q). The N and q represent the trucation mode number and degree of exact solution smoothness in the additional dimension. © 1993 John Wiley & Sons, Inc.     

Explicit solution of an optimization problem

A simply statedn-variable constrained optimization problem, useful as a test problem, is explicitly solved. It has a large number of easily described local optima.This work was supported (in part) by the Office of Naval Research under contract number N00014-71-C-0112.     

Mathematical programming problems with quasi-convex objective functions

This paper generalizes results obtained by Arrow and Enthoven in [1] for functions of ClassC ² on the non-negative orthant.This research was supported by Hydro—Quebec; University of Montreal; Office of Naval Research, Contract N-0014-67-A0112-001; National Science Foundation, Grant GP 25738.     

Relevance of the Bayesian paradigm for “applied probabilists”

This paper is based on an invited lecture given by the author at the ORSA/TIMS Special Interest Group on Applied Probability Conference onStatistical and Computational Problems in Probability Modeling, held at Williamsburg, Virginia, January 7–9, 1985.The theme of this paper is twofold. First, that members of the above group should be seriously concerned with issues of statistical inference — they should not stop short upon proposing a probability model. Second, that inference be undertaken via a strict adherence to the rules of probability — the Bayesian paradigm. To underscore a need for emphasizing the first theme, it may be pertinent to note that an overwhelming majority of the papers dealing with statistical and inferential issues that were presented at this conference were authored by members who did not claim to belong to the ORSA/TIMS Special Interest Group on Applied Probability.The lecture was followed by a panel discussion, with Drs. Lyle Broemeling and Edward Wegman of the Office of Naval Research as discussants. Dr. Robert Launer of the Army Research Office served as a moderator. Discussions from the floor included comments by Professors D. Harrington of Harvard University, E. Parzen of Texas A & M University, and R. Smith of Imperial College, London, England. This paper, and the comments of the panelists, are published in this volume of theAnnals of Operations Research, which is going to serve as a Proceedings of the Conference.Supported by Contract No. N00014-85-K-0202, Office of Naval Research, and Grant No. DAAG 29-84-K-0160, Army Research Office.     

Newton's method for nonlinear inequalities

A Newton-type algorithm has been presented elsewhere for solving non-linear inequalities of the formf(x)0,g(x)=0, and quadratic convergence has been proved under very strong hypotheses. In this paper we show that the same results hold under a considerable weakening of the hypotheses.This research was supported in part by contract number N00014-67-A-0126-0015, NR 044-425, from the Office of Naval Research.