线性方程组的迭代法

第一次写博客，时间不多，所以原理什么的就不写了。
以下代码基于python和numpy。
解释就一张图。

设有线性方程组 Ax = b，其中A非奇异, 且 aii不等于0, (i = 1, 2, …, n )。

这里十分详细的讲解了“迭代法求解线性方程组”。

Jacobi迭代法

首先

import numpy as np

以下便是我定义的函数

def jacobi(a,b,c=0.0001,d=30):
    x1=np.zeros(a.shape[1])
    x2=np.ones(a.shape[1])
    k=0
    while k<d:
        k=k+1
        print('k=',k)
        for i in range(a.shape[1]):
            x2[i]=(-a[i].dot(x1)+b[i]+a[i,i]*x1[i])/a[i,i]
        if np.max(np.abs(x2-x1))<=c:
            print("x%d=" % k,x2)
            break
        print("x%d=" % k,x2)
        print(np.max(np.abs(x2-x1)))
        x1=x2.copy()

参数说明

“a”就是“A”,“b”就是“b”，和上图对应。
c是一个跳出循环的限定值。
d是最大迭代次数。

实例运行

拿个实例运行一下。

a=np.array([[2,-1,0,0],
          [-1,2.5,-1,0],
           [0,-1,2.5,-1],
           [0,0,-1,2]])
b=np.array([-4,4,4,-4])
jacobi(a,b)

得出以下结果：

k= 1
x1= [-2. 1.6 1.6 -2. ]
k= 2
x2= [-1.2 1.44 1.44 -1.2 ]
k= 3
x3= [-1.28 1.696 1.696 -1.28 ]
k= 4
x4= [-1.152 1.7664 1.7664 -1.152 ]
k= 5
x5= [-1.1168 1.84576 1.84576 -1.1168 ]
k= 6
x6= [-1.07712 1.891584 1.891584 -1.07712 ]
k= 7
x7= [-1.054208 1.9257856 1.9257856 -1.054208 ]
k= 8
x8= [-1.0371072 1.94863104 1.94863104 -1.0371072 ]
k= 9
x9= [-1.02568448 1.96460954 1.96460954 -1.02568448]
k= 10
x10= [-1.01769523 1.97557002 1.97557002 -1.01769523]
k= 11
x11= [-1.01221499 1.98314992 1.98314992 -1.01221499]
k= 12
x12= [-1.00842504 1.98837397 1.98837397 -1.00842504]
k= 13
x13= [-1.00581301 1.99197957 1.99197957 -1.00581301]
k= 14
x14= [-1.00401021 1.99446662 1.99446662 -1.00401021]
k= 15
x15= [-1.00276669 1.99618256 1.99618256 -1.00276669]
k= 16
x16= [-1.00190872 1.99736635 1.99736635 -1.00190872]
k= 17
x17= [-1.00131683 1.99818305 1.99818305 -1.00131683]
k= 18
x18= [-1.00090847 1.99874649 1.99874649 -1.00090847]
k= 19
x19= [-1.00062675 1.99913521 1.99913521 -1.00062675]
k= 20
x20= [-1.0004324 1.99940338 1.99940338 -1.0004324 ]
k= 21
x21= [-1.00029831 1.99958839 1.99958839 -1.00029831]
k= 22
x22= [-1.0002058 1.99971603 1.99971603 -1.0002058 ]
k= 23
x23= [-1.00014198 1.99980409 1.99980409 -1.00014198]
8.805852909499201e-05

Gauss-Seidel迭代法

定义的函数如下：

def Gauss_Seidel(a,b,c=0.0001,d=30):
    x1=np.zeros(a.shape[1])
    x2=np.zeros(a.shape[1])
    k=0
    while k<d:
        k=k+1
        print('k=',k)
        for i in range(a.shape[1]):
            x2[i]=(-a[i].dot(x2)+b[i]+a[i,i]*x2[i])/a[i,i]
        if np.max(np.abs(x2-x1))<=c:
            print("x%d=" % k,x2)
            print(np.max(np.abs(x2-x1)))
            break
        print("x%d=" % k,x2)
        x1=x2.copy()

