（運(yùn)籌學(xué)與控制論專業(yè)論文）遞歸算法及應(yīng)用.pdf

煳淵 。 廣西大學(xué)學(xué)位論文原創(chuàng)性聲明和學(xué)位論文使用授權(quán)說明 學(xué)位論文原創(chuàng)性聲明 本人聲明：所呈交的學(xué)位論文是在導(dǎo)師指導(dǎo)下完成的，研究工作所取得的成果和相關(guān) 知識(shí)產(chǎn)權(quán)屬廣西大學(xué)所有除已注明部分外，論文中不包含其他人已經(jīng)發(fā)表過的研究成果， 也不包含本人為獲得其它學(xué)位而使用過的內(nèi)容對(duì)本文朐研究工作提供過重要幫助的個(gè) 人和集體，均已在論文中明確說明并致謝 論文作者簽名= 重烯達(dá) 2 d f d 年6 月，日 學(xué)位論文使用授權(quán)說明 本人完全了解廣西大學(xué)關(guān)于收集、保存、使用學(xué)位論支的規(guī)定即： 本人保證不以其它單位為第一署名單位發(fā)表或使用本論文的研究內(nèi)容； 按照學(xué)校要求提交學(xué)位論文的印刷本和電子版本； 學(xué)校有權(quán)保存學(xué)位論文的e p , 屙j 本和電子版，并提供目錄檢索與閱覽服務(wù)； 學(xué)?？梢圆捎糜坝?、縮印、數(shù)字化或其它復(fù)制手段保存論文： 學(xué)?？梢怨颊撐牡牟糠只蛉績?nèi)容 請(qǐng)選擇發(fā)布時(shí)間： 口即時(shí)發(fā)布口解密后發(fā)布 ( 保密論文需注明，并在解密后遵守此規(guī)定) 做各獬蜘磁各p 瑚鉍月知 ， 。iz。善“囂。二、盛小“l(fā)藝。lt萎掣罄譬囂塹爵強(qiáng)罄l鬟 遞歸算法及應(yīng)用 摘要 遞歸算法是求解矩陣特征值和奇異值的重要方法它的實(shí)質(zhì)是調(diào)用遞歸函數(shù)把問題 轉(zhuǎn)化為規(guī)模縮小了的同類問題的子問題，然后再次調(diào)用遞歸函數(shù)來完成問題的求解近 年來，一些學(xué)者( 如b r o w n e 、c h a n d r a s e k a r a n 等) 給出了求解h a n k e l 矩陣奇異值的快速 遞歸算法和求解t o e p l i t z 矩陣奇異值的快速遞歸算法，并證明了遞歸算法仍適用于 s e m i s e p a r a t e 矩陣特征值的求解 本文首先在求解t o e p l i t z 矩陣奇異值的快速遞歸算法的基礎(chǔ)上，通過探討p a s c a l 矩陣的結(jié)構(gòu)，得到p a s c a l 矩陣與向量相乘的快速算法，從而得到了求解p a s c a l 矩陣奇異 值的快速遞歸算法：然后給出廣義j a c o b i 矩陣的定義，在其順序主子陣的特征值不滿足 嚴(yán)格交織的條件下，證明了遞歸算法仍可以求解廣義j a c o b i 矩陣的特征值數(shù)值實(shí)驗(yàn)表明 算法是有效的 關(guān)鍵詞：分而治之法；快速傅里葉變換；二分法；變號(hào)數(shù) r e c u r s i v ea l g o r i t h ma n di t sa p p l i c a t i o n a b s t r a c t t h er e c u r s i v ea l g o r i t h mi sa ni m p o r t a n tw a yf o rs o l v i n gm a t r i xe i g e n v a l u ea n ds i n g u l a r v a l u e i t se s s e n c ei st or e d u c et h es i z eo ft h ep r o b l e mi n t os u b - p r o b l e m s o fs i m i l a rp r o b l e m s b ye m p l o y i n gt h er e c u s i v ef u n c t i o n , t h e nb ye m p l o y i n gt h er e c u s i v ef u n c t i o na g a i n , w e c o m p l e t et h ep r o b l e m s i i nr e c e n ty e a r s ，s o m er e s e a r c h e r sh a v ep r o p o s e daf a s tr e c u r s i v e a l g o r i t h mf o rh a n k e lm a t r i c e sa n dt o e p l i t zm a t r i xs v d ，s u c ha sb r o w n e ，c h a n d r a s e k a r a n , e t c ，a n dt h e yh a v ep r o v e dt h a tt h er e c u r s i v ea l g o r i t h mi ss t i l ls u i t a b l et os o l v et h ee i g e n v a l u e o fs e m i s e p a r a t em a t r i x a c c o r d i n gt ot h ef a s ts v d r e c u r s i v ea l g o r i t h mo ft o e p l i t zm a t r i x ，w eg e tf a s ts v d r e c u r s i v ea l g o r i t h mo fp a s c a lm a t r i xb yt a k i n ga d v a n t a g eo fp a s c a ls t r u c t u r e t h e nw eg i v et h e d e f i n i t i o no ft h eg e n e r a l i z e do fj a c o b im a t r i x ，a n dp r o v et h a tt h er e c u r s i v ea l g o r i t h mi s s t i l l s u i t a b l et os o l v ei t s e i g e n v a l u ew i t h o u tt h e c o n d i t i o no f s t r i c t l y i n t e r l a c e n u m e r i c a l e x p e r i m e n t si n d i c a t et h a tt h ea l g o r i t h mi se f f e c t i v e k e yw o r d s ：d i v i d ea n dc o n q u e rm e t h o d ；f i t ；b i s e c t i o n ；v a r i a b l en u m b e r 目錄 第一章引言1 1 1 遞歸算法的發(fā)展歷史1 1 2 本文的工作4 第二章定義與引理6 第三章求解p a s c a l 矩陣奇異值的快速分而治之法9 3 1 求解矩陣奇異值的分而治之法9 3 2p a s c a l 矩陣與向量乘積的快速算法1 0 3 3 數(shù)值試驗(yàn)15 第四章求解廣義j a c o b i 矩陣特征值的二分法1 6 4 1 口類矩陣1 6 4 2 類矩陣1 9 4 3 “一個(gè)零廣義j a c o b i 矩陣2 5 4 4 “q 個(gè)零”廣義j a c o b i 矩陣2 7 4 5 算法設(shè)計(jì)3 0 4 6 數(shù)值試驗(yàn)3 2 第五章結(jié)論3 3 參考文獻(xiàn)3 4 致謝3 7 攻讀學(xué)位期間發(fā)表論文情況3 8 劫 歸算法及壓u 嗣 第一章引言 1 1 遞歸算法的發(fā)展歷史 矩陣的特征值和奇異值在結(jié)構(gòu)振動(dòng)等方面有著重要的應(yīng)用【3 】求解矩陣特征值和奇 異值的方法有很多，如t w i s t e dm e t h o d 11 - 1 3 、q rm e t h o d 1 舢1 6 1 、j a c o b im e t h o d b7 - 2 3 、 d a v i d s o nm e t h o d 2 4 - 3 0 1 遞歸算法也是求解矩陣特征值和奇異值的重要方法【i - 3 】它在區(qū)間上表現(xiàn)為區(qū)間分 半法，即二分法：在矩陣上表現(xiàn)為矩陣分半法，即分而治之法 1 9 6 7 年，w b a r t h 2 9 】首次給出求解不可約對(duì)稱三對(duì)角矩陣特征值的二分法1 9 9 7 年，t r e f e t h e n 2 1 年提出使二分法有效的性質(zhì)2 0 0 6 年，陸金甫嗍再次詳細(xì)地介紹了該性質(zhì)， 并指出二分法是求解矩陣部分特征值的標(biāo)準(zhǔn)算法 設(shè)n 階矩陣r 的k 階順序主子陣r 。的特征值為五，五，五，k + l 階順序主子陣冠+ 1 的特征值為鸕，鮑，版小使二分法有效的關(guān)鍵性質(zhì)是這些特征值是嚴(yán)格交織的，即對(duì)于 k = 1 ，2 ，n - 1 ，不等式4 鸕 五 鸕 以 聆 定義2 1m x np a s c a l 矩陣p = ( 仍，) 的定義如下： a 。，= 錙- 2 其中，q = 南 例如，6 x 5p a s c a l 矩陣 p = = l 11l1 12345 1361 01 5 l41 02 03 5 151 53 57 0 162 1 5 61 2 6 定義2 2 5 1n x n - f - - 角p a s c a l 矩陣l = ( ，) 定義如下： 定義2 3 【5 1 實(shí)數(shù)列 口o ，口1 ，a m 一2 ，a m 一1 ， ( 2 1 ) ( 2 2 ) 且口o 0 ，a m 0 ，從左到右，如果a t l q 0 ，即q 與q l 符號(hào)相反，則為有一個(gè)變號(hào)數(shù)，如 果q = 0 ，a j 一?？趈 0 ，也為有一個(gè)變號(hào)數(shù)，序列中的變號(hào)數(shù)的總和稱為該序列的變號(hào)數(shù) 為了證明的需要，在第一類零點(diǎn)的基礎(chǔ)上，我們給出廣義第1 類根的定義 定義2 4 如果實(shí)數(shù)而是f o ( x ) 的一個(gè)根，并且存在一個(gè)正數(shù)s ，使得對(duì)任意 6 紛 挖 o ， 而對(duì)壇( x o ，而+ f ) ，有兀( x ) 彳( x ) o 或五 ) 彳( x ) 0 ，則稱r 為j a e o b i 矩陣 設(shè)r 的k 階順序主子陣r 七的特征多項(xiàng)式為p a x ) 令風(fēng)( 功= 1 ，根據(jù)( 1 1 ) 式，對(duì) k = 2 ，3 ，n ，有 p a x ) = o - b , ) p h o ) 一e 五一l p t 一2 ( d ( e k - l ，五一l o ) ( 2 3 ) 滿足( 2 3 ) 式的序列p o ( x ) ，p l ( x ) ，p n i ( x ) ，以( x ) 稱為j a e o b i 矩陣特征多項(xiàng)式序列若 a ( 護(hù)) = 0 ( 1 f 刀一1 ) ，由( 2 3 ) 式，b + 。( 目) = 飛z b l ( p ) ，那么易一1 ( 秒) b + l ( d o ，見文獻(xiàn) 【3 】 引理2 1 吲通過f f t ，珂以下三角p a s c a l 矩陣和任意一個(gè)門維的向量的乘積的運(yùn)算 量是o ( n l o gn ) 證明見文獻(xiàn) 5 引理2 2 【6 】通過f f t ，m nt o e p l i t z 矩陣和任意一個(gè)n 維的向量的乘積的運(yùn)算量 是o ( ( m + n ) l o g ( m + n ) ) 證明見文獻(xiàn) 6 7 q 0p。i = 數(shù) 尺 實(shí)是 t s 翻 z- c 葉q 設(shè) 對(duì) 爭(zhēng)乞 義定 遞歸算法及應(yīng)用 一 引理2 3 3 1 p o ( x ) ，a ( x ) ，見( x ) 是j a e o b i 矩陣特征多項(xiàng)式序列，則島( x ) 有”個(gè)不 同的實(shí)根，并且見( x ) 的根都是關(guān)于見一。( x ) 的廣義第1 類根 證明見定義2 4 和文獻(xiàn) 3 定理4 1 1 與定理4 1 2 引理2 4 p 1i 發(fā)p o ( x ) = o ，記v n ( x ) 是j a e o b i 矩陣特征多項(xiàng)式序列島( x ) ，崩( x ) ，見( x ) 的變號(hào)數(shù)，給定咖，如果見( 口) o ，以( 6 ) o ，那么v n ( a ) - v n ( b ) 等于見( x ) 在區(qū)f s q a ，b 】上根 的個(gè)數(shù) 證明見文獻(xiàn) 3 引理2 5 嘲i 艮p o ( x ) ，a ( x ) ，以( x ) 是j a c o b i 矩陣特征多項(xiàng)式序列，若見( 鄉(xiāng)) = 0 ，則 見一i ( 矽) 0 證明見文獻(xiàn) 3 廣西大掌碩士掌位論文 第三章求解p a s c a l 矩陣奇異值的快速分而治之法 本章首先給出求解矩陣奇異值的分而治之法，接著探討p 嬲c a l 矩陣的結(jié)構(gòu)，得到 p a s c a l 矩陣與向量乘積的快速算法，從而我們可以得到求解p a s c a l 矩陣奇異值的快速分 而治之法 3 1 求解矩陣奇異值的分而治之法 算法1 第一步是l a n c z o s 雙對(duì)角化算法1 一給定向量z ，尋找正交矩陣u 和v n 。，使 u r p v = b 此算法把m x n 矩陣p 轉(zhuǎn)化為，z 力雙對(duì)角矩陣 u o = 0 ；屬= 1 ； 廠2 瓶； f o r j = lt on _ = ； z = h - p j 一心 哆= 14 ：； 吩= 兀； i f j o ( f = 1 ，k - 1 ) ，由( 4 1 ) 式和定義2 5 知p o ( x ) ，a ( x ) ，仇( x ) 是j a c o b i 矩陣順序 主子陣的特征多項(xiàng)式序列。q z = o q = 尼，以一1 ) ，根據(jù)( 4 1 ) 式，有 見+ i ( x ) = ( x - b , + i ) 見( x ) ， 以一l ( x ) = o - b 一1 ) 島一2 ( 力， 1 6 廣西大掌碩士學(xué)位論文 遞歸算法及窟己j 書 店( x ) = o 一吃) 以一l ( 力， ( 4 2 ) 一 則 見( x ) = ( x 一玩+ 。) ( z 一甌+ 2 ) ( x 一吃) 見( x ) 設(shè)s 。( x ) 是序列p o ( x ) ，p l ( 力，見( x ) 的變號(hào)數(shù)，k ( x ) 是序列p o ( x ) ，a ( x ) ，p k ( x ) 的 變號(hào)數(shù)，k ( x ) 是序列仇0 ) ，風(fēng)+ 。( x ) ，以( x ) 的變號(hào)數(shù)，則s 。( x ) = v k ( x ) + 1 k ( 妁 引理4 1 給定a ，b ，如果p n ( a ) 0 ，見( 6 ) 0 ，那么最( 口) 一最( 6 ) 是見( x ) 在區(qū)間 口，b 】 中根的個(gè)數(shù) 證明 最( 口) 一最( 6 ) = 圪( 口) + 瓦一七0 ) 一( 圪( 6 ) + 乙一。( 6 ) ) = v k ( a ) - v k ( b ) + ( t 一i ( 口) 一乙一i ( 6 ) ) 見( z ) = ( x 一玩+ 1 ) ( x 一吮+ 2 ) ( x 一吃) 見( x ) ，p n ( a ) 0 ，見( 6 ) 0 ，見( 口) 0 ，p k ( b ) 0 p o ( x ) ，p l ( x ) ，p a x ) 是j a c o b i 矩陣的特征多項(xiàng)式序列，設(shè)c 是見( x ) 在區(qū)間【口，6 】中根的 個(gè)數(shù)，由引理2 4 知v a a ) 一v k ( b ) = c 假設(shè)刀一七個(gè)數(shù)小玩+ 2 ，吃有h 個(gè)在【口，糾中，由 磊( x ) = ( x 一玩+ i ) ( x 一玩+ 2 ) ( x b ) p a x ) 知，在 口，6 】中，見( x ) i 七p k ( x ) 多h 個(gè)根故只需證明砭一。( 口) 一瓦一。( 6 ) = 廳成立 p k ( x ) ，p k + ( x ) ，以( x ) 在【口，6 內(nèi)的所有根由小到大排列成 h ，塢，_ ，k 令= 口，九“= 6 ，那么在區(qū)間【口，6 】中有歷+ 1 個(gè)不相交的小區(qū)間 ( ，啊) ，( 啊，鴨) ，( ，k + 。) 在每個(gè)小區(qū)間( 扛，曩+ ，) 中，序列中的每個(gè)多項(xiàng)式乃( x ) 都不變號(hào)，即x ( 吩，忍+ 。) ，t 一。( x ) 是 常數(shù)在每個(gè)小區(qū)間( 吩，羈+ ，) 內(nèi)任取一點(diǎn)而，瓦叫( 墨) 代表序列見( x ) ，見+ 。( x ) ，見o ) 在 ( 囊，曩+ ) 中的變號(hào)數(shù)，則有變號(hào)數(shù)的序列 瓦一。( 口) ，瓦一。( 而) ，瓦一。瓴) ，瓦一。( ) ，瓦一。p ) 記，= 瓦州( 薯) 一五一。( t + 1 ) ，于是 1 7 廣西大學(xué)碩士學(xué)位企文 m - i 瓦一。c a ) 一瓦。( 6 ) = 瓦。( 口) 一露。( 嘞) + ，+ 瓦一。( x a - r , 一。( 6 ) 下面分析，和瓦一。( a ) 一瓦一。( x o ) ，互一。( ) 一瓦一。( 6 ) 首先分析j = 互一。( t ) 一瓦吲( 五+ ，) ，且p x i a ( h , ，瑰+ 。) 變到( 曩小吩+ ：) 時(shí)瓦咀( x ) 的變化情況 由( 4 2 ) 式知每個(gè)7 j l + 。都是見( x ) 的根，根據(jù)p a x ) = ( x - b , + ，) 一+ ：) ( x - b a p 。( x ) 分兩種 情況討論 ( 1 ) 如果既( + 。) = 0 且紅+ ，玩“，吃4 ， 由( 4 2 ) 式知， + ，也是p k + ，( x ) ，p n 一。o ) ，n ( x ) 的根由易o(hù) ) a “ ) = o 一島+ ，) p ；( 功 ( 1 = l q k + l ，, n - 1 ) 知，口j + l 是以( x ) 關(guān)于見一t ( x ) 廣義第3 類根，p n l ( x ) 關(guān)于n 一2 ( x ) f - y 第3 類根，鼽+ ，( 曲關(guān)于仇( x ) 廣義第3 類根，則仇+ 。( 五) ，以一瓴) ，見“) 的變號(hào)數(shù)與在 見+ 。( 玉+ 1 ) ，磊一l ( 工i + 1 ) ，p n ( x , + 1 ) 的變號(hào)數(shù)相同 因此，當(dāng)見( 曩+ ) = o 且曩+ 。仇+ ，既_ 1 ，吃時(shí)，總有r ( 毛) = 丁( 而+ 。) ( 2 ) 如果島+ 。= 以( 七+ 1 ，擰) ，即6 ， 釓+ 。，釓+ 2 ，玩 由所一。( x ) 刃( x ) = 一6 ，) p 二( 功知，口j + 。是b ( x ) 關(guān)于b 一。o ) 的廣義第1 類根在 ( 魂， + 。) 中，所一。( x ) ，只( z ) 有一個(gè)變號(hào)數(shù)，而在( 曩+ p 縱2 ) 中沒有變號(hào)數(shù)對(duì)于 吃 玩+ l ，釓+ 2 ，色) ( 七+ 1 g 刀) 且6 譬紅+ l = 啡， 由島一。( x ) 以( 功= o 一6 9 ) p 乙( x ) 知，囊“是段( 功關(guān)于以一t ( x ) 的廣義第3 類根，則 珞一。( 功，硌( 功在( ，曩+ - ) 與( 曩+ pj j i + z ) 中變號(hào)數(shù)相同 因此，當(dāng)鴨+ l = 4 ( 七+ 1 ，刀) 時(shí)，h ，= 瓦- 打( 一) 一瓦一。( 薯+ 1 ) 等于6 ，個(gè)數(shù) m - i 在【口，6 】中，6 ，總的個(gè)數(shù)是h 綜合( 1 ) 和( 2 ) 分析，a ；= | z 現(xiàn)在分析瓦叫( 口) 一互一。( 而) 和瓦。( x d 一瓦一。( 掃) 因?yàn)榭诓皇莂 ( x ) 的根，由( 4 2 ) 式知口也不是見+ 。( x ) ，島一。( x ) ，見( x ) 的根對(duì)于 1 8 廣西大掌碩士掌位論文 遞歸算法及應(yīng)用 p a x ) p , “( x ) = ( x 一島+ 。) p ；( x ) ( 1 - l 【，k + 1 ，n 一1 ) ， 如果口= 不是它們的根，那么p a x ) ，所+ 。( x ) 在口的變號(hào)數(shù)與在( ，囊) 中的變號(hào)數(shù)相同，即 仇“( x ) ，n _ ( x ) ，n ( x ) 在口的變號(hào)數(shù)與在( ，i l l l ) 中的變號(hào)數(shù)相同，則瓦一。( 口) 一五一。( ) 2 0 同理可證互嘲( ) 一瓦一。( 6 ) = 0 ，則瓦一廳( 口) 一互叫( 6 ) 2 h 4 2 類矩陣 設(shè)島，島，z 都是實(shí)數(shù)，r = 石0 如 。 。 z l 一l吮 如果只存在一個(gè)正整數(shù)七( 1 k 萬一1 ) 使得以= o 且白彳 o ( ，七) ，則稱r 為類矩陣 設(shè)r 的f 階順序主子陣r 的特征多項(xiàng)式為p a x ) 令島( x ) = 1 ，根據(jù)( 1 1 ) 式，對(duì) i = 2 ，3 ，刀，有 a ( x ) = 0 6 ：) a 一。( 力一島一。z 一，刃一。( 功 ( 4 3 ) e , g o ( ，= l ，2 ，k - 1 ) ，由( 4 3 ) 式和定義2 5 知，風(fēng)( x ) ，p l ( 力，見( 功是j a c o b i 矩陣順 序主子陣的特征多項(xiàng)式序列。五= 0 ，根據(jù)( 4 3 ) 式，有 仇+ l ( x ) = ( x 一甌+ 1 ) p t ( x ) ， 仇+ 2 ( x ) = ( x 一玩+ 2 ) n + l ( x ) 一咯+ l 五+ l p a x ) ， p a x ) = ( x 一吃) 見一l ( x ) 一一l z l 見一2 ( x ) 設(shè)9 1 ( x ) = x 一+ l ，則 見+ l ( x ) = g l ( x ) 見( x ) ， a + 2 ( x ) = ( x 一甌+ 2 ) p i + l ( x ) - e k + l 五+ l p ( x ) = ( x - t , + 2 ) g l ( x ) 仇( x ) 一氣+ l 以+ l 見( x ) 1 9 廣西大學(xué)碩士掌位論文遞歸算法及應(yīng)用 = ( x 一甌+ 2 ) g l ( x ) 一e k + l 五+ i p k ( x ) 設(shè)9 2 ( z ) = ( x 一釓+ 2 ) q l ( x ) - e k + l 以“，貝i j 仇+ 2 ( x ) = 9 2 ( x ) 仇( x ) ， 仇+ 3 ( x ) = 一釓+ 3 ) 辦+ 2 ( x ) - e k + 2 五+ 2 a + i ( x ) = ( x 一甌+ 3 ) 9 2 ( x ) p a x ) 一e k + 2 五+ 2 q i ( x ) p k ( x ) 2 ( x 一+ 3 ) 9 2 ( z ) 一氣+ 2 五+ 2 q i ( x ) 】j ( x ) 類似地，可以假設(shè)q s ( x ) ，q n 一。( z ) 并推導(dǎo)出 q s ( x ) = ( x 一玩+ 3 ) 9 2 ( x ) 一e k + 2 五+ 2 q i ( x ) ， 見+ 3 ( 石) = q s ( x ) p a x ) ， 吼一i ) = o 一吃) 吼一( 工) 一一i z l q n - k - 2 ( x ) ， 見( x ) = q n 一七( x ) p a x ) 引理4 2 設(shè)q o ( x ) = 1 ，則9 0 ( x ) ，q l ( x ) ，q 2 ( x ) 9 oo0 1 1 吼一l ( x ) ，q n 一七( x ) 是j a c o b i 矩陣特征多項(xiàng) 式序列 證明由 q o ( x ) = 1 ， q l ( x ) = x 一反+ l ， 9 2 ( x ) = ( x 一玩+ 2 ) g i ( 功一+ l 以+ l ， 吼一( x ) = ( x b ) q n i 1 ( x ) 一一l z l q n - k - 2 ( x ) 及定義2 5 可知q o ( x ) ，g l ( x ) ，q 2 ( x ) ，q n - k - t ( x ) ，q n t ( x ) 是j a c o b i 矩陣的特征多項(xiàng)式序列 設(shè)s 。( x ) 是序列p o ( x ) ，a ( 力，p n ( x ) 的變號(hào)數(shù)，k ( x ) 是序列p o ( x ) ，a ( x ) ，見( x ) 的 變號(hào)數(shù)，k ( x ) 是序列p a x ) ，p k + 。( x ) ，見( x ) 的變號(hào)數(shù)，則s 。( x ) = v k ( x ) + t k m ( x ) 廣西大學(xué)碩士掌位論文 引理4 3 給定a , b ，如果見( 口) 0 ，見( 6 ) 0 ，那么甌( 口) 一甌( 6 ) 等于見( x ) 在區(qū)間 【a , b 】中根的個(gè)數(shù) 證明 最( 口) 一最( 6 ) = 圪( 口) + 乙一i ( 口) 一( 圪( 6 ) + 乙一i ( 6 ) ) = 圪( 口) 一圪( 6 ) + ( 巧廿( 口) 一乙吐( 6 ) ) 見( 口) 0 ，以( 6 ) 0 ，見( x ) = 吼一七( x ) p k ( x ) ，見( 口) 0 ，p k ( b ) 0 p o ( x ) ，a ( x ) ，見( x ) 是j a e o b i 矩陣的特征多項(xiàng)式序列，設(shè)c 是a o ) 在區(qū)間 a ，b 中根的個(gè)數(shù)，由引理2 4 知 圪( 口) 一k ( 6 ) = c 假設(shè)靠一。( x ) 有h 個(gè)根在【口，6 】中，由p a x ) = 吼一i ( x ) 仇( x ) 知，在 a , b 】 中，見( z ) p k ( x ) 多辦個(gè)根故只需證明乏。( 口) 一瓦。( 6 ) = 辦成立 把p a x ) ，a + ，( x ) ，p n ( x ) 在【口，b 】內(nèi)的所有根由小到大排列成 h ，心，k _ ，k 令h o = 口，吃+ 。= 6 ，那么在區(qū)間【口，b 】中有m + 1 個(gè)不相交的小區(qū)間 ( ，魄) ，( 啊，紅) ，c h ，+ ) 在每個(gè)小區(qū)間( 曩，吩+ ，) 中，序列中的每個(gè)多項(xiàng)式乃( 力都不變號(hào)，即x ( 忽，曩+ ) ，瓦。( x ) 是 常數(shù)在每個(gè)小區(qū)間( 囊，扛+ 。) 內(nèi)任取一點(diǎn)t ，互一。( t ) 代表序列見( z ) ，見+ ( z ) ，p n ( x ) 在 ( 忍，囊+ ，) 中的變號(hào)數(shù)，則有變號(hào)數(shù)的序列 砭一。( 口) ，瓦一。( 粕) ，瓦一。( x o ，瓦一。( 矗) ，瓦呻( 6 ) 記，= 瓦一。( 一) 一瓦一療( 葺+ 。) ，于是 瓦一。( 口) 一瓦。( 6 ) = 瓦。( 口) 一瓦。( 而) + ，+ 五。( 霸) 一瓦一。( 6 ) 下面分析a ，和砭一。( 口) 一瓦叫( 而) ，瓦一什( ) 一瓦一。( 6 ) 首先分析i = 互叫( t ) 一疋一。( + 。) ，x t a ( h , ，紅+ 。) 變到( 磅小紅+ ：) 時(shí)k ( x ) 的變化情況 ( 1 ) 假設(shè)島( 曩+ 1 ) 0 由以( x ) = 吼一。( x ) 仇( 工) 知j j i + 。也不是見( x ) 的根，而是序列中某個(gè)乃( x ) 的根即 2 l p j ( h , + 1 ) = q j - ( 瑰+ 1 ) 仇( 吩+ 1 ) = 0 ( k + 1 ，刀一1 ) ， 貝t j q j i ( 曩+ 1 ) = o 由引理4 2 和定義2 5 知乃小l f h , + 1 ) q j + l ( 曩+ i ) 0 ，貝t l q j - k - 1 ( x ) ，q j - k + t ( x ) 在 ( 紅，j j l + 2 ) 沒有根，即x ( 繡，瑰+ ：) 時(shí)，劬一七- l ( x ) q j m l ( x ) o 因此，劬七l ( 五) ，乃一i ( 五) ，q j 小l ( 薯) 與劬- 七一l ( 一+ 1 ) ，q j i ( 五+ 1 ) ，q j 一( h i ) 都只有一個(gè)變號(hào)數(shù)根據(jù)( 4 4 ) 式，有 乃一i ( t ) = 劬一i - l ( 薯) 仇( 墨) ， 乃( 墨) = q j i ( 而) 見( 薯) ， ， 乃+ l ( t ) = q j i + l ( ) 仇( 薯) ， 乃一l ( 薯+ 1 ) = 留一h ( h o p t ( x , + 1 ) ， 1 5 ( x , + 1 ) = q j 一( 一+ 1 ) 以( 而+ i ) ， 乃+ l ( 五+ 1 ) = 乃礎(chǔ)+ - ( 墨卅) 見( 薯+ i ) ， 則乃一。( 薯) ，乃( 薯) ，乃+ ( 五) 與乃一( 薯+ 。) ，乃( t + 。) ，乃+ ，( 毛+ 。) 都只有一個(gè)變號(hào)數(shù)這說明x 從 f h , ，紅+ 。) 變到( 忽m 忽+ ：) 時(shí)，序列島一( x ) ，p a x ) ，乃+ 。( x ) 的變號(hào)數(shù)不改變 對(duì)于以( 工) ，珞+ 。( x ) ( 七g ，z 一1 ) ，如果以( 曩) 以+ t ( 紅) o ，那么段( x ) ，珞+ 。( x ) 在( 曩，魂+ 。) 的變號(hào)數(shù)與在( 吩小吩+ ：) 中的變號(hào)數(shù)是相同的 因此，當(dāng)p , f h , + 。) 0 時(shí)，總有瓦一。( 而) = 瓦一。( 毛+ 1 ) ( 2 ) 假設(shè)k ，是見( x ) 的根 根據(jù)見( x ) = q , , - k ( x ) 仇( x ) ，分兩種情況討論 ( 2 1 ) 仇( 忽+ 1 ) = o 且吼一i ( 7 l l + 1 ) o 若存在g f h , + 1 ) = 0 ( 0 歹 九一七) ，由引理4 2 和定義2 5 知鳥一l ( 曩+ 1 ) 乃+ l ( + 1 ) 0 ，則 g h ( x ) ，乃+ 。( x ) 在( 曩，囊+ ：) 沒有根，即z ( ，j j i + 2 ) 時(shí)，劬一。( x ) 乃+ 。( x ) 0 因此，劬一。( 葺) ，乃( t ) ， g ，+ l ( t ) 與g 川( + 。) ，乃( 札1 ) ，乃+ l ( 葺+ i ) 都只有一個(gè)變號(hào)數(shù)根據(jù)( 4 4 ) 式，有 乃+ i l ( t ) = 劬一- ( ) p i ( 五) j - - 西大掌碩士掌位論文 p j “( 五) = g ( ) p ( t ) ， 乃“+ l ( 薯) = q j + l ( t ) 風(fēng)( 薯) ， 乃+ t l ( + 1 ) = q j i ( 薯+ 1 ) p k ( t + 1 ) ， 所“( 薯+ t ) = 劬( 五+ 1 ) p t ( 五+ i ) ， 所+ i + t ( t + 1 ) = 劬+ l ( 五“) p i ( 毛+ 1 ) ， 則乃+ h “) ，乃“( _ ) ，乃m 。( 薯) 與乃“一t ( + 。) ，乃詘( 薯+ t ) ，乃m i ( 一+ 。) 都只有一個(gè)變號(hào)數(shù)這說 明x 從( 噍，吩+ 。) 變到( 忽小h i 4 ：) 時(shí)，序列乃小。( z ) ，乃+ t ( x ) ，乃m 。( x ) 的變號(hào)數(shù)不改變 對(duì)于島( 石) ，島+ 1 ( x ) ( 七g ，z 1 ) ，如果以( 如) 取+ t ( 吩) 0 ，那么段( x ) ，既+ 。( x ) 在( 紅，紅+ 1 ) 的變號(hào)數(shù)與在( 吩巾曩+ ：) 中的變號(hào)數(shù)是相同的 因此，當(dāng)仇( 曩+ 。) = 0 且吼一。( 忽+ ，) 0 時(shí)，總有瓦一。( t ) = 瓦。( 毛+ ，) ( 2 2 ) 吼以( 忽+ 1 ) = 0 首先分析從( 忽，吩+ 。) 到( 鬼+ p 紅+ ：) ，見一。( x ) ，見( x ) 的變號(hào)數(shù)變化情況 吼出( 曩+ i ) = o ，由引理4 2 和引理2 3 知吩+ l 是g 柑( x ) 關(guān)于g n - k - 1 ( x ) 的第1 類零點(diǎn)，也 是廣義第1 類根，則吼靠一。( j c ) ，g 樅( x ) 在( 吃，曩+ 。) 中有一個(gè)變號(hào)數(shù)，而在( 小吃+ ：) 中沒有變 號(hào)數(shù)根據(jù)( 4 4 ) 式，有 島一l ( 而) = 吼一i - l ( t ) 仇( 薯) ， 島( t ) = g 。一( ) 以( 薯) ， 見一l ( 葺+ 1 ) = 吼一i 一( 一+ ，) 仇( 誓+ 1 ) ， 島( t + 1 ) = 吼一t ( + 1 ) 見( 薯+ 1 ) ， 則n l ( 薯) ，島( 而) 只有一個(gè)變號(hào)數(shù)，見一。( 而+ 。) ，見( 薯+ ) 沒有變號(hào)數(shù) 接著分析從( 紅，紅+ 。) 到( 吃小紅+ ：) ，見( x ) ，見+ 。( x ) ，見一。( x ) 的變號(hào)數(shù)變化情況 g 柑( 曩+ 1 ) = o ，由引理4 2 和引理2 5 知g n - k - ! ( 口f + 1 ) o 若存在 遞歸算法及矗己j 明 日( 紅“) = 0 ( 1 9 j g n k 一2 ) ， 由定義2 5 知g 一( 魄+ 1 ) g 川( 魂+ 。) o ( g = z + 1 ，刀一1 ) 及( 4 5 ) 式可得 見+ l ( x ) = ( x 一吃+ 1 ) p a x ) ， b + 2 ( x ) = ( x 一吃+ 2 ) p z + i ( x ) 一e z + l 正+ l j 氣( x ) ， 島( z ) = o 一吃) 見一。( x ) 一巳一i z l n 一2 ( x ) 設(shè)q t ( x ) = x - b ：+ l ，則 見+ l ( x ) = q l ( x ) p ：( x ) ， 見+ 2 ( x ) = 一6 ：+ 2 ) 見+ l ( x ) - e z + l 六“p a x ) = ( x 一吃+ 2 ) g l ( x ) 見( x ) 一p 。l 正+ l 見( x ) 2 【( x 一6 ：+ 2 ) g l ( 功一巳+ i z + ?！恐? x ) 設(shè)9 2 ( 力= ( z 一吃+ 2 ) g 。( x ) 一巳+ l z + l ，貝u 廣西大掌碩士掌位淪文 遞歸算法及應(yīng)用 p ：+ 2 ( x ) = q 2 ( x ) p ：( x ) ， p z + 3 ( 功= o b z + 3 ) 見+ 2 ( x ) 一乞+ 2 z + 2 見+ l ( x ) = ( x - b ：+ 3 ) 9 2 ( x ) p a x ) 一巳+ 2 z + 2 吼( x ) 見( x ) 2 【( x 一吃+ 3 ) 9 2 ( x ) 一e z + 2 z + 2 q l ( x ) 】見( x ) 類似地，可以假設(shè)g ，( x ) ，吼一。( x ) 并推導(dǎo)出 設(shè)q o ( x ) = 1 ，由 q s ( x ) = ( x - - 吃+ 3 ) 9 2 ( x ) 一乞+ 2 f z + 2 9 l ( 功， 見+ 3 ( 功= q s ( x ) p z ( x ) ， 吼一：( x ) = o 一吃) g n - z - i ( x ) 一一l z l q - x - 2 ( 功， p a x ) = 吼q ( x ) p a x ) q o ( x ) = 1 ， 吼( x ) = x - b ：+ l ， q 2 ( x ) = o 一吃+ 2 ) g l ( x ) 一巳+ l 五+ l ， q n 一：(