下载文档原格式
求解线性方程组的直接解法5.2LU分解① Gauss消去法实现了LU分解顺序消元结束时的上三角矩阵U和所用的乘数,严格下三角矩阵。
将下三角矩阵的对角元改成1,记为L,则有A=LU,这事实是一般的,我们不难从消去的第k个元素时的矩阵k行及k列元素的历史得到这一点.因为从消元的历史有u kj=a kj-m k1u1j- m k2u2j -…- m k,k-1u k-1,j, j=k,k+1,…,nm ik=(a ik-m i1u1k- m i2u2k -…-m i,k-1u k-1,k>/u kk i=k+1,k+2,…,n于是a kj=m k1u1j+m k2u2j+…+m k,k-1u k-1,j+u kj, j=k,k+1,…,na ik=m i1u1k+m i2u2k+…+m i,k-1u k-1,k+m ik u kk i=k+1,k+2,…,n从前面两个式子我们可以直接计算L和U(见下段>.将矩阵分解为单位下三角矩阵和上三角矩阵之积称为矩阵的LU分解.顺序消元实现了LU分解,同时还求出了g, Lg=b的解.②直接LU分解上段我们得到(l ij=m ij>u kj=a kj-l k1u1j-l k2u2j -…- l k,k-1u k-1,j, j=k,k+1,…,nl ik=(a ik-l i1u1k-l i2u2k -…-l i,k-1u k-1,k>/u kk i=k+1,k+2,…,n2诸元素对应乘积,只不过算L的元素时还要除以同列对角元.这一规律很容易记住.可写成算法(L和U可存放于A>:for k=1:n-1for j=k:nu kj=a kj-l k1u1j-l k2u2j -…- l k,k-1u k-1,jendfor i=k+1:nl ik=(a ik-l i1u1k-l i2u2k -…-l i,k-1u k-1,k>/u kkendend这一算法也叫Gauss消去法的紧凑格式,可一次算得L,U的元素,不需逐步计算存储.考察上面的表格会发现还可安排其它计算次序,只要在这一次序下每个元素左边的L的元素与上方的U的元素已计算在先。
数值分析第三章线性方程组解法在数值分析中，线性方程组解法是一个重要的主题。
线性方程组是由一组线性方程组成的方程组，其中未知数的次数只为一次。
线性方程组的解法包括直接解法和迭代解法两种方法。
一、直接解法1.1矩阵消元法矩阵消元法是求解线性方程组的一种常用方法。
这种方法将方程组转化为上三角矩阵，然后通过回代求解得到方程组的解。
1.2LU分解法LU分解法是将系数矩阵A分解为一个下三角矩阵L和一个上三角矩阵U的乘积，然后通过解两个三角方程组求解线性方程组。
这种方法可以减少计算量，提高计算效率。
1.3 Cholesky分解法Cholesky分解法是对称正定矩阵进行分解的一种方法。
它将系数矩阵A分解为一个下三角矩阵L和它的转置的乘积，然后通过解两个三角方程组求解线性方程组。
Cholesky分解法适用于对称正定矩阵的求解，具有较高的精度和稳定性。
二、迭代解法2.1 Jacobi迭代法Jacobi迭代法是一种迭代求解线性方程组的方法。
它通过分解系数矩阵A为一个对角矩阵D和一个余项矩阵R，然后通过迭代更新未知数的值，直至达到一定精度要求为止。
Jacobi迭代法简单易懂，容易实现，但收敛速度较慢。
2.2 Gauss-Seidel迭代法Gauss-Seidel迭代法是一种改进的Jacobi迭代法。
它通过使用新计算出的未知数值代替旧的未知数值，达到加快收敛速度的目的。
Gauss-Seidel迭代法是一种逐步逼近法，每次更新的未知数值都会被用于下一次的计算，因此收敛速度较快。
2.3SOR迭代法SOR迭代法是一种相对于Jacobi和Gauss-Seidel迭代法更加快速的方法。
它引入了一个松弛因子，可以根据迭代的结果动态地调整未知数的值。
SOR迭代法在理论上可以收敛到线性方程组的解，而且收敛速度相对较快。
三、总结线性方程组解法是数值分析中的一个重要内容。
直接解法包括矩阵消元法、LU分解法和Cholesky分解法，可以得到线性方程组的精确解。
数值分析小论文线性方程组的直接解法线性方程组的直接解法是指通过一系列的代数运算直接求解线性方程组的解。
线性方程组是数值分析中非常重要的问题，广泛应用于工程、科学、计算机图形学等领域。
在线性方程组的直接解法中，最常用的方法是高斯消元法，它是一种基于矩阵变换的方法。
高斯消元法将线性方程组表示为增广矩阵，并通过一系列的行变换将增广矩阵转化为行阶梯形矩阵，从而得到方程组的解。
高斯消元法的主要步骤包括消元、回代和得到方程组的解。
消元是高斯消元法的第一步，通过一系列的行变换将增广矩阵的元素转化为上三角形式。
在消元过程中，我们首先找到主元素，即矩阵的对角线元素，然后将其它行的元素通过消元操作转化为0，从而使得矩阵逐步变成上三角形矩阵。
回代是高斯消元法的第二步，通过一系列的回代操作求解线性方程组。
回代操作是从上三角形矩阵的最后一行开始，通过依次求解每个未知数的值，最终得到方程组的解。
高斯消元法的优点是算法简单易于实现，可以在有限的步骤内求解线性方程组，适用于一般的线性方程组问题。
但是高斯消元法也存在一些问题，例如当矩阵的主元素为0时，无法进行消元操作，此时需要通过行交换操作来避免这种情况。
另外，高斯消元法对病态矩阵的求解效果较差，容易引起舍入误差累积，导致解的精度下降。
在实际应用中，为了提高求解线性方程组的效率和精度，人们常常使用一些改进的直接解法，例如列主元高斯消元法和LU分解法。
列主元高斯消元法通过选择最大主元来避免主元为0的情况，进一步提高了求解线性方程组的精度。
LU分解法将矩阵表示为两个矩阵的乘积，从而将线性方程组的求解问题转化为两个三角形矩阵的求解问题，提高了求解效率。
综上所述，线性方程组的直接解法是一种基于矩阵变换的方法，通过一系列的代数运算求解线性方程组的解。
高斯消元法是最常用的直接解法之一，它简单易于实现，适用于一般的线性方程组问题。
在实际应用中，可以通过改进的直接解法来进一步提高求解效率和精度。
线性方程组的直接解法程序设计一、高斯消元法高斯消元法是解线性方程组最常用的方法之一、它通过消元和回代的方式，将线性方程组转化为上三角形式，进而求解未知数的值。
程序设计步骤如下：1.读入线性方程组的系数矩阵A和常数向量b；2.进行初等行变换，将系数矩阵A转化为上三角矩阵U，并同时对常数向量b进行相应的变换；3.判断是否有唯一解，如果主对角线上存在零元素，则方程组无解；如果主对角线上所有元素都非零，则方程组有唯一解；4.进行回代计算，求解未知数的值。
高斯消元法的优点是简单直观，容易理解和实现。
但是在一些情况下，会出现主对角线上有零元素的情况，此时需要进行行交换，增加了额外的计算量。
二、LU分解法LU分解法是另一种常用的线性方程组直接解法。
它将系数矩阵A分解为下三角矩阵L和上三角矩阵U的乘积，即A=LU。
程序设计步骤如下：1.读入线性方程组的系数矩阵A和常数向量b；2.进行LU分解，找到下三角矩阵L和上三角矩阵U；3.解第一个方程Ly=b，先求解向前替代方程，计算出y的值；4.解第二个方程Ux=y，再求解向后替代方程，计算出x的值。
LU分解法的优点是可以在多次需要解线性方程组的情况下重复使用LU分解的结果，提高计算效率。
但是LU分解法需要找到L和U的值，增加了额外的计算量。
三、数学实验在进行数学实验时，需要注意以下几点：1.线性方程组的系数矩阵应该是满秩的，以保证方程组有唯一解；2.对于大规模的线性方程组，可以使用稀疏矩阵存储和计算，减少内存和计算时间的消耗；3.在求解过程中，需要判断方程组是否有解，并且考虑特殊情况的处理；4.通过数学实验可以验证直接解法的正确性和有效性，分析计算结果的误差和稳定性。
综上所述，线性方程组的直接解法程序设计在计算方法和数学实验中都是重要的研究内容。
高斯消元法和LU分解法是常用的直接解法，通过编写程序并进行数学实验，可以深入理解和应用这些方法。
这些方法的有效性和稳定性对于解决实际问题具有重要意义。
线性方程组的直接解法
线性方程组（linear equation system）是一类几何问题，也是解决线性系统和代数问题的重要方法，线性方程组由多个联立方程组成，这些方程中也可能含有未知量。
直接解法是把数学模型转换为数值模型，并给出实现其解题步骤的算法，它不同于间接求解的方法，既不做任何假设，也不处理不确定性问题，只是简单地直接求解线性方程组。
解线性方程组的直接解法主要分为三种，分别是高斯消元法、列主元消去法和列坐标变换法。
高斯消元法是一种比较常用的方法，主要是把线性方程组的未知量从左到右一步步求出来，其中用到的主要技术是把矩阵中部分元素消去为零，以便求解不定线性方程组的未知量。
而列主元消去法则是以一列为主元，去消除其他联立方程中出现的此列中的变量，从而最终求出其他未知变量的值。
最后，列坐标变换法是将线性方程组转换为一个更有利于求解的矩阵，其中未知量可以直接求得解答。
除了这三种常见方法外，还有一些更特殊的直接解法，比如要解常微分方程的未知函数，可以用拉格朗日方法和分部积分方法，再比如求解雅各比方程的根，可以通过主副方程互解求解，这种方法也叫作特征根法。
综上，解线性方程组的直接解法有高斯消元法、列主元消去法、列坐标变换法等；特殊问题可以采用拉格朗日方法、分部积
分法和特征根法等。
每种方法都有自己的优势，因此在使用时，可以根据问题的特点，选择适合的方法来解决。
第三章 解线性方程组的直接法3.1 引言许多科学技术问题要归结为解含有多个未知量x 1, x 2, …, x n 的线性方程组。
例如，用最小二乘法求实验数据的曲线拟合问题，三次样条函数问题，解非线性方程组的问题，用差分法或有限元法解常微分方程、偏微分方程的边值等，最后都归结为求解线性代数方程组。
关于线性方程组的数值解法一般有两类：直接法和迭代法。
1. 直接法直接法就是经过有限步算术运算，可求得线性方程组精确解的方法（假设计算过程中没有舍 入误差）。
但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解。
本章将阐述这类算法中最基本的高斯消去法及其某些变形。
2. 迭代法迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法，迭代法需要的计算机存储 单元少、程序设计简单、原始系数矩阵在计算过程中不变，这些都是迭代法的优点；但是存在收敛性和收敛速度的问题。
迭代法适用于解大型的稀疏矩阵方程组。
为了讨论线性方程组的数值解法，需要复习一些基本的矩阵代数知识。
3.1.1 向量和矩阵 用nm ⨯R表示全部n m ⨯实矩阵的向量空间，nm C⨯表示全部n m ⨯复矩阵的向量空间。
()⎪⎪⎪⎪⎪⎭⎫⎝⎛==⇔∈⨯nn n n n n ij nm a a aa a aa a a a212222111211A R A 此实数排成的矩形表，称为m 行n 列矩阵。
⎪⎪⎪⎪⎪⎭⎫⎝⎛=⇔∈n n x x x 21x R x x 称为n 维列向量矩阵A 也可以写成)(n 21a ,,a ,a A = 其中 a i 为A 的第i 列。
同理⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=T T T n 21b b b A其中T i b 为A 的第i 行。
矩阵的基本运算：（1） 矩阵加法 )( ,n m n m R C ,R B ,R A B A C ⨯⨯⨯∈∈∈+=+=n m ij ij ij b a c . （2） 矩阵与标量的乘法 ij j a ci αα== ,A C （3） 矩阵与矩阵乘法 p nk kjik b acij ⨯⨯⨯=∈∈∈==∑m p n n m R C ,R B ,R A AB C ( ,1（4） 转置矩阵 ji ij T nm a c ==∈⨯ , ,A C RA（5） 单位矩阵 ()n n ⨯∈=R e ,,e ,e I n 21 ，其中 ()Tk e 0,0,1,0,0 = k=1,2,…,n（6） 非奇异矩阵 设nn ⨯∈RA ，nn ⨯∈RB 。
线性方程组求解的直接法5.2线性方程组直接解法概述直接解法就是利用一系列公式进行有限步计算，直接得到方程组的精确解的方法．当然，实际计算结果仍有误差，譬如舍入误差，而且舍入误差的积累有时甚至会严重影响解的精度．这是一个众所周知的古老方法，但用在计算机上仍然十分有效．求解线性方程组最基本的一种直接法是消去法．消去法的基本思想是，通过将一个方程乘以或除以某个常数，以及将两个方程相加减这两种手段，逐步减少方程中的变元的数目，最终使每个方程仅含一个变元，从而得出所求的解．高斯（Gauss ）消去法是其中广泛应用的方法，其求解过程分为消元过程和回代过程两个环节．消元过程将所给的方程组加工成上三角方程组，所归结的方程组再通过回代过程得出它的解．Gauss 消去法由于添加了回代的过程，算法结构稍复杂，但这种改进的算法明显减少了计算量．直接法比较适用于中小型方程组．对高阶方程组，即使系数矩阵是稀疏的，但在运算中很难保持稀疏性，因而有存储量大，程序复杂等不足．5.3直接解法5.3.1Gauss 消去法Gauss 消去法是一个古老的求解线性方程组的方法，由它改进而来的选主元法是目前计算机上常用的有效的求解低阶稠密矩阵线性方程组的方法．例5.1用Gauss 消去法解方程组1231231232221(5.3.1)1324 (5.3.2)2539(5.3.3)2x x x x x x x x x ⎧++=⎪⎪++=⎨⎪++=⎪⎩解〖JP4〗第1步，式35.3.12⨯-（）（）加到式(5.3.2)上，式()15.3.1()2⨯-加到式(5.3.3)上，得到等价方程组123232322211(5.4.4)282(5.4.5)x x x x x x x ⎧++=⎪⎪-+=-⎨⎪⎪+=⎩第2步，式()2⨯5.3.4加到式(5.3.5)上得等价的方程组12323322211100(5.3.6)x x x x x x ++=⎧⎪-+=-⎨⎪=⎩第3步，回代法求解方程组(5.3.6)，即可求得该方程组的解为32110,1,.2x x x ===-.用矩阵描述其约化过程即为233(2)22221011100100r r r ⨯+⇒⎡⎤⎢⎥--⎢⎥⎢⎥⎣⎦→[]122133(1)3()21()222212221,3241/201111395/20282r r r r r r A b ⨯-+⇒⨯-+⇒⎡⎤⎡⎤⎢⎥⎢⎥=--⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦→.这种求解过程称为具有回代的Gauss 消去法．由此例可见，Gauss 消去法的基本思想是：用矩阵的初等行变换将系数矩阵A 化为具有简单形式的矩阵（如上三角阵、单位矩阵等），而三角形方程组是很容易回代求解的．一般地，设有n 个未知数的线性方程组为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 +++=⎧⎪+++=⎪⎨⎪⎪++=⎩L L MM M L (5.3.7)1212)(,,)(,,)T T ij n n n n A a X x x x b b b b ⨯===L L （，，，则方程组(5.3.7)化为AX b =.方便起见，记()(1)det 0A AA ==≠，(1)b b =，且()1A的元素记为()()11,ij a b ，的元素记为()1i b ，则消去法的步骤如下：第1步：1110a≠（），，计算(1)11(1)11(2,3,4),i i a m i n a ==L 用()1i m -乘方程组(5.3.7)中的第1个方程加到第i个方程中()2,3,i n =L ，即进行行初等变换()112,3,i i i R m R R i n -⋅→=L ，消去第2个到第n个方程中的未知数1,x ,得等价方程组111121(2)(2)(2)22222(2)(2)(2)2inn n n nn n x a a b x a a b ⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦LMM LM M L (5.3.8)记为(2)(2)A X b =，其中(2)(1)(1)(2)(1)(1)1111(,2,3),2,3,ij ij i j i i i a a m a i j n b b m b i n =-==-=L L ，，第k 步()1,2,1k n =-L：继续上述消元过程．第1步到第1k -步计算已完成，且得到与原方程组等价的方程组(1)(1)(1)(1)1112111(2)(2)(2)222223()()()()()()nn k k k kkkn k n k k k nk nn n a a a b x a a b xx aa b x a a b ⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎢⎥⎢⎥⎣⎦⎣⎦L L LLOM L M MMM L(5.3.9)记为()(()K k A X b =，进行第k 步消元：设()0k kka≠，计算乘数()()(1,)k ikk ik kka m k k n a ==+L ，用ik m -乘方程组(5.3.9)中第k 个方程加到第i 1)i k n =+L （，，，个方程上消去方程组(5.3.9)中第i 1)i k n =+L （，，个方程的未知数k x ，得到与原方程组等价的方程组：(1)()()(1)()()(1)(1)()(,1,)( 1.)k k k ij ij ik kj k k k i i ik k k k k k a a m a i j k n b b m b i k n A A k b b k ++++⎧=-=+⎪=-=+⎨⎪⎩L L （）与前行元素相同，与前个元素相同 (5.3.10) 记为(1)(1)k k A X b ++=其中(1)(1,k k A b ++）中元素计算公式为(1)()()(1)()()(1)(1)()(,1,)( 1.)k k k ij ij ik kj k k k i i ik k k k k k a a m a i j k n b b m b i k n A A k b b k ++++⎧=-=+⎪=-=+⎨⎪⎩L L （）与前行元素相同，与前个元素相同 (5.3.11)重复上述过程，且设()0(1,2,1)k kk a k n ≠=-L ，共完成1n -步消元计算，得到与方程组(5.3.7)等价的三角形方程组1111211(2)(2)(2)22222()()n n n n n nn n x a a b x a b ⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦LMOM M (5.3.12)再用回代法求方程组(5.3.12)的解，计算公式为()()()()1()(),(1,2,1)n n n nn n i i i ij j j i i i ii b x a b a x x i n n a =+⎧=⎪⎪⎨-⎪==--⎪⎩∑L (5.3.13)元素()k kka 称为约化的主元素．将方程组(5.3.7)化为方程组(5.3.12)的过程称为消元过程．方程组(5.3.12)的求解过程(5.3.13)称为回代过程．由消元过程和回代过程求解线性方程组的方法称为Gauss 消去法．定理5.1（Gauss 消去法）设AX b =。
第三章 线性方程组的数值方法在自然科学和工程技术中很多问题的解决常常归结为求解线性代数方程组.⎪⎪⎩⎪⎪⎨⎧=++=++=++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 =⨯-=≈=结果与准确解非常接近.这个例子告诉我们，在采用高斯消元法解方程组时,用做除法的小主元素可能使舍入误差增加，主元素的绝对值越小，则舍入误差影响越大。
线性方程组的直接解法2.1实验目的理解线性方程组计算机解法中的直接解法的求解过程和特点，学习科学计算的方法和简单的编程技术。
2.2程序中Mathematica语句解释1．MatrixForm[a] 以矩阵的形式显示a2．Table[Random[Integer,{xa,xb}],{n}] 产生xa 到xb 之间的n个随机整数的向量3. x=Table[0,{n}] 定义变量x为n维向量4. a=Table[0,{n},{n}] 定义变量a为n n矩阵5. Timing[expr] 给出计算表达式expr所用的计算机时间2.3方法、程序、实验解线性方程组的直接法是用有限次运算求出线性方程组 Ax=b 的解的方法。
线性方程组的直接法主要有Gauss消元法及其变形、LU(如Doolittle、Crout方法等)分解法和一些求解特殊线性方程组的方法（如追赶法、LDLT法等）1. Gauss消元法1) Gauss消元法的构造过程Gauss消元法是一个古老的直接法,由它改进得到的选主元的消元法,是目前计算机上常用于求低阶稠密矩阵方程组的有效方法,它是通过消元将一般线性方程组的求解问题转化为三角方程组的求解问题的。
Gauss消元法的求解过程可分为两个阶段:首先,把原方程组化为上三角形方程组,称之为“消去”过程;然后,用逆次序逐一求出三角方程组(原方程组的等价方程组)的解,并称之为“回代”过程，其“消去”和“回2) Gauss消元法程序Clear[a,b,x];n= Input[“线性方程组阶数n=”]；a=Input["系数矩阵A="]；b=Input["常数项b="]；eps1=0.000000001；t=1；Do[If[Abs[a[[k,k]]]<eps1,Print["Gauss消元失效"];t=0;Break[]]；Do[m=-a[[i,k]]/a[[k,k]];Do[a[[i,j]]=a[[i,j]]+m*a[[k,j]],{j,k+1,n}];b[[i]]=b[[i]]+m*b[[k]],{i,k+1,n}],{k,1,n}];x=Table[0,{n}];If[t==1,x[[n]]=b[[n]]/a[[n,n]];Do[x[[k]]=(b[[k]]-Sum[a[[k,j]]*x[[j]],{j,k+1,n}])/a[[k,k]],{k,n-1,1,-1}]];Print[“Ax=b 的解为 ” , x]说明 本程序用于求线性方程组Ax=b 的解。
第2章线性方程组的直接解法2.1实验目的理解线性方程组计算机解法中的直接解法的求解过程和特点，学习科学计算的方法和简单的编程技术。
2.2概念与结论1. n阶线性方程组如果未知量的个数为 n ,而且关于这些未知量x1,x2, …,x n的幂次都是一次的(线性的)那末, n 个方程a11x1+a12x2+ … +a1n x n=b1┆┆┆ (1)a n1x1+a n2x2+ … +a nn x n=b n构成一个含n个未知量的线性方程组,称为n阶线性方程组。
其中,系数a11,…,a1n,a21, …,a2n, …,a n1, …,a nn 和b1, …,b n都是给定的常数。
方程组(1)也常用矩阵的形式表示,写为Ax=b其中,A是由系数按次序排列构成的一个n阶矩阵,称为方程组的系数矩阵,x和b都是n维向量,b称为方程组的右端向量。
2. n阶线性方程组的解使方程组(1)中每一个方程都成立的一组数x1*,x2*, …,x n*称为式(1)的解,把它记为向量的形式,称为解向量.3.一些特殊的线性方程组1) 上三角方程组2) 三对角方程组⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛-----nnnnnnnnnnnnbbbxxxaaaaaaaaaaaa212111121223221111312114.矩阵的Doolittle 分解5.Doolittle 分解的紧凑格式6．矩阵的Crout 分解⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--n n n n n n d d d x x x b a c b c b a c b a c b21211133322211⎪⎪⎪⎪⎪⎭⎫⎝⎛⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛nn n n n n nn n n n n u u u u u u l l l a a a a a a a a a222112112121212222111211111⎪⎪⎪⎪⎪⎭⎫⎝⎛⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛111211221222111212222111211n n nn n n nn n n n n u u u l l l l l l a a a a a a a a a ⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛nn n n n nn n u l l l u u l l u u u l u u u u3213333231223222111312112.3程序中Mathematica 语句解释1．MatrixForm[a] 以矩阵的形式显示a2．Table[Random[Integer,{xa,xb}],{n}] 产生xa 到xb 之间的n 个随机整数的向量 3. x=Table[0,{n}] 定义变量x 为n 维向量 4. a=Table[0,{n},{n}] 定义变量a 为n ⨯n 矩阵5. Timing[expr] 给出计算表达式expr 所用的计算机时间2.4 方法、程序、实验解线性方程组的直接法是用有限次运算求出线性方程组 Ax=b 的解的方法。
线性方程组的直接法主要有Gauss 消元法及其变形、LU(如Doolittle 、Crout 方法等)分解法和一些求解特殊线性方程组的方法（如追赶法、LDLT 法等）。
这里只给出Gauss 消元法、Doolittle 分解法和追赶法的构造过程及程序。
1. Gauss 消元法1) Gauss 消元法的构造过程Gauss 消元法是一个古老的直接法,由它改进得到的选主元的消元法,是目前计算机上常用于求低阶稠密矩阵方程组的有效方法,它是通过消元将一般线性方程组的求解问题转化为三角方程组的求解问题的。
Gauss 消元法的求解过程可分为两个阶段:首先,把原方程组化为上三角形方程组,称之为“消去”过程;然后,用逆次序逐一求出三角方程组(原方程组的等价方程组)的解,并称之为“回代”过程，其“消去”和“回代” 两个过程如下： 消去过程第一步: 设a 11≠0,取 m i1=-a i1/a 11 , 做(消去第i 个方程组的x 1)操作： m i1⨯第一个方程+第i 个方程 i=2,3,…n则第i 个方程变为第一步消元后的方程组变为)1()1(2)1(1)1(21i n b x a x a x a ini i =+++ iiij ij i i i j i ij ijb b a a b m b b a m a a ==+=+=)0()0()0(11)0()1()0(11)0()1(,,,第二步，考虑后n-1个方程组消除变量x 2 ，以此类推，经过n-1步消元，就得到与第一个线性方程组同解的上三角方程组： 回代过程为求解如上三角方程组，先从最后一个方程解出x n 再依次解出x n-1，x n-2,⋅⋅⋅⋅ , x 1 ，从而求出线性方程组的解。
Gauss 消元法的计算量为 n 3/3+n 2-n/3。
2) Gauss 消元法算法1.输入变量个数n 、系数矩阵A 、常数项b 2 For i=1,2,…,n-12.1 如果|a ii |<eps1,则输出“Gauss 消元失败”提示并终止 2.2 For I=k+1,k+2,n 2.2.1 a ik ⇐ -a ik /a kk2.2.2 a ij ⇐a ij +a ik *a kj ( j=k+1,k+2,…,n)⎪⎪⎩⎪⎪⎨⎧=++=++=+++)1()1(2)1(2)1(2)1(22)1(22)0(1)0(12)0(121)0(11n n nn n n n n n b x a x a b x a x a b x a x a x a nk k j i b m b b a m a a a a m n k k k b a b x a b x a x a b x a x a x a k k ik k i k i k kj ik k ij k ijk kkk ik ik k ik ijn n n n nn n n n n,...,2,1,/1,,3,21,)1()1()()1()1()()1()1()()()1()1()1(2)1(22)1(2211212111++=⎪⎪⎩⎪⎪⎨⎧+=+=-=-=⎪⎪⎭⎪⎪⎬⎫==++=+++-------- ，对计算公式为次消元后的系数，表示第的上标和其中2.2.3 b i ⇐b i +a ik *b k3. x n ⇐ b n /a nn注：如上算法中使用了节省存储单元的技术，其中利用a ik 替代算法中的m ik ，而a ij 替代算法中的a ij (k),k=0,1,2,…,n-1。
3) Gauss 消元法程序Clear[a,b,x];n= Input[“线性方程组阶数n=”]; a=Input["系数矩阵A="]； b=Input["常数项b="]； eps1=0.000000001; t=1;Do[If[Abs[a[[k,k]]]<eps1,Print["Gauss 消元失效"];t=0;Break[]]; Do[m=-a[[i,k]]/a[[k,k]];Do[a[[i,j]]=a[[i,j]]+m*a[[k,j]],{j,k+1,n}]; b[[i]]=b[[i]]+m*b[[k]], {i,k+1,n}], {k,1,n}]; x=Table[0,{n}];If[t==1,x[[n]]=b[[n]]/a[[n,n]];Do[x[[k]]=(b[[k]]-Sum[a[[k,j]]*x[[j]],{j,k+1,n}])/a[[k,k]], {k,n-1,1,-1}]];Print[“Ax=b 的解为 “ , x]∑+=-⇐--=nk j kkj kj k k a x a b x n n k For 1/)(1.41,,2,1.4说明本程序用于求线性方程组Ax=b的解。
程序执行后，先通过键盘输入线性方程组阶数n、系数矩阵A、常数项b，程序即可给出线性方程组Ax=b的解。
如果Gauss消元中出现主对角线元素a ii=0,程序中用|a ii|<eps1表示a ii=0,给出Gauss失效提示。
程序中变量说明a：存放系数矩阵A及用于Gauss消元的中间变量和矩阵x: 存放Ax=b的解b: 存放线性方程组Ax=b的常数项beps1:描述a ii=0的数，程序中用|a ii|<eps1描述a ii=0的数，上程序eps1取为10-8，它是可以自行设置的。
t:临时控制变量4) 例题与实验例1. 用Gauss消元法解如下线性方程组5x1+2x2+x3= -12-x1+4x2+2x3= 202x1-3x2+10x3= 3解：执行Gauss消元法程序后在输入的三个窗口中按提示分别输入:3、{{5, 2, 1}, {-1, 4, 2}, {2, -3, 10}}、{-12, 20, 3}每次输入后用鼠标点击窗口的“OK”按扭，得如下输出结果Ax=b的解为 {-4, 3, 2}此结果说明所求解为 x1=-4，x2=3，x3=2 。
为检验结果的正确性，输入命令：{{5, 2, 1}, {-1, 4, 2}, {2, -3, 10}}.{-4,3,2}得计算结果{-12, 20, 3}，说明计算结果正确。
例2．用Gauss消元法解如下线性方程组10-7x1+2x2+3x3+x4= 03x1+4x2+3x3+2x4= 12x1+3x2+4x3+2x4= -1x 1+2x 2+3x 3+4x 4= 0解：执行Gauss 消元法程序后在输入的三个窗口中按提示分别输入: 4、{{0.0000001,2,3,1},{3,4,3,2},{2,3,4,2},{1,2,3,4}}、{0,1,-1,0}} 每次输入后用鼠标点击窗口的“OK ”按扭，得如下输出结果 Ax=b 的解为 {-0.875, 1.66667, -1.20833, 0.291667}此结果说明所求解为 x 1=-0.875, x 2=1.66667, x 3=-1.20833, x 4=0.291667。
为检验结果的正确性，输入命令：{{0.0000001,2,3,1},{3,4,3,2},{2,3,4,2},{1,2,3,4}}. {-0.875, 1.66667, -1.20833, 0.291667} 得计算结果{-1.11022⨯10-16, 1., -1., 5.30894⨯10-9}显然它与正确的结果{0,1,-1,0}}有误差，只要用0取代其中的 -1.11022⨯10-16和5.30894⨯10-9就可以得到准确解。
本题计算说明用Gauss 消元法求线性方程组的解向量，有时得出的解并不是真正的准确解。
