搜索

逐次超松驰迭代法

数学术语

D. M. Young于20世纪70年代提出逐次超松弛(Successive Over Relaxation)迭代法，简称SOR方法，是一种经典的迭代算法。它是为了解决大规模系统的线性等式提出来的，在GS法基础上为提高收敛速度，采用加权平均而得到的新算法。由于超松弛迭代法公式简单，编制程序容易，很多工程学、计算数学中都会应用超松弛迭代方法。使用超松弛迭代法的关键在于选取合适的松弛因子，如果松弛因子选取合适，则会大大缩短计算时间。

简介
为解决实际问题中大维数线性代数方程组的求解问题，提出了许多迭代法。但大多数迭代法不是对各类线性方程组都有收敛性。在解题时，对原方程组矩阵作一根本的变换，从而可能使条件数变坏，也可能破坏了变换前后方程组的等价性，以及丧失使原方程组的对称性等。通过对GS法进行改进，从而产生了逐次超松弛(SOR)迭代法。
SOR方法的思路为：如果能够简单有效地确定单个样本加入样本集后对训练结果的影响，一方面，出现新的样本时可以利用原来的一训练结果而不必重新开始；另一方面，让训练样本逐个进入样本集可以简化寻优过程，提高算法速度。这实际上是将样本集中的样本数减少到一个。
对于逐次超松弛迭代法，松弛因子的选取对算法的收敛速度有很大影响，通常对于方程组Ax=Y，若A为正定矩阵，则当0< <2时，逐次超松弛迭代恒收敛。
逐次超松弛迭代法与Jacobi迭代法、Seidel迭代法等相比收敛速度较快。由逐次超松弛迭代法求出的方程组的数值解具有较高的精确性。逐次超松弛迭代法可以大大减少计算量和计算机的内存储量，从而提高计算效率。逐次超松弛迭代法可以广泛地应用于实际，如支持向量机算法中求最大分类间隔的二次规划问题、解高阶稀疏线性方程组等。
逐次超松弛迭代法的定义
设已求得n元线性代数方程组Ax=b第k -1次迭代向量 及第k次迭代向量 的分量 ，要计算分量 。
(1) 用Gauss-Seidel(GS)迭代求得： ；
(2) 计算 与第k -1次迭代值 的加权平均 作为第k次迭代值：
或整理成： ， 。
其中，参数 称为松弛因子，0< <2。当 >1时，上式称为逐次超松弛迭代法；当 =1时，上式为Gauss-Seidel迭代法；当0< <1时，上式称为低松弛迭代法。
逐次超松弛迭代法的收敛性判别
收敛性判别条件
SOR迭代法收敛的充分必要条件是ρ(λω)<1，ρ(λω)与松弛因子ω有关。ρ(λω)与ω的关系以及SOR方法收敛的条件有如下定理。
定理1：(Kahan)对任意的A ，设其对角元皆非零，则对所有实数ω，有：ρ(λω)≥ ω-1。
推论：如果解Ax=b的SOR方法收敛，则有ω-1<1，即0<ω<2。
定理2：(Ostrowski-Reich)设A ，A对称正定，且0<ω<2，则解Ax=b的SOR方法收敛。
收敛速度的估计
SOR迭代法的迭代矩阵λω与ω有关，当选取不同的ω时，其迭代速度也有所不同。因此，需要找到最优的松弛因子 ，使对应 的SOR方法收敛最快。
定理3　设A ，A=D-L-U为LU分解。如果存在排列矩阵P，使：
其中， 、 为对角方阵，则称A是2-循环的。此外，若当 ≠0时，矩阵 的特征值都和 无关，则称A是相容次序矩阵。
定理4：设A ，A有非零的对角元，且是2-循环和相容次序的；又设 是方程组Ax=b的Jacobi迭代的迭代矩阵，且 的所有特征值均在[0,1)上。记μ=ρ(B)及 。则方程组的SOR方法迭代矩阵的谱半径ρ(λω)满足：
且当0<ω< 时，ρ(λω)是ω的单调减函数，并有
逐次超松弛迭代法松弛因子的选取
SOR迭代方法中松弛因子的取值直接影响到算法的收敛性及收敛速度。若选择得当，可以加快收敛速度，甚至可以使发散的迭代变成收敛。因此，松弛因子取值的选取是SOR方法能否成功的关键。为了保证迭代过程的收敛，必须要求o< <2，对超松弛法去1< <2。只有在系数矩阵具有少数特殊类型的情况下，才能通过数学公式确定松弛因子。对于一般情况，有如下取值方法。
二分比较法
将松弛因子 的区间(1，2)进行二分，每个小区间的长度为1/2， 取区间中点值3/2，按照SOR迭代公式迭代，求出迭代次数k。如果k不超过指定的发散常数，则可确定 的值；否则将(1，2)区间四等分，每个小区间的长度为1/4， 取各分点的值，继续迭代。一般地，将区间(1，2)二分M次，每次二分步长为 ， 依次取各二分点的值，按照SOR迭代公式迭代，并求出迭代次数k值。如果k值不超过指定的发散常数，则可确定 的值，这样总能找到一个不超过指定发散常数的 值。算法描述如下：
(1) 给定发散常数RADIATl0N的值，令二分次数M的初始值为1；
(2)将区间(1，2)二分M次，每次二分的步长为 ， 取各二分点的值；
(3) 对每一个二分点SOR迭代公式迭代求出迭代次数k；
(4) 比较各二分点的k值找出最少迭代次数的 值；
(5) 判断若 小于RADIATl0N，则结束；否则二分次数M++，转步骤(2)继续二分。
逐步搜索法
将 的取值区间(1，2)进行M等分， 分别取 。通过SOR迭代公式依次对同一个精度要求求出迭代次数k的值，并从中选出最优松弛因子 的值。算法描述如下：
(1) 给定等分数M和精度要求的值，令的初始值为1；
(2) 令p=1，2，…，M一1，重复步骤(3)-(5)；
(3) ；
(4) 按照如下公式迭代：
其中，。找出符合精度要求的迭代次数；
(5)比较找出使值最小的，即为最优松弛因子的值。
黄金分割法
依据黄金分割法的思想，通过计算机自动选取最优松弛因子的近似值，算法描述如下：
(1) 对(1，2)区间第一次0.618的分割，区间边界a1=1，b1=2，在(a1，b1)区间分割出黄金t1=a1+0.618(b1-a1)，进行SOR法的迭代，求出迭代次数k值。如果迭代次数没有超出规定的发散常数，迭代结束；否则转步骤(2)。
(2) 在(1，1.618)和(1.618，2)之间进行第二次的黄金分割，找出分割点t2=a2+0.618(b2-a2)，其中a2和b2是新分割区间的左右边界。找出迭代次数最少的。发散则改变区间继续进行黄金分割。
MATLAB实例程序（解线性方程组）
%---逐次超松弛迭代法-----
%---successive over-reaxation iteration method
clear;clc;
A=[10,-1,-2;-1,10,-2;-1,-1,5];
b=[72,83,42]';
N=length(b); %解向量的维数
fprintf('库函数计算结果：');
x=inv(A)*b %库函数计算结果
x=zeros(N,1);%迭代初始值
%-----(A=D-E-F)------
D=diag(diag(A));
E=-tril(A,-1);%下三角
F=-triu(A,1);%上三角
w=1.1; %松弛因子，一般0
B=inv(D-w*E)*[(1-w)*D+w*F];g=w*inv(D-w*E)*b;
eps=0.00001;%相邻解的距离小于该数时，结束迭代
%--------开始迭代-------
for k=1:100 %最大迭代次数为100
fprintf('第%d次迭代：',k);
y=B*x+g;
if abs(x-y)
break;
end
x=y
end
x
全国各地天气预报查询

