SOR迭代法收敛性判定

迭代法的收敛性与误差估计一…的童滚.11/{安务刊迭代法的收敛性.与误差估计’\虞福星..Z冬}7.在许多工程技术问题中,常常会遇到求解一元非线性方程的问题.例如,代数方程一x—l一0或超越方程x+{x—l看上去形式很简单,但不易求出其准确根,只能求出方程达到一定精度的近似根.求解这类方程的方法很多,迭代法就是其中的一种.迭代法有许多优点:1.其算法的逻辑结构简单f2.收敛速度快I3.中间结果有扰动不会影响计算结论;4.计算误差容易控制.正因为如此,迭代法得到非常广泛的应用.一,迭代法的基本思想设有方程f(11=0首先,我们设法将式(1)代成下列等价形式x—g∽然后按式(2)构造迭代公式(1)(2)+l—g{-,k=o,1,2, (3)从给定的初始近似根x.出发,按迭代公式(3)可以得到一个敦列x.,x1,x2,...,x, (4)如果这个数列{}有极限,则称迭代公式(3)是收敛的,此时数列螅极限x=limx就是原方程(1)的根.二,迭代法的收敛性及误差估计具备怎样的条件,迭代公式(3)是收敛的,这就是我们要讨论的中心问题.对此,我们有定理:设方程x—g在(a,b)内有根x,若gt满足李普希茨条件,即对(a,b)内任意的x】和都有lg(x1)g(x2)l≤qlxl—x2l(5)q为某个正数,当q<1时,则方程在(a’b)内有唯一的根I且迭代公式(3)对任意初始近似值xo均收敛于根x;还有误差估计式一≤lXk--Xkil≤lXI--Xol(6)证明:先证唯一性由已知条件知,x’是方程x—g的根,即x一g66设i也是方程x=g(x)的根,则x=g于是1x一i1=1g)--g1由李普希茨条件,得1x一;1一Ig(-～g’;I≤q1x一il因为0<q<1,故必有x.=;,根的唯一性得证. 再证收敛性由李普希茨条件,得IXk+I--X.l=Ig’--g)l≤qI一x.I同样l一x’l≤qIXk一1一x.1,…,1x1--X.1≤qI～x’1于是有1+I—x’I≤?Ix.一x’1因为0<q<1,当k—o.时,一0,即有Ix…--X’j—O(k—oo)所以,limxx.k一收敛性得证.利用李普希茨条件,得l+1～f=fg’)--g(,一.I≤Ix,一一1I于是对任意正整数P,有l+p一1≤1Xk—p一+rII+1Xk+p一1--Xk+p一±1+…+1一1一I≤(q+qP 一+…+q)?j一l一lxr令P—oo,得一I≤一一l≤IX1--X0I三,选择迭代公式的原则如果方程(2)中的g’满足Ig’I]l≤M<IxE(a,b)则可取这里的M作为李普希茨(5)中的q,由式(6)可知,正数q越小,收敛速度越快.所以,选遗代公式要遵循使IgI在(a山)的最大值M为最小这个原则.由于把方程f㈨一0化成等价形式x;g的方法很多.例如,方程x一x一1—0可以化成以下四种形式(1)x一一167(2)x一+1㈣x=X--每=㈤x一一由此可得四个迭代公式x+?=x:一1(7);(8):(9)’(9)l一—)(,)式(1I)也可用牛顿切线法导出,可见牛顿切线法可视为谴代法的特殊情形.由于=苎【)所以.f(?f().因此,只要ll≤q<l,L”)J公式(II)就收敛68。

计算科学中的迭代和收敛性分析在计算科学中，迭代和收敛性分析是两个常见的概念。

迭代是指通过重复执行一定的计算过程来逐步逼近所要求解的问题的方法。

而收敛性则是评估所得解与真实解之间的误差以及迭代过程中的精度变化。

迭代方法在计算科学中的应用非常广泛。

例如，在求解非线性方程和求解常微分方程等问题中，常用的方法都是迭代法。

迭代法的基本思想是从初始条件开始，逐步逼近所要求解的问题。

具体操作时，首先需要选定一个初始值，然后通过一定的迭代公式进行计算，得到一个新的值，并将其作为下一次迭代时的初始值。

如此重复执行，直到所求解的问题达到所期望的精度要求为止。

然而，迭代方法并不总是能够收敛到所要求的真实解。

这就引出了收敛性分析的问题。

收敛性指的是迭代方法是否在无限迭代的情况下，能够收敛到真实解。

如果能够收敛，那么我们还需要考虑的是其收敛速度，即迭代过程中精度变化的规律。

在实际应用中，迭代法的收敛性和收敛速度是非常重要的问题，因为它们直接影响到所得结果的可靠性和计算效率。

因此，在迭代法的设计和评估中，收敛性分析是一个非常重要的环节。

