Numerical study of the basic stationary spherical couette flows at low Reynolds numbers

Previously developed iterative numerical methods with splitting of boundary conditions intended for solving an axisymmetric Dirichlet boundary value problem for the stationary Navier-Stokes system in spherical layers are used to study the basic spherical Couette flows (SCFs) of a viscous incompressible fluid in a wide range of outer-to-inner radius ratios R/r (1.1 ≤ R/r ≤ 100) and to classify such SCFs. An important balance regime is found in the case of counter-rotating boundary spheres. The methods converge at low Reynolds numbers (Re), but a comparison with experimental data for SCFs in thin spherical layers show that they converge for Re sufficiently close to Re_cr. The methods are second-order accurate in the max norm for both velocity and pressure and exhibit high convergence rates when applied to boundary value problems for Stokes systems arising at simple iterations with respect to nonlinearity. Numerical experiments show that the Richardson extrapolation procedure, combined with the methods as applied to solve the nonlinear problem, improves the accuracy up to the fourth and third orders for the stream function and velocity, respectively, while, for the pressure, the accuracy remains of the second order but the error is nevertheless noticeably reduced. This property is used to construct reliable patterns of stream-function level curves for large values of R/r. The possible configurations of fluid-particle trajectories are also discussed.     

A multigrid preconditioner for an adaptive Black-Scholes solver

This paper is concerned with the efficient solution of the linear systems of equations that arise from an adaptive space-implicit time discretisation of the Black-Scholes equation. These nonsymmetric systems are very large and sparse, so an iterative method will usually be the method of choice. However, such a method may require a large number of iterations to converge, particularly when the timestep used is large (which is often the case towards the end of a simulation which uses adaptive timestepping). An appropriate preconditioner is therefore desirable. In this paper we show that a very simple multigrid algorithm with standard components works well as a preconditioner for these problems. We analyse the eigenvalue spectrum of the multigrid iteration matrix for uniform grid problems and illustrate the method’s efficiency in practice by considering the results of numerical experiments on both uniform grids and those which use adaptivity in space.     

New GMRES(k)-Type Algorithms with Explicit Restarts and the Analysis of Their Convergence Properties Based on Matrix Relations in QR Form

The paper considers the problem of constructing a basic iterative scheme for solving systems of linear algebraic equations with unsymmetric and indefinite coefficient matrices. A new GMRES-type algorithm with explicit restarts is suggested. When restarting, this algorithm takes into account the spectral/singular data transferred using orthogonal matrix relations in the so-called QR form, which arise when performing inner iterations of Arnoldi type. The main idea of the algorithm developed is to organize inner iterations and the filtering of directions before restarting in such a way that, from one restart to another, matrix relations effectively accumulate information concerning the current approximate solution and, simultaneously, spectral/singular data, which allow the algorithm to converge with a rate comparable with that of the GMRES algorithm without restarts. Convergence theory is provided for the case of nonsingular, unsymmetric, and indefinite matrices. A bound for the rate of decrease of the residual in the course of inner Arnoldi-type iterations is obtained. This bound depends on the spectral/singular characterization of the subspace spanned by the directions retained upon filtering and is used in developing efficient filtering procedures. Numerical results are provided. Bibliography: 9 titles.     

Second-order iterations with guaranteed convergence

Recent results on optimal extrapolations of first-order stationary iterations have shown that they are necessarily divergent in a wide class of problems. This paper examines a second-order iterative process which is guaranteed to converge — in particular when applied to the solution of an arbitrary equation system. A general convergence theory for semi-iterative techniques is established at the same time.     

Multipoint boundary value problems for ODEs. part I

The method of quasilinearization is applied to multipoint boundary value problems of ordinary differential equations. It is shown that monotone iterations converge quadratically to the unique solution of our problem.     

On the asymptotic behaviour of some new gradient methods

The Barzilai-Borwein (BB) gradient method, and some other new gradient methods have shown themselves to be competitive with conjugate gradient methods for solving large dimension nonlinear unconstrained optimization problems. Little is known about the asymptotic behaviour, even when applied to n−dimensional quadratic functions, except in the case that n=2. We show in the quadratic case how it is possible to compute this asymptotic behaviour, and observe that as n increases there is a transition from superlinear to linear convergence at some value of n≥4, depending on the method. By neglecting certain terms in the recurrence relations we define simplified versions of the methods, which are able to predict this transition. The simplified methods also predict that for larger values of n, the eigencomponents of the gradient vectors converge in modulus to a common value, which is a similar to a property observed to hold in the real methods. Some unusual and interesting recurrence relations are analysed in the course of the study.This work was supported by the EPRSC in UK (no. GR/R87208/01) and the Chinese NSF grant (no. 10171104)     

Multipoint Boundary Value Problems for Odes. Part II

