内点法中线性方程组三种解法的误差分析

摘要

在用内点法求解线性规划问题的过程中,我们经常遇到一个对称的秩-p修改的系统（I+UU<'T>）x=r.我们研究三种算法,即QR算法：先对U进行QR分解,再求解该系统;EQR算法：除了对U进行EQR分解,其它与QR算法相同;SMW算法：使用Sherman-Morrison-Woodbury公式求解该系统.我们的理论分析表明如果||U||较大,那么QR算法比EQR算法和流行的方法：SMW算法更有效.该系统和不可行内点法的数值试验也和理论分析一致.

目录

文摘

英文文摘

§1引言

§1.1线性规划和原-对偶内点法

§1.2求解(I+UUT)x=r的三种算法

§4QR，EQR和SMW算法的误差分析

§4.1QR算法的误差分析

§4.2 EQR算法的误差分析

§4.3 SMW算法的误差分析

§4.4三种算法的对比

§5数值试验

§6不可行内点法的应用

§7结论

参考文献

致谢

声明