数值计算解线性方程组的迭代法.doc
文本预览下载声明
第4章? 解线性方程组的迭代法
用迭代法求解线性方程组与第4章非线性方程求根的方法相似，对方程组进行等价变换，构造同解方程组(对可构造各种等价方程组，如分解，可逆，则由得到)，以此构造迭代关系式
???? ?????????? （4.1）
任取初始向量，代入迭代式中，经计算得到迭代序列。
若迭代序列收敛，设的极限为，对迭代式两边取极限
即是方程组的解，此时称迭代法收敛，否则称迭代法发散。我们将看到，不同于非线性方程的迭代方法，解线性方程组的迭代收敛与否完全决定于迭代矩阵的性质，与迭代初始值的选取无关。迭代法的优点是占有存储空间少，程序实现简单，尤其适用于大型稀疏矩阵；不尽人意之处是要面对判断迭代是否收敛和收敛速度的问题。
可以证明迭代矩阵的与谱半径是迭代收敛的充分必要条件，其中是矩阵的特征根。事实上，若为方程组的解，则有
再由迭代式可得到
由线性代数定理，的充分必要条件。
因此对迭代法(4.1)的收敛性有以下两个定理成立。
定理4.1 迭代法 收敛的充要条件是。
定理4.2 迭代法收敛的充要条件是迭代矩阵的谱半径
因此，称谱半径小于1的矩阵为收敛矩阵。计算矩阵的谱半径，需要求解矩阵的特征值才能得到，通常这是较为繁重的工作。但是可以通过计算矩阵的范数等方法简化判断收敛的工作。前面已经提到过，若||A||p矩阵的范数，则总有。因此，若，则必为收敛矩阵。计算矩阵的1范数和范数的方法比较简单，其中
于是，只要迭代矩阵满足或，就可以判断迭代序列是收敛的。
要注意的是，当或时，可以有，因此不能判断迭代序列发散。
在计算中当相邻两次的向量误差的某种范数小于给定精度时，则停止迭代计算，视为方程组的近似解（有关范数的详细定义请看3.3节。）
4.1 雅可比（Jacobi）迭代法
4.1.1 雅可比迭代格式
雅可比迭代计算
元线性方程组
?????????????????（4.2）
写成矩阵形式为。若将式（ 4.2）中每个方程的留在方程左边，其余各项移到方程右边；方程两边除以则得到下列同解方程组：
记，构造迭代形式
或
??? ??（4.3）
迭代计算式（4.3）称为简单迭代或雅可比迭代。任取初始向量 ，由式（4.3）可得到迭代向量序列
雅可比迭代矩阵
设
由，得到等价方程：
记
不难看出，正是迭代式（4.3）的迭代矩阵，是常数项向量。于是式（4.3）可写成矩阵形式：
?????????????????（4.4）
其中：
雅可比迭代算法
下面描述解线性方程组的雅可比迭代算法，为了简单起见，在算法中假定矩阵满足雅可比迭代要求，即，并设由系数矩阵构造迭代矩阵是收敛的。
1．定义和输入系数矩阵与常数项向量的元素。
2．FOR i：=1，2，…，n
{???//假定，形成常数项向量
??????????? FOR j:=1,2,…,n
??????????????
????????
}????????????? //形成迭代矩阵元素
3．
????????????????? // 赋初始值，x1和x2分别表示和
4．WHILE???
???? x1:=x2
??? ?x2:=B*x1+g???//? FOR? u:=1,2,…,n
??????????????????//?? ??s:= g[u];
??????????????????//??FOR v:=1,2,…,n?? s:=s+b[u][v]*x1[v];
??????????????????// ????x2[u]:=s；
? ENDWHILE
5．输出方程组的解
例4.1 用雅可比方法解下列方程组：
解：方程的迭代格式：
?
或
?
雅可比迭代收敛。
取初始值，计算结果由表4.1所示。
表4.1 计算结果
0 1 1 1 ? 1 -1.5 1.6 0.9 0.25 2 -1.25 2.08 1.09 0.48 3 -0.915 2.068 1.017 0.335 4 -0.9575 1.9864 0.9847 0.0816 5 -1.01445 1.98844 0.99711 0.05695 6 -1.00722 2.00231 1.0026 0.01387 7 -0.997543 2.00197 1.00049 0.0096
显示全部