第二章 解线性代数方程组的直接法
- 格式：doc
- 大小：957.50 KB
- 文档页数：25
下载文档原格式
合集下载
第二章 线性方程组的直接解法
a i(kk ) l ik = ( k ) a kk a ( k +1) = a ( k ) − l a ( k ) ij ik kj ij ( k +1) = 0 a ik b ( k +1) = b ( k ) − l b ( k ) i ik k i
( i = k + 1, ⋯ , n ) ( i , j = k + 1, ⋯ , n ) ( i = k + 1, ⋯ , n ) ( i = k + 1, ⋯ , n )
定理2 定理2.1 高斯消元法消元过程能进行到底的充要条件是系 n- 阶顺序主子式不为零； Ax=b 能用高斯消元 数阵A的 数阵 A 的 1 到 n-1 阶顺序主子式不为零 ； Ax=b能用高斯消元 法解的充要条件是A的各阶顺序主子式不为零 的各阶顺序主子式不为零. 法解的充要条件是 的各阶顺序主子式不为零.
(i=2,3,⋯,k) )
(i ) 显然, Di ≠ 0 ↔ a ii ≠ 0 , 可知,消元过程能进行到底的充 显然, 可知, 要条件是D 要条件是 i≠0 ,(i=1,2,⋯,n-1),若要回代过程也能完成,还应 , 若要回代过程也能完成, 加上D ｜ ｜ ,综合上述有: 加上 n=｜A｜≠0,综合上述有:
⋯
( a kkk )
⋮
( a nkk )
⋯ a 1(1 ) b1(1 ) n (2) (2) ⋯ a 2 n b2 ⋯ ⋯ ⋯ (k ) (k ) ⋯ a kn b k ⋯ ⋮ ⋮ (k ) (k ) ⋯ a nn b n
7
结束
本次消元的目的是对框内部分作类似第一次消元的处 ( (k 消掉第k+1到第 个方程中的 k项,即把 akk ) ,k到 ank ) 化 到第n个方程中的 理,消掉第 到第 个方程中的x +1 为零.计算公式如下: 为零.计算公式如下:
线性方程组的解法例题线性方程组的解法
线性方程组的解法例题线性方程组的解法第二章线性方程组的解法n阶线性方程组的一般形式为:a11x1,a12x2, ,a1nxn b1 ax,ax, ,ax b 2112222nn2(2.0.1)an1x1,an2x2, ,annxn bnAx b用矩阵表示为: 其中A称为系数矩阵，x称为解向量，b称为常数向量(简称方程组自由项)，它们分别为:x1 b1 a11a12a1nx b aa2122a2n x 2 b 21，， Axn bn an1an2ann如果矩阵A非奇异，即A的行列式值det(A) 0，则根据克莱姆(Cramer)规则，方程组有唯一解:Di,i 1,2, ,n xi D其中D det(A)，Di表示D中等i列换b后所得的行列式值。
但克莱姆规则不适用于求解线性代数方程组，因为计算工作量大得难以容忍。
实际用于求解线性代数方程组的计算方法主要有两种:一是消去法，它属于直接解法;二是迭代解法。
消去法的优点是可以预先估计计算工作量，并且根据消去法的基本原理，可以得到矩阵运算(如矩阵求逆等)的求解方法。
但是，由于实际计算过程总存在有误差，由消去法得到的结果并不是绝对精确的，存在数值计算的稳定性问题。
迭代解法的优点是简单，便于编制计算机程序。
在迭代解法中，必须考虑迭收敛速度快慢的问题。
?2.1 线性方程组的直接计算求解线性代数方程组的直接解法主要是消去法(或称消元2法)。
消去法的基本思想是通过初等行变换:将一个方程乘以某个常数，以及将两个方程相加或相减，减少方程中的未知数数目，最终使每个方程中含一个未知数，从而得到所需要的解。
2.1.1 三角形方程组的计算对下三角形方程组:a11x1 b1ax,ax b 2112222(2.1.1)an1x1,an2x2, ,annxn bn可以通过前代的方法求解:先从第1个方程求出x1，代入第2个方程求出x2，依次类推，可以逐次前代求出所有xi(i 1,2, ,n)，计算公式如下:b1x1 a11i～1bi～ aij xj(2.1.2)j 13xi , i 2, 3, , n aii对上三角形方程组:a11x1,a12x2, ,a1nxn b1ax, ,ax b 2222nn2annxn bn(2.1.3)可以通过回代的方法求解:先从第n个方程求出xn，代入第n～1个方程求出xn～1，依次类推，可以逐次回代求出所有xi(i n,n～1, ,1)，计算公式如下:bnxn annnbi～ aij xj(2.1.4)j i,1xi , i n～1, n～2, , 1 aii2n 前代法和回代法的计算量都是次四则运算。
数值计算方法总结
误差分类
模型误差 数据误差 截断误差 计算误差 在建立数学模型时，忽略次要因素而造成的 由于问题中的值通过观察得到的，从而产生误差 通过近似替代，简化为较易求解的问题 由于计算机中数的位数限制而造成的
第1章 数值计算方法的一般概念
1.2 误差
~ x 设 为真值, x 为真值的近似值
绝对误差 绝对误差：是指近似值与真正值之差或差的绝对 值，即 x x x,或 x 绝对误差界：用一个满足 绝对误差的大小，并记为 的数 ,来表示
分为n -1步, 第k步变换n - k 行 : 求倍数, 再从n 1- k 个元素中减去第k 行 对应列的倍数,因此所需乘除次数: n3 n 2 5n N1 (n k )(n 1 k 1) 3 2 6 k 1
n
2.回代运算量
求xn需做1次除法, 求xn-1需做1次乘法和1次除法,..., 求x1需n -1次 乘法和1次除法,因此所需乘除次数: n(n 1) N 2 1 2 ... n n3 2 2 n 因此,N N1 N 2 n 3 3
j i, i 1,..., n j i 1, i 2,..., n 1
第2章 解线性代数方程的直接法
2.2 三角分解法 2.2.3 追赶法
b1 a 1 A A b
作克洛特分解
c1 b2 a2
c2 b3 c3 an 1 bn 1 cn 1 an
选主元方法分为行主元法与全主元法
第2章 解线性代数方程的直接法
2.2 三角分解法 2.2.1 杜里特尔分解法 高斯消去法的消去过程,实质上是把系数矩阵A分解为单位下三角矩 阵L与上三角矩阵R的乘积,并且求解方程组Ly=b的过程,回代过程是求解 上三角形方程组Rx=y
模型误差 数据误差 截断误差 计算误差 在建立数学模型时，忽略次要因素而造成的 由于问题中的值通过观察得到的，从而产生误差 通过近似替代，简化为较易求解的问题 由于计算机中数的位数限制而造成的
第1章 数值计算方法的一般概念
1.2 误差
~ x 设 为真值, x 为真值的近似值
绝对误差 绝对误差：是指近似值与真正值之差或差的绝对 值，即 x x x,或 x 绝对误差界：用一个满足 绝对误差的大小，并记为 的数 ,来表示
分为n -1步, 第k步变换n - k 行 : 求倍数, 再从n 1- k 个元素中减去第k 行 对应列的倍数,因此所需乘除次数: n3 n 2 5n N1 (n k )(n 1 k 1) 3 2 6 k 1
n
2.回代运算量
求xn需做1次除法, 求xn-1需做1次乘法和1次除法,..., 求x1需n -1次 乘法和1次除法,因此所需乘除次数: n(n 1) N 2 1 2 ... n n3 2 2 n 因此,N N1 N 2 n 3 3
j i, i 1,..., n j i 1, i 2,..., n 1
第2章 解线性代数方程的直接法
2.2 三角分解法 2.2.3 追赶法
b1 a 1 A A b
作克洛特分解
c1 b2 a2
c2 b3 c3 an 1 bn 1 cn 1 an
选主元方法分为行主元法与全主元法
第2章 解线性代数方程的直接法
2.2 三角分解法 2.2.1 杜里特尔分解法 高斯消去法的消去过程,实质上是把系数矩阵A分解为单位下三角矩 阵L与上三角矩阵R的乘积,并且求解方程组Ly=b的过程,回代过程是求解 上三角形方程组Rx=y
线性代数方程组的直接解法赖志柱
第二章线性代数方程组的直接解法教学目标：1.了解线性代数方程组的结构、基本理论以及相关解法的发展历程；2.掌握高斯消去法的原理和计算步骤，理解顺序消去法能够实现的条件，并在此基础上理解矩阵的三角分解（即LU分解），能应用高斯消去法熟练计算简单的线性代数方程组；3.在理解高斯消去法的缺点的基础上，掌握有换行步骤的高斯消去法，从而理解和掌握选主元素的高斯消去法，尤其是列主元素消去法的理论和计算步骤，并能灵活的应用于实际中。
教学重点：1. 高斯消去法的原理和计算步骤；2. 顺序消去法能够实现的条件；3. 矩阵的三角分解（即LU分解）；4. 列主元素消去法的理论和计算步骤。
教学难点：1. 高斯消去法的原理和计算步骤；2. 矩阵的三角分解（即LU分解）；3. 列主元素消去法的理论和计算步骤。
教学方法：教具：引言在自然科学和工程技术中，许多问题的解决常常归结为线性方程组的求解，有的问题的数学模型中虽不直接表现为线性方程组，但它的数值解法中将问题“离散化”或“线性化”为线性方程组。
例如，电学中的网络问题、船体数学放样中建立三次样条函数问题、最小二乘法用于求解实验数据的曲线拟合问题、求解非线性方程组问题、用差分法或有限元法求解常微分方程边值问题及偏微分方程的定解问题，都要导致求解一个或若干个线性方程组的问题。
目前，计算机上解线性方程组的数值方法尽管很多，但归纳起来，大致可以分为两大类：一类是直接法（也称精确解法）；另一类是迭代法。
例如线性代数中的Cramer法则就是一种直接法，但其对高阶方程组计算量太大，不是一种实用的算法。
实用的直接法中具有代表性的算法是高斯（Gauss）消元法，其它算法都是它的变形和应用。
在数值计算历史上，直接法和迭代法交替生辉。
一种解法的兴旺与计算机的硬件环境和问题规模是密切相关的。
一般说来，对同等规模的线性方程组，直接法对计算机的要求高于迭代法。
对于中、低阶（200n ）以及高阶带形的线性方程组，由于直接法的准确性和可靠性高，一般都用直接法求解。
上海交通大学计算方法课件(宋宝瑞)CH.2(1)
1第二章 解线性方程组的直接法解线性方程组11112211211222221122n n n n n n nn n na x a x a xb a x a x a x b a x a x a x b+++=⎧⎪+++=⎪⎪⎨⎪+++=⎪⎪⎩或写成矩阵式Ax b =其中()1212,(,,,),(,,,)T Tij n n n nA a x x x x b b b b ⨯=== Gauss 消去法（矩阵行变换法）第k 次消元公式()()(1)()()(1)()()/(1,,)(,1,,)(1,,)k k ik ik kk k k k ij ij ik kj k k k i i ik k m a a i k n a a m a i j k n b b m b i k n ++==+=-=+=-=+计算中，中间结果不必保留，进行一次变换后原来存放(1)k A -的单元存放()k A，(1)k b-的单元存放()k b。
因此，我们得到Gauss消去法的算法：2循环：1,2,,k = n-1何时可行？即第k 步 Gauss 消去法可实行，易见充要条件是()0k kk a ≠若A 的各阶顺序主子式 *det()0ij k k a ≠ 1,,1k n =- ，则有：()**()()()1122()det()det() ||k ij k k ij k kk k k kk k kk a a a a a a =⇔≠ 消元过程可进行到 1k n =-。
因此，可以用Gauss 消去法解线性方程组的充要条件是系数矩阵的各阶顺序主子式不为0。
最后得到()()() n n n A x b A =是上三角阵()()k k A x b =与Ax b =同解2,,k n =解()()n n A x b=只需递推（回代过程）2211112()/, ,,1(0 = 1)nk k kjj kk j k k k i i i k i k x b ax a k n k k a a =+===-=>=∑∑∏ 当时，规定：3计算量 第k 步消元计算ik m 用(n-k )次除法，算诸()k ij a 用2(-)n k 乘法和2(-) n k 次加减法， 对1,,1k n =- 相加，可得消元过程共需2(1)/3n n -⨯÷次 (1)(21)/6n n n -- 右端 (1)()n bb →(1)/2 n n -⨯÷ (1)/2 +n n -－(1)/2 (1)/2 +-n n n n -⨯÷-回代3233 /3/3 /3(1)(25)/6 /3n n n n n n n n +-≈-+≈总数：乘除法加减法矩阵的三角分解（用矩阵乘法分解的观点看Gauss 消去法）对A 作行变换相当于左乘初等矩阵，例如(1)(2)AA →(2)1A L A =其中421131110-1 -01-001n m L m m ⎛⎫ ⎪ ⎪⎪ ⎪ ⎪ ⎪⎝⎭＝ 类似的讨论易知：()()1111 ,,n n n n A L L A b L Lb --==1,,100001 00000001 k k k n k L m m k +⎛⎫ ⎪ ⎪ ⎪⎪- ⎪ ⎪ ⎪ ⎪-⎝⎭＝第列令()1111111121313212,1= := 110 =11n n n n n n n U A A L L U L L L m m m m m m -------=⎛⎫⎪ ⎪ ⎪⎪⎪ ⎪ ⎪ ⎪⎝⎭上三角阵则单位下三角阵5定理：**(),det()0 1,,1ij n n ij k k A a a k n =≠=- ，则A 可表示为A=LU L ：单位下三角阵，U 上三角阵，且分解唯一。
21高斯消元法
令 c aik / akk （“适当倍数”）
对j= k+1~n+1（列）令 aij aij cakj
回代过程是解同解的上三角形方程组
a11x1 a12x2
a22 x2
a1,n1 xn1 a1n xn
a2,n1xn1 a2 ,n xn
a x n1,n1 n1 an1,n xn ann xn
素，……，第n-1步消去an-1，n-1下方元素。即第k 步将第k行的适当倍数加于其后各行，或可说是 从k+1~n行减去第k行的适当倍数，使它们的第k 列元素变为零，而其余列元素减去第k行对应列 元素的倍数。
因此，如把增广矩阵 A 变换前后都在计算
机上用同一数组A存储， 则消去过程可写为：
对k=1~n-1（步）做 对i= k+1~n（行）做
求出x2代回第一个方程时，因 10-5x1+2x2=1， 10-5x1’+2x2’=1 两式相减得10-5(x1－ x1’)+2(x2－ x2’)=0，可见 | x1－ x1’ |=200 000| x2－ x2’|
~x 表明 x1的误差被放大200 000倍， x1’自然失真。2
列主元消去法
为了避免出现小主元，在每次消元前进行选 主元。即每次消元前先选取所要消元的列中绝对 值最大的元素作为主元，然后再消元。
通常情况下稳定性彼此相差不大，所以一般 情况都只用列主元消去法。
复习题
1、何谓高斯消去法？它与一般消去法有 何不同？怎样计算行列式？
2、计算机上为什么不用克莱姆法与约当 消去法？
3、何谓主元消去法？有何优点？
具体为：
中选~x在主2第元k，步即的在第其k列中的找元出素绝a对kk值, a最k大~x1,1的k ,元素, aankpk，
对j= k+1~n+1（列）令 aij aij cakj
回代过程是解同解的上三角形方程组
a11x1 a12x2
a22 x2
a1,n1 xn1 a1n xn
a2,n1xn1 a2 ,n xn
a x n1,n1 n1 an1,n xn ann xn
素，……，第n-1步消去an-1，n-1下方元素。即第k 步将第k行的适当倍数加于其后各行，或可说是 从k+1~n行减去第k行的适当倍数，使它们的第k 列元素变为零，而其余列元素减去第k行对应列 元素的倍数。
因此，如把增广矩阵 A 变换前后都在计算
机上用同一数组A存储， 则消去过程可写为：
对k=1~n-1（步）做 对i= k+1~n（行）做
求出x2代回第一个方程时，因 10-5x1+2x2=1， 10-5x1’+2x2’=1 两式相减得10-5(x1－ x1’)+2(x2－ x2’)=0，可见 | x1－ x1’ |=200 000| x2－ x2’|
~x 表明 x1的误差被放大200 000倍， x1’自然失真。2
列主元消去法
为了避免出现小主元，在每次消元前进行选 主元。即每次消元前先选取所要消元的列中绝对 值最大的元素作为主元，然后再消元。
通常情况下稳定性彼此相差不大，所以一般 情况都只用列主元消去法。
复习题
1、何谓高斯消去法？它与一般消去法有 何不同？怎样计算行列式？
2、计算机上为什么不用克莱姆法与约当 消去法？
3、何谓主元消去法？有何优点？
具体为：
中选~x在主2第元k，步即的在第其k列中的找元出素绝a对kk值, a最k大~x1,1的k ,元素, aankpk，
第二章 解线性代数方程组的直接法(DOC)
第二章 解线性方程组的直接法本章研究的对象是n 阶线性方程组⎪⎪⎩⎪⎪⎨⎧=+++=+++=+++nn nn n n n n n n b x a x a x a b x a x a x a b x a x a x a .........22112222212111212111 （2.1）其矩阵形式为b AX = （2.1）′其中，)(ij a A =是方程组的系数矩阵，⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=n x x x X ...21,⎪⎪⎪⎪⎪⎭⎫⎝⎛=n b b b b ...21分别为方程组的未知向量和常数向量。
所谓直接法，就是在不计舍入误差时，经过有限步运算能求得方程组精确解的方法。
下面介绍几种较实用的直接法。
2.1 Gauss 消去法 2.1.1 Gauss 顺序消去法高斯（Gauss ）消去法实质是消元法,只是步骤规范,便于编程。
它的基本做法是把方程组(2.1)转化成一个等价的三角方程组⎪⎪⎩⎪⎪⎨⎧==++=+++n n nn n n n n g x b g x b x b g x b x b x b 2222211212111 (2.2) 这个过程称为消元。
然后,逐个求出11,,,x x x n n -,这个过程称为回代。
(一) 高斯消去法的计算过程为了符号统一,把方程组(2.1)改写成下面形式⎪⎪⎩⎪⎪⎨⎧=+++=+++=+++)1()1(2)1(1)1()1()1(2)1(1)1()1()1(2)1(1)1( (212)22221111211n nn n n n n b x a x a x a b x a x a x a b x a x a x a n n n(2.3)用矩阵表示为)1()1(b X A = (2.3)′其中⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡=)1()1(2)1(1)1(2)1(22)1(21)1(1)1(12)1(11)1(nn n n nn a a a a aa a aa A, ⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=)1()1()1()1(...21n b b b b 若0)1(11≠a ,用第二个方程减去第一个方程的)1(11)1(21/a a 倍,第三个方程减去第一个方程的)1(11)1(31/a a 倍,等等。
第02讲：线性代数方程组求解(直接方法)
1 2 b (1) ) 3 4 1 1 2 3 1 1 1 2 1 4 1 5 1 7 1 10
A(1) ( A(1)
§2.1 Gauss evaluation method
首先进行消去过程，对 A (1) 分别用-2，-3，-4乘第一行 后加到第2、3、4行有
例：试用高斯顺序消去法求解线性代数方程组：
x1 x2 x3 x4 4 2x x x x 5 1 2 3 4 3 x1 2 x2 x3 x4 7 4 x1 3 x2 2 x3 x4 10
解：线性方程组的增广矩阵为：
(2) a22 0时，用矩阵 第二步：等价于：若 左乘 A (1) 即有
(1) a 0 1 11 0 0 1 (1) l0 L A 1 L 0 2 32 0 0 l n2
(1) a 012 (2) a 022
1
(2) a 0n 2
基本思想 对线性代数方程组所对应的增广矩阵进行一系 列 “把某一行的常数倍加到另一行上去” 这样的 初等行变换,最后得到上三角矩阵所对应的线性代数 方程组,只要回代就可得到原方程组的解。
A
a
(1)
(A
(1)
b ) ( A b)
(1)
(1) ij
aij (i, j 1,2,3, , n)
, n)
§2.1 Gauss evaluation method
(1) a11 0 ( A(3) | b(3) ) 0 0 (1) a12 (2) a22 0 (1) a13 (2) a23 (3) a33 (1) a1(1) b n 1 (2) (2) a2 n b2 (3) (3) a3 b n 3 (3) (3) ann bn
A(1) ( A(1)
§2.1 Gauss evaluation method
首先进行消去过程，对 A (1) 分别用-2，-3，-4乘第一行 后加到第2、3、4行有
例：试用高斯顺序消去法求解线性代数方程组：
x1 x2 x3 x4 4 2x x x x 5 1 2 3 4 3 x1 2 x2 x3 x4 7 4 x1 3 x2 2 x3 x4 10
解：线性方程组的增广矩阵为：
(2) a22 0时，用矩阵 第二步：等价于：若 左乘 A (1) 即有
(1) a 0 1 11 0 0 1 (1) l0 L A 1 L 0 2 32 0 0 l n2
(1) a 012 (2) a 022
1
(2) a 0n 2
基本思想 对线性代数方程组所对应的增广矩阵进行一系 列 “把某一行的常数倍加到另一行上去” 这样的 初等行变换,最后得到上三角矩阵所对应的线性代数 方程组,只要回代就可得到原方程组的解。
A
a
(1)
(A
(1)
b ) ( A b)
(1)
(1) ij
aij (i, j 1,2,3, , n)
, n)
§2.1 Gauss evaluation method
(1) a11 0 ( A(3) | b(3) ) 0 0 (1) a12 (2) a22 0 (1) a13 (2) a23 (3) a33 (1) a1(1) b n 1 (2) (2) a2 n b2 (3) (3) a3 b n 3 (3) (3) ann bn
第二章线性代数方程组的直接解法
2 ~ A A b 4 1 1 2 2 3 5 0
1 2 r ( 2 ) r 4 0 1 r ( ) r 2 7 0
2 1 3 1
i 行）
1 2 13 2
1 3 4 1 5 3 2 2
(1 a11) (1 a12) (2 a 22 )
a11
( a n2 ) 2
( a11) x1 b1(1) n ( ( 2) x 2 b2 2 ) a2n ( 2) ( 2) a nn x n bn
一般线性方程组使用高斯消去法求解时，
(k 在消元过程中可能会出现 akk ) 0 的情况，这
(k 时消去法将无法进行；即使 akk ) 0 ，但它的
绝对值很小时，用其作除数，会导致其他元素
第3章 解线性方程组的直接法 一般b≠0, 当系数矩阵A非奇异(即detA≠0) 常见的线性方程组是方程个数和未知量个 时，方程组（2.1）有惟一解。 数相同的n阶线性方程组，一般形式为
a11 x1 a12 x2 ... a1n xn b1 a21 x1 a22 x2 ... a2 n xn b2 ...... an1 x1 an 2 x2 ... ann xn bn
(k a ik ) mik (k a kk ) ( k 1) ( (k a ij a ijk ) mik a kj ) ( bi( k 1) bi( k ) mik bk k ) i, j k 1, k 2, , n
② 回代过程
( bn n ) xn (n a nn ) n (i ) ( bi a iji ) x j j i 1 xi ( a iii ) i n 1, n 2, ,1
1 2 r ( 2 ) r 4 0 1 r ( ) r 2 7 0
2 1 3 1
i 行）
1 2 13 2
1 3 4 1 5 3 2 2
(1 a11) (1 a12) (2 a 22 )
a11
( a n2 ) 2
( a11) x1 b1(1) n ( ( 2) x 2 b2 2 ) a2n ( 2) ( 2) a nn x n bn
一般线性方程组使用高斯消去法求解时，
(k 在消元过程中可能会出现 akk ) 0 的情况，这
(k 时消去法将无法进行；即使 akk ) 0 ，但它的
绝对值很小时，用其作除数，会导致其他元素
第3章 解线性方程组的直接法 一般b≠0, 当系数矩阵A非奇异(即detA≠0) 常见的线性方程组是方程个数和未知量个 时，方程组（2.1）有惟一解。 数相同的n阶线性方程组，一般形式为
a11 x1 a12 x2 ... a1n xn b1 a21 x1 a22 x2 ... a2 n xn b2 ...... an1 x1 an 2 x2 ... ann xn bn
(k a ik ) mik (k a kk ) ( k 1) ( (k a ij a ijk ) mik a kj ) ( bi( k 1) bi( k ) mik bk k ) i, j k 1, k 2, , n
② 回代过程
( bn n ) xn (n a nn ) n (i ) ( bi a iji ) x j j i 1 xi ( a iii ) i n 1, n 2, ,1
线性方程组直接法
类似选主元法
练习 利用LU分解法求解方程组
1 2 3 x1 2 1 3 5 x2 4. 1 3 6 x3 5
1001 2 3 2 1 答L： U 110 01 2 ， y 2 ,x 0 .
111 001 1 1
二、解三对角方程组的追赶法
在数值求解常微分方程边值问题、热传导方程和建立
二、向量和矩阵的范数
定义1 ( 向量范数) x 和 y 是 Rn 中的任意向量 , 向量范数‖•‖是定义
在 Rn上的实值函数, 它满足:
(1) ‖ x ‖≥0, 并且当且仅当 x=0 时, ‖ x ‖=0;
(2) ‖k x ‖=|k| ‖ x ‖, k 是一个实数;
(3) ‖ x + y ‖≤ ‖ x ‖+ ‖ y ‖
1 0 01 2 3
A 2 3
1 5
0 0 1 0
1 0
4
24
LU
3=-72/-24; 2=[-10+4*3]/1;
求解
1=[14-(2*2+3*3)]/1]
Ly (14, 18, 20)T , 得y (14, 10,72)T 同理当 ukk 0或 Ux (14, 10, 72)T , 得x (1, 2, 3)T 很小时，可用
子式 Di 0(i 1,2,,k)，即
a11 Di
ai1
a1i
aii
0aa1i((i1i1))
0 Di
Di1 0
由于高斯消去法过在程消中元可能ak(出 kk) 现 0的情况， 这时消去法将无；法即进使行主a元 k(kk) 素0但很小时， 用其作除数，会他导元致素其数量级的长严和重舍增
入误差的扩散，使最得后计也算的解不可靠。
练习 利用LU分解法求解方程组
1 2 3 x1 2 1 3 5 x2 4. 1 3 6 x3 5
1001 2 3 2 1 答L： U 110 01 2 ， y 2 ,x 0 .
111 001 1 1
二、解三对角方程组的追赶法
在数值求解常微分方程边值问题、热传导方程和建立
二、向量和矩阵的范数
定义1 ( 向量范数) x 和 y 是 Rn 中的任意向量 , 向量范数‖•‖是定义
在 Rn上的实值函数, 它满足:
(1) ‖ x ‖≥0, 并且当且仅当 x=0 时, ‖ x ‖=0;
(2) ‖k x ‖=|k| ‖ x ‖, k 是一个实数;
(3) ‖ x + y ‖≤ ‖ x ‖+ ‖ y ‖
1 0 01 2 3
A 2 3
1 5
0 0 1 0
1 0
4
24
LU
3=-72/-24; 2=[-10+4*3]/1;
求解
1=[14-(2*2+3*3)]/1]
Ly (14, 18, 20)T , 得y (14, 10,72)T 同理当 ukk 0或 Ux (14, 10, 72)T , 得x (1, 2, 3)T 很小时，可用
子式 Di 0(i 1,2,,k)，即
a11 Di
ai1
a1i
aii
0aa1i((i1i1))
0 Di
Di1 0
由于高斯消去法过在程消中元可能ak(出 kk) 现 0的情况， 这时消去法将无；法即进使行主a元 k(kk) 素0但很小时， 用其作除数，会他导元致素其数量级的长严和重舍增
入误差的扩散，使最得后计也算的解不可靠。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第二章 解线性方程组的直接法本章研究的对象是n 阶线性方程组⎪⎪⎩⎪⎪⎨⎧=+++=+++=+++nn nn n n n n n n b x a x a x a b x a x a x a b x a x a x a .........22112222212111212111 （2.1）其矩阵形式为b AX = （2.1）′其中，)(ij a A =是方程组的系数矩阵，⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=n x x x X ...21,⎪⎪⎪⎪⎪⎭⎫⎝⎛=n b b b b ...21分别为方程组的未知向量和常数向量。
所谓直接法，就是在不计舍入误差时，经过有限步运算能求得方程组精确解的方法。
下面介绍几种较实用的直接法。
2.1 Gauss 消去法 2.1.1 Gauss 顺序消去法高斯（Gauss ）消去法实质是消元法,只是步骤规范,便于编程。
它的基本做法是把方程组(2.1)转化成一个等价的三角方程组⎪⎪⎩⎪⎪⎨⎧==++=+++n n nn n n n n g x b g x b x b g x b x b x b 2222211212111 (2.2) 这个过程称为消元。
然后,逐个求出11,,,x x x n n -,这个过程称为回代。
(一) 高斯消去法的计算过程为了符号统一,把方程组(2.1)改写成下面形式⎪⎪⎩⎪⎪⎨⎧=+++=+++=+++)1()1(2)1(1)1()1()1(2)1(1)1()1()1(2)1(1)1( (212)22221111211n nn n n n n b x a x a x a b x a x a x a b x a x a x a n n n(2.3)用矩阵表示为)1()1(b X A = (2.3)′其中⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡=)1()1(2)1(1)1(2)1(22)1(21)1(1)1(12)1(11)1(nn n n nn a a a a aa a aa A, ⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=)1()1()1()1(...21n b b b b 若0)1(11≠a ,用第二个方程减去第一个方程的)1(11)1(21/a a 倍,第三个方程减去第一个方程的)1(11)1(31/a a 倍,等等。
即得与(2.3)等价的方程组 ⎪⎪⎪⎩⎪⎪⎪⎨⎧=++=++=++=+++)2()2(2)2()2(3)2(2)2()2()2(2)2()1()1(2)1(1)1( (23322)222111211nnn n nn n b x a x a b x a x a b x a x a b x a x a x a n n n n (2.4) 用矩阵表示为)2()2(b X A = (2.4)′其中⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=)2()2(3)2(2)2(3)2(33)2(32)2(2)2(23)2(22)1(1)1(13)1(12)1(11)2(000nn n n n n n a a a a a a a a a a a a a A, ⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛=)2()2()1()2(...21n b b b b 令),3,2(/)1(11)1(11n i a a m i i ==,则n j i b m b b a m a a i i i j i ij ij ,3,2,)1(11)1()2()1(11)1()2(=⎪⎩⎪⎨⎧-=-= (2.5)类似地,若0)2(22≠a ,(2.4)中第i 个方程减去第二个方程的)2(22)2(2/a a i 倍,得(2.4)的等价方程组⎪⎪⎪⎩⎪⎪⎪⎨⎧=++=++=+++=++++)3()3(3)3()3(3)3(33)3()2()2(3)2(2)2()1()1(3)1(2)1(1)1( (3332)2232211131211nnn n n n b x a x a b x a x a b x a x a x a b x a x a x a x a n n n n n (2.6) 用矩阵表示为)3()3(b X A = (2.6)′其中⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=)3()3(3)3(3)3(33)2(2)2(23)2(22)1(1)1(13)1(12)1(11)3(00000nn n n n n a a a a a a a a a a a A, ⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛=)3()2()1()3(...21n b b b b 令),4,3(/)2(22)2(22n i a a m i i ==,则n j i b m b b a m a a i i i j i ij ij ,4,3,)2(11)2()3()2(11)2()3(=⎪⎩⎪⎨⎧-=-= (2.7)若0)3(33≠a ,上述步骤可继续进行下去,经过1-n 步,即得等价的三角方程组⎪⎪⎪⎩⎪⎪⎪⎨⎧==++=+++=++++)()()3(3)3(33)3()2()2(3)2(2)2()1()1(3)1(2)1(1)1( (332)2232211131211n n n n n n n n nn n n b x a b x a x a b x a x a x a b x a x a x a x a (2.8) 用矩阵表示为)()(n n b X A = (2.8)′其中⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=)()3(3)3(33)2(2)2(23)2(22)1(1)1(13)1(12)1(11)(00000n nn n n n n a a a a a a a a a a A , ⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛=)()2()1()(...21n n n b b b b 把系数矩阵化为上三角矩阵的过程称为消元过程。
消元过程元素的计算公式为⎪⎪⎩⎪⎪⎨⎧≤<≤≤=≤≤+≤≤+-=-=≤≤==+++++ni k j a n j k n i k baab b a a a a a n j k i b b a a k ijk kk kkk ikk ik ik kjk kk k ik k ij k ij k i k i k ij k ij 101,1)/()/(,,)1()()()()()1()()()()()1()()1()()1( (2.9)有了等价的三角方程组(2.8),就很容易求解了。
从(2.8)最后一个式子,得)()(/n nnn n n x b x = 把它代入倒数第二个式子,可求出1-n x ,把1,-n n x x 代入倒数第三个式子可求出2-n x ,依次求得全部变量),,2,1(n i x i =,这一过程叫回代过程,其计算公式为⎪⎪⎩⎪⎪⎨⎧--=-==∑+=1,,2,1/)(/)(1)()()()( n n i a x a b x a b x i ii n i j j i ij i i i n nn n n n (2.10)(二) 高斯消去法的运算量因为相对于乘除法而言，加减法所需的时间很少，故只计乘除法的运算量。
消去第一列的1-n 个系数,需做乘法)1(-⨯n n 次, 消去第二列的2-n 个系数,需做乘法)2()1(-⨯-n n 次,……。
共需∑=-=-nk n n k k 12)1(3)1(次乘法,要做的除法运算次数为)1(211-=∑-=n nk n k ，消元过程所需的乘除次数为 n n n N 6523231-+=回代过程所需的乘除次数为)1(212+==∑=n nk N nk ,所以高斯消去法的运算量为n n n N N N 31312321-+=+=2.1.2Gauss 主元消元法高斯消去法消元过程中，第k 步求k n -个倍数)()(/k kkk ik a a 用到的除数)(k kk a ,称为主元，若它为0，或接近于0，计算机将因“0作除数”或“溢出”而中止计算，或产生较大的误差。
例2.1 方程组⎩⎨⎧=+=+210001.02121x x x x 的精确解为.9999/9998,9999/1000021==x x 若在尾数为三位十进数字的计算机上用高斯消元求解。
消去第二个方程的1x ,得⎩⎨⎧-=-=+100001000010001.0221x x x 回代得0,112==x x ，与精确解相差甚远。
这是因为用0.0001作除数,使舍入误差剧增造成的。
为了避免这种情况,先将方程组的两个方程交换一下,变为⎩⎨⎧=+=+10001.022121x x x x 消去第二个方程的1x ,得⎩⎨⎧==+12221x x x 回代得1,112==x x 。
结果和精确解非常接近,因为这样避免了小主元。
一般地,为避免出现小主元，可在消去过程的第k 步，在第k 列)()(,1)(,,,k nk k k k k kk a a a +中选主元(绝对值最大的数)(k pk a )，交换k p ,两行,这种选主元的高斯消去法称为列主元高斯消去法。
若在消去过程的第k 步,在n k ~行,n k ~列中选主元,则称为全主元高斯消去法。
全主元法选主元要花大量的时间,并且需要交换变量的次序。
而列主元高斯消去法,计算简单,且基本能控制误差的影响。
故一般采用列主元法。
算法2.1 列主元高斯消去法1．输入系数矩阵A ，常数列向量b ，阶数n2．对1,,2,1-=n k 做(1) 按列选主元 ||max ||ik ni k pk a a ≤≤=保存主元所在的行标p(2) 若0||=pk a ，则系数矩阵奇异，计算停止；否则顺序进行。
(3) 若k p ≠,交换k p ,两行(4) 计算kk ik ik a a m /=,n k i ,,1 += (5) 消元:n k j i a m a a kjik ij ij ,,1,: +=-=n k i b m b b kik i i ,,1: +=-=3．回代1,,1,,/][:1-=-=∑+=n n i ab a b b iini j jiji i解X 存于常数项b 中例2.2 用列主元高斯消去法求解方程组⎪⎩⎪⎨⎧=+-=-=++-6557710462332121321x x x x x x x x 解 用增广矩阵][b A 表示计算过程⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡---6515707104623 行，交换第选主元2110}5,10,3max{,21a ==⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡---6515462370710 0,3121为消元，化a a⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--2/552/5010/61610/1070710行，交换第选主元322/5}2/5|,10/1max{|32a ==-⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--10/61610/102/552/5070710032为消元，化a⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-5/315/31002/552/5070710这就是上三角方程组的增广矩阵。