线性方程组求解的数值方法.ppt

1、1、第二章是求解线性方程组的数值方法，第二章是求解线性方程组的数值方法，1。高斯消去法2。矩阵分解方法3。向量范数和矩阵范数4。迭代解法5。方程的病态问题和误差分析，主要内容：第二章是求解线性方程的数值方法，了解各种线性方程的数值解法；掌握解法和解法的误差分析方法；该算法可以通过编程实现。特别强调的是：培养用计算机编程解决问题的习惯，而不是用笔计算，这是国内外学生之间的一个主要差距。教学要求：在自然科学和工程技术中，许多问题需要通过解线性方程来解决。因此，求解线性方程组是科学技术中的一个普遍问题。求解线性方程组有两种数值方法：直接法和迭代法。直接法：计算过程中没有舍入误差，方程组的精确解可以通

2、过有限的四次运算得到。(实际计算中存在舍入误差)高斯消去法、矩阵分解法和迭代法：核心是迭代解的收敛条件和收敛速度。雅可比迭代，高斯-塞德尔迭代，基本思想和方法：通过行初等变换将系数矩阵化为三角矩阵；用逆向生成法求解方程。(1)利用消去法(高斯消去法)求解方程，高斯消去法是求解方程的经典方法。高斯消去法，(2.1)，3.1结论：整个计算过程可分为两个部分：(1)消去法：将原始方程转化为以系数矩阵为上三角矩阵的方程；(2)回归：求解系数矩阵为上三角矩阵的方程，(2)得到：解：(1)消去法：对于一般情况：n阶线性方程的高斯消去法，记住，增广矩阵，(2.2)，(1)步骤1 (k=1)，一般形式的高斯消

