第四章解线性方程组的直接法 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 初等变换
消元法 第一步：第1行x01+第i行，i=2,3,n an a12 n b ar d12 b 2) 21 a22 … 0 初等变换) 022 a …: an an2 0 a … a 运算量：(n-1)*(1+n) 6
¡ 第一步：第 行 第 行， 运算量： 6 1 11 i a a 1 i i 2,3,,n 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 (2) (2) (2) 2 (2) 2 (2) 2 (2) 22 11 12 1 1 0 0 n nn n n n a a b a a b a a a b 初等变换 n 1 *1 n
消元法 第二步：第2行×+第1行，i=3.4n (2) b an 412 a13 a11 a 0 … a bg2 0 a品 a 6g2 初等变换 0 0 a bs ... .; 0 a a 0 0 … a b3) 运算量：(n-2)*(1+n-1)=(n-2)n 7
¡ 第二步：第 行 第 行， 运算量： 7 (2) 2 (2) 22 i a a 2 i i 3,4,,n (3) (3) (3) 3 (3) 3 (3) 3 (3) 33 (2) 2 (2) 2 (2) 23 (2) 22 11 12 13 1 1 0 0 0 0 0 n nn n n n n a a b a a b a a a b a a a a b (2) (2) (2) 2 (2) 2 (2) 2 (2) 22 11 12 1 1 0 0 n nn n n n a a b a a b a a a b 初等变换 n - 2 *1 n -1 n - 2 n
消元法 ■类似的做下去，第k步： 第行×验+第：行，i=十1，，” (k) ■ 运算量： (n-k)*(1+n-k+1)=(n-k)(n-k+2) ◆ n-1步运算之后 411 12 a13 b 0 a 2 0 0 0 0 0 B() 总运算量： n-kn-k+2）+(m+1)）n/2=T+i-1=07) n-1 k=1 3 3 8
¡ 类似的做下去，第 步： 第 行 第 行， ¡ 运算量： ¡ 步运算之后 ¡ 总运算量： 8 k k ( ) ( )kikkkk aa i i k 1,,n (n－k) *(1＋n－k＋1) (n－k)(n－k＋2) n 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 nn nnnnnn a b a a b a a a b a a a a b 1 3 2 3 1 ( )( 2) 1 / 2 ( ) 3 3 nk n n n k n k n n n O n
消元法 ■ Gauss消元算法 Algorithm 9 Gaussian Elimination Algorithm Input: n,(a,(b) 1:for k 1 to n-1 do 2:for i=k+1 to n do 3: 之←-aik/akk 4: ak←0： 6 for j=k+1 to n do 6: ai)←aij-2akj; end for 8: b:←b,-zbk 9: end for 10:end for 11:for i=n to 1 step-1 do 12::←(：-∑=i+1ax)/a 13:end for Output: (c) 9
¡ Gauss消元算法 9
消元法 Gauss随元法的可行条件为：a≠0，即要求矩阵A的 所有顺序主子式均不为零 ■例：求解线性方程组 10x1+x2=1 x,=10°/(10°-1) x1+x2=2 x2=(10°-2)/(109-1) 高斯消元法： m1=a2/a1=10'8个 422=1-m21×1=0.0.01×109-109÷-109 b2=2-m21×1÷-109 11 )-109-109 →x2=1,x1=0 10
¡ Gauss消元法的可行条件为： ，即要求矩阵 的 所有顺序主子式均不为零 ¡ 例：求解线性方程组 高斯消元法： 10 ( ) 0 k kk a A 9 9 9 1 2 1 9 9 1 2 2 10 1 10 / (10 1) 2 (10 2) / (10 1) x x x x x x 9 21 21 11 m a / a 10 9 9 9 22 21 a 1 m 1 0.0...0110 10 10 8个 9 b2 2 m 21 1 10 9 9 9 10 1 1 0 10 10 2 1 x 1, x 0