Exact SOR convergence regions for a general class ofp-cyclic matrices

Linear systems whose associated block Jacobi iteration matrixB is weakly cyclic generated by the cyclic permutation = (₁,₂,..., _p ) in the spirit of Li and Varga are considered. Regions of convergence for the corresponding blockp-cyclic SOR method are derived and the exact convergence domains for real spectra, (B ^p ), of the same sign are obtained. Moreover, analytical expressions for two special cases forp = 5 are given and numerical results are presented confirming the theory developed. The tools used for this work are mainly from complex analysis and extensive use of (asteroidal) hypocycloids in the complex plane is made to produce our results.This work was supported in part by AFOSR grant F49620-92-J-0069 and NSF grant 9202536-CCR.     

Preconditioned sor methods for generalized least-squares problems

1.IntroductionThegeneralizedleastsquaresproblem,definedasmin(Ax--b)"W--'(Ax--b),(1.1)xacwhereAERm",m>n,bERm,andWERm'misasymmetricandpositivedefinitematrix,isfrequentlyfoundwhensolvingproblemsinstatistics,engineeringandeconomics.Forexample,wegetgeneralizedleastsquaresproblemswhensolvingnonlinearregressionanalysisbyquasi-likelihoodestimation,imagereconstructionproblemsandeconomicmodelsobtainedbythemaximumlikelihoodmethod(of.[1,21).Paige[3,4]investigatestheproblemexplicitly.Hechangestheorig…     

Old and new from SOR

From the long history of Successive Over Relaxation (SOR) between the end of second world war and today three points are considered: (1) Classical results of Young and Varga are described. (2) It is shown how results on semiiterative methods can be used to derive these classical results in a unifying way and to compare SOR with other iterative methods. (3) In the last 15 years the application of SOR to compute the stationary distribution of a homogeneous Markov chain has been discussed. These results are reported, considering especially the term extended convergence introduced by Kontovasilis, Plemmons and Stewart.     

GSOR方法最优迭代参数的简化推导

对于增广线性系统,Bai等研究了广义SOR方法（Bai Z Z,Parlett B,Wang Z Q.On generaliged successive overrelaxation methods for augmented linear systems.Numerische Mathematik,2005,102（1）：1-38）,并得到其最优迭代参数.给出了另外一种推导最优迭代参数的简化方法,这种方法对于求解其他参数加速定常迭代方法的最优迭代参数非常有意义.     

A multicolour SOR method for the finite-element method

In this paper we present several algorithms to reorder unknowns in a finite-element mesh so that we can use the multicolour SOR method to solve the corresponding linear system on a pipelined computer or on a parallel computer. We also discuss the assembling process by reordering elements with our algorithms. Numerical tests on a pipelined computer indicate the efficiency of the multicolour SOR method.     

确定SOR最佳松弛因子的一个实用算法

SOR迭代方法中的最佳松弛因子的确定 ,是数值代数中的一个理论难题。本文采用优化技术中简便的直接搜索法 ,构造出近似确定最佳松弛因子的数值算法 ,并由此得出一个具有近似确定ωop t功能的自适应 SOR算法 ,数值算例表明 :该算法是实用和快捷的。     

USSOR优于SOR,SSOR的收敛区域

对于SSOR与SOR的渐近收敛速度的比较,有下面的一些结果。 (a)当A为非奇异的M-矩阵,Woznicki[1]证明了,ρ(S_w~A)≤户((?)_w~A)<1,(?)ω∈(0,1)且(?)V=卢(B~A)∈(0,1)。 (b)当A为3—循环不可约的H—矩阵,Neumann[2]证明了,对每个(?):=卢(|B~A|)∈(0,r_3),r_3≈0.418192802是方程17r~3+r~3—r—1=0在区间(0,1)内的唯一正根,则存在ω(A)=2/(1+(?))的一个邻域Ω_(w(a)),满足     

Parallel gradient projection successive overrelaxation for symmetric linear complementarity problems and linear programs

A gradient projection successive overrelaxation (GP-SOR) algorithm is proposed for the solution of symmetric linear complementary problems and linear programs. A key distinguishing feature of this algorithm is that when appropriately parallelized, the relaxation factor interval (0, 2) isnot reduced. In a previously proposed parallel SOR scheme, the substantially reduced relaxation interval mandated by the coupling terms of the problem often led to slow convergence. The proposed parallel algorithm solves a general linear program by finding its least 2-norm solution. Efficiency of the algorithm is in the 50 to 100 percent range as demonstrated by computational results on the CRYSTAL token-ring multicomputer and the Sequent Balance 21000 multiprocessor.This material is based on research supported by National Science Foundation Grants DCR-8420963 and DCR-8521228 and Air Force Office of Scientific Research Grants AFOSR-86-0172 and AFOSR-86-0255.     

Exterior point algorithms for nearest points and convex quadratic programs

We consider the problem of finding the nearest point (by Euclidean distance) in a simplicial cone to a given point, and develop an exterior penalty algorithm for it. Each iteration in the algorithm consists of a single Newton step following a reduction in the value of the penalty parameter. Proofs of convergence of the algorithm are given. Various other versions of exterior penalty algorithms for nearest point problems in nonsimplicial polyhedral cones and for convex quadratic programs, all based on a single descent step following a reduction in the value of the penalty parameter per iteration, are discussed. The performance of these algorithms in large scale computational experiments is very encouraging. It shows that the number of iterations grows very slowly, if at all, with the dimension of the problem.Partially supported by NSF Grant No. ECS-8521183, and by the two universities.     

广义鞍点问题的改进的类SOR算法

针对广义鞍点问题,本文提出了一个改进的类逐次超松弛迭代算法,在较弱的条件下,分析了算法的收敛性及线性收敛率.新算法的每步计算量与已有的算法类似,都是需要（近似）求解线性方程组,但新算法有更好的灵活度通过合适地选取参数矩阵,每一步子问题可以容易地求解,甚至可以有闭式解（closed-form solution）.数值实验结果显示了新算法的有效性.