当前位置：文档之家 › 新的预条件USSOR迭代方法及收敛性的比较

新的预条件USSOR迭代方法及收敛性的比较

  • 格式：pdf
  • 大小：127.14 KB
  • 文档页数：4

．
维普资讯
第 ２期
王 卫 芳 等 ： 的 预条 件 ＵＳ ＯＲ迭 代 方 法 及 收 敛 性 的 比较 新 Ｓ
・１９ ・ ５
对 方程 （ ） 用 ＵＳ ＯＲ迭代 法 ， 得 的迭代 矩 阵为 １运 Ｓ 所
Ｓ ， ＝ （ 一 【） （ 一 ∞ Ｌ ［ １ Ｊ ， Ｉ ｌ ） （ 一 ） ＋ Ｌ ［ １ １ Ｉ ∞ 【］ Ｊ ］ （ 一∞ ） ＋ １， ，
Ａ 一 （ Ｊ＋ Ｓ ） — Ｉ Ｌ — Ｕ ＋ Ｓｌ Ｓ — Ｓ Ｕ — Ｄｌ Ｌｌ Ｕｌ １Ａ — — ｌ Ｌ ｌ — — ， ＡＲ一 （ Ｊ＋ Ｒ） — Ｉ Ｌ 一 【 ＋ Ｒ — ＲＬ — ＲＵ ＝ ＤＲ— ＬＲ— ＵＲ Ａ — ， ．
则在 Ｐ 下新 的 ＵＳ ＯＲ迭 代法 的迭代 矩 阵为 Ｓ
好 地 说 明选 择 适 当 的 预 条 件矩 阵 能加 快 收 敛 速 度 ． 数 值 例 子验 证 了所 得 结 论 的正 确 性 ． 用 关 键 词 ：收敛 性 ； 半径 ； 条 件 ； Ｓ Ｒ 迭 代 方 法 谱 预 ＵＳ ｏ
中 圈 分类 号 ： ２ １ ６ Ｏ ． ４ 文 献 标 识 码 ：Ａ 文 章 编 号 ：１ ０ － ７ ５ ２ Ｏ ） ２ Ｏ ５ 一 ４ ０ １ ８ ３ （ Ｏ ８ Ｏ一 ｌ８ Ｏ
：
０ 一 ｎ３ ２
：
… …
：
０ ０
：
Ｐ — ＰＲ— Ｉ－ Ｓ－ ＝ ｋ ｋＲ
：
０
０
０
… 一 ｎ ｌ ，
ห้องสมุดไป่ตู้
一 ｎｌ — ｎ Ｈ
一 ｎ 砧
…
１
讨 论 了该 预条件 矩阵 下 Ｇａ ｓ — ｅｄ ｌ 法 的收敛 性和 比较定 理． ｕ ｓ ｓｉｅ 方 本文 在 Ｐ 及 Ｐ一 卜卜 下提 出新 的 ＵＳ ＯＲ方法 ， 中 。 Ｒ Ｓ 其
ｌ Ｏ
…
Ｏ ０
：
●
・ ・ ・
Ｐｌ— Ｊ十 Ｓｌ—
：
●
：
●
Ｏ
— ｎｎ １
・ ・ ・
０
…
１
讨 论 了该 预条件矩 阵下 ＡＯ Ｒ方 法的收 敛性 和 比较定理 ． ２０ ０ ４年 ， ｋ 等 提 出 了预 条件矩 阵 ， Ｎｉｌ 即
１ ０ — ｌ ２ １
阵． ≥ ０ 且 ， Ｎ≥ ０ ． 并 且 Ａ ≥ ０ 则 称 之 为 ，
定义 ２。 设 Ａ为 一实 阵 ， Ｍ 为非 奇异 矩 阵 ， ［ 若 则称 Ａ — Ｍ —Ｎ 为 Ａ 的一个 分裂 ：（）正 规分裂 ， ａ 如果
Ｏ Ｏ Ｏ Ｏ Ｏ
…
Ｏ Ｏ
Ｏ
…
Ｒ ： ＝
Ｏ
— ｎｎ １ —
Ｏ
ｎ
Ｏ
…
・ ・ ・
０
一 ｎ Ｈｌ Ｈ—
０
讨 论 了在非奇 异但不 一定 是不可 约对 角 ｔ｛ － ／￣ｚ 阵下 的收敛 性 ， 到 几个 比较定 理 ， 广 了 Ｅ ａ ｓ ＮｉｉＪ 得 推 ｖ ｎ ［ 和 ｋＣ ｔ ＇
一
， ，
（ 一 【１ ［ １ Ｄｌ ，） （ 一 ） ＋∞ Ｌ ］ Ｄ１ ｌ Ｉ ［ １ １ＤＩ Ｏ Ｕ１ ， Ｄｌ ２ １ （ 一∞ Ｌ ） （ 一∞ ） ＋ Ｊ ］ １
在 Ｐ＝ Ｉ ＋Ｒ 下新 的 ＵＳ ＯＲ迭代 法 的迭代 矩阵 为 Ｓ
誊 ＝ （ 一 【Ｒ一［ １ ， ＤＲ ，） （ 一 ） ＋ ∞Ｌ ］ＤＲ一∞ Ｌ ） ［ １ ∞ ） ＋∞ ＵＲ． ＤＲ ２ Ｒ （ １Ｒ （ 一 １ＤＲ １ ］
维普资讯
第３ ７卷 第 ２ 期 ２ ０ ０ ８年 ３ 月
。
内蒙 古 师 范 大 学 学报 （ 自然科 学汉 文 版 ）
Ｊ ｕ ｎ ｌｏ ｎ ｅ ｏ ｇ ｌ ｒ ｌＵｎｖ ｒｉ （ ｔ ｒｌＳ ｉｎ ｅＥｄｔ ｎ ｏ ｒ ａ ｆＩ ｎ ｒＭ ｎ ｏｉ Ｎｏ ｍａ ｉｅｓｔ Ｎａｕ ａ ｃｅ ｃ ｉｏ ） ａ ｙ ｉ
Ｖｏ ． ７ Ｎｏ ２ １３ ． Ｍ ａ． ２ ０ ｒ ０８
新 的预 条件 ＵＳ ＯＲ 迭 代 方 法及 收 敛性 的 比较 Ｓ
王 卫 芳 ，畅 大为
（ 西师 范大 学 数 学与 信 息 科 学 学 院 ， 西 西安 ７ ０ ６ ） 陕 陕 １０ ２
摘
要 ； 不 同 的 预 条 件 矩 阵 下提 出新 的 ＵＳ Ｏ 迭 代 法 ， 论 了新 方 法 的 收 敛 性 ， 得 到 比较 定 理 ， 而 更 在 ＳＲ 讨 并 从
０ 引 言
对 于线性 方程 组
ＡＸ ＝ ｂ ， （） １
其 中 Ａ ＝ （ｆ Ｊ ）∈ Ｒ 非 奇异 ， ｂ∈ Ｒ ． ， 不失 一般性 ， Ａ ＝ ｊ 设 —Ｌ— Ｕ， 中 一Ｌ和 一 分 别是 Ａ 的严 格 其 下三 角和严 格上三 角矩阵 ． 考虑 预条件线 性 方程 组 Ｐ ｘ ＝ Ｐ ， 中 Ｐ ∈ Ｒ 非 奇异 ． Ａ ｂ其 ２０ ０ １年 ， ｖ ｎ Ｅ ａ ｓ等 提出 了预条件 矩阵 Ｐｌ 即 ，
其 中 Ａ１ 的元 素为 ：当 ≠ ， 一 ａ 当 — ，＂： ａ 中 石 ， 石 一ａ１ｌ； Ｒ中的元 素为 ：当 ｉ ｎ Ａ ａ ≠ ， ｆ— ａ ， ｊ ａ ｆ 当 Ｊ
ｒ １
．
～
ｚ
’ｎ ａｉ
ｎｊ一 厶 ａｋ ・ ” ｎａ
１ 预 备 知 识
定义 １ ［ 设 Ａ 一 （ ）为 × 的矩 阵 ， 。， ０（ ｎ 若 ≤ ≠ Ｊ ， ） 则称 之 为 Ｚ 矩 阵． Ａ是非 奇异 矩阵 ＿ 若
的结果．
收 稿 日期 ｌ２Ｏ 一Ｏ —２ Ｏ ７ ６ Ｏ
基 金 项 目 ｔ国家 自然 科 学基 金 资助 项 目（ ０ ７ ０ ８ １０１４）
作 者 简 介 一 卫 芳 （ ９ １ ， ， 南 洛 阳人 ， 王 １８ 一） 女 河 陕西 师 范 大学 硕 士 研 究 生 ， 要从 事并 行 算 法 及 其 应 用 研 究 主

