（计算数学专业论文）解大型稀疏鞍点问题的迭代算法.pdf

摘要 摘要 本文研究了解大型稀疏鞍点问题迭代算法，主要就解鞍点问题的s o r - l i k e 迭 代、h s s 迭代算法的格式和收敛性展开了介绍和研究，并且研究了一种新的解 鞍点问题的迭代算法，全文共分为四章 第一章是绪论部分，简要介绍鞍点问题的背景的一些概念和预备知识 第二章主要研究了s o r l i k e 迭代算法的格式，在分析了此算法的收敛性的同 时给出了在特殊条件下的最佳迭代参数最后给出了几种特殊的算法格式 第三章主要研究了h s s 迭代格式的导出，并且以p o i s s o n 方程为例，对其在解 一维连续问题时候的收敛性进行了分析，同时给出了最佳的参数选取 第四章主要给出了一种新的解鞍点问题的迭代算法，然后给出了此算法的一 般形式并对算法的收敛性进行了分析- 其中基于一般形式推出的一种特殊算法有 着比经典的u z a w a 算法更为好的收敛条件文章最后部分的数值例子表明新算法 的提出是有意义的，是对经典的u z a w a 算法的一个颇有意义的改进 关键词：鞍点问题，迭代算法，收敛速度，谱半径，分裂 a b s t r a c t a b s t r a c t t h i sp a p e rm a i n l ys t u d i e st h ea l g o r i t h m s ，s o r l i k ei t e r a t i o na n dh s si t e r a t i o n ， f o rs a d d l e - p o i n tp r o b l e m s b ya n a l y s i so ft h ei t e r a t i v es c h e m e st h e i rc o n v e r g e n c ec o n d i t i o n sa n do p t i m a lc o n v e r g e n c ep a r a m e t e r sa r eg i v e no u t o t h e r w i s e ，w ep r o p o s ean e w i t e r a t i v em e t h o df o rt h es a d d l e - p o i n tp r o b l e m si nt h el a s tc h a p t e r t h ep a p e rc o n s i s t s o ff o u rc h a p t e r s i nt h ef i r s tc h a p t e rw eg i v es o m ei n t r o d u c t i o n sa n dp r e l i m i n a r i e sf o rs a d d l e - p o i n t p r o b l e m s i nt h es e c o n dc h a p t e rw ei n v e s t i g a t et h es o r - l i k ei t e r a t i v es c h e m ea n di t sc o n v e r g e n c ec o n d i t i o n s w es t u d yt h eo p t i m a lp a r a m e t e rf o rt h em e t h o da n dm a k es o m e s p e c i a lc h o i c e sf o r 国， i nt h et h i r dc h a p t e rw es t u d yt h es c h e m eo fh s si t e r a t i v em e t h o d w ef o c u so n t h em o d e lp r o b l e mo fp o i s s o ne q u a t i o na n dg i v eo u tt h ea n a l y s i so ft h ec h o i c eo ft h e o p t i m a lc o n v e r g e n c ep a r a m e t e ra tt h ec o n t i n u o u sl e v e l i nt h ef o r t hc h a p t e rw ef i r s tp r o p o s ean e wi t e r a t i v em e t h o df o rt h es a d d l e - p o i n t p r o b l e m s ，t h e nw eg i v eo u tag e n e r a lf o r m u l ao ft h en e wm e t h o da n di t sc o n v e r g e n c e a n a l y s i s 。o n e o f t h e t w o p a r t i c u l a r f o r m u l a i s p r o v e d t o h a v ea b e t t e rc o n v e r g e n c e c o i l d i t i o nt h a nt h ec l a s s i cu z a w am e t h o d f i n a l l yw er e p o r ts o m en u m e r i c a le x p e r i m e n t s s h o w i n gt h eg o o db e h a v i o ro f t h en e wa l g o r i t h m sf o rt h es a d d l ep o i n tp r o b l e m s k e yw o r d s ： s a d d l e p o i n tp r o b l e m s ，i t e r a t i v ea l g o r i t h m , c o n v e r g e n c er a t e ，s p e c t r a l r a d i u s ，s p l i t t i n g 。 一| i 一 第一章绪论 第一章绪论 1 1 鞍点问题的相关介绍 本文要解决的问题来源于如下2 2 的块状线性系统： ( 岛a 笔) ( ：) = ( ；) 其中块矩阵a 取“，b 1 和b 2 彤“，c 科“。”m ) ，向量x ，i r n , y ，g 明显地，在适当的分块之下，任何线性方程组都能够表示成( 1 1 ) 的形式， 当然这里排除了a = 0 或b 1 和岛中b 1 = 0 或岛= 0 或同时为0 的情况当块矩 阵a ，b 1 ，玩和a ，满下以后的一条或几条时，称( 1 1 ) 问题为鞍点问题： g ：a 是对称的，即a = a 7 凸：a 的对称部分h ；+ a t ) 是对称正定的 c 3 ：b 1 = b 2 = b c 4 ：c 对称( g = c 7 ) 且半正定 c 5 ：c = 0 注意到g 条件包含了q ，最基本的情况是g g 全部满足在这种情况 下，a 是对称半正定，我们有如下一个对称线性方程组： ( b a 髻) ( i ) = ( ；) ( 1 2 ) 这里我们还假设a 和b 没有共同的非平凡的零向量，从而保证( 1 2 ) 解的唯 一存在 上面这一线性方程组可以看成是以下一阶带约束条件的最优化问题： m i n j ( ) ：；z t a x - f 乇 ( 1 3 ) z s u b j u c tt o b x = g 一1 一 ( 1 4 ) 第一章绪沧 这种情况下变量口代表l a g r a n g e l 夭l 式的向量所以任何一个( 1 2 ) 的解都 是l a g r a n g e 式 砸，f ) = ；z 7 a x - ，t x + ( b x - g ) t ( 1 5 ) 的一个鞍点，因此我们称问题( 1 ，2 ) 为鞍点问题 注意到鞍点( z + ，玑) 还满足 l ( o + ，y ) sl ( x ，y + ) l ( x ，y + ) ( 1 6 ) 或等价于 r a i n m a x l ( x ，y ) = l ( x + ，蜘) = m a x a f i n l ( x ，y ) ( 1 7 ) o 日 * 线性方程组( 1 2 ) 常常来源于计算流体力学中的s t o k e s 方程和电磁学m a x w e l l 方程 的有限元离散和二阶椭圆方程问题的混合有限元方法，或者来源于参数识别和 区域分解问题( 【l 】- 【5 ) 一2 一 第一章绪论 1 2 本文的主要研究内容 关于解鞍点问题的数值方法近些年来在许多杂志和书本以及会议论文集中 出现了大量的研究结果，解鞍点问题的数值方法无论是理论还是具体计算过程的 执行都日趋完善，但事实上，解任何一类问题都不存在既普遍适用又最有效的算 法，每种所谓的最佳算法都是用来解某种特殊情况下的问题由于迭代算法简单 有效且只需要较小的存储空间执行起来相对容易，因此在解鞍点问题的一类方法 中迭代方法得到了最为广泛的关注本文主要的目的就是介绍解大型稀疏鞍点问 题中的三类迭代算法，并对它们的收敛性质进行了分析，最后部分通过一种将系数 矩阵分裂的思想，构造一种新的迭代方法，通过对参数矩阵的选取所得到算法比原 有的经典的u z a w a 迭代算法有更大的收敛区域和更快的收敛速度 本文共分四章，符章的内容安排如下： ( 1 ) 简要介绍鞍点问题的背景和文章研究内容的安排 ( 2 ) s o r l i k e 迭代方法及其收敛性和最优松弛参数的选取 ( 3 ) h s s j 塞_ 代方法及其收敛性h s s 迭代方法及其收敛性和最优参数的选取 ( 4 ) 关于一种新的解大型稀疏鞍点问题的迭代算法及其收敛性和特殊算法 在大多数情况下，鞍点问题中的线性方程组的系数都是实系数，而且实系 数的情况可以很容易的推广到复系数的情况( 【6 】，【7 】) ，因此本文中除第三章讨论 的h s s 迭代方法以外，我们都假设鞍点问题的系数是实数 3 第：章s o r - l i k e 迭代方法及其收敛性 2 1 引言 第二章s o r l i k e 迭代方法及其收敛性 由于方程组( 1 2 ) 的系数阵在大多数情况下都是大型的稀疏矩阵，迭代方法 是解决这一问题的有效方法，因为迭代方法具有简单有效、存储空间小、容易 执行等优点戒们知道经典的s o r 迭代( 【8 ) 是非常简单有效的迭代方法之一且在 工程计算中有着广泛的应用，但是由于方程组( 1 2 ) 的系数矩阵中块对角的奇异 性，s o r 迭代不能直接应用来解( 1 2 ) 近年来l i 和g o l u b ( 8 ，【2 6 】) 等学者研究了所谓 的推广的s o r 方法和s o r l i k e 方法可以有效的应用到解( 1 2 ) 的问题 为了简单表示，下面的章节中，我们将( 1 2 ) 表示成： ( 拶a 言) ( i ) = ( 二) ( 2 1 ) 本章共分为三节2 2 节首先导出 s o r l i k e 塞_ 代法的算法格式2 3 节分析 t s o r l i k e 算法的收敛条件2 4 节给出了算法的最优松弛参数的选取2 5 节通 过对参数矩阵的不同选取，给出了几种不同的算法格式 4 第二章s o r l i k e 迭代方法及其收敛性 2 2s o r l i k e 迭代方法的格式 本节主要叙述s o r l i k e 迭代方法格式的导出过程s o r - l i k e 迭代方法思想 起源于经典的s o r 迭代，首先将( 2 1 ) 的系数矩阵作如下分裂： 其中 ( 三，言) 一 z ， 。= a 吕) ，l = 0 ，：) ，u = 0 且0 是对称非奇异的，于是考虑如下格式 苫) ( x k + li = u wix k ) + w ( d - w l ) - i ( 二) 其中迭代矩阵为 肘0 = ( d u l ) 一1 ( 1 一u ) d + 。矿】 将其写成分块矩阵的形式便得： 帆= ( 一。a b ，q 0 ) 一1 ( 口一0 “) a 一苫b ) s o r l i k e 算法 5 ( 2 3 ) ( 2 4 ) ( 2 5 ) ( 2 6 ) ( 2 7 ) 旷 b，卜叫 。 蚪 矽驴 u u 一 + 0 圹 | | = “ “ 神驴 第二章s o r l i k e 迭代方法及其收敛性 2 3s o r l i k e 迭代的收敛性 这一节中我们将就上一节中导出的s o r “k e 算法的收敛性进行分析 引理2 3 1 ：( 【2 6 】) 设“是q 一1 b t a 。b 的一个特征值，如果a 满足 ( a 一1 ) ( 1 一u a ) = a u 2 肛， ( 2 8 ) 那么a 是m 。的一个特征值反之，若a 是m 。的一个特征值，使得a 1 且a 1 u ，且“满足( 2 8 ) ，则p 是q 一1 8 7 a _ 1 b 的一个非零特征值 证明：假设a 是舰。的一个特征值，( ，y t ) 7 是其对应特征值向量，那么由 可知 帆( i ) = a ( i ) ( 1 0 。) a 一苫b ) ( ；) = a ( 一左，q 0 ) ( i ) ( 2 9 ) ( 2 1 0 ) n l l g l * t ( 2 1 0 ) 可得 。1 - 一w 。，- q ，a ) ：a a x 。= b w t b 茁 c z ， 由于a 是对称正定的，由( 2 1 1 ) 可得( 1 一u a ) z = w a b y 因此，由于q 的非 奇异性，我们得到 ( a 1 ) ( 1 一u a ) = a u 2 q 一1 b t a 一1 b y ( 2 1 2 ) 设芦是q - 1 8 7 a _ 1 口的特征值，那么可得 ( a 一1 ) ( 1 一u a ) = a u 2 卢 反之，同理我们可以证明引理的后半部分 为了得到关于收敛性条件定理，我们首先引用下面的结果( 【2 1 ) 6 f 2 1 3 ) 第二章s o r l i k e 迭代方法及其收敛性 引理2 3 2 ：( 【2 l 】) 实一元二次方程茁2 一妇+ c = 0 的两根之模都小于一，当且仅当 方程的系数满足： i c l 1 ，l b l o ，s o r - l i k e 算法是收敛的，对丁任何“使得 。 u 南， 其中p 是q _ 1 8 7 a - 1 b 的谱半径 证明：由引理2 3 1 得 a 2 + ( u 2 p + u 一2 ) a u = 0 ， 根据引理2 3 2 ， 1 当且仅当 1 1 一u i 1 且 l u 2 肛+ u 一2 l l + l u = 2 一u 由( 2 1 7 ) 失 1 0 u 2 ，从而得到 u 一2 u 2 “+ 叫一2 2 一u 因此 0 u 2 “u 2 p 4 2 u 从而，我们得到 。 u 肋，由( 2 2 5 ) 知i a ( u ) i i a ( m ) 1 这里 a ( 肛o ) i = o 5 1 2 一u u 2 p o i + w x ( w # o + 1 ) 2 - - 4 z o 9 一 第一j 章s o r o l i k c 迭代方法及其收敛性 当越 1 4 我们同样可以得到i a ( p o ) l2 r = 石对于u ( 2 万 a ( p ) l ，其中 i x ( p ) l = 0 5 1 2 一u j p l + u 、，i j 万了1 了啊 由( 2 3 5 ) 和( 2 3 6 ) ，我们可以得到( 2 3 3 ) 和( 2 3 4 ) l o 1 ) p ，i a ( p o ) l f 2 3 6 ) 第二章s o r - l i k e 迭代方法及其收敛性 2 5 几种特殊的8 0 r - i _ i k e 方法 在这一节中，我们始终假设b 是满秩的，a 是对称正定的 ( i ) ：q = b 7 b 首先我们取q = b 7 b ，注意到( b 7 口) 一1 8 7 a 一1 b = b t a - 。b 其中b t 是的广 义逆，b * a 一1 b 的特征值是非负的，所以( b 7 b ) 一1 8 7 a _ 1 b 的特征值是非负的 s o r l i k e 算法1 ： lz + 1 = ( i u ) 。+ w a 一1 ( ，一b ”) ， iy + 1 = y + u ( b t b ) 一1 ( b t z + 1 一g ) 由上节中对于s o r “k e 方法收敛性的分析结果知，0 u 了i ； 雨时算法收 敛其中p 是( b 7 b ) 一1 8 7 a _ 1 b 的谱半径 r i i ) ：q = b 7 a 一1 b 这里我们选择q = b 7 a b ，这种情况下，q 一1 b t a 一1 b = ，此时所对应的特 殊算法的收敛性分析和最优参数的选择相对比较容易，我们可以写出其对应的算 法， s o r l i k e 算法2 ： z 蚪1 = ( 1 一u ) 扩+ w a 。1 ( ，一b y 2 ) ，( 2 3 8 ) l 可。+ 1 = y + u ( b r a 一1 b ) - 1 ( b t 。+ 1 一g ) 、。 显然当我们取u = 1 的时候得到在q = b 7 a 一1 b 情况下的最优的s o r l i k e 算 法这时的算法等价于块高斯消去法，因此利用这种算法可以得到很好的收敛效 果 ( i i ) ：q = a i 这里我们考虑最简单的取法q = 。，此时算法表示如下 s o r l i k e 算法3 ： p ，：扛。哆1 ( j 加矿) ， ( 2 3 9 ) 【y + 1 = y + 嚣( b 丁z + 1 一g ) 第一章s o r - l i k e 迭代方法及其收敛性 上面算法收敛条件为 。 u o ，将分裂成下面两种形式， ：言) = ( 州十n d 一( a i s ) ，= ( 5 + a i ) 一( o ，一州) 其中j 表示协+ m ) ( 站+ m ) 单位矩臻，予是洼意翻 ? - t + o d = 船硪n 0。羔) ， s 午i i ；耐n 攀 、一嚣n k 都是非奇异矩阵，镪激选取( 。o ，g o ) 7 作为初始值，x = ( 妒，v k ) t 表示第七次迭代后 掰褥的解，于是我翻霹激褥室j h s s 迭代据_ 戏强下： 傺篇a i ) x 裂竺掣。n ) x 兰a 涵z ， 【( s + 1 = ( 耽， + 1 2 + b 。 对于算法3 2 的前半步可以通过如下步骤计算 苎：- 8 i , z ；) x k + ，l ，：。= ：a 。，l ，x 。+ j 一暑4 爹2 ， ( 3 3 ) lp 啪= y + j ( 嚣茹m 2 一彩 、 ；主记2 ：注意到( 3 3 ) 的第一式系数矩阵为对称正定，进一步讲对于p d e i h 题，a + 一1 4 第三章h s s 迭代方法及其收敛性 旺藏霞是条箨数与步长h 无关静，事实主将砖正勰稼整零a 一蠢) = l ，巅我弱可鞋 得到a + a j 条件数的上界 托( a + a ，) = 揣s ，+ 三 送蠢强t 3 ) 第一式缀褰瑟瑟褥，捌翅露舔蕊c h o l e s k y 分解或共鬓撵凌法 对于( 3 2 ) 的第二式等价于求解： a x k + l + b * y k + l 却乇：，k + l 2 ，叫， ( 3 4 ) l b x o + 1 + o 扩“= a y + 1 2 一g ! g 、 洼记3 ：上嚣线瞧方程缝可敬奏多秘方法潦楚銎包季羞c g - l i k e 方法( 【1 2 琢或者秘 用s c h u r 分解游去( 3 4 ) 中的x k + l 得到一个带有m 个未知量的对称正定线性系统 ( b b + + 0 3 2 厶。) 。+ 1 一b f + 0 9 。 ( 3 5 ) 然爱再诗莫护+ 1 一i ( ，一b 4 爹蚺1 ) ，注意攀l 让是够大对( 3 。5 ) 中的系数短箨变残对螽 占优矩阵，且条羚数翡上赛与步长h 无荧，麓蔟轭梯度法便霹禳褥 一1 5 一 第三章h s s 迭 t 方法及其收敛性 3 3 解连续闰题豹h s s 迭健的收敛悭分析 为了分析( 3 2 ) 的收敛性，我们先将中间量x + 1 2 消去，将迭代写成 x + 1 = 瓦x o + e ， 其中 五：裟( s + o d 一1 ( 口j 一州) ( “+ d 一1 ( o j s ) 是h s s 方法的迭代矩阵，且 e ：= ( s + d f ) 一1 蓼+ ( 氆j 一弼) p + 馥j ) 一1 ( 3 6 ) ( 3 7 ) ( 3 ，8 ) 显然在给定一个初始值x o ，迭代( 3 2 ) 收敛于解x = 。b ，当且仅当p ( 五) o 的情况，而参数是不可以任意取的，因为七也必须有上界最大频 阵 e非成写式 ， 第三章h s s 迭代方法及其收敛性 率，。= f 矗( 1 l 麓步长) 控裁，圈祥南氇赫须有下器女。t 。 0 ( = o 会导致阉 题奇异) ，铡如区域有限且d i r i c m e t 条件时m = 7 r 肛，其中三怒隧域长度当区域一 边是齐次d i r i c h l e t 边值条件，另一边是齐次n e w m a n 条件时“。一7 r ( 2 l ) 因此为了最优化h s s 算法的收敛性，就归结为求如下的最大鼹小闽题 嘧( 妻懋妒池的) 对于这一问题文献( 【1 3 】) ，有以下两个定壤作为结果 f 3 1 5 ) 定理3 3 1 ：若。；1 且k 。( 2 血。一t ) 惫“。 ，所以下面的定 疆将跨出是“。毙较小静嫉戆最大最小翊熬 0 ，所以a 0 若 c ，设a = + h i , 同样易知2 。= 锋导 o ，从而n o ，故引理得证 基于引理4 2 1 ，我们提出如下迭代 ( = ( 翥) 一a ( 二署) ( 妻) 一( 二) ) ( 4 8 ) ( 4 9 ) 这里6 o 足一个参数根据引理4 2 1 ，我们可以知道只要j o r 6 足够小，则迭 代( 4 9 ) 是收敛的，这一结论我们将在下面的定理4 2 2 中给出 首先令( 茁，”) t 表示方程组( 4 1 ) 的精确解，( 。，) 7 表示经过n 次( 4 9 ) 迭代后得 到的解，用e ：，e 嚣分别表示误差则 e 。, v c = z z 。，e ：= ”一v 。，e 。+ ，= ( 。e i n + + ，1 ) c 4 - 。 因此由( 4 2 ) 和( 4 9 ) 可得： 钳- = 卜( 三等) ) e n 设丁= i d m 为迭代( 4 9 ) 所对应的迭代矩阵 定理4 2 2 ：对于线性方程组( 4 1 ) ，a 为对称正定，b 行满秩，若参数6 满足： o 6 如，南= 扣嚷砌五丽2 a 则迭代( 4 9 ) 收敛，其中a ( m ) = a l m = ，o ) 一2 l 一 ( 4 1 1 ) ( 4 1 2 ) 第四章关j 二新的解大型稀疏鞍点问题的迭代算法 证明：要使得迭代( 4 9 ) 收敛，必然要求其迭代矩阵的谱半径小于1 ，也就是要满足 p ( i a m ) 2 榧m & 剐x1 6 九 2 榧i i i 。& 【m x ) 而习丽虿 1 ( 4 1 3 ) 也就是： ( 0 2 + 铲) 铲一2 a 5 0 。因此若j 满足： o 6 南i 研2 a ( 4 1 5 ) 则迭代( 4 9 ) 是收敛的，故定理得证 迭代( 4 9 ) 对应的算法如下： 算法1 ： ，坼1 = z n + j ( ，一a z n b t 鲰) ( 4 1 6 ) 【+ 1 = 鲰+ 6 ( b x 。一g ) 、 。 在实际计算当中我们通常将上面的算法第二式中的z 。用+ l 代替，从而写成 算法2 ： 嘶1 + 6 ( f - a x , t b 7 ) ( 4 1 7 ) 1 帅= + 6 ( b x 。一9 ) ”“ 从定理4 2 2 我们知道，只要参数6 选取为足够小的正数，便可以得到一个收敛 的迭代算法2 事实上利用( 4 1 ) 的等价方程组( 4 2 ) 我们可以导出更为一般的迭代格 式这一个格式将在下一节中给出 第四章关于新的解大型稀疏鞍点问题的迭代算法 4 3 一般迭代格式及其收敛性分析 在这一节中我们根据线性方程组( 4 2 ) 的形式给出一种更为一般的迭代格式 及其几种特殊形式，与此同时我们对这一迭代格式及其特殊形式的迭代收敛性进 行了分析 对于方程组( 4 2 ) 的系数矩阵m ，将其分裂为如下形式： ( 二：) = ( a 一- i - b d l 三) d _ 玩b t ) 其中d 1 满足a + d 1 的非奇异性，d 2 为非奇异的，这里我们也可以将d 1 和d 。看成预 处理矩阵，从而可以得到一种新的迭代格式： ( a 篡1 三) ( d 詈) ( 黧) + ( 二) 于是可以推得 ，a + d 1 “5i b 0 、。1 ，d 。一b r 、 功i 、od 2 f 4 1 9 ) ( 4 2 0 ) 记迭代矩阵 g = a + d 1 玎d 1 珂d 2 ) z ， 令p ( g ) 表示迭代矩阵g 的谱半径，从而要保证迭代( 4 1 9 ) 收敛就必须满足p ( g ) 1 ，也就是如果a 为g 的特征值，那么a 必须满足： al 1 ( 4 2 2 ) 第四章关于新的解大型稀疏鞍点问题的迭代算法 下面令a 是g 的一个特征值，( ：) 为其对应的特征向量 贝 j g ( ：) = a ( ：) ( 4 2 3 ) 【d 1 一a ( a + d 1 ) “= 矾，( 4 - 2 4 ) 【( 1 a ) d 2 v a b u 在对迭代( 4 1 9 ) 的收敛性进行分析之前我们首先证明三个引理 引理4 3 1 ：设a 是对称正定的，b 是行满秩的，若a a ( g ) ，则a 1 证明：由于a 对称正定的，b 是行满秩的，从而( 4 1 ) 的系数矩阵是非奇异的，假 设a = - ( ：) 是其对应特征向量，则由c 。2 4 ，知 a 曰u + ：b 。7 = 。 c 4 z s ， 由于( ：) 是非零向量，故h z s ，式表明方程组一，的系数矩阵是奇异的，这与假 设矛盾故引理4 3 1 得证 一 同样利用反证法，我们可以得到下面的引理 引理4 3 2 ：设a 睦对称正定的，b 是行满秩的，设( 札，u ) t 是g 对应特征向量且d 2 为 非奇异的，则u 0 证明：略 引理4 3 3 ：设a 足对称正定的，b 是行满秩的，设a a ( g ) 且( n ， ) 丁是其对应的特 征向量，d 2 为非奇异的，d l 是对称半正定的若v = 0 ，则iaj o ( 4 2 7 ) u 1 t 正1 o a = 厕o l 1o 十廿 ( 4 2 8 ) ( 4 2 9 ) 下面我们令, k m i n ( m ) 和a m a x ( m ) 分别表示矩阵m 的最小和最大特征值，于是 我们给出迭代格式( 4 1 9 ) 的收敛定理 定理4 3 4 ：设a 为对称正定的，b 为行满秩的，若d 1 是对称半正定，d 2 是对称正定 的且 a 。( b 7 d i l b ) 2 ( 2 3 。e 。d 1 + a 。m a ) ( 4 3 0 ) 则迭代格式( 4 1 9 ) 是收敛的 证明：我们仍设a 是迭代矩阵g 的特征值，( ：) 为其对应的特征向量首先根据 定理的假设条件以及由引理4 3 1 和引理4 3 2 知a 1 r u 0 ，下面再分b u = 0 和b u 0 讨论 若b u = o y , 0 由( 4 2 4 ) 知1 v = o ，根据引理4 3 f 3 知lai o( 4 _ 3 1 ) , t u 。 、7 对( 4 2 4 ) 式中消去v 得到： 【d 1 一a ( a + d ，) 】乱= j 、_ b 7 d i l b u ( 4 3 2 ) 整理后得： 牡等a + 南= o ( a ) 一2 5 第四章关于新的解大型稀疏鞍点问题的迭代算法 由文献( 【2 1 】) ，我们知道对于一元二次方程n a 2 + b a + c = o ( a o ) 的根ia1 1 的 充分必要条件是： l 硫一k in1 2 一ic1 2 ( 4 3 4 ) 因此上面这个条件对于( 4 3 3 ) 来讲也就是要满足： i 南i 1 ( 4 3 5 ) 一而2 a + 普 而2 a + f l ( 4 3 6 ) 一i 万 _ 苒万2 i 万 竹删 由于( 4 3 5 ) 式以及( 4 3 6 ) 的右边不等式是显然成立的所以迭代( 4 1 9 ) 收敛条件归 结为满足： 一而2 q + f l 訾 ( 4 _ 3 7 ) 一i 万 o ，故( 4 3 7 ) 等价为 又因为 1 o ) 则迭代( 4 1 9 ) 即为 算法4 ： 坼1 2 x n + ( + 2 a ) 。( ，一a z n b 7 ) ( 4 删 i + 1 = + 5 ( b z n + 1 一g ) 根据定理4 3 4 ，可以推得迭代算法4 的收敛条件 推论4 4 2 ：对于线性方程组( 4 1 ) ，a 是对称正定的，b 是行满秩的，如果迭代参数5 满足： 坠生链磷攀 则迭代算法4 必收敛 事实上当迭代算法4 中的迭代参数j 取的适当小时， + 2 a 近似与一个对角元 素非常大的对角矩阵，在计算逆的过程中较a 更为方便，并且由上面的两个推论可 知算法4 的迭代参数6 的取值范围明显比经典u z a w a 算法中的6 的取值范围至少扩 大两倍，下一部分的数值例子，也显示了此算法是对经典的u z a w a 算法更好改进 2 7 第四章关于新的解大型稀疏鞍点问题的迭代算法 4 。5 数值例子 下面给出算法2 , n 算法3 以及算法4 的数值例子，设a 是一个 n 的矩阵，满足 a = ( m ，j ) n n = i + l , i = j 1 ， ( 4 4 6 ) b 是一个m n 的矩阵，满足 b = c 一 巍 r 4 4 7 ) 这里我们取m = 5 0 m = 6 0 ，则由定理4 2 2 和推论4 4 1 以及推论4 4 2 ，可以算出各 个算法中迭代参数的上限如，下面给出三种算法在6 不同取值下的数值实验的结 果，这里我们取迭代终止误差标准是1 0 ，t 表示迭代的步数 表l ：当m = 5 0a n dn = 6 0 时u z a w a 算法的迭代数 l 品= 0 0 0 1 0 6 = 0 0 0 16 = 0 0 0 0 85 = 0 0 0 0 5 6 = 0 0 0 0 1 t2 5 5 1 73 1 8 9 85 1 0 4 02 5 5 2 2 3 表2 ：当m = 5 0a n d n = 6 0 时算法2 的迭代数 5 0 = 0 0 2 0 6 6 = 0 0 26 = 0 0 1 56 = 00 0 16 = 0 0 0 0 5 t1 0 3 21 3 7 32 0 5 54 1 0 3 表3 ：当m = 5 0 a n d n = 6 0 时算法4 的迭代数 5 0 = o 0 4 1 6 6 = 0 0 0 4 j = 0 0 3 56 = 0 0 3j = 0 0 2 t4 8 05 5 46 5 29 9 4 由上面的数值例子，通过比较三种算法在6 不同取值下的迭代步数可以说明 本文提出的两种新算法是对经典的u z a w a 算法的一种颇有意义的改进，并且具有 其可靠性和有效性 参考文献 参考文献 【1 】r g l o w i n s k i n u m e r i c a lm e t h o d sf o rn o n l i n e a rv a r i a t i o n a lp r o b l e m s s p r i n g e rs e r i e si n c o m p u t a t i o n a lp h y s i c s ，s p r i n g e r - v e r l a g ，n e wy 0 r k ，1 9 8 4 ， 2 】m h w r i g h t ，i n t e r i o rm e t h o d s y o rc o n s t r a i n e do p t i m i z a t i o ma c t an u m e r i c a1 9 9 2 ，p p 3 4 1 4 0 7 【3 】i l o c h u a ，c a d e s o e r , a n d e s k u h ，l i n e a r a n d n o n l i n e a r c i r c u i t sm c g r a w h i l l ，n e w y o r k ，1 9 8 7 ， 【4 】a t o s e l l ia n d0 b w i d l u n d ，d o m a i nd e c o m p o s i t i o nm e t h o d s - a l g o r i t h m sa n dt h e o r y s p r i n g e rs e r i e si nc o m p u t a t i o n a lm a t h e m a t i c s ，s p r i n g e rv e r l a g ，v 0 1 3 4 ，2 0 0 4 【5 】eb m z z ia n dm f o r t i n ，m i x e da n d 坶b r i d f i n i t ee l e m e n tm e t h o d s s p r i n g e rs e r i e si nc o m p u t a t i o n a lm a t h e m a t i c s ，s p r i n g e r - v e r l a g ，n e wy o r k ，v 0 1 1 5 ，1 9 9 1 【6 】ec i a r l e tj r , j h u a n ga n dj z o u ，s o m eo b s e r v a t i o n so ng e n e r a l i z e ds a d d l e - p o i n t p r o b l e m s s i a mj m a t r i xa n a l a p p l 2 5 ：2 2 4 2 3 6 ，2 0 0 3 【7 l h m a h a w a ra n dvs a t i n ，p a r a l l e li t e r a t i v em e t h o d sf o rd e n s el i n e a rs y s t e m si ni n d u c t a n c e e x t r a c t i o n p a r a l l e lc o m p u t 2 9 ：1 2 1 9 1 2 3 5 ，2 0 0 3 【8 】y o u n g d m ，i t e r a t i v es o l u t i o n so f l a