1、 应用背景及数学模型应用背景及数学模型 )13(22112222212111212111nnnnnnnnnnbxaxaxabxaxaxabxaxaxa 在自然科学和工程技术中，许多问题的解决往往归结为线性方程组的求解问题，如电路网络、结构设计、数据分析、应力分析、自由振动等问题，另外，许多有效的数值计算方法，其关键步骤就是要求解解线性方程组，如三次样条插值、常微分方程边值问题的差分法和有限元法、最小二乘等问题。线性方程组的数学模型如下：引入矩阵及向量符号后,其矩阵形式为：)23(bAx按阶数阶数分为：高阶：n1000中阶：500-1000低阶：n500按系数矩阵的形状和性质分为：对称正定三对角
2、对角占优按系数矩阵零元素的多少分为：稠密型稀疏型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、法直接法 迭代法迭代法（第（第3章）章）思想思想：类似于一元方程的迭代法，构造迭代公式，用序列逼近特点特点：占内存少、程序设计简单适用适用：中、大规模问题，尤其是高阶稀疏矩阵问题问题：迭代过程（矩阵）的收敛性与收敛速度 直接法直接法（第（第4章）章）思想思想：对系数矩阵进行分解分解、变换变换，经有限次算术运算，求出精确解特点特点：准确、可靠、无方法误差无方法误差适用适用：中、小规模问题，尤其是稠密系数矩阵问题问题：舍入误差对病态方程组的影响，算法可能不稳定 常见的线性方程组常见的线性方程组数值方法分类数值方法分类 平方根分解法乔立斯基三对角方程组的追赶法分解克劳拉分解杜利特里分解分解法消去法主
4、元消去法消去法消去法直接法迭代法迭代法迭代法迭代法)()()(CholesyCroutDoolittleLUJordanGaussGaussGaussSORSeidelGaussJacobi3.1.1 向量的范数向量的范数向量的范数、1范数、2范数、范数、p范数向量序列的极限和收敛性定理、范数的等价性定理 3.1.2 矩阵的范数矩阵的范数 3.1.3 矩阵级数的收敛性矩阵级数的收敛性 矩阵序列的极限矩阵级数的收敛性定理 Neumann引理 矩阵的范数、1范数（列和范数）、2范数、范数（行和范数）矩阵的范数的性质、矩阵的普半径矩阵范数的等价性、矩阵范数和普半径的关系定理3.1 向量和矩阵的范数向
5、量和矩阵的范数向量与矩阵的范数3.1 向量和矩阵的范数向量和矩阵的范数例3-2 P393.2 线性方程组的迭代解法线性方程组的迭代解法 3.2.1 雅克比雅克比(Jacobi)迭代法迭代法 迭代法的基本思想是构造迭代公式，用某种极限过程去逐步逼近线性方程组的精确解。线性方程组迭代公式的基本形式为：Jacobi迭代公式的构造迭代公式的构造Jacobi迭代法又称简单迭代法，是其它方法的基础。将(3-1)变形为)43(,2,1,0)()1(kfBxxkk其中：其中：B称为迭代矩阵迭代矩阵f 称为迭代向量迭代向量),2,1,0(/)(1niaaxabxiiiijnijjijii)53(),2,1,0,
6、2,1(/)()(1)1(kniaxabxiikjnijjijiki从而得到 Jacobi迭代公式迭代公式（3-5）2.453.82102.7210321321321xxxxxxxxx例例3-3 用Jacobi迭代法求解 Jacobi迭代法的特点迭代法的特点 简单简单 可并行计算可并行计算有三种固定格式的迭代方法3.2.2 高斯高斯-赛德尔赛德尔(Gauss-Seidel)迭代法迭代法 Gauss-Seidel迭代迭代公式的构造公式的构造 该方法基于分量的上标越大，越接近于精确解。故用分量 和 计算分量 。从而得到Gauss-Seidel迭代迭代公式公式（3-6）)1(1)1(2)1(1,ki
7、kkxxx)()(1,knkixx)1(kix)63(),2,1,0,2,1(/)()(1)1(11)1(kniaxaxabxiikjnijijkjijijiki Gauss-Seidel迭代迭代法的特点法的特点通常较Jacobi迭代快、节省空间 不具备并行计算功能不具备并行计算功能例例3-4 P41 Gauss-Seidel迭代迭代算法步骤与流程图算法步骤与流程图 P42 图图3-1两种迭代算法程序及算例演示3.2.3 超松弛迭代法超松弛迭代法 超松弛迭代超松弛迭代公式的构造公式的构造 超松弛迭代法是对Gauss-Seidel迭代法的一种改进，是求解大型稀疏矩阵方程组的有效方法之一。其思想思
8、想是：为求得 ，先把用Gauss-Seidel迭代的 记作 ，即)1(kix),2,1()()1()(1)1(11)()1(nixaxabaxxkjnijijkjijijiiikiki)1(kix),2,1(/)()(1)1(11)1(niaxaxabxiikjnijijkjijijiki再令于是得到超松弛迭代公式超松弛迭代公式)()1()()1()()1()()1(kikikikikikixxxxxx)73(),2,1()()()1(11)()1(nixaxabaxxkjnijijkjijijiiikiki或)1(kix 超松弛迭代超松弛迭代算法步骤算法步骤 P44令 jiajilaaaLi
9、jijnn00000002121jiajidaaaDijijnn02211 jijiauaaaUijijnn00000002112则UDLA原方程组可写成bUxDxLxbAx fBxx,2,1,0)()1(kfBxxkk分量表示便于分量表示便于编程编程矩阵表示便于矩阵表示便于判定收敛性判定收敛性3.3 迭代公式的矩阵表示迭代公式的矩阵表示 )83()(1UxLxbDx1.Jacobi迭代迭代法的矩阵表示法的矩阵表示整理得)()()1(1)1(kkkUxLxbDx由(3-8)得Gauss-Seidel迭代迭代公式为公式为bLDUxLDxkk1)(1)1()()(便得到Gauss-Seidel迭代
10、的矩阵表示。矩阵表示。bLDfULDBSGSG11)()103()(式中bDfADEULDBJJ111)93()(2.Gauss-Seidel迭代迭代法的矩阵表示法的矩阵表示故超松弛迭代法的矩阵形式矩阵形式可写成)()1()()1()()1(kkkkUxLxbDxDxbxUDxLDkk)()1()1()()113()()1(fxBxkkbLDfUDLDB11)(,)1()(即于是得到超松弛的矩阵表示其中当0w 1时，称为超松弛迭代法超松弛迭代法，可提高收敛速度当w=1时，退化为Gauss-Seidel迭代法),2,1()()1()(1)1(11)()1(nixaxabxaxakjnijijkj
11、ijijikiiikiii3 超松弛迭代法矩阵表示超松弛迭代法矩阵表示 超松弛迭代公式可变形为超松弛迭代公式可变形为3.4 迭代法的收敛性判定迭代法的收敛性判定 定理定理3-2 （迭代法收敛基本定理）（迭代法收敛基本定理）对于任何初始向量x(0)和常数项f，由迭代公式（3-3）产生的向量序列收敛x(k)的充分必要条件是1)(B定理表明：迭代是否收敛只与迭代矩阵的谱半径有关，即与系数矩阵A及其演变过程有关，与迭代初值x(0)和常数项f无关。迭代矩阵迭代矩阵B的谱的谱半径越小，迭代过程收敛越快半径越小，迭代过程收敛越快。3.4.1 迭代法的收敛性迭代法的收敛性结合预备知识3.1节的定理 容易得到：
12、1)(0AAk1)(0AAk例例3-2 给定方程组分别采用Jacobi和Gauss-Seidel迭代法求解时的收敛性。111211111112321xxx02/12/11012/12/10JB2/1002/12/102/12/10SGB例例3-3 给定方程组分别采用Jacobi和Gauss-Seidel迭代法求解时的收敛性。321122111221321xxx022101220JB200320220SGBJacobi法发散Gauss-Seidel法收敛Jacobi法收敛Gauss-Seidel法发散定理定理3-4 （迭代法收敛充分条件）（迭代法收敛充分条件）若|B|1，则由迭代公式（3-3）产
13、生的向量序列收敛x(k)收敛于方程组x=Bx+f的精确解x*,且有误差估计)133(1)123(1)0()1(*)()1()(*)(xxBBxxxxBBxxkkkkk注意注意：该定理是充分但不必要的条件。例例3-9（P 49）从上面的例子可以看出，用迭代基本定理来判定迭代方法的收敛性理论上是可行的，实际上是困难的，因为当阶数较大时B的特征值几乎是无法用手工计算的，即使是用数值方法求特征值，计算量也不小。但由于可以用|B|作为谱半径上界的一个估计，得到下面的定理。BB)(定理定理3-6 若方程组若方程组Ax=b的系数矩阵是严格对角占优的，则该方程组有唯的系数矩阵是严格对角占优的，则该方程组有唯一
14、解且求解方程组的雅克比迭代和高斯一解且求解方程组的雅克比迭代和高斯-赛德尔迭代均收敛。赛德尔迭代均收敛。定理定理 若方程组若方程组Ax=b的系数矩阵是严格对角占优的，则当的系数矩阵是严格对角占优的，则当0w=1时，求时，求解方程组的解方程组的SOR迭代收敛；若迭代收敛；若A对称正定时，则当对称正定时，则当0w2时，求解方程组时，求解方程组的的SOR迭代收敛。迭代收敛。定理定理 若方程组若方程组Ax=b的系数矩阵非奇异且主对角线元素不为的系数矩阵非奇异且主对角线元素不为0，则求解方，则求解方程组的程组的SOR迭代收敛的必要条件是迭代收敛的必要条件是0w2。例例3.5 非线性方程组的迭代解法非线性
15、方程组的迭代解法 迭代公式的收敛性与非线性方程的迭代法类似。即在迭代公式满足映迭代公式的收敛性与非线性方程的迭代法类似。即在迭代公式满足映内性和压缩性的条件下是收敛的。内性和压缩性的条件下是收敛的。3.5.1 非线性方程组的迭代格式非线性方程组的迭代格式)1,0(,)()(,D)(DLyxLyxDyxxx其中压缩性：，映内性：.0)(,)(.lim)()()(*)()()()1(的解是从而的不动点为迭代函数称设。否则，称迭代公式发散收敛，称迭代公式收敛若迭代产生向量序列为迭代公式。为迭代函数，称xFxxxxxxxxxkkkkkTnTnkkxxxxxfxfxfxFkxxxxxF)(,),(),()(,)(,),(),()(,2,1,0),()(0)(2121)()1(其中：3.5 非线性方程组的迭代解法非线性方程组的迭代解法 3.5.2 非线性方程组的牛顿迭代法非线性方程组的牛顿迭代法
