2177数值分析课件

1、 第二章第二章 线性方程组的直接解法线性方程组的直接解法 2.1 2.1 引引 言言 在自然科学和工程技术中在自然科学和工程技术中, ,很多问题归结为解线性方程很多问题归结为解线性方程组组. .有的问题的数学模型中虽不直接表现为含线性方程组有的问题的数学模型中虽不直接表现为含线性方程组, ,但它的数值解法中将问题但它的数值解法中将问题“离散化离散化”或或“线性化线性化”为线性为线性方程组方程组. .因此线性方程组的求解是数值分析课程中最基本的因此线性方程组的求解是数值分析课程中最基本的内容之一内容之一. . 线性方程组线性方程组: :结束nnnnnnnnnnbxaxaxabxaxaxabxax

2、axa22112222212111212111常记为矩阵形式常记为矩阵形式 Ax=b (2.2) 1 此时此时A是一个是一个nn方阵方阵, ,x和和b是是n维列向量维列向量. . 根据线性代数知识若根据线性代数知识若 |A| 0,(2.2) 0,(2.2)的解存在且唯一的解存在且唯一. . 关于线性方程组的解法一般分为两大类关于线性方程组的解法一般分为两大类, ,一类是一类是直接法直接法, ,即经过有限次的算术运算即经过有限次的算术运算, ,可以求得可以求得(2.1)(2.1)的精确解的精确解( (假定计假定计算过程没有舍入误差算过程没有舍入误差).).如线性代数课程中提到的克莱姆算如线性代数

3、课程中提到的克莱姆算法就是一种直接法法就是一种直接法. .但该法对高阶方程组计算量太大但该法对高阶方程组计算量太大, ,不是不是一种实用的算法一种实用的算法. .实用的直接法中具有代表性的算法是实用的直接法中具有代表性的算法是高斯消元法高斯消元法, ,其它算法都是它的变形和应用其它算法都是它的变形和应用. . 另一类是另一类是迭代法迭代法, ,它将它将(2.1)(2.1)变形为某种迭代公式变形为某种迭代公式, ,给出初给出初始解始解x0 0, ,用迭代公式得到近似解的序列用迭代公式得到近似解的序列xk k, ,k=0,1,2, =0,1,2, , ,在一定的条件下在一定的条件下xk kx* *

4、( (精确解精确解).).迭代法显然有一个收敛条迭代法显然有一个收敛条件和收敛速度问题件和收敛速度问题. . 这两种解法都有广泛的应用这两种解法都有广泛的应用,我们将分别讨论我们将分别讨论,本章介绍直本章介绍直接法接法.结束结束 2 2.2 2.2 高斯高斯(Gauss)(Gauss)消元法消元法 高斯消元法是一种古老的方法高斯消元法是一种古老的方法. .我们在中学学过消元法我们在中学学过消元法, ,高斯消元法就是它的标准化的、适合在计算机上自动计算高斯消元法就是它的标准化的、适合在计算机上自动计算的一种方法的一种方法. .2.2.1 2.2.1 高斯消元法的基本思想高斯消元法的基本思想例例1

5、 1 解方程组解方程组 (2.3)(2.3) (2.4) (2.4) (2.5) (2.5)3946572132321321321xxxxxxxxx第一步第一步, ,将将(2.3)(2.3)乘乘-2-2加到加到(2.4)(2.4)；(2.3)(2.3)乘乘-1-1加到加到(2.5),(2.5), 得到得到 (2.3)(2.3) (2.6) (2.6) (2.7) (2.7)462431323232321xxxxxxx 3结束结束第二步第二步, ,将将(2.6)(2.6)乘乘-2/3-2/3加到加到(2.7),(2.7),得到得到 (2.3)(2.3) (2.6) (2.6) (2.8) (2.

6、8)32032043132332321xxxxxx回代回代: :解解(2.8)(2.8)得得x3 3, ,将将x3 3代入代入(2.6)(2.6)得得x2 2, ,将将x2 2, , x3 3代入代入(2.3)(2.3)得得x1 1, ,得到解得到解 x* *=(2,1,-1)=(2,1,-1)T T 容易看出第一步和第二步相当于增广矩阵容易看出第一步和第二步相当于增广矩阵:b在作在作行变换行变换, ,用用ri表示增广阵表示增广阵A:b的第的第i行行: :441620130321361941572321:3132122rrrrrrbA结束结束 4320413200013032132332rrr

