[理学]31-32线性方程组迭代解法.ppt

第三章 线性方程组迭代解法Iterative techniques for solving linear system 内容提要(content) 3.1 概 论(Introduction) 3.2(I) Jacobi 迭代法(Jacobi iterative) 3.2(II) Gauss-Seidel 迭代法 (Gauss-Seidel iterative) 3.3 迭代法的收敛性 (The convergence of iterative method) 3.4 SOR法 (SOR method)) 本章学习要点 概 论 引子 迭代法的基本思想 迭代法的主要步骤 引子(Introduction) 迭代法的基本思想The ideal of iterative method 迭代法的主要步骤The process of iterative method 迭代公式的构造 迭代公式的收敛性 研究 {x(k) }的收敛性 基本迭代法the based iterative technique 设有 §3.2(I) Jacobi 迭代法（Jacobi iterative method） 数学问题的描述 Jacobi迭代法的主要步骤 数学问题的描述 3.2 雅可比( Jacobi ) 迭代法 迭代矩阵 (Iterative matrix) ; 每迭代一次主要是计算一次矩阵乘向量 ； The calculation amount lies in in every step. 计算过程中,初始数据A始终不变; The matrix A is always unchanged in the iterative process 计算过程中涉及到的中间变量 及 ,需要两组工作单元x(n),　y(n)来存储. Two computer storages x(n),　y(n) are required. 问题：如何判断可以终止迭代？ Jacobi迭代法的主要步骤 对于Jacobi迭代法,它的每一步设定计算顺序为 在计算迭代值 时, 利用它前面已计算的值 而此时 也已计算, 但是Jacobi迭代法并没有充分及时地利用这些信息, 为此我们得到改进的格式 ,称为高斯—塞德尔(Gauss–Seidel)迭代 公式。 §3.2(II) Gauss-Seidel迭代法 算法分析与描述 实例求解 算法分析与描述 推导Gauss-Seidel迭代法的矩阵形式 (高斯-塞德尔迭代法) 设Ax=b，其中A 为非奇异矩阵且a ii≠0 .本算法用高斯-塞德尔迭代法解Ax=b，数组x(n)开始存放x0,后存放x_k,N0为最大迭代次数 实例求解 * * 直接法得到的解是理论上准确的，但是我们可以看得出，它们的计算量都是n3数量级，存储量为n2量级，这在n比较小的时候还比较合适（n400），但是对于现在的很多实际问题，往往要我们求解很大的n的矩阵，而且这些矩阵(系数矩阵)往往是含有大量的0元素。对于这类的矩阵，再用直接法时就会耗费大量的时间和存储单元。另一方面,实际计算结果精度有时无法保证. 主要原因是在多次消去、回代过程中四则运算的误差积累与传播无法控制. 因此我们有必要引入一类新的方法：迭代法。 返回节 Direct techniques are used for solving linear systems of small dimension. For large systems with high percentage of 0 entries, the direct methods are not efficient enough in term Of computer storage and computation amount. 迭代法是解线性方程组的一种重要的实用方法，特别适用于求解在实际中大量出现的，系数矩阵为稀疏阵的大型线性方程组。 迭代法的基本思想是去构成一个向量序列{x(k)}，使其收敛至某个极限向量x* ，并且x*就是要求解的方程组：Ax = b 的准确解。 返回节 An iterative technique to solving Ax=b starts with an initial Approximate x0 and