Semiconvergence of block SOR method for singular linear systems with p-cyclic matrices

In this paper, we discuss semiconvergence of the block SOR method for solving singular linear systems with p-cyclic matrices. Some sufficient conditions for the semiconvergence of the block SOR method for solving a general p-cyclic singular system are proved.     

Optimal successive overrelaxation iterative methods for P-cyclic matrices

Summary We consider linear systems whose associated block Jacobi matricesJ _p are weakly cyclic of indexp. In a recent paper, Pierce, Hadjidimos and Plemmons [13] proved that the block two-cyclic successive overrelaxation (SOR) iterative method is numerically more effective than the blockq-cyclic SOR-method, 2<qp, if the eigenvalues ofJ _p ^p are either all non-negative or all non-positive. Based on the theory of stationaryp-step methods, we give an alternative proof of their theorem. We further determine the optimal relaxation parameter of thep-cyclic SOR method under the assumption that the eigenvalues ofJ _p ^p are contained in a real interval, thereby extending results due to Young [19] (for the casep=2) and Varga [15] (forp>2). Finally, as a counterpart to the result of Pierce, Hadjidimos and Plemmons, we show that, under this more general assumption, the two-cyclic SOR method is not always superior to theq-cyclic SOR method, 2<qp.Dedicated to R. S. Varga on the occasion of his 60th birthdayResearch supported in part by the Deutsche Forschungsgemeinschaft     

A note on Hermitian splitting induced relaxation methods for convection-diffusion equations

The solution of the linear system Ax = b by iterative methods requires a splitting of the coefficient matrix in the form A = M − N where M is usually chosen to be a diagonal or a triangular matrix. In this article we study relaxation methods induced by the Hermitian and skew-Hermitian splittings for the solution of the linear system arising from a compact fourth order approximation to the one dimensional convection-diffusion equation and compare the convergence rates of these relaxation methods to that of the widely used successive overrelaxation (SOR) method. Optimal convergence parameters are derived for each method and numerical experiments are given to supplement the theoretical estimates. For certain values of the diffusion parameter, a relaxation method based on the Hermitian splitting converges faster than SOR. For two-dimensional problems a block form of the iterative algorithm is presented. © 1998 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 14: 581–591, 1998     

Some extensions of the improved modified Gauss–Seidel iterative method for H‐matrices

In this paper, first we present a convergence theorem of the improved modified Gauss–Seidel iterative method, referred to as the IMGS method, for H‐matrices and compare the range of parameters α_i with that of the parameter ω of the SOR iterative method. Then with a more general splitting, the convergence analysis of this method for an H‐matrix and its comparison matrix is given. The spectral radii of them are also compared. Copyright © 2006 John Wiley & Sons, Ltd.     

Optimality relationships forp-cyclic SOR

Summary The optimality question for blockp-cyclic SOR iterations discussed in Young and Varga is answered under natural conditions on the spectrum of the block Jacobi matrix. In particular, it is shown that repartitioning a blockp-cyclic matrix into a blockq-cyclic form,q, results in asymptotically faster SOR convergence for the same amount of work per iteration. As a consequence block 2-cyclic SOR is optimal under these conditions.Research supported in part by the US Air Force under Grant no. AFOSR-88-0285 and the National Science Foundation under grant no. DMS-85-21154 Present address: Boeing Computer Services, P.O. Box 24346, MS 7L-21, Seattle, WA 98124-0346, USA     

Optimal Semi-Iterative Methods for Complex SOR with Results from Potential Theory

We consider the application of semi-iterative methods (SIM) to the standard (SOR) method with complex relaxation parameter ω, under the following two assumptions: (1) the associated Jacobi matrix J is consistently ordered and weakly cyclic of index 2, and (2) the spectrum σ(J) of J belongs to a compact subset Σ of the complex plane , which is symmetric with respect to the origin. By using results from potential theory, we determine the region of optimal choice of for the combination SIM–SOR and settle, for a large class of compact sets Σ, the classical problem of characterising completely all the cases for which the use of the SIM-SOR is advantageous over the sole use of SOR, under the hypothesis that . In particular, our results show that, unless the outer boundary of Σ is an ellipse, SIM–SOR is always better and, furthermore, one of the best possible choices is an asymptotically optimal SIM applied to the Gauss–Seidel method. In addition, we derive the optimal complex SOR parameters for all ellipses which are symmetric with respect to the origin. Our work was motivated by recent results of M.Eiermann and R.S. Varga.Dedicated to Professor Richard S. Varga in recognition of his substantial contributions to the subject of the paper.     

An improved general extra-gradient method with refined step size for nonlinear monotone variational inequalities