3、去法：把它加到第I个方程中，去掉第二个方程2.2，直到第n个方程中的未知数，(代表第I行)，得到等价于原始方程的方程。记为(2)一般的第k个消去法()，让我们假设上述消去过程的第一步、第二步和第k-1步已经完成，并且，其中：让我们计算乘数，(也就是说，将乘以2.2的第k个方程加到第I个方程，并且消去2.2的第k-1个方程，直到第n个方程。直到第(n-1)次消去完成，我们最终得到与原始方程等价的三角形方程。(2.3)消去过程结束后，我们求解三角形方程2.3，得到解的公式。这一过程被称为反向生成过程。例如：考虑到方程，在高斯消去法的每一步中用来消去其他元素的主要元素称为该步。高斯消去法作为一种数值

4、方法，主成分的选择会影响计算结果吗？则方程的精确解为，而以(1)为主要元素的高斯消去法得到的解为，显然结果是错误的。错误在哪里？原因是我们在消去法中使用了小的主成分，这大大增加了简化方程元素的数量级，然后将它们四舍五入。然而，计算机的有效位数是有限的，这使得消去后的三角方程不准确。结论：在消去过程中，主元素可能为零，则消去法不会执行，即使不为零，当主元素很小时，将其作为除数会导致其他元素的严重增加和舍入误差的扩散，最终使计算解不可靠。解决方法：对于一般矩阵，最好选择系数矩阵(或消去后的低阶矩阵)列中绝对值最大的元素作为每一步的主元素，这样高斯消去法具有更好的数字稳定性。(高斯列主元消去法)，1

5、。列主元法，第一列最大绝对值为10，取10作为主元。在n阶方程的第k轮消去中，选择第k列最后(n-k-1)个元素中绝对值最大的主元素。，x3=6.2/6.2=1，x2=(2.5-5x3)/2.5=-1，x1=(7 7x2-0x3)/10=0，x1=0x2=-1x3=1，第二列中的最后两个数字选择主元素2.5，2作为完全主元素X1=0 x2=-1 x3=1，6是框中最大的，在交换行和列(即x3和x2交换位置)时应进行记录：完整主元素之间的优缺点比较缺点：计算量大；在矩阵A上实现初等行变换相当于将A乘以左初等矩阵，因此在第一次消去(2.2)之后，它被变换成，即3.1矩阵的三角分解LU分解，步骤k的

6、初等矩阵是，并且，重复这个过程，最终得到上三角矩阵被表示为u，然后上三角矩阵被表示为u，然后本质上，高斯消去产生分解成两个三角矩阵并相乘的因式分解。如果A是非奇异矩阵，则逻辑单元分解是唯一的；否则，分解不是唯一的。消元法：消元法与三角分解法的关系：三角分解法：用直接三角分解法求解线性方程组的具体过程：1。2。计算U的R行和L的R列，元素r=2，3，n，3。(1) LU分解，然后，求解： (1)矩阵LU分解，(1)，所以，(2)，经过计算，(2)求解x:因此，乔莱斯基分解，3.2矩阵，对称正定矩阵A: AT=A，A的各阶主子公式大于零。摘要：指出当A是A(2.4)，uii 0 (i=1，n)的L

7、U分解时，非奇异矩阵可以有三角分解，因为A是对称的正定矩阵，那么u进一步分解：根据A:so:的对称性，由分解的唯一性可知，其中p是上三角矩阵，这个对称正定矩阵的分解称为Cholesky分解。对称正定矩阵的乔莱斯基分解由Matlab中的函数“chol”给出。在n个步骤之后，可以直接获得。思路： (1)分解对称正定矩阵，让n阶对称正定矩阵a被分解，首先用待定系数法求出l的元素，胆斯基分解的具体步骤(胆斯基分解):(2)分解并求解方程，胆斯基法计算公式：分解计算：解：，1。向量范数的定义，其中范数是，最常用的范数是，并且很容易证明向量范数满足以下性质：(1)如果，那么；此外，当且仅当(2)对于任何数

8、c具有(3)时，范数也称为2-范数或欧氏函数；规范也称为-规范或统一规范。该函数用于在Matlab中计算向量x的范数。从性质(3)，很容易得到矩阵范数的定义。矩阵范数可以在向量范数的基础上进一步定义。如果上述公式中的向量范数作为范数，可以证明定义的矩阵范数(称为矩阵范数或列范数)是，如果向量范数作为2-范数，那么，其中(模)称为矩阵B的谱半径(是B的任意特征值.)，类似地，Matlab函数范数(，)给出矩阵p=1，2或范数。如果向量范数为0，则可以证明定义的矩阵范数(称为矩阵的范数或行范数)为0，并且很容易证明矩阵范数满足以下性质：(1)如果是，则；此外，只有当(2)与任何数(3)和(4)相容

9、，并由矩阵范数定义时，它也称为矩阵范数。39，3.4经典迭代法的构造，求解线性代数方程的方法，中小问题，直接法，迭代法，大规模和超大规模问题，经典方法，现代方法，40。线性方程的一般形式是：如果它是非奇异的，上面的公式有唯一的解。我们将用一个特定线性方程组的例子来解释迭代方法。取：即线性方程组为：方程的精确解(用直接法计算)，41。如果方程组是变形的，变量分别从三个方程中分离出来：初始值是，所以公式(1)可以表示为迭代形式：所以我们可以得到一个向量序列，只要序列有一个极限，那么这个极限就是。上述求解线性方程组的迭代法称为雅可比迭代法。考虑到线性方程的一般形式：其中矩阵A是nn阶的平方矩阵，方程

10、的分量形式是：重写为：从而得到迭代公式：上述公式是一般的雅可比迭代法，也可以记为：充分利用雅可比迭代法中的新值，可以得到以下迭代：上述迭代方法也称为高斯-塞德尔迭代法，也可以记为： 方程组的精确解是x *=(1，1，1) t，雅可比迭代公式的解是，取初始向量x(0)=(0，0，0)T，可以通过迭代得到。 例1:利用雅可比法和高斯-塞德尔法求解线性方程组，可以看出迭代序列逐一收敛到方程组的解，计算结果列表如下：高斯-塞德尔迭代法的公式为：并取初始向量x(0)=(0，0，0)T。计算结果表明，高斯-塞德尔迭代法收敛速度快。对于精确到小数点后两位的近似解，高斯-塞德尔迭代法只需迭代三次。雅可比迭代法

11、需要迭代七次。为了进一步研究，从矩阵的角度讨论了上述迭代方法。对于方程Ax=b的线性系统，记住，D=diag(a11，a22，ann)，有A=D-L-U，所以方程Ax=b的线性系统可以写成(D-L-U)x=b，这相当于，因此，迭代公式x(k 1)=D-1(L U)x(k) D-1b k=0，1，2，或者写成x(k 1)=Bx(k) f k=0，1，2，其中高斯-塞德尔迭代例如，它的精确解是：可以看出，不是所有的方程都收敛，即使不同的方法(如雅可比法和高斯-塞德尔法)收敛速度不同，计算结果如下：假设矩阵B的任意特征值是对应的特征向量，即假设它是任意向量范数及其相容的矩阵范数，有：首先，引入几个定

12、义和引理： 记住并称它为矩阵b的谱半径。然后，首先，引入两个引理(详细证明见附录):引理3.1矩阵，那么充要条件是引理3.2矩阵，如果是，它是非奇异的。 定理3.1对于任意初始向量，迭代收敛的充要条件是证明由迭代法生成的序列收敛是必要的，这是序列的极限点。因此，满足迭代关系，我们可以得到任意性，已知：已知：通过引理3.1已知，和通过引理2充分(即，有一个唯一的解决方案，这类似于必要性。众所周知，只要存在某个相容的矩阵范数，那么当然，这在实践中往往是一个有效的收敛准则。严格对角占优矩阵：考虑，假设，当矩阵。定理3.2如果A是严格对角占优的矩阵，它必须是非奇异的。因为a是对角占优矩阵，所以矩阵是可

13、逆的。考虑到矩阵的范数是，因为A是对角占优矩阵，从引理3.2可知它是非奇异的，并且因为它是非奇异的，所以A是非奇异的。去拿证书！引理3.2矩阵，如果，是非奇异的。定理3.3系数矩阵是严格对角占优的线性代数方程组，其雅可比迭代和高斯-塞德尔迭代是收敛的。证明了雅可比方法的迭代矩阵为。根据定理3.2的证明，严格对角占优矩阵满足：然后通过定理3.1，雅可比迭代法收敛。(a)证明a)Jocobi，1 .再次考虑高斯-塞德尔方法。它的迭代矩阵，通过反证的方法，假设高斯-塞德尔迭代不收敛，那么从定理3.1可知，存在一个模大于1的特征值。有一个行列式：(b)高斯-塞德尔的证明，因此，只有它才能成立。因为A是

14、对角占优的，所以矩阵是对角占优的，那么矩阵必须是非奇异的，这与上面矩阵等于0的行列式相矛盾。因为可逆，所以，得到证书！定理3.4如果满足迭代矩阵B，由迭代产生的序列满足收敛速度问题，其中精确解被表达。证明：首先证明(b)，然后证明(a)，因此，这一页上的第一个公式可以写成，因为，因此，(b)被证明，显然对于任何正整数p，那么(a)和(a)可以通过在这一页上的第一个公式中重复使用上述公式来证明也就是说，只要和足够接近，就意味着和足够接近。定理3.4 (a)给出了迭代收敛速度的估计。显然，越接近0，生成的序列收敛得越快。定理3.14 (b)，定理3.4、3.6的讨论过松弛迭代和块迭代法。对于给定的迭代方法，每次迭代所需的工作量是确定的。如果迭代方法收敛速度慢，需要更多的迭代，导致算法工作量大，失去使用价值。因此，各种迭