四川大学数值分析期末总复习

1、四川大学水利水电学院数值分析程复习课四川大学水利水电学院Gauss消元法解线性代数方程组的直接法列主元素消去法全主元素消去法矩阵三角分解法范数、条件数平方根法LU分解法追赶法列主元素三角分解法四川大学水利水电学院第四章 解线性代数方程组的直接法（适用于中等规模的n阶线性方程组）范数、条件数Gauss消去法LU分解法平方根法四川大学水利水电学院了解几个：顺序主子式Di：方阵前i行、前i列元素矩阵的行列式；非奇异矩阵：对方阵A而言， 即可证明A非奇异，涉及特征值时，全部 特征值均不等于0可证明A非奇异.对称正定矩阵：A的全部特征值大于0；顺序主子式全大于0； 行列式为正；严格对角占优矩阵：详见书P

2、173.0A TAA四川大学水利水电学院Gauss消去法11 11221121 1222221 122nnnnnnnnnna xa xa xba xa xa xba xa xa xb线性代数方程组：用矩阵及向量形式表示：AX = b（PS:A为非奇异矩阵，即 ）1112111212222212nnnnnnnnaaaxbaaaxbAXbxbaaa0A 四川大学水利水电学院消元过程：消元过程：实质上是用)1(11)1(21/aa去乘以第一个方程，得到一个新的方程，然后用第二个方程减去这个新的方程，使其第一项为0，最终变成：)2(2)2(23)1(232)2(22bxaxaxann同样取)1(11)

