线性方程组的迭代法

线性方程组的迭代法2023/2/261第一页，共八十七页，2022年，8月28日其中A为非奇异矩阵.其解法大致分为直接法(第六章)和迭代法(第五章)两大类.对线性方程组Ax=b，(1.1)5.1迭代公式的建立在用直接法解线性方程组时要对系数矩阵不断变换.如果方程组的阶数很高,则运算量将会很大并且大量占用计算机资源，因此对线性方程组要求找寻更经济、适用的数值解法.2023/2/262第二页，共八十七页，2022年，8月28日当A为大型稀疏矩阵方程组(A的阶数n很大，但零元素较多),利用迭代法求解是合适的.本节将介绍迭代法的一些基本理论及雅可比迭代法，高斯-赛德尔迭代法，超松弛迭代法，而超松弛迭代法应用很广泛。2023/2/263第三页，共八十七页，2022年，8月28日迭代法：从一个初始向量出发，按照一定的迭代格式，构造出一个趋向于真解的无穷序列迭代解法是目前求解大规模线性方程组的主要方法.只需存储系数矩阵中的非零元素运算量不超过O(kn2),其中k为迭代步数

(1)迭代格式的建立(3)误差估计和收敛速度研究内容：(2)收敛性判断下面举一简例，以便了解迭代法的思想.2023/2/264第四页，共八十七页，2022年，8月28日

例1求解方程组记为Ax=b，其中此方程组的精确解是x*=(3,2,1)T.现将改写为2023/2/265第五页，共八十七页，2022年，8月28日或写为x=B0x+f，其中2023/2/266第六页，共八十七页，2022年，8月28日任取初始值，例如取x(0)=(0,0,0)T.将这些值代入(1.3)式右边(若(1.3)式为等式即求得方程组的解，但一般不满足)，得到新的值x(1)=(x1(1),x2(1),x3(1))T=(3.5,3,3)T，再将x(1)分量代入(1.3)式右边得到x(2)，反复利用这个计算程序，得到一向量序列和一般的计算公式(迭代公式)2023/2/267第七页，共八十七页，2022年，8月28日简写为x(k+1)=B0x(k)

+f，其中k表示迭代次数(k=0,1,2,).迭代到第10次有2023/2/268第八页，共八十七页，2022年，8月28日迭代法的一个突出优点就是算法简单，因而编制程序比较容易。但是迭代法也有缺点,它要求方程组的系数矩阵具有某种特殊性质，以保证迭代过程的收敛性.发散的迭代过程是没有实用价值的.这种方式就称为迭代法.以上过程称为迭代过程.迭代法产生一个序列如果其极限存在,即则称迭代法收敛,否则称为发散.从此例看出，由迭代法产生的向量序列x(k)逐步逼近方程组的精确解x*=(3,2,1)T.即有2023/2/269第九页，共八十七页，2022年，8月28日对于任何一个方程组x=Bx+f(由Ax=b变形得到的等价方程组)，由迭代法产生的向量序列x(k)是否一定逐步逼近方程组的解x*呢？回答是不一定.例如：考虑用迭代法解下述方程组

x(k)并不是所有的都收敛到解x*！2023/2/2610第十页，共八十七页，2022年，8月28日对于给定方程组x=Bx+f，设有唯一解x*，则

x*=Bx*+f.(1.5)又设x(0)为任取的初始向量,按下述公式构造向量序列

x(k+1)=Bx(k)+f,k=0,1,2,.(1.6)其中k表示迭代次数.