Extra-gradient method and its modified versions are direct methods for variational inequalities VI(Ω, F) that only need to use the value of function F in the iterative processes. This property makes the type of extra-gradient methods very practical for some variational inequalities arising from the real-world, in which the function F usually does not have any explicit expression and only its value can be observed and/or evaluated for given variable. Generally, such observation and/or evaluation may be obtained via some costly experiments. Based on this view of point, reducing the times of observing the value of function F in those methods is meaningful in practice. In this paper, a new strategy for computing step size is proposed in general extra-gradient method. With the new step size strategy, the general extra-gradient method needs to cost a relatively minor amount of computation to obtain a new step size, and can achieve the purpose of saving the amount of computing the value of F in solving VI(Ω, F). Further, the convergence analysis of the new algorithm and the properties related to the step size strategy are also discussed in this paper. Numerical experiments are given and show that the amount of computing the value of function F in solving VI(Ω, F) can be saved about 12–25% by the new general extra-gradient method.     

Optimum first and second order extrapolations of Successive Overrelaxation type methods for certain classes of matrices

This paper deals with the iterative solution of the linear systemx=Bx+c when its Jacobi matrixB is weakly 2-cyclic consistently ordered and has a complex eigenvalue spectrum which lies on a straight-line segment. The optimization problem of the following three methods is considered and solved: i) The extrapolation of the optimum Successive Overrelaxation (SOR) ii) The second order extrapolation of a good SOR and iii) The second order extrapolation of the Gauss-Seidel method. In addition a variant of the second order methods considered, suitable for the solution of the system even ifB isnot necessarily weakly 2-cyclic consistently ordered, is proposed. Finally a reference to a theoretical comparison of the various optimum methods in the paper is made and their asymptotic convergence factors for selected eigenvalue spectra are illustrated in a Table in support of the theory developed.     

On the Location of Pseudozeros of a Complex Interval Polynomial

Given a univariate complex interval polynomial F, we provide a rigorous method for deciding whether there exists a pseudozero of F in a prescribed closed complex domain D. Here a pseudozero of F is defined to be a zero of some polynomial in F. We use circular intervals and assume that the boundary C of D is a simple curve and that C is the union of a finite number of arcs, each of which is represented by a rational function. When D is not bounded, we assume further that all the polynomials in F are of the same degree. Examples of such domains are the outside of an open disk and a half-plane with boundary. Our decision method uses the representation of C and the property that a polynomial in F is of degree 1 with respect to each coefficient regarded as a variable.      

Application of the Rank-Factorization Method to the Analysis of Spectral Characteristics of Multiparameter Polynomial Matrices

The method of rank factorization (the W-q method), previously suggested by the author as a method for solving algebraic problems for a multiparameter matrix F polynomially dependent on parameters, is applied to analyze the finite spectrum of F. Special attention is paid to the part of the spectrum [F] of the q-parameter matrix F whose points are independent of at least one of the spectral parameters. Bibliography: 6 titles.     

Convergence of a direct-iterative method for large-scale least-squares problems

In 1975 Chen and Gentleman suggested a 3-block SOR method for solving least-squares problems, based on a partitioning scheme for the observation matrix A into

$\text{A=}\text{A}{}_1\text{A}{}_2$

where A₁ is square and nonsingular. In many cases A₁ is obvious from the nature of the problem. This combined direct-iterative method was discussed further and applied to angle adjustment problems in geodesy, where A₁ is easily formed and is large and sparse, by Plemmons in 1979. Recently, Niethammer, de Pillis, and Varga have rekindled interest in this method by correcting and extending the SOR convergence interval. The purpose of our paper is to discuss an alternative formulation of the problem leading to a 2-block SOR method. For this formulation it is shown that the resulting direct-iterative method always converges for sufficiently small SOR parameter, in contrast to the 3-block formulation. Formulas for the optimum SOR parameter and the resulting asymptotic convergence factor, based upon 6A₂A^-1₁6₂, are given. Furthermore, it is shown that this 2-cyclic block SOR method always gives better convergence results than the 3-cyclic one for the same amount of work per iteration. The direct part of the algorithm requires only a sparse-matrix factorization of A₁. Our purpose here is to establish theoretical convergence results, in line with the purpose of the recent paper by Niethammer, de Pillis, and Varga. Practical considerations of choosing A₁ in certain applications and of estimating the resulting 6A₂A^-1₁6₂ will be addressed elsewhere.     

Solution of monotone complementarity problems with locally Lipschitzian functions

The paper deals with complementarity problems CP(F), where the underlying functionF is assumed to be locally Lipschitzian. Based on a special equivalent reformulation of CP(F) as a system of equationsφ(x)=0 or as the problem of minimizing the merit functionΘ=1/2∥Φ∥ ₂ ² , we extend results which hold for sufficiently smooth functionsF to the nonsmooth case. In particular, ifF is monotone in a neighbourhood ofx, it is proved that 0 εδθ(x) is necessary and sufficient forx to be a solution of CP(F). Moreover, for monotone functionsF, a simple derivative-free algorithm that reducesΘ is shown to possess global convergence properties. Finally, the local behaviour of a generalized Newton method is analyzed. To this end, the result by Mifflin that the composition of semismooth functions is again semismooth is extended top-order semismooth functions. Under a suitable regularity condition and ifF isp-order semismooth the generalized Newton method is shown to be locally well defined and superlinearly convergent with the order of 1+p.     