3、1(31aa乘以第一个方程，得到一个新的方程，然后用第三个方程减去这个新的方程，使其第一项为0，最终变成： 上标(2)实际上表示经过消去法一步，以此类推(3)表示经过消去法两步。)2(3)2(33)1(332)2(32bxaxaxann四川大学水利水电学院(1)(1)(1)(1)11112211(2)(2)(2)22222(2)(2)(2)32233(2)(2)(2)22nnnnnnnnnnnaxaxaxbaxaxbaxaxbaxaxb重复此步骤n-1次最终得到等价方程组：经过消元法n-1步后，可以得到一个等价的上三角形方程组：（PS：经过初等变换得到的矩阵与原矩阵等价）(1)(1)(1)(1

4、)(1)11112213311(2)(2)(2)(2)22223322(3)(3)(3)33333 nnnnnna xa xa xa xba xa xa xba xa xb( )( ) nnnnnna xb( )( )nnAxb即：已为00四川大学水利水电学院经过回代可得到方程组的解：1( )( ).nnnnnnxbxa此时必须满足条件：( )0nnnan阶线性方程组消元过程所需要的总运算量为：nnn313123消元乘法运算量：消元除法运算量：221()(1)3nknkkn11(1)2nknkn回代乘除法运算量：) 1(2nn四川大学水利水电学院( )( )(1)( )( )(1)( )( )

5、1,1,1,kikikkkkkkkijijikkjkkkiiikkaliknaaalai jknbblbikn（4.1.1）( )( )( )( )( )11,1nnnnnnnkkkkkkjjkkj kxbaxbaxakn （4.1.2）四川大学水利水电学院消元法能够运用的为：( )01,2,.,iiiaik：( )01,2,.,iiiaik矩阵A的顺序主子式01,2,., ;.iDik kn推论：若矩阵A的顺序主子式 则有： 01,2,., ;.iDik kn(1)( )1111,2,3,.,.kkkkkDaD aknD四川大学水利水电学院若某个主元 很小，会引起很大的误差。 ()kkka因

6、此可以采用或。 实质上是在消元法进行了k（k=0,1,2,.,n-1）步之后，选取系数矩阵A第k+1行到第n行中绝对值最大的元作为主元，并利用初等行变换和列变换交换其位置，使其置于对角线上，成为对角元，以减小误差。 实质上是在消元法进行了k（k=0,1,2,.,n-1）步之后，选取系数矩阵A第k+1列中绝对值最大的元作为主元，并利用初等行变换使主元其置于对角线上，成为对角元，以减小误差。四川大学水利水电学院典型题目1、概念题、消元及回代公式； 2、用全主元素消去法或列主元素消去法解方程组； 3、相关定理、定义或变形证明题(详见书本证明过程).：分别用全主元素消去法和列主元素消去法解方程组，并由

7、此计算系数行列式的值.第一步：消元法进行了0步后，选出前三行的主元素4，经交换得：23123123 3 +4=1 - +2223.xxxxxxxx ，：323213214x +3x =1 - + 2223xxxxxx 3221214x+ 3x =177 + 4415 -222xxxx 经Gauss消元得四川大学水利水电学院2131=-37612xxx 第二步：消元法进行了1步后，选出前两行的主元素2，经交换得：3212124+ 3 =115 2 - 2277 -44xxxxxx 经Gauss消元得321224+ 3 = 115 2 - 2231 -22xxxxx 回代求解得：四川大学水利水电学

8、院第一步：选出第一列的主元素2，经交换得：23123123 3 +4=1 - +2223.xxxxxxxx ，12312323223 - +2 3 +4=1.xxxxxxxx ，经Gauss消元得12322322331 - 22 3 +4=1xxxxxx 四川大学水利水电学院第二步：选出第二列的主元素3，经交换得：123232223 3 +4=131 - 22xxxxxx 经Gauss消元得123233223 3 +4=1 21xxxxxx 321121=-376xxx 回代求解得：结果相同！结果相同！四川大学水利水电学院：矩阵A的元素 ，经过Gauss消去法1步后，A变为110a 11120

9、TarA证明若A 对称，A2也对称.证明：11121211.nijnnnaaaaAaaaGuass消元法第一步11121.0.0.nijnnaaaaa(2,)i jn四川大学水利水电学院1111;ijijijaaaaa1111.jijijiaaaaa即 故A2也是对称矩阵.已知A为对称矩阵, 故 1111=,=,=.ijjiiijjaaaaaa1111ijjiijijaaaaaa因此：211.ijnnAa 其中：221111.TijjinnnnAaaA 得证.四川大学水利水电学院矩阵三角分解法：对对矩阵进行一次初等变换，相当于用相应的初等矩阵去左矩阵进行一次初等变换，相当于用相应的初等矩阵去左

10、乘原来的矩阵。从这个观点来考察乘原来的矩阵。从这个观点来考察Gauss消去法，用矩阵乘法表消去法，用矩阵乘法表示，即可得到求解线性方程组的另一种直接法：矩阵的三角分解。示，即可得到求解线性方程组的另一种直接法：矩阵的三角分解。矩阵分解：矩阵分解：ALU四川大学水利水电学院1112111121212222212(1)(1)(1)(1)(1)(1)(1)(1)(1)(22131(1)(1)(1)1.1.101.00.1.nnnnnnnnaaaaaaaaaalllaaa2)(2)(2)(2)2.nnnnaaa1L(1)A(2)A(1)11(1)11,2,3, ,iialina第一步为：第一步为：LU

11、分解法四川大学水利水电学院第第k步为：步为：相当于左乘矩阵相当于左乘矩阵Lk( )( )( )( )1( )11,1, .11kkikkikkkkkkkknkaLliknlal( )( )kikkkkaa1, ,ikn 第第k行行第第i i行，行，四川大学水利水电学院(1)(1)(1)(1)1112131(2)(2)(2)22232(3)(3)1221333( ).0.00.000.nnnnnnnnaaaaaaaLLL L AUaaa总体有：总体有：21211111110010010100101nnllLLll易证：易证：四川大学水利水电学院1111112211221(.).nnnnALLL

12、LUL LLLU其中其中L为单位下三角阵，为单位下三角阵，U为上三角阵。为上三角阵。所以有：所以有：21313212,1111,.1nnn nlllULUlll四川大学水利水电学院().LybL UxbUxy注：分解理论由注：分解理论由Gauss消去法得出，因此能够进行分解的条件与消去法得出，因此能够进行分解的条件与Gauss消去法结果一样。消去法结果一样。* *（实际使用时也需要选主元，即列主元素三角分解法）（实际使用时也需要选主元，即列主元素三角分解法）由此，解线性方程组由此，解线性方程组Ax=b等价于解两个三角形方程组：等价于解两个三角形方程组：关键在于关键在于四川大学水利水电学院： A

13、的所有顺序主子式均不为零，则的所有顺序主子式均不为零，则A存在唯一的分解式存在唯一的分解式A=LU.(),ijnnAa11(1,2,., )kikirrkrikkkal ulikknu11(,1,., )kkjkjkrrjrual ujk kn：对非奇异矩阵：对非奇异矩阵A，存在排列阵，存在排列阵P，以及元素值全不，以及元素值全不大于大于1的单位下三角阵的单位下三角阵L和上三角阵和上三角阵U，使，使.PALU四川大学水利水电学院平方根法：设：设A为对称正定矩阵，则存在唯一分解为对称正定矩阵，则存在唯一分解 其中其中L为为 单位下三角阵，单位下三角阵，D D为对角阵且对角元全大于为对角阵且对角元

14、全大于0.0.,TALDL1/21/21/21/2()()TTTALDLLDDLLDLD：n n阶矩阵阶矩阵A A对称正定时，则有如下分解：对称正定时，则有如下分解： 则则A存在唯一分解存在唯一分解( (即平方根分解即平方根分解) )：其中其中G为下三角阵，规定为下三角阵，规定G的对角元的对角元全为正时，分解式是唯一的全为正时，分解式是唯一的. .TAGG四川大学水利水电学院12111,1(),(1, ).kkkkkkjjjkjkjkijiikkgaggag gkjng ：若线性代数方程组：若线性代数方程组 的系数矩阵的系数矩阵A A对称正定，则用平方对称正定，则用平方根法进行求解是稳定的根法

15、进行求解是稳定的. .（证明过程详见（证明过程详见P172P172）Axb：平方根法约需：平方根法约需 次乘法，大约为直接次乘法，大约为直接LU分解计算量的一半分解计算量的一半. .6/3n四川大学水利水电学院111)0(1,2,. )2) | |, (2,3,.,1),3) | |, | |,iiiinncinbacinbcba，定理：定理：A为三对角矩阵，且满足为三对角矩阵，且满足 则则A非奇异，且追赶法可实现。非奇异，且追赶法可实现。三对角方程组的三对角方程组的四川大学水利水电学院1111,(2,3,., ).,iiiiiiiqbapinqqbpc如果如果A存在存在LU分解，则有：分解，

