第五章解线性方程组的直接法
2 第五章 解线性方程组的直接法
线性方程组的求解 ■在科学研究和工程应用中，求解线性方程组是非常基 础的问题 ■ 一般的线性方程组 a11X1+.+a1nXn=b1 ←→ Ax=b an1x1+.+annXn=bn ■ (Gram公式)当且仅当det(A)≠0时，方程组有唯一解 x=D ,i=1,2.n a11 .a-1b1 1i+1 D=det(A),D.=det ani-bn amtl 3
线性方程组的求解 在科学研究和工程应用中，求解线性方程组是非常基 础的问题 一般的线性方程组 （Gram公式）当且仅当 时，方程组有唯一解 3 11 1 1 1 1 1 n n n nn n n ax ax b ax ax b ++ = ⇔ ++ = Ax = b det( ) 0 A ≠ 11 1 1 1 1 1 1 111 , 1,2, , det( ), det i i iin i n ni n ni nn D xi n D a a ba a D D a a ba a − + − + = = = = A
线性方程组的求解 ■求解线性方程组的方法可分为 ·直接解法：采用消元（初等变换）、矩阵分解等技巧；从理论上来说， 直接法经过有限次四则运算（假设运算无舍入误差），可以得到线性方 程组的精确解 ●迭代解法：采用迭代、分块、预条件处理等技巧；将线性方程的解视为 某种极限过程的向量序列，近似解 ■直接法与迭代法的使用建议 ·一般来说，对同等规模的线性方程组，直接法对计算机的要求高于送代 法 ·对于中等规模的线性方程组，考虑到直接法的准确性与可靠性，建议使 用直接法求解 ·对于高阶稀疏线性方程组（非零元素较少），建议使用迭代法求解 。要充分考虑线性方程的特性，譬如对称性、正定性、稀疏性等，来选用 合适的算法
线性方程组的求解 求解线性方程组的方法可分为 直接解法：采用消元（初等变换）、矩阵分解等技巧；从理论上来说， 直接法经过有限次四则运算（假设运算无舍入误差） ，可以得到线性方 程组的精确解 迭代解法：采用迭代、分块、预条件处理等技巧；将线性方程的解视为 某种极限过程的向量序列，近似解 直接法与迭代法的使用建议 一般来说，对同等规模的线性方程组，直接法对计算机的要求高于迭代 法 对于中等规模的线性方程组，考虑到直接法的准确性与可靠性，建议使 用直接法求解 对于高阶稀疏线性方程组（非零元素较少），建议使用迭代法求解 要充分考虑线性方程的特性，譬如对称性、正定性、稀疏性等，来选用 合适的算法 4
线性方程组的求解 求解线性方程组的常用软件 ●Matlab ●LAPACK/EISPACK/LINPACK(一般的线性方程组求解) ●TACUS(大型稀疏线性方程组) ●SuperLU(大型稀疏线性方程组) ●Eigen(开源，C++,线性代数模板库) ●MKL(商业软件) ● 推荐参考书 G.H.Golub,C.F.V.Loan.Matrix Computations.4th Ed.The Jonhs Hopkins University Press.(有影印本与中译本，人民邮电出版社) ●L.N.Trefethen,D.B.Ill.Numerical Linear Algebra.SIAM Press.(有中译 本，人民邮电出版社) 5
线性方程组的求解 求解线性方程组的常用软件 Matlab LAPACK/EISPACK/LINPACK（一般的线性方程组求解） TACUS（大型稀疏线性方程组） SuperLU（大型稀疏线性方程组） Eigen（开源，C++，线性代数模板库） MKL（商业软件） . 推荐参考书 G. H. Golub, C. F. V. Loan. Matrix Computations. 4th Ed. The Jonhs Hopkins University Press. （有影印本与中译本，人民邮电出版社） L. N. Trefethen, D. B. III. Numerical Linear Algebra. SIAM Press. （有中译 本，人民邮电出版社） 5
消元法 ■基本思想：通过初等变换，将一般的线性方程组等价 变换为特殊形式的线性方程组，如上/下三角方程组、 对角方程组，进行求解 对角形线性方程组 aux =b a22X2 =b2 =: ,i=1,2n a amxn=b 附问复杂度：O(n) 6
消元法 基本思想：通过初等变换，将一般的线性方程组等价 变换为特殊形式的线性方程组，如上/下三角方程组、 对角方程组，进行求解 对角形线性方程组 时间复杂度： 6 11 1 1 22 2 2 , 1,2, , i i ii nn n n a x b a x b b xi n a ax b = = ⇒= = = = O n( )