合集下载

预条件的Jocobi迭代法的收敛性及其谱半径的比较定理

预条件的Jocobi迭代法的收敛性及其谱半径的比较定理

预条件的Jocobi迭代法的收敛性及其谱半径的比较定理摘要利用一种新的预条件矩阵讨论了预条件Jacobi迭代方法,得到了比较定理,并且揭示了预条件Jacobi迭代方法的收敛速度和参数之间的关系.关键词预条件矩阵;Jacobi迭代方法;比较定理;谱半径.Preconditioned Jacobi iterative method and comparison theoremsXUE Wei(Gansu Construction V ocational Technical College, Lanzhou, 730050, China)Abstract:With the aid of a new preconditioned matrix , the preconditioned Jacobi iterative method is discussed. Some comparison theorems are obtained , and the relation between the convergence rate of preconditioned Jacobi iterative method and the parameters is brought to light .Keywords:preconditioned matrix ; Jacobi iterative method ; comparison theorems ; spectral radius1 引言求解线性方程组（1）时,通常通过预条件的方法加速迭代法的收敛性,即在方程组的两端同时左乘一个非奇异矩阵,使方程组变为（2）2004年,Niki等在文献[1]中引入了几种预条件矩阵,,和.对于系数矩阵为矩阵时,它们都能加快Jocobi迭代法的收敛速度.同时,还有文献[2-4]中提出的预条件矩阵等.本文给出一种新的预条件矩阵:其中.论述了在一定条件下该预条件Jocobi迭代法为收敛的,同时从数值例子上可以说明该方法的优越性.为讨论方便,假定是具有单位对角元素的非奇异矩阵,若,其中,则分裂迭代法可表示为:(3)设,其中,分别是矩阵的严格下三角和严格上三角矩阵.此时,,得到经典的Jocobi迭代法的迭代矩阵.预条件后其中,令,,,分别是的对角,严格下三角和严格上三角矩阵.则预条件后其中,(4)如果是非奇异的,则在预条件下Jocobi迭代法的迭代矩阵2 相关的定义和引理2.1 几个定义定义如果一个矩阵满足:时,,是非奇异的且,则称为非奇异矩阵.定义对于实矩阵,和,是的一个分裂,如果,,则是的正规分裂;如果,,则是的弱正规分裂.定义设是的正规或弱正规分裂,则的充要条件为.2.2 几个引理引理设非奇异矩阵且,满足,那么有(1),都存在,并且还有;(2)的每个特征值为正值;(3).引理设是的两个弱正规分裂且,若满足下列条件之一:(1);(2),;(3),,.3 结论定理1 设非奇异矩阵,和分别是和的Jocobi分裂,如果,则有.证明由于.所以有是非奇异矩阵,从而,.因此.另外,也是非奇异的.其中,,,则,.由定义2可知为的弱正规分裂.另一方面,,其中,,有,,则也是的弱正规分裂.下证:.由于,显然是一个矩阵,并且,所以,由定义1可知为非奇异矩阵..由引理1(1)知,而,由引理2(3)知又.所以有,.定理2 设非奇异矩阵,和分别是和的Jocobi分裂.如果.则有.证明,其中,,.同理,其中,,.则由定理1的证明可知D都是的弱正规分裂,因,所以有,即.并且是非奇异矩阵,从而,由引理2(1)知,而,,所以有,.参考文献[1] Niki H,Harada K,Morimoto M, et al. The survey of preconditionersused for accelerating the rate of convergence in the Grass-Seidel method.Journal of Computational and Applied Mathematics,2004; 165(5) : 587—600[2] 石艳超,徐安农. 预条件Grass-Seidel 迭代法. 桂林电子科技大学学报,2008; 28(3) : 258—260[3] 李爱娟，畅大为. 预条件Jacobi迭代法及比较定理. 西北师范大学学报,2005;41(5) :21—23[4] 常岩磊, 张国凤, 赵景余. 新的预条件迭代法和新的比较定理[J] . 兰州大学学报: 自然科学版, 2009, 45(1) : 112- 114.[5] 金小庆. 数值线性代数[M]. 北京: 科学出版社, 2004.[6] 戴华. 矩阵论. 北京: 科学出版社, 2001[7] 胡家赣. 线性代数方程组的迭代解法[M] . 北京: 科学出版社, 1991: 20-22.。

