解线性不等式组的松弛直交变换法  

THE RELAXATION AND ORTHOGONAL TRANSFORMATION METHOD FOR SOLVING LINEAR INEQUALITIES

作　　者：盛松柏[1] 

机构地区：[1]南京大学数学系

出　　处：《高等学校计算数学学报》1990年第4期370-379,共10页Numerical Mathematics A Journal of Chinese Universities

基　　金：国家自然科学基金

摘　　要：求解线性不等式组已有许多方法。本文利用直交变换将原线性不等式组之解集变换成一个r维平面与正锥之交集,然后采用松弛直交投影法。在采用加速方法后,很快就能求得一个解。这不但可以解相容线性不等式组,还可以方便地判别线性不等式组不相容。数值试验表明,本文提出的方法相当有效。 本文在§2中介绍计算公式,收敛性分析放在§3。加速方法和初始点的选取分别在§4和§5中叙述。算法见§6,然后介绍数值试验情况。最后一节将介绍本文的方法可以改善坏条件问题,以及怎样用新方法寻找线性规划的初始可行点。This paper describes a new method for solving linear inequalities Ax<b.At first we introduce a relaxation vector y>0 into the original linear inequalities such that it can be transformed into a linear system Ax+y = b,and the QR decomposition of A is used.Then we need only solve an equivalent problemwhere Q is a rectangular matrix with orthogonal columns.The relaxation projection is an important tool for solving above equivalent form.After taking two kinds of accelerating technique we can easily get its solution.Our method can show that the linear inequalities are consitent or not.The efficiency of new method has been verified by some numerical tests.

关 键 词：线性不等式组 直交投影 松弛法 

分 类 号：O241.6[理学—计算数学]