广义加速超松弛方法解线性互补问题
|
摘要
从20世纪60年代线性互补问题的提出到现在,尤其是最近20多年来,线性互补问题发展迅速。它被广泛地应用于工程、经济和运筹学中,对线性互补问题的研究可以分为理论和算法两个方面,前者主要研究问题解的存在性、唯一性、稳定性以及灵敏度分析等性质;后者集中研究如何构造有效算法及其理论分析。本文主要研究一种解线性互补问题的数值解法:广义加速超松弛算法。
在本文中我们主要研究用广义加速超松弛迭代方法(简称为GAOR方法)来解线性互补问题LCP ( M,q),其中M是一个n×n阶的非奇异矩阵, q∈Rn。在论文的第一部分,我们首先提出了一类解决线性互补问题的广义AOR方法,其特殊情况转化为广义的SOR方法。
在第二部分中我们讨论了所提出的两种算法的收敛性,对于GAOR方法给出了下面的结论:当系数矩阵M = ( m_(kj) )∈Rn×n是对角元素均为正数的H ?矩阵,且分裂M = D+L+U满足时,若α∈R~+,其中J = D~(-1)(L+U),则对任一初始向量z~0∈R~n,由GAOR方法产生的迭代序列{ z~p}收敛于LCP ( M,q)的唯一解z~*∈R~n,并且满足:当0 <α≤1时,当α≥1时。
作为GAOR方法的特殊情况,我们也得到了GSOR方法的收敛性质,而由于一个M -矩阵也是一个H -矩阵,所以上面的结论也适用于M -矩阵,而且对角元素均为正的严格或不可约对角占优矩阵也满足结论的条件,则上述结果对这些矩阵也成立。
第三部分中我们主要考虑两种算法的单调收敛性质,我们得到了这样的结论:当M∈Rn×n是L ?矩阵,且当0 <ωi≤1,i=1,2,n,0<α≤1时,则对任一初始向量z 0∈?,由GAOR方法或GSOR方法产生的迭代序列{ zp },p=0,1,2,有下面的两个性质:
(1) 0≤z p +1≤zp≤z0;
(2) lim zpz*p→∞=,其中z *是LCP ( M,q)的唯一解。
在这一部分中我们还讨论了参数ωi , i=1,2,n和参数α对GAOR方法和GSOR方法的收敛速度的影响,得出了当参数ω1 =ω2=ωn =α=1时能导致更快的收敛速度,这也意味着导致两种方法收敛速度最快的参数可能在[1 ,∞)中,也即
在最后一部分中,我们用一个数值例子来验证第三部分所得出的结论,也即当各个参数越接近于1时,由GAOR方法所产生的迭代序列收敛于所求线性互补问题的精确解所需的迭代次数就越少,也就是说收敛速度越快。
Linear complementarity problems have been developed very quickly since they appeared in the 60s last century, especially the recent two decades. And they were widely used in engineering, economics and operations research. Roughly speaking, the study of the linear complementarity problems can be classified into two classes: theories and algorithms. The former is devoted to the existence, uniqueness, stability and sensitivity analysis of the solutions, while the latter is intended to solve the problems efficiently, together with the theoretical analysis of the algorithms. We will consider a class of method for solving the linear complementarity problem: generalized accelerated overrelaxation methods.
In this paper, we will consider the generalized accelerated overrelaxation (GAOR ) methods for solving the linear complementarity problem LCP ( M,q), where M is an n×n nonsingular matrix, q∈Rn. In section one, a class of GAOR methods, in which one special case reduces to GSOR methods, for solving the linear complementarity problems are firstly proposed.
In section two, we discuss the convergence of the GAOR and the GSOR methods, for the GAOR methods, we describe its convergence: when the system matrix M = ( mkj )∈R×is an H ?matrix with positive diagonal elements and let the splitting M = D+L+U satisfy M = D?L?U. If 0 <ωi <1 +ρ2(J), i = 1,2,n, andα∈R+,then for any initial guess z 0∈Rn, the iterative sequence { z p} generated by the GAOR methods converges to the unique solution z * of the LCP ( M,q) and
As the special case, for the GSOR methods, we also have the convergence results. It is clearly that an M ?matrix is also an H ?matrix, hence, the statements are valid for the M ?matrix, since a strictly or irreducible diagonally dominant matrix with positive diagonal elements is also satisfying the condition of the theorem, then the results are also valid for these matrices.
In section three, we consider the monotone convergence of the two methods, we get the result of the monotone convergence of the two methods: assume that M∈Rn×n is an L ?matrix. Also, assume that 0 <ωi≤1,i=1,2,n,0<α≤1. Then for any initial vector z 0∈? , the iterative sequence { z p },p=0,1,2,, generated by the GAOR methods or the GSOR methods has the following properties:
(1) 0≤z p +1≤zp≤z0, p =0,1,2,;
(2) lim zpz*p→∞= is the unique solution of the LCP ( M,q).
In this section, we also discuss the influence of the parametersωi, i = 1,2,n andαupon the convergence rate of the GAOR and GSOR methods. We can get the result that the parameter collectionsω1 =ω2==ωn =α=1 can result in faster convergence rate of the GAOR and GSOR methods under the assumptions. This also implies that the optimum parameters, in general, should beα*ω1*,ω2*,ωn*∈[1 ,∞).
Finally, a numerical example is used to validate the results proved in section three, that is, the larger the parameters are, the smaller the number of iterations are needed by the sequence to converge to the required accurate solution. In other words, the converg- ence rate is much quicker.
在本文中我们主要研究用广义加速超松弛迭代方法(简称为GAOR方法)来解线性互补问题LCP ( M,q),其中M是一个n×n阶的非奇异矩阵, q∈Rn。在论文的第一部分,我们首先提出了一类解决线性互补问题的广义AOR方法,其特殊情况转化为广义的SOR方法。
在第二部分中我们讨论了所提出的两种算法的收敛性,对于GAOR方法给出了下面的结论:当系数矩阵M = ( m_(kj) )∈Rn×n是对角元素均为正数的H ?矩阵,且分裂M = D+L+U满足时,若α∈R~+,其中J = D~(-1)(L+U),则对任一初始向量z~0∈R~n,由GAOR方法产生的迭代序列{ z~p}收敛于LCP ( M,q)的唯一解z~*∈R~n,并且满足:当0 <α≤1时,当α≥1时。
作为GAOR方法的特殊情况,我们也得到了GSOR方法的收敛性质,而由于一个M -矩阵也是一个H -矩阵,所以上面的结论也适用于M -矩阵,而且对角元素均为正的严格或不可约对角占优矩阵也满足结论的条件,则上述结果对这些矩阵也成立。
第三部分中我们主要考虑两种算法的单调收敛性质,我们得到了这样的结论:当M∈Rn×n是L ?矩阵,且当0 <ωi≤1,i=1,2,n,0<α≤1时,则对任一初始向量z 0∈?,由GAOR方法或GSOR方法产生的迭代序列{ zp },p=0,1,2,有下面的两个性质:
(1) 0≤z p +1≤zp≤z0;
(2) lim zpz*p→∞=,其中z *是LCP ( M,q)的唯一解。
在这一部分中我们还讨论了参数ωi , i=1,2,n和参数α对GAOR方法和GSOR方法的收敛速度的影响,得出了当参数ω1 =ω2=ωn =α=1时能导致更快的收敛速度,这也意味着导致两种方法收敛速度最快的参数可能在[1 ,∞)中,也即
在最后一部分中,我们用一个数值例子来验证第三部分所得出的结论,也即当各个参数越接近于1时,由GAOR方法所产生的迭代序列收敛于所求线性互补问题的精确解所需的迭代次数就越少,也就是说收敛速度越快。
Linear complementarity problems have been developed very quickly since they appeared in the 60s last century, especially the recent two decades. And they were widely used in engineering, economics and operations research. Roughly speaking, the study of the linear complementarity problems can be classified into two classes: theories and algorithms. The former is devoted to the existence, uniqueness, stability and sensitivity analysis of the solutions, while the latter is intended to solve the problems efficiently, together with the theoretical analysis of the algorithms. We will consider a class of method for solving the linear complementarity problem: generalized accelerated overrelaxation methods.
In this paper, we will consider the generalized accelerated overrelaxation (GAOR ) methods for solving the linear complementarity problem LCP ( M,q), where M is an n×n nonsingular matrix, q∈Rn. In section one, a class of GAOR methods, in which one special case reduces to GSOR methods, for solving the linear complementarity problems are firstly proposed.
In section two, we discuss the convergence of the GAOR and the GSOR methods, for the GAOR methods, we describe its convergence: when the system matrix M = ( mkj )∈R×is an H ?matrix with positive diagonal elements and let the splitting M = D+L+U satisfy M = D?L?U. If 0 <ωi <1 +ρ2(J), i = 1,2,n, andα∈R+,then for any initial guess z 0∈Rn, the iterative sequence { z p} generated by the GAOR methods converges to the unique solution z * of the LCP ( M,q) and
As the special case, for the GSOR methods, we also have the convergence results. It is clearly that an M ?matrix is also an H ?matrix, hence, the statements are valid for the M ?matrix, since a strictly or irreducible diagonally dominant matrix with positive diagonal elements is also satisfying the condition of the theorem, then the results are also valid for these matrices.
In section three, we consider the monotone convergence of the two methods, we get the result of the monotone convergence of the two methods: assume that M∈Rn×n is an L ?matrix. Also, assume that 0 <ωi≤1,i=1,2,n,0<α≤1. Then for any initial vector z 0∈? , the iterative sequence { z p },p=0,1,2,, generated by the GAOR methods or the GSOR methods has the following properties:
(1) 0≤z p +1≤zp≤z0, p =0,1,2,;
(2) lim zpz*p→∞= is the unique solution of the LCP ( M,q).
In this section, we also discuss the influence of the parametersωi, i = 1,2,n andαupon the convergence rate of the GAOR and GSOR methods. We can get the result that the parameter collectionsω1 =ω2==ωn =α=1 can result in faster convergence rate of the GAOR and GSOR methods under the assumptions. This also implies that the optimum parameters, in general, should beα*ω1*,ω2*,ωn*∈[1 ,∞).
Finally, a numerical example is used to validate the results proved in section three, that is, the larger the parameters are, the smaller the number of iterations are needed by the sequence to converge to the required accurate solution. In other words, the converg- ence rate is much quicker.
引文
[1] A.Berman, R.J.plemmons, Nonnegative Matrix in the Mathematical Sciences, Academic Press, NewYork, 1979.
[2] B.H.Ahn. Solution of nonsymmetric linear complementarity problems by iterative methods, J.Optim. Theory Appl. 33(1981)175-185.
[3] D.Yuan, Convergence of parallel chaotic AOR method for H ?matrix, DCABES 2001 proceedings 24-28.
[4] D.Yuan, Y.Song, Modified AOR methods for linear complementarity problem, Appl. Math. Comput. 140(2003) 53-67.
[5] D.R.Wang, On the convergence of the parallel multisplitting AOR algorithm, Linear Algebra Appl. 154/156(1991) 473-486.
[6] D.M.Young, Iterative solution of large linear systems, Academic Press, New York, 1971.
[7] J.F. Bonnans, C.C. Gonzaga, Convergence of interior point algorithms for the mon-otone linear complementarity problem, Mathematics of Operations Research 21(1996)1-25.
[8] J.S.Pang, Necessary and sufficient conditions for the convergence of iterative methods for the linear complementarity problem, J.Optim. Theory Appl. 42(1984)1-17.
[9] Jtidice, J.J., and Pires, EM., Basic-set algorithm for ageneralized linear compleme- ntarity problem, Journal of Optim&ation Theory and Applications 74/3 (1992) 391-411.
[10] K.R.James, Convergence of matrix iterations subject to diagonal dominances, SIAM J.Numer.Anal.12(1973) 478-484.
[11] M.Q. Jiang, J.L. Dong, On convergence of two-stage splitting methods for linear c- omentarity problems, J. Comput. Appl. Math.181 (2005)58-69.
[12] M,S. Gowda, Oil the extended linear complementarity problem, Mathematical Pro-gramming 72(1996)33-50.
[13] O.L.Mangasarian, Solution of symmetric linear complementarity problems by iterative methods, J.Optim. Thoery Appl.22(1997)465-485.
[14] R.S.Varga, Matrix Iterative Analysis, Prentice-Hall, Englewood Cliffs, NJ,1962.
[15] R.W. Cottle, J.S. Pang, R.E. Stone, The Linear Complementarity Problem, Acade- mic Press, San Diego, 1992.
[16] R.E. White, Multisplitting of a symmetric positive definite matrix,SIAM J. Matrix Anal. Appl. 11 (1990) 69-84.
[17] Y.Song, On the convergence of the generalized AOR method, Linear Algebra Appl, 256(1997) 199-218.
[18] Y. Song, Konvergenzkriterien fur das verallgemeinerte AOR-Verfahren, Z. Angew. Math. Mech. 72 (1992) 445–447.
[19] Z.Z.Bai, On the monotone convergence of matrix multisplitting relaxation methods for the linear complementarity problem, IMA J.Numer. Anal, 18(1998)509-518.
[20] Z.Z.Bai, D.J.Evans, Chaotic iterative methods for linear complementarity problem, J. Comput. Appl. Math.63(1997)127-138.
[21] Z.Z.Bai, D.J.Evans, Matrix multisplitting relaxation methods for linear compleme- ntarity problems, Int. J. Computer Math. 63(1997)309-326.
[22] Z.Z.Bai, On the convergence of the multisplitting methods for the linear complem- entarity problem, SIAM J. Matrix Anal. Appl. 21(1999)67-78.
[23] Z.Q.Luo, P.Teng, On the convergence of a matrix splitting algorithm for the symm- etric monotone linear complementarity problem, SIAM J.Control Optim.29(1991)1037- 1060.
[24] 宋永忠,线性方程组的迭代解法(讲义)。
[25] 吴彦强,曹德欣,韩超,关于线性互补问题的一个迭代算法,淮北煤炭师范学院学报,2005,26(1) 14-15。
[26] 陈培贤,AOR 方法的收敛性,计算数学 51(1983),66-71。
[2] B.H.Ahn. Solution of nonsymmetric linear complementarity problems by iterative methods, J.Optim. Theory Appl. 33(1981)175-185.
[3] D.Yuan, Convergence of parallel chaotic AOR method for H ?matrix, DCABES 2001 proceedings 24-28.
[4] D.Yuan, Y.Song, Modified AOR methods for linear complementarity problem, Appl. Math. Comput. 140(2003) 53-67.
[5] D.R.Wang, On the convergence of the parallel multisplitting AOR algorithm, Linear Algebra Appl. 154/156(1991) 473-486.
[6] D.M.Young, Iterative solution of large linear systems, Academic Press, New York, 1971.
[7] J.F. Bonnans, C.C. Gonzaga, Convergence of interior point algorithms for the mon-otone linear complementarity problem, Mathematics of Operations Research 21(1996)1-25.
[8] J.S.Pang, Necessary and sufficient conditions for the convergence of iterative methods for the linear complementarity problem, J.Optim. Theory Appl. 42(1984)1-17.
[9] Jtidice, J.J., and Pires, EM., Basic-set algorithm for ageneralized linear compleme- ntarity problem, Journal of Optim&ation Theory and Applications 74/3 (1992) 391-411.
[10] K.R.James, Convergence of matrix iterations subject to diagonal dominances, SIAM J.Numer.Anal.12(1973) 478-484.
[11] M.Q. Jiang, J.L. Dong, On convergence of two-stage splitting methods for linear c- omentarity problems, J. Comput. Appl. Math.181 (2005)58-69.
[12] M,S. Gowda, Oil the extended linear complementarity problem, Mathematical Pro-gramming 72(1996)33-50.
[13] O.L.Mangasarian, Solution of symmetric linear complementarity problems by iterative methods, J.Optim. Thoery Appl.22(1997)465-485.
[14] R.S.Varga, Matrix Iterative Analysis, Prentice-Hall, Englewood Cliffs, NJ,1962.
[15] R.W. Cottle, J.S. Pang, R.E. Stone, The Linear Complementarity Problem, Acade- mic Press, San Diego, 1992.
[16] R.E. White, Multisplitting of a symmetric positive definite matrix,SIAM J. Matrix Anal. Appl. 11 (1990) 69-84.
[17] Y.Song, On the convergence of the generalized AOR method, Linear Algebra Appl, 256(1997) 199-218.
[18] Y. Song, Konvergenzkriterien fur das verallgemeinerte AOR-Verfahren, Z. Angew. Math. Mech. 72 (1992) 445–447.
[19] Z.Z.Bai, On the monotone convergence of matrix multisplitting relaxation methods for the linear complementarity problem, IMA J.Numer. Anal, 18(1998)509-518.
[20] Z.Z.Bai, D.J.Evans, Chaotic iterative methods for linear complementarity problem, J. Comput. Appl. Math.63(1997)127-138.
[21] Z.Z.Bai, D.J.Evans, Matrix multisplitting relaxation methods for linear compleme- ntarity problems, Int. J. Computer Math. 63(1997)309-326.
[22] Z.Z.Bai, On the convergence of the multisplitting methods for the linear complem- entarity problem, SIAM J. Matrix Anal. Appl. 21(1999)67-78.
[23] Z.Q.Luo, P.Teng, On the convergence of a matrix splitting algorithm for the symm- etric monotone linear complementarity problem, SIAM J.Control Optim.29(1991)1037- 1060.
[24] 宋永忠,线性方程组的迭代解法(讲义)。
[25] 吴彦强,曹德欣,韩超,关于线性互补问题的一个迭代算法,淮北煤炭师范学院学报,2005,26(1) 14-15。
[26] 陈培贤,AOR 方法的收敛性,计算数学 51(1983),66-71。