一般迭代法matlab编程代码_解线性方程组的经典迭代法(1)-理论

93 阅读 0 评论 62 点赞

我是靠谱客的博主拼搏音响，最近开发中收集的这篇文章主要介绍一般迭代法matlab编程代码_解线性方程组的经典迭代法(1)-理论，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

本文复习求解线性方程组的经典迭代法的理论部分，且主要是单步迭代法.

下一节将会是MATLAB编程实现，并大概比较下各算法的优劣.

我们考虑的问题是求解线性方程组

$equation?tex=ax%3db$ ,其中

$equation?tex=a$ 是n阶实方阵，

$equation?tex=x%2cb$ 是n维列向量.

迭代法的一般格式
Jacobi迭代
Gauss-Seidel迭代
JOR迭代
SOR迭代

1.一般格式

单步迭代法的一般格式是

$equation?tex=x%5e%7b%28k%2b1%29%7d%3dbx%5e%7b%28k%29%7d%2bf%2ck%3d0%2c1%2c...$ ,

$equation?tex=x%5e%7b%280%29%7d$ 是迭代初值，矩阵

$equation?tex=b$ 被称为

迭代矩阵.

任意给定初值后，由上述迭代格式可以确定一列向量

$equation?tex=%5c%7bx%5e%7b%28k%29%7d%5c%7d_%7bk%3d1%7d%5e%7b%5cinfty%7d$ ,若有

$equation?tex=%5clim_%7bk+%5crightarrow+%5cinfty%7d+x%5e%7b%28k%29%7d%3dx%5e%2a$ ，则称迭代格式是

收敛的.

若迭代格式收敛，在迭代格式两端取极限，得

$equation?tex=x%5e%2a%3dbx%5e%2a%2bf$ ,为了由此方程得到原方程得解，我们引入相容性的概念：称

$equation?tex=ax%3db$ 与方程

$equation?tex=x%5e%2a%3dbx%5e%2a%2bf$ 是

相容的，若存在可逆n阶方阵

$equation?tex=g$ ，使得

$equation?tex=g%28i-b%29%3da%2cgf%3db$ 。可以看出，若相容性条件满足，迭代所得的极限就是原方程的解.

下面给出迭代收敛的充要条件

定理1.1 任给初值
$equation?tex=x%5e%7b%280%29%7d$ ,迭代格式

$equation?tex=x%5e%7b%28k%2b1%29%7d%3dbx%5e%7b%28k%29%7d%2bf%2ck%3d0%2c1%2c...$ 收敛的充要条件是迭代矩阵

$equation?tex=b$ 的谱半径

$equation?tex=%5crho%28b%29%3c1$ .

实际应用中，谱半径的计算是非常困难的，注意到矩阵的谱半径与矩阵范数的关系，可以给出下面的更易行的收敛性判据和先验与后验误差估计.

定理1.2 若存在由某向量范数
$equation?tex=%7c%7c%c2%b7%7c%7c$ 诱导出的矩阵范数

$equation?tex=%7c%7c%c2%b7%7c%7c$ ,使得

$equation?tex=%7c%7cb%7c%7c%3c1$ ,则迭代法收敛，且有下列误差估计式

$equation?tex=%7c%7cx%5e%7b%28k%29%7d-x%5e%2a%7c%7c+%5cleq+%5cfrac%7b%7c%7cb%7c%7c%5ek%7d%7b1-%7c%7cb%7c%7c%7d+%7c%7cx%5e%7b%281%29%7d-x%5e%7b%280%29%7d%7c%7c%2ck%3d1%2c2%2c...$ （1）

$equation?tex=%7c%7cx%5e%7b%28k%29%7d-x%5e%2a%7c%7c+%5cleq+%5cfrac%7b%7c%7cb%7c%7c%7d%7b1-%7c%7cb%7c%7c%7d+%7c%7cx%5e%7b%28k%29%7d-x%5e%7b%28k-1%29%7d%7c%7c%2ck%3d1%2c2%2c...$ （2）

上面第一个式子叫做先验误差估计，即可以通过最初两步的迭代值估计出第k步与真值的误差.第二个式子叫做后验误差估计，即可以通过最近算完的k和k-1两步估计出k步与真值的误差.

在实际应用中，计算机只能计算有限步，故我们采用有限次迭代后的结果逼近真实解.上面两式给出了逼近的误差估计。若要求误差不超过

$equation?tex=%5cepsilon$ ，当迭代序列