定义1(1)对于给定的方程组x=Bx+f,用公式(1.6)逐步代入求近似解的方法称为迭代法(或称为一阶定常迭代法，这里B与k无关).B称为迭代矩阵.(2)如果limx(k)(k→∞)存在(记为x*),称此迭代法收敛,显然x*就是方程组的解,否则称此迭代法发散.2023/2/2611第十一页，共八十七页，2022年，8月28日由上述讨论，需要研究{x(k)}的收敛性.引进误差向量由(1.6)减去(1.5)式，得ε(k+1)=Bε(k)(k=0,1,2,)，递推得要考察{x(k)}的收敛性，就要研究B在什么条件下有limε(k)=0(k→∞)，亦即要研究B满足什么条件时有Bk→0(零向量)(k→∞).2023/2/2612第十二页，共八十七页，2022年，8月28日其中，A=(aij)∈Rn×n为非奇异矩阵，下面研究任何建立Ax=b的各种迭代法.设线性方程组Ax=b，(1.7)其中，M为可选择的非奇异矩阵，且使Mx=d容易求解，一般选择A的某种近似，称M为分裂矩阵.将A分裂为A=M-N.(1.8)1迭代公式的矩阵表示2023/2/2613第十三页，共八十七页，2022年，8月28日于是，求解Ax=b转化为求解Mx=Nx+b，即求解可构造一阶定常迭代法其中B=M-1N=M-1(M-A)=I-M-1A，f=M-1b.称B=I-M-1A为迭代法的迭代矩阵，选取M矩阵，就得到解Ax=b的各种迭代法.设aii0(i=1,2,,n)，并将A写成三部分2023/2/2614第十四页，共八十七页，2022年，8月28日2023/2/2615第十五页，共八十七页，2022年，8月28日即A=D-L-U2023/2/2616第十六页，共八十七页，2022年，8月28日2雅可比(Jacobi)迭代公式设aii0(i=1,2,,n)，选取M为A的对角元素部分,即选取M=D(对角阵)，A=D-N，由(1.9)式得到解方程组Ax=b的雅可比(Jacobi)迭代法.又称简单迭代法.其中B=I-D-1A=D-1(L+U)=J,f=D-1b.称J为解Ax=b的雅可比迭代法的迭代矩阵.2023/2/2617第十七页，共八十七页，2022年，8月28日于是雅可比迭代法可写为矩阵形式其Jacobi迭代矩阵为2023/2/2618第十八页，共八十七页，2022年，8月28日下面给出雅可比迭代法(1.10)的分量计算公式,记由雅可比迭代法(1.10)有每一个分量写出来为即当aii0时，有2023/2/2619第十九页，共八十七页，2022年，8月28日等价方程组其中

aii(i)0(i=1,2,,n)即由方程组Ax=b得到的2023/2/2620第二十页，共八十七页，2022年，8月28日建立的雅可比迭代格式为2023/2/2621第二十一页，共八十七页，2022年，8月28日于是，解Ax=b的雅可比迭代法的计算公式为由(1.11)式可知，雅可比迭代法计算公式简单，每迭代一次只需计算一次矩阵和向量的乘法且计算过程中原始矩阵A始终不变.2023/2/2622第二十二页，共八十七页，2022年，8月28日3高斯－赛德尔迭代法在Jacobi

迭代中，计算xi(k+1)(2in)时，使用xj(k+1)代替xj(k)(1ji-1)，即有建立迭代格式2023/2/2623第二十三页，共八十七页，2022年，8月28日或缩写为称为高斯—塞德尔(Gauss—Seidel)迭代法.其Gauss—Seidel迭代矩阵为BG=(D-L)-1U于是高斯—塞德尔迭代法可写为矩阵形式2023/2/2624第二十四页，共八十七页，2022年，8月28日这就是说，选取分裂矩阵M为A的下三角部分,即选取M=D-L(下三角阵)，A=M-N，由(1.9)式得到解Ax=b的高斯—塞德尔(Gauss—Seidel)迭代法.其中B=I-(D-L)-1A=(D-L)-1U=G,f=(D-L)-1b.称矩阵G=(D-L)-1U为解Ax=b的高斯—塞德尔迭代法的迭代矩阵.2023/2/2625第二十五页，共八十七页，2022年，8月28日由高斯—塞德尔迭代法(1.12)有每一个分量写出来为即当aii0时，有(与前面一样的式子)或2023/2/2626第二十六页，共八十七页，2022年，8月28日于是，解Ax=b的高斯—塞德尔迭代法的计算公式为或2023/2/2627第二十七页，共八十七页，2022年，8月28日

雅可比迭代法不使用变量的最新信息计算xi(k+1)，而由高斯—塞德尔迭代公式(1.13)可知，计算x(k+1)的第i个分量xi(k+1)时，利用了已经计算出的最新分量xj(k+1)(j=1,2,,i-1).

可看作雅可比迭代法的一种改进.由(1.13)可知，高斯—塞德尔迭代公式每迭代一次只需计算一次矩阵与向量的乘法.

算法(高斯—塞德尔迭代法)见书p160.2023/2/2628第二十八页，共八十七页，2022年，8月28日

例2用高斯—塞德尔迭代法解例1的方程组(1.2).

解用高斯—塞德尔迭代公式：取x(0)=(0,0,0)T.迭代到第7次有2023/2/2629第二十九页，共八十七页，2022年，8月28日由此例可知，用高斯—塞德尔迭代法，雅可比迭代法解线性方程组(1.2)(且取x(0)=0)均收敛，而高斯—塞德尔迭代法比雅可比迭代法收敛较快(即取相同的x(0)，达到同样精度所需迭代次数较少)，但这结论只当A满足一定条件时才是对的.2023/2/2630第三十页，共八十七页，2022年，8月28日