收敛性分析的方法很多。

其中，最常用的方法是通过构造数值序列来评估迭代法的收敛性和收敛速度。

构造数值序列可以通过一系列数学技巧和推导来实现。

对于线性问题，可以通过构造矩阵和向量来实现数值序列的构造。

而对于非线性问题，一般需要考虑一些特定的方法，如牛顿迭代法、欧拉迭代法等。

除了构造数值序列外，在收敛性分析中还有一些其他的方法。

例如，可以考虑迭代法的局部收敛性和全局收敛性。

局部收敛性是指迭代法在某一点附近是否收敛。

这个问题往往可以通过利用泰勒级数来解决。

而全局收敛性则是指迭代法是否对任意的初始值都能收敛。

这个问题的解决通常需要使用一些特定的技巧和算法，例如逐步缩小逼近区间法。

总之，迭代和收敛性分析是计算科学中常见的概念，对于许多实际问题的求解都有重要的应用价值。

通过对迭代法的设计、评估和分析，我们可以帮助提高计算效率和解决实际问题，为科学研究和工程应用做出贡献。

数值分析期末复习资料数值分析期末复习题型：一、填空 二、判断 三、解答（计算） 四、证明第一章误差与有效数字一、有效数字1、定义：若近似值X*的误差限是某一位的半个单位，该位到x*的第一位非零数字共有n 位，就说x*有n 位有效数字。

2、两点理解：（1） 四舍五入的一定是有效数字（2） 绝对误差不会超过末位数字的半个单位eg. ・§丄％ 3、 定理1 （P6）：若x*具有n 位有效数字，则其相对误差虧疗茲T 4、考点：（1）计算有效数字位数：一个根据定义理解，一个根据定理1 （P7例题3） 二、避免误差危害原则 1、原则:（1） 避免大数吃小数（方法：从小到大相加；利用韦达定理：xl*x2= c / a ） 避免相近数相减（方法：有理化）eg. V777-77 =c ・2 X2sin7 或 减少运算次数（方法：秦九韶算法）eg.P20习题14 三. 数值运算的误差估计 1、公式：（1） 一元函数：I £*（ f 3））1 Q |「（於）1・| £*（力|或其变形公式求相对误差（两边同时除以f （卅））eg. P19习题1、2、5(2) (3) ln(x + £)- In x = In 1；1 — cos X =（2）多元函数（P8） eg. P8例4, P19习题4第二章插值法一、插值条件1、定义：在区间［a, b］上，给定n+1个点，aWxoVx［V・・・VxWb的函数值yi=f(xi),求次数不超过n的多项式P(x),饋兀)=儿 i =0,1,2,…，力2、定理：满足插值条件、n+1个点、点互异、多项式次数Wn的P(x)存在且唯一二、拉格朗日插值及其余项1、n次插值基函数表达式(P26 (2.8))2、插值多项式表达式(P26 (2.9))3、插值余项(P26 (2.12))：用于误差估计4、插值基函数性质(P27 (2. 17及2. 18)) eg. P28例1三、差商(均差)及牛顿插值多项式1、差商性质(P30)：(1)可表示为函数值的线性组合(2)差商的对称性：差商与节点的排列次序无关(3)均差与导数的关系(P31 (3.5))2、均差表计算及牛顿插值多项式例：已知X=1,4,9的平方根为1,2,3,利用牛顿基本差商公式求"的近似值。

