第四章解线性方程组的直接法 1
1 第四章 解线性方程组的直接法
直接解法 1958》 采用消元（初等变换）、矩阵分解等技巧 ■从理论上来说，直接法经过有限次四则运算（假设运 算无舍入误差)，可以得到线性方程组的精确解 ■但因数值计算有舍入误差，得到的仍然是近似解
¡ 采用消元（初等变换）、矩阵分解等技巧 ¡ 从理论上来说，直接法经过有限次四则运算（假设运 算无舍入误差） ，可以得到线性方程组的精确解 ¡ 但因数值计算有舍入误差，得到的仍然是近似解 2
消元法 ■基本思想：通过初等变换，将一般的线性方程组等价 变换为特殊形式的线性方程组，如上/下三角方程组、 对角方程组，进行求解 ■对角形线性方程组 a11X1 =b, a22X2 =b2 1 = →X= b,i=12,n amxn=bn 时间复杂度：O(n) 3
¡ 基本思想：通过初等变换，将一般的线性方程组等价 变换为特殊形式的线性方程组，如上/下三角方程组、 对角方程组，进行求解 ¡ 对角形线性方程组 时间复杂度： 3 11 1 1 22 2 2 , 1,2, , i i ii nn n n a x b a x b b x i n a a x b O(n)
消元法 ■上三角方程组 411X1+42X2+…+41nXn=b h22X2+…+42nXn=b2 6-24, j=i+1 -,i=n,n-1,.,1 = X= u umnxn =br 时间复杂度：O(n2) 下三角方程组 hx =b1 1-1 121x1+122x2 =b2 -1 b i=1 = →X= -,i=1,2,,n x+n2x2++lmx=bn 时间复杂度：O(n) 4
¡ 上三角方程组 时间复杂度： ¡ 下三角方程组 时间复杂度： 4 11 1 12 2 1 1 22 2 2 2 1 , , 1, ,1 n n n i ij j n n j i i ii nn n n u x u x u x b b u x u x u x b x i n n u u x b 2 O(n ) 1 11 1 1 21 1 22 2 2 1 1 1 2 2 , 1,2, , i i ij j j i ii n n nn n n l x b b l x l x l x b x i n l l x l x l x b 2 O(n )
消元法 ■初等变换： ●交换矩阵的两行 ●某一行乘以一个非零数 ●某一个乘以一个非零数，加到另一行 ■ Guss随元法：先将矩阵化为上/下三角矩阵，再回代 求解 a2 3 b a a12 41n 0 a a b d21 22 a2n b2 初等变换 0 0 an an2 … bn 0 0 0 5
¡ 初等变换： l 交换矩阵的两行 l 某一行乘以一个非零数 l 某一个乘以一个非零数，加到另一行 ¡ Gauss消元法：先将矩阵化为上/下三角矩阵，再回代 求解 5 n n nn n n n a a a b a a a b a a a b 1 2 21 22 2 2 11 12 1 1 ( ) ( ) (3) 3 (3) 3 (3) 33 (2) 2 (2) 2 (2) 23 (2) 22 11 12 13 1 1 0 0 0 0 0 0 n n n nn n n n a b a a b a a a b a a a a b 初等变换