数值计算方法3方程组的迭代解法.ppt

3 方程组的迭代解法 ( Iterative methods of Equations )
本章主要内容
向量和矩阵的范数
线性方程组的迭代解法
迭代法的矩阵表示
迭代法的收敛性判定
非线性方程组的迭代解
重点:三种迭代法格式
难点:迭代法的收敛性
应用背景及数学模型
在自然科学和工程技术中,许多问题的解决往往归结为线性方程组的求解问题,如电路网络、结构设计、数据分析、应力分析、自由振动等问题,另外,许多有效的数值计算方法,其关键步骤就是要求解解线性方程组,如三次样条插值、常微分方程边值问题的差分法和有限元法、最小二乘等问题。
线性方程组的数学模型如下:
引入矩阵及向量符号后,其矩阵形式为:
按阶数分为:
高阶:n>1000
中阶:500-1000
低阶:n<500
按系数矩阵的形状和性质分为:
对称正定
三对角
对角占优
按系数矩阵零元素的多少分为:
稠密型
稀疏型
3 方程组的迭代解法 ( Iterative Solution of Equations )
数学方法及存在问题
由克莱姆(Gramer)法则可知:若线性方程组(3-2)的系数行列式D=det(A)非零,则线性方程组(3-2)有且有惟一解,且xj=Dj/D。
但该方法仅乘(除)法运算的次数高达(n+1)n!(n-1)次,当n较大时,其计算量是相当惊人的。如n=20时,计算量大约为1021,用每秒一亿次浮点运算的计算机也需要计算30万年。
数值方法基本思想
线性方程组的数值解法分为两大类,即迭代法和直接法
迭代法(第3章)
思想:类似于一元方程的迭代法,构造迭代公式,用序列逼近
特点:占内存少、程序设计简单
适用:中、大规模问题,尤其是高阶稀疏矩阵
问题:迭代过程(矩阵)的收敛性与收敛速度
直接法(第4章)
思想:对系数矩阵进行分解、变换,经有限次算术运算,求出精确解
特点:准确、可靠、无方法误差
适用:中、小规模问题,尤其是稠密系数矩阵
问题:舍入误差对病态方程组的影响,算法可能不稳定
常见的线性方程组数值方法分类
向量的范数
向量的范数、1范数、2范数、范数、p范数
向量序列的极限和收敛性定理、范数的等价性定理
矩阵的范数
矩阵级数的收敛性
矩阵序列的极限
矩阵级数的收敛性定理
Neumann引理
矩阵的范数、1范数(列和范数)、2范数、范数(行和范数)
矩阵的范数的性质、矩阵的普半径
矩阵范数的等价性、矩阵范数和普半径的关系定理
向量和矩阵的范数
向量与矩阵的范数
向量和矩阵的范数
例3-2 P39
线性方程组的迭代解法
雅克比(Jacobi)迭代法
迭代法的基本思想是构造迭代公式,用某种极限过程去逐步逼近线性方程组的精确解。线性方程组迭代公式的基本形式为:
 Jacobi迭代公式的构造
Jacobi迭代法又称简单迭代法,是其它方法的基础。将(3-1)变形为
其中:
B称为迭代矩阵
f 称为迭代向量
从而得到 Jacobi迭代公式(3-5)
例3-3 用Jacobi迭代法求解
 Jacobi迭代法的特点
简单可并行计算
有三种固定格式的迭代方法
高斯-赛德尔(Gauss-Seidel)迭代法
Gauss-Seidel迭代公式的构造
该方法基于分量的上标越大,越接近于精确解。故用分量
和计算分量。从而得到Gauss-Seidel迭代公式(3-6)
Gauss-Seidel迭代法的特点
通常较Jacobi迭代快、节省空间
不具备并行计算功能
例3-4 P41
Gauss-Seidel迭代算法步骤与流程图
P42 图3-1
两种迭代算法程序及算例演示
超松弛迭代法
超松弛迭代公式的构造
超松弛迭代法是对Gauss-Seidel迭代法的一种改进,是求解大型稀疏矩阵方程组的有效方法之一。
其思想是:为求得,先把用Gauss-Seidel迭代的记作,即
再令
于是得到超松弛迭代公式
或
超松弛迭代算法步骤 P44
令
则
原方程组可写成
分量表示便于编程
矩阵表示便于判定收敛性
迭代公式的矩阵表示