预条件SOR方法收敛性比较

预条件SOR方法收敛性比较

-1 -1 -1
[3] 引理 7 令 T Ε 0, 如果存在 T Ε 0 x > 0和 α > 0, 使 Tx Φ αx, 则 ρ( T ) Φ α 。 进一步 , 如果使 Tx < αx, 则 ρ( T ) < α 。 [3] -1 -1 引理 8 令 A = M ∃ N 为弱正则分裂 , 则 ρ(M N ) < 1 Ζ A Ε 0 。 [5] -1 -1 引理 9 令 A 为不可约矩阵 ,若 A =M - N 为 M - 分裂 ,则存在一个正向量 x,使得 ρ(M N ) x =M N x 。
在解线性方程组
Ax = b ( 1)
时 ,一般采用迭代法 。这里 A 为一个 n 阶方阵 , x, b为 n 维向量 1 常见的迭代法有 AOR、 SOR、 Gauss Seidel等经典的迭代法 , 为了加快迭代法的收敛速度 , 许多学者采用预条件方法 。在 2001 年 , Evans等 人在文献 [ 1 ]中给出了一个新的预条件子 P = ( I + C ) , 其中 - a1 n i = 1, j = n ( 2) C = ( aij ) = , 0 其他 并证明了预条件 AOR 法加快了一般 AOR 方法的收敛速度 。 本文给出一种新预条件子 P = ( I + S ) , 其中 - ain i = 1 …n - 1, j = n ( 3) S = ( aij ) = 1 0 其他 我们将证明 , 在这种预条件子作用下的预条件 SOR 方法加快了经典的 SOR 方法的收敛速度 。 对于线性方程组 ( 1 ) ,不失一般性 ,令 A = I - L - U, 其中 I为单位矩阵 , L 和 U 分别为 A 的严格下 三角和严格上三角矩阵 。则对应于 ( 1 ) 的 Gauss - Seidel和 SOR 迭代阵分别为 -1 -1 ( 4) TG - S = M N = ( I - L ) U; -1 ( 5) TSOR = ( I - ωL ) ( ( 1 - ω) I +ωU ) , 0 < ω Φ 11 对应于 ( 2 ) 的 Gauss - Seidel 迭代矩阵为
预处理后新分裂下的SOR迭代法收敛性讨论

