计算方法 第二章解线性方程组的直接法 §23 Gauss列主元消去法
第二章 解线性方程组的直接法 §2.3 Gauss列主元消去法
§23 Gauss列主元消去法 、 Gauss列主元消去法的引入 例1用Gas消去法解线性方程组(用3位十进制浮 点数计算) 0.0001x1+x2=1 x1+x=2 解:本方程组的精度较高的解为 x*=(1.000100010.998999 用 Gauss消去法求解(用3位十进制浮点数计算)
§2.3 Gauss列主元消去法 例1. 用Gauss消去法解线性方程组(用3位十进制浮 点数计算） î í ì + = + = 2 0.0001 1 1 2 1 2 x x x x 解: 本方程组的精度较高的解为 T x* = (1.00010001,0.99989999) 用Gauss消去法求解(用3位十进制浮点数计算) 一、Gauss列主元消去法的引入
主元 0.00010011 (A,b) 1 9999 0.000100 m21=10000 0 100×104-100×104 回代后得到 x1=0.00,x2=1.00 与精确解相比,该结果相当糟糕 究其原因,在求行乘数时用了很小的数0.0001作除数
A = (A,b) ÷ ÷ ø ö ç ç è æ = 2 1 1 1 0.000100 1 ¾m¾21=¾10000 ¾® ÷ ÷ ø ö ç ç è æ - ´ - ´ 4 4 1.00 10 1 0 1.00 10 0.000100 1 9999 0.00 , 1.00 回代后得到 x1 = x2 = 与精确解相比,该结果相当糟糕 究其原因,在求行乘数时用了很小的数0.0001作除数 主元
如果在求解时将1,2行交换,即 2 A=(A,b)→ 0.00010011 11 0.9999 121=0.0001 0100100 回代后得到 x1=1.00,x2=1.00 这是一个相当不错的结果
A = (A,b) ÷ ÷ ø ö ç ç è æ ® 1 2 0.000100 1 1 1 ¾m¾21 =¾0.0001 ¾® ÷ ÷ ø ö ç ç è æ 1.00 2 0 1.00 1 1 如果在求解时将1,2行交换,即 0.9999 1.00 , 1.00 x1 = x2 = 回代后得到 这是一个相当不错的结果
例2.解线性方程组用8位十进制尾数的浮点数计算) 10 3 13.7124623x2=2 210725643x 解:这个方程组和例1一样若用Gaus消去法计算会有 小数作除数的现象,若采用换行的技巧,则可避免 10 2 31 108很小,绝对值最大 A=(Ab)=-13.71246232的列元素为a1=2 210725.6433|因此13行交换
A = (A,b) 例2. 解线性方程组(用8位十进制尾数的浮点数计算) ÷ ÷ ÷ ø ö ç ç ç è æ = ÷ ÷ ÷ ø ö ç ç ç è æ ÷ ÷ ÷ ø ö ç ç ç è æ - - - 3 2 1 2 1.072 5.643 1 3.712 4.623 10 2 3 3 2 1 8 x x x 解: 这个方程组和例1一样,若用Gauss消去法计算会有 小数作除数的现象,若采用换行的技巧,则可避免 ÷ ÷ ÷ ø ö ç ç ç è æ - = - - 3 2 1 2 1.072 5.643 1 3.712 4.623 10 2 3 8 因此 行交换 的列元素为 很小 绝对值最大 1,3 2, 10 , 13 8 = - - a
21.07256433 (4①),b(D n分13 13.7124.6232 绝对值最犬 10 2 3 不需换行 m1=0.5 21072 5.643 3 m1=-0.5×10-8 00.3176×100.18015×100.5 00.2×10 0.3×100.1×10 (2 m12=0.62972292 (A,b 21.072 5.643 00.3176×100.18015×10 0.5 0 0 0.18655541×100.68513854 (3)(3
¾r¾1Û¾r3® ÷ ÷ ÷ ø ö ç ç ç è æ - - - 1 2 3 10 2 3 1 3.712 4.623 2 1.072 5.643 8 ¾¾¾¾¾® - =- ´ = 8 31 21 0.5 10 0.5 m m ÷ ÷ ÷ ø ö ç ç ç è æ ´ ´ ´ ´ ´ - 0.1 10 0.5 3 0 0.2 10 0.3 10 0 0.3176 10 0.18015 10 2 1.072 5.643 绝对值最大 不需换行 ¾m¾32 =¾0.629¾722¾92® ÷ ÷ ÷ ø ö ç ç ç è æ ´ ´ ´ - 0.685 138 54 0.5 3 0 0 0.186 555 41 10 0 0.3176 10 0.18015 10 2 1.072 5.643 ( , ) (1) (1) = A b ( , ) ( 2) (2) = A b ( , ) (3) (3) = A b
经过回代后可得 b (3) 0.68513854 二 (3) =0.36725739 0.18655541×10 33 x305-018015×10 x =-0.05088607 0.3176×10 22 2 X =-0.49105820 事实上,方程组的准确解为 x*=(-0.4910582270.0508860750.367257384)
(3) (3) 3 3 33 a b x = = 经过回代后可得 (1) 11 3 (1) 2 13 (1) 12 (1) 1 1 a b a x a x x - - = 0.685 138 54 0.186 555 41´10 = 0.367 257 39 (2) 22 3 (2) 23 (2) 2 2 a b a x x - = 0.3176 10 0.5 0.18015 10 3 ´ - ´ ´ = x = -0.05088607 = -0.49105820 事实上,方程组的准确解为 T x* = (-0.491058227,-0.050886075,0.367257384)
例2所用的方法是在 Gauss消去法的基础上利用换行 避免小主元作除数,该方法称为Gaus列主元消去法 、 Gauss消元过程与系数矩阵的分解 1. Gauss消去法消元过程的矩阵描述 12 b (4,b)=1 22 2n 行变换相 n 2 nn 当于左乘 初等矩阵 由于 777 =23…,n
( , ) (1) (1) A b 例2所用的方法是在Gauss消去法的基础上,利用换行 避免小主元作除数,该方法称为Gauss列主元消去法 二、Gauss消元过程与系数矩阵的分解 1.Gauss消去法消元过程的矩阵描述 ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ = (1) (1) (1) 2 (1) 1 (1) 2 (1) 2 (1) 22 (1) 21 (1) 1 (1) 1 (1) 12 (1) 11 n n nn n n n a a a b a a a b a a a b L M M M M L L i n a a m i i 2,3, , (1) 11 (1) 1 1 = = L 行变换相 当于左乘 初等矩阵 由于
1 令 1 则1(40.b)=(42,b2) 显然若令 1 k k+1,k nk
÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ - - = 1 1 1 1 21 1 mn m L M O 令 则 ( , ) (1) (1) L1 × A b ( , ) ( 2) (2) = A b ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç ç è æ - - = + 1 1 1 1 , 1 , n k k k k m m L M O O 显然若令
则有1(41.b)=(4,4) k=1,2,3,…,n-1 因此 L2·L1(AD,b①)=(4(0,b0) 从而Ln1…:L2·L1A=A0 故A=1L2…Ln140)=LU L=L1L2…Ln1为单位下三角矩阵 U=A)为上三角矩阵
则有 ( , ) (k ) (k ) Lk × A b ( , ) ( +1) ( +1) = k k A b k = 1,2,3,L,n - 1 ( , ) (1) (1) × L × L2 × L1 × A b Ln-1 ( , ) (n) (n) 因此 = A b 从而 Ln-1 × L × L2 × L1 × A 1 ( ) 1 1 2 1 1 n L L Ln A - - - - 故 A = L U = A (n)为上三角矩阵 L = L - 1 1 L - 2 1LL - n 1 -1为单位下三角矩阵 = LU (n) = A