We apply the method of quasilinearization to multipoint boundary value problems for ordinary differential equations showing that the corresponding monotone iterations converge to the unique solution of our problem and this convergence is quadratic.     

On the partial synchronization of iterative methods

The rapidly growing field of parallel computing systems promotes the study of parallel algorithms, with the Monte Carlo method and asynchronous iterations being among the most valuable types. These algorithms have a number of advantages. There is no need for a global time in a parallel system (no need for synchronization), and all computational resources are efficiently loaded (the minimum processor idle time). The method of partial synchronization of iterations for systems of equations was proposed by the authors earlier. In this article, this method is generalized to include the case of nonlinear equations of the form x = F(x), where x is an unknown column vector of length n, and F is an operator from ?ⁿ into ?ⁿ. We consider operators that do not satisfy conditions that are sufficient for the convergence of asynchronous iterations, with simple iterations still converging. In this case, one can specify such an incidence of the operator and such properties of the parallel system that asynchronous iterations fail to converge. Partial synchronization is one of the effective ways to solve this problem. An algorithm is proposed that guarantees the convergence of asynchronous iterations and the Monte Carlo method for the above class of operators. The rate of convergence of the algorithm is estimated. The results can prove useful for solving high-dimensional problems on multiprocessor computational systems.     

The Role of Management Science

Many of the arguments that are found in the literature on the theme "O.R./M.S. in crisis" stem not just from alternative definitions of O.R./M.S., but from differences in strongly held views about its scope and role in organisations, and these are then reflected in the vehemence with which certain definitions are defended or criticised. It is when the hopes and aspirations of O.R./M.S. are compared with what is being achieved in practice, that we realise the degree to which O.R./M.S. has failed to live up to its original promise. In most organisations, O.R. analysts are expected and are happy to act as technicians and not as advisers, so that technique orientation and concern with tactical problems are constantly reinforced. In addition, managers in various functions have become aware of the potential contribution of analytical modelling in their own spheres and have begun to recruit analysts direct, resulting in the possible fragmentation of O.R. and the loss of its unique identity. The responsibilities of O.R./M.S. obviously relate not only to its organisational status, but also to an examination of and an identification with organisational goals. Many O.R. analysts are plainly more comfortable when these goals are clearly defined for them, an attitude which people from other professions will readily endorse, but if O.R./M.S. has any aspirations to get involved in strategic problems, it will have to pose questions about the validity and appropriateness of organisational goals and try to influence the formulation of problems accordingly.     

Control subspaces of minimal dimension. Elementary introduction. Discotheca