$equation?tex=x%5e%7b%28k%29%7d$ 逼近真实解时，

$equation?tex=%7c%7cx%5e%7b%28k%29%7d-x%5e%7b%28k-1%29%7d%7c%7c$ 已经很小了，（2）式中的系数

$equation?tex=%5cfrac%7b%7c%7cb%7c%7c%7d%7b1-%7c%7cb%7c%7c%7d$ 若忽略不计，可以得到迭代时的中止条件

$equation?tex=%7c%7cx%5e%7b%28k%29%7d-x%5e%7b%28k-1%29%7d%7c%7c+%3c+%5cepsilon$ ，这个条件容易编程实现.

观察(1)式可见，迭代法的收敛速度估计可由

$equation?tex=%7c%7cb%7c%7c$ 来决定，定义

$equation?tex=r_k%28b%29%3d-ln+%5csqrt%5bk%5d%7b%7c%7cb%5ek%7c%7c%7d$ ,来刻画

收敛速度.但是对于不同的迭代矩阵，随着k的值不同，迭代速度常常没有固定的大小关系，为此我们定义 渐进收敛速度：

$equation?tex=r_%7b%5cinfty%7d%28b%29%3d%5clim_%7bk+%5crightarrow+%5cinfty%7d+r_k%28b%29$ .进一步我们有下面的定理：

定理 1.3 若单步迭代法的迭代矩阵为
$equation?tex=b$ ，则

$equation?tex=r_%7b%5cinfty%7d%28b%29%3d-ln+%5b%5crho%28b%29%5d$ .

4.2 Jacobi迭代法

做下列约定，给定方阵

$equation?tex=a$ ，

$equation?tex=a$ 的元素可分为三类：主对角线，主对角线下的，主对角线上的。将这三类元素分开，得到矩阵

$equation?tex=a$ 的分解

$equation?tex=a%3dl%2bd%2bu$ ,其中

$equation?tex=l%ef%bc%8cd%ef%bc%8cu$ 分别是下三角，对角，上三角矩阵.

假设

$equation?tex=a$ 可逆，对方程

$equation?tex=ax%3db$ ，保留对角线元素不动，其余元素移至右边，得到

$equation?tex=dx%3d-%28l%2bu%29x%2bb$ ,等价于

$equation?tex=x%3d-d%5e%7b-1%7d%28l%2bu%29x%2bd%5e%7b-1%7db$ ,从而可以构造Jacobi迭代格式：

$equation?tex=x%5e%7b%28k%2b1%29%7d%3d-d%5e%7b-1%7d%28l%2bu%29x%5e%7b%28k%29%7d%2bd%5e%7b-1%7db+%2ck%3d0%2c1%2c...$

对于上述迭代法，我们有如下的收敛性判据

定理 2.1 若系数矩阵
$equation?tex=a$ 对称，对角元都大于零，则Jacobi迭代法收敛的充要条件是

$equation?tex=a%2c2d-a$ 都是正定矩阵.

此外还有更易于验证的充分条件

定理 2.2 若系数矩阵
$equation?tex=a$ 严格对角占优或者不可约对角占优，则Jacobi迭代法收敛.

4.3 Gauss-Seidel迭代法

改进Jacobi方法，考虑到计算

$equation?tex=x%5e%7b%28k%29%7d%3d%28x%5e%7b%28k%29%7d_1%2cx%5e%7b%28k%29%7d_2...%2cx%5e%7b%28k%29%7d_n%29%5et$ ,时使用到的全部是

$equation?tex=x%5e%7b%28k-1%29%7d$ 的分量，若先计算并更新

$equation?tex=x_1%5e%7b%28k%29%7d$ ,再将更新后的值用于计算

$equation?tex=x_2%5e%7b%28k%29%7d$ ，依次类推，最后完全计算得到

$equation?tex=x%5e%7b%28k%29%7d$ ，这就是Gauss-Seidel迭代法.

G-S迭代法有矩阵格式如下：

$equation?tex=x%5e%7b%28k%2b1%29%7d%3d-%7b%28d%2bl%29%7d%5e%7b-1%7dux%5e%7b%28k%29%7d%2b%28d%2bl%29%5e%7b-1%7db+%2ck%3d0%2c1%2c...$

类似上一节，有下面的收敛判据

定理 3.1
$equation?tex=a$ 实对称且正定，则G-S迭代法收敛.
定理 3.2
$equation?tex=a$ 严格对角占优或不可约对角占优，则G-S迭代法收敛.

