The convergence of the cascadic conjugate-gradient method applied to elliptic problems in domains with re-entrant corners

We study the convergence properties of the cascadic conjugate-gradient method (CCG-method), which can be considered as a multilevel method without coarse-grid correction. Nevertheless, the CCG-method converges with a rate that is independent of the number of unknowns and the number of grid levels. We prove this property for two-dimensional elliptic second-order Dirichlet problems in a polygonal domain with an interior angle greater than . For piecewise linear finite elements we construct special nested triangulations that satisfy the conditions of a ``triangulation of type ' in the sense of I. Babuska, R. B. Kellogg and J. Pitkäranta. In this way we can guarantee both the same order of accuracy in the energy norm of the discrete solution and the same convergence rate of the CCG-method as in the case of quasiuniform triangulations of a convex polygonal domain.

     

Orthogonality correction in the conjugate-gradient method

This paper describes a simple algorithm for calculating the carryover term β in the conjugate-gradient method. The proposed algorithm incorporates an orthogonality correction as well as an automatic restart. Its performance is compared with alternate β forms reported, using five test functions and two cases of parameter estimation.     

Alternative proofs for inequalities of some trigonometric functions

By using an identity relating to Bernoulli's numbers and power series expansions of cotangent function and logarithms of functions involving sine function, cosine function and tangent function, four inequalities involving cotangent function, sine function, secant function and tangent function are established.     

Some convergence properties of the conjugate gradient method

It has been conjectured that the conjugate gradient method for minimizing functions of several variables has a superlinear rate of convergence, but Crowder and Wolfe show by example that the conjecture is false. Now the stronger result is given that, if the objective function is a convex quadratic and if the initial search direction is an arbitrary downhill direction, then either termination occurs or the rate of convergence is only linear, the second possibility being more usual. Relations between the starting point and the initial search direction that are necessary and sufficient for termination in the quadratic case are studied.     

A conjugate-gradient optimization method invariant to nonlinear scaling

A conjugate-gradient optimization method which is invariant to nonlinear scaling of a quadratic form is introduced. The technique has the property that the search directions generated are identical to those produced by the classical Fletcher-Reeves algorithm applied to the quadratic form. The approach enables certain nonquadratic functions to be minimized in a finite number of steps. Several examples which illustrate the efficacy of the method are included.     

Fluid dynamic limits of kinetic equations II convergence proofs for the boltzmann equation

Using relative entropy estimates about an absolute Maxwellian, it is shown that any properly scaled sequence of DiPerna-Lions renormalized solutions of some classical Boltzmann equations has fluctuations that converge to an infinitesimal Maxwellian with fluid variables that satisfy the incompressibility and Boussinesq relations. Moreover, if the initial fluctuations entropically converge to an infinitesimal Maxwellian then the limiting fluid variables satisfy a version of the Leray energy inequality. If the sequence satisfies a local momentum conservation assumption, the momentum densities globaly converge to a solution of the Stokes equation. A similar discrete time version of this result holds for the Navier-Stokes limit with an additional mild weak compactness assumption. The continuous time Navier-Stokes limit is also discussed. © 1993 John Wiley & Sons, Inc.     

Probabilistic and deterministic convergence proofs for software for initial value problems

The numerical solution of initial value problems for ordinary differential equations is frequently performed by means of adaptive algorithms with user-input tolerance τ. The time-step is then chosen according to an estimate, based on small time-step heuristics, designed to try and ensure that an approximation to the local error commited is bounded by τ. A question of natural interest is to determine how the global error behaves with respect to the tolerance τ. This has obvious practical interest and also leads to an interesting problem in mathematical analysis. The primary difficulties arising in the analysis are that: (i) the time-step selection mechanisms used in practice are discontinuous as functions of the specified data; (ii) the small time-step heuristics underlying the control of the local error can break down in some cases. In this paper an analysis is presented which incorporates these two difficulties. For a mathematical model of an error per unit step or error per step adaptive Runge–Kutta algorithm, it may be shown that in a certain probabilistic sense, with respect to a measure on the space of initial data, the small time-step heuristics are valid with probability one, leading to a probabilistic convergence result for the global error as τ→0. The probabilistic approach is only valid in dimension m>1 this observation is consistent with recent analysis concerning the existence of spurious steady solutions of software codes which highlights the difference between the cases m=1 and m>1. The breakdown of the small time-step heuristics can be circumvented by making minor modifications to the algorithm, leading to a deterministic convergence proof for the global error of such algorithms as τ→0. An underlying theory is developed and the deterministic and probabilistic convergence results proved as particular applications of this theory. This revised version was published online in June 2006 with corrections to the Cover Date.     

Properties of the conjugate-gradient and Davidon methods