预处理后新分裂下的SOR迭代法收敛性讨论

出一 个 数 值 例 子 ．
关键词 ： 预处理 ； 收敛 性 ；Ｏ Ｓ Ｒ迭 代法 ； 谱半径
中 图分 类 号 ：２ １６ Ｏ ４ ． 文献标志码 ： Ａ 文 章 编 号 ：０ ０—２ ６ （０ ０ ０ ０ ３ ０ １０ １２ ２ １ ）４— ０９— ５
Ｔｈ ｏ ｅ ｇ ｎ ｅ ｄｉｃ ｓｏ ｆ ｔ ｅ ｃ ｎｖ ｒ ｅ ｃ ｓ ｕｓ ｉ ｎ ｏ ｈｅ ＳＯＲ ｔ ｒ ｔｖ ｅ ｈｏ ｉｅ ａ ｉ ｅ ｍ ｔ ｄ ｉ ｒ ｃ ｎｄ ｔ０ ｄ ｆ ｒ ｔ ｅ ｎ ｗ ｐｌ ｔｎｇ ｎ ｐ ｅ ０ ｉｉ ｎｅ ｏ ｈ ｅ ｓ ｉ ｉ ｔ
法， 此方 法不 仅 能加速 Ｓ Ｒ迭 代法 的收 敛性 ， ０ 而且 优 于一 般 的 预处 理 方 法 ． 后 用数 值 例 子 加 以验 证 ． 最 其 中 ：为单位 矩阵 ， Ｊ Ｃ为如下形式 的方 阵（ 所有列全 为零 向量 ， 第一列 是 （ ， ： －， ））： 其 只有 ０ 一ａ － 一ａ
ｉ ｗａ ｅ ｏ ｓｎ ｕ ａ ｔｉ ｔ ｕ ｔｔ ｅ ｌｎ ａ ｙ ｔｍ ｓ Ｔ ｓｐａ ｅ ｙ ｕ ｉ ｇ ｍ ａｒｘ ｉｅａ ｉｅ ａ ａ ｙ ｉ ｎ ｔ ｓ ｌｔｎ ｎ ｉｇ ｌ ｒｍａ ｒｘ Ｐ ｏ ｍｏ ｎ ｈ ｉ ｅ ｒ ｓ ｓｅ ． ｈｉ ｐ ｒｂ ｓｎ ｔ ｔ ｒ ｔｖ ｎ ｌ ｓｓ ａ ｄ ｉ
ｍｅｈ ｄ ｎ ｔｏ ｌ ｏ ａ ｃ ｌ ｒ ｔ ｈ ｔ ｏ ｏ ｎ ｙ ｔ ｃ ｅｅ ａ ｅ ｔ ｅ ＳＯＲ ｔｒ ｔｖ ｔ ｏ ｉｅ ａｉ ｅ ｍｅｈ ｄ，ｂ ｔ ａｓ ｏ ｅ ｃ ｌｅ ｈ ｅ ｅ ａ ｒ ｃ ｎｄ ｔ ｎ ｄ Ｓ ｕ ｌｏ ｔ ｘ ｅｌ ｄ ｔ ｅ ｇ ｎ ｒ ｌｐ ｅ ｏ ｉ ｏ ｅ ＯＲ ｉ
ｍ ｅｈ ｄ． Ｌａ ｔｔ ｅ ｎ ｍ ｅ ｃ ｌｅ ａ ｔｏ ｓ ｈ ｕ ｒ ａ ｘ ｍｐｌ ｓｇ ｖ ｎ． ｉ ｅ ｗａ ｉｅ
计算科学中的迭代和收敛性分析

计算科学中的迭代和收敛性分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

收敛性分析的方法很多。

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

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

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

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

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

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

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

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

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

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

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

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