4.4 JOR迭代

逐次超松弛迭代(Successive Overrelaxation Iteration ) 是用于加速经典迭代格式的一种技术，通过引入适当的松弛因子来加快收敛速度.

本节以应用于Jacobi迭代来阐明此加速技术，得到JOR迭代法.

以下凡涉及某矩阵的逆，都假设其存在.

Jacobi迭代有等价形式

$equation?tex=x%5e%7b%28k%2b1%29%7d%3dx%5e%7b%28k%29%7d-d%5e%7b-1%7d%28ax%5e%7b%28k%29%7d-b%29+$

相邻两项差值

$equation?tex=%5cdelta_k%3dx%5e%7b%28k%2b1%29%7d-x%5e%7b%28k%29%7d%3d-d%5e%7b-1%7d%28ax%5e%7b%28k%29%7d-b%29+$ ,对差值引入松弛因子

$equation?tex=%5comega$ ,得到

$equation?tex=x%5e%7b%28k%2b1%29%7d%3dx%5e%7b%28k%29%7d-%5comega+d%5e%7b-1%7d%28ax%5e%7b%28k%29%7d-b%29+$ ,整理即得

JOR迭代格式：

$equation?tex=x%5e%7b%28k%2b1%29%7d%3d%28i-%5comega+d%5e%7b-1%7da%29x%5e%7b%28k%29%7d%2b%5comega+d%5e%7b-1%7db$

自然地，我们期望随着松弛因子不同，收敛的速度会发生改变，那么松弛因子取什么值最佳？下面的定理回答了这个问题.

定理 4.1 当Jacobi迭代法的迭代矩阵
$equation?tex=b_j$ 特征值为实数，且谱半径小于1时，JOR迭代法有最佳松弛因子

$equation?tex=%5comega_%7bopt%7d%3d%5cfrac%7b2%7d%7b2-%5clambda_m-%5clambda_m%7d$ ,其中

$equation?tex=%5clambda_m%2c%5clambda_m$ 是

$equation?tex=b_j$ 的最小和最大特征值.此外，若

$equation?tex=%5clambda_m+%5cneq+-%5clambda_m$ 时，JOR迭代的收敛速度快于Jacobi迭代.

下面是JOR迭代收敛性判据

定理 4.2
$equation?tex=a$ 具有正对角元且对称，则JOR法收敛的充要条件是

$equation?tex=a%2c2%5comega+%5e%7b-1%7d+d-a$ 均正定.
定理 4.3 若已有Jacobi迭代法收敛且
$equation?tex=%5comega+%5cin+%280%2c1%5d$ ，则JOR法收敛.

具体地，我们有下列定理

定理 4.4 若
$equation?tex=a$ 严格对角占优或不可约对角占优，则松弛因子

$equation?tex=%5comega+%5cin+%280%2c1%5d$ 的JOR迭代法收敛.

4.5 SOR迭代

本节将逐次超松弛迭代技术用于G-S迭代法，得到SOR迭代法.

将G-S迭代格式改写为

$equation?tex=dx%5e%7b%28k%2b1%29%7d%3ddx%5e%7b%28k%29%7d%2b%5b%7bb-lx%5e%7b%28k%2b1%29%7d-%28d%2bu%29%7dx%5e%7b%28k%29%7d%5d$ ,对上式引入松弛因子得到

$equation?tex=dx%5e%7b%28k%2b1%29%7d%3ddx%5e%7b%28k%29%7d%2b+%5comega+%5b%7bb-lx%5e%7b%28k%2b1%29%7d-%28d%2bu%29%7dx%5e%7b%28k%29%7d%5d$ ，整理得SOR迭代

$equation?tex=x%5e%7b%28k%2b1%29%7d%3d%28d%2b+%5comega+l%29%5e%7b-1%7d+%5c%7b+%5b%281-+%5comega+%29d-+%5comega+u%5dx%5e%7b%28k%29%7d%2b%5comega+b+%5c%7d$ .

对于收敛性，我们有下面的定理

定理 5.1 SOR法收敛的必要条件是
$equation?tex=0+%3c+%5comega+%3c2$ .
定理 5.2 当
$equation?tex=a$ 对称正定时，

$equation?tex=0+%3c+%5comega+%3c2$ 是SOR法收敛的充要条件.
定理 5.3 当
$equation?tex=a$ 严格对角占优或不可约对角占优，则

$equation?tex=%5comega+%5cin+%280%2c1%5d$ 时SOR法收敛.