Two quadratically convergent gradient methods for minimizing an unconstrained function of several variables are examined. The heart of the Fletcher and Powell reformulation of Davidon's method is a variableH-matrix. The eigenvalues and eigenvectors of this matrix for a quadratic function are explored, leading to a proof that the gradient vectors at each step are mutually orthogonal. From this, a geometric interpretation of theH-matrix in terms of the projection of the gradient into a solution subspace is derived. These properties are then used to arrive at the main result, which states that, for a quadratic function, the direction vectors generated by the Davidon algorithm and the conjugate-gradient algorithm of Hestenes and Stiefel are scalar multiples of each other, provided the initial step each takes is in the direction of steepest descent. If one assumes no round-off error and a perfect one-dimensional search, the methods generate identical steps leading to the minimum.It is also shown that, for a quadratic function, the Davidon algorithm has a simplified version which searches in the same directions. However, the unique advantage of the original scheme, that it yields the curvature of the function at the minimum, is sacrificed for simplicity.Although these results apply to the case of a quadratic function, a comparative study of the same algorithms for a general function can be found in a companion paper.This research was carried out under Contract No. NAS 9-4036, NASA-Manned Spacecraft Center, Houston, Texas. The author is indebted to Dr. H. J. Kelley, whose suggestions and encouragement provided the inspiration for this paper.     

Alternative proofs of a theorem of Moyls and Marcus on the numerical range of a square matrix

Moyls and Marcus [4] showed that for n≤4,n×n an complex matrix A is normal if and only if the numerical range of A is the convex hull of the eigenvalues of A. When n≥5, there exist matrices which are not normal, but such that the numerical range is still the convex hull of the eigenvalues. Two alternative proofs of this fact are given. One proof uses the known structure of the numerical range of a 2×2 matrix. The other relies on a theorem of Motzkin and Taussky stating that a pair of Hermitian matrices with property L must commute.     

On the convergence of Wang-Zheng's method

The choice of initial conditions ensuring safe convergence of the implemented iterative method is one of the most important problems in solving polynomial equations. These conditions should depend only on the coefficients of a given polynomial P and initial approximations to the zeros of P. In this paper we state initial conditions with the described properties for the Wang-Zheng method for the simultaneous approximation of all zeros of P. The safe convergence and the fourth-order convergence of this method are proved.     

Global convergence properties of the modified BFGS method associating with general line search model

To the unconstrained programme of non-convex function, this article give a modified BFGS algorithm. The idea of the algorithm is to modify the approximate Hessian matrix for obtaining the descent direction and guaranteeing the efficacious of the quasi-Newton iteration pattern. We prove the global convergence properties of the algorithm associating with the general form of line search, and prove the quadratic convergence rate of the algorithm under some conditions.     

Use of a nonquadratic model in a conjugate-gradient method of optimization with inexact line searches

An algorithm for unconstrained minimization is developed which uses a rational function model, rather than a quadratic, as a basis for conjugate directions. The algorithm is similar to one previously proposed by the authors, but inexact linear searches are investigated in the present paper.     

On the convergence of the UOBYQA method

We analyze the convergence properties of Powell's UOBYQA method. A distinguished feature of the method is its use of two trust region radii. We first study the convergence of the method when the objective function is quadratic. We then prove that it is globally convergent for general objective functions when the second trust region radius ρ converges to zero. This gives a justification for the use of ρ as a stopping criterion. Finally, we show that a variant of this method is superlinearly convergent when the objective function is strictly convex at the solution.     

On the convergence of the midpoint method

The midpoint method is an iterative method for the solution of nonlinear equations in a Banach space. Convergence results for this method have been studied in [3, 4, 9, 12]. Here we show how to improve and extend these results. In particular, we use hypotheses on the second Fréchet derivative of the nonlinear operator instead of the third-derivative hypotheses employed in the previous results and we obtain Banach space versions of some results that were derived in [9, 12] only in the real or complex space. We also provide various examples that validate our results.      

On the convergence of the MAOR method

In order to solve a linear system Ax = b, Hadjidimos et al. (1992) defined a class of modified AOR (MAOR) method, whose special case implies the MSOR method. In this paper, some sufficient and/or necessary conditions for convergence of the MAOR and MSOR methods will be achieved, when A is a two-cyclic matrix and when A is a Hermitian positive-definite matrix, an H-, L- or M-matrix, and a strictly or irreducibly diagonally dominant matrix. The convergence results on the MSOR method are better than some known theorems. The optimum parameters and the optimum spectral radii of the MAOR and MSOR methods are obtained, which also answers the open problem given by Hadjidimos et al.     

Influence of geometric properties of space on the convergence of Cauchy's method in the best-approximation problem

The reciprocity of certain geometrical properties of finite-dimensional Banach space is established. The role of these properties in the construction of best-approximation elements by Cauchy's method is investigated.Translated from Matematicheskie Zametki, Vol. 8, No. 3, pp. 329–338, September, 1970.The author wishes to thank N. I. Cherni for his valuable advice.