数值计算方法 第3章线性方程组的解法

.第三章线性方程的解，在3.1问题的探讨、自然科学及社会科学研究中，经常需要解线性代数方程，这些方程的系数矩阵大体分为两种。一个是低阶的稠密矩阵(例如，阶小于或等于约150)，另一个是大稀疏矩阵(矩阵阶高，零元素多)。计算机求解线性代数方程的一般数值解法：1，直接法：通过有限算术运算，在计算过程中没有舍入误差的情况下，求出方程精确解的方法。但是，由于舍入误差在实际计算中的存在和影响，该方法只能求线性方程的近似解。该方法是求解低阶高密度矩阵和大型带状方程的有效方法。2，迭代法：一种利用极限过程逐步逼近线性方程精确解的方法。迭代方法的优点是需要计算机的存储单元少，编程简单，原始系数矩阵在计算机中不变，但存在收敛和收敛速度等问题。迭代法是求解大型稀疏矩阵方程的重要方法。注：直接法解n元线性代数方程所需的乘法次数为1，Cramer(克莱姆)法则：(n 1)！n=10时，(n 1)！=39916800次2，高斯移除方法：n=10时约430次，3.2线性方程的直接解，n圆线性方程，缩写，当a设置为非奇异时，方程有自己的解。方程式的矩阵格式，高斯消元法，高斯消元法步骤：(1)首先将增量矩阵A，b作为上三角阵列；(2)使用三角形方程式再次求解。高斯消元法是求解线性代数方程的老方法(公元前250年以前，我国已经掌握了理解三元联立方程的方法)。但是，改进、删除变形的关键元素、三角剖分仍然是计算机中常用的有效方法。使用简单的例子说明消除方法的基本思路。(1)解三角方程后， ，(2)解下一个方程后，按照以下方法处理，从下往上慢慢解，标记x3的值，找出x3，x2的值，求出x1。相应的增广矩阵变化，(-2)r1 r3r3，r2 r3r3，1 .基本思想，删除原始方程，按照未知元素的顺序，换成相应的上三角形，以上用矩阵语言描述的过程是使用基本行转换将扩展矩阵作为向上三角形数组，使用向上三角形方程反向解。2 .根据以下上三角表达式，分别为xk、22、n-1、n-1、定义：使用高斯消元法时，仅转换为方程式的倍数，形成了顺序高斯消元法。求解n元线性方程的序高斯消去法的总乘法数为：顺序高斯剔除方法计算过程中出现的主要元素。出现时，卸载过程不再继续。定理：阶高斯消去法的前n-1父元素非零的充要条件是方程的系数矩阵a的前n-1阶主，在序列高斯消元法的计算过程中，如果将akk(k)称为基本元素，并在步骤k中将其用作消元数，则遇到1，akk (k)=0时，可能会发生以下情况，消除过程不会继续：2，akk(k)0，可以进行消除过程，但如果|akk(k)|太小，则会积累舍入误差，从而降低计算解决方案的精度。顺序高斯消除方法的数值稳定性不能保证！顺序主元素删除方法可能会失败，例如，使用单精度解决方案方程、顺序主元素删除方法8，小主/* smallpivotlelement */。例如，在4位小数限制中，计算顺序高斯剔除求解以下方程式：x=17.46，x2=-45.76，x3=5.546，解释按Gauss删除的顺序解决。卸载过程如下：x3=5.546，x2=100.0，x1=-104.0，与此方程式的精确解法相比较，x3=5.546，x2=-104.0，在此范例中，顺序高斯剔除方法的主要元素绝对值非常小，因此剔除乘数绝对值非常大，计算过程中大量吃掉小数，导致大舍入错误，从而导致计算解决方案x1=-104.0和x2=100.0完全失真。为了避免这种现象，可以使原始方程成为等效变换，然后使用顺序高斯消去法求解。写入原始方程式的增量矩阵：寻找第一栏中绝对值最大的元素，然后等效转换：表示方程式的解，x3=5.546，x2=-45.76，x1=17.46，精确解决方案为x3=5.546，x2=-45.76，x1=17.46。由此可见，第二种高斯剔除方法的精度比顺序高斯剔除方法高得多。热主元素移除方法和序列高斯移除的区别如下：后者是在每个步骤中删除元素之前，先选择主元素，然后按删除元素的自然顺序删除主元素。3.栏主元素高斯移除法，使用高斯移除法定义第k个移除前的第k个延伸阵列A(k)，b(k)，交换的第二列的转换，将绝对值最大的元素变更为(k，k)位置，移除元素此方法称为栏主元素高斯移除法。1 .移除程序为k=1、2、对于n-1，选择(1)行号ik以交换(2)行k和ik行。(3) I=i=k 1，k 2，n.n计算，2 .逆向代进程，注释：列主要元素剔除方法，低于要求的条件，方程的系数矩阵a是非特异性的。此外，一般方程具有较好的数值稳定性，类似于顺序消除方法的计算量。3.3矩阵的直接分解方法在3.2中讨论，顺序高斯剔除方法的剔除过程是将扩展矩阵A，b=a (1)，b(1)逐步变为矩阵A(n)，b(n)。显示，顺序高斯剔除过程中，系数矩阵a=a (1)将一系列单位下三角形矩阵的左边相乘作为父三角形矩阵A(n)，即1。矩阵的三角分解法，轻松验证这一点。顺序高斯消去的矩阵表达式等，表明系数矩阵a可以分解为一个单位下的三角形矩阵l和上一个三角形矩阵u的乘积。在这里，A=LU定义名为A的三角分解。l，u是向下、向上的三角形阵列。如果l是单位向下三角形矩阵，u是向上三角形矩阵，则A=LU称为A的Doolittle分解。如果l是向下三角形矩阵，则u是单位向上三角形矩阵，A=LU称为A的Crout分解。方程式Ax=b的系数阵列A可以分解为A=LU。其中l是下三角形矩阵，u是上三角形矩阵。此时，求解方程Ax=b是求解两个三角形方程Ly=b，Ux=y的y。如果先求解Ly=b中的矢量y，然后分解Ux=y中的矢量x，则x是原始方程Ax=b的求解向量。三角剖分的有用性，对于，对于，对于，对于，对于，对于，对于，对于，对于，对于，对于，对于，对于系数矩阵，在此简单计算过程中，您可以看到系数矩阵的三角剖分非常重要，Ax=b，A=LU，以Doolittle (dulittle)分解为例，如果在Gauss删除顺序中使用每个步骤删除的主要元素akk(k)0，矩阵a将分解。Akk(k)0的充分条件是，a的每个顺序主节点不是0。，单位下的三角形阵列，父三角形阵列，矩阵a-rnn的Doolittle分解，示例：使用Doolittle三角分解分解矩阵；解决方案：1，2，3，4，1，1，2，6，12，3，7，6，24；矩阵的三角分解；7，6，24，6，24，如果要求矩阵的三角分解，则由获得，已求解，已求解，求解表达式：解法：设定，比较双变量系数为：例如，使用Doolittle (Doolittle)分解方程式，练习1:使用Doolittle三角分解法求解线性方程，求解：的三角分解a=Lu，将增强矩阵A，b三角分解为：123-2，-3，2，2，-。3，3，17，123-2，-3，2，2，-3，-1，3，3，17，在此情况下，方程式为，练习2:使用Doolittle三角分解方法求解线性方程，解决方案：扩展矩阵三角分解，123-4-2，-3，2，4，2，-3，3，2，123-4-2，-3，2，4，2，-3，1，3，3，2，2，-4，-1，17，-16，解析，等价方程可以通过分解轻松写出来：练习：A=LU解析方程式分解为矩阵的后半部：回答：2 .热主要元三角分解法，与热主要元高斯消去法相对应的热主要元三角分解法。选择关键元素；D-分解实现方法采用与热关键元素相似的方法；关键元素也从D-分解中选择。使用D-分解公式，步骤k-1，k-1分解矩阵为，(1)执行k阶段分解，首先查找关键元素，计算中间量，(2)在公式中，进行步骤k的D-分解运算。满足是的值，是步骤k的主要元素。为此，请交换矩阵A(k-1)的k行和ik行。此时：示例：通过将公式分解为主元素的Doolittle (Doolittle)，可以转换解矩阵。是、等效三角方程为：逆对顺解决，实现值，3.4特殊线性方程式解决方案，1 .追赶法，追赶法专门用于求解三角方程。这些方程经常发生在使用差分法或有限元法解决二阶常微分方程边值问题、热传导问题和三次样条函数插值等问题上，三次方程ax=b的系数矩阵是，满足，条件(I)保证不能下方程，条件(ii)保证三角分解到最后。在此条件下，A=，a=，根据矩阵乘法和矩阵等价定义，可以三角分解，如下所示：可以根据此公式三角化三重矩阵，并且对于三重方程ax=b，如果将a的三角剖分设置为a=Lu，则原始表达式由y=b，UX=y，ly=b确定为y；在Ux=y中查找x。参考追赶法进行了总计5n-4的乘法和除法运算的小存储和计算。试验“追赶法”求解线性代数方程：2 .改进的平方根方法，改进的平方根方法通常用于求解对称线性方程。因为是高斯对称的：诱导：3.6线性方程的迭代解法，1 .问题建议，1 .直接方法的缺陷(用高斯消元法表示):虽然对低中间数(n100)的线性方程很有效，但是n非常大，特别是通过一些微分方程的数值解法提出的线性方程，由于舍入误差的积累和计算机的存储困难，直接方法是无能为力的。2 .解决方法： (使用迭代方法)，迭代方法：通过使线性方程的数值解法成为迭代序列来实现。具体方法，(2)用任意初始向量x(0)构造迭代序列：的迭代方法可以避免系数矩阵的零元素的存储和计算，因此，对于求解系数矩阵角度高、非零元素极少(即大稀疏)的线性方程尤其有用。迭代格式：定义：迭代矩阵：迭代过程收敛：如果序列x(k)有限制，则称为此迭代过程收敛，否则称为发散。3 .要讨论的问题：如何设置迭代格式；迭代过程是否聚合，错误分析；收敛速度提高方法等。迭代方法控制计算精度，对求解系数大的方程特别有用。2 .Jacobian迭代方法、迭代格式：缩写：以此格式迭代解决的方法称为Jacobian迭代方法，简称为j方法。以矩阵形式创建：L，U，D，分割A=D L U，分割A为三部分。，Jacobi迭代矩阵，那么原始方程与下一个迭代方程是相同的解：D，L，U的特定形式，j .j .例如，使用jacobi迭代方法求解线性方程，生成jacobi迭代格式。如该表所示，如果迭代序列收敛到x*，并将x(12)用作近似解决方案，则错误为10-5，3 .高斯-赛德尔迭代法，矩阵格式：高斯-Seidel迭代数组，G，g-s迭代，Jacobi迭代，G-S迭代表达式：解法，原始方程式为，创建Jacobi迭代格式，创建Gauss-Seidel迭代格式，如下所示：4 .连续超松弛迭代法，SOR是GS迭代法的加速方法，也是求解大稀疏矩阵方程的有效方法之一。计算公式简单、易于编程、使用较少的计算机内存等优点，但应选择好的加速度系数(最佳松弛系数)。首先，使用GS方法定义辅助对象。添加松弛系数:注：=1时，SOR方法是GS迭代方法。SOR方法计算每个迭代的主运算量与矩阵和矢量的乘法。1的时候，称为超松弛法。1的时候被称为低缓解法。SOR迭代的矩阵格式：fw，SOR迭代矩阵，5 .迭代方法的收敛性，2 .Gauss-Seidel方法的收敛条件，(充分条件)当a严格对角最佳数组时，解的Ja