实例运行

拿同一个实例运行一下。

a=np.array([[2,-1,0,0],
          [-1,2.5,-1,0],
           [0,-1,2.5,-1],
           [0,0,-1,2]])
b=np.array([-4,4,4,-4])
Gauss_Seidel(a,b)

得到如下结果：

k= 1
x1= [-2. 0.8 1.92 -1.04]
k= 2
x2= [-1.6 1.728 1.8752 -1.0624]
k= 3
x3= [-1.136 1.89568 1.933312 -1.033344]
k= 4
x4= [-1.05216 1.9524608 1.96764672 -1.01617664]
k= 5
x5= [-1.0237696 1.97755085 1.98454968 -1.00772516]
k= 6
x6= [-1.01122458 1.98933004 1.99264195 -1.00367902]
k= 7
x7= [-1.00533498 1.99492279 1.99649751 -1.00175125]
k= 8
x8= [-1.0025386 1.99758356 1.99833293 -1.00083354]
k= 9
x9= [-1.00120822 1.99884988 1.99920654 -1.00039673]
k= 10
x10= [-1.00057506 1.99945259 1.99962234 -1.00018883]
k= 11
x11= [-1.0002737 1.99973946 1.99982025 -1.00008987]
k= 12
x12= [-1.00013027 1.99987599 1.99991445 -1.00004278]
k= 13
x13= [-1.000062 1.99994098 1.99995928 -1.00002036]
6.826783096514077e-05

SOR迭代法

定义的函数如下：

def SOR(a,b,w=1,c=0.0001,d=30):
    x1=np.zeros(a.shape[1])
    x2=np.zeros(a.shape[1])
    k=0
    while k<d:
        k=k+1
        print('k=',k)
        for i in range(a.shape[1]):
            x2[i]=(-a[i].dot(x2)+b[i])*w/a[i,i]+x2[i]
        if np.max(np.abs(x2-x1))<=c:
            print("x%d=" % k,x2)
            print(np.max(np.abs(x2-x1)))
            break
        print("x%d=" % k,x2)
        x1=x2.copy()

参数说明

w是松弛因子。

实例运行

拿同一个实例运行一下。

a=np.array([[2,-1,0,0],
          [-1,2.5,-1,0],
           [0,-1,2.5,-1],
           [0,0,-1,2]])
b=np.array([-4,4,4,-4])
w=1.16
SOR(a,b,w)

得到如下结果：

k= 1
x1= [-2.32 0.77952 2.21769728 -1.03373558]
k= 2
x2= [-1.4966784 2.06582956 1.98006004 -1.00616748]
k= 3
x3= [-0.88235031 2.03480459 2.01647801 -0.98945596]
k= 4
x4= [-0.99863729 2.00270936 2.0035131 -0.99964945]
k= 5
x5= [-0.9986466 2.00182455 2.00044715 -0.99979674]
k= 6
x6= [-0.9991583 2.0003061 2.0001648 -0.99993694]
k= 7
x7= [-0.99995713 2.00004738 2.00002488 -0.99999566]
k= 8
x8= [-0.99997938 2.00001353 2.00000431 -0.99999819]
3.3849332815805155e-05

总结

综上可知，同一个实例，在速度上，SOR迭代法>Gauss-Seidel迭代法>Jacobi迭代法。当然，前提是三者均需满足收敛条件。

迭代法收敛的充要条件如下图所示。

以上便是我（为了不用一步一步按计算器来写作业）写的三种迭代方法的定义函数，可能会有更简单，可以评论一番，多多加交流。

本来是为了补数学作业，想GKD，没想到出了点bug（就几行代码还出了bug。。。），吃了个中午饭才大概想到了“x1=x2”应该有问题。

不过塞翁司马，焉知祸福，填补了空白也不错。

可谓是前人栽树，后人乘凉。