上海市

  • 市辖区

    • 云南省

  • 临沧市

    • 云南省

  • 丽江市

    • 云南省

  • 保山市

    • 云南省

  • 大理白族自治州

    • 云南省

  • 德宏傣族景颇族自治州

    • 云南省

  • 怒江傈僳族自治州

    • 云南省

  • 文山壮族苗族自治州

    • 云南省

  • 昆明市

    • 云南省

  • 昭通市

    • 云南省

  • 普洱市

    • 云南省

  • 曲靖市

    • 云南省

  • 楚雄彝族自治州

    • 云南省

  • 玉溪市

    • 云南省

  • 红河哈尼族彝族自治州

    • 云南省

  • 西双版纳傣族自治州

    • 云南省

  • 迪庆藏族自治州

    • 内蒙古自治区

  • 乌兰察布市

    • 内蒙古自治区

  • 乌海市

    • 内蒙古自治区

  • 兴安盟

    • 内蒙古自治区

  • 包头市

    • 内蒙古自治区

  • 呼伦贝尔市

    • 内蒙古自治区

  • 呼和浩特市

    • 内蒙古自治区

  • 巴彦淖尔市

    • 内蒙古自治区

  • 赤峰市

    • 内蒙古自治区

  • 通辽市

    • 内蒙古自治区

  • 鄂尔多斯市

    • 内蒙古自治区

  • 锡林郭勒盟

    • 内蒙古自治区

  • 阿拉善盟

    • 北京市

  • 市辖区

    • 吉林省

  • 吉林市

    • 吉林省

  • 四平市

    • 吉林省

  • 延边朝鲜族自治州

    • 吉林省

  • 松原市

    • 吉林省

  • 白城市

    • 吉林省

  • 白山市

    • 吉林省

  • 辽源市

    • 吉林省

  • 通化市

    • 吉林省

  • 长春市

    • 四川省

  • 乐山市

    • 四川省

  • 内江市

    • 四川省

  • 凉山彝族自治州

    • 四川省

  • 南充市

    • 四川省

  • 宜宾市

    • 四川省

  • 巴中市

    • 四川省

  • 广元市

    • 四川省

  • 广安市

    • 四川省

  • 德阳市

    • 四川省

  • 成都市

    • 四川省

  • 攀枝花市

    • 四川省

  • 泸州市

    • 四川省

  • 甘孜藏族自治州

    • 四川省

  • 眉山市

    • 四川省

  • 绵阳市

    • 四川省

  • 自贡市

    • 四川省

  • 资阳市

    • 四川省

  • 达州市

    • 四川省

  • 遂宁市

    • 四川省

  • 阿坝藏族羌族自治州

    • 四川省

  • 雅安市

    • 天津市

  • 市辖区

    • 宁夏回族自治区

  • 中卫市

    • 宁夏回族自治区

  • 吴忠市

    • 宁夏回族自治区

  • 固原市

    • 宁夏回族自治区

  • 石嘴山市

    • 宁夏回族自治区

  • 银川市

    • 安徽省

  • 亳州市

    • 安徽省

  • 六安市

    • 安徽省

  • 合肥市

    • 安徽省

  • 安庆市

    • 安徽省

  • 宣城市

    • 安徽省

  • 宿州市

    • 安徽省

  • 池州市

    • 安徽省

  • 淮北市

    • 安徽省

  • 淮南市

    • 安徽省

  • 滁州市

    • 安徽省

  • 芜湖市

    • 安徽省

  • 蚌埠市

    • 安徽省

  • 铜陵市

    • 安徽省

  • 阜阳市

    • 安徽省

  • 马鞍山市

    • 安徽省

  • 黄山市

    • 山东省

  • 东营市

    • 山东省

  • 临沂市

    • 山东省

  • 威海市

    • 山东省

  • 德州市

    • 山东省

  • 日照市

    • 山东省

  • 枣庄市

    • 山东省

  • 泰安市

    • 山东省

  • 济南市

    • 山东省

  • 济宁市

    • 山东省

  • 淄博市

    • 山东省

  • 滨州市

    • 山东省

  • 潍坊市

    • 山东省

  • 烟台市

    • 山东省

  • 聊城市

    • 山东省

  • 菏泽市

    • 山东省

  • 青岛市

    • 山西省

  • 临汾市

    • 山西省

  • 吕梁市

    • 山西省

  • 大同市

    • 山西省

  • 太原市

    • 山西省

  • 忻州市

    • 山西省

  • 晋中市

    • 山西省

  • 晋城市

    • 山西省

  • 朔州市

    • 山西省

  • 运城市

    • 山西省

  • 长治市

    • 山西省

  • 阳泉市

    • 广东省

  • 东莞市

    • 广东省

  • 中山市

    • 广东省

  • 云浮市

    • 广东省

  • 佛山市

    • 广东省

  • 广州市

    • 广东省

  • 惠州市

    • 广东省

  • 揭阳市

    • 广东省

  • 梅州市

    • 广东省

  • 汕头市

    • 广东省

  • 汕尾市

    • 广东省

  • 江门市

    • 广东省

  • 河源市

    • 广东省

  • 深圳市

    • 广东省

  • 清远市

    • 广东省

  • 湛江市

    • 广东省

  • 潮州市

    • 广东省

  • 珠海市

    • 广东省

  • 肇庆市

    • 广东省

  • 茂名市

    • 广东省

  • 阳江市

    • 广东省

  • 韶关市

    • 广西壮族自治区

  • 北海市

    • 广西壮族自治区

  • 南宁市

    • 广西壮族自治区

  • 崇左市

    • 广西壮族自治区

  • 来宾市

    • 广西壮族自治区

  • 柳州市

    • 广西壮族自治区

  • 桂林市

    • 广西壮族自治区

  • 梧州市

    • 广西壮族自治区

  • 河池市

    • 广西壮族自治区

  • 玉林市

    • 广西壮族自治区

  • 百色市

    • 广西壮族自治区

  • 贵港市

    • 广西壮族自治区

  • 贺州市

    • 广西壮族自治区

  • 钦州市

    • 广西壮族自治区

  • 防城港市

    • 新疆维吾尔自治区

  • 乌鲁木齐市

    • 新疆维吾尔自治区

  • 伊犁哈萨克自治州

    • 新疆维吾尔自治区

  • 克孜勒苏柯尔克孜自治州

    • 新疆维吾尔自治区

  • 克拉玛依市

    • 新疆维吾尔自治区

  • 博尔塔拉蒙古自治州

    • 新疆维吾尔自治区

  • 吐鲁番市

    • 新疆维吾尔自治区

  • 和田地区

    • 新疆维吾尔自治区

  • 哈密市

    • 新疆维吾尔自治区

  • 喀什地区

    • 新疆维吾尔自治区

  • 塔城地区

    • 新疆维吾尔自治区

  • 巴音郭楞蒙古自治州

    • 新疆维吾尔自治区

  • 昌吉回族自治州

    • 新疆维吾尔自治区

  • 自治区直辖县级行政区划

    • 新疆维吾尔自治区

  • 阿克苏地区

    • 新疆维吾尔自治区

  • 阿勒泰地区

    • 江苏省

  • 南京市

    • 江苏省

  • 南通市

    • 江苏省

  • 宿迁市

    • 江苏省

  • 常州市

    • 江苏省

  • 徐州市

    • 江苏省

  • 扬州市

    • 江苏省

  • 无锡市

    • 江苏省

  • 泰州市

    • 江苏省

  • 淮安市

    • 江苏省

  • 盐城市

    • 江苏省

  • 苏州市

    • 江苏省

  • 连云港市

    • 江苏省

  • 镇江市

    • 江西省

  • 上饶市

    • 江西省

  • 九江市

    • 江西省

  • 南昌市

    • 江西省

  • 吉安市

    • 江西省

  • 宜春市

    • 江西省

  • 抚州市

    • 江西省

  • 新余市

    • 江西省

  • 景德镇市

    • 江西省

  • 萍乡市

    • 江西省

  • 赣州市

    • 江西省

  • 鹰潭市

    • 河北省

  • 保定市

    • 河北省

  • 唐山市

    • 河北省

  • 廊坊市

    • 河北省

  • 张家口市

    • 河北省

  • 承德市

    • 河北省

  • 沧州市

    • 河北省

  • 石家庄市

    • 河北省

  • 秦皇岛市

    • 河北省

  • 衡水市

    • 河北省

  • 邢台市

    • 河北省

  • 邯郸市

    • 河南省

  • 三门峡市

    • 河南省

  • 信阳市

    • 河南省

  • 南阳市

    • 河南省

  • 周口市

    • 河南省

  • 商丘市

    • 河南省

  • 安阳市

    • 河南省

  • 平顶山市

    • 河南省

  • 开封市

    • 河南省

  • 新乡市

    • 河南省

  • 洛阳市

    • 河南省

  • 漯河市

    • 河南省

  • 濮阳市

    • 河南省

  • 焦作市

    • 河南省

  • 省直辖县级行政区划

    • 河南省

  • 许昌市

    • 河南省

  • 郑州市

    • 河南省

  • 驻马店市

    • 河南省

  • 鹤壁市

    • 浙江省

  • 丽水市

    • 浙江省

  • 台州市

    • 浙江省

  • 嘉兴市

    • 浙江省

  • 宁波市

    • 浙江省

  • 杭州市

    • 浙江省

  • 温州市

    • 浙江省

  • 湖州市

    • 浙江省

  • 绍兴市

    • 浙江省

  • 舟山市

    • 浙江省

  • 衢州市

    • 浙江省

  • 金华市

    • 海南省

  • 三亚市

    • 海南省

  • 三沙市

    • 海南省

  • 儋州市

    • 海南省

  • 海口市

    • 海南省

  • 省直辖县级行政区划

    • 湖北省

  • 十堰市

    • 湖北省

  • 咸宁市

    • 湖北省

  • 孝感市

    • 湖北省

  • 宜昌市

    • 湖北省

  • 恩施土家族苗族自治州

    • 湖北省

  • 武汉市

    • 湖北省

  • 省直辖县级行政区划

    • 湖北省

  • 荆州市

    • 湖北省

  • 荆门市

    • 湖北省

  • 襄阳市

    • 湖北省

  • 鄂州市

    • 湖北省

  • 随州市

    • 湖北省

  • 黄冈市

    • 湖北省

  • 黄石市

    • 湖南省

  • 娄底市

    • 湖南省

  • 岳阳市

    • 湖南省

  • 常德市

    • 湖南省

  • 张家界市

    • 湖南省

  • 怀化市

    • 湖南省

  • 株洲市

    • 湖南省

  • 永州市

    • 湖南省

  • 湘潭市

    • 湖南省

  • 湘西土家族苗族自治州

    • 湖南省

  • 益阳市

    • 湖南省

  • 衡阳市

    • 湖南省

  • 邵阳市

    • 湖南省

  • 郴州市

    • 湖南省

  • 长沙市

    • 甘肃省

  • 临夏回族自治州

    • 甘肃省

  • 兰州市

    • 甘肃省

  • 嘉峪关市

    • 甘肃省

  • 天水市

    • 甘肃省

  • 定西市

    • 甘肃省

  • 平凉市

    • 甘肃省

  • 庆阳市

    • 甘肃省

  • 张掖市

    • 甘肃省

  • 武威市

    • 甘肃省

  • 甘南藏族自治州

    • 甘肃省

  • 白银市

    • 甘肃省

  • 酒泉市

    • 甘肃省

  • 金昌市

    • 甘肃省

  • 陇南市

    • 福建省

  • 三明市

    • 福建省

  • 南平市

    • 福建省

  • 厦门市

    • 福建省

  • 宁德市

    • 福建省

  • 泉州市

    • 福建省

  • 漳州市

    • 福建省

  • 福州市

    • 福建省

  • 莆田市

    • 福建省

  • 龙岩市

    • 西藏自治区

  • 山南市

    • 西藏自治区

  • 拉萨市

    • 西藏自治区

  • 日喀则市

    • 西藏自治区

  • 昌都市

    • 西藏自治区

  • 林芝市

    • 西藏自治区

  • 那曲市

    • 西藏自治区

  • 阿里地区

    • 贵州省

  • 六盘水市

    • 贵州省

  • 安顺市

    • 贵州省

  • 毕节市

    • 贵州省

  • 贵阳市

    • 贵州省

  • 遵义市

    • 贵州省

  • 铜仁市

    • 贵州省

  • 黔东南苗族侗族自治州

    • 贵州省

  • 黔南布依族苗族自治州

    • 贵州省

  • 黔西南布依族苗族自治州

    • 辽宁省

  • 丹东市

    • 辽宁省

  • 大连市

    • 辽宁省

  • 抚顺市

    • 辽宁省

  • 朝阳市

    • 辽宁省

  • 本溪市

    • 辽宁省

  • 沈阳市

    • 辽宁省

  • 盘锦市

    • 辽宁省

  • 营口市

    • 辽宁省

  • 葫芦岛市

    • 辽宁省

  • 辽阳市

    • 辽宁省

  • 铁岭市

    • 辽宁省

  • 锦州市

    • 辽宁省

  • 阜新市

    • 辽宁省

  • 鞍山市

    • 重庆市

  • 县

    • 重庆市

  • 市辖区

    • 陕西省

  • 咸阳市

    • 陕西省

  • 商洛市

    • 陕西省

  • 安康市

    • 陕西省

  • 宝鸡市

    • 陕西省

  • 延安市

    • 陕西省

  • 榆林市

    • 陕西省

  • 汉中市

    • 陕西省

  • 渭南市

    • 陕西省

  • 西安市

    • 陕西省

  • 铜川市

    • 青海省

  • 果洛藏族自治州

    • 青海省

  • 海东市

    • 青海省

  • 海北藏族自治州

    • 青海省

  • 海南藏族自治州

    • 青海省

  • 海西蒙古族藏族自治州

    • 青海省

  • 玉树藏族自治州

    • 青海省

  • 西宁市

    • 青海省

  • 黄南藏族自治州

    • 黑龙江省

  • 七台河市

    • 黑龙江省

  • 伊春市

    • 黑龙江省

  • 佳木斯市

    • 黑龙江省

  • 双鸭山市

    • 黑龙江省

  • 哈尔滨市

    • 黑龙江省

  • 大兴安岭地区

    • 黑龙江省

  • 大庆市

    • 黑龙江省

  • 牡丹江市

    • 黑龙江省

  • 绥化市

    • 黑龙江省

  • 鸡西市

    • 黑龙江省

  • 鹤岗市

    • 黑龙江省

  • 黑河市

    • 黑龙江省

  • 齐齐哈尔市