16、则有：1111222222311111111,1nnnnnnnnnbcqcabcpqcpabcqcabpq其中其中四川大学水利水电学院111,(2,.,).,iiiiyfinyfp y.LUyfxy则：求解则：求解Ax=f11222333111,1nnnyfpyfpyfpyf 四川大学水利水电学院1,.,(1,.,1).nnniiiiiyxqyc xxinq111122221111,nnnnnnnqcxyqcxyqcxyqxy 再由再由解得解得以上称为解三对角方程组的追赶法。以上称为解三对角方程组的追赶法。四川大学水利水电学院典型题目1、利用LU方法、平方根法或追赶法对矩阵进行求解； 2、判断

17、LU分解是否存在且唯一.：判断下述矩阵的LU分解是否存在？若存在，是否唯一？1123241467A2111222331A3126251561546A( )0iiia已知(1,2,3.1)in0iD A有唯一的LU分解（LU存在且唯一）可从这两方面对问题进行考虑四川大学水利水电学院？1123241467A2111222331A3126251561546A以从判断矩阵的顺序主子式为例0iD 对于A1 212024D 所以不存在LU分解对于A2 211022D 所以不存在LU分解对于A2 212125D 31262515161546D 所以存在唯一的LU分解四川大学水利水电学院范数、条件数 为了研究

18、线性方程组近似解的误差估计和迭代法的收敛性，我们需要对 (n维向量空间)中的向量或 中矩阵的“大小”引入一种度量向量和矩阵的范数。n nRnR向量范数向量范数 ：如果向量 的某个满足条件：nxR( )N xx0,x 1）正定性： 当且仅当x=0时0;x ,;xxR2）齐次性：.xyxy3）三角不等式：nR则称N(x)是 上的一个向量范数.四川大学水利水电学院1maxiinxx 常用的几种范数：向量的2-范数：12221()niixx11niixx向量的1-范数：向量的 -范数：绝对值之和模最大值四川大学水利水电学院| | | | | ,.nstsm xxM xxR ：对 上定义的任意两种范数

19、必存在两正常数m，M，使得：nR| | ,| | ,st( )*limkkxx：设 中一向量序列( )(1,2,.),kxk nR其中( )( )( )( )12,., .kkkkTnxxxx若满足*12(,.,)TnnxxxxR*lim,(1,2,., )kjjkxxjn则称向量序列 (依分量)收敛到 ，记作：( )kx*x( )*lim | 0.kkxx( )limkkxx：（PS： 必须为向量任一范数.）| | 四川大学水利水电学院矩阵范数矩阵范数 ：如果矩阵 的某个满足条件：n nAR( )N AA0,A 1）正定性： 当且仅当x=0时0A ,;xxR2）齐次性：ABAB3）三角不等式

20、：nR则称N(A)是 上的一个矩阵范数.4）相容性：A BAB,;n nA BR,.n nA BR,;n nAR四川大学水利水电学院： 算子范数：0max,1sssxsAxAIx且常见的矩阵范数：max2(),TAA A谱范数111maxnijj niAa 列范数11maxniji njAa 行范数12211() .nnijFijAaF-范数算子范数四川大学水利水电学院( )limkkAA：设 中一矩阵序列 ( )(1,2,.),kAk n nR其中( )( )( )( )12,.,.kkkknAAAA若( )lim,( ,1,2,., ),kijijkaai jn则称矩阵序列 收敛到矩阵 ，

21、记作：( )kAA( )lim | 0.kkAA：( )limkkAAPS：必须为任一种矩阵范数.：设 为矩阵A的特征值，称 为矩阵A的。(1 2, )i i, ,n1( )max|ii nS A 谱半径和范数的关系：( ).S AA四川大学水利水电学院：设任意n阶矩阵F满足 ，则 非奇异，且：1F IF11.1IFF： lim01.kkAS A1( ).cond AAA（ 非奇异 ）：n nAR矩阵条件数的：1) cond( )1;A 2)cond()cond( );AA为任意非0常数。13)=1,cond( );AAA若 则4）若A是正交矩阵，则A的谱条件数等于1（相应的谱范数也为1），为最小值.四川大学水利水电学院典型题目1、范数的证明与判断(较难)，求常见范数(易)； 2、