下载文档原格式
第三章直接法解线性方程组习题3-11. 写出列主元消去算法。
For k =1 to n-1 do1）消元：(1) 选主元：(2) 判别： , than stop(3) 换行： (j=k,k+1,...,n+1)(4) 计算乘数： (i=k+1,...,n)(5) 消元：(i=k+1,...,n; j=k+1,...,n+1) 2) 回代：(1) ,than stop(2) 回代：for k=n,n-1,...,1 do(3) 打印：print x j =a j,n+12. 用全主元高斯—约当消元法求下列方程的解3. 用全主元高斯—约当消去法求下列矩阵的逆矩阵4. 请用列全主元高斯—约当消去法求下列矩阵的逆矩阵6．如果在解方程组过程中，希望顺便求出系数矩阵A的行列式值det(A)，用什么方法比较方便？需注意一些什么问题？如果用高斯—约当列主元消去法，如何求出det(A)?高斯消元法解方程时；主元素高斯消元法解方程时，注意换行列会改变行列式的符号；用高斯—约当列主元消去法解方程时，把列主元 记录下来，把换行的次数m记录下来，。
7. 设A x=b是线性方程组1) 用列元高斯约当消去法，求解此方程组。
2) 求系数矩阵的行列式。
3) 求系数矩阵的逆矩阵。
也是一个指标为k的初等下三角阵，其中I i,j 为排列阵：证明：只是m i,k与m j,k换了个位置。
9．试证明单位下三角阵的逆矩阵仍然是一个单位下三角阵。
证：证得 下三角阵的逆阵仍是下三角阵。
当A为单位下三角阵时， ，B也是单位下三角阵。
习题3-25. 设A为n阶非奇异阵，且有分解式 A=LU，其中L为单位下三角阵，U为上三角阵，求证：A的所有顺序主子式均不为零。
证明：U一定是非奇异阵，否则A=LU也奇异。
记A的顺序主子阵为A k ，L的顺序主子阵为L k ，U的顺序主子阵为U k ，由分块阵的乘法6. 设A对称正定，试证明A一定可以进行以下分解:A=UU T，其中U是上三角阵，若限定U的对角元为正的，此分解唯一。
第三章 解线性方程组的迭代法解线性方程组：10,(,......,)Tn Ax b x x x -== 将方程组变形为1,(,......,)T n x Bx f x x x =+= 的形式 移项法111213112122232231323333a a a x b a a a x b a a a x b ⎡⎤⎛⎫⎛⎫⎪ ⎪⎢⎥=⇒ ⎪ ⎪⎢⎥ ⎪ ⎪⎢⎥⎣⎦⎝⎭⎝⎭131211111111123212222222223331323333333000a a b a a ax x a a b x x a a a x xaa b a a a ⎛⎫⎛⎫ ⎪ ⎪ ⎪ ⎪⎛⎫⎛⎫ ⎪ ⎪ ⎪ ⎪=-+ ⎪ ⎪ ⎪⎪ ⎪ ⎪⎪⎪⎝⎭⎝⎭ ⎪ ⎪⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭很容易推广到n 阶简单迭代法（Jacobi 迭代法）1122(,,......,)nn D diag a a a =迭代：11100()1,2,...k k x B x f B I D A f D b k +--=+=--== 0x ：初值，任意。
分量式：(1)()11()nk k ii ij j j ii j ixb a x a +=≠=-∑ 1,2,...,i n = ,L U 分别表示A 的下三角和上三角部分（不含对角线）。
A=D+L+U10();0()ij n n ij ij ij L l l a i j l i j B D L U ⨯-==>=≤=-+迭代次数的控制：迭代到1*(1)k k k xx x x ε++-<≈ 取(1)()(1)1()1?()k k k k x x x I D A x D b ++---==-- (1)()1()1()()k k k k x x D Ax b D r +---=-=前述()*()()||||k k x x r cond A xb -≤，控制()()*,()k k rx x cond A - 与有关，对病态方程组，可能ε很小而解的精度不高。
第三章 线性方程组的数值方法在自然科学和工程技术中很多问题的解决常常归结为求解线性代数方程组.⎪⎪⎩⎪⎪⎨⎧=++=++=++nnnn 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当它的系数行列式不为零时，由克莱姆法则可以给出方程组的唯一解，但是这一理论上完 善的结果，在实际计算中可以说没有什么用处。
因此如何建立在计算机上可以实现的有效而实用的解法，具有极其重要的意义。
这些方法大致可分为两类：一类是直接法，就是经过有限步算术运算,可求得方程组精确解的方法(如果每步计算都是精确进行的话)；另一类是迭代法，就是用某种极限过程去逐步逼近其精确解的方法.本章将阐述这两类算法中最基本的高斯消元法及其变形、矩阵分解法、雅可比迭代法、高斯 -塞德尔迭代法等.第一节 高斯消元法一 回代过程设系数矩阵为n 阶上三角矩阵的线性方程组(1)2222211212111⎪⎪⎩⎪⎪⎨⎧==+=++nn nn n n n n b x a b x a x a b x a x a x a如果a ,...a ,a nn 2211都(1)自下而上可以逐次求出x ,...x ,x n n 11-为()21211⎪⎪⎩⎪⎪⎨⎧--=∑-==+=,...n ,n k ,a x a b x a b x kk jn k j kj k k nn n n按上述公式求方程组(1) 解的过程称为回代过程.不难看出，解方程组(1)共需()121+n n 次加法和()121-n n 次乘法.这恰好是用一个n 阶三角方阵乘n 维向量所需的运算次数。
当n 较大时,n n >>2，同时加法运算速度远快于乘法的运算速度，所以，可用n 221次乘法来近似表示回代过程的运算量.二 消元过程设有线性方程组()322112222212*********⎪⎪⎩⎪⎪⎨⎧=++=++=++n n 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 为了符号统一，记()()()n ...,j ;n ,...,i b a ,a a i in ij ij2121010====+, 则原方程组改写成()()()()()()()()()()()()()301020*******2022*********10120121011'nnnnn n n n )n nn n a x a x a x a a x a x a x a a x a x a x a ⎪⎪⎩⎪⎪⎨⎧=++=++=+++++如果()0011≠a ，那么就可以保留其中第一个方程并利用它分别与其余方程消去第一个未知量.令()()n,..,,i ,a a l i i 32011011==()4则以l i 1-乘第一个方程加到第i个方程中，就把方程组()3'化为()()()()()()()()()()()51112121121221220110120121011⎪⎪⎩⎪⎪⎨⎧=+=+=+++++a x a x a a x a x a a x a x a x a nn nnn n n nn n n n其中()()()1323201101+==-=n ,...,j ,n ,...,i ,a l a a j i ij ij ()6由方程组(3′)化为(5)的过程中，元素()a 011起着特殊的作用，特把元素()a 011称为主元素.如果方程组(5)中()0122≠a , 则以()a 122为主元素，并利用类似的方法消去第n ,...,43个方程中的第二个未知量，即令()()n ,..,,i ,a a l i i 43122122== ()7则以l i 2-乘以第二个方程加到第i 个方程中,于是得到新的方程组()()()()()()()()()()()()()()()()8212323213233233112123123212201101301320121011⎪⎪⎪⎩⎪⎪⎪⎨⎧=+=++=+++=++++++++a x a x a a x a ....x a a x a x a x a a x a x a x a x a nn n nn n n n n n n n n n n其中()()()13312212+==-=n ,...j ,n ,...i ,a l a a j i ij ij ()9重复上述过程1-n 步后，我们得到原方程组等价的系数矩阵为三角形方阵的方程组()()()()()()()()()()()()()()()10111213233233112123123212201101301320121011⎪⎪⎪⎩⎪⎪⎪⎨⎧==++=+++=++++-+-+++a x a a x a ....x a a x a x a x a a x a x a x a x a n nn n n nn n n n n n n n n n其中()()a a l k kk k ikik 11--= ()11()()()⎪⎩⎪⎨⎧+++=++=-=-=--1212112111n ,...k ,k j ;n ,...k ,k i n ,...,k a l a a k kj ik k ij k ij()12把方程组(3)逐步化为方程组(10)的过程称为消元过程.最后，由回代过程可求得原方程组的解为()()()()()⎪⎪⎩⎪⎪⎨⎧--=∑-==-+=--+--+122111111111,,...n .n k ,a x a a x a a x k kk n k j j k kjk kn k n nnn nn n ()13这种通过消元、再回代的求解方法称为高斯(Gauss)消元法(其特点是始终消去主对角线下方的元素).注意到，上标k 仅仅用来识别一次消元前后系数矩阵的变化，而()a k ij 变为()a k ij 1+后,()a k ij不再使用，所以在计算机存贮中只要用()a k ij1+冲掉()a k ij即可；另一方面，主元素所在列中主元素下面的各元素在消元过程中必然是零，而且在后面将要列出的回代过程中也不用它们，所以没有必要通过计算得到它们，从而在消元过程中j 就可从1+k 开始，这样做还可以节约计算时间.例1 用高斯消元法求解方程组⎪⎩⎪⎨⎧=++=-+=++52213614282321321321x x x x x x x x x解 用第一个方程消去后两个方程中的x 1，得 ⎪⎩⎪⎨⎧-=-=-=++9962214282232321x x x x x x 再用第二个方程消去第三个方程中的x 2，得⎪⎩⎪⎨⎧=-=-=++18962214282332321x x x x x x 最后，经过回代求得方程组的解为52281412262918321323=--==+=-=-=x x x x x x 三 高斯消元法的条件与运算量从消元过程可以看出，对于n 阶线性方程组，只要各步主元素不为零，即()01≠-a k kk ，经过1-n 步消元，就可以得到一个等价的系数矩阵为上三角形阵的方程组，然后再利用回代过程可求得原方程组的解.因此,有下面结论.定理1 如果在消元过程中A 的主元素不为零，即()01≠-a k kk (k=1,2,…,n),则可通过高斯消元法求出b Ax =的解.矩阵A 在什么条件下才能保证()01≠-a k kk ,下面的定理给出了这一条件.引理 在高斯消元过程中系数矩阵A 的主元素不为零，即()01≠-a k kk (k=1,2,…，n)的充要条件是矩阵A 的各阶顺序主子式不为零，即n...,k ,a ...a .........a ...a D a D kkk kk 32001111111=≠=≠=证明 首先利用归纳法证明引理的充分性，显然 ，当1=n 时，引理的充分性是成立的，现假设引理对1-n 时也成立，求证引理对n 也成立，由归纳法假设有()01≠-a k kk , 121-=n ...,k于是可用高斯消元法将A 化为⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛→--------)n (nn)n (n ,n )n (n n)(n )(n )()(n )(n )()(a a a a a a a a a a A 1212111211212201011012011且()()a a D 0110111==()()()()()a a a a a D 1220111220120112==()()()a ...a a a a a a a a a a D n nn)n (nn )(n )(n )()(n )(n )()(n 112201111211212201011012011----=⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛=由假设,n ,...,k ,D k 210=≠所以有()01≠-a n nn .反过来,由上式可知必要性是显然的.定理2 如果n 阶矩阵A 的所有顺序主子式均不为零，即,n ,...,k ,D k 210=≠则可通过高斯消元法求出的解.下面考虑求解(3)的高斯消元法的运算量.消元过程需要除法()()()1211221-=+++-+-n n ...n n次，而需要的乘法和加法的次数都是()()()()131122112-=⋅++-⋅-+-⋅n n ...n n n n加上回代过程的运算次数，共需乘、除法的次数为()()()()133112113112122-+=++-+-n n n n n n n n n加、减法的次数为()()()5326112113122-+=-+-n n n n n n n 当n 较大时,n n 23>>,消元过程的运算量远大于回代过程，从而，高斯消元法中乘除法的次数与加减法的次数近似为n331.第二节 第二节 高斯主元素消元法一 问题的提出由高斯消元法可知，在消元过程中如果出现()01=-a k kk 的情况，这时消元法将无法进行；另一方面，即使主元素()01≠-a k kk ，但很小时，用其作除数，会导致其它元素数量级的严重增长和舍入误差的扩散，最后也使得计算结果很不可靠.例1 例1 解方程组⎩⎨⎧=+=+0000100001000010001200003000302121.x .x ..x .x .(它的精确解为323121==x ,x )解法一 用高斯消元法求解(取5位有效数字)，用第一个方程消去第二个方程中的x 1得⎩⎨⎧-=-=+0666609999000120000300030221.x ..x .x . 因而再回代，得000300666700003000120666799990666612=⨯-=≈--=....x ...x 显然，这个解与精确解相差太远，不能作为方程组的近似解其原因是我们在消元过程中使用了小主元素，使得约化后的方程组中的元素量级大大增长，再经舍入使得计算中舍入误差扩散，因此经消元后得到的三角形方程组就不准确了.为了控制舍入误差，我们采用另一种消元过程. 解法二 为了避免绝对值很小的元素作为主元，先交换两个方程，得到⎩⎨⎧=+=+0001200003000300000100001000012121.x .x ..x .x .消去第二个方程中的x 1，得⎩⎨⎧==+9998199972000010000100001221.x ..x .x .再回代，解得()3333066670000010000166670999729998112....x ...x =⨯-=≈=结果与准确解非常接近.这个例子告诉我们，在采用高斯消元法解方程组时,用做除法的小主元素可能使舍入误差增加，主元素的绝对值越小，则舍入误差影响越大。
