（计算数学专业论文）the+optimal+accelerated+overrelaxation++for+rank+deficient+linear+systems.pdf

单位谕文狷劁性聱明 本人郑重声明： l 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成果。 3 ，本论文中除引文外，所有实验、数据和有关材料均是真实的， 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已经发表或 撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了谢意。 作者签名： 董盘! 函 日 期：2 噬：垒8 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质舨；有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅；有 权将学位论文的内容编入有关数据库进行检索f 有权将学位论文的标题和摘要 汇编出版。保密的学位论文在解密后适用本规定。 作者签名： 遣茎，蛩 e t 期：三口4 生一 t h e o p t i m a l a c c e l e r a t e do v e r r e l a x a t i o n m e t h o d sf o rr a n kd e f i c i e n tl i n e a r s y s t e m s a b s t r a c t i nt h i sp a p e r ，w es t u d , t h eo p t i m a lp a r a m e t e r so ft h ea o r i t e r a t i v em e t h o df o r r a n kd e f i c i e n ts y s t e m sb yi n t r o d u c i n gt h ee x t r a p o l a t i o ns c h e m ea n ds i m p l i f i e dm s b i u s t r a n s f o r m a t i o nt h ed e t e r m i n a t i o no ft h et w oo p t i m a lp a r a m e t e r sra n duo ft h e a o ri t e r a t i o nm a t r i xi sr e d u c e dt ot h eo p t i m ao fe x t r a p o l a t i o np a r a m e t e r0a n dt h e r e l a x a t i o np a r a m e t e rro ft h ea s s o c i a t e ds o ri t e r a t i o nm a t r i x t h e d e v e l o p m e n to ft h ec l a s s i c a li t e r a t i v em e t h o d s f o rt h es o l u t i o no fl i n e a rs y s t e m s i nt h el a s t2 0 t hc e n t u r yo rm o r ee a r l i e ri ss i m p l yi n t r o d u c e di nc h a p t e r1 i nc h a p t e r2 ，w eg i v eo u to t h e rs u b p r o p e ra o r s p l i t t i n g sf o rr a n kd e f i c i e n t f i n e a rs y s t e m so i lt h eb a s eo fr e s u l t sw h i c hs t u d i e db yt i a n 1 7 a n ds o m en e c e s s a r y p r e l i m i n a r i e so fs u b p r o p e rs p l i t t i n g sa r ea l s oi n t r o d u c e d t h em a i nr e s u l t so fo u rp a p e ra r ei nc h a p t e r3 i nt h i sc h a p t e rw es t u d yt h e o p t i m a lp a r a m e t e r su n d e ro u rc o n c e p t i o no fo p t i m u mb yg e o m e t r y m e t h o d t h eb a s i c p r o p e r t i e so fe x t r a p o l a t i o ns c h e m e a n dm s b i u st r a n s f o r m a t i o nm a k ea ni m p o r t a n tr o l e i no u rp r o c e s so fo b t a i n i n gt h eo p t i m a lp a r a m e t e r s k e y w o r d s ：i t e r a t i v em e t h o d s ，j a c o b im e t h o d ，a o rm e t h o d ，s u b p r o p e rs p l i t t i n t ，s e m i c o n v e r g e n c e ，e x t r a p o l a t i o ns c h e m e ，c o n s i s t e n t l yo r d e r e dm a t r i x ，o p t i m a l p a r a m e t e r a m e r i c a nm a t h e m a t i c ss u b j e c t ( 1 9 9 1 ) c l a s s i f i c a t i o n ：6 5 f 1 0 c h i n e s el i b r a r yc l a s s 汾c a t i o n ：0 2 4 1 6 2 亏秩线性方程组的最优a o r 迭代法 摘要 在本论文中，我们通过引入外推方法和一次m s b i u s 映射来研究亏秩线性 方程组的a o r 迭代法的最优因子我们把推导a o r 迭代矩阵的最优因子 归结为对一次m s b i u s 映射申的0 因子和相应于a o r 迭代法的s o r 迭代矩 阵的松弛因子r 的最优性的确定 我们在第一章中简要介绍了一下2 0 世纪或更早时期的有关解线性方程 组的经典迭代法的发展过程。 在第二章中，我们在参考文献 17 】的基础上又给出了另外几个s u b p r o p e r a o r 分裂，同时也介绍了一些关于s u b p r o p e r 分裂的基础知识。 第三章是本篇论文的重点。在这一章中，我们用几何的方法来推导a o r 迭代法的最优因子。外推方法和一次m s b i u s 映射的基本性质在我们的推导 过程中起了十分重要的作用。 关键词：迭代法，j a c o b i 迭代，a o r 迭代，s u b p r o p e r 分裂，半收敛，外推 法，相容次序矩阵，最优因子 a m s ( 1 9 9 1 ) 主题分类：6 5 f 1 0 中图分类：0 2 4 1 6 3 c h a p t e r1 t h ei n t r o d u c t i o no ft h ec l a s s i c a l i t e r a t i v em e t h o d sf o rl i n e a rs y s t e m s n u m e r i c a ll i n e a ra l g e b r ai sa ne x c i t i n gf i e l do fr e s e a r c ha n dm u c ho ft h i sr e s e a r c h h a sb e e nt r i g g e r e db ya p r o b l e m t h a tc a nb ep o s e ds i m p l ya s ：g i v e na c ”。“，b c ”， f i n ds o l u t i o nv e c t o r ( s 1z c “s u c ht h a ta z = b m a n ys c i e n t i f i cp r o b l e m sl e a dt ot h e r e q u i r e m e n tt os o l v el i n e a rs y s t e m so fe q u a t i o n sa sp a r to ft h ec o m p u t a t i o n s a l t h o u g hi t e r a t i v em e t h o d s f o rs o l v i n gl i n e a rs y s t e m sf i n dt h e i ro r i g i ni nt h ee a r l y 1 9 t hc e n t u r y ( w o r kb yg a u s s ) ，t h ef i e l dh a ss e e na ne x p l o s i o no fa c t i v i t ys p u r r e d b yd e m a n dd u et oe x t r a o r d i n a r yt e c h n o l o g i c a la d v a n c e s i ne n g i n e e r i n ga n ds c i e n c e s ， t h ep a s tf i v ed e c a d e sh a v eb e e np a r t i c u l a r l yr i c hi nn e wd e v e l o p m e n t s ，e n d i n gw i t h t h ea v a i l a b i l i t yo fl a r g et o o l b o xo fs p e c i a l i z e da l g o r i t h m sf o rs o l v i n gt h ev e r yl a r g e p r o b l e m sw h i c ha r i s ei ns c i e n t i f i ca n di n d u s t r i a lc o m p u t a t i o n a lm o d e l s i t e r a t i v em e t h o d sh a v et r a d i t i o n a l l yb e e nu s e df o rt h es o l u t i o no fl a r g el i n e a rs y s t e m sw i t hd i a g o n a l l yd o m i n a n ts p a r s em a t r i c e s f o rs u c hs y s t e m st h ej a c o b ia n d g a u s s s e i d e lm e t h o d sc o u l db eu s e dw i t hs o m es u c c e s s ，n o ts om u c hb e c a u s eo ft h e r e d u c t i o ni nc o m p u t a t i o n a lw o r k ，b u tm a i n l yb e c a u s eo ft h el i m i t e da m o u n to fm e m o r y t h a ti s r e q u i r e d t h eg a u s s s e i d e li t e r a t i o nw a st h es t a r t i n gp o i n tf o rt h es u c c e s s i v e o v e r r e l a x a t i o nf s o r ) m e t h o d sw h i c hd o m i n a t e dm u c ho ft h el i t e r a t u r eo ni t e r a t i v e m e t h o d sf o rab i gp a r to ft h es e c o n dh a l fo ft h el a s tc e n t u r y t h em e t h o dw a sd e v e l o p e di nt h e1 9 t hc e n t u r y ，o r i g i n a l l yb yg a u s s i nt h em i d 一1 8 2 0 sa n dt h e nl a t e rb ys e i d e l i n1 8 7 4 t h e p o i n ts u c c e s s i v eo v e r r e l a x a t i o nt e c h n i q u e ss e e m s t oh a v ea p p e a r e di nt h e1 9 3 0 s h o w e v e r ：f o r m a l l yi t st h e o r yw a se s t a b l i s h e da l m o s ts i m u l t a n e o u s l yb yp r a n k e la n d y o u n g i nt h e1 9 5 0 s s u c c e s s i v eo v e r r e l a x a t i o nm e t h o d s ，a n dn u m e r o u sv a r i a n t s ，b e c a m e e x t r e m e l yp o p u l a r a n dw e r et h em e t h o d so f c h o i c ei nc o m p u t e rc o d e sf o rl a r g ep r a c t i c a l p r o b l e m s a l t h o u g ht h e i rp o p u l a r i t yh a sb e e no v e r s h a d o w e dl a t e r ，a r o u n da f t e r1 9 8 0 ， b ym o r ep o w e r f u lt e c h n i q u e s t h e ya r e s t i l lu s e di ns o m e a p p l i c a t i o n se i t h e ra st h em a i n i t e r a t i v es o l u t i o nm e t h o do ri nc o m b i n a t i o nw i t hr e c e n tt e c h n i q u e s ( e g a ss m o o t h e r s f o r m u l t i g r i do r a sp r e c o n d i t i o u e r s f o rk r y l o vm e t h o d s lt h es u c c e s so ft h es o r 4 m e t h o d sh a sl e dt oar i c ht h e o r yf o ri t e r a t i v em e t h o d s ；t h i sc o u l db eu s e df r u i t f u l l yf o r t h ea n a l y s i so fl a t e rm e t h o d sa sw e l l t h ea c c e l e r a t e dg a u s s s e i d e lm e t h o d sh a v em o t i v a t e di m p o r t a n td e v e l o p m e n t si n t h et h e o r yo fl i n e a ra l g e b r a i np a r t i c u l a r ，r e l e v a n t p r o p e r t i e sf o rm m a t r i x ，i n t r o d u c e db yo s t r o w s k i ( 1 9 3 7 ) ，w e r eu n c o v e r e da n dc o n v e r g e n c er e s u l t sf o rs o c a l l e dr e g - u l a rs p l i t t i n g s ，i n t r o d u c e db yv a r g a ( 1 9 7 4 ) ，w e r ee s t a b l i s h e d ac o r n e r s t o n ei nt h e c o n v e r g e n c et h e o r yw a ss t e i n r o s e n b e r gt h e o r e m ( 1 9 4 8 ) w h i c hp r o v e dr e l a t i o n sb e t w e e nt h ea s y m p t o t i cr a t e so fc o n v e r g e n c ef o rt h es u c c e s s i v eo v e r r e l a x a t i o um e t h o d s ， i n c l u d i n gt h eg a u s s s e i d e lm e t h o d ，a n dt h ej a c o b im e t h o d i n1 9 7 8 ，h a d j i d i m o s 9 】f i r s ts u g g e s t e da s i m p l e ，b u tp o w e r f u ls c h e m ef o rl a r g el i n e a r s y s t e m su n d e rt h en a m eo fa c c e l e r a t e do v e r r e l a x a t i o n ( a o r ) a n dt h ew e l l k n o w n j a c o b im e t h o d ，g a u s s s e i d e lm e t h o da n ds o rm e t h o dc a nb ed e r i v e df r o mt h ea o r m e t h o da ss p e c i a lc a s e s w ew i l li n t r o d u c et h e mi nt h ef o l l o w i n gd e t a i l s f o rt h es i m p l ec a s ew h e nn = ma n dai sn o n s i n g u l a rw ec o n c e r nw i t ht h en u m e r i c a ls o l u t i o no fal a r g el i n e a rs y s t e m a x = b a c ”。”，b c “ 0 ) ( 1 1 ) w ec o n s i d e ri t e r a t i v em e t h o d sb a s e do nas p l i t t i n go ft h em a t r i xa ( s e er e f e r e n c ei n 3 ) n a m e l y ，w ew r i t e a = m n ，( 12 ) w h e r em ，t h ep r e c o n d i t i o n e r ，o rp r e c o n d i t i o n i n gm a t r i x ，i st a k e nt ob ei n v e r t i b l ea n d c h e a pt oi n v e r t ，m e a n i n gt h a tal i n e a rs y s t e mw i t hm a t r i xc o e f f i c i e n tm i sm u c hm o r e e c o n o r l f i c a lt os o l v et h a n ( 1 1 ) b a s e do n ( 1 2 ) ，( 1 1 ) c a nb ew r i t t e ni nt h ef i x e d p o i n t f o r m z = t x + c ，t ：= m n ，c ：= m b ，( 1 3 ) w h i c hy i e l d st h ef o l l o w i n gi t e r a t i v es c h e m ef o rt h es o l u t i o no f ( 11 ) ： z m + 1 ) = t x ( m + c ，竹1 = 0 ，1 ，2 ， a n dz ( o ) c “ a r b i t r a r y( 14 ) as u f f i c i e n ta n dn e c e s s a r yc o n d i t i o nf o r ( 1 4 ) t oc o n v e r g e ，t ot h es o l u t i o no f ( 1 1 ) ，i s p ( t ) 1 ，w h e r ep ( ) d e n o t e ss p e c t r a lr a d i u s w h i l eas u f f i c i e n tc o n d i t i o nf o rc o n v e r - g e n c ei sj i t i i 1 ，w h e r e j fd e n o t e sm a t r i xn o r mi n d u c e db yav e c t o rn o r m ( s e e 3 】) 5 t od e r i v et h ec l a s s i c a ll t e r a t i v em e t h o d so n ew r i t e sa d luw i t hd= d i a g ( a ) ，a n da s s u m e sd e t ( d ) 0 ，ls t r i c t l yl o w e ra n dus t r i c t l yu p p e rt r i a n g u l a r m a t r i c e s ，r e s p e c t i v e l y t h u s ，t h ej a c o b ii t e r a t i v em e t h o d ( m 兰d ) i sd e f i n e db y z m + 1 = d 一1 ( l + u ) z ( m + d 一1 6 ； ( 1 5 ) t h eg a u s s s e i d e li t e r a t i v em e t h o d ( m 兰d l ) b y z ( ”+ 1 = ( d l ) 一1 u x ( ”) + ( d 一) 一1 6 ；( 1 6 ) t h es u c c e s s i v eo v e r r e l a x a t i o n ( s o r ) i t e r a t i v em e t h o d ( m 兰( 1 w ) ( d w l ) ) b y 。m + 1 = l 。m + c 。，l 。：= ( d u l ) 一1 ( 1 一w ) d + w u ，c c 。：= u ( d u l ) 1 b ( 1 7 ) i n ( 1 7 ) ，u c o ) i st h er e l a x a t i o nf a c t o r ( o ro v e r r e l a x a t i o np a r a m e t e r ) f o ru=1 t h es o rb e c o m e st h eg a u s s - s e i d e lm e t h o d a n dt h ea c c e l e r a t e do v e r r e l a x a t i o n ( a o r ) i t e r a t i v em e t h o d ( m 三( 1 w ) ( d 一儿) ) b y z ( r e + i ) = l r ，。z ( m ) + c r 。 l r ，u ：= ( d r l ) 一1 f ( 1 一u ) d + ( u r ) l4 - w u ，c r h ：= u ( d r l ) 一1 b ( 1 8 ) i n ( 1 8 ) ，r ，u 0a r ec a l l e dt h ea c c e l e r a t i o na n dt h eo v e r r e l a x a t i o np a r a m e t e rr e s p e c t i v e l y a n df o rr = u ，t h ea o rr e d u c e st ot h es o r m e t h o d ；f o rr = u ：1 t o 此e g a u s s s e i d e lm e t h o d ；f o rr = 0 ，“= 1 t ot h ej a c o b im e t h o d t i l ea b o v ef o u rm e t h o d sa r ec a l l e d p o i n tm e t h o d st od i s t i n g u i s ht h e mf r o mt i l e b l o c km e t h o d sf o rt h el a t t e r ，c o n s i d e ra p a r t i t i o n i n go fa i nt h ef o l l o w i n gb l o c kf o r m ： a = a 1 l a 2 l a m a 2 2 4 1 p a 2 p a p la p 2 a 卯 ( 19 ) w h e r e a “c m “，i = 1 ，2 ，p ，a n d n i = n i fw ed e f i n ed = d i a g ( a 1 1 ，a 2 2 ， 一，a p p ) ，a s s u m i n gd e t ( a i , ) 0 ，i = 1 ，2 ，一，p ，s e ta = d l uw i t hla n du b e i n gs t r i c t l yl o w e ra n ds t r i c t l yu p p e rt r i a n g u l a rm a t r i c e sr e s p e c t i v e l y , t h e nt h eb l o c k j a c o b i ，t h eb l o c kg a u s s s e i d e l ，t h eb l o c ks o ra n dt h eb l o c ka o rm e t h o d sa s s o c i a t e d w i t ht h ep a r t i t i o n i n g ( 1 9 ) o f aa x et h ei t e r a t i v em e t h o d sd e f i n e d b yp r e c i s e l vt h es a m e i t e r a t i v es c h e m e sa st h e i rp o i n tc o u n t e r p a r t si n ( 1 5 ) 一( 1 8 ) ，r e s p e c t i v e l y 6 f o rt h ec a s et h a tm n ，t h ep r o b l e m i sb e c o m et of i n d i n gt h el e a s ts q u a r es o l u t i o n o fm i n i m a 【n o r mt ot h e 【i n e a rs y s t e m 4 x = b f 1 ，1 0 1 w h e r eai sac o m p l e xm nm a t r i xa n dbac o m p l e xm v e c t o r i t e r a t i v em e t h o d sf o r s o l v i n gt h i sp r o b l e m ，o b t a i n e dv i as p l i t t i n g so ft h ec o e f f i c i e n tm a t r i xa a n de x t e n d i n g w e l l k n o w nr e s u l t sf o rt h ec a s ei nw h i c ha i san o n s i n g u l a rm a t r i x ，h a v eb e e ns u g g e s t e d b yv a r i o u sp e o p l e w em e n t i o nh e r et h ea p p r o a c h e sb a s e do np r o p e ra n ds u b p r o p e r s p l i t t i n g sa sd e v e l o p e db yb e r m a n a n dp l e m m o n s 【2 1 b e r m a na n dn e u m a n nh 巩a n d n e u m a n n 【1 3 w em e n t i o nt h a tc h e n ，i nh i sd o c t o r a lt h e s i s 7 7 c o n s i d e r e dt h ec a s ew h e nai n ( 1 1 0 ) i saf u l lc o l u m nr a n km a t r i xa n ds u g g e s t e dac o m b i n e dd i r e c t i t e r a t i v em e t h o d a u g m e n t i n gt h es y s t e m ( 1 ，1 0 ) t oas q u a r en o n s i n g u l a rs y s t e m f o rs o l v i n gt h el e a s t s q u a r e sp r o b l e m l a t e r ，m i l l e ra n dn e u m a n n 1 2 h a v es h o w nt h a t c h e n sa u g m e n t u t i o np r o c e d u r ef o rt h ef u l lc o l u m nr a n kc a s ec a nb ee x t e n d e dt ot h ec a s ew h e r ea i n ( 1 1 0 ) i sr a n kd e f i c i e n ta n dd e v e l o p e dt h et h e o r yo fs o r i t e r a t i o n sf o rs o l v i n gt h i s a u g m e n t e da n dc o n s i s t e n tl i n e a rs y s t e m ，a n di nt h i sc e n t u r y 、t i a n 1 7 】d e v e l o p e dt h e t h e o r yo fa o r i t e r a t i o n sf o rt h er a n kd e f i c i e n tl i n e a rs y s t e m s i nt h ed e v e l o p m e n to ft i l es o rt h e o r yo n es e e k sv a l u e so fu c o f o rw h i c ht h e s o rm e t h o dc o n v e r g e so r ，t h es e to fw h i c hd e f i n e st h er e g i o no fc o n v e r g e n c e ，a n d ，i f p o s s i b l e t h eb e s tv a l u eo f “，u 6 f o rw h i c ht h ec o n v e r g e n c ei sa s y m p t o t i c a l l yo p t i m a l ， n a n l e l y ，( l u 。) 2 。m c i n 0 ) p ( l u ) a n df o rt h ea o r m e t h o d ，i t sc o u n t e r p a r t sa r er ba n dw bs u c ht h a t p ( l q “b ) = ，m c i n 。) p ( e r ，u ) r 。u e 0 、 u t of i n dr e g i o n so fc o n v e r g e n c ei sap r o b l e mg e n e r a l l ym u c he a s i e rt h a nt od e t e r m i n e t h eo p t i m a lp a r a m e t e r si ne i t h e rc a s e ，h o w e v e r ，o n ea s s u m e st h a ts o m ei n f o r m a t i o n r e g a r d i n gt h es p e c t r u mo ft h ea s s o c i a t e dj a c o bi t e r a t i v em a t r i x 了，d ( j ) ，i sa v a i l a b l e t h i si n f o r m a t i o nc o m e sm o s t l yf r o mt h ep r o p e r t i e so ft h em a t r i xa f a n dt h ep a r t i t i o n i n gc o n s i d e r e d ) 7 c h a p t e r 2n o t e so nt h ea o rm e t h o d f o r r a n kd e f i c i e n ts y s te m f o rt h ep r o b l e mo f o b t a i n i n gt h e l e a s ts q u a r es o l u t i o no fm i n i m a ln o r mt ot h el i n e a r s y s t e m a y = b ，( 2 0 1 ) w h e r ea c ”。“a n db c ”i nt h ep a p e ro fm i l l e ra n dn e u m a n n 1 2 1 ，t h es y s t e m w a sf i r s t a u g m e n t e dt o ab l o c k4 4c o n s i s t e n t s y s t e m a n dt h e n t h ea u g m e n t e d c o e f f i c i e n tm a t r i xw a ss p l i t t e db yas u b p r o p e rs o rs p l i t t i n g a ni n t e r v a lf o r t h e r e l a x a t i o np a r a m e t e r si nw h i c ht h es u b p r o p e rs o r i t e r a t i o nm a t r i xi ss e m i c o n v e r g e n t i sd e t e r m i n e d r e c e n t l y ，t i a n 1 7 】e x t e n d e dm i l l e ra n dn e u i n a n n 7 sr e s u l t sb ys p l i t t i n gt h ea u g m e n t e dc o e f f i c i e n tm a t r i xi n t oas u b p r o p e ra o ri t e r a t i o nm a t r i x t h ei n t e r v a l sf o r t h ea c c e l e r a t i o na n dt h eo v e r r e l a x a t i o np a r a m e t e ri nw h i c ht i l es u b p r o p e ra o r i t e r a t i o nm a t i xi ss e m i c o n v e r g e n ta r ed e t e r m i n e d t h ep u r p o s eo ft h i sc h a p t e ri st od i s c u s st h eo t h e rs u b p r o p e ra o r s p l i t , t i n g st h a t t i a n 1 7 jd i d n o t g i v eo u t i ns e c t i o n2l s o m en e c e s s a r yp r e l i m i n a r i e sa n dr e s u l t s c o n c e r n i n gs u b p r o p e ra n dp r o p e rs p l i t t i n g sa r ep r o v i d e d a n di ns e c t i o n2 2 w es t u d ) , t h eo t h e rs u b p r o p e ra o r s p l i t t i n g st h a th a v et h es a m es e m i c o n v e r g e n c e i n t e r v a l sw i t h t i a n 2 1p r e l i m i n a r i e s l e ta c ”“t h e nt h e r ee x i t sau n i q u em a t r i xx c “s a t i s f i e s ： ( 1 ) a x a = a ，( 2 ) x a x = x ，( 3 ) a x = ( a x ) + ，( 4 ) x a = ( x a ) 。， w h e r ea + d e n o t e st h ec o n j u g a t et r a n s p o s eo fa t h i sx i sc a l l e dm o o r e p e n r o s ei n v e r s e o fa d e n o t e db ya + i ti sw e l lk n o w nt h a tt h el e a s ts q u a r es o l u t i o no fm i n i m a ln o r m t ot h es y s t e m ( 2 0 1 ) i sa + b l e ta c “。“a n di n d e x ( a ) s1 ，t h e nt h e r ee x i t sau n i q u ex c ”。“s a t i s f y i n g ( 1 ) ， ( 2 ) a n da x = x a t h i sm a t r i xx i sc a l l e dg r o u pi n v e r s eo fa ，d e n o t e db ya 4 ，w h e r e 8 i n d e z ( a ) i st h el e a s tn o n n e g a t i v ei n t e g e rt ，s u c ht h a tr ( a ) = r ( a 抖1 ) ，w h e r e 尺( a ) d e n o t e st h er a n g es p a c eo fa a ni t e r a t i v es c h e m ef o rd e