中国科学技术大学：《计算方法》课程教学资源（课件讲稿）第四章 解线性方程组的直接法

第四章解线性方程组的直接法 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...0110 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