不同分裂形式的SOR与AOR迭代法收敛性比较雷刚【摘要】讨论预条件后用迭代法求解的线性方程组Ax=b.在预条件的基础上引入参数,给出一种含参数形式的非负分裂.证明这种分裂形式可以加速SOR迭代法的收敛性,而且收敛效果超过AOR迭代法的收敛性,说明这种分裂形式更好.%The iterative method to solve the linear system Ax=b in preconditioned is discussed. A kind of nonnegative split with parameter is given on the base of the preconditioned. This new splitting form is proved to accelerate SOR iterative method convergence not only better than the general iterative method, but also convergence rate surpass the AOR iterative method.【期刊名称】《西安工程大学学报》【年(卷),期】2012(026)003【总页数】4页(P384-386,396)【关键词】收敛性;SOR迭代法;AOR迭代法;M-矩阵【作者】雷刚【作者单位】宝鸡文理学院数学系,陕西宝鸡721013【正文语种】中文【中图分类】O241.6在求解大型线性方程组Ax＝b时（其中A＝（aij）n×n∈Rn×n，x，b∈Rn），通常有直接法求解和迭代法求解两种方法，随着并行计算机的快速发展，特别是当系数矩阵具有某种特点时，迭代法的优势不断的体现出来，而数学、物理中的许多问题求解归结为线性方程组时系数矩阵大多为M-矩阵.为加速和改善收敛性，许多学者采用预条件方法来处理［1－4］，也就是对方程两边左乘以非奇异矩阵P，转化为PAx＝Pb.通常设矩阵A＝I－L－U，I单位矩阵，L和U分别是严格下三角矩阵和严格上三角矩阵.那么求解方程组Ax＝b的SOR迭代法时将系数矩阵分解为相应的SOR迭代矩阵为如果将系数矩阵A分解为A＝（1／ω）｛（I－γL）－［（1－ω）I＋（ω－γ）L ＋ωU］｝，相应的AOR迭代矩阵为现考虑常用的预条件矩阵P＝（I＋S），其中a12，a23，…，an－1，n是系数矩阵A＝（aij）n×n对应位置上的元素.那么DP，－LP和－UP分别是系数矩阵PA的对角线部分、严格下三角部分和严格上三角部分组成的矩阵.为使得预条件后的矩阵分裂更具有一般性，引入参数α，将系数矩阵PA分解为可知当α＝1时，式（4）即为一般预条件后的矩阵分裂形式.相应的SOR迭代法的迭代矩阵为一般的预条件后SOR迭代法的迭代矩阵为定义1［5－6］设n×n实矩阵A＝（aij），如果对任意i＝j，有aij≥0，且任意i≠j，有aij≤0，那么称矩阵A为L-矩阵，如果矩阵A能表示为A＝sI－B，B≥0，当s≥ρ（B）时，称A为M-矩阵，特别当s＞ρ（B）时，称A为非奇异的M-矩阵；当s＝ρ（B）时，称A为奇异M-矩阵.其中ρ（B）为B的谱半径.定义2［7］设A为实矩阵，那么对A＝M－N，（1）如果M－1≥0且N≥0，称A＝M－N为正规分裂；（2）如果M－1≥0且M－1 N≥0，称A＝M－N为弱正规分裂；引理1［7］设A－1≥0，并且A＝M－N＝M′－N′是弱正规分裂.如果M－1≤M′－1，且N≥0，则ρ（M′－1 N′）≤ρ（M－1 N）.引理2［7］设A是H-矩阵，当0≤γ≤ω≤1 （ω≠0）时，ρ（TSOR）＜1，ρ（TAOR）＜1，其中TSOR，TAOR分别是SOR迭代矩阵和AOR迭代矩阵.引理3［7］设A为非负矩阵，则（1）若αx≤Ax对某一个非负向量x且x≠0成立，那么就有α≤ρ（A）；（2）若Ax≤βx对某一个正向量x成立，那么就有ρ（A）≤β，进一步，如果A不可约且有0≠αx≤Ax≤βx，αx≠Ax，Ax≠βx对某一个非负向量x成立，则α＜ρ（A）＜β.定理1 设线性方程组Ax＝b的系数矩阵A是不可约非奇异M-矩阵，且0＜ai，i＋1ai＋1，i＜1，i＝1，2，…，n－1，ω∈（0，1）时，TP和TPA分别由式（6）和（5）给出的一般预条件SOR迭代法和含参数形式的SOR迭代法的迭代矩阵，则∀ω≤α≤1，有ρ（TPA）≤ρ（TP）≤ρ（TSOR）＜1.证明预条件后的系数矩阵的分解可知由于ω≤α≤1，［DP－ωLP］和［αDP－ωLP］都是非负三角矩阵，且0≤［αDP －ωLP］≤［DP－ωLP］，所以［αDP－ωLP］－1≥［DP－ωLP］－1≥0.结合文献［1］的结论3，TP非负矩阵，从而迭代矩阵的谱半径是它特征值，且有与之相对应的非负特征向量x＝（x1，x2，…，xn）T，使得TPx＝ρ（TP）x.λ是通常形式的SOR迭代矩阵的谱半径，那么由引理2及其M-矩阵必是H-矩阵可知λ＜1，所以TPAx－ρ（TP）x≤0，利用引理3以及文献［8-9］得ρ（TPA）≤ρ（TP）≤ρ（TSOR）＜1.注1 从定理1可以看出，随着α的不断减小，迭代法的谱半径也在不断的减小，从而可以得到当α＝ω时，新分裂下的迭代法的谱半径达到最小.定理2 设线性方程组Ax＝b的系数矩阵A是不可约非奇异M-矩阵，且0＜ai，i＋1ai＋1，i＜1，i＝1，2，…，n－1，0≤γ≤ω≤1 （ω≠0）时，TPA是由式（5）给出的含参数形式的SOR迭代法的迭代矩阵，TAOR是由式（2）给出的AOR迭代法的迭代矩阵，那么∀ω≤α≤1，有ρ（TPA）≤ρ（TAOR）＜1.证明令预条件后PA＝（1／ω）｛（αDP－ωLP）－［（α－ω）DP＋ωUP］｝＝EP－FP.其中（1）证明E－1P≥0，FP≥0.假设SL＋SU＝D1＋L1＋U1；D1，L1，U1分别是矩阵SL＋SU的对角线部分、严格下三角部分和严格上三角部分.那么DP＝（I－D1），LP＝（L＋L1），UP＝（U－S＋U1），由于0＜ai，i＋1ai＋1，i＜1，所以DP≥0，LP≥0，UP≥0，结合0＜ω≤α≤1，可知EP－1≥0，FP≥0.又由于P＝（I＋S）是非奇异的非负矩阵，且对角线元素都为1，那么令MP＝（I ＋S）－1 EP，NP＝（I＋S）－1 FP可知，MP－1＝EP－1（I＋S）≥0，M1PNP ＝EP－1（I＋S）（I＋S）－1 FP＝EP－1FP≥0，从而A＝P－1 PA＝（I＋S）－1（EP－FP）＝MP－NP是矩阵A的一个弱正规分裂.另一方面，对于AOR迭代法，令A＝（1／ω）｛（I－γL）－［（1－ω）I＋（ω－γ）L＋ωU］｝＝M－N，那么M＝（1／ω）（I－γL），N＝（1／ω）［（1－ω）I＋（ω－γ）L＋ωU］.结合0≤γ≤ω≤1 （ω≠0）可知M－1≥0，N≥0，所以A＝M－N是一个正规分裂.（2）证明MP－1≥M－1.首先说明MP不可能等于M，如果MP＝（I＋S）－1 EP＝M，那么也就是（I＋S）MP＝（1／ω）（αDP－ωLP）＝（I＋S）（1／ω）（I－γL）＝（I＋S）M，那么可得这样，左边是下三角矩阵，右边是上三角含有非零元的矩阵，所以MP≠M.结合0＜ω≤α≤1，0≤γ≤ω≤1 （ω≠0），还可得到α（I－D1）－ω（L＋L1）≤I＋S－γL－γSL.也就是MP≤M，且它们都是非负的，所以MP－1≥M－1.综上，利用引理1及文献［10］有ρ（TPA）≤ρ（TAOR）＜1.例1 如果矩阵当ω＝0.6时，可以得到SOR迭代法的谱半径为ρ（TSOR）＝0.926 5，在预条件P＝（I＋S）后，SOR迭代法的谱半径ρ（TP）＝0.902 1，引入参数α＝1，0.8，0.6以后，可以得到新分裂下的SOR迭代法的谱半径为ρ（TPA）＝0.902 1，0.890 3，0.884 2，取γ＝0.5时，可以得到相应的AOR迭代法的谱半径为ρ（TAOR）＝0.912 8，符合定理2的结论.从理论上的分析和证明可以看出，预条件后含参数的分裂形式更一般，而且加速SOR迭代法的收敛效果要优于一般的SOR迭代法和一般的预条件SOR迭代法，并找到新分裂形式下参数的最优选择，然后将所得的结论与近年来常用的AOR迭代法的收敛性进行比较，证明这种新分裂的形式的收敛性更好，为运用计算机处理数值计算中的大型稀疏线性方程组的求解提供理论分析和算法设计.【相关文献】［1］ WAMG Xuezhong，HUANG Tingzhu，FU parison results on preconditioned SOR-type iterative method for Z-matrices linear systems［J］.Journal of Computational and Applied Mathematics，2007，206：726-732.［2］张拴红，畅大为.矩阵双分裂下的收敛定理与比较定理［J］.纺织高校基础科学学报，2011，24（3）：322-325.［3］刘娟宁，畅大为.预条件I＋S＋R下的AOR迭代方法［J］.纺织高校基础科学学报，2010，23（4）：396-400；438.［4］ HUNAG Tingzhu，CHENG Guanghui，CHENG Xiaoyu.Modified SOR-type iterative method for Z-matrices［J］.Applied Mathematics and Computation，2006，175：258-268.［5］ YUN Jaeheon.A note on the modified SOR method for Z-matrices［J］.Applied Mathematics and Computation，2007，194：572-576.［6］高树玲，畅大为.相容次序矩阵AOR迭代收敛的充要条件［J］.纺织高校基础科学学报，2009，22（2）：229-231.［7］张谋成，黎稳.非负矩阵论［M］.广州：广东高等教育出版社，1995.［8］康锋艳，畅大为.奇异p－循环阵块AOR迭代的半收敛性［J］.纺织高校基础科学学报，2010，23（4）：389-392.［9］雷刚.预条件（I＋S）后改进矩阵分裂的SOR迭代法收敛性分析［J］.宝鸡文理学院学报，2010，31（3）：13-17.［10］刘晓光，畅大为.（1，2）相容次序矩阵SOR迭代法的敛散性［J］.纺织高校基础科学学报，2010，23（3）：303-308.。