- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
10 ⇒ 0
−9
9
1 − 10
9
1 9 − 10
小主元 可能 导致计算失 败
⇒
x 2 = 1,
x1 = 0
主元素Gauss消元法 Pivoting Strategies */ 消元法/* 二、 主元素 消元法
思 想
每次消元之前，在剩余元素中选择绝对值最大的 每次消元之前，在剩余元素中选择绝对值最大的 消元之前 绝对值最大 非零元素作为主元， 然后经过换行换到主元位置 换行换到 非零元素作为主元， 然后经过换行换到主元位置
(1) 11
a a
(1) 12 ( 2) 22
l32
ln2
L a x1 a L a x2 a . . . = O . . . . . . ( n) ( n) ln,n−1ann xn an,n+1
a
(1) 11
T
=
−1 1
a
(1) i1
i = 2, 3,L , n
−1 1 T 1 1
记
A
( 2)
=L A
(1)
L = I −l e
(1 a11) 0 I n−1 c1 T 1
A
( 2)
1 = c1 − (1) a11
r A1
A
解：增广矩阵
2 2 3 3 2 2 3 3 4 7 7 1 = 0 3 1 −5 ( A b) = −2 4 5 −7 0 6 8 −4
2 2 3 3 2 2 3 3 4 7 7 1 ( A b) = = 0 3 1 −5 −2 4 5 −7 0 6 8 −4 (1)
, i = k , k + 1,L , n
然后交换矩阵A( k )的第 k行和
再进行消元 消元过程 ik行，再进行消元过程
t = a ;a
= a ;a
(k ) ik , j
(k ) ik , j
= t , j = 1, 2,L, n + 1
算法: 列主元消去算法 算法: Gauss列主元消去算法 列主元 求方程组Ax=b 的解. 的解. 求方程组 输入:增广矩阵 输入:增广矩阵An 消元过程 消元过程 for k = 1,2,…,n-1 do Step 1 - Step 4 Step 1 寻找行号 ik , 使得 ai Step 2 如果 a 否则转Step 7 否则转 则交换第k行和 行和i ≠ 0，则交换第 行和 k行； ik ,k
三角（系数矩阵）方程组易于求解 三角（系数矩阵）
a11 0 a a22 21 M M an1 an 2
L 0 L 0 O M L ann
a11 a12 0 a 22 M M 0 0
L a1n L a2 n O M L ann
b
( 2) j
−1 1
− 1 (1 ) 同样记 1
b
( 2)
=L b
−1 (1) 1
=b −
(1) j
a
b
a
(1) 11
, j = 2, 3,L , n
记 (A
(1)
b ) = (a ), i = 1,L, n; j = 1,Ln, n + 1
(1) (1) ij
上述两个计算公式可以写成统一形式： 上述两个计算公式可以写成统一形式： 统一形式
2 2 4 2 −2 −1
2 2 7 3 4 2 6
3 3 7 1 5 6 8
x3 = 1, x2 = −2, x1 = 2
3 3 l 1 −5 −7 6 −4 l
l21 =
31
a21
(1) 31
a a a a
( 2) 32
(1) 11
=2
= =
要求用Gaussian Elimination计算。 计算。 要求用 计算
−9
解：l 21 = a 21 / a11 = 10
9
x1 ≈ x2 ≈ 1
8个 个 } 9 9 9 a22 = 1 − l21 × 1 = 0. 0 ... 01× 10 − 10 = −10
b2 = 2 − l 21 × 1 = − 1 0
k ,k
（ ） (n+1)=（A|b）.
输出: 或失败信息. 输出 近似解 xk=ak,n+1(k=1,2,…,n) 或失败信息
ax , , = m ai,k , i = k, k +1L n
k≤i≤n
算法: 列主元消去算法 算法: Gauss列主元消去算法（续） 列主元消去算法（ Step 3 for i=k+1,…,n 计算
Step k：第k步消元过程的计算公式 ： 步消元过程的计算公式 计算 l ik
k =1 2,L n−1 , ,
=
a
(k ) ik
a
(k ) kk
i = k + 1, k + 2,L , n
a
( k +1) ij
a i =1L k; j =1L n+1 , , , , (k ) (k ) = aij − lik akj i = k +1,L n; j = k +1,L n+1 , , i = k +1L n j =1L k , , ; , , 0
(1) 11
r A1
T 1
Step 1：如果 a ：
≠0
r ∗
T 1
r A1
T 1
初等变换
a 0
(1) 11
下面用初等矩阵来描述上述消元过程 下面用初等矩阵来描述上述消元过程 初等矩阵来描述上述消元
取
L = I +l e 1
其中 l i1
T 1 1
l1 = (0, l21,L ln1) ,
∑
∑
3
2
6
过程： 过程： ( n + 1) n
2
法的
n n 5n n + − ≈ 3 2 6 3
3
2
3
消元法的实现条件） 消元法的实现条件 T 510 基本 h . （基本Gauss消元法的实现条件） 全不为零 a ( i = 1, 2,L , k ( k ≤ n)) 全不为零的充要条件是
(i ) ii
列主元消去法 列主元消去法/* Column Pivoting Strategies */ 消去法 Step k：第k步首先选择主元 步首先选择主元 ： 步首先选择 寻求
k =1 2,L n−1 , ,
(k ) i ,k
ik满足 a
(k ) kj (k ) kj
(k ) ik , k
= max a
k ≤i≤n
顺序主子式都不等于 都不等于零 A 的顺序主子式都不等于零，即
∆i =
a11 a12 L a1i a21 a22 L a2i M M O M ai1 ai 2 L aii
≠ 0, i = 1, 2,L, k(≤ n)
证明： 归纳法证明( 证明： 归纳法证明(对k归纳) 归纳) 归纳
设直到k-1成立, 设直到 成立,只要证明 成立
a , a ,L , a
(k ) kk
( 2) 22
A A
(k ) 12 (k ) 22
其中 A
(1) (k ) 是对角元为 11 11
( k −1) 的 k −1, k −1 上三角矩阵
上三角的 矩阵 A( k ) 的k阶主子式 ∆ ( k )为上三角的 阶 k
∆
(k ) k
≠0⇔a
≠0
(1) 1n ( 2) 2n (1) 1,n+1 ( 2) 2,n+1
回代过程的计算公式： 回代过程的计算公式： 过程的计算公式
( n) n , n +1
等价方程组 等价方程组
A x=b
(n)
(n)
a (n) xn = an , n n (i) (i) (ai ,n +1 − ∑ ai , j x j ) j = i +1 xi = (i ) ai ,i
∆1 , ∆ 2 ,L , ∆ k −1 非零时，
即可。 ≠ 0 即可。
(k ) 11
∆ k非零的充要条件是 a
(k )
(k ) kk
在归纳假设下，基本Gauss消元法可进行到第 步 消元法可进行到第k-1步 在归纳假设下，基本 消元法可进行到第
A
A −1 −1 −1 −1 = Lk −1 Lk − 2 L L2 L1 A = 0
方程组 Ax 其中 (1) A
(1)
增广矩阵记为 ( 矩阵记为： = b的增广矩阵记为： A b) = ( A
(1) ij (1) (1) j
(1)
b )
(1)
= (a ) = (aij ) = A, b
(1) 11
= (b ) = (b j ) = b
(1) 11
a 令A = c1 a (1) A = c1
b
(n) i
=a
(n) i , n +1
i = 1, 2,L , n
得到的解向量 得到的解向量 存放在增广矩 阵的最后一列 阵的最后一列
i = n−1 n−2,L 2,1 , ,
for
法 的 消 元 过 程
回 代 过 程
k =1 2,L n−1 , , for i = k + 1, k + 2,L , n aik aik = ; akk for j = k +1L n+1 , , aij = aij − aik akj