Codimensions of Newton strata for <Emphasis Type="Italic">SL</Emphasis><Subscript>3</Subscript>(<Emphasis Type="Italic">F</Emphasis>) in the Iwahori case

We study the Newton stratification on SL ₃(F), where F is a Laurent power series field. We provide a formula for the codimensions of the Newton strata inside each component of the affine Bruhat decomposition on SL ₃(F). These calculations are related to the study of certain affine Deligne–Lusztig varieties. In particular, we describe a method for determining which of these varieties is non-empty in the case of SL ₃(F).     

Computation of generalized differentials in nonlinear complementarity problems

Let f and g be continuously differentiable functions on R ⁿ . The nonlinear complementarity problem NCP(f,g), 0≤f(x)⊥g(x)≥0, arises in many applications including discrete Hamilton-Jacobi-Bellman equations and nonsmooth Dirichlet problems. A popular method to find a solution of the NCP(f,g) is the generalized Newton method which solves an equivalent system of nonsmooth equations F(x)=0 derived by an NCP function. In this paper, we present a sufficient and necessary condition for F to be Fréchet differentiable, when F is defined by the “min” NCP function, the Fischer-Burmeister NCP function or the penalized Fischer-Burmeister NCP function. Moreover, we give an explicit formula of an element in the Clarke generalized Jacobian of F defined by the “min” NCP function, and the B-differential of F defined by other two NCP functions. The explicit formulas for generalized differentials of F lead to sharper global error bounds for the NCP(f,g).     

A Smoothing Newton Method for General Nonlinear Complementarity Problems

Smoothing Newton methods for nonlinear complementarity problems NCP(F) often require F to be at least a P ₀-function in order to guarantee that the underlying Newton equation is solvable. Based on a special equation reformulation of NCP(F), we propose a new smoothing Newton method for general nonlinear complementarity problems. The introduction of Kanzow and Pieper's gradient step makes our algorithm to be globally convergent. Under certain conditions, our method achieves fast local convergence rate. Extensive numerical results are also reported for all complementarity problems in MCPLIB and GAMSLIB libraries with all available starting points.     

The Operator Factorization Method in Inverse Obstacle Scattering

The standard factorization method from inverse scattering theory allows to reconstruct an obstacle pointwise from the normal far field operator F. The kernel of this method is the study of the first kind Fredholm integral equation (F^* F)^1/4 f = Φ_z with the right-hand part In this paper we extend the factorization method to cover some kinds of boundary conditions which leads to non-normal far field operators. We visualize the scatterer explicitly in terms of the singular system of the selfadjoint positive operator F_# = [(ReF)^* (ReF)]^1/2 + ImF. The following characterization criterium holds: a given point z is inside the obstacle if and only if the function Φ_z belongs to the range of F_#^1/2. Our operator approach provides the tool for treatment of a wide class of inverse elliptic problems.     

Waiting Time Problems in a Two-State Markov Chain

Let F ₀ be the event that l ₀ 0-runs of length k ₀ occur and F ₁ be the event that l ₁ 1-runs of length k ₁ occur in a two-state Markov chain. In this paper using a combinatorial method and the Markov chain imbedding method, we obtained explicit formulas of the probability generating functions of the sooner and later waiting time between F ₀ and F ₁ by the non-overlapping, overlapping and "greater than or equal" enumeration scheme. These formulas are convenient for evaluating the distributions of the sooner and later waiting time problems.     

A stationary iterative pseudoinverse algorithm

Iterative methods applied to the normal equationsA ^T Ax=A ^T b are sometimes used for solving large sparse linear least squares problems. However, when the matrix is rank-deficient many methods, although convergent, fail to produce the unique solution of minimal Euclidean norm. Examples of such methods are the Jacobi and SOR methods as well as the preconditioned conjugate gradient algorithm. We analyze here an iterative scheme that overcomes this difficulty for the case of stationary iterative methods. The scheme combines two stationary iterative methods. The first method produces any least squares solution whereas the second produces the minimum norm solution to a consistent system. This work was supported by the Swedish Research Council for Engineering Sciences, TFR.     

The Jost-Lehmann-Dyson representation and target mass effects

We develop a method for taking target mass effects into account for the structure functions of inelastic lepton-hadron scattering using analytic moments in the variable s instead of the well-known Nachtmann variable ξ and Bjorken variable x. We find new expressions for the structure functions F ₁, F ₂, and F ₃ that depend on the target mass and agree with the spectral property.     

Optimal Control of an M/G/1/K Queueing System with Combined <Emphasis Type="Italic">F</Emphasis> Policy and Startup Time

We investigate the optimal management problem of an M/G/1/K queueing system with combined F policy and an exponential startup time. The F policy queueing problem investigates the most common issue of controlling the arrival to a queueing system. We present a recursive method, using the supplementary variable technique and treating the supplementary variable as the remaining service time, to obtain the steady state probability distribution of the number of customers in the system. The method is illustrated analytically for exponential service time distribution. A cost model is established to determine the optimal management F policy at minimum cost. We use an efficient Maple computer program to calculate the optimal value of F and some system performance measures. Sensitivity analysis is also investigated.