（计算数学专业论文）若干最小二乘问题的舍入误差研究.pdf

若干最j 、- - 乘问题的舍人误差研究 摘要 最j l , - - 乘问题不仅是许多数学分支的基本工具，而目在经济学、统计学、测量 学、最优化、信息处理、自动控制、工程技术和运筹学等应用学科中都有着广泛的 应用最小二乘问题的广泛应用，引起了数值代数领域诸多学者对最小二乘问题数 值稳定性的高度重视 本文，我们主要研究与最小二乘问题相关的数值算法和舍入误差估计具体有 如下五类问题； 1 l u 和c h o l e s k y 分解的向前畲入误差估计 l u 分解( 高斯消去法) 作为解可逆线性系统的重要工具，其舍入误差估汁一直 为人们所关注事实上，长方矩阵的高斯消去过程在解约束最小二乘问题，确定矩 阵数值秩的l u 分解等问题中也扮演着及其重要的角色现有文献在表达l u 分解 的向前舍入误差时不够简洁我们将对【一u 和c h o l e s k y 分解的向前舍入误差进行 研究，以简洁的形式表达出l u 和c h o l c s k y 分解的向前舍入误差式该表达式表 明l u 和c h o l e s k y 向前误差只与初始矩阵的子矩阵和舍入误差累积方式有关在 此基础上，我们估计了矩阵的l u 因子，非奇异方程组的解的误差界 2 改进的g r a m s c h m i d t ( m g s ) 解最小二乘问题的误差估计 作为解最小二乘问题m j l l a x 一州。三种常用的正交化算法之一改进的g r a m s c h m i d t ( m g s ) 有其独特的数值性质选主列m o s ( p m g s ) 的向后误差分析文献 中已有人研究，但多数误差估计郝是范数型估计我们给出的p m g s 的向后误差估 计是元素型误差估计另外我们还研究了p m g s 的向前舍入误差该结果表明如 果a 良态，则p m g s 不仅保证得蛰j 的上梯形r 因子误差比较小，而且通过选择 合适的误差限我们还可确定a 的数值秩，在此基础上，我们进一步研究了p m g s 解最小二乘问题时的向前向后舍入误差 3 类p m g s 解约束最i j 、 - 乘问题的误差估计 约束最小二乘问题 馔粤i i c z h l l 。，s = ： l b 一4 | | z 。m 。 i n l 口z 一“i l z 的极小范数解x l s e 和加权最小二乘问题( w l s ) ：婴辩苫 z 一 j ? 。的极限解相 等，即；旦：m ，n s ( r ) = e l s e 利用二者的等价性，在 ? 】的p m g s 取极限，我 得到类p m g s 钟法，井将约束最小二乘州题的解疆式地表示出求尽符泼算法 币b j 6 r c k 的直接消去法等价，但利用该算法的推导方式可导出约求最小二乘问题 华东师范大学博士论文若干最小二乘问题的舍人误差研究 的向后误差分析利用l u 和p m g s 的误差分析结果，我们还给出i r 类i m g s 和 约束最小二乘问题的向前舍入误差估计 4 刚性加权最i 、- - 乘问趣的数值稳定算法及畲人误差估计 在解线性约束最优化问题、电子网络、椭圆型的边界问题等问题时，人们常常 需要解一个刚性加权最小二乘问题，即m 坐r ( ，1 一 ) 1 1 2 其中”= d i a g ( w 。) 1 的对角因子相差很大大量的数值例子表明，经典的p m g s 解刚性最小二乘问题 时，其数值稳定性随着权矩阵的刚性程度的增强而变得越来越差根据魏木生教授 提出的刚性最小二乘问题数值稳定的充要条件，我们首次给出刚性最j , - 乘问题的 数值稳定的r b p m g s 算法，并对该算法进行舍入误差估计 5 各类矩阵分解的增值因子的上界 l u 分解、p m g s 及类p m g s 算法的舍入误差估计结果表明，矩阵分解的增 长因子对矩阵分解的数值稳定性起着及其重要的作用因此我们还探讨r 上述几类 矩阵分解的增长因子的上界 文献中给出的部分选主元的l u 分解的增长因子的 二界随着矩阵的维数璺指数 增长，因此对于给定的矩阵特别是实际增长因子不太大时，指数型上界昆然不能 作为增长因子的合理逼近同样对于p m g s ，指数型增长因子也需要进一步改进 我们经过研究，发现l u 分解和m g s 的增长因子的上界与原始矩阵的子矩阵 有关，并且受限于原始矩阵某种类型的条件数我们还继续探讨了类m g s 、m g s 锯加权最小二乘问题时，对应的增值因子的上界 关键词l u 分解，最小二乘，改进的g l 。a , l n s c h n f i d t ( m g s ) ，舍入误差，数值 稳定，增长因子。 r o u n d o f fe r r o ra n a l y s i so f s o m el e a s ts q u a r e sp r o b l e m s a b s t r a c t l e a s ts q n a r e s ( l s ) p r 0 1 ) l e m sa r eo n eo ft h ei n o s l ，i m p e lt a u ta n dw i d e l yu s e d t o o l si nn l a n yf i e l d s ，s u c ha 8e c o n o m i c s ，s t a t i s t i c s ，o p t i m i z a t i o n s e n g i n e e r i n g ，m l t o m a t i o n ，e t c ，w h i c hh a v ea t t r a c t e dm a n ) , n u l u e r i e a la l g e b r aa n a l y s t st oa t t a c hd e e p i m p o r t a n c et ot i l en u m e r i c a ls t a b i l i t i e so fl e g i s ts q u a r e sp r o b l e m s i nt h i sd i s s e r t a t i o n w em a i n l y s t u d yn u m e r i c a lp r o p e r t i e s a l g o r i t h m sa n d r o u n d o f fe r r o re s t i m a t e sr e l a t e dt ol e a s ts q u a r p r o b l e m s ，a sm e n t i o n e di nt h ef o l l o w i n g s e c t i o n s ： 1 f o r w a r dr o u n d o f fe r r o re s t i m a t e so fl ua n dc h o l e s k yf a c t o r i z a t i o n s i u a c t o r i z a t i o n ( g a u s s i a l le l i n f i n a t i o n li sal u n d a ! i m n t a lt o o lf o rs o l v i n gi n v e r t i b l el i n e a rs y s t e mi nf a c t ，t h el uo far e c t a n g u l a rm a t r i xa l s op l a y sa ni m p o r t a l i t r o l ei ns o l v i n gt l l ee q u a l i t yc o n s t r a i n e dl e a s ts q u a r e sp r o b l e m ，a n dr a a kr e v e a l i n g l u ( r r l lj ) f a c t o r i z a t i o n ，e t c b a c k w a r dr o l l n d ( d t ( t ( ) re s t , i u l a t e so fl uf a c t o r i z a - t i o aa r ew i d e l ys t t t d i e di nl i t e r a t u r e h o w e v e r ，f o r w a r dr o u n d o f fe r r o re s t i m a t e so f i 。ue x p l e s s e di nl i t e r a t u r ea r en o tc o n c i s ee n o u g h 、v ew i l ls t u d yf o r w a r dr o u n d o f f e r r o r so fl ua n d c h o l e s k yt k c t o li z a t i o n s ，a n dc o n c i s e l ye x p r e s st h ef o r w a r dr o n n d o f f e r r o r s ，w h i c ha r eo n l yr e l a t e dt ot h es u b m a t r i c e so fo r i g i n a lm a t r i xa n dt i l em o d e lo f r o u n d o f fe r r o ra ( 1 c u u m l a t i o nf u r t h e r m o r e w ea l s og i v er o u n d o f fe s t i m a t e sf o ri , u f a c t o ra n dtt t es o l u t i o no fa ni n v e r t i b l es y s t e m 2 r o u n d o f fe r r o re s t i m a t e so ft h em o d i f i e dg r a m s c h m i d t f m g s l a l g o r i t h mi b rs o l v i n gs t a n d a r dl sp r o b l e m t i t ( ! t l o u s e h o h l e r ( 2 r g i v e n sq ra n dm o d i f i e d ( h a l i t s c l n n i d la l g o li t h l n “1 e f r ! q u e n t l yt l s o d “1f o r 州。i “gs t a n d a r dl e a s t8 q 、1 8 “p r 0 1 ) l ( l s ) = 。r a 锄i ni i m b 1 1 2 m g sh a si t sp a t t i e u l a ri l l n n e i i c a lp l o p e r t i e sb a c k w a r dr o u n d o i f e i - r o te s t i m a t e s t ) f m g sh a v es t u d i e di nl i t e r r t o leb u t ，i n o s t ( ft h ee s t i m a t e sa l en o t1 1 1 一w i s ew ed e 1 1 、r et i l ec o m p o n e l l t w i s eb a c k w a r de r l o re s t i m a t e so ft h em g sw i t he o h l n l np i v o t i n g f p m g s ) t a l s of i l s t l ys t u d yf o r w a r dr o u n d o f fe r r o le s t i t l l a r e so fi v l g sa n dr e v e a l i l a t ti lc o e l t i ( i e n lm a t 1 i xi sw e l l ( f m ( 1 i t i o l l ( ! d ，t h e nw h h p l o ) e t l 3 , c h o s ( 、i i l o l e r 3 n c cy ， t h ep m g sc i v i la l s oc , o r l e c t l 3 d e t e r m i n et l l en l i i l l t q j ( a lt a n ko ft h ec o e f f i t ：l e n t n i l l x 华东师范大学博士论文若干最小二乘问题的畲八误差研究 o u n d o f fe r r o le s t i m a t e so fp m g sf o r s o l v m gt h es t a n d a r dl sp r o b l e mt i r ea l s o d i s e u e s e d 3 r o u n d o f fe r r o re s t i m a t e so ft h em g s l i k ea l g o r i t h mf o r s o l v i n g t h ee q u a l i t yc o n s t r a i n e dl e a s ts q u a r e sp r o b l e m t h ee q u a l i t yc o n s t r a i n e dl e a s ts q u a r e s ( l s e ) p r o b l e n _ i m 。i s n 1 1 g j ：一f 2 ，s = ：n 8 一d n 2 2 ，l l l i l l i b j ：一“ 2 1 i 8 e q u j v a l e l l tt ot | ew e i g h t e _ l l e ts q u a r e sp 1 0 b 胁( w l s ) ；, n i ni l l t b 一吲1 1 2 w h e nt o o ，ic ，l i m ：f w l s ( t ) = x l s ew ed e r i v et h em g s l i k ei n e t h o df o rl s e p r o b l e n tb yt a k i n gl i m i t sm t h em g so f i 苫l ，a n de x p i e s s t h el s es o h t t , i o l lo f n l i n i n m n in o r n le x p l i c i t l y w ea l s od e r i v ei ) a c k w a r dr o u n d o f fe r r o re s t i m a t e so ft h e m g s 1 i k ea l g o r i t h m f u r t h e r m o r e b a s e do i lt h ee r r o re s t i m a t e so fl ua n dm ( i s a l g o l i t h m ，w ep r e s e n tf o r w m dr o u n d o f fe r r o re s t i m a t e so fm g s l i k ea l g o r i t h mf o r s o l v i n gt h el s ei r o b t e m 4 t h en u m e r i c a is t a b l ea l g o r i t h ma n dr o u n d o f fe r r o re s t i m a t e sf i l r t i ms t i f fw e i g h t e dl e a s ts q u a r e sp r o b l e m t i l e8 “f f ”。g dl e a s t8 q “0 8p r o b l c m u ( s w l s i m m i n 。1 1 w i ( z 一a r i s c s i n s e v e r a la p p l i c a t i o n8 r e a si n c i u 0v a r yw i d e l y an n m b e ro fn u m e r i c a lt e s t s s h o w e dt h a ts t a n d a r dp m g s a l g o r i t h mi sm n n e r i e a lu n s t a b l ef o rs o l v i n gs w l s ，a n d t h el l l o i es t i f fo f 7 ，t h ew o r s eo ft h ei l l l r r l e r i ( ：越s t a b i t i t vb a s e do nt h e8 1 1 f f i c i e n ta n d l l e c e s s a r yc o n d i t i o n sd e d u c e db ymw e if o rs o l v i n gs w i s 1 7 2 ，w ep r e s e n tn u m e r i c a l s t a b l ea l g o r i t h mf o rs o l v i n gt h es t i f fw e i g h t e dl e a s ts q u a r e sp r o b l e n _ 1a n de v a h m t e t h ef o r w a r da l l ( 1b g ：k w a r dr o t m d o f fe lr o ee s t i i n a t e so ft i l ea l g o r i t h m 5 o nu p p e rb o u n d so ft h eg r o w t hf a c t o r sf o rl u ，c h o l e s k y ，m g s a l g o r i t h m s r o u n d o t fe r r o le s t i l n a t e so fl u m g sa l l ( 1m g s ，l i k ea l g o l il l u n ss h o w e l lt h a t th eu p l l e lk l l t n d so ft h eg r o w t hf a c ! o r sf o rn | a t r i xf a e t o r i z a t i o n sp l a ya l li m p o ir a n t i o l ei n1 1 1 i l i c a ls t a b i l i t yo fm a t r i xf a e t o r i z a t o i o n sw et h e r e f o r es t i l l y t h e t p p e t b o u n d so f1 1 l og l i j w t hf a c t o ) sf o l i a j c h ( f l ( x s k ya 1 1 c lm g sm g s l i k ea l g o l i t h m s t i mu i l p c lk i i l i l d 5 出t h e o w t ht s e t o r st b rp a l t i a lp i 、，o t i n gl ut a ( ：t , o r i z a t i o n g r o we x p o n e t i a l l yw i t hf l l a f _ l i x d i m e n s i ( i r i sr hag i v e n l l l j l t i i x ，e s p e 0 令 a ( i 】= a ，则其咒步的c h d l c s k y 分解舳产生矩阵序列川1 = ( n 咎) ，k = l 。m 且在 c h o & ￥ 。分解的第 ( 1 n j 步，计算 t 戡 = = n ；i 1 ， 十 ，l n k 一 ，= ，j 似擅k f 饥 k “ 华东师范大学博士论文若干最小二乘问题的舍人误差研究 则n 步后，a 可分解成 其中l r “”为对角元都大于零的下三角矩阵 当a 衅。“对称半正定时，则应当选主元以保证c h o l e s k y 分解能持续r 步 c h o l e s k y 分解中典型的选主元策略，即在第k 步选取 s = m i n d ：或l 托m a 。x 。a l ：) ，1 g 因为a ( ) ( 女：n ，k ：扎) 半正定，所以上述的选元方法类似于l i j 分解中的全部选主 元策略因而a 的选主元的c h o l e s k y 分解为 i t a i i = l l t , 觯也舢舢“r ， 这里鼍换阵n 考虑了所有的列交换，且下三角阵l 1 的r 个对角元都大于零 l - 3 3q r 分解 给定矩阵a 醒“，且2n ，r a n k ( a ) = n ，则a 的q r 分解形式为 a = q r = ( q 1 q t ，r 1 = q t r t ， c ，t ， 其中q 世“为正交阵，q l 包含q 的前n 列， r 因子行瓞“”。是上三角 阵，且其上三角部分r 1 是非奇异的 若a 的秩7 n ，则q r 分解形式为 a h = q r = ( q , r0 2 其中q = ( q -q 2 ) r “。为正交阵，且q l 包含q 的前，列， r h r “7 是 非奇异的上三角矩阵，置换阵1 i r ”“使得a 的前r 列线性无关 由q r 分解，我们立即得到冗( a ) 和冗( a ) 1 标准正交基，佗( _ ) = 冗( q 1 ) ，冗( _ ) 1 = n ( q 。) 由正交投影的定义，还可得 最( ) _ q 。嘏1 ，- = q 甾 特别地，若4 列满秩，则n ( a t ) = r “，( a ) = 0 ) 5 华东师范大学博士论文若干最小二乘问题的畲人误差研究 1 3 4 计算矩阵的q r 分解 h o u s e h o l d e r 变换，改进的g r a m 一$ c h m i d t 法和g i v e n s 变换是三种常用的计算 矩阵a 的q r 分解的正交化方法 据文 2 3 l ，要得到矩阵a r ”的q r 分解结构，则需要在q r 分解的过程 中进行选主列下面我们介绍三种选主列的q r 方法 选主列的h o u s e h o l d e r 变换 在( 1 2 ) ，我们提到，对3 ：r ”，可找到h o u s e h o l d e r 矩阵p = i 一, z 荔v v j ，其中 = z 千f i x 1 2 e l 使得 p x = 土陋 尽管理论上v = 。千i i x l l 2 e t 中的正负号都可行，但在实际的浮点运算过程中， 当i x ( i ) i m 1 ) i ，i = 2 ：扎时，由于计算机字长的限制，v ( 1 ) = x ( 1 ) 一i z 将会 产生消去现象，使v ( 1 ) 失去有效位，因此我们常选取 ”= z 十s ；s n ( * ( ) ) i l z l l z e ，其中s t s n ( 。( ，) ) = ! 。，：；：；： b d l f i l 乘子瓦2 的相对误差 下面我们香如何用一系列h o u s e h o l d e r 变换将a 螂“化成上梯形阵记 a ( 1 ) = a ，计算矩阵列 a ( k + l 】= r a ( ) i f k ，a = 1 ，p 其中4 ( ) 丌kjf 铲，n 譬，“妒 ，列置换阵i i 使得 且r = ，一2 菇v k v t ，这里 v k ( i 1 = a ? 1 ( 七：删i 。2 鼍嚣蝼( 七 m ) 她 i 由于r 保持a ( ) k 前女一1 行不变，且将a 【) n 第k 列的主对角线以下的元素 消成零，因而a ( 1 ) 的前k 列必然是上三角形式的矩阵，并有如下结构： 6 件k n 三； n g s+ ，触让 0 n n 1，j l， 忙晗舱 r a。0 r 。l | | k na rr = +k a 华东师范大学博士论文若干最小二乘问题的舍人误差研究 其中r 1 融。为非奇异的上三角矩阵 弓p l a l l l n p = ( ”+ 1 因此，p 步以后，必有 = r 剥 取r i = ( 月“r ( v 。+ 1 1 ) ，q = ( b p 1 ) 7 = p l b ，n = l n p ，得 仰= 其中粘一l e 矿为上梯形 选主列的改进的g r a m s c h m i d t ( p m g s ) 对矩阵a r p “，令a ( 1 ) = a ，r = o n ，则选主列的m g s 过程将产生矩阵序 列a t “，= 1p ： a ( 丌i = ( o ，一0 ，n 于，一，口紫) ， ( 11 3 ) 这里a ( ) n t 的前( 一1 ) 列常用来存储已经得到的q l ，饥一1 以节省存储空间。 f i l 置换阵n k 满足 l l “ i i z = i i 巧4 忆 在选主列m g s 的第k 步，计算 r k k = = i | o 譬i i y ，q k = = n 譬1 ，1 k k ： ( 11 4 ) 并以蛳i l i a t ：慰l ，u 譬： n = 毋一吼，啊= 露n 灶j = 女+ 1 ：n ( j1 5 ) 显然，向量“即为n 0 在s p a , t q 1 啦，吼一1 1 空间上的正交投影因此p 步 以后，a 可分解成 a h = q l r l ，( 1 16 ) 其中i i 一1 1 1h ，q l = ( q l ，q 2 ，邯) ，r l = r ( 1 ：p ：l ：n ) 为行满秩的上梯形 阵。 注意以( ”+ 1 的后一p 列理论上应该为零，但在浮点运剪中一般不为零，本文 我们称a ( p + 1 为以经过p 步浮点运算后得到的“余阵” 选主罗u 的g i v e n s 变换 彤如矩阵0 豫一n ： l i l 0 0c o s0 00 )一s i n 0 i )( ) 0 0 一l 】 l 】 ， 0 ( j s i l l 0 0 00 c o s 0 ) l ， ， 华东师范大学博士论文若干最小二乘问题的舍人误差研究 的变换叫g i v e n s 雯换 显然，g 是正交阵，且= g f 等价于将z 在叼平面上逆时$ t 旋转角度0 。若 令 s i n0 = 一一；：兰c o s 0 = = ；：! ：= = ：， 、z ；十一；z ；托； 则g 的作用使”= g z 中的g ，= 0 利用g i v e n s 变换计算矩阵a 的q r 分解的过程类似于h o u s e h o l d e rq r 过 程要将a r 鬻”。变为上梯形矩阵，我们需要左乘一系列g i v e n s 变换而最终 的正交矩阵q 可以通过这些g i v e n s 矩阵乘积的转鬣得到 下面我们以4 3 矩阵说明g i v e n s 变换的全过程，其中非零元素我们统一以3 表示，主列上的元索统一标为黑体，设g 。，为作用在量的i ，j 行上的旋转，且使 得( q ， k a ) ，k = 0 ，a ( 1 ) = a ，_ 4 ( 。为将( 一1 ) 列上主对角线以下元素消成零后得 到的矩阵 详细的消零过程如下： z茁 茁茁 zz 霉 g 1 2 ，i “13 i 塑 zr 0z 0z 0茁 g 232 氅譬 o z oz 00 00 rf o 。e 0 ) 0 0 州_脚_a ( 3 ) 一删= ：r 由此将原矩阵化成所需要的上三角形 若4 r ? “，其中r 0 我们把口i ，口2 一，口，叫做a 的奇异值，它是唯一确定的，但正交矩阵以v 不是唯 一的 双边q r 分解 给定矩阵a r “，则 a = u l v r = u f 之1 ： v 7 ， c - 。， 叫做a 的双边q r 分解，其中u r m 舯”，v r 为正交阵， l l l r ”舯为下 三角阵 事实上，要得到a 的双边q r 分解，可先考虑a 的q r 分解： a i i = u r = u 鼍l 。其中，r ”。为正交阵，m 衅“为行满秩的上梯形阵；接着考虑疗7 的q r 分解：月7 = = 矿| 杼：l ，其中矿r 7 1 。”为正交阵，l - - 科。为非奇异的 下三角阵令v = n v ，弁并两次分解即得4 的双边q r 分解 呀0 k v u n 吁姒 第二章l u 和c h o l e s k y 分解的向前舍人误差分析 高斯消去法作为数值代数领域解可逆线性方程组的重要工具，其舍入误差一直 为众多学者所关注事实t ，长方矩阵的高斯消去法也有着广泛的应用，如，在确 定矩阵数值秩的l u 分解( r r l u ) 中( 见文f 3 2 ，4 1 ，4 6 1 ) ，在解线性约柬最：b - - 乘问 题的直接消去法中( 见文3 6 ，11 1 ) 高斯消去法的向后舍入误差，文献中已进行了广泛的研究，具体可参见i ，4 、2 0 1 等文而对向前舍入误差分析，文献中涉及的并不多本章我们将研究长方矩阵高 斯消去法的向前舍入误差分析给出误差矩阵更为简洁的表达式，并将研究所得的 结果推广至c h o l e s k y 分解 2 1 浮点运算规则 本章及下面各章中涉及的舍入误差分析，其浮点运算都遵循以下规则 n ( to py ) = ( o p ) ( 1 + 6 ) ，l j i 曼u 其中0 p 代袭+ ，一，或运算，u 为机器精度，t l ( z o py ) 表示zo py 的浮点 计算值对于精确值w ，本论文统一以f 表示”的浮点计算值 同文1 6 1 ，定义 k u ， c k | l 讯。而，仉2 丽：， 其中c 为一个比较小的正整数，具体值我们并不关心我们假定c k u 1 ，则在此 假定下，我们有3 7 。= 彳。，m = 研。= ，讹+ 加( 1 - i - 1 5 ) = 铂 如无特别说明，本文的数值结果都是通过m a t l a b 计算丽得，其机器精度u = 2 - 5 3 11 l 1 0 一“ 2 2l u 分解的向前舍人误差分析 关于长方矩阵【。u 分解的具体描述可参见1 31 ，给定矩阵a r ”，7 8 = a + a a ，其中a a 为初始数据误差，鼠l i a a i l 2 i i a l l 2 考虑a ，页的选主元( 部分 全部) 的l u 分解的浮点运算，并设在浮点运算中确定的行置换阵和列置换阵分 别为i l l ，1 1 什令a f i ) 三i i i a 1 1 r ，五( 三n ，万r i r ，a a ( i ) = r ll a a f ! 托下面我们研究 a 1 ) = l u 的向前舍入误差，其中l ，u 具有结构( j8 ) 篁奎堡堇奎堂堕圭堕塞薹至量! ! 三墨堡塾竺童垒堡叁堡塞 2 2 ，1 s 垮= a s 一o s 的一阶误差表达式及其上界 主要记号 设1 sr ，且a ( ”，l ，u 有如下划分 a t l ) ： a l ? ( 七) a 2 2 ( ) 0 三2 2 ( 南) 其中 j l ( 血) ，l 1 1 ( 七) ，u l l ( 南) r h ，令 篆) ” = l 2 1 ( k ) l l l ( k ) - 1 , - l 。- k ，k = 卜k ) “i u l “q 记s ( ) ：m ，k r t ) ；( s 黧 同文【5 9 】，记p ： 耩，q j q 一一蓦 鼠= ( 6 u + p ：嘶) 盥?q t = ( “十# 甚嚣 ( 2 2 ) 其中屯为k r o n e c k e r6 函数 引理2 1 5 9 1 考虑a 的精确的三u 运算及再1 的浮点l u 运算，则s 等+ a ：“一n 磬“的一阶误差表达式满足下j o 递归方程 s 等h = s 等+ 砖s 垮+ q k s 慷k + p ? 砖 8 k 仳k + 劈+ ” 其中k = l ：ri = k + 1 m ，j = l ：n ，s ：= 硝= n ： 塔“= n p 黝n 譬( 一， r ：。) ( 24 ) 这里e f ；，e ，e 而表示磊：+ 1 1 = 瓦字一嚣。学的浮点运算过程中除法，乘法和减法 的相对舍入误差此外， 其中 s ”1 ：k + l = n ) 。e 纠( l ，k ：n ) 璐 + f f + ( k + 1 ：，七+ 1 。) ， 、 f ( “ m 0 k ：j ? 卜f 矿 “0 l “ =rl1，j1，j ) 七七七七 ( 1 2 l 2 a a l l 。【 ，liij 华东师范大学博士论文若干最小二乘问题的畲人误差研究 因此 ，s 【+ 1 ( 七+ 1 ：m ，七+ 1 ：扎) = ( r ，气叫p 1 ) e ( ( e 。 q 扣l - q 1 ) t ，( 26 ) k 这里e ( 。) = f ( t + 1 ) l = 0 由( 2 6 ) 可看出，s t u m m e l 给出的表达式和qc 有关，而长方阵r q k q 2 q 1 中包含的信息不够明朗下面我们给出s ( ( + 1 ：m ，女a - 1 为简洁的表达式。 引理2 2 设r ，阢，件l ，k 如偿纠俾圳所定义则 证通过简单计算验证 r w 0 一，= i ，k ，q = k p e w k l d i a g ( l l l ( k ) ，l 。一k ) = w d i a g ( l l l ( ) ，k 一) d i a g ( u 1 1 ( ) ，厶一 ) k 一1 q ；= d i a g ( u l l ( ) ，k ) k ， 琏只， n ) 更 即证引理 口 定理2 1 设a ( ，h 0 ，k 如俾j ，一俾圳，f ( ) 如引理2 j 定义。对1s ，- ， 记 层( 女) = 圭1 = 0f ( f + 1 ) 三 爱；：；：；莲： ：； ，e f ：c t ，瓞k 则对= 1 ：7 ， s ( + 1 ) ( 七+ 1 ：m ，k + l ：n ) = 肌e ( ) v k = 趔：( ) + a 2 1 ( ) a l ，( ) 一e f ：( ) - 4 ，( ) 一1 a 2 ( ：) 一 a 2 1 ( ) a t ( k ) 1 磁( k ) 十础( ( 舟) 一1 _ - z ( 女) ( 2 7 ) ( 28 ) 证我们首先证明( 2 7 ) 当= 1 时，由于s ( 1 ) = f ( “，i i7 i = 一p i ，k = 一q 丁 则由( 2 5 ) 得 s ( 2 ( 2 ：m ，2 ：诈) = 蜀f ( 1 ) q t + f ( 2 1 ( 2 ：7 h ，2 ：乱) = p i e 1 q r r = w 7 1 e ( 1 k 故当= 1 时( 2 7 ) 成立 华东师范大学博士论文若干最，j x - - 乘问题的舍八误差研究 假设当l k k 都成立。由此得( 2 1 0 ) 另方面，由选主元及一阶误差表达式得 1 7 一i 钏f ( 嚣) 釉= 降置垒辚垦盥逍1 襄e 乞i 志( 岸i 十i 嚣- ( k l s 尝襄e 拈州i k q i 十1 s 龆1 ) + u 陬，一i = i s 嚣i ， t e e e 心。i 曼u 表示t 的浮点计算过程中除法的相对舍入误差将s = 0 及( 21 0 ) 代入上式即得( 21 1 ) 一( 21 2 ) 口 j 。 一。 华东师范大学博士论文若干最小二乘问题的鬯、 误差研究 2 2 2 可逆线性系统a x = b 的向前畲人误差分析 下面我们分析可逆线性系统a x = b 的向前舍入误差分j 斤。其中a r “”1 非 奇异假定n l ，n r 如2 21 定义，令4 ( 1 ) = a h r ，6 ( 1 ) = n l b 在解方程组的 过程中，我们需要将系统( ( ”，6 ( 1 ) 化成上梯形( u ，