7、 由此看出上述过程是逐次消去未知数的系数由此看出上述过程是逐次消去未知数的系数, ,将将Ax=b化化为等价的三角形方程组为等价的三角形方程组, ,然后回代解之然后回代解之, ,这就是高斯消元法这就是高斯消元法. .2.2.2 2.2.2 高斯消元法公式高斯消元法公式 记记Ax=b为为A(1)x=b(1),A(1)和和b(1)的元素记为的元素记为 和和 ,i,j=1,2,n.第一次消元第一次消元,目的是消掉第二个方程到第目的是消掉第二个方程到第n个方程个方程中的中的x1项项,得到得到A(2)x=b(2),这个过程须假定这个过程须假定 0.) 1 (ija) 1 (ib) 1 (11a结束结束 5

8、)2()2()2()2(2)1(1)2()2(2)1(1)2(2)2(22)1(12)1(11),3,2()1()1(2)1(1)1()1(2)1(1)1(2)1(1)1(22)1(21)1(12)1(11)1()1(:00:11bAbbbaaaaaaabbbaaaaaaaaabAnnnnnnrrlrninnnnnnniii 在在A(1):b(1)中中, ,红方框中的元素是要化为红方框中的元素是要化为0 0的部分；的部分；A(2):b(2)中中, ,红方框中的元素全部已发生变化红方框中的元素全部已发生变化, ,故上标由故上标由(1)(1)改改(2),(2),计算公式为计算公式为: :结束结束

9、6)1(11)1()2()2(1)1(11)1()2()1(11)1(110blbbaalaaaaliiiijiijijii (i=2,3,n) (i,j=2,3,n) (i=2,3,n) (i=2,3,n)第第k次消元次消元(1(1kn-1)-1) 设第设第k-1次消元已完成次消元已完成,且且 0,此时增广矩阵如下此时增广矩阵如下:)(kkka)()()2(2)1(1)()()2(2)1(1)()()2(2)2(22)1(1)1(12)1(11)()(:knkkknnkknnnknkkkkkkkkbbbbaaaaaaaaaaabA结束结束 7 本次消元的目的是对框内部分作类似第一次消元的处理

10、本次消元的目的是对框内部分作类似第一次消元的处理,消掉第消掉第k+1个方程到第个方程到第n个方程中的个方程中的xk项项,即把即把 到到 化化为零为零.计算公式如下计算公式如下:)(, 1kkka)(knka)()()1()1()()()1()()(0kkikkikikikkkjikkijkijkkkkikikblbbaalaaaal (i=k+1,n) (i,j=k+1,n) (i=k+1,n) (i=k+1,n) 只要只要 0,(k=1,2,n-1)消元过程就可以进行下去消元过程就可以进行下去.当当k=n-1时时,消元过程完成消元过程完成,得得:)()2(2) 1 (1)()2(2) 1 (

11、1)2(22) 1 (12) 1 (11)()(:nnnnnnnnnbbbaaaaaabA)(kkka结束结束 8 它的方阵部分它的方阵部分A(n)是一个上三角形矩阵是一个上三角形矩阵,它对应的方程组是它对应的方程组是一个上三角形方程组一个上三角形方程组,只要只要 0,就可以回代求解就可以回代求解,公式为公式为)(nnna)(1)()()()(iiinijjiijiiinnnnnnaxabxabx (i=n-1,n-2,1)综合以上讨论综合以上讨论, ,高斯消元法解线性方程的公式为高斯消元法解线性方程的公式为: : 1 1消元消元 令令 ( (i,j=1,2,=1,2, ,n) )iiijij

12、bbaa) 1 () 1 (,结束结束 9)()()1()()()1()1()()(0kkikkikikkjikkijkijkikkkkkikikblbbalaaaaal( (i=k+1,k+2,n) ) ( (i,j=k+1,k+2,n) ) ( (i=k+1,k+2,n) (2.9) (2.9)2 2回代回代, ,若若 0 0)(nnna)(1)()()()(iiinijjiijiiinnnnnnaxabxabx (i=n-1,n-2,1) (2.10)(2.10)结束结束 对对k=1=1到到n-1,-1,若若 0 ,0 ,进行进行: : ( (i=k+1,k+2,n) )(kkka 10

13、2.2.3 高斯消元法的条件高斯消元法的条件 以上过程中以上过程中,消元过程要求消元过程要求 0 (i=1,2,n-1),回代过程则回代过程则进一步要求进一步要求 0,但就方程组但就方程组Ax=b讲讲, 是否等于是否等于0是无法是无法事先看出的事先看出的.)(nnna)(iiia)(iiia注意注意A的顺序主子式的顺序主子式Di (i=1,2,n)在消元过程中不变在消元过程中不变.这是因这是因为消元所作的变换是为消元所作的变换是“将某行的若干倍加到另一行将某行的若干倍加到另一行”上上,据线性代数知识据线性代数知识,此类变换不改变行列式的值此类变换不改变行列式的值.若高斯消元若高斯消元过程已进行

14、了过程已进行了k-1步步(此时当然应有此时当然应有 0,ik-1),这时计算这时计算A(k)的顺序主子式的顺序主子式:)(iiia(1 )11 1(1 )( 2 )21 12 2(1 )( 2 )(1 )11 12 21 ,1(1 )( 2 )()1 12 2kkkkkkk kDaDaaDaaaDaaa结束结束 11)(1) 1 (111iiiiiaDDaD 有递推公式有递推公式( (i=2,3,k) )显然显然, , 可知可知,消元过程能进行到底的充要条件消元过程能进行到底的充要条件是是Di0 ,(i=1,2,n-1),若要回代过程也能完成若要回代过程也能完成,还应加上还应加上Dn=A0,综

15、合上述有综合上述有:00)(iiiiaD定理定理2.1 高斯消元法消元过程能进行到底的充要条件是系数高斯消元法消元过程能进行到底的充要条件是系数阵阵A的的1到到n-1阶顺序主子式不为零；阶顺序主子式不为零；Ax=b能用高斯消元法解能用高斯消元法解的充要条件是的充要条件是A的各阶顺序主子式不为零的各阶顺序主子式不为零.2.2.4 高斯消元法的计算量估计高斯消元法的计算量估计 消元过程的工作量消元过程的工作量,参看公式参看公式(2.9),k是消元次数是消元次数,k=1,2,n-1,第第k步消元时步消元时,计算计算lik(i=k+1,n)需要需要n-k次除法次除法；计算；计算 (i,j=k+1, ,

16、n)需要需要(n-k)2次乘法及次乘法及(n-k)2次加减法；计算次加减法；计算 需要需要n-k次乘法及次乘法及n-k次减法次减法,合计合计:) 1( kija) 1( kib结束结束 12 乘除法次数乘除法次数 加减法的次数加减法的次数111122) 1(6) 12)(1()()(nknknnnnnknkn111122) 1(6) 12)(1()()(nknknnnnnknkn 回代过程的工作量回代过程的工作量,参见公式参见公式(2.10),求求xk需需n-k次加减法次加减法, n-k次乘法和次乘法和1次除法次除法,合计为合计为 乘除法次数乘除法次数12) 1() 1(nknnkn 加减法次

17、数加减法次数12) 1()(nknnkn 总的运算次数为总的运算次数为 乘除法乘除法 (当当n较大时较大时)333323nnnn结束结束 13 加减法加减法 (当当n较大时较大时)36) 12)(1(3nnnn 一般讲乘除法的运算比加减法占用机时多得多一般讲乘除法的运算比加减法占用机时多得多, ,往往只往往只统计乘除法次数而称高斯消元法的运算量为统计乘除法次数而称高斯消元法的运算量为 次次. .33n 2.3 选主元的高斯消元法选主元的高斯消元法 在上节的算法中在上节的算法中,消元时可能出现消元时可能出现 =0的情况的情况,高斯消元高斯消元法将无法继续；即使法将无法继续；即使 0,但但 0 (

18、i=1,2, ,n). 38)32.2(/112/1112kkjkjkikijijjkjkjjjjlllallalyxLbLyT结束 39结束 40).(,/,/3321121111nnilxlyxnilylbyiinikkkiiiiiikkikii结束 41 nnnnnnnnnffffxxxxbacbacbacbA12112111122211结束 42)35.2(, 3 ,2,/1, 3 ,2,/111111nicniabbbciiiiiii)36.2(, 3 ,2,/)(/1111niyafybfyiiiii).(,3721211nnixyxyxiiiinn结束 432.8 向量和矩阵的范

19、数向量和矩阵的范数在分析方程组的解的误差及下章中迭代法的收敛时在分析方程组的解的误差及下章中迭代法的收敛时,常产生一个问题常产生一个问题,即如何即如何判断向量判断向量x的的“大小大小”,对矩阵也有类似的问题对矩阵也有类似的问题.本节介绍本节介绍n维向量和维向量和nn矩阵矩阵的范数的范数.结束结束|max|,|, |1211221ininiiniixxxxxx1 442.8.1 向量范数向量范数定义定义2.1 x和和y是是Rn中的任意向量中的任意向量,向量范数向量范数是定义在是定义在Rn上的实值函数上的实值函数,它满足它满足:容易看出容易看出,实数的绝对值实数的绝对值,复数的模复数的模,三维向量

20、的模都满足以上三条三维向量的模都满足以上三条,n维向量的维向量的范数概念是它们的自然推广范数概念是它们的自然推广.常使用的向量范数有三种常使用的向量范数有三种,设设x=(x1,x2,xn)T (1) x 0,并且并且,当且仅当当且仅当x=0时时, x =0;(2) k x =|k| x ,k是一个实数是一个实数;(3) x + y x + y 容易验证容易验证, ,它们都满足三个条件它们都满足三个条件. .例例6 6 x=(1,0.5,0,-0.3)=(1,0.5,0,-0.3)T, T, 求求解解: :结束结束115761305018130050122221x.x.x2.8.2 2.8.2

21、矩阵范数矩阵范数从向量范数出发从向量范数出发, ,可以定义矩阵的范数可以定义矩阵的范数. .定义定义2.22.2 设设A是是nn矩阵矩阵, ,定义定义|max|max|1|0AxxAxAnnRxxRxx为矩阵为矩阵A的范数的范数. .这样定义的范数有如下性质这样定义的范数有如下性质: :45xxx,21(1) (1) A0,0,并且并且, ,当且仅当当且仅当A A是零矩阵时是零矩阵时, , A = =0 0(2) (2) kA= |= |k| | A(3)(3)两个同阶方阵两个同阶方阵A,B, ,有有A+BA+B(4)(4)A是是nn矩阵矩阵, ,x是是n维向量维向量, ,有有AxAx(5)(

22、5)A,B都是都是nn矩阵矩阵, ,有有ABAB矩阵范数最常用的有以下三种矩阵范数最常用的有以下三种: :它们分别与向量的三种范数对应它们分别与向量的三种范数对应,即用一种向量范数可定义相应的矩阵范数即用一种向量范数可定义相应的矩阵范数.定理定理2.5 Rn空间上的范数等价空间上的范数等价.即对任意给定的两种范数即对任意给定的两种范数 有下列关系有下列关系: m M 其中的其中的m,M是正的常数是正的常数, 表示向量或矩阵的表示向量或矩阵的范数范数.结束结束njijniniijnjaAAaA1112111|max|max|（1 1 是是ATA的最大特征值）的最大特征值）46从以上定理看出从以上

23、定理看出,当向量或矩阵的任一种范数趋于零时当向量或矩阵的任一种范数趋于零时,其它各种范数也趋于其它各种范数也趋于零零.因此讨论向量和矩阵序列的收敛性时因此讨论向量和矩阵序列的收敛性时,可不指明使用的何种范数；证明时可不指明使用的何种范数；证明时,也只要就某一种范数证明就行了也只要就某一种范数证明就行了.有了向量和矩阵范数的概念有了向量和矩阵范数的概念,就可以定义向量和矩阵序列的收敛就可以定义向量和矩阵序列的收敛.定义定义2.3 如果如果 称向量序列称向量序列x (k)收敛于向量收敛于向量x.。结束结束0|lim)(xxkk定义定义2.4 如果如果 称方阵序列称方阵序列A (k)收敛于方阵收敛于

24、方阵A.。0|lim)(AAkk定理定理2.6 向量序列向量序列x (k)收敛于向量收敛于向量x的充要条件是的充要条件是:njxxjkjk, 2 , 1,lim)(定理定理2.7 方阵序列方阵序列A (k)收敛于方阵收敛于方阵A的充要条件是的充要条件是:njiaaijkijk, 2 , 1,lim)(2.8.3 谱半径谱半径定义定义2.5 设设n阶方阵阶方阵A的特征值为的特征值为j (j=1,2,n),则称为则称为A的谱半径的谱半径.|max)(1jnjA|)(AA 47定理定理2.8 方阵谱半径和方阵范数有如下关系方阵谱半径和方阵范数有如下关系:证证: : 设设i是是A的任一特征值的任一特征

25、值, ,xi为对应的特征向量为对应的特征向量 Axi= ixi两边取范数两边取范数, ,用矩阵性质用矩阵性质(4)(4)有有 | |i| |x iAx i 因为因为 x i 0,0,所以所以x i00所以所以 | |i | |A i=1,2,=1,2, ,n, , 所以所以 ( (A)=max|)=max|i | |A.定理定理2.9 设设A是是nn阶矩阵阶矩阵,A的各次幂组成的矩阵序列的各次幂组成的矩阵序列 I,A,A2, ,Ak, 收敛于零收敛于零,即即 的充要条件是的充要条件是(A)1.证明从略证明从略.结束结束例例7求求A1 1, , A2 2 , , A , , ( (A).0lim

26、kkA4142. 3246|246222A，所以之模最大显然210121012A解解:显然显然A1 1 =4, =4,A=4=4 .2464,0)412)(4(541464145|,5414641453212，TT，AAIAA解之得48结束结束这里这里,我们指出我们指出,对于实对称矩阵对于实对称矩阵A,有有2.8.4 条件数及病态方程组条件数及病态方程组线性方程组线性方程组 Ax=b 的解是由系数阵的解是由系数阵A及右端向量及右端向量b决定的决定的.由实际问题中得到由实际问题中得到的方程组中的方程组中,A的元素和的元素和b的分量的分量,总不可避免地带有误差总不可避免地带有误差,因此也必然对解向

27、因此也必然对解向量量x产生影响产生影响.222, 0) 24)(2(210121012|3212，AI解之得4142. 322|)(2233A，所以之模最大显然2|)(AA 1.设设Ax=b中仅中仅b向量有误差向量有误差b ,对应的解对应的解x发生误差发生误差x ,即即:bbxAAxbbxxA)(49这就提出一个问题这就提出一个问题:当当A有误差有误差A,b有误差有误差b时时,解向量解向量x有多大误差有多大误差?即当即当A和和b有微小变化时有微小变化时,x的变化有多大的变化有多大? 若若A和和b的微小变化的微小变化,也只导致也只导致x的微小变的微小变化化,则称此问题是则称此问题是“良态良态”的

28、；反之的；反之,若若A和和b的微小变化会导致的微小变化会导致x的很大变化的很大变化,则称此问题为则称此问题为“病态病态”问题问题.在以下的讨论中在以下的讨论中,设设A非奇异非奇异,b0,所以所以|x|0. 注意到注意到Ax=b, ,所以所以Ax=b, ,若若A非奇异非奇异, ,有有 x= =A-1-1b. .结束结束2.A有误差有误差A ,b无误差无误差,此时有类似的结论。此时有类似的结论。|1bbAAxx|Abx 定义定义2.6 若若nn方阵方阵A非奇异非奇异,则称则称AA-1-1为为A的条件数的条件数,记为记为 Cond(A)=AA-1-1由于选用的范数不同由于选用的范数不同,条件数也不同

29、条件数也不同,在有必要时在有必要时,可记为可记为Condp(A)=ApA-1-1p (p=1,2, ).503.由以上分析不难看出由以上分析不难看出,当当b和和A一定时一定时,AA-1-1的大小的大小,决定了决定了x 的相对的相对误差限误差限. AA-1-1越大时越大时,x 可能产生的相对误差越大可能产生的相对误差越大,即问题的即问题的“病态病态”程程度越严重度越严重.同时同时,我们看出我们看出,Ax=b 的的“病态病态”程度程度,只与只与A的元素有关的元素有关,而与而与b的的分量是无关的分量是无关的.为此为此,我们有我们有:所以所以 xA-1-1 b . . 又因为又因为b=AxAx,所以所

30、以 两式相除两式相除, ,有有即即x的相对误差小于等于的相对误差小于等于b的相对误差的的相对误差的AA-1-1倍倍. . 由于由于1=I=AA-1AA-1=cond(A),可知可知cond(A)总是大于等于总是大于等于1的数的数.条件条件数反映了方程组的数反映了方程组的“病态程度病态程度”.条件数越小条件数越小,方程组的状态越好方程组的状态越好,条件数很大条件数很大时时,称方程组为病态方程组称方程组为病态方程组.但多大的条件数才算病态则要视具体问题而定但多大的条件数才算病态则要视具体问题而定,病病态的说法只是相对而言态的说法只是相对而言. 结束结束51条件数的计算是困难的条件数的计算是困难的,这首先在于要算这首先在于要算A-1,而求而求A-1比解比解Ax=b的工作量还大的工作量还大,当当A确实病态时确实病态时,A-1也求不准确；其次要求范数也求不准确；其次要求范数,特别是求特别是求A2, A-12又十分