In this paper there is introduced and studied the following characteristic of a linear operator A acting on a Banach space Χ: , where Cyc A=R∶R is a subspace of Χ, dim R<+∞. Spqn (AⁿR∶n?0)=χ. Always disc A ?μ_A=(the multiplicity of the spectrum of the operator (dim R∶R∈Cyc A), where (by definition) in each A-cyclic subspace there is contained a cyclic subspace of dimension ? disc A. For a linear dynamical system x(t)=Ax(t)+Bu,(t) which is controllable, the characteristic disc A of the evolution operator A shows how much the control space can be diminished without losing controllability. In this paper there are established some general properties ofdisc (for example, conditions are given under which disc(A⊕B))=max(discA, disc B); disc is computed for the following operators: S (S is the shift in the Hardy space H²); disc S=2, (but μ_S=i); disc S _n ^* =n (butμ=1), where S_n=S⊕. ⊕S; disc S=2, (but μ_S=1), where S is the bilateral shift. It is proved that for a normal operator N with simple spectrum, disc N=μ_N=1 ? (the operator N is reductive). There are other results also, and also a list of unsolved problems.     

Convergence Properties of the Successive Extrapolated Relaxation (S.E.R.) Method

Extrapolation methods to accelerate convergence of a sequenceof iterates are investigated. A transformation formula derivedfrom the related deterministic sequence is modified so thatit may be used for the stochastic sequences. The S.E.R. method,which is related to Aitken's ² process, is discussed. For linearlyconvergent sequences it is shown that S.E.R. not only will convergeif the original sequence converges, but will converge to thesame limit. An analysis of the bounds for the convergence andthe perturbations is made for Aitken's ² process, S.E.R. andS.E.O.R. The method is applicable to convergent and locallyconvergent vector sequences.     

Models and algorithms for skip-free Markov decision processes on trees

We introduce a class of models for multidimensional control problems that we call skip-free Markov decision processes on trees. We describe and analyse an algorithm applicable to Markov decision processes of this type that are skip-free in the negative direction. Starting with the finite average cost case, we show that the algorithm combines the advantages of both value iteration and policy iteration—it is guaranteed to converge to an optimal policy and optimal value function after a finite number of iterations but the computational effort required for each iteration step is comparable with that for value iteration. We show that the algorithm can also be used to solve discounted cost models and continuous-time models, and that a suitably modified algorithm can be used to solve communicating models.     

Newton's method with mesh refinements for numerical solution of nonlinear two-point boundary value problems

Summary The object of this paper is the numerical solution of nonlinear two-point boundary value problems by Newton's method applied to the discretized problem on successively refined grids. The first part consists of a theoretical development of a phenomenon that often occurs in practice, namely, that the number of iterations for Newton's method to converge to within a fixed tolerance and for a fixed starting vector is essentially independent of the mesh size. The second part develops a process based on these results for determining an efficient mesh refinement strategy. Numerical results are also provided.This work was supported by N.S.F. grant GJ42626     

Limits of the Letac principle. The discrete case

The Letac principle says that if the backward iterations of a random function converge almost surely, then the forward iterations converge in distribution. In this paper, we find conditions for the inverse implication to hold.     

On attraction of linearly constrained Lagrangian methods and of stabilized and quasi-Newton SQP methods to critical multipliers

It has been previously demonstrated that in the case when a Lagrange multiplier associated to a given solution is not unique, Newton iterations [e.g., those of sequential quadratic programming (SQP)] have a tendency to converge to special multipliers, called critical multipliers (when such critical multipliers exist). This fact is of importance because critical multipliers violate the second-order sufficient optimality conditions, and this was shown to be the reason for slow convergence typically observed for problems with degenerate constraints (convergence to noncritical multipliers results in superlinear rate despite degeneracy). Some theoretical and numerical validation of this phenomenon can be found in Izmailov and Solodov (Comput Optim Appl 42:231–264, 2009; Math Program 117:271–304, 2009). However, previous studies concerned the basic forms of Newton iterations. The question remained whether the attraction phenomenon still persists for relevant modifications, as well as in professional implementations. In this paper, we answer this question in the affirmative by presenting numerical results for the well known MINOS and SNOPT software packages applied to a collection of degenerate problems. We also extend previous theoretical considerations to the linearly constrained Lagrangian methods and to the quasi-Newton SQP, on which MINOS and SNOPT are based. Experiments also show that in the stabilized version of SQP the attraction phenomenon still exists but appears less persistent.     

On Brown's and Newton's methods with convexity hypotheses

In the context of the monotone Newton theorem (MNT) it has been conjectured that discretised Brown iterations converge at least as fast as discretised Newton iterations, because such is the case for analytic iterations. With easily verified hypotheses, it is proved here that Brown analytic iterations converge strictly faster than Newton ones. As a consequence, the same result holds for discretised iterations with conveniently small incremental steps. However, in the general context of the MNT, it may happen that Newton's discretised method converges faster than Brown's, but this situation can be remedied in many cases by conveniently shifting the initial value, so that those hypotheses ensuring the reverse are satisfied. Thus, a fairly effective solution is given to the problem stated initially.     

The Art of Course Planning: Soft O.R. in Action

This article is a case study described from two viewpoints: that of an analyst and that of a ‘decision-maker’. It describes the use of two ‘soft O.R.’ methods in helping the members of a university O.R. group to plan revisions to a postgraduate Diploma course, resulting in the implementation of an improved course. One author conducted the exercise while the other was a member of the client group. Given that case studies are usually written by the analyst alone, it is hoped that a client's eye-view will be useful as feedback for practitioners and can also introduce some of the concepts and terminology of soft O.R. to those engaged in more mathematical O.R. activities.     

Pricing Policy Models: A Case Study in Practical O.R.

A simple but robust and widely applicable approach to determining the price discount to use during periodic sales promotions is described. The approach provides an illustration of O.R. methodology, and it is discussed in the context of a problem formulation exercise used for O.R. courses. This discussion clarifies alternatives and provides cautionary notes for those wishing to implement the approach.     

Evaluations of Parameters for the Optimization of S.S.O.R. and A.D.I. Preconditioning

The main goal of this paper is to give two ways to estimate the needed parameters in order to obtain the condition number of S.S.O.R. preconditioned matrices, namely, the algebraic matricial formulation of convexity Riesz theorem and the tridiagonal Fourier analysis. The improvement with respect to Axelsson's approach is explicitly given. Estimations of the condition number in the case of A.D.I. preconditioning is also considered.     

On relaxation methods for systems of linear inequalities

In their classical papers Agmon and Motzkin and Schoenberg introduced a relaxation method to find a feasible solution for a system of linear inequalities. So far the method was believed to require infinitely many iterations on some problem instances since it could (depending on the dimension of the set of feasible soltions) converge asymptotically to a feasible solution, if one exists. Hence it could not be used to determine infeasibility.Using two lemma's basic to Khachian's polynomially bounded algorithm we can show that the relaxation method is finite in all cases and thus can handle infeasible systems as well. In spite of more refined stopping criteria the worst case behaviour of the relaxation method is not polynomially bounded as examplified by a class of problems constructed here.