例3用雅可比迭代法解方程组

解：Jacobi

迭代格式为2023/2/2631第三十一页，共八十七页，2022年，8月28日kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15…………111.0999931.1999931.299991121.0999981.1999981.299997取x(0)=(0,0,0)T

计算结果如下：2023/2/2632第三十二页，共八十七页，2022年，8月28日

解：Gauss-Seidel

迭代格式为

例4用Gauss—Seidel迭代法解上题.2023/2/2633第三十三页，共八十七页，2022年，8月28日取x(0)=(0,0,0)T

计算结果如下：kx1(k)

x2(k)x3(k)10.720.9021.1644…………81.0999981.1999991.32023/2/2634第三十四页，共八十七页，2022年，8月28日4解大型稀疏线性方程组的逐次超松弛法(SOR方法)我们取>0为松弛因子，建立迭代格式如下即2023/2/2635第三十五页，共八十七页，2022年，8月28日或改写为称为逐次超松弛迭代法(SuccessiveOverRelaxationMethod),

，简称SOR方法.(1.14)2023/2/2636第三十六页，共八十七页，2022年，8月28日(1)显然，当=1时即为Gauss—Seidel迭代法.(2)SOR方法每迭代一次主要运算量是计算一次矩阵与向量的乘法.(3)当>1时，称为超松弛法；当<1时，称为低松弛法.(4)在计算机实现时可用控制迭代终止，或用控制迭代终止.2023/2/2637第三十七页，共八十七页，2022年，8月28日

SOR迭代法是Gauss—Seidel迭代法的一种修正，可由下述思想得到.设已知x(k)及已计算x(k+1)的分量xj(k+1)(j=1,2,,i-1).(1)首先用Gauss—Seidel迭代法定义辅助量,(2)再由与加权平均定义，即将(1.15)代入(1.16)得到解Ax=b的SOR迭代(1.13)式.2023/2/2638第三十八页，共八十七页，2022年，8月28日记笔记5.2向量和矩阵的范数为了研究线性方程组近似解的误差估计和迭代法的收敛性,有必要对向量及矩阵的“大小”引进某种度量----范数的概念.向量范数是用来度量向量长度的,它可以看成是二、三维解析几何中向量长度概念的推广.用Rn表示n维实向量空间.5.2向量和矩阵的范数2023/2/2639第三十九页，共八十七页，2022年，8月28日基本概念:

“范数”是对向量和矩阵的一种度量,实际上是二维和三维向量长度概念的一种推广.数域:数的集合,对加法和乘法封闭

线性空间:可简化为向量的集合,对向量的加法和数量乘法封闭,也称为向量空间

二维向量和三维向量都可以度量其大小和长度。高维向量的"长度"能否定义呢?2023/2/2640第四十页，共八十七页，2022年，8月28日定义1

对任一向量XRn,按照一定规则确定一个实数与它对应,该实数记为||X||,若||X||满足下面三个性质:(1)||X||0；||X||=0当且仅当X=0；(2)对任意实数，||X||=||||X||；对任意向量YRn，||X+Y||||X||+||Y||

则称该实数||X||为向量X的范数.2023/2/2641第四十一页，共八十七页，2022年，8月28日在Rn中，常用的几种范数有：其中x1,x2,…,xn分别是X的n个分量。以上定义的范数分别称为1-范数，2-范数和-范数可以验证它们都是满足范数性质的，其中是由内积导出的向量范数。2023/2/2642第四十二页，共八十七页，2022年，8月28日当不需要指明使用哪一种向量范数时，就用记号||.||泛指任何一种向量范数。有了向量的范数就可以用它来衡量向量的大小和表示向量的误差。设x*为Ax=b的精确解，x为其近似解，则其绝对误差可表示成||x-x*||，其相对误差可表示成或2023/2/2643第四十三页，共八十七页，2022年，8月28日2023/2/2644第四十四页，共八十七页，2022年，8月28日例1证明对任意同维向量x,y

有

证：

即2023/2/2645第四十五页，共八十七页，2022年，8月28日例2设x=(1,0,-1,2)T,计算

解:=1+0+|-1|+2=42023/2/2646第四十六页，共八十七页，2022年，8月28日定理1对于任意向量x,有证:∵

∴即

当p→∞，

∴2023/2/2647第四十七页，共八十七页，2022年，8月28日定义2(向量序列的极限)设为中的一向量序列，,记.如果(i=1,2,…,n)，则称收敛于向量，记为

定理2（向量范数的等价性）设为上任意两种向量范数,则存在常数C1,C2>0,使得对任意恒有（证:略）

