（计算数学专业论文）（k）jacobi矩阵特征值反问题算法的稳定性分析.pdf

2 0 0 4 上海大学硕士学位论文 摘要 摘要所谓( k ) j a c o b i 反问题就是，如果我们不知道j a c o b i 矩阵丑但是我们知道所有乃卜t 、死扎。和乃，。的特征值， 我们能否构造出矩阵蜀，。 令 s 1 = ( 肛l ，卢2 ，肛一1 ) ， s 2 = ( 卢女，芦+ 1 ，- 一，u - 1 ) ， a = ( a 1 ，a 2 ，a 。) 分别是矩阵蜀，女一1 ，丑+ 1 t 。a n dn ，。的特征值。则所提的问题变为 以上述2 n 一1 个数构造下面2 n 一1 个数： a 1 ，乜2 ，和芦1 ，芦2 ，& 一1 很明显，当k = l 和k = n 时，( k ) j a c i b i 反问题就是经典的 j a c o b i 矩阵反问题，并且有很多算法构造乃，。 3 】f 6 】【9 】，而且在文 献 2 】中给出了算法的稳定性分析当k = 2 ，3 礼一1 ，在文献 1 】中给出了一种新的算法构造丑。 本文就是要进行该新算法的稳定性分析。最后得出结论： 该( k ) j a c o b i 反问题的算法是l i p s c h i t z 连续的。 关键字： j a c o b i 矩阵，( k ) 反问题，稳定性，特征值。 a b s t r a c t i fw ed o n ，tk n o wt h ej a c o b im a t r i x 正m ，b u tw e k n o wa l le i g e n v a l u e so fm a t r i xt 1 1 1 ，a l le i g e n v a l u e so fm a t r i xt k + l ，n ，a n da l le i g e n v a l u e so fm a t r i xt 1 m ，c o u l dw ec o n s t r u c tt h em a t r i x 乃，n l e 七 s 1 = = ( 芦1 ，p 2 ，p k 1 ) ， s 2 = ( 弘七，p 七+ 1 ，n 一1 ) ， a = ( a 1 ，a 2 ，a n ) a , r et h ee i g e n v a l u e so fm a t r i c e s 乃，一1 ，t k + l ，na n d 丑，nr e s p e c t i v e l y t h e p r o b l e m i st h a tf r o ma b o v e2 n - 1d a t at of i n do t h e r2 n - 1d a t a ： a 1 ，a 2 ，d n ，a n d 卢1 ，岛，风一1 o b v i o u s l y , w h e nk = l o rk = nt h i sp r o b l e mh a sb e e ns o l v e da n dt h e r e a r e m a n ya l g o r i t h m s t o c o n s t r u c t 乃，”【3 】 6 儿9 】，a n di t ss t a b i l i t ya n a l y s i s c a nb ef o u n d e di nf 2 1 w r h i l e 南= 2 ，3 佗一1 ，an e wa l g o r i t h mh a s b e e n p u tf o r w a r dt oc o n s t r u c t 乃， 【1 】i nt h i sp a p e r w ew i l lg i v es o m e s t a b i l i t yq u a l i t i e so ft h en e wa l g o r i t h m i nc a s ek = 2 3 n 一1 i nt h i sp a p e rw ew i l la n a l y z et h ep e r t u r b a t i o nq u a l i t yf o ran e w a l g o r i t h mo ft h e ( k 1j a c o b im a t r i xi n v e r s ee i g e n v a l u ep r o b l e m a n d f i n a l l yt a k et h ec o n c l u s i o nt h a tt h ea l g o r i t h m o ft h e ( k ) j a c o b ii n v e r s e p r o b l e m i sl i p s c h i t zc o n t i n u o u s k e y w o r d s ：j a c o b i m a t r i x ，( k ) i n v e r s ep r o b l e m ，s t a b i l a t y , e i g e n - v a l u e 上 海大学 本论文经答辩委员会全体委员审查，确认符合上海大学硕 士学位论文质量要求。 答辩委员会签名： 主 任： 叼坼氏l 止f 引子也，二学) 委员： 导师： 答辩日期： 砸住蔫 且钔 j 嚣挈凇 2 一。午白多臼 c 上场大孑) ( 上蹲方孕) j10 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 日期：2 。牛，j ，fj 2 0 0 4 上海大学硕士学位论文 l 引言 矩阵特征值反问题( 亦称逆特征值问题) 涉及的领域有数学物理、地球物理、量 子化学、光学、力学、结构设计、模式识别、自动控制等例如著名的s t u r r a - l i o u v i l l e 逆问题，弹簧一质量系统的参数识别，极点配置等。 1 1特征值反问题的物理背景 考虑一个两端固定的弦的振动问题，它的数学模型可以化成下列边值问题： j 钍”( z ) 一仃( 。) u ( g ) = a u ( x )、 1u ( o ) = 牡( 1 ) = o l j o ( x ) 是跟弦的密度有关的函数，如果弦是均匀的，那么o ( x ) = g o = c o n s t 。当a 取固有值时，( 1 1 ) 有非零解让( z ) ，这是固有值对应弦的固有频率。 已知盯( z ) ，求固有值a 的问题，称为固有值问题或特征值问题反过来，如 果通过试验手段测得弦的固有频率，计算得到固有值，从已知固有值来求盯( 霉) 的 问题，就称为特征值反问题。 用差分方法解边值问题( 1 1 ) ，就把微分方程的特征值问题，化为矩阵的特 征值问题，因此也把微分方程的特征值反问题化成了矩阵的特征值反问题。例如 ( z ) 用中心差分尘啦上= 型坐剑代替，这里h = i 1 ，= 访，那么对应的矩 阵是一个对称三角阵因此弦振动问题的特征值反问题，就化成了一个对称三对 角矩阵的特征值反问题。 边值问题( 1 1 ) 是弦振动问题的数学模型，也可看作一个粒子的一维薛定谔 方程，这时珏( 。) 表示粒子的波函数，盯( 。) 代表势函数，固有值a 代表在这个场 中运动的粒子所具有的能级。如果已知各个允许的能级，求势函数o ( x ) 的问题也 是对称三对角矩阵的特征值反问题。 上面介绍的简单的物理问题对应对称三对角短阵的特征值反问题。可以设想， 更复杂一些物理问题，会对应更复杂的矩阵的特征值反问题，被大家所重视。 1 2 经典的特征值反问题提法 1 9 6 7 年h a r r y h o c h s t a d t 在f 10 提出两种类型的反问题 问题一给定两个序列a 1 ，a 2 ，a 。和弘l ，弘2 ，p 。一l ，并且满足九 0 i = 1 ，2 圆 也即是乃。是关于第二条主对角线( 从右上到左下) 也是对称的 1 9 7 9 年g h g o l u b 又提出了下面类型的反问题： 问h - - - - 如果噩。的特征值a l ，k ，a 。给定，矩阵矗，。的特征值肛l ，肛2 ，一。 也给定，构造丑，其中矩阵聂。定义为： ，丑，。 o 1 风一 io风一。a 。 h o c h s t a d t 证明问题一和问题二都至多有一个解。1 9 7 6 年o h h a l d 证明问 题一和同题二都至少有一个解，并且给出了求解的方法f 3 ，但是算法不稳定。 1 9 7 8 年c d eb o o r 和g _ h g o l u b 给出了问题一和问题二的解【1 1 1 3( k ) j a c o b i 矩阵特征值反问题提法 五n = 0 岛一1 恳 反毗尾 m 风 0 ，一 2 0 0 4 上海大学硕士学位论文 3 是一个nx 竹不可约的对称三对角矩阵，定义它的子矩阵耳肿 0 故慨( a o ) 与一2 ( o ) 反号。 序列妒。( a ) ，一l ( a ) 妒l ( a ) ，妒o ( a ) 具有上述三个性质，因此为任何区间a ，功 内的s t m m 序列。 定理2 2 【6 ，1 6 j a c o b i 矩阵的特征多项式序列 妒。( a ) ，i 一l ( a ) 妒l ( a ) ，印( a ) 中任意一个多项式仇q ) 有七个实单根z p ，z 竽) z 于，并且它们与q z l - t ) 的 k 1 个实单根。字- 1 ) ，z 一茹兰1 有如下隔离性质； z z p 一1 z 梦 谬一1 ) x ( k - 1 毋 ( 2 3 ) 证明：现在来分析序列( 2 2 ) ( a ) ，一i ( a ) 妒- ( a ) ，妒o ( a ) 的零点分布。 1 妒o ( a ) = 1 ，说明 f o o ( a ) 在整个实数轴( 一o 。，c o ) 上都保持正号 2 4 0 l ( a ) = a b l 有一个零点，即。i 1 = b t , 5 l o l ( a ) 在a b 1 时为正。 2 0 0 4 上海大学硬士学位论文 6 3 妒2 ( ) 、) = ( 一6 2 ) 妒l ( 入) 一n t c ，( a ) 是一个二次多项式，首项系数为正，因 此在a 叶士o 。时，妒。( a ) 为正，但在a = 二1 1 处妒。( z i l ) = - - a l c i 为负，这说明 妒2 ( a ) 有两个零点。( 2 ) 、z ，并且 卫( 2 g i l ) 霉乎 4 一般地，可以用数学归纳法证明如下性质：一l 弘) 有k 一1 个实单根 z - i ) ，z 一”，z 蛀”，( a ) 有个实单根z p ，茁乎，z 乎并成立下列关系 。于 茹 叫 霉乎 z 乎一1 ) 。盟 x ( 七- i 。譬 假如这一性质对k 成立，可以证明这一性质对+ 1 也成立。 对于任意小的正数，考察一。( a ) 在( 硝“一岛。+ g ) 中的符号。 当k 是奇数时，k 一1 是偶数，锹一l ( a ) 在( 一。，。i 七“) 中是正的，鼢一l ( a ) 在 ( z ；七。) ，z - 1 ) 中是负的，可知妒k 一。( 入) 在( z 5 譬，z 乎- 1 ) 中的符号同( 一1 ) ，因为 ( 。一s ，z + ) c ( 譬1 1 ，g p _ 1 ) ，因此当k 是奇数时一- ( a ) 在( 。：m 一，。+ ) 的符号同( 一1 ) 卜1 当女是偶数时，一1 是奇数，妒一l ( a ) 在( 一o 。，z p 。) 中的符号为负，在 0 p - 1 ) ，g _ 1 ) 中的符号为正，在( 生，z k - 1 ) ) 中的符号同( 一1 ) ，因此当南是 偶数时一z ( a ) 在( 。一s ，茁+ e ) 的符号同( - i ) 因为讯+ 1 ( z ) 的符号与妒k 一( z ) 的相反，因此当k 是奇数时，p 蚪t ( z ) 的符号同( 一1 ) ，这样+ 。( a ) 在( z 5 m ，逋譬) 中至少有一个根，于是在扛p ) ，罐) 中至少有七一1 个根，因为七是奇数，侬+ i ( x i k ) 是负的，饥+ ，( 卫) 也是负的， 而讯+ ，( a ) 是偶数次多项式，在a - - - y 士o o 处都是正的，因此在( 一。，z ) 中至 少有一个根，在( o ，o 。) 中也至少有一个根，+ l ( a ) 至多有k + 1 个根，于是 知道在( 越m ，z 嚣) 中有且只有一个根，记为z ：譬”，同样在( 一0 ( 3 ，。p ) 中有且只 有一个根记为z r “) ，在 ，o o ) 中也有且仅有一个根记为；t k 任+ “l ，。这就证明了 当 是奇数时所述的性质对k + 1 也成立。 同法可得，当k 是偶数时所述的性质对k + 1 也成立。 1 9 9 9 年，蒋尔雄教授在【8 】中将定理2 2 推广到了更般的情况。 定理2 3 8 设死是礼不可约对称三对角矩阵，它的特征值为：a l a 。 2 0 0 4 上海大学硕士学位论文 7 a 。，将乃化去第女行和第k 列后的矩阵为 w = ( ) 它的特征值为p l 一1 。 如果五扣- 和t k + l | 。没有共同的特征值，则有关系 a l p l a 2 ，上2 a 。一l 肛n 一1 a n ( 2 4 ) 如果t 1 扣l 和t k + 1 ，n 有共同的特征值雎= 胁+ l ，则上述关系( 2 4 ) 中 i a l 0 ，f ( p k - f ) 0 ，( 一) o a i 卢l a 2 p 2 p n l 0 ，f ( z j + e ) 0 充分小时， ，( 脚一) 0 ，( 脚+ ) 0 这样就证明了 a l l a 2 比 脚= a p + l = 坳+ l + 2 脚+ 2 芦n l 0 ，t 不可约，7 的特征值都不相同，因此氟与毛至多相差一个符 号，即 i s i = 毛8 i ，矗= 士l ， 由此可知 8 h i 2 毛s “， 利用( 2 1 3 ) 式， 8 1 i 8 。i ( 吼) = 历岛良一l ， 或者 s 锌皆， 又 x i ( o f ) = ( o f 一0 1 ) ( o f 一巩一1 ) ( 巩一o f + 1 ) ( o f 一以) ， s i g n x ( 馥) = ( 一1 ) “一，芦l 岛岛一l 0 ， 故e i = ( - 1 ) ”，从而得到 j卢- 岛风一l ii - i“ 、j 里( 巩一钔：星。( 0 1 一 再由l a n c z o s 过程( 2 7 ) 就可以得到t 。 问题三由( 2 1 ) 式知，对于五。有 同理对于磊。有 ( a o f ) = ( a 一) x l ，。( a ) 一藤硝。，。( a )( 2 1 6 ) l = 1 g ( a 刊娟喝) x t , - 1 一髓孙。 ( 2 l7 ) “n 嘛一) x - 一- ( a ) = n 一- i i ( a 一以) i = 1 i = 1 2 0 0 4 上海大学硕士学位论文 1 9 即 由( 2 1 5 ) 式 以及 可得 兀( 如一胁) x l , n - 1 ( 乃) 2 百 兀( 如一胁) s 弘( o d 2 x l , n - i ( o ) 2 嚣 a 。一a 。= ( 巩一胁) 再由l a n c z o s 过程( 2 7 ) 就可以得到t 。 3 ( k ) j a c o b i 矩阵特征值反问题算法 3 1 存在唯一性定理 定理3 1 1 如果两列有序数字肛l ，p 2 ，胀一1 和m ，m + l ，一l 中的元素没 有重复，那么( k ) j a c o b i 问题存在唯一解的充分必要条件是； a l 心， a 2 心。一。 a 。， ( 3 1 ) 其中p 2 ( 坳- ，如心。一。) ，胁，“= l ，2 扎一1 ) 定义为纵，0 = 1 ，2 几一1 ) 使得满足； 如- 畅 o ，j = 1 ，2 ，n 一1 n ( 心一胁) s t e p3 ：计算凤一i 和凤 仇一 s t e p4 ：计算毯2 1 ，；，i = l ，2 ，蠢一1 和s 。( 2 ) i = 惫，+ 1 ，一，n 一1 & 兰。j = 再凤_ l ，j = 1 ，2 ，南一1 ( 3 4 ) ( 3 5 ) ( 3 6 ) ( 3 7 ) s ，= 瓜反，i = ，七+ 1 ，n 一1( 3 8 ) 其中磷翌l j 是t l 卢对应于心的单位特征向量最后的元素。而s 嚣是最+ 1 j 。 对应于胁的单位特征向量第一个元素。 s t e p5 ：通过l a n c z o s 过程或者g i v e n s 正交过程 3 】 6 7 】，由毹1 1 - f ，i = l ，2 和弘1 ，p 2 ，m l 的信息计算乃扣l 。 通过l m a c z o s 过程或者g i v e n s 正交过程1 3 1 1 6 1 1 7 ，由s 器，i = ，k + i ， 和，d k + i ，a n - 1 的信息计算正+ l 。 和 k 1 礼一1 4 ( k ) j a e o b i 矩阵特征值反问题算法的稳定性分析 对于两组数据 a = ( a i ，a 2 砖) t ，s 1 = ( p l ，抛绺一1 ) t ，s 2 = ( 鲰，溉斗l 一1 ) t 五= ( 天，工。五。) t ，负= ( 豇。，屈觑一。) t ，庇= ，风+ 1 一。) r( 4 2 ) 辱巨刈 2 0 0 4 上海大学硕士学位论文 2 l 如果它们都满足隔离性质( 3 1 ) 和 a l j 1 a 2 姐 助。一l a n 天1 乃。 天2 乃。 - 西。一， k 则通过算法3 2 ，我们可以从信息( 4 1 ) 得到矩阵t a ，。，通过信息( 4 2 ) 得到矩 阵磊，现在我们要分析l l 五，。一磊。怯的界。 引理4 1 定义函数再( t ) 则它的导数是 证明 形( f ) = n 1 7 ( a i + b i t ) 元( t ) = 案 ，j = 1 ，2 礼一1 兀( 岛+ d i t ) 任1 ，j 刀( t ) = 石( t ) ( f = 1 ( 兀( 吼+ k t ) ) 。 k = l n 一1 n ( c k + d k t ) k = l ，j 志一；萎，熹， 如+ 咏 f 象，c f + d + ( ( 钆+ 6 棚) ( k = l n 魄n ( a k + b k t ) = 里_ 扛1 ( a i + b i t ) n ( c k + 融喜去一萎 现在定义函数办( f ) 为 f j ( t ) = n ( c 女+ d k t ) k = l ，匀 。一ld i 兀( a k + b k t ) 一r ! 曼 d k t ) 一1 ，刊( q + d i t ) i - i ( c k + d k t ) k = l ，j 上、 ic i + d i t 7 h 阻j 一九+ t ( 乃一心+ 九一元) 2 = 1 n 一1 n 阻，一胁+ ( 玛一心+ 胁一胁) 2 = l ， t 0 ，1 ( 4 3 ) 2 0 0 4 上海大学硕士学位论文2 2 由引理4 1 我们得到 驰，叫吼喜万等卷 n 一1 一。至；萨寿若等等丽) ( 4 a ) i 耋刍脚一地+ t ( 岛一脚+ 胁一忍) 7 。4 由中值定理可以得到 记 f j ( 1 ) 一f j ( o ) l = 刀t 、t ) j ，f ( 0 ，1 )( 4 5 ) 5 嚣躏i 方， 妒；面再隶再丽， 驴。毛画萨南萨丽， ( 4 6 ) ( 4 7 ) ( 4 8 ) ( 4 9 ) 。0 0 4 圭塑奎堂堡主兰垡笙茎兰! 一一 则由( 4 , 4 ) 可得： 可i f ：；( t ) i s i 喜万等等i马 “鲁脚一九+ t ( 西一如+ 凡一凡) 引；= l , ；t j 而 t j - - 瑞斋) 1 喜瑞喾揣 + ；羲n - 1 瑞篙褊 山i i j - # j + a i 一九l 帕罨i 西一脚讹一训 a 3 ( 旧一心i + m 一 + 岛( 旧一心i + 一圳 如【2 ( n 一1 ) f 西一蜥1 + i ip 一豇1 l l + 1 1 ) 、一天i h ( 2 礼一1 ) 如( 1 lp 一豇 i l + 1 la 一天 1 1 ) ( 4 , 1 0 ) 定理4 2 若即，风_ l ，凤，壶j ，风一l 和晟各自是由信息( 4 1 ) 和信息( 4 2 ) 通过 ( 3 4 ) ，( 3 5 ) 和( 3 6 ) 计算出来的值，那么我们可以得到以下估计： l 、丐一、酉i 如( i l 弘一乒l l l + i la 一天1 1 1 ) ( 4 1 1 ) l 卢k 一。一孱一。i p ，( 1 lp 一豇l i ，+ i ia 一天1 1 1 ) ( 4 1 2 ) 卢k 一声ki p 2 ( i lp 一口n + i 一天i i i ) ( 4 - 1 3 ) 舯啪用旌妫。曲：鬻 ( 2 犯一1 ) 曩吼 m 2 1 i 百 “一1 ( 2 n 一1 ) e 羁晚 砌2 面矿 ( 4 1 4 ) ( 4 1 5 ) ( 4 1 6 ) 2 0 0 4 上海大学硕士学位论文 2 4 证明： 另外可得 婀一届l = 拇磊 ：i 垂( ! l 盘型! 再+ 再 9 ( 沥2 n - + 1 ) 再f j o j l 。i t 卢一肌+ 卜 肛l 靠。| = i 、j 擎一u i = 1 1 k - 1 规 l 七一i iq 一西i s 芾 亍1肛_肛一 驴+ 儋磊 o ( i = 七，k + l n 1 ) ，f i 口l | j 2 ：1 ，j | 9 2f | 2 ： 1 。定义a i 2 d i a g ( # 1 ，2 肌一1 ) ，a 2 = d i a 9 ( # ，肛女+ l 脚) 。则 k 1 = 坩q l ，a p q l j 口l 】r ( k 1 ) ( f 4 2 1 1 辱一 m 一 2 0 0 4 上海大学硕士学位论文 = q 2 ，a 2 q 2 ，a ? 一m 口2 】兄( “一) “( “一( 4 2 2 ) 都是非奇异矩阵，且有 | | k i - 11 1 2 l l i 写1 n 。 其中d l 和啦定义为： - 2 佩m a x ，i j 诗等m i n l _ i _ k - 1 i i k 一1 锚t ( 4 2 3 ) ，i j la f a lj 一”b 、1 驴丽唧辫；列诗蝌r a i n 。s k i n 器 ( 4 2 4 ) 七s i s n 一1 ，f ，ia 一a if l 王，、， 引理4 6 f 4 3 令a = q 冗是阶数为r a n k i a ) = n 的矩阵aer n n 的0 r 分解。如果 e r “满足： | | a 。f | 2 | | ei i s 1( 4 2 5 ) 那么存在一个唯一的q 月分解： a + e = ( q + 彬) ( 冗+ f )f 4 。2 6 ) 且满足t r l w jr f s 黯躲f ( 4 2 7 ) 同样的方法，我们可以推广得到结果t a = q 三是阶数为r a n k ( a ) ：n 的矩阵 a e 尼“的q l 分解，如果e 昂- n 满足： 那么存在一个唯一的q l 分解 a 1 ej 1 2 1 a + e = ( q + ) ( l + f ) 且满足： jj w f l f s 黯斜觥f ( 4 ，2 8 ) ( 4 2 9 ) ( 4 3 0 ) 定理4 7 如果丑， 一z 和磊扣1 分别是由信息( 4 1 ) 和信息( 4 2 ) 构造出的矩阵，且 o l 矗 l ，那么有： n ， 一，一丑，t z l | z l ( j i 卢一口j | ，+ ia 一天i 1 1 ) f 4 3 1 ) 2 0 0 4 上海大学硕士学位论文 2 7 其中0 f t 由( 4 2 3 ) 定义，( t 、f - 和6 - 定义为 证明：首先有 令 则 于是可得 因为 易得 t = ( j 可醴一2 日。+ 蹬一3 ) ( ! f 弘一豇jj l + ja 一五ij 1 ) 七一2 f i _ 1 + 2 ( 碍q l + i ) i i s 11 6 - = m a x i i s ll 。，| i 由l l 。，1 ) 噩卜l = q - a 。甜，磊扣l = 国l 天。钎 q e 自一l = q l ，国 魂一l = 蠡 w j = q l 一0 l ，q 1 = a 1 一天l 丑， 一- 一矗，一，= q - a l q t 一国l 天l 百 = q - a ，w ，+ ( q t a - 一国。天。) 钎 = q 1 a 1 w + ( q 1 a z 一亩1 a 1 + 国l a l 一亩。五。) 钾 ( 4 。3 2 ) ( 4 3 3 ) ( 4 3 4 ) ( 4 3 5 ) ( 4 3 6 ) = q 1 a 1 w 7 + 啊a l 国 + 国，q 。国( 4 3 7 ) 五， 一l 一丑，七一lf f ，f in l | i f + 2i f a l | | f f ii 竹| i f( 4 3 8 ) k 1 = 【a ! 一2 吼，a 一3 口l ，g l 】咒忙一1 ) 忙一l ) q 1 k l = l l ， t k - 2e ，互k ，- 3e ，一l 】= 工l ( 4 3 9 ) 其中l l 是主对角元都是正数下三角矩阵 6 。 是k l 的q l 分解。 甄= 研三1 等 + | | 0 一， 2 2 0 0 4 上海大学硕士学位论文2 8 记 同法，我们可以得到霞。的q l 分解 我们有 e l = k l k l ( 4 4 0 ) 1 1 日= | | k i 一膏。ij 。 = | | a ：一2 q l 一天i 一2 蟊，a 一3 q l 一天 一3 甄，q 。一丑】j j 。 。 i n l 。a 女x 一。| | a i 口t 一五i 蠡| | ， 。嚣豸芑。( i a i f t l lg - 一丞i i t + i l a j 一天it t l ) d ：一2f | q l 一盈| | l + d ：一3 ia 。一天l ( 、画刁f 一2 叩1 + 6 一3 ) ( | j 卢一西i l l + | | a 一天1 1 1 ) 2 af 4 4 1 另一方面 耳l + ( 一毁) = ( q 子+ ( 一吼) ，) ( l + 曩) 由引理4 , 5 和引理4 6 可得：若 j l 奸1 f 蜀j f 2 o 。( 1 1 则 1 1 w - f j f 蹄勰i f s 譬1 警1 ， ( 4 a 。) 一a ( 】” 、“ 2 0 0 4 上海大学硕士学位论文 因此由引理4 3 可得 e l 怙= i ik i 一盔陆 = i i a 一2 9 - 五：一2 口- ，a ：一3 9 。j i ：一3 口l ，g 。一口1 j j f k 一2 i ia i g z 一天i 磊j 。 i = 0 1 1 2 1 1 玑一训。+ i ia i 一五m i = 0 = o k - 2k - 2 醴一盈i i ：+ i 一天，1 1 。 - 2 ( 叼t + i 1 ) 川p 一豇t l 。+ f fa 一五i i i )( 4 4 a ) i = 0 将( 4 4 2 ) 式和( 4 4 3 ) 式代入( 4 3 8 ) 式可得下列不等式 i i 丑，一一矗，k zi l f l | q 。8 f + 2 | | a 。i i f | | 研i l f 邹+ 2 驴k - 2 州矿t ) i i 5 1 i i 。譬警】 1 + 2 ( 讯+ i 6 2 半兰挚】 忙0、i - ( j | p 一豇i i + i i 五| i ，) = f l ( j jp 一豇1 1 1 + i ja 一天1 1 1 ) f 4 4 4 ) 由此我们证明了定理4 7 。 定理4 8 如果t k ，n 一- 和磊，1 分别是由信息( 4 1 ) 和信息( 4 2 ) 构造出的矩阵，且 a 2 已 1 那么有： 瓦一一一靠，n 一11 1 f 2 ( | | 肛一声1 1 1 + l ia 一五1 1 1 ) ( 4 4 5 ) 其中。由( 4 2 4 ) 式定义。岛、f 2 和如定义为 岛= ( 、穗6 一一1 啦+ 凹一一2 ) ( j j 卢一西1 1 1 + i ia 一玉f f 。) ( 4 4 6 ) n - - 一】 一 拈l + 2 善( “矿鼬譬等 ( 4 4 7 ) l = u z 、y 如2 m a x l ls 2i i 。，i i 虎| | 。，1 ) f 4 4 s ) 2 0 0 4 上海大学硕士学位论文 3 0 证明：定理4 8 的证明完全类似与定理4 7 。唯一不同的是( 4 3 9 ) 式换成为 0 2 恐= f e l ，疋p 1 e l t 一2 - 一k - ，1 e l 】= 尼 其中尼是一个主对角元都是正数的上三角矩阵f s 】 施= 霹而 是k 2 的q r 分解。 定理4 9 如果t 1 ，。和磊，。分剐是由信息( 4 1 ) 和信息( 4 2 ) 构造出的矩阵，且 m a x m t 6 ，锄岛) 1 则： f l 乃，n 一丑，nf | f 三( f i 一豇f f t + f l 一天f f l ) ( 4 4 9 ) 其中三定义为： 三= 1 + p l + 励+ z l + 如 ( 4 5 0 ) p l ，p 2 ，f l ，f 2 分别由( 4 1 5 ) ( 4 1 6 ) ( 4 3 3 ) ( 4 4 7 ) 式定义。 证明：由定理( 4 2 ) ( 4 7 ) 和( 4 8 ) 可得t l 乃，n 一正，n 怯| j 霸，女一l 一壶加，恬+ 9 噩，1 一磊，。一。怙 + i 风一t 一厦一。i + i 凤一良i + 1a k 一瓢i ( 1 + p l + p 2 + 1 1 + ；2 ) ( 1 l 卢一豇| | 1 + 1 1a 一天1 1 1 ) 定理4 1 0 算法3 2l i p s c h i t z 连续。 证明：由c a u c h y s c h w a r z 不等式 8 nn 蚴( 。；) 5 ( ? ) i = l f = l i = l 由定理4 9 立刻得到； f f 正m 一磊。7 f f s 、至i 孔( f f 扛f 拷+ f fa 一五f 曙) ； 证明完毕 2 0 0 4 上海大学硕士学位论文 3 1 5 数值实例 现在我们将通过算法3 2 来构造一个矩阵，并由此观察算法的稳定性。 令 n 9 = 其中丑9 的特征值为 a = l10 00 0 000 1 2100 00 00 0l310 000 0 0 01410 00 0 000 1 5 l0 0 0 00o 01 610 0 00 0 0 0 l710 o o0 o 0 o181 oo ooooo19 o 2 5 3 8 0 5 8 1 7 1 0 0 3 1 l _ 7 8 9 3 2 1 3 5 4 7 3 4 9 5 2 9 6 1 0 5 9 0 7 0 8 0 1 0 6 3 9 9 6 0 5 6 1 2 5 9 2 8 6 1 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 3 9 4 3 8 7 4 0 7 1 3 9 7 0 3 8 9 4 0 9 2 9 1 9