SOR方法的收敛性问题

1SOR方法的收敛性问题引理2.方程组Axb=的SOR方法，总有1()Lωωρ−≤。证明：设111()((1))DLDUωω−+−+的特征值为12,,,nλλλ⋅⋅⋅，则()iLωλρ≤，1,2,,in=⋅⋅⋅。这样，11211()((1))()nnDLDULωλλλρωω−+−+=⋅⋅⋅≤但另一方面，111(1)1111)((1))()(1)11(1)11()nnnDUDLDUDLDUDLDDωωωωωωωωω−−−++−+=+⋅−+=+−==−因此，1()nnLωωρ−≤，也就是1()Lωωρ−≤至此，证明完毕！由上述引理，我们马上得到了SOR方法收敛的必要条件。定理9.方程组Axb=的SOR方法收敛的必要条件是11ω−。特别地，如果ω为实数，则02ω。证明：线性方程组Axb=的SOR迭代格式收敛，因此，()1Lωρ。由引理2，21()1Lωωρ−≤特别地，如果ω为实数，则111ω−−，即02ω。定理10.若A严格对角占优且01ω≤，则SOR方法收敛。证明：必须且只须证明()1Lωρ，其中111()((1))LDLDUωωω−=−+−+。任取Lω−的特征值λ，假设12(,,,)Tnxxxx=⋅⋅⋅为相应的特征向量。则111()((1))DLDUxxλωω−+−+=，也就是11((1))()DUxDLxλωω−+=+，((1))()DUxDLxωωλω−+=+将其写为分量形式，即为111(1)()niiiiijjiiiijjjijaxaxaxaxωωλω−=+=−+=+∑∑，1,2,,in=⋅⋅⋅设kx为x模最大的分量，则0kx≠。考查第k个方程，为111(1)()nkkkkkjjkkkkjjjkjaxaxaxaxωωλω−=+=−+=+∑∑由于01ω≤，1111111111()kkkkkkkkjjkkkkjjkkkkjjkkkkjkjjjjkkkkjkjaxaxaxaxaxaxaxaxaaxωωωωω−−−−====−=+≥⋅−≥⋅−⋅≥⋅−⋅=−∑∑∑∑∑11111(1)(1)(1)(1)(1)nnnkkkkjjkkkkjjkkkkjjjkjkjknnkkkkjkkkkjkjkjkaxaxaxaxaxaxaxaxaaxωωωωωωωωωω=+=+=+=+=+−+≤−⋅+≤−⋅+⋅⎡⎤≤−⋅+⋅=−+⎢⎥⎣⎦∑∑∑∑∑这样，111111()()(1)(1)kknkkkjkkkkkjjkkkkjjjjjknkkkjkjkaaxaxaxaxaxaaxλωλωωωωω−−===+=+−≤+=−+⎡⎤≤−+⎢⎥⎣⎦∑∑∑∑3因此，111()(1)knkkkjkkkjjjkaaaaλωωω−==+−≤−+∑∑，111(1)nkkkjjkkkkkjjaaaaωωλω=+−=−+≤−∑∑1111111,(1)()0knknnkkkjkkkjkkkjkjkkkjjjkjjkjjkaaaaaaaaaωωωωωωω−−==+==+=≠⎡⎤−−−+=−−=−⎢⎥⎣⎦∑∑∑∑∑因此，111(1)0knkkkjkkkjjjkaaaaωωω−==+⎡⎤−−+≥⎢⎥⎣⎦∑∑111(1)1nkkkjjkkkkkjjaaaaωωλω=+−=−+≤−∑∑至此，结论得证！对于A为对称正定的情形，我们有如下的结论。定理11.若A为对称正定矩阵，02ω，则SOR方法收敛。证明方法与定理8类似。证明：必须且只须证明()1Lωρ，其中111()((1))TLDLDLωωω−=−+−+。任取Lω−的特征值λ，假设12(,,,)Tnxxxx=⋅⋅⋅为相应的特征向量。则111()((1))TDLDLxxλωω−+−+=，也就是11((1))()TDLxDLxλωω−+=+，((1))()TDLxDLxωωλω−+=+于是，((1))()HTHxDLxxDLxωωλω−+=+假设HxDxp=，由于对称正定矩阵的对角元均为正数，因此0p。又假设HxLxiαβ=+，则4()HTHHHHHxLxxLxxLxxLxiαβ====−这样，[]((1))(1)(1)()(1)HTHHTxDLxxDxxLxpipiωωωωωωαβωωαωβ−+=−+=−++=−++()()()HHHxDLxxDxxLxpipiωωωαβωαωβ+=+=++=++由于A对称正定，因此()20HHTHHHTxAxxDLLxxDxxLxxLxpiipαβαβα=++=++=+++−=+(1)(2)(1)0222ppppωωωωαα+=−++−因此，()0HxDLxω+≠这样，[](1)((1))()HTHpixDLxxDLxpiωωαωβωωλωωαωβ−++−+==+++[][]222222222(1)(1)()()pipppiωωαωβωωαωβλωαωβωαωβ−++−++==++++由于[][][]222222()(1)(1)(1)(2)(2)0ppppppppωαωβωωαωβωαωωαωαωωαωωα++−−+−=++−++−−−=−+因此，[]222222()(1)0ppωαωβωωαωβ++−++≥也就是说[]2222222(1)1()ppωωαωβλωαωβ−++=++，1λ由λ的任意性，()1Lωρ。至此，结论证毕！最后，我们以最佳松弛因子的选取结束这一讲的内容。所谓最佳松弛因子，是使得()Jωρ最小的松弛因子。我们不加证明地指出如果Jacobi方法收敛，则SOR方法的最佳松弛因子为52111()optJLωρ=+−()JLρ为Jacobi迭代矩阵的谱半径。