2023/2/2648第四十八页，共八十七页，2022年，8月28日定理3

其中为向量中的任一种范数.

2023/2/2649第四十九页，共八十七页，2022年，8月28日例3求下列向量的各种常用范数解:1*4≤9≤9/4*4=92023/2/2650第五十页，共八十七页，2022年，8月28日定义3

（矩阵的范数）如果矩阵的某个

非负的实值函数，满足则称是上的一个矩阵范数(或模).

2023/2/2651第五十一页，共八十七页，2022年，8月28日定义4（矩阵的算子范数）设n维向量X和n阶方阵A，当给定一种向量范数||X||时，则定义

为矩阵的范数，并称为矩阵的算子范数。矩阵范数定义的另一种方法:从定义可以看出，矩阵范数和向量范数密切相关。2023/2/2652第五十二页，共八十七页，2022年，8月28日常用的矩阵范数--------(5)--------(6)--------(7)矩阵算子范数：（诱导范数）由向量范数||·||p

导出关于矩阵A

Rnn

的p范数:2023/2/2653第五十三页，共八十七页，2022年，8月28日矩阵范数的性质可由向量范数定义直接验证.(1)设A≠0,x≠0,使Ax≠0,根据向量范数的性质Ax>0,所以>0x≠0,使Ax=0,则=0当A=0时,2023/2/2654第五十四页，共八十七页，2022年，8月28日∴(2)根据向量范数的性质2023/2/2655第五十五页，共八十七页，2022年，8月28日(3)2023/2/2656第五十六页，共八十七页，2022年，8月28日例4计算方阵

的三种范数

解先计算

所以,从而

2023/2/2657第五十七页，共八十七页，2022年，8月28日例5求矩阵A的各种常用范数解:由于2023/2/2658第五十八页，共八十七页，2022年，8月28日特征方程为2023/2/2659第五十九页，共八十七页，2022年，8月28日容易计算计算较复杂对矩阵元素的变化比较敏感使用最广泛性质较好使用最广泛2023/2/2660第六十页，共八十七页，2022年，8月28日5.3迭代过程的收敛性1迭代收敛的充分条件其中，A=(aij)∈Rn×n为非奇异矩阵，记x*为(3.1)精确解，且设有等价的方程组设线性方程组Ax=b，(3.1)于是设有解Ax=b的一阶定常迭代法2023/2/2661第六十一页，共八十七页，2022年，8月28日有意义的问题是：迭代矩阵B满足什么条件时，由迭代法产生的向量序列{x(k)}收敛到x*.引进误差向量由(3.3)式减(3.2)得到误差向量的递推公式由5.1节可知，研究迭代法(3.3)收敛性问题就是要研究迭代矩阵B满足什么条件时，有.2023/2/2662第六十二页，共八十七页，2022年，8月28日

定义1设有矩阵序列Ak=(aij(k))∈Rn×n

及A=(aij)∈Rn×n，如果n2个数列极限存在且有则{Ak}称收敛于A，记为limAk=A(k→∞).

例1设有矩阵序列{Ak},其中Ak=Bk,而且设|λ|<1，考查矩阵序列极限.

解显然,当|λ|<1时,则有2023/2/2663第六十三页，共八十七页，2022年，8月28日矩阵序列极限概念可以用矩阵算子范数来描述.

定理1其中||·||为矩阵的任意一种算子范数.

证明显然有再由矩阵范数的等价性,则定理对其它算子范数亦对.

定理2

证明作为练习.2023/2/2664第六十四页，共八十七页，2022年，8月28日

定理3(迭代法收敛的充分条件)设有方程组x=Bx+f，B=(bij)∈Rn×n，及一阶定常迭代法x(k+1)=Bx(k)+f.如果有B的某种算子范数||B||=q<1，则(1)迭代法收敛，即对任取x(0)有2023/2/2665第六十五页，共八十七页，2022年，8月28日2对角占优方程组在科学及工程计算中，要求解方程组Ax=b，其矩阵A常常具有某些特性.例如，A具有对角占优性质或A为不可约阵，或A是对称正定阵，下面讨论用基本迭代法解这些方程组的收敛性.2023/2/2666第六十六页，共八十七页，2022年，8月28日

定义2(对角占优阵)设A=(aij)n×n

.(1)如果A的元素满足称A为严格(按行)对角占优阵.(2)如果A的元素满足且上式至少有一个不等式成立，称A为弱(按行)对角占优阵.2023/2/2667第六十七页，共八十七页，2022年，8月28日

定义3(可约与不可约矩阵)设A=(aij)n×n

