资源描述
第二章解线性方程组的直接法华长生制作1第二章 解线性方程组的华长生制作1线性方程组线性方程组 稠密和稀疏稠密和稀疏（按系数矩阵含零元多少分）高阶和低阶高阶和低阶（按阶数的高低分）对称正定、三对角占优等对称正定、三对角占优等（按系数矩阵的形 状性质分）基基 本本 解解 法法 直接法直接法（通过有限步计算得到精确解精确解，适用于低阶线性 方程组，第二章内容）迭代法迭代法（通过逐次迭代逼近得到近似解近似解，适用于大型线 性方程组和非线性方程，第六章内容）2.12.1直接法与三角形方程直接法与三角形方程组求解求解线性方程组及方法分类线性方程组稠密和稀疏（按系数矩阵含零元多少分）基 本 解（2.1）求解线性方程组：求解线性方程组：AX=b AX=b 根据根据Cramer(克莱姆克莱姆)法则法则,若若 则方程组则方程组 有唯一解有唯一解。（2.1）求解线性方程组：AX=b 根据Cramer三角形线性方程组解法三角形线性方程组解法（2.3）上三角形上三角形三角形线性方程组解法（2.3）上三角形2.22.2高斯消去法高斯消去法Gaussian Elimination高斯消去法高斯消去法消元消元回代回代化上三角方程组的过程思思路路首先将首先将A化为上三角阵化为上三角阵 ，再回代求解，再回代求解=自下而上解上三角形方程组的过程2.2 高斯消去法Gaussian Eliminatio 经过经过n-1次次以上求解线性方程组的方法称为以上求解线性方程组的方法称为高斯高斯(Gauss)消去法消去法利用利用同 解假设假设 ，对增广矩阵作，对增广矩阵作行初等变换行初等变换:执行行过程程上三角阵通过解通过解 得原方程组得原方程组 的解。的解。1.不改变行列式的值2.不改变未知量次序 经过n-1次以上求解线性方程组的方法称为高斯(Gauss 设设 ，计算因子，计算因子将增广矩阵将增广矩阵 第第i 行行 mi1 第第1 1行行，得到：，得到：其中其中记记消元消元过程程行乘数Step 1：设 ，计算因子将增广矩阵 第i 行 mi1设设 ，计算因子，计算因子Step k：其中其中行乘数将增广矩阵将增广矩阵 第第i 行行 mik 第第k行行，得到：，得到：设 ，计算因子Step k：其中行乘数将增广矩阵共进行共进行？步步n 1?以上消元过程均假定以上消元过程均假定注注:如果如果 怎么办怎么办 共进行？步n 1?以上消元过程均假定注:如果 由于由于 ，则，则 A 的第一列中至少有一元素的第一列中至少有一元素不为零。不为零。如果如果 ，则将，则将 的第的第1行与第行与第 行交换后再行交换后再消元，得消元，得假设例：例：当当 时，采取类似的处理措施。时，采取类似的处理措施。由于 ，则 A 的第回代回代过程程由于由于 ，所，所以以即得线性方程组即得线性方程组 Ax=b 解：解：因此，上三角形方程组因此，上三角形方程组 有唯一解。有唯一解。回代过程由于 ，所以即得线性方No unique solution exists.Then we must find the integer k i with ,and interchange the k-th row with the i-th row.No unique solution exists.注注注注:事事实实上上,只只要要 A 非非奇奇异异,即即 A 1 存存在在,则则可可通通过过逐逐次次消消元及行交换元及行交换,将方程组化为三角形方程组将方程组化为三角形方程组,求出唯一解。求出唯一解。定理定理定理定理 若若A的所有的所有顺序主子式顺序主子式 均不为均不为0，则高斯消元无需，则高斯消元无需换行即可进行到底，得到唯一解。换行即可进行到底，得到唯一解。What if?What if?What if we cant find such k?No unique solution exists.Then 由由于于计计算算机机中中乘乘除除运运算算的的时时间间远远远远超超过过加加减减运运算算的的时时间间，故故估估计计某某种种算算法法的的运运算算量量时时，往往往往只只估估计计 乘乘除除次次数数，而而且且通通常常以以乘乘除除次次数数的的 最高次幂最高次幂 为运算量的为运算量的 数量级数量级。(n k)次次Step k：设设 ，计算因子，计算因子 且计算且计算共进行共进行 n 1 步步(n k)2 次次(n k)(n k+2)次次消元乘除次数：消元乘除次数：1 次次(n i+1)次次回代乘除次数：回代乘除次数：GaussGauss消去法的运算量消去法的运算量(n k)次次 由于计算机中乘除运算的时间远远超过加减运算的时间，故n-1 步回代过程需作乘除运算总次数为：步回代过程需作乘除运算总次数为：Gauss消去法的乘除运算总次数为消去法的乘除运算总次数为：完成完成 n-1 步消元需作乘除运算总次数为：步消元需作乘除运算总次数为：n-1 步回代过程需作乘除运算总次数为：Gauss消去法的乘例如例如而如果用而如果用 Cramer 法则法则的乘除法运算次数约为：的乘除法运算次数约为：当当 n 很大时，很大时，当当 n=20 时，时，Gauss 消去法消去法乘除法约为乘除法约为 2700 次次例如而如果用 Cramer 法则的乘除法运算次数约为：当 nGauss 消去法算法消去法算法设计1、输入：矩阵阶数输入：矩阵阶数 n，增广矩阵增广矩阵 A(n,n+1)2、对于对于3、回代计算：回代计算：(2)(2)消元：消元：(1)(1)如果如果 ，找非零元，找非零元 ，交换第，交换第 k 行和第行和第 i 行，行，若不存在非零元，算法停止若不存在非零元，算法停止(1)(1)若若 ，算法停止，算法停止(2)(2)回代：回代：Gauss 消去法算法设计1、输入：矩阵阶数 n，增广矩阵 例例1.用用Gauss消去法解线性方程组消去法解线性方程组(用用3 位十进制浮位十进制浮点数计算）点数计算）解解:本方程组的精度较高的解为本方程组的精度较高的解为用用Gauss消去法求解（用消去法求解（用3位十进制浮点数计算）位十进制浮点数计算）2.32.3高斯列主元素消去法高斯列主元素消去法例1.用Gauss消去法解线性方程组(用3 位十进制浮解:本-9999回代后得到回代后得到与精确解相比与精确解相比,该结果很差！该结果很差！主元-9998在求行乘数时用了很小的数在求行乘数时用了很小的数0.0001作除数。作除数。原因原因:-9999回代后得到与精确解相比,该结果很差！主元-999如果在求解时将如果在求解时将1,2行交换行交换,即即0.9999回代后得到回代后得到0.9998与与 很接近！很接近！如果在求解时将1,2行交换,即0.9999回代后得到0.9例例2.解线性方程组解线性方程组(用用8位十进制尾数的浮点数计算位十进制尾数的浮点数计算)解解:此方程组同例此方程组同例1,若用若用Gauss消去法计算会有小数消去法计算会有小数作除数的现象作除数的现象,若采用换行的技巧，则可避免若采用换行的技巧，则可避免。例2.解线性方程组(用8位十进制尾数的浮点数计算)解:此方回代后可得回代后可得:绝对值最大不需换行回代后可得:绝对值最大事实上事实上,方程组的准确解为方程组的准确解为:上述方法是在上述方法是在GaussGauss消去法的基础上消去法的基础上,利用换行避免利用换行避免小主元作除数小主元作除数,该方法称为该方法称为 GaussGauss列主元消去法列主元消去法事实上,方程组的准确解为:上述方法是在Gauss消去法的基4、对于对于 回代回代列列主主元元消消去去法法算算法法设计1、输入：输入：方程组维数方程组维数 n，矩阵矩阵A，右端项，右端项 b 和控制精度和控制精度 eps2、对于对于(1)选主元选主元(2)如果如果 ，停止运算，停止运算 控制小主元控制小主元(3)如果如果 uk,转转(4)，否则执，否则执行行 换行换行3、如果如果 ，则停止，则停止 无解无解5、输出解输出解计算行乘数公式(2.1)公式(2.2)(4)消元消元4、对于 回代列1、输入：方程组维数 n，矩阵A，右端项 开始输出无解信息消元换行停机回代求解三、Gauss列主元消去法的算法设计(一)流程图开始输出无解信息消元换行停机回代求解三、Gauss列主元消去(二)自然语言选主元(二)自然语言选主元换行消元换行消元回代回代上述过程中的储存空间需要:注意:储存空间需要较大上述过程中的储存空间需要:注意:储存空间需要较大(三)自然语言的改进选主元n输入方程组的维数.1EPS控制条件转移精度1,2,1,2,1,),(+=njniabAijLL的元素增广矩阵1:n-1.2=k对于PkkA),(1.2k:ni2.2=对于|),(|PkiA如果,),(0则IiPkiA.7,|3.2则转到如果EPSP(三)自然语言的改进选主元n输入方程组的维数.1EPS控制换行消元)(),(/)1,(.4nxnnAnnA+0=S换行消元)(),(/)1,(.4nxnnAnnA+0=S回代停机.8输出无解信息.7.),(,),2(),1(.6并转8输出解nxxxxTL=)(),(/kxkkASSSnkA-+)1,(SjxjkAS+)(*),(nkj,1L+=对于注意：为提高算法效率，下列矩阵和向量共用了相同的存储空间：回代停机.8输出无解信息.7.),(,),2(),1(.
展开阅读全文