（应用数学专业论文）广义加速超松弛方法解线性互补问题.pdf

张惠广义加速超松弛方法解线性互补问题 中文摘要 从2 0 世纪6 0 年代线性互补问题的提出到现在，尤其是最近2 0 多年来，线性 互补问题发展迅速。它被广泛地应用于工程、经济和运筹学中，对线性互牵 问题 的研究可以分为理论和算法两个方面，前者主要研究问题解的存在性、唯一性、 稳定性以及灵敏度分析等性质；后者集中研究如何构造有效算法及其理论分析。 本文主要研究一种解线性互补问题的数值解法：广义加速超松弛算法。 在本文中我们主要研究用广义加速超松弛迭代方法( 简称为g a o r 方法) 来解 线性互补问题上c 尸( m ，g ) ，其中吖是一个，l 珂阶的非奇异矩阵，g r “。在论文 的第一部分，我们首先提出了一类解决线性互补问题的广义a o r 方法，其特殊情 况转化为广义的s o r 方法。 在第二部分中我们讨论了所提出的两种算法的收敛性，对于g a o r 方法给出 了下面的结论：当系数矩阵m = ( m 。) r 是对角元素均为正数的h 一矩阵，且 分裂肠= d + l + 【，满足( m ) = d 一一l u i 乖t 若o q i 亏丽7 = 1 ，2 ，片， 口r + ，其中j = d 一1 ( + u ) ，则对任一初始向量z o 只“，由g a o r 方法产生的 迭代序列乜， 收敛- 于l c p ( m ，q ) 的唯一解z r 4 ，并且满足： p ( ( q ) 。渊) 舞( 1 1 一卿i + q 户q ，i ) ) 1 ， 当o 口s l 时， p ( ( q ) 。) l l 一剖+ l 口m 。a ；x 。 1 1 一圳+ q 训帅 1 ， 当口1 时。 作为g a o r 方法的特殊情况，我们也得到了g s o r 方法的收敛性质，而由于一 个肘一矩阵也是一个日一矩阵，所以上面的结论也适用于m 一矩阵，而且对角元 素均为正的严格或不可约对角占优矩阵也满足结论的条件，则上述结果对这些矩 阵也成立。 第三部分中我们主要考虑两种算法的单调收敛性质，我们得到了这样的结论： 扬州大学硕士学位论文 2 当m r 是一矩阵，且当0 q 茎1 , i = 1 ，2 , - - n ，0 盯s l 时，则对任一初鲐向量 z o a ，由g a o r 方法或g 致欢方法产生的迭代序列( z p ，p = o ，l ，2 ，有下面的两 个性质： ( 1 ) 0 ：，“sz 9 z o ： ( 2 ) l i r a z = z ，其中z ；是l c p ( m ，g ) 的唯一解。 r 。，w 在这一部分中我们还讨论了参数；，i = 1 , 2 ，月和参数口对g a o r 力法和 g s o r 方法的收敛速度的影响，得出了当参数国。= 吐_ - 吼= a = l 时能导致更快 的收敛速度，这也意味着导致两种方法收敛速度最快的参数可能在【1 ，m ) 中，也即 口，彩：，反，：f 1 ，o o ) 。 在最后一部分中，我们用一个数值例子来验证第三部分所得出的结论，也即 当各个参数越接近于l 时，由g a o r 方法所产生的迭代序列收敛于所求线性互补 问题的精确解所需的迭代次数就越少，也就是说收敛速度越快。 关键词：g a o r 方法，g s o r 方法，线性互补问题，收敛性，单调性a 张惠广义加速超松弛方法解线性互补问题 a b s t r a c t l i n e a rc o m p l e m e n t a r i t yp r o b l e m sh a v e b e e nd e v e l o p e d v e r yq u i c k l ys i n c et h e y a p p e a r e di nt h e6 0 sl a s tc e n t u r y , e s p e c i a l l yt h er e c e n tt w od e c a d e s a n dt h e yw e r e w i d e l yu s e di ne n g i n e e r i n g ，e c o n o m i c sa n do p e r a t i o n sr e s e a r c h r o u g h l ys p e a k i n g ，t h e s t u d yo ft h el i n e a rc o m p l e m e n t a r i t yp r o b l e m sc a nb ec l a s s i f i e di n t o t w oc l a s s e s ： t h e o r i e sa n da l g o r i t h m s t h ef o r m e ri sd e v o t e dt ot h ee x i s t e n c e ，u n i q u e n e s s ，s t a b i l i t y a n ds e n s i t i v i t ya n a l y s i so ft h es o l u t i o n s ，w h i l et h el a t t e ri si n t e n d e d t os o l v et h e p r o b l e m se f f i c i e n t l y , t o g e t h e rw i t ht h et h e o r e t i c a la n a l y s i so f t h ea l g o r i t h m s w ew i l l c o n s i d e rac l a s so fm e t h o df o rs o l v i n gt h el i n e a rc o m p l e m e n t a r i t yp r o b l e m ：g e n e r a l i z e d a c c e l e r a t e do v e r r e l a x a t i o nm e t h o d s i nt h i sp a p e r , w ew i l lc o n s i d e rt h eg e n e r a l i z e da c c e l e r a t e do v e r r e l a x a t i o n ( g a o r ) m e t h o d sf o rs o l v i n gt h el i n e a rc o m p l e m e n t a r i t yp r o b l e ml c p ( m ，曰) ，w h e r em i sa n f ixnn o n s i n g u l a rm a t r i x ，g r ”i ns e c t i o no n e ，ac l a s so fg a o rm e t h o d s ，i n w h i c ho n e s p e c i a l c a s er e d u c e st og s o rm e t h o d s ，f o rs o l v i n g t h el i n e a r c o m p l e m e n t a r i t yp r o b l e m s a r ef i r s t l yp r o p o s e d i ns e c t i o nt w o ，w ed i s c u s st h ec o n v e r g e n c eo ft h eg a o ra n dt h eg s o rm e t h o d s ， f o rt h eg a o rm e t h o d s w ed e s c r i b ei t sc o n v e r g e n c e ：w h e nt h es y s t e m m a t r i x m = ( ) r i sa n 日一m a t r i xw i t hp o s i t i v e d i a g o n a le l e m e n t s a n dl e tt h e s p l i u i n gm = d + 上+ u 训s f y ( m ) = d i 上i i u | 1 fo q i 亏布= 1 2 玑 a n d 盘r + ，t h e nf o ra n yi n i t i a lg u e s sz o r ”，t h ei t e r a t i v es e q u e n c e z p ) g e n e r a t e d b yt h eg a o rm e t h o d sc o n v e r g e st ot h eu n i q u es o l u t i o n z o f t h el c p ( m ，g ) a n d p ( ( q ) r - m 。a 。x 1 一q i + 以p q 帅 l ，w h 。n 。v 盯o 口1 ， p ( ( q ) - l i r 噼一爿+ 丢蹬 h 州) ) ，讪e n c v c r 口扎 扬州大学硕士学位论文 4 a st h es p e c i a lc a s e ，f o rt h eg s o rm e t h o d s ，w ea l s oh a v et h ec o n v e r g e n c er e s u l t s i t i sc l e a r l yt h a ta l lm m a t r i xi sa l s oa l lh - m a t r i x ，h e n c e ，t h es t a t e m e n t sa r ev a l i df o r t i l em m a t r i x s i n c eas t r i c t l yo ri r r e d u c i b l ed i a g o n a l l yd o m i n a n tm a t r i xw i t hp o s i t i v e d i a g o n a le l e m e n t si sa l s os a t i s $ i n gt h ec o n d i t i o no ft h et h e o r e m ，t h e nt h er e s u l t sa l e a l s ov a l i df o rt h e s em a t r i c e s i ns e c t i o nt h r e e ，w ec o n s i d e rt h em o n o t o n ec o n v e r g e n c eo ft h et w om e t h o d s ，w eg e t t h er e s u l to ft h em o n o t o n ec o n v e r g e n c eo ft h et w om e t h o d s ：a s s u m et h a tm 矗“i s a n 一m a t r i x a l s o ，a s s u m et h a t0 q l ，i = 1 , 2 c - ，0 p ( e ) ，则称a 为m 一矩阵。 对于m 一矩阵，有这样一个等价命题： 命题i 3 1 2 4 ：令爿z ，则a 是m 一矩阵的充要条件为一可逆且爿- 1 0 。 定义1 4 ：令爿c ，若爿的比较矩阵( 爿) 是肘一矩阵，则称一为h 一矩阵。 注意到一个日一矩阵是非奇异的，且有性质p _ 1j ( 4 ) 一，p ( 俐。阍) l ，其 中d = d f a g ( a ) ，b = d a 。 对角优势矩阵是与m 一矩阵和一矩阵有着密切联系的一类重要矩阵，下面 我们给出对角优势矩阵的定义： 定义1 5 ：设彳= ( ) e c ”，彳称为是按行对角优势矩阵，如果j 吒l f i ， ；：j i ：1 , 2 蚪。若上式全部成立严格不等式，则称a 是按行强( 或严格) 对角优势的； 若a 不可约且上式中至少有一个严格不等式成立，则称a 是按行不可约对角优势 的。 扬州大学硕士学位论文 给定疗阶线性方程组 4 x = b ，( 1 1 ) 其中爿c ，6 ，工c ”，x 是未知向量，考虑用一组序列 x 来逼近它的解， 序列伽) 是通过逐次迭代得到的，它由如下的一般迭代格式定义： x 门= 西o ( 彳，6 ) ， x = 吼+ l ( x ，工；a ，6 ) ，k = o ，l ，2 通常，对某f 20 ，工”，工5 是任意的，即吼，由，是4 和b 的任意函数，也即 任意选取s + 1 个初始向量。 定义1 6 ：若对某个整数j 0 ，k 2 s 时，吼与k 无关，则称此迭代法为定常 的，否则称为非定常的。若对任意七，m 。是矿，j 1 ，工“1 的线性函数，则称迭代 法是线性的，否则称为是非线性的。 最简单的线性定常迭代法是一阶线性定常迭代法，此时迭代格式可表示为 石“1 = g x + g ，k = 0 ，1 ，2 ，一， ( 1 2 ) 其中g 为矩阵，g 为向量，x 。为任意的初始向量。 迭代法( 1 2 ) 称为简单迭代法，其中g 为迭代矩阵。 简单迭代法可由矩阵分裂 a = m 一( 1 ，3 ) 导出，如此的简单迭代法的迭代矩阵为g = m - 1 ，着p ( m 。n ) 1 ，则称矩阵分 裂( 1 3 ) 是收敛的，否则称其为发散的。 定义1 7 ：矩阵分裂( 1 3 ) 称为是： ( a ) 非负的，如果肘- 1 存在，g = m - 1 n 2 0 ； ( b ) 正则的，如果肘。存在且m 。0 ，n 0 ； ( c ) 弱f 则的，如果肼一1 存在且m 。0 ，m 一0 ； 张惠广义加速超松弛方法解线性互补问题 9 ( d ) 肘一分裂：如果时是m 一矩阵且n 0 。 从定义i 7 立即看出，m 一分裂是正则分裂，正则分裂是弱正则分裂，弱正 则分裂是非负分裂，但它们的逆命题不复成立。 关于线性互补问题的基本理论，我们首先引入一定义：若x r ”，x + 的各个 分量被定义为o + ) j = m a x o ，x ，) ，= 1 ，2 ，疗 对于任意的工，y r 4 ，下面的四个性质显然成立： ( a ) ( x + y ) + s x + + j ，+ ： ( b ) 工+ 一y + ( x y ) + ； ( c ) 旧= t + ( 一z ) + ； ( d ) 工y j x + y + 对于线性互补问题l c p ( m ，q ) 。下面的两个引理很重要。 引理1 8 【1 3 】：设m r ，e 是对角元素均为正的对角矩阵，则有： 2 m z + 。口。 1 , ( z - c t e ( m z + q ) ) - z = o , ( 1 4 ) z 7 ( m z + g ) = 0 j 其中盯是任意的正常数。 弓l 理1 9 【2 l 】：设m r 是一个对角元素均为正的抒一矩阵，则线性互补闯 题l c p ( m ，q ) 有一个唯一的解z + r ” 扬州大学硕士学位论文 l o 2 已有相关结论 在 4 中，作者提出了一类解决线性互补问题的修正的加速超松弛迭代方法 ( 简称为m a o r 方法) ，当系数矩阵m r ”“是一个2 一循环矩阵时，m a o r 方法 和m s o r 方法被提出，并且作者讨论了他们的收敛性以及单调收敛性质。 在那篇文献中，系数矩阵m 满足性质4 ，特别地，m 有这样的形式： 肘= ( 篓差) ，其中，d l r ”m ，d 2 r 似小扣1 都是非奇异矩阵。 设q = d i a g ( 埘a i l ，2 ，2 ) ，其中q ，0 ) 2 0 ，f = d i a g 眵i i ，矽z ) ，1 1 r ”。1 ，m a o r 方法的迭代格式为： z p l = ( z 一d 一 ，心，“+ ( w 一皿) z p + 】) + 当，= 卯，时，m a o r 方法就转化为m s o r 方法，所以m s o r 方法的迭代格式为： z 9 = ( z 9 一d o j 2 l z 9 + ( 【协+ 国l u ) z ，+ f 】) + 两种方法提出后，作者考虑了其收敛性，得出了结论： 定理2 1 4 ：设m = ( m h ) r 是对角元素均为正数的h 一矩阵，且m 有分 裂满足掰) = d - i l l - i v ，则对任一初始向量z o 丑“，由删锹方法产生的迭代 序列 z p ，收敛于l c p ( m ，q ) 的唯一解z r ”，并且满足： p ( ( q ) i r i ) _ m 。a ：x 1 1 一q i + q p ( 1 j 1 ) ) 1 ， 当q 和缈2 分别满足。 毡 石了2 丽，。 鲍 石i 2 丽，。，吃时。 类似地，作为m a o r 方法的特殊情况，对于m s o r 方法也有其收敛性的结论。 推论2 2 1 4 ：设吖= ( 朋。) r 是对角元素均为正数的h 一矩阵，f 1 m 有分 裂满足( m ) = d - i i - i u i ，则对任一初始向量z 。r ”，由m s o r 方法产生的迭代 序列 z 9 收敛于l c p ( m ，g ) 的唯一解z + r ”，并且满足： 张惠广义加速超松弛方法解线性互补问题 p ( ( q ) 。 r i m 。a x 1 1 一q l + q p ( m l ， 当珊t 和吐分别满足。 q 丽2，。 吐 五靠时 当m 是对角元素均为正的按行不可约对角占优矩阵或按行严格对角占优矩 阵时，上述的定理和推论也适用于这些矩阵，且有 p 日卅) _ m a x e r t ，仃2 = 盯 l ， 其中盯= m 。，0 i = l i d , - t 【，k = 0d l 1 1 。，c r 2 = 0 d ，l 。= 0 珥足k 定理2 3 4 ：设m g “”是对角元素均为正的按行不可约对角占优矩阵，则 对任给初始向量z o r ”。由m a o r 方法或m s o r 方法产生的迭代序列 2 ， ，p = 0 ，l ，2 ，收敛于l c p ( m ，q ) 的唯一解z ，且满足 p ( ( 帅 m a x 1 一q i 十q 盯) 1 ， 当在删锨方法中，o 二1 + o - ，o y 2 赤5 ， 在脚肪法中，呦- 高，o c o ：焘4i + 盯l 十仃 定理2 4 1 4 ：设m r 是对角元素均为正的按行严格对角占优矩阵，则对 任给初始向量z o 掣，由m a o r 方法或m s o r 方法产生的迭代序列 z ， ，p = o , 1 ，2 ，收敛于c p ( 膨，g ) 的唯一解z ，且满足 p ( ( 谚。 r 1 ) 罂蛩日l q i + q 田 1 ， 。 当在心。胃方法中，。 q 再，。 吐 i ，o s y s c o x , 在燃方法中，。 q 五，。 吐 去 在【4 】的最后一部分，作者描述了j | l 翻0 幔方法和 舶尺方法的单调收敛性质且 讨论了松弛因子和加速因子对收敛速度的影响。 扬州大学硕士学位论文 定理2 5 4 ：设m r 是一矩阵，则对任意的初始向量z o = o ，由 m a o r 方法或m s o r 方法产生的迭代序列仁9 和伽9 ，p = o , l ，2 ，其中序列 口9 对应的参数为( ，q ，缈：) ，序列扣9 对应的参数为( 尹，0 3 1 ，匠) ，则臼一 和伽， 都收敛于l c p ( m ，譬) 的唯一解z ，且有 ， z 9s 彩9 ，p = o , 1 ，2 ， 当参数( 扎缈i ，：) 和( 歹，蠢，匠) 分别满足 0 。 z = ( 1 一咏磁一i ( o kt 否k - 1 z ，+ 熹z j + 吼】 ( 3 9 ) 疗 2 0 t 毪 = 七 扬州大学硕士学位论文 1 6 4 两种算法的收敛性 在讨论两种算法的收敛性之前，我们首先定义一个映射厂：r 4 - 足”，满足 ( z ) = 亭，其中 善= ( z d 。善+ ( t i m - a o l ) z + n q l ) + ， 令 q = ，一a d d l ， r = ，一d 一( 叫- a o z ) 定理4 1 ：设m = i 研。) r 是对角元素均为正数的h 一矩阵，分裂( 3 3 ) 满 足( m ) = 。一i l _ l u l ，若。 q 百了2 丽，= 1 ，2 ，口r + ，则对任一初始向 量z o 月n ，由g a o r 方法产生的迭代序列 z 9 ) 收敛于l c p ( m ，q ) 的唯一解 z 置”，并且满足： p ( ( q ) - l i r | ) 麟 l l 一l + 。p 帅 l ，当o 口1 时， ( 4 1 ) p “扪r 啡一剖+ 吉僻 h p l ，当纠时。( 4 2 ) 证明：首先设0 口1 ，令r l = ，( y ) ，也即 军= ( ) ，一d 一【a q 上弩+ ( 鲫一缸l d y + o * t ) + 则善一1 = ( z - d 一1 口q f + ( w 一口f 2 ) 暑+ 】) + 一( y d 一1 【口q 叩+ ( ( w a f m ) y + 】) + ( ( z y ) 一d 一1 “心m ( 善一叮) + ( 【w - a o l ) ( z y ) 】) + 所以 g 一玎) + s ( 一a d 一0 正( f 一叩) ) + + ( 【，一d 一1 ( w n r 址) 】( z 一) m + ( 4 3 ) 类似地，我们可以得到 ( 叩一掌) + ( 一a d 一魁一孝) ) + + ( 【卜d i l ( m ，一础) 】( y z ) ) + ( 4 4 ) 张惠广义加速超松弛方法解线性互补问题 1 7 所以 溶一叫= ( 善一玎) + + ( 7 一手) + s ( - g d 。q 三( f 一，7 ) ) + + ( 一a d “q ( 叩一孝) ) + + ( u - d 。( q z 一拉魁) 】( z y ) ) + + ( 【，一d - 1 ( q f a q ) 】 一z ) ) + ， = p 。m ( 孝一r 1 ) + l 【l - d 。( c m y - a n o ( z - y ) l 加一1 中怙一卅l 一d 一( r i m 一她) l l z - y 1 ( 4 5 ) 由引理1 9 中知，在定理条件下，l c p ( m ，叮) 有唯一解z r “，即z = f ( z ) ，从 g a o r 方法的定义和( ，5 ) 式，有 z p + l z | = f ( z 9 ) 一他叫( q ) 。川z 9 一z | 所以，若户( ( q ) i r i ) 1 ，则迭代序列 z ， ，p = o 12 收敛于z ，因为m 是一个日一 矩阵，所以p ( i j l ) 1 ，在 1 的定理3 中，有 p ( t m 。a 。x 1 1 一哆l + 哆p ( 1 卅) ， 其中 丁= ( ，一优d 。q l l ) 。0 ，一g + o a ) d 。1 d i + d q u l ( 4 6 ) 另一方面，f ( 功一 r i - l 时，由p ( ( 锄) l 和。 吉 再面2 面两， 由外推原则亨p ( ( q ) 。l r l ) s i l 一剖+ i i 户( ( q ) ) f t 剖+ 吉蹬m 刊+ q 础i ) ) h + i i = 1 作为g a o r 方法的特殊情况，对于g s o r 方法，有如下的收敛结果： 推论4 2 ：设m = ( m 。) r “”是对角元素均为正数的h 一矩阵，设分裂( 3 3 ) 满足( 膨) = d h l u i ，若o 哆 再j 2 丽f = 1 ，2 ，n ，则对任一初始向量 z o r ”，由g s o r 方法产生的迭代序列 z ， 收敛于l c p ( m ，q ) 的唯一解，并且满 足 p ( ( q ) 。) 鉴 l l q l + q p q 卅) 1 注4 3 ：我们已经知道一个肘一矩阵也是一个h 一矩阵，所以定理4 1 徊推论 4 2 的结论对膨一矩阵也成立，既然一个对角元素均为正的严格或不可约对角占优 张惠广义加速超松弛方法解线性互补问题 1 9 矩阵也满足定理4 i 的条件，则定理4 1 和推论4 2 也适用于这些矩阵，进而对 于这些矩阵，m 旧够代替户0 卅) 在定理4 1 和推论4 2e p 。 为了描述收敛定理，令盯= 。，若m 是按行严格或不可约对角占优矩阵， 则p ( i 邓盯 1 ，由定理4 1 ，我们可以得到下面的收敛结果： 推论4 4 ：设m r 是对角元素均为正的按行严格对角占优矩阵，则对任一 初始向量z o r “，由g a o r 捌g s o r 方法产生的迭代序列 2 ，) ，p = 0 , i ，2 ，收 敛于l c p ( m ，g ) 的难一解z ，且有 ( a ) 在g a o r 方法中，若0 q l ，i = 1 , 2 ，甩，0 o f l ，则 l 十盯 p ( ( q ) 。帅慨扯q l + q 仃) 1 ( 4 7 ) ( b ) 在g a o r 方法中，若0 够 1 ，则 1 4 - 盯 户( ( q ) “i r 畦罂1 - 剖十l m a 。x l - q i + q 盯) 1 ( 4 8 ) ( c ) 在g s o r 方法中，若o 珊， ，i = 1 , 2 ，万，则 l 十仃 p ( 锄。 r ) s m 。a 。x i l q + 哆仃) 1 ( 4 9 ) 扬州大学硕士学位论文 5 两种算法的单调收敛- 陛 首先定义一个集合= 扛r 4i x 0 , m x + q 2o ) ，很显然，若线性互补问题 l c p ( m ，g ) 是有解的，则集合是非空的。 下面来研究映射f ：r ”j 满足，( z ) = 善的单调性质，其中 掌= ( z d 一1 f + ( r m ，一a n l ) z + n q ) + ( 5 1 ) 定理5 1 ：设映射，：r 4 _ 月”如( 5 1 ) 所定义，又设m r “是三一矩阵， 并且有分裂( 3 3 ) 式，设o 0 ，l o 得 磊z 2 ，磊气，磊z 。， 贝亭= f ( z ) s z ，证得( a ) 。 下证( b ) ：设玎= 八y ) = ( 仉，7 ：，仉) 7 ，则由g a o r 方法有： 所以 ”( 旷c o k 口蔷k - i 盱铂嚆嘲，圯】) + 扣1 2 ，拧 伍4 ) 磊 0 ，1 - - o f 0 ，y z ，并且三0 ，u 0 ，所以r 1 卣，从而得到： 可2 磊，现岛，磊， 也即：可善，厂( y ) f ( z ) ，证得( b ) 。 现在证明( c ) ：由映射，的定义知善= ( z ) 0 ，而且有 m 专+ q = d 专+ l 专+ u 专2 d 专+ l 毒+ u z 七q 2 d ( z - d q 【以( 孝一力+ 缸+ g 】) + 工善+ 沈+ g = d z - a t 2 l ( 善一z ) 一r x d + 三+ u ) z q g 4 - 三掌+ u z + g 扬州大学硕士学位论文 所以得： 掌 定理得证。 = ( ，一( 刁( d z + u z + g ) + ( i - a a ) t 4 - 0 - u ) t z l z ( j f 的( d z + u z + g ) + ( ，一a a ) t , z 一( 1 - a ) o z z = ( ，一q ) ( d z + u z + q ) + ( ，一t 1 ) l z = ( i 一哟( d z + l z + u z + g ) 0 2 2 运用上面的定理5 1 ，可以证明g a o r 方法和g s o r 方法的单调收敛性质： 定理5 2 ：设m r 是一矩阵，设0 c o t l ，f = l ，2 ，n ，0 口l ，则对 任一初始向量矿a ，由g a o r 法或g s o r 法产生的迭代序列 z 一) ，p = o ，1 ，2 ，有 如下的性质： ( a ) 0 z 9 + 1 z p 茎z o ，p = 0 , 1 ，2 ，； ( b ) l i m z 9 = z ，其中2 l c p ( m ，g ) 的唯一解。 口，w 证明：我们仅仅对g a o r 方法进行证明：因为z o a ，由定理5 1 的( a ) 知 z z o 和z a ，则反复运用知0 z ”1sz 9 z o ，p = 0 , 1 ，2 ，所以( a ) 得证。 下证( b ) ：由( a ) 可知伫9 ，p = o ，l ，2 ，是单调有界的，所以该序列收敛于莱z ， 且满足： z + = ( z 。一d 。 n ( 比+ ( r 2 ，一a t m ) z + + 啦】) + ， 也即 z = ( z 一d 一1 n m z + q g 】) + 所以z 。是线性互补问题l c p ( m ，g ) 的唯一解。 张惠广义加速超松弛方法解线性互补问题 最后一部分我们来讨论参数q ，f = 1 , 2 ，疗和参数口对g a o r 方法和g , s o r 方 法的收敛速度的影响： 定理5 3 ：设m r “。是三一矩阵，贝q 对任意的初始向量z o = y o a ，由g a o r 方法或g s o r 方法产生的迭代序列 z 9 和 y v ) ，p = o , i ，2 ，其中仁9 ) 对应的参 数为位，( 0 1 ，埘。) ， y 9 对应的参数为函，面，玩) ，若满足0 c o t q l 。 i ；1 , 2 ，月，0 五 口l 。则序列扛9 ) 和 y 9 ) 都收敛于z ，且有 z 9 y 9 ，p = o ，l ，2 ， ( 5 5 ) 证明：序列 z 9 和 y 9 ) 的收敛性可由定理5 2 得到，下面证明( 5 5 ) 式： 和定理5 1 类似，我们可以证明z 9 ，y 9 ，p = o ，l ，2 ，设q = a i a g ( & ，五，玩) ， 则 y 9 “= ( y 9 一d 一。瞳两勿”1 + ( a f 一3 f i l ) y 9 + 壶们) + 因为 3 壶l y “+ ( q m 一3 凸l ) y 9 + q 目= 口壶上( _ y p 一y p ) + q ( 坳p + g ) a 0 匹( y 州一y v ) + q ( 五旁+ 譬) 所以 y p + | ( y 9 一d _ 【口( m ( y p “- y 9 ) + q ( 耖+ g ) 】) + = f ( y 9 ) ( 5 6 ) 用数学归纳法证明( 5 5 ) 式，事实上，当p = 0 时，( 5 5 ) 式显然。设( 5 5 ) 式 对某一正整数p 成立，则由定理5 1 和( 5 6 ) 式有 y ”1 f ( y 9 ) f ( z ) = z 9 “ ， 所以2 ”j ，9 ，p = o ，1 ，2 ，则定理成立。 扬州大学硕士学位论文 注5 4 ：定理5 2 和定理5 3 证明了当参数q = 2 一= = 口= 1 时能导 致更快的收敛速度，这也意味着导致收敛速度最快的参数可能在【l ，+ m ) 中，也即 口，珊_ 出：，珊：【1 ，+ a 。) 。 张惠广义加速超松弛方法解线性互补问题 6 数值实验与小结 考虑一个线性互补问题l c p ( m ，q ) ，其中m = 4一l l4 o一1 0o oo 一1o 4 一l l4 q = ( - 1 ，3 ，- 4 ，2 ) 7 ，因为m 是对角元素均为正的按行严格对角占优矩阵，所以对任 一初始向量，r ”，由g a o r 方法产生的迭代序列扛，) 收敛于该线性互补问题豹 唯一解z = ( 1 0 0 0 ，0 0 0 0 ，1 0 0 0 ，0 ，0 0 0 ) 7 。 设给定初始向量z o = ( 2 ，3 ，4 ，5 ) 7 ，下面的表格给出了数值结果： 参数迭代次数 a ( o i哆0 0 3c 0 4 1 61 41 3i 21 63 6 2 3 1 22 33 4 l 31 5 3 4 2 3 3 4 7 8 l 21 2 l1l1l4 从上表我们可以看出参数越接近于l 时，序列收敛于线性互补问题的精确值 所需的迭代次数就越少，也就是说迭代速度更快，这也证明了定理5 2 和定理5 3 的结论。 在本章中，我们提出了一类解决线性互补问题l c p ( m ，q ) 的广义的a o r 方法， 其特殊情况转化为广义的s o r 方法。在给出两种算法的基础上，我们讨论了当系 数矩阵m r 一是日一矩阵，m 一矩阵及严格的或不可约对角占优矩阵时两种方 法的收敛性，并且得到了相