(n≥2)，如果存在置换阵P使其中A11为r阶方阵，A22为n-r阶方阵(1≤r≤n)，则称A为可约矩阵.否则，如果不存在这样置换阵P使(3.6)式成立，则称A为不可约矩阵.

A为可约矩阵意即A可经过若干行列重排化为(3.6)或Ax=b可化为两个低阶方程组求解(如果A经过两行交换的同时进行相应两列的交换，称对A进行一次行列重排).2023/2/2668第六十八页，共八十七页，2022年，8月28日

事实上，由Ax=b可化为PTAP(PTx)=PTb.于是，求解Ax=b化为求解且记,其中yi,di为r维向量.由上式第2个方程组求出y2,再代入第1个方程组求出y1.

显然，如果A所有元素都非零，则A为不可约阵.2023/2/2669第六十九页，共八十七页，2022年，8月28日

例7设有矩阵则A,B都是不可约矩阵.2023/2/2670第七十页，共八十七页，2022年，8月28日

定理4(对角占优定理)如果A=(aij)n×n为严格对角占优矩阵或A为不可约弱对角占优矩阵，则A为非奇异矩阵.

证明只就A为严格对角占优矩阵证明此定理.采用反证法，如果det(A)=0，则Ax=b有非零解，记为x=(x1,x2,,xn)T，则.

由齐次方程组第k个方程则有即这与假设矛盾，故det(A)≠0.2023/2/2671第七十一页，共八十七页，2022年，8月28日

定理5设方程组Ax=b，如果(1)A为严格对角占优阵，则解Ax=b的Jacobi迭代法,Gauss-Seidel

迭代法均收敛.(2)A为弱对角占优阵，且A为不可约矩阵,则解Ax=b的Jacobi迭代法,Gauss-Seidel

迭代法均收敛.

证明只证(1)，(2)作为练习.

因为A是严格对角占优阵，所以aii≠0(i=1,,n).则||J||<1，所以Jacobi迭代法收敛.Jacobi迭代阵2023/2/2672第七十二页，共八十七页，2022年，8月28日下面证明Gauss—Seidel迭代法收敛.由G=(D-L)-1U，得下面证明||<1.若不然,即||1,则由于所以2023/2/2673第七十三页，共八十七页，2022年，8月28日即矩阵是严格对角占优矩阵，故可逆，这与(*)

式矛盾，所以||<1,从而(G)<1，即Gauss—Seidel迭代法收敛.2023/2/2674第七十四页，共八十七页，2022年，8月28日定理6若A为正定矩阵，则方程组Ax=b的Gauss-Seidel迭代法收敛.证因为A=D-L-LT，G=(D-L)-1LT，设为G

的特征值，y为对应的特征(复)向量，即

(D-L)-1LTy=y，LTy=(D-L)y，则内积(LTy,y)=((D-L)y,y).从而

因为A正定，所以D正定，故(Dy,y)=>0.2023/2/2675第七十五页，共八十七页，2022年，8月28日所以||<1,从而(G)<1,故Gauss-Seidel迭代法收敛.令-(Ly,y)=a+ib，则由复向量内积的性质有下面研究对于解方程组Ax=b的SOR方法中松弛因子ω在什么范围内取值，SOR方法才可能收敛.2023/2/2676第七十六页，共八十七页，2022年，8月28日定理7(SOR方法收敛的必要条件)设解方程组Ax=b的SOR迭代法收敛，则0<<2.

证

A=D-L-U，L=(D-L)-1[(1-)D+U],由于SOR迭代法收敛，则(L)<1.设迭代矩阵L的特征值为i

(i=1,,n)，则有det(L)<|12n|<[(B

)]n<1.于是所以|1-|<1，即0<<2.2023/2/2677第七十七页，共八十七页，2022年，8月28日

定理7说明解Ax=b的SOR迭代法，只有在(0,2)范围内取松弛因子，才可能收敛.定理8(SOR方法收敛的充分条件)设有方程组Ax=b，如果：(1)A为对称正定矩阵，A=D-L-LT;(2)0<<2.则解方程组Ax=b的SOR迭代法收敛.

证在上述假定下，设迭代矩阵L的任一特征值为，只要证明||<1即可.2023/2/2678第七十八页，共八十七页，2022年，8月28日事实上，设y为对应的Lω的特征向量，即亦即有内积则

因为A正定，所以D正定，记(Dy,y)=>0.令-(Ly,y)=a+ib，则由复向量内积的性质有2023/2/2679第七十九页，共八十七页，2022年，8月28日当0<<2时，有(分子减分母)即L的任一特征值满足||<1,故SOR迭代法收敛.2023/2/2680第八十页，共八十七页，2