（计算数学专业论文）关于鞍点问题若干性质的研究.pdf

， 一 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 王遣重远日期：砂o 年夕月多目 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：垲导师签名： 日期： 7 ，f b 年，月日 r k 一 t _ ， - t s y s t e m ”( 来自于k a r u s h k u h n t u c k e r 一阶优化条件) 因此研究鞍点类型的线性 系统具有重要的意义，但鞍点矩阵一般是不定矩阵又具有较弱的谱条件，所以对 鞍点矩阵性质的研究是困难而重要的研究领域 本文主要做的工作如下： 第一部分，综述了鞍点问题的产生背景以及鞍点问题的基本概念与分类： 第二部分，广义鞍点问题的性质的研究，给出鞍点矩阵可对角化的新条件，同 时给出了鞍点矩阵具有有实( 正) 的特征值的充分条件： 第三部分，h s s 预处理技术研究，本文主要对h s s 预处理后的矩阵的谱进行了 研究，对其特征值的实部的上下界作了更精确的估计 关键词：鞍点矩阵，谱条件，可对角化，预处理 一 i - 一 一 a bs t r a c t l a r g ej i n e a fs y s t 锄so fs a d d l ep o i n tt y p ea r i s ei naw i d ev a r i e t yo fa p p l i c a t i o n s t t l r o u 曲o u t c o m p u t a t i o n a ls c i e n c ea n de n g i n e e r i n g ，s u c ha si nt h ei 芏1 c o m p r e s s i b l ef l o w m e c h 锄c sf i e l d s ，t h ef a m o u sn a v i e r - s t o k e s e q u a t i o n s a r et h e p a r t i a ld i f f e r e n t i a l e q u a t l o n sw l t hc o n s t r a i n t s t y p i c a l l yt h ec o n s t r a i n t sr e p r e s e n ts o m eb a s i cc o n s e r v a t i o n 1 a w ( c o n s e a t i o no fm o m e n t u ma n dm a s sc o n s e r v a t i o n ) ，d i s c r e t i z a t i o no f t h ee q u a t i o n s l e a d st ot h es a d d l ep o i n tp r o b l e m s b e c a u s es a d d l ep o i n t e q u a t i o n sc a nb ed e r i v e da s e q u l l l b n u mc o n d i t i o n sf o rap h y s i c a ls y s t e m ，t h e ya r es o m e t i m e sc a l l e de q u i l i b r i u m e q u a t i o n s ；b u ta o t h e rp o p u l a rn a m ef o rs a d d l e p o i n ts y s t e m s ，e s p e c i a l l yi n t h e o p t l m l z a 1 0 ni i t e r a t u r e ，i s k k t s y s t e m ( f r o mt h ek a r u s h - k u h n - t u c k e rf i r s t o r d e r o p t i m a l i t yc o n d i t i o n s ) t h e r e f o r e ，t h er e s e a r c ho ft h el i n e a rs y s t e n l so f s a d d l ed o i n t t y p eh a s 蚰p o r t a n tm e a n i n g ，b u td u et ot h e i ri n d e f i n i t e n e s sa n do r e np o o rs p e c t r a l p r o p e r t i e s ，s os i g n i f i c a n tc h a l l e n g ef o rs o l v e rd e v e l o p e r s i nt h i st h e s i s ，o u rm a i nw o r k i n c l u d e si nt h e f o l l o w i n g ： ， l nt h ef i r s tp a r t ，w ew i l lc o n c l u d et h eo r i g i no f t h es a d d l ep o i n tp r o b l 锄a n di t s b a s i cc o n c e p t i o na n dc l a s s i f i c a t i o n ； i nt n es e c o n dp a r t ，a c c o r d i n gt oa n a l y z et h ec h a r a c t e r so f t h eg e n e r a ls a d d l ep o i n t p r o b l e m ，w eg e tt h en e ws u f f i c i e n tc o n d i t i o nt h a ts a d d l e p o i n tm a t r i xw i l lh a v e 口o s i t i v e s p e c t r u ma n dm a yb ed i a g o n a l i z a b l e ； i nt h et h i r dp a r t ，b a s e do nt h ei n t r o d u c t i o no ft h e p r e c o n d i t i o n ，w em a i n l ys t u d y t h es p e c 仃a jp r o p e r t i e so ft h ep r e c o n d i t i o n e dm a t r i c e s a n dw e e s t i m i t et h eu p d e rb o u n d a n dt h el o w e rb o u n do f t h er e a lp a r to ft h ee i g e n v a l u em u c h m o r ea c c u r a t e l v k e y w 。r d s ：s a d d l ep o i n tm a t r i c e s ，s p e c t r a lp r o p e r t i e s ，d i a g o n a l i z a b i l i t y ，p r e c o n d i t i 。n lfjiffjlfjilj1ifjlijlfjifjlliiiiii_ 0 一 1 5 1 3 本文创新点7 1 4 论文结构安排7 第二章鞍点问题的相关性质8 2 1 对称鞍点问题的特征值分析8 2 2 非对称( 广义) 鞍点问题的谱分析8 2 2 1 概念和性质8 2 2 2 广义鞍点矩阵的谱条件分析1 0 2 2 3 数值算例16 第三章鞍点问题的预处理技术18 3 1 预处理技术的简单介绍1 8 3 2 广义鞍点问题h s s 预处理矩阵的谱分析2 2 3 2 1 h s s 预处理方法的介绍2 2 3 2 2 h s s 预处理矩阵的谱分析2 4 3 2 3 数值算例3 1 第四章结论与展望3 4 致谢3 5 参考文献3 6 作者攻硕期间取得的成果4 0 i l l 第一章绪论 1 1 选题背景和意义 第一章绪论 随着计算机科学与技术的发展，大型线性系统的研究与计算成为了科学计算 的重要课题，而大规模的鞍点类型的线性系统出现在许多重要的研究领域，如约 束最优化、约束与加权最小二乘估计、经济学、电磁学、图像重构、图像定位和 参数识别等计算科学与工程学领域比如， 1 在不可压缩流体中，对于稳定的n a v i e r - s t o k e s 方程【1 】 v a u4 - u g r a d u 4 - g r a d p = f d i v u = o ， b u = g 其中y 0 表示运动粘度系数，表示拉普拉斯算子，u 代表速度，代表压力，而 是某种有界算子 为了唯一地决定p ，需要强加一些条件，比如 d x = 0 可以看出n a v i e r s t o k e s 方程是非线性的，要将其线性化可以选择p i c a r d s 迭代 那么，需要构造一系列的近似解( “，p 。) ，从而转换为了求解线性的o s e e n 问题， 一v a u + ( 一1 g r a d ) u + g r a d p = f d i v u ) = o ， b u ) = g 在一定的条件下，这个稳定的n a v i e r - s t o k e s 方程有唯一的解，并且每次迭代 当七专0 0 时，对于任意初始值“o 的选取，迭代是收敛的 电子科技大学硕士学位论文 所以，在每次p i c a r d s 迭代中，我们需要解一个o s e e n 问题，形如 一l ，i | + ( 1 ，g r a d ) u + g r a d p = f d i v u = o ， b u = g 如此反复求解，也就是将其线性化离散化的过程，这样就产生了线性的鞍点类型 的代数系统： ( ao r 怍j k v ) m 其中a 对称半正定，b 是满秩的( 当然也可以利用c f d 软件直接产生) 其中一个重要的特殊例子，其中v = 0 ，那么相应的稳定的s t o k e s 方程为 一a u + g r a d p = f 然而，不失一般性，我们可以定义v = 1 ，那么就可以将此稳定的s t o k e s 方程解 释为欧拉一拉格朗日偏微分方程： m i n m ) = v “哆一厂一， s u b j e c t t o v “= 0 其中l | ul ：= “表示向量“的欧几里得模从而压力p 就是拉格朗曰乘子 那么稳定的s t o k e s 方程就是描述一种慢流的，高粘性的流体流动将其近似离 散化以后就产生了一个对称的鞍点问题，其中彳是一个块对角矩阵而且它的每个 对角块是一定近似界条件的拉普拉斯算子一的离散化那么此时的彳是对称半正 定的 2 约束的加权最小二乘问题，形如 m i n 忙一回| l ： s u b j e c tt oe y = d 其中c r p , g r p x m , y r m , e q x m , d r q , q 屯+ 2 石万， ( 2 3 ) 时，则移c ( 厂) 是正定的，锣是可以对角化的而且有实( 正) 的特征值而且莎c ( 多) 的谱条件数满足： 枷纠；矧鬲2 ( a - 丽6 1 + 瓯) 定理2 1 设a 为对称正定矩阵，b 为行满秩矩阵，c 为对称半正定矩阵如果 y = 圭( 。+ 允) ，且 “ 瓯，- i - 2 、吒， ( 2 4 ) 则矽c ( y ) 是正定的，彦是可以对角化的而且有实( i g ) 的特征值并且莎c ( ) 的 谱条件数满足： 捌纠_ 搠等爱 证明：已知护是矽c ( 7 ) 的任意特征值，而且 x ，y + 】是相应的特征向量，其中 石表示向量石的共轭转置，从而 矽c ( 7 ) x + ，y = 臼 x ，y 。， 彳z 一尹z + b r y = 臼z ， ( 2 5 ) 电子科技大学硕士学位论文 接下来考虑以下三种情况： b x + 亍y c y = o y ( 2 6 ) 第二章鞍点问题的相关性质 瓦歹1 百工b7 戤石+ b r ( ( 秒一尹玩+ c r ) 一1 戤瓦丽1 z 男r 眈， ( 2 - 9 ) 从口一尹+ 4 0 ，( 2 8 ) 和( 2 9 ) 我们可以得出 z 血一尹x x + 瓦号百z 冶r 戤叙。z ， 因为x a x 0 ，0 - 尹+ 8 1 0 ，那么 臼一尹+ 4 + 了x * b 万r b x ( 臼一尹+ 4 ) ( 秒+ 尹) 毫， ( 2 - 1 0 ) 由于丽( b x , b x ) = 搿矧挪么将不等北加，左边放大为 州m 等舛m + 鲁， 协 因为伊一尹+ 4 0 ，即口 歹一4 ，而且秒+ 尹 2 尹一瓯= “+ 巧。一匹，从( 2 4 ) 式可 以得出 口+ 胗“+ 吒一4 2 8 一4 + 2 厄 o ， ( 2 1 2 ) 从( 2 1 2 ) 式以及 ；土，我们可以得出 xa x p n ( 州+ 4 ) ( 州) 熹( 州+ 瓯) ( 州) 去，( 2 - 1 3 ) 从( 2 1 0 ) ，( 2 1 1 ) 和( 2 1 3 ) ，我们可以得出 州哪盘- t i ( 州+ 4 ) ( 嘶) 去 将上面不等式展开可以得到关于秒的二次不等式 1 3 电子科技大学硕士学位论文 9 2 一( 。- a , ) e 一夕2 + ( 以+ 西) 少一( 4 + 吒h 一1 ) 以o ， ( 2 1 4 ) 求解( 2 1 4 ) ，可以得到p 的上界 臼兰( 以一4 + 乙i _ 二j j f ：i i 了互= = | 乙i _ 二否j 丐_ _ i i j i 丽) = 批讲瓜百雨再丽丽) 。协 第三种情况：( e - y ) i 。+ c 0 显然 而且 9 一夕+ 吒 0 ， ( e - 7 ) o + c ( 臼一尹+ 瓯) l _ 4 ( ，一毛) 2 4 0 ，那么 ( 2 2 2 ) 以一4 + 氏一圭( 以一4 + 乙：_ 二z i 二i i ：_ 戛了产：_ 瓣) 。，( 2 2 3 ) t综合( 2 2 1 ) 一( 2 - 2 3 ) 的结果，可以得出 圭( d i - - 瓯一2 厄) 秒“一4 + 名， 即产生了匿( 彩c ( 尹) ) 的上g - 证明完毕 定理2 2 已知彳对称正定，口行满秩，c 对称半正定如果“ 屯+ 2 乏， 1 5 电子科技大学硕士学位论文 那么，非对称鞍点矩阵 够：卜 b 有正的特征值 证明：从注释2 1 和定理2 1 的证明，我们可以知道，如果满足一定的条件，可 以保证钐的所有特征值是实的 广，1 已知五是5 y 的任意一个特征值，甜= l l 是相应的实特征向量，并且满足 = 1 ，) g z , ， - = ： ； = 兄 ； ， 兄= x r y 7 x y = p y 7 匕础 - i ， 的 矿 意 r 一 任 b 于 、 扩 c l _ 第二章鞍点问题的相关性质 r3 l 钐：i 5 l 一6 lo 尺4 x 4b 0 ，c 0 ， 我们可以计算得出“= l ，吒= 以= 3 c ，= 吒= 里乎6 2 ，吒：晚：西： 那么代入引理2 1 得出 代入引理2 3 得出 代入定理2 1 得出 显然， 以得出，当 入( 2 2 6 ) 1 1 2 c + 4 b 2 ( 9 1 + - , , 5 8 7 7 、 4 8 1 3 c + 2 l b 1 3 c + 2 1 b i 当c 取接近古时，( 2 2 4 ) 式就不能够满足，而将其代入 i b l o 1 9 7 4 时，能保证廖可以对角化而且有正( 实) 的特 可以得出i b i 0 3 7 5 0 事实上，通过m a t l a b 计 ( 2 - 2 4 ) ( 2 2 5 ) ( 2 2 6 ) ( 2 2 5 ) 中可 征值，将其代 算得出，当 l b i 0 是一个实参数，在【4 6 】中，作为典型的a d i ( a l t e m a t i n g d i r e c t i o ni m p l i c i t ) 电子科技大学硕士学位论文 方法 那么接下来研究了预处理矩阵的特征值问题，其中 ( 万+ j ) 石= r ( 2 a ) 一1 ( 万+ 口z ) ( + 口z ) x ， o r9 f x = r i p x ， ( 3 2 ) 其中( r l , x ) 是预处理矩阵尸叫廖的特征对 3 2 2 h s s 预处理矩阵的谱分析 ( 3 - 3 ) ( 3 4 ) 第三章鞍点问题的预处理技术 j ( o ) 和谚( 秒) 分别表示秒的虚部和实部 注释3 1 已知4 是对称半正定的，那么 o 以华丑v u ec 一，“0 ， “甜 引理3 1 删假设么是对称半正定的定义k ：= ，+ 古b r b 对于( 3 2 ) 中任意 的特征对( 7 7 ， “；1 ， ) ，r = 丽2 0 ，其中乡0 并且满足： 1 如果i ( o ) 0 ，那么 劳= 三等，l e l 2 = i u * k b 矿r b u ( 3 - 5 ) 2 如果( 秒) = 0 ，那么 秒p ， ( 3 6 ) 其中夕：2 a ( 1 + o - 1 ，2 ，、 口。 注释3 2 我们可以知道k ：= + 古b r b 是对称正定的，所以 从注释3 1 可以得出， k ( 妒1 每，i n ( 她1 ， ( 3 _ 7 ) 而且我, f i q e 容易可以得出 以了u * k a 万k u a ( 3 8 ) 南 乃 电子科技大学硕士学位论文 引理3 2 【删在引理3 1 的假设和定义下，问题( 3 1 ) 的特征值为： 1 女口果。矿( 刁) 0 ，男巧么 ( 3 9 ) 乎 黝协蔫) ， 悖 ( 3 1 1 ) ( 3 - 1 2 ) l 舯一k 垒+ “。生“也l 亳篇 一目u 第三章鞍点问题的预处理技术 一 f m i n l 3 口2 + 三刀a 2 + 4 ” 鬈 嘲+ 衙 1 0 而且 m 等鲁k 可2 p 南) ， ( 3 - 1 3 ) 其中万：= a ( 1 + 争) ，而且p ：= a ( 1 + 事) 证明：定义x = u ；v 】0 是关于9 的特征向量而且从( 3 4 ) 可以得出下列两个 矩阵方程： 彳( ，+ b ) u + b r v = 锄，( 3 - 1 4 ) 一b u = 钆( 3 1 5 ) 我们可以假设：“0 1 ， 由( 3 1 5 ) 可以得出，1 ，= 一9 b u ，将其代入( 3 1 4 ) 中得到 秒彳( n 1 咖) “b 甜纠玑 用“+ k 左乘方程的两边，可以得到： o u k , 4 k u u k b r b u = 秒2 u k u 如果上述二次方程有实根，那么从( 3 3 ) 可以得出( 刁) 0 ， 2 7 电子科技大学硕士学位论文 那么 ( u * k a k u ) 2 - 4 ( u + k u ) ( u k b r b u ) 0 ， 而且根据( 3 7 ) 和( 3 9 ) ，得出 ( u k a k u ) 2 0 ，“+ k 2 “ 4 ( “+2 “) 2 “ 4 。 。净等崭希崭，( 3 - 1 8 ) 由( 3 1 6 ) ，( 3 1 7 ) 和( 3 - 8 ) ，得出 ( 3 1 9 ) ( 3 2 0 ) 从而得到 第三章鞍点问题的预处理技术 卜口等卜却一u k a k u + 2 一u * k b r b u ， 2 ， 将( 3 8 ) ，( 3 - 1 8 ) 和( 3 1 9 ) 都代入( 3 2 1 ) 中，而且谚( 7 7 ) 0 ，那么 通过计算可以得出： p 缪( 7 7 ) 4 0 ：2 3 口2 劈( 7 7 ) + 吮) 砑( 7 7 )纽2 砌2 岳， 吮( 口2 + 嵋) 谚( 7 7 ) 1 2 魄+ i 霄 二 口2 + 嵋 鲰最 尺( 7 7 ) 三呈! 当 0 6 + 以 二生_ r ( 7 7 ) 口+ a 吮+ 丢砰 口2 + 嵋 2 州口南 口+ 丸 、2 a + 2 0 ：口一o + ? 孑 尺( 7 7 ) 二乇工 口+ 以 2 9 哪扣 + + 矿 以 涫 吮 ，【 2 ，= = 、 2 p “ 纤 嵋哪 矧 嘲 切矿 历 氢 吮 口几。 坛 吮 一扩 叠+ 力盯一功 一万 弋 2 茸， 吃厨 2 l 铊 嵋 弘 口 一 印 秘 ，一2 口 k 艳 吮 2 口 ，、，【 砰 掰0 2 吮 一 电子科技大学硕士学位论文 那么这些结果的交集就是结果( 3 1 2 ) 继续完成下一个结果的证明 通过式( 3 3 ) ，我们可以得出 ( 口2 + 2 口q ) f 7 7 1 2 = ( 4 一1 7 7 1 2 ) i 臼1 2 将其代入( 3 5 ) 中，然后将等式两边同除以“+ k 2 u ，得出 ( 口2 丽u k u + 口訾) 卅i ( 4 一l 硎i ) u * “k k b r f b u 同理，我们对m 2 的两边求界，根据( 3 7 ) 和( 3 - 9 ) ， 我们可以得出 由( 3 8 ) ，( 3 9 ) 和( 3 1 9 )，可以得出 通过计算，可以得出 ( 南+ 训开嘉( 4 _ i 秆) 丢砑( 4 一f 刁1 2 ) ( 口2 + 2 口2 ) 1 7 7 1 2 ( 南+ 训7 7 1 2 如2 ( 4 槲) 丢2 2 ( 4 一1 7 7 | 2 ) 驰2 + 嘲) 1 7 7 1 2 南跏卜南 赤跏卜一 篇 扩可 一口 第三章鞍点问题的预处理技术 同理，计算它的交集可以得出结果，那么第一部分的证明就结束了 如果仞) = 0 ，那么根据引理3 1 中( 3 - 6 ) 中实的护相应的界，再由( 3 3 ) 的关系，定理中第二部分的结果就得以证明了 3 2 3 数值算例 由一种地表水流体问题，将其问题离散化以后产生了一种鞍点系统【4 7 】，例中 n = 2 7 0 ，m = 2 0 7 ，z + m = 4 7 7 ，而且莎包含有1 ，7 4 6 个非零元素并且得出 以= 0 0 0 1 7 ，a = 0 0 1 0 ，0 1 = 2 6 11 而且吒= o 1 9 7 4 3 在此例中，对于非实的特征值，在表3 1 ，表3 3 中表示出了引理3 2 中( 3 1 0 ) 和( 3 。1 1 ) 给出的相应的上下界，还有p 叫廖的真实特征值，将它们进行比较；而 表3 2 和表3 4 同样也表示出了定理3 1 中( 3 1 2 ) 和( 3 1 3 ) 的上下界与真实值 的比较 表3 - 1 口 分( 刁)劈( 7 7 )卯( 7 7 )贸( r z ) 的取值的下界的最小值的最大值的上界 o 0 50 0 1 1 31 8 2 3 11 9 6 2 42 0 0 0 0 o 10 0 0 5 61 5 7 1 91 9 7 5 8 2 0 0 0 0 0 3o 0 0 1 90 6 0 9 01 9 6 6 42 0 0 0 0 0 50 0 0 1 10 2 7 4 81 9 2 4 92 0 0 0 0 1 00 0 0 0 60 0 7 8 31 7 4 2 42 0 0 0 0 3 00 0 0 0 20 0 0 9 80 8 6 2 l2 0 0 0 0 5 00 0 0 0 10 0 0 3 80 4 2 8 82 0 0 0 0 ( 3 1 0 ) 的界与非实特征值实部的真实值的比较 电子科技大学硕士学位论文 表3 - 2 口 刃( 刀)绍( 7 7 )( 7 7 )刃( 7 7 ) 的取值的下界的最小值的最大值的上界 0 0 5 0 0 2 8 8 1 8 2 3 0 1 9 6 2 42 0 0 0 0 0 1 o 0 1 5 61 5 7 1 81 9 7 5 82 0 0 0 0 0 30 0 0 5 50 6 0 8 91 9 6 6 41 9 9 6 0 o 50 0 0 3 30 2 7 4 81 9 2 4 91 9 4 2 6 1 0o 0 0 1 70 0 7 8 31 7 4 2 41 7 5 1 2 3 o0 0 0 0 60 0 0 9 80 8 6 2 10 8 6 4 9 5 o0 0 0 0 30 0 0 3 80 4 2 8 80 4 3 0 4 ( 3 - 1 2 ) 的界与非实特征值实部的真实值的比较 表3 - 3 口 m蚓蚓l r i 的取值的下界的最小值的最大值的上界 o 0 50 0 1 9 21 8 6 0 11 9 6 3 31 9 6 7 1 o 10 0 0 9 61 7 5 3 9 1 9 7 7 2 1 9 8 2 1 o 30 0 0 3 21 0 9 3 1 1 9 7 9 21 9 8 1 7 0 5 o 0 0 1 90 7 3 2 01 9 5 9 71 9 6 2 4 1 00 0 0 1 0o 3 8 6 71 8 6 5 51 8 8 1 8 3 o0 0 0 0 3o 1 3 1 31 3 1 2 51 5 9 6 4 5 o0 0 0 0 20 0 7 8 9 0 9 2 5 5 1 4 9 6 5 ( 3 - 11 ) 的界与非实特征值实部的真实值的比较 表3 - 4 口 l r i i r il r ll r l 的取值的下界的最小值的最大值的上界 0 0 50 0 3 1 01 8 6 0 11 9 6 3 3 1 9 6 6 5 o 1o 0 1 6 21 1 7 5 3 91 9 7 7 21 9 8 1 8 o 30 0 0 5 6 1 0 9 3 11 9 7 9 21 9 8 1 3 o 50 0 0 3 4 0 7 3 2 01 9 5 9 71 9 6 1 0 1 o0 0 0 1 7 0 3 8 6 71 8 6 5 51 8 6 6 1 3 o0 0 0 0 6 o 1 3 1 3 1 3 1 2 5 1 3 1 2 6 5 00 0 0 0 3 0 0