为控制迭代终止的条件。 但要注意当q?1时,
q较大,尽管x(k)?x(k?1)很小,却有可能误差向量模q?1?(k)?x*?x(k)很大,迭代法收敛很慢。而且此充分性条件的结果(3)可以用来事先确定需要迭代多少次才能保证?(k)??。
定理6.3.10 解方程组Ax?b的G-S迭代法收敛的充分必要条件是?(G)?1,G为G-S迭代矩阵。
定义6.3.7 (对角占优矩阵)设A?(aij)n?n
(1) 若aii??aij?0(i?1~n),即A的每一行对角元素绝对值严格大于同行其
j?1j?in他元素绝对值之和。则称A为严格对角占优矩阵。
(2) 若aii??aij?0(i?1~n),且至少有一个不等式严格成立,则称A为弱对
j?1j?in角占优矩阵。
定义6.3.8 (可约与不可约矩阵)设A?(aij)n?n,当n?2时,如果存在n阶排列
?A矩阵p使pTAp??11?0A12?成立。其中A11为r阶子矩阵,A22为n?r阶子矩阵?A22?(1?r?n),则称矩阵A为可约的。若不存在排列矩阵p使上式成立,则称A为不可约矩阵。当A为可约矩阵,则Ax?b可经过若干行列重排化为两个低阶方程
?y??d?组求解。事实上,由Ax?b化为:设y?PTx??1?,PTb??1?,PTAP(PTx)?PTb,
?y2??d2?其中y1,d1为r维向量。
?Ay?Ay?d1 于是,求解Ax?b化为求解:?111122,另外A为可约矩阵的充要
?A22y2?d2条件:存在指标集J??1,2,,n?,J??使akj?0,k?J,j?J.
定理6.3.11(对角占优定理):若A?(aij)n?n为严格对角占优阵或为不可约弱对角占优阵,则A是非奇异阵。 证明 (1)A为严格对角占优阵,采用反证法。若detA?0,则Ax?0有非零的解,
146 / 18
设为x?(x1x2xn)T?0。设xk?maxxi由齐次方程中的第k个方程得:
1?i?nxi?0?ai?1nkixj?0,则可得:
akkxk?n?aj?1j?knkjxj??akj?xj?xkj?1j?kn?aj?1j?knkj (6.3.10)
即有:akk??akj这与严格对角占优阵矛盾,故detA?0。
j?1j?k(2)A为不可约弱对角占优阵,采用反证法。 设?x?0,x?(x1xn)使Ax?0。并令m使amm??amj.(6.3.11)(由弱对角占
Tj?1j?mn优定义)成立。再定义下标集合:
J??kxk?xi,i?1n,xk?xj.对某个j?
在(6.3.10)中取k?m,将导致与(6.3.11)得矛盾。故J??(空集合)。对任意
k?J,有ak??jkaj?xk/x(由(6.3.10)),由此可见,当xk?xj时有akj?0。
j?1j?kn否则,上式就与A为弱对角占优阵矛盾。
但对任意k?J和j?J,必有xk?xj,因而akj?0,k?J,j?J从而A为可约矩阵,这与A为不可约矩阵假设矛盾。
定理6.3.12 若A?Rn?n为严格对角占优矩阵或为不可约对角占优矩阵,则对任意的初始向量x(0),方程组Ax?b的Jacobi迭代法和G-S迭代法均收敛。且G-S迭代法比Jacobi迭代法收敛速度快。
证明 设A为不可约对角占优矩阵,先证明G-S迭代法收敛。由弱对角占优阵假设知aii?0,(i?1~n),而G-S迭代矩阵为G?(D?L)?1U,又det(D?L)?1?0,
det(?I?G)?det(?I?(D?L)?1U)?det(D?L)?1,det(?(D?L)?U)?0即
det(?(d?l)?U)?0.,记C??(D?L)?U。则:
147 / 18
??a11a12??a?a22c??21????an1?an2a1n??a23???a2n? ???an3????ann?a13???下面来证明当??1时,detC?0,这是因为A为不可约阵,则C也不可约,由A为弱对角矩阵,可得:
(当??1)cii??aii???aij?j?1i?1j?i?1?anij??cij
j?i且至少有一个不可约等式严格成立,这表明当??1时,C为不可约弱对角占优矩阵,于是由前一个定理可知当??1时,detC?0,这一结论表明detC?0的根?满足:??1,即?(G)?1,故G-S法收敛。
在同一条件下,对于Jacobi方法(J?D?1(L?U))完全类似于上可证。当A为严格对角占优阵时,证明方法完全类似。
6.3.4 超松弛代法
逐次超松弛迭代法(Successive Over Relaxation Method.简称为SOR法)是Gauss-Seidel法的一种加速方法。这是解大型矩阵方程组的有效方法之一,具有计算公式简单、程序设计容易、占用计算机内存较少等优点,但需要选择好的加速因子,即最佳的加速因子。
对Ax?b(6.3.12)其中A?Rn?n为奇异矩阵,且设aii?0.(i?1n),分解:
A?D?L?U (6.3.13)
设已知第k次迭代向量x(k),及第k?1次迭代向量xi(k?1)的分量 x(jk?1()j?1,2,?i,现在来计算分量:1)先用G-S迭代法求出辅助量xi(k?1)(预测)
xi(k?1)i?1n1(k?1)?(bi??aijxj??aijx(jk)),i?1~n (6.3.14) aiij?1j?i?1再取xi(k?1)为xi(k)与xi(k?1)的某种平均值(即加权平均),即
xi(k?1)?(1??)xi(k)??xi(k?1)?xi(k)??(xi(k?1)?xi(k)) (6.3.15)(校正)将(6.3.14)代入(6.3.15)即得解Ax?b的逐次超松弛迭代公式:
148 / 18
x(k?1)ix(k)???aijx(jk))?aiij?1j?i? (6.3.16) (k)(k)?(x1(k),x2,???xn),(k?0.1,???,i?1~n)???x(k)i??(bi??aijxi?1(k?1)jn其中称?为松弛因子,或写为:
??i?1n???xi?(bi??aijx(jk?1)??aijx(jk))? (6.3.17)
aiij?1j?i??(k?0,1,???,i?1,2,~n)?xi(k?1)?xi(k)??xi显然??1时,解(6.3.12)的SOR法即为Gauss-Seidel迭代法。
SOR法中每迭代一次,主要计算量是计算一次矩阵与向量乘法。由(6.3.16)可见在计算机上用SOR法解方程组只需一组工作单位元,以便存放近似解。迭代计算时,可用p?max?xi?maxxi(k?1)?xi(k)??来控制迭代终止。
i1?i?n当??1时,称(6.3.16)为低松弛法;当??1时,称(6.3.16)为超松弛法。 例6.3.5 用SOR法解:
??4111??x1??1??1?411??x??1????2???? ?11?41??x3??1???????111?4???x4??1?其精确解为x*?(?1,?1,?1,?1)T。 解 取x(0)?0,则SOR迭代公式为:
(k)(k)(k)?x1(k?1)?x1(k)??(1?4x1(k)?x2?x3?x4/4?(k?1)(k)(k?1)(k)(k)(k)?x2?x2??(1?x1?4x2?x3?x4/4 ?(k?1)(k)(k?1)(k?1)(k)(k)?x3?x3??(1?x1?x2?4x3?x4/4(k?1)(k)(k?1)(k?1)(k?1)(k)?x?x??(1?x?x?x?4x41234/4?4取??1.3,第11次迭代结果为:
x(11)?(?0.99999646,?1.00000310,?0.99999953,?0.99999912)T
?(11)2?x(11)?x*2?0.46?10?5
对?取其它值,迭代次数如下表,由此例可见,松弛因子选择得好,会使SOR迭代的收敛大大加速。本例中,??1.3是最佳松弛因子。
表6.3.1 结果表
松弛因子 1.0 1.1 满足误差x?k??x*?10?5的迭代次数 22 17 149 / 18
1.2 1.3* 1.4 1.5 1.6 1.7 1.8 1.9 12 11*最少迭代次数 14 17 23 33 53 109 下面考察SOR迭代公式的矩阵形式,由(6.3.16)可改写为: ax(k?1)iii?(1??)ax(k)iii??(bi??aijxj?1i?1(k?1)j?j?i?1?axijn(k)j),i?1n (6.3.17)
(k?1)由A?D?L?U,则:Dx??(b?Lx(k?1)?Ux(k))?(1??)Dx(k)即
均为奇异阵(D??L)x(k?1)?((1??)D??U)x(k)??b,由于对任意? ,(D??L)(设aii?0.i?1~n,而L为下三角阵,且对角线元素为0)则:
x(k?1)?(D??L)?1?(1??)D??U?x(k)??(D??L)?1b.
因此,若aii?0,i?1~n,则SOR迭代公式为:
x(k?1)?L?x(k)?f (6.3.18) 其中L??(D??L)?1?(1??)D??U?,称L?为SOR方法的迭代f??(D??L)?1b,
矩阵,应用关于迭代法的收敛性定理于(6.3.18)可得:
定理6.3.13 对Ax?b,且aii?0(i?1~n)则解方程组的充要条件是:?(L?)?1。引进超松弛法的想法是希望能选择松弛因子使迭代过程(6.3.16)收敛较快,也就
(L?*)?min?(L?*)是应选择因子?*使?。
? 下面考虑对于方程组(6.3.12)(aii?0,i?1~n),超松弛因子在什么范围内取值才可能收敛。
定理6.3.14 (必要条件)对Ax?b,(aii?,0i1~?0???2。
n)的SOR方法若收敛,则:
证明 由SOR法收敛及上定理,知?(L?)?1,设L?的特征值为?1,?2,???,?n则:
det(L?)??1?2????n?(?(L?)),即det(L?)??(L?)?1,而
n1n150 / 18
回归问题——线性方程组求解的迭代法
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)