递归算法及应用

分类号 UDC 硕士学位论文 密级 递归算法及应用 覃炜达 论文答辩El期 2Q!Q生§旦2窆旦学位授予Et期 ＼煳渊 · 。 广西大学学位论文原创性声明和学位论文使用授权说明 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相关 知识产权属广西大学所有．除已注明部分外，论文中不包含其他人已经发过的研究成果， 也不包含本人为获得其它学位而使用过的内容．对本文朐研究工作提供过重要帮助的个 人和集体，均已在论文中明确说明并致谢． ● 论文作者签名=重烯达 2DfD年6月／，日 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论支的规定．即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校提交学位论文的印刷本和电子版本； 学校有权保存学位论文的Ep,屙J本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文： 学校可以公布论文的部分或全部内容． 请选择发布时间： 口即时发布 口解密后发布 (保密论文需注明，并在解密后遵守此规定) 做⋯各獬蜘磁各P瑚铋．月／知 ， 。}IZ}。善^《“嚣。二、盛小“l艺。●lt萎掣罄譬嚣堑爵强罄l鬟 递归算法及应用 摘要 递归算法是求解矩阵特征值和奇异值的重要．它的实质是调用递归函数把问题 转化为规模缩小了的同类问题的子问题，然后再次调用递归函数来完成问题的求解．近 年来，一些学者(如Browne、Chandrasekaran等)给出了求解Hankel矩阵奇异值的快速 递归算法和求解Toeplitz矩阵奇异值的快速递归算法，并证明了递归算法仍适用于 Semiseparate矩阵特征值的求解． 本文首先在求解Toeplitz矩阵奇异值的快速递归算法的基础上，通过探讨Pascal 矩阵的结构，得到Pascal矩阵与向量相乘的快速算法，从而得到了求解Pascal矩阵奇异 值的快速递归算法：然后给出广义Jacobi矩阵的定义，在其顺序主子阵的特征值不满足 严格交织的条件下，证明了递归算法仍可以求解广义Jacobi矩阵的特征值．数值实验表明 算法是有效的． 关键词：分而治之法；快速傅里叶变换；二分法；变号数 RECURSIVEALGORITHMANDITSAPPLICATIoN ABSTRACT Therecursivealgorithmisanimportantwayforsolvingmatrixeigenvalueandsingular value．ItsessenceiStoreducethesizeoftheproblemintosub-problems．ofsimilarproblems byemployingtherecusivefunction,thenbyemployingtherecusivefunctionagain,we completetheproblems．IInrecentyears，someresearchershaveproposedafastrecursive algorithmforHankelmatricesandToeplitzmatrixSVD，suchasBrowne，Chandrasekaran, etc．，andtheyhaveprovedthattherecursivealgorithmisstillsuitabletosolvetheeigenvalue ofSemiseparatematrix． AccordingtothefastSVDrecursivealgorithmofToeplitzmatrix，wegetfastSVD recursivealgorithmofPascalmatrixbytakingadvantageofPascalstructure．Thenwegivethe definitionofthegeneralizedofJacobimatrix，andprovethattherecursivealgorithmisstill suitabletosolveitseigenvaluewithouttheconditionofstrictlyinterlace．Numerical． experimentsindicatethatthealgorithmiseffective． KEYWORDS：divideandconquermethod；fit；bisection；variablenumber 目 录 第一章引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．1 1．1递归算法的发展历史⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．1 1．2本文的工作⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．4 第二章定义与引理⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．6 第三章求解Pascal矩阵奇异值的快速分而治之法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯9 3．1求解矩阵奇异值的分而治之法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．9 3．2Pascal矩阵与向量乘积的快速算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．10 3．3数值试验⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．15 第四章求解广义Jacobi矩阵特征值的二分法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．16 4．1口类矩阵⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯16 4．2∥类矩阵⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．19 4．3“一个零’’广义Jacobi矩阵⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯25 4．4“q个零”广义Jacobi矩阵⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．27 4．5算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯30 4．6数值试验⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯——⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯32 第五章结论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯33 参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯34 致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．37 攻读学位期间发表论文情况⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯38 劫}归算法及压U嗣 第一章引言 1．1递归算法的发展历史 矩阵的特征值和奇异值在结构振动等方面有着重要的应用【3】．求解矩阵特征值和奇 异值的方法有很多，如twistedmethod[11-13]、QRmethod[1舢161、JacobimethodB7-23]、 Davidsonmethod[24-301． 递归算法也是求解矩阵特征值和奇异值的重要方法【I-3】．它在区间上表现为区间分 半法，即二分法：在矩阵上表现为矩阵分半法，即分而治之法． 1967年，W．Barth[29】首次给出求解不可约对称三对角矩阵特征值的二分法．1997 年，Trefethen[21年提出使二分法有效的性质．2006年，陆金甫嗍再次详细地介绍了该性质， 并指出二分法是求解矩阵部分特征值的标准算法． 设n阶矩阵R的k阶顺序主子阵R。的特征值为五，五，⋯，五，k+l阶顺序主子阵冠+1 的特征值为鸬，鲍，．．．，版小使二分法有效的关键性质是这些特征值是严格交织的，即对于 k=1，2，．．．，n-1，不等式／4<^<鸬<五<鸬<⋯<以<五<段+l成立，见文献[4]第196 页． 根据特征根的严格交织性质，文献[3]给出求解Jacobi矩阵特征值的二分法原理． 设po(x)=O，记vn(X)是Jacobi矩阵特征多项式序列风O)，A(x)，⋯，见@)的变号数， 给定口，b，如果岛(口)≠0，岛(6)≠O，那么vn(a)-v．(b)等于见(z)在xvf日-1[a，b】上根的个数． 1981年，J．M．Cuppen【l'321给出求解对称三对角矩阵 F= 岛q 0 q 如 ‘． 。． ’ en—l 0 ％一I 玩 特征值的分而治之法，该算法主要有两步，分别是DivideMethod和ConquerMethod，它们 的原理如下． DivideMethod： 广西大学硕士学位论文 递归算法及应用 设 互= peR，pe=b肘，《帕= 6l q el 2j2 O 0 ％一I 6卅 ，露’= ，最= 肛斟， k+l％“0 ％+l吒+2。． 。· 。· ％一1 0 巳．1 ‰ 其中，瓦=吒m石=瓦+1-P82"于是，n瞄廿∥r矗五也是对称三对角矩 阵，可以继续进行矩阵分半． ． ConquerMethod： 设Q，Q2分别是鼻和E的特征向量矩阵，对角矩阵彤和吸分别是巧和最的特征值 蹴舭=瞄跏倒，墨玎鼽拖=一廿州，对角觯 肚陌甜脚摊s舯出allk-one1210difieddiag。nalmatrix，关于它的特征 分解参见文献【32，33，34，35，36，37，38]．设它的特征分解为W+pzz7’=JGJr，则F的特征分 ⋯=噼刖G噼荆撕删一腿一⋯⋯阵G 和特征向量矩阵噼斗)【8，9’10邓6】，oiviae觚aco—Me怕d的运算量删柳． 2004年，Chandrasekaran【lo】给出求解Semiseo撒ble矩阵 D= c2吐 c2畋 c2以 c2以 c3dl c3d2 特征值的分而治之法．2008年，WeiXu140]给出求解对称五对角矩阵 2 盔吐； 西 “靠 靠 递归算法及应用 R== 特征值的分而治之法． 运用分而治之法求解任何m×靠矩阵P的奇异值分两步【l一．首先把P化为双对角矩 阵B：根据定义，P的奇异值等于对称三对角矩阵BTB的特征值，然后运用分而治之法求 解BTB的特征值．在算法中占用时间最多的运算步骤是mx玎矩阵P与刀维向量相乘． 2008年，KevmBrowen证明了肌×挖Hankel矩阵 和聊×刀T0印litz矩阵 H= R=： 曩 红 缟 ⋯ ％ 红 呜 钆 ⋯吃+。 玛 ％ 旭 ⋯％+： ● ● ● ● ● ● ％ 吃引 ％+： ⋯吃剃 ● ● ● ● ● ● ● ● ● ● ‰％+t％+z⋯吃+川 ％ ‰+1 ‘ ，：l+1 吩 ，=l 吃 吩 ‘ 呢 ⋯ ，卅+n ⋯‰ ⋯，：l+2 ⋯，：，+1 ⋯ ％ 与刀维向量乘积的快速算法，从而我们可以得到求解Hankel矩阵和T0印1池矩阵奇异值的 快速分而治之法，见文献【6】． 2 2 k．：k．：吒五吩 递归算法及应用 1．2本文的工作 本文将解决递归算法的两个问题． 第一个问题：由于对称正定性，r／x刀Pascal矩阵P的Cholesky分解总是存在的， P=彬．相对于刀×胛矩阵与，?维向量x直接相乘的运算量O(n2)，通过FFT(快速傅里叶变 换)，厶的运算量是D(力109即)，则Px的运算7量是O(nlogn)【5】．当使用分而治之法求解矩阵 的奇异值时，占用时间最多的运算步骤是矩阵与向量相乘．当m>以时，mxr／Pascal矩阵 不存在Cholesky分解，我们仍可以给出求解m×nPascal矩阵奇异值的快速分而治之法．· 第二个问题：在Jacobi矩阵的基础上给出一个新的矩阵，我们称之为广义Jacobi矩阵， 在其顺序主子阵的特征值不满足严格交织的条件下，我们证明了二分法仍可以求解广义 Jacobi矩阵的特征值． 设ei，包，Z都是实数， R= 2jI石0 q 如 ’． ‘． ‘． 五一。 0 ％．1 吃 如果色，Z≥0，则称R为广义Jacobi矩阵． 设R的七阶顺序主子阵为Rt，则R，=岛，R。=R．设R。的特征多项式为放(x)，则 4 递归算法及应用 见(力=det(订一冠) x一岛 一q O 一石 x一乞 =(x一魄)见一l(x)+五一l =(X--瓯)见一1(x)一吼一1五一l 吖 工一62 X一6l —q O =@一钆)仇一l(x)一气一l五一l仇一2(x)． “ 戈一么 令Po(X)=1，根据(1．1)式，k=2，3，⋯，n，有 x一6七一l 0 见(x)=O一玩)见一l(z)一‰一l以一l仇一2@)． 根据广义Jacobi矩阵的定义，存在，使得白石=O．由(1．2)式，有 易+l(x)=(X--6f+1)pAx)， (1．2)． 则乃@)和A+。(x)的根不是严格交织的，本文将证明二分法仍适用求解它的特征值． 5 oo 叫卜呐， o o X ． 递归算法及矗U啊 第二章定义与引理 根据mxnHankel矩阵和mxnToeplitz矩阵的定义，在mxmPascal方阵的基础上， 我们给出川×拧Pascal矩阵的定义．其中，m>聆． 定义2．1mxnPascal矩阵P=(仍，，)的定义如下： ’ A。．，=锱-2． 其中，q=南． 例如，6x5Pascal矩阵 P== l 1 1 l 1 1 2 3 4 5 1 3 6 10 15 l 4 1020 35 1 5 15 35 70 1 6 2156126 定义2．2‘51nxn-F--角Pascal矩阵L=(‘，／)定义如下： 定义2．3【51实数列 口o，口1，⋯，am一2，am一1，％ (2．1) (2．2) 且口o≠0，am≠0，从左到右，如果at—lq<0，即q与q—l符号相反，则为有一个变号数，如 果q=0，aj一。口j¨<0，也为有一个变号数，序列中的变号数的总和称为该序列的变号数． 为了证明的需要，在第一类零点的基础上，我们给出广义第1类根的定义． 定义2．4如果实数而是fo(x)的一个根，并且存在一个正数s，使得对任意 6 纷 挖<一V|鲥q．，，．卜 VI Vl嘴o，●●●r1【 = √‘ 广西大掌硕士学位论文 Vxe(xo—s，xo)，有五(x)Z(x)<0，而对协∈(xo，xo+s)，有石(力石(z)>o，则称而为厶(曲 关于石(x)的广义第1类根．如果存在一个正数s，使得对№∈(‰一s，xo)，有^(x)彳(x)>o， 而对坛∈(xo，而+F)，有兀(x)彳(x)O或五@)彳(x)0，则称R为Jaeobi矩阵． 设R的k阶顺序主子阵R七的特征多项式为pax)．令风(功=1，根据(1．1)式，对 k=2，3，⋯，n，有 pax)=O-b,)pHO)一e¨五一lPt一2(D(ek-l，五一l>o)．(2．3) 满足(2．3)式的序列po(X)，Pl(x)，．．．，Pn—I(x)，以(x)称为Jaeobi矩阵特征多项式序列．若 A(护)=0(1≤f≤刀一1)，由(2．3)式，B+。(目)=飞ZB—l(p)，那么易一1(秒)B+l(D0(i=l，⋯，k-1)，则称只 为口类矩阵． 设R的J阶顺序主子阵Rj的特征多项式为pj(x)．令Po(x)=l，根据(1．1)式，对 J=2，3，⋯，玎，有 pj(x)=@一乞)马一l(x)-ej—l乃一lPj一2(x)． (4．1) ·．‘qZ>O(f=1，⋯，k-1)，由(4．1)式和定义2．5知po(x)，A(x)，．．．，仇(x)是Jacobi矩阵顺序 主子阵的特征多项式序列．·．。qZ=oq=尼，⋯，以一1)，根据(4．1)式，有 见+I(x)=(x-b,+I)见(x)， 以一l(x)=O-b．一1)岛一2(力， 16 广西大掌硕士学位论文 递归算法及窟己J书 店(x)=O一吃)以一l(力， (4．2) 一 ～’ ‘ 则 见(x)=(x一玩+。)(z一瓯+2)⋯(x一吃)见(x)． 设S。(X)是序列po(x)，pl(力，．．．，见(x)的变号数，K(X)是序列po(X)，A(x)，．．．，pk(x)的 变号数，k(X)是序列仇0)，风+。(x)，．．．，以(x)的变号数，则S。(x)=vk(X)+1k(妁． 引理4．1给定a，b，如果Pn(a)≠0，见(6)≠0，那么最(口)一最(6)是见(x)在区间[口，b】 中根的个数． 证明 最(口)一最(6)=圪(口)+瓦一七0)一(圪(6)+乙一。(6)) =Vk(a)-Vk(b)+(T．一I(口)一乙一I(6))． ·．‘见(z)=(x一玩+1)(x一吮+2)⋯(x一吃)见(x)，Pn(a)≠0，见(6)≠0，．‘．见(口)≠0，Pk(b)≠0． po(X)，Pl(x)，．．．，pax)是Jacobi矩阵的特征多项式序列，设c是见(x)在区间【口，6】中根的 个数，由引理2．4知VAa)一Vk(b)=c．假设刀一七个数％小玩+2，⋯，吃有h个在【口，纠中，由 磊(x)=(x一玩+I)(x一玩+2)⋯(x—b．)pAx) 知，在[口，6】中，见(x)I七pk(x)多h个根．故只需证明砭一。(口)一瓦一。(6)=厅成立． Pk(x)，Pk+．(x)，．．．，以(x)在【口，6]内的所有根由小到大排列成 h．，坞，．．．，％_．，k 令％=口，九“=6，那么在区间【口，6】中有历+1个不相交的小区间 (％，啊)，(啊，鸭)，⋯，(‰，k+。)． 在每个小区间(扛，曩+，)中，序列中的每个多项式乃(x)都不变号，即x∈(吩，忍+。)，t一。(x)是 常数．在每个小区间(吩，羁+，)内任取一点而，瓦叫(墨)代表序列见(x)，见+。(x)，．．．，见O)在 (囊，曩+．)中的变号数，则有变号数的序列 瓦一。(口)，瓦一。(而)，瓦一。瓴)，⋯，瓦一。(■)，瓦一。p)． 记△，=瓦州(薯)一五一。(t+1)，于是 17 广西大学硕士学位’．企文 m-I 瓦一。Ca)一瓦。(6)=瓦。(口)一露。(嘞)+∑△，+瓦一。(xA-r,一。(6)． 下面分析△，和瓦一。(a)一瓦一。(Xo)，互一。(‰)一瓦一。(6)． 首先分析△j=互一。(t)一瓦吲(五+，)，且PxI．A(h,，瑰+。)变到(曩小吩+：)时瓦咀(x)的变化情况． 由(4．2)式知每个7jl+。都是见(x)的根，根据pAx)=(x-b,+，)@一‰+：)⋯(x-bAp。(x)分两种 情况讨论． (1)如果既(％+。)=0且红+，≠玩“，．．．，吃4，％． 由(4．2)式知，^+，也是Pk+，(x)，．．．，Pn一。o)，n(x)的根．由易O)A“@)=O一岛+，)p；(功 (1=lqk+l，⋯,n-1)知，口j+l是以(x)关于见一t(x)广义第3类根，⋯，Pn—l(x)关于n一2(x)f-Y． 第3类根，鼽+，(曲关于仇(x)广义第3类根，则仇+。(五)，．．．，以一．瓴)，见“)的变号数与在 见+。(玉+1)，．．．，磊一l(工i+1)，pn(X,+1)的变号数相同． 因此，当见(曩+．)=O且曩+。≠仇+¨⋯，既_1，吃时，总有r(毛)=丁(而+。)． (2)如果岛+。=以(七+1≤，．≤拧)，即6，∈{钆+。，钆+2，⋯，玩}． 由所一。(x)刃(x)=@一6，)p二(功知，口j+。是B(x)关于B一。o)的广义第1类根·在 (魂，^+。)中，所一。(x)，只(z)有一个变号数，而在(曩+p纵2)中没有变号数．对于 吃∈{玩+l，钆+2，⋯，色)(七+1≤g≤刀)且6譬≠红+l=啡， 由岛一。(x)以(功=o一69)p乙(x)知，囊“是段(功关于以一t(x)的广义第3类根，则 珞一。(功，硌(功在(％，曩+-)与(曩+pJjI+z)中变号数相同． 因此，当鸭+l=4(七+1≤，．≤刀)时，h，=瓦-打(一)一瓦一。(薯+1)等于6，个数． m-I 在【口，6】中，6，总的个数是h．综合(1)和(2)分析，∑A；=|}z． 现在分析瓦叫(口)一互一。(而)和瓦．。(xD一瓦一。(扫)． 因为口不是A(x)的根，由(4．2)式知口也不是见+。(x)，．．．，岛一。(x)，见(x)的根．对于 18 广西大掌硕士掌位论文 递归算法及应用 pAx)p,“(x)=(x一岛+。)p；(x)(1-l【，k+1，⋯，n一1)， 如果口=％不是它们的根，那么pax)，所+。(x)在口的变号数与在(％，囊)中的变号数相同，即 仇“(x)，．．．，n_(x)，n(x)在口的变号数与在(‰，Illl)中的变号数相同，则瓦一。(口)一五一。(‰)20· 同理可证互嘲(‰)一瓦一。(6)=0，则瓦一厅(口)一互叫(6)2h． 4．2∥类矩阵 设岛，岛，Z都是实数，R= 石0 如 ’． 。． 。． Z—l ％一l 吮 如果只存在一个正整数七(1≤k≤万一1)使得％以=O且白彳>o(，≠七)，则称R为∥类矩阵． 设R的f阶顺序主子阵R的特征多项式为pax)．令岛(x)=1，根据(1．1)式，对 i=2，3，⋯，刀，有 A(x)=0—6：『)A一。(力一岛一。Z一，刃一。(功． (4．3) ·．·e,g>o(，=l，2，⋯，k-1)，由(4．3)式和定义2．5知，风(x)，Pl(力，．．·，见(功是Jacobi矩阵顺 序主子阵的特征多项式序列．·．。％五=0，根据(4．3)式，有 仇+l(x)=(x一瓯+1)pt(x)， 仇+2(x)=(x一玩+2)n+l(x)一咯+l五+lpax)， pax)=(x一吃)见一l(x)一％一lZ—l见一2(x)． 设91(x)=x一‰+l，则 见+l(x)=gl(x)见(x)， A+2(x)=(x一瓯+2)pI+l(x)-ek+l五+lP々(x) =(x-t,+2)gl(x)仇(x)一气+l以+l见(x) 19 广西大学硕士掌位论文 递归算法及应用 =[(x一瓯+2)gl(x)一ek+l五+I]pk(x)． 设92(z)=(x一钆+2)ql(x)-ek+l以“，贝Ij 仇+2(x)=92(x)仇(x)， 仇+3(x)=@一钆+3)办+2(x)-ek+2五+2A+I(x) =(x一瓯+3)92(x)pAx)一ek+2五+2qi(x)Pk(X) 2[(x一％+3)92(z)一气+2五+2qI(x)】j％(x)． 类似地，可以假设qs(x)，．．．，qn一。(z)并推导出 qs(x)=(x一玩+3)92(x)一ek+2五+2qI(x)， 见+3(石)=qs(x)pAx)， 吼一I@)=O一吃)吼一¨(工)一％一IZ—lqn-k-2(x)， 见(x)=qn一七(x)pAx)． 引理4．2设qo(x)=1，则90(x)，ql(x)，q2(x)9oo011吼★一l(x)，qn一七(x)是Jacobi矩阵特征多项 式序列． 证明 由 qo(x)=1， ql(x)=x一反+l， 92(x)=(x一玩+2)gI(功一％+l以+l， 吼一々(x)=(x—b．)qn—I．1(x)一％一lZ—lqn-k-2(x) 及定义2．5可知qo(x)，gl(x)，q2(x)，．．．，qn-k-t(x)，qn—t(x)是Jacobi矩阵的特征多项式序列． 设S。(x)是序列po(X)，A(力，．．．，Pn(X)的变号数，K(X)是序列Po(X)，A(x)，．．．，见(x)的 变号数，k(X)是序列pax)，Pk+。(x)，．．．，见(x)的变号数，则S。(x)=Vk(x)+Tkm(x)． 广西大学硕士掌位论文 引理4．3给定a,b，如果见(口)≠0，见(6)≠0，那么瓯(口)一瓯(6)等于见(x)在区间 【a,b】中根的个数． 证明 最(口)一最(6)=圪(口)+乙一I(口)一(圪(6)+乙一I(6)) =圪(口)一圪(6)+(巧廿(口)一乙吐(6))． ．．’见(口)≠0，以(6)≠0，见(x)=吼一七(x)pk(x)，．．．见(口)≠0，Pk(b)≠0．po(X)，A(x)，．．．，见(x) 是Jaeobi矩阵的特征多项式序列，设c是AO)在区间[a，b]中根的个数，由引理2．4知 圪(口)一K(6)=c．假设靠一。(x)有h个根在【口，6】中，由pax)=吼一I(x)仇(x)知，在[a,b】 中，见(z)Pk(x)多办个根．故只需证明乏。(口)一瓦。(6)=办成立． 把pax)，A+，(x)，．．．，Pn(X)在【口，b】内的所有根由小到大排列成 h，，心，．．．，k_，k． 令ho=口，吃+。=6，那么在区间【口，b】中有m+1个不相交的小区间 (％，魄)，(啊，红)，⋯，Ch．，‰+．)． 在每个小区间(曩，吩+，)中，序列中的每个多项式乃(力都不变号，即x∈(忽，曩+．)，瓦。(x)是 常数．在每个小区间(囊，扛+。)内任取一点t，互一。(t)代表序列见(z)，见+．(z)，．．．，pn(X)在 (忍，囊+，)中的变号数，则有变号数的序列 砭一。(口)，瓦一。(粕)，瓦一。(xO，⋯，瓦一。(矗)，瓦呻(6)． 记△，=瓦一。(一)一瓦一疗(葺+。)，于是 瓦一。(口)一瓦。(6)=瓦。(口)一瓦．。(而)+∑△，+五。(霸)一瓦一。(6)． 下面分析A，和砭一。(口)一瓦叫(而)，瓦一什(‰)一瓦一。(6)． 首先分析△I=互叫(t)一疋一。(‘+。)，xtA(h,，红+。)变到(磅小红+：)时k(X)的变化情况． (1)假设岛(曩+1)≠0． 由以(x)=吼一。(x)仇(工)知JjI+。也不是见(x)的根，而是序列中某个乃(x)的根．即 2l pj(h,+1)=qj-(瑰+1)仇(吩+1)=0(k+1≤，≤刀一1)， 贝．tJqj—I(曩+1)=O．由引理4．2和定义2．5知乃小lfh,+1)qj^+l(曩+I)<0，．贝tlqj-k-1(x)，qj-k+t(x)在 (红，Jjl+2)没有根，即x∈(绣，瑰+：)时，劬一七-l(x)qjml(x)O(k≠，)，则称 R为“一个零’’广义Jacobi矩阵． 设R的i阶顺序主子阵置的特征多项式为见(曲．令po(X)=l，根据(1．1)式，对 f-2，3，⋯，挖，有 只(x)=@一6f)只一I(曲一q—l丘117,一。(力． (4．5) 由(4．5)式知pax)，A(x)，．．．，见(x)是口类矩阵的特征多项式序列． 由％‘>o(g=z+1，⋯，刀一1)及(4．5)式可得 见+l(x)=(x一吃+1)pAx)， B+2(x)=(x一吃+2)Pz+I(x)一ez+l正+lj气(x)， 岛(z)=O一吃)见一。(x)一巳一IZ—ln一2(x)． 设qt(x)=x-b：+l，则 见+l(x)=ql(x)p：(x)， 见+2(x)=@一6：+2)见+l(x)-ez+l六“pax) =(x一吃+2)gl(x)见(x)一P。l正+l见(x) 2【(x一6：+2)gl(功一巳+IZ+。】只(x)． 设92(力=(z一吃+2)g。(x)一巳+lZ+l，贝U 广西大掌硕士掌位‘沦文 递归算法及应用 P：+2(x)=q2(x)p：(x)， Pz+3(功=O—bz+3)见+2(x)一乞+2Z+2见+l(x) =(x-b：+3)92(x)pAx)一巳+2Z+2吼(x)见(x) 2【(x一吃+3)92(x)一ez+2Z+2ql(x)】见(x)． 类似地，可以假设g，(x)，．．．，吼一。(x)并推导出 设qo(x)=1，由 qs(x)=(X--吃+3)92(x)一乞+2fz+29l(功， 见+3(功=qs(x)pz(x)， 吼一：(x)=O一吃)gn-z-I(x)一％一lZ—lq．-x-2(功， pax)=吼q(x)pAx)． qo(X)=1， 吼(x)=x-b：+l， q2(X)=O一吃+2)gl(x)一巳+l五+l， qn一：(x)=(X,--瓦)吼一：一l(x)一巳一lZ一1qn-z'-2(x) 及定义2．5可知留o(力，g。(x)，q2(x)，．．．，qn-z-I(x)，g一(x)是Jacobi矩阵的特征多项式序列． 设S。(X)是序YOto(X)，P。(x)，．．．，岛(x)的变号数，圪(X)是序列风(x)，A(x)，．．．，见(z)的变 号数，乙(X)是序列B(x)，Pz+l(x)，．．．，以(x)的变号数．则S。(X)_、，z(x)+1二(x)． 引理4．4给定口，b，如果pAa)≠0，磊(6)≠0，那么瓯(口)一瓯(6)等于见(力在区间 【a,b]中根的个数． 证明 最(口)一瓯(6)=圪(口)+正。0)一(圪(6)+t一。(6)) =Vz(a)一形(6)+(互一。(口)一Z一。(6))． ·．‘见(口)≠0，以(6)≠0，pax)=吼一：(x)见(x)，．．．见0)≠0，岛(6)≠0．po(x)，AO)，．．．，pax)是 Jacobi矩阵的特征多项式序列，设c是pax)在区间[a，b]中根的个数，由引理4．1知， 圪(口)一圪(6)=c．假设吼一：(x)在【口，明中有h个根，由pax)=吼一：(x)pAx)知，在【口，6】 中，见@)比p：(x)多h个根．故只需根据证明t一。(口)一t一。(6)=h成立．证明过程与引理4．3 类似。 4．4“g个零”广义Jacobi矩阵 设乞，岛，Z都是实数， R= 2jI 石 eI％ O 0 。． 五一。