（运筹学与控制论专业论文）fir数字滤波器的约束chebyshev设计理论与算法.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：盘整查 日期：趔：点：! 竺 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名： 导师签名：赶丝圣日期：婴：墨1 7 擎 起 山东大学硕士学位论文 f ir 数字滤波器的约束c h e b y s h e v 设计理论与算法 摘要 本文主要讨论和研究了f i r 数字滤波器的频域约束c h e b y s h e v 设计问题，包括线性 相位f i r 数字滤波器的等式不等式约束c h e b y s h e v 设计和复系数f i r 数字滤波器的不等 式约束c h e b y s h e v 设计众所周知，r e m e z 算法是一种高效的解决c h e b y s h e v 逼近问题的 数值算法，它的理论基础是交错点组定理( 见附录) m c c l e l l a n 和p a r k s 在文献 6 ，9 中 设计出了一个基于r e m e z 算法的计算机程序m c c l e l l a n p a r k s ( m p ) 程序一用于解决线性 相位f i r 数字滤波器的c h e b y s h e v 设计问题，这一工作取得很大的成功，也使得 c h e b y s h e v 误差指标在滤波器设计中被广泛使用但是对于约束c h e b y s h e v 逼近问题， r e m e z 算法是不能解决的，故而人们试用其它方法解决f i r 数字滤波器的约束c h e b y s h e v 设计问题，但是，效果并不十分理想 r e m e z 算法之所以有很高的效率，是因为它是根据交错点组定理中对c h e b y s h e v 逼 近问题最优解的特性的描述而设计的基于这种思想，本文首先对带不等式约束的 c h e b y s h e v 逼近问题进行了研究，并把交错点组定理扩展到这类问题，然后根据此扩展 定理设计了两个算法来求解线性相位f i r 数字滤波器的不等式约束c h e b y s h e v 设计问题 由于这两种算法是根据约束c h e b y s h e v 逼近问题最优解的特性来设计的，所以和r e m z e 算法一样有很高的效率，优于现有的其它方法，并且如果问题的解存在则保证收敛到此 解而后，文章进一步地把交错点组定理扩展到同时带等式不等式约束的c h e b y s h e v 逼 近问题，再以此为理论基础设计算法解决线性相位f i r 数字滤波器的等式不等式约束 c h e b y s h e v 设计问题 由于复数域的c h e b y s h e v 逼近问题最优解的特性不能被确切的描述，所以复系数 f i r 滤波器的c h e b y s h e v 设计问题是滤波器设计中的一个难题l j k a r a m 和m c c l e l l a n 在文献 2 0 中把交错点组定理扩展到复数域，并提出了求解复系数f i r 滤波器的复 r e m e z 算法，但由于此扩展定理只是一个充分条件，所以此算法不能保证得到最优解 在文献 2 3 中，他们对复r e m e z 算法进行了完善，使其收敛到最优解本文把文献 2 0 中的复数域交错点组定理扩展到有不等式约束的情况，以此定理为基础并结合复r e m e z 算法和赖晓平在文献 3 0 中提出的迭代r e m e z 算法，设计了一种有效的算法来解决带不 等式约束的复系数f i r 数字滤波器的c h e b y s h e v 设计问题 基金项目国家自然科学基金项目( 6 0 2 7 5 0 0 6 ) 山东，肯自然科学基金项目( y 2 0 0 i g 0 8 ) 山东大学硕士学位论文 文中通过设计实例用m a t l a b 对上述各算法进行仿真并与现有的其它方法做了比较 仿真和比较结果说明本文提出的算法兼具稳定性和高效性 关键词：f i r 数字滤波器，c h e b y s h e v 设计指标，r e m e z 算法，交错点组定理 t h e o rle sa n da l g o rit h m sf o rt h eo o n s t r aln e do h e b y s h e v d e s i g no ff l rd l g l t a lf l l t e r s a b s t r c t i nt h i sp a p e r ，t h ec h e b y s h e vd e s i g np r o b l e m so ff i rd i g i t a lf i l t e r sw i t h f r e q u e n c yc o n s t r a i n sa r ec o n s i d e r e d ，i n c l u d i n gt h ec h e b y s h e vd e s i g no fl i n e a r p h a s e f i rd i g i t a lf i l t e r sw i t h e q u a l i t y a n d i n e q u a l i t yc o n s t r a i n s ，a n d t h e c b e b y s h e vd e s i g no fc o m p l e xf i rd i g i t a lf i l t e r sw i t hi n e q u a l i t yc o n s t r a i n s i t i sw e l lk n o w nt h a tt h ea l t e r n a t i o nt h e o r e mi st h eb a s i so ft h er e m e za l g e r i t h m ， w h i c hi sa ne f f i c i e n tc h e b y s h e va p p r o x i m a t i o na l g o r i t h m a n dt h ec o m p u t e rp r o g r a m b a s e do nt h er e m e za l g o r i t h m ，m pp r o g r a m ，m a d eb ym c c l e l f a na n dp a r k s iss o e x c e l l e n tf o rs o l v i n gt h ec h e b y s h e vd e s i g np r o b l e m so fl i n e a rp h a s ef i rf i l t e r s t h a tt h ec h e b y s h e ve r r o rn o r mi sw i i d l yu s e df o rf i rf i l t e rd e s i g n h o w e v e r ，t h e c h e b y s h e va p p r o x i m a t i o np r o b l e mw i t h c o n s t r a i n s c a n tb es o l v e db yt h er e m e z a l g o r i t h m a l t h o u g hs o m eo t h e rw a y sw e r ep r o p o s e dt of i n dt h es o l u t i o no ft h i s p r o b l e m ，b u tt h e i re f f e c t i v e n e s si s n tg o o de n o u g h t h er e a s o nw h yt h er e m e za l g o r i t h mi sh i g h l ye f f i c i e n ti st h a ti tw a sd e v i s e d o nt h eb a s i so ft h ep r o p e r t yo ft h eo p t i m a ls o l u t i o nd e s c r i b e di nt h ea l t e r n a t i o n t h e o r e m b a s e do nt h i st h o u g h t ，i nt h i st h e s i s ，t h ea l t e r n a t i o nt h e o r e mi sf i r s t e x t e n d e dt ot h ec h e b y s h e va p p r o x i m a t i o np r o b l e m sw i t hi n e q u a l i t yc o n s t r a i n t s ， a n dt h e nt w oa l g o r i t h m sa r ed e v i s e df o rd e s i g n i n g1 i n e a rp h a s ef i rf i l t e r sw i t h i n e q u a l i t yc o n s t r a i n t s i nc h e b y s h e vs e n s ea c c o r d i n gt ot h ee x t e n d e dt h e o r e m b e c a u s et h et w oa l g o r i t h m sp r o p o s e da r ed e v i s e di nl i n ew i t ht h ep r o p e r t yo ft h e o p t i m a l s o l u t i o no ft h e p r o b l e m a st h er e m e za l g o r i t h m ，t h e yh a v eh i g h e r e f f i c i e n c yt h a no t h e re x i s t i n gm e a n s a n di ft h eo p t i m a l s o l u t i o ne x i s t s ，t h e t w oa l g o r i t h m sa r e g u a r a n t e e dt oc o n v e r g e t oi t a f t e rt h a t ，t h ea l t e r n a t i o n t h e o r e mi se x t e n d e dt ot h ec h e b y s h e va p p r o x i m a t i o np r o b l e mw i t he q u a l i t ya n d 2 山东大学硕士学位论文 i n e q u a l i t yc o n s t r a i n t s ，a n da l g o r i t h mb a s e do nt h i se x t e n d e dt h e o r e mis d e v i s e d f o rd e s i g n i n gl i n e a rf i rf i i t e r sw i t he q u a l i t ya n di n e q u a l i t yc o n s t r a i n t s i n c h e b y s h e vs e n s e s i n c et h ep r o p e r t yo fo p t i m a ls o l u t i o no fc o m p l e xc h e b y s h e va p p r o x i m a t i o n p r o b l e mc a n t b ed e p i c t e de x a c t l y ，t h ec h e b y s h e vd e s i g no fc o m p l e xf i rf i l t e r s i sam u c hd i f f i c u l tp r o b l e mi nt h ef i e l do ff i l t e rd e s i g n k a r a ma n dm c c l e l l a n e x t e n d e dt h ea l t e r n a t i o nt h e o r e mt ot h ec o m p l e xc a s ei nr e f 2 0 ，a n dp r o p o s e d t h ec o m p l e xr e m e za l g o r i t h mt os o l v et h i sp r o b l e m b u tt h ee x t e n d e dt h e o r e mi s o n l yas u f f i c i e n tc o n d i t i o na n dt h ea l g o r i t h mo n l yg a i n sas u b o p t i m a ls o l u t i o n i nr e f 2 3 ，k a r a ma n dm c c l e l l a nc o m p l e m e n t e dt h e i ra l g o r i t h ms u c ht h a to p t i m a l s o l u t i o nc a nb eg a i n e d i nt h i st h e s i s ，t h ec o m p l e xa l t e r n a t i o nt h e o r e mi nr e f ， 2 0 i se x t e n d e dt ot h ec a s e w i t hi n e q u a l i t yc o n s t r a i n t s ，a n dc o m b i n i n g t h e i t e r a t i r er e m e za l g o r i t h mp r o p o s e di nr e f 3 0 b yx a i p i n gl a i ，an e wa l g o r i t h m i sd r o p o s e dt os o l v et h ec h e b y s h e vd e s i g np r o b l e mo fc o m p l e xf i r f i i t e r sw i t h i n e q u a l i t yc o n s t r a i n t s i ft h ep r o b l e ms o l u t i o ne x i s t s ，t h ea l g o r i t h mc o n v e r g e s t ot h es o l u t i o n ， s o m ed e s i g ne x a m p l e sa r ep r e s e n t e dt o i l l u s t r a t et h ep e r f o r m a n c eo ft h o s e p r o p o s e da lg o r it h m s k e yw o r d s ：f i rd i g i t a lf i l t e r ，c h e b y s h e v e r r o rn o r m ，r e m e za l g o r i t h m ，t h e a l t e r n a t i o nt h e o r e m 符号说明：本文中，1 1 1 1 表示范数，m i n m a x 表示极小化最大值，r e 【】表示复数的实 部，h n 【】表示复数的虚部，a r g ) 表示复数的相角 山东大学硕士学位论文 第一节前言 数字滤波器的设计问题是数字信号处理中的基本问题，近3 0 年来，由于数字信号系 统的广泛应用，而受到人们越来越多的关注根据结构的不同，数字滤波器分为无限冲 击响应( i i r ) 数字滤波器和有限冲击响应( f i r ) 数字滤波器，其中，由于有限冲击响应 ( f i r ) 数字滤波器总是稳定的，而且可以做到严格的线性相位，故丽人们对它进行了大 量而深入的研究f i r 数字滤波器的设计指标通常有最小二乘指标，c h e b y s h e v 指标，l ， 指标及混和指标等因为最小二乘指标设计简单，c h e b y s h e v 指标物理意义明确，所以 此两种指标最常用7 0 年代m c c l e l l a n 和p a r k s 在 6 ，9 中设计出的基于r e m e z 算法的计 算机程序一m c c l e l l a n p a r k s ( m p ) 程序一能高效地解决线性相位f i r 数字滤波器的 c h e b y s h e v 设计问题，这也使得c h e b y s h e v 误差标准在f i r 滤波器的设计中被更多的采 用 随着数字信号系统的大量运用及数字信号处理技术的不断发展，人们对数字滤波器 的要求也越来越多样化比如在通讯系统中要求尽量减小阻带能量，在图象处理中要求 保持信号的直流分量不变，在许多场合下都要求去掉5 0 h z 的电源干扰信号，而为达到这 些目的就需要在滤波器的设计中加入各种约束但是，r e m e z 算法并不能直接约束 c h e b y s h e v 逼近问题，为此本文在第二节首先讨论了在频域加入不等式约束的f i r 数字 滤波器的c h e b y s h e v 设计问题对于这一类经典问题，已有许多人做了大量工作 l r r a b if i e f 和k s t e i g l i t z 曾用线性规划算法 7 1 7 求解此问题，但是所需计算量很 大，从而收敛速度慢f g r e n e z 则通过修改r e m e z 算法e ，1 3 来寻找问题的解，不过他 的算法不能保证收敛，k h a l ilc h a d d a d 等人在 2 6 中应用向量空间投影方法解决此类问 题，虽然此方法还可以扩展到多维滤波器设计中，但是它只收敛到问题的可行解而非最 优解文献 1 6 的广义r e m e z 算法虽然能在一定的范围内求解这类问题，但是笔者发现， 当滤波器长度为偶数或者较大时，广义r e m e z 算法不能收敛到问题的c h e b y s h e v 意义下 的最优解在文献 3 0 中，赖晓平提出一种迭代r e m e z 算法，把约束优化问题转化为一 系列无约束优化问题，这种方法不仅能保证收敛到问题的最优解，而且有较快的收敛速 度，虽然如此，算法中需要反复运用r e m e z 算法， r e m e z 算法的高效性源于它是根据交错点组定理中对c h e b y s h e v 逼近问题最优逼近 误差的交错特性的描述而设计的基于这种思想，本文先对交错点组定理进行扩展，得 到一个扩展定理，此扩展定理描述了不等式约束c h e b y s h e v 逼近问题的最优解的特性， 然后根据这一特性，设计了两种算法用于求解带不等式约束的线性相位f i r 滤波器的 c h e b y s h e v 设计问题算法不仅能够保证收敛到最优解，并且有很快的收敛速度，优于 山东大学硕士学位论文 现有的其它方法对于在频域中加入等式约束的f i r 滤波器设计问题，也有很多人进行 了研究并取得不错的结果，文献 2 5 ， 2 7 ， 2 9 ：中分别用了交换算法，o p r e m e z 算法和 广义r e m e z 算法解决此问题在本文第三节中把交错点组定理进步扩展到带有等式不 等式约束的c h e b y s h e v 逼近问题，并在第二节提出的算法的基础上设计算法求解等式不 等式约束的线性相位f i r 滤波器的c h e b y s h e v 设计问题此算法同样保证了收敛性和高 效性 近年来，人们开始对复系数f i r 滤波器的设计问题进行研究原因之一是当线性相 位滤波器的阶数很高时会产生较大延迟，而阻带的线性相位是没必要的：之二是一些场 合必须用到非线性相位滤波器，如波束形成器( b e a m f o r m e r ) ，地震杂波滤波器( s e i s m i c m i g r a t i o nf i l t e r ) 等但是，由于复数域c h e b y s h e v 逼近问题的最优解不能像实数域中 那样被确切的描述，故复系数f i r 滤波器的c h e b y s h e v 设计问题一直是滤波器设计中的 难点，一些人已经在这方面做了有益的工作，其中l j k a r a m 和m c c l e l l a n 提出的算法 较为成功在文献1 2 0 中，他们把交错点组定理扩展到复数域，并提出高效的复r e m e z 算法解决复系数f i r 滤波器的c h e b y s h e v 设计问题但是由于此扩展定理仅是一个充分 条件，所以此算法并不能保证收敛到最优解而往往只找到一个次优解在文献 2 3 中他 们对上述算法进行补充，若复r e m e z 算法找不到最优解，则在找到的次优解的基础上用 一种基于最速下降法的交换算法寻找最优解本文第四节研究了复系数f i r 数字滤波器 的约束c h e b y s h e v 设计问题，对于这一问题m l a n g 在他的博士论文 2 2 中用了迭代重加 权最小二乘( i r l s ) 算法，这类算法收敛速度一般不陕本文首先把文献 2 0 中的复交错 点组定理扩展到带不等式约束的情况，然后以此为理论基础，借鉴文献：2 0 ，2 3 中的算 法，通过适当修改第二节中的算法来求解带不等式约束的复系数f i r 滤波器设计问题 但是，这样也往往只能得到次优解，所以需要做进一步处理赖晓平在文献 3 0 中针对 线性相位f i r 滤波器的不等式约束c h e b y s h e v 设计问题提出的迭代r e m e z 算法完全能够 用于复系数f i r 滤波器的设计，于是再结合此算法就能得到约束问题的最优解了，并且 最终得到的算法仍具收敛性和高效性的特点 作者把本文所提出的各种算法均做成了i a t l a b 程序，并通过设计实例对上述各算法 进行了仿真分析经过与现有其它算法的比较，本文算法显示出了它的优越性 这里首先对c h e b y s h e v 误差准则做一些说明，设b 为实数轴上一紧集，定义在b 上 的连续函数厂的c h e b y s h e v 范数定义为： 。= m a a 瑚f ( 划 j ( 1 1 ) c h e b y s h e v 误差准则就是极小化误差函数的c h e b y s h e v 范数 考虑所要研究的问题的数学模型，长度为的因果的f i r 数字滤波器的频率特肚函 数可表示为： 山东大学硕士学位论文 一l 雷( p ”) = h ( n ) e ， n = 0 其中 ( h ) ) = 为系统的单位脉冲响应( 可为复数) 式写成如下形式： 如果把幅值和相角分离，则可把( 1 2 ) 亨( e j “) = 疗( ) 8 州， ( 1 3 ) 其中疗 ) ，庐) 分别称为幅频特性函数和相频特性函数，它们是数字域频率珊的实函 数所谓f i r 滤波器的c h e b y s h e v 设计就是求解参数伽( h ) ) n - i ，使得曰( p 7 “) ： e c h e b y s h e v 范数意义下最优地逼近一个给定的期望频率特性函数d ( e 一) ，即： m i n m 。a x 、( c o ) d ( e7 。) 一膏( ) m ( 1 4 ) 其中，q 是卜丌，厅) 上的闭子集，也称期望频带，( 出) 0 是一个加权函数，b ( e ，“) 为 - 万，丌) 上的连续函数 山东大学硕士学位论文 第二节线性相位f i r 数字滤波器的不等式约束c h e b y s h e v 设计 2 1 问题概述 对于f i r 数字滤波器的设计问题，如果参数弘( h ) 譬是实数，当我们把它取成奇对 称( h ( n ) = - h ( n 一1 一h ) ) 或偶对称( ( h ) = h ( n l 一月) ) 形式时，滤波器的相频特性是 数字域频率的线性函数： ( 珊) = 一( ( 一1 ) 2 ) + z r 2 或( ) = 一( ( 一1 ) 2 ) a ) ， 此时滤波器称为线性相位滤波器线性相位滤波器的幅频特性函数具体形式有以下四 种： 情况1 ：n 为奇数，协( ”) ) 。n - l 为偶对称形式 疗( 珊) = ：”“a ( n ) c o s c o n ，口( o ) = “一1 ) 2 ) ，d ( h ) = 2 h ( ( n 一1 ) 2 一n ) ， 月= 1 , 2 ，( 一1 ) 2 情况2 ：n 为偶数，协( ) = 为偶对称形式 ：( c o ) = ：2 6 ( h ) c o s ( 一1 2 ) ，b ( n ) = 2 h ( n 2 一 ) 情况3 ：n 为奇数， h 、n ；- 。i 为奇对称形式 ：( c o ) = ：i ”2 c ( 月) s i n o ) r t ，c ( 一) = 2 h ( ( n i ) 2 一n ) ， 情况4 ：n 为偶数，协( ”) = 为奇对称形式 ：( c o ) = ：3 d ( 月) s i nc o ( 订一i 2 ) ，d ( 月) = 2 h ( n 2 一n ) 经过三角运算，这四种情况可以统一地写成： 疗( ) ：q ( c o ) h ( 甜，q ) ， h ( 脚，q ) = 口。c o s n ， h i o n = 1 , 2 n | 2 n = 1 , 2 f 一l ) 2 n = 1 , 2 ；n 1 2 ( 2 1 1 ) 其中，n = 。，a l 一，口。) 是与 ( 行) 。, v - 1 相关的实值向量，q ) 在四种情况下分别为：1 ， c o s ( 珊2 ) ，s i n 出和s i n ( c o 2 ) 所以只需研究函数h ( o ，) 对相应的函数的逼近情况即可 为简单起见，在此只讨论情况l 时滤波器的设计问题，所得算法稍加修改即适合其它三 种情况对于情况1 式( 2 i 1 ) 中： r = ( + 1 ) 2 ，口o = “| v 一1 ) 2 ) ，a 。= 2 ( ( n 一1 ) 2 一玎) ，n = 1 , 2 ，一1 山东大学硕士学位论文 由于 ，n ) 是的偶函数，所以只在 0 ，羽上对它研究如果设d ) 为期望的幅 频特性函数，它是 0 ，万 上的连续实值函数，则可定义如下的误差函数： 定义1 ： e ( m ，a ) = d ( o ) 一日( ，) ( 2 i 2 ) 那么线性相位f i r 数字滤波器的c h e b y s h e v 设计问题根据式( 1 4 ) 可表达为： m i nm 。a 。x 。 w ( c o ) e ( c o ，) i ， ( 2 1 3 ) 与( 1 4 ) 式不同，这里q 只是 0 ，羽上的闭子集 本文所要讨论的线性相位f i r 数字滤波器不等式约束c h e b y s h e v 设计问题的数学模 型为： m i nm a x 。 w ( c o ) l e ( c o , a ) 眦 ( 2 1 4 ) s t 1 e ( c o ，i t ) 1 户( ) ，出孬， ( 2 1 ，5 ) 其中，壶和q 是 0 ，羽上不相交的闭子集，p ) 0 称为幅值约束函数，w ( c o ) 0 为加权 函数如果记此问题的可行域为a 。即： a h = - i i e ( o 。, ) l 兰p ( 缈) ，五；n r 7 ， ( 2 1 ，6 ) 那么问题( 2 1 4 ) ( 2 1 5 ) 还可描述为形式： 晌m i n 唆杪( 珊) l e ( 叫) l ( 2 l 7 ) 2 2 理论基础 前言中已指出，以交错点组定理为理论依据而设计的r e m e z 算法能很好的解决问题 ( 2 1 3 ) ，但是对于问题( 2 1 7 ) ，r e m e z 算法却无能为力为了找到解决此问题的高效 算法，这里首先把交错点组定理扩展到约束c h e b y s h e v 逼近问题 定理1 ：如果问题( 2 1 7 ) 的解存在，则a 是其唯一解的充分必要条件是：伍a ， 且存在至少r + 1 个按升序排列的频率点酗， ：。c ( h u r l ) 满足下式： w ( c o i ) e ( 一征) = ( 一1 ) “。万，苎国! ， ( 2 2 1 ) i e ( i ，旺) = ( - d ”。p ( ，) ，若e 2 ， 其中c 为常数取l 或0 ， j = r ：紧杪( 甜) l e ( m ，+ ) ( 2 2 2 ) 为了更清楚的说明问题，在证明定理之前先定义一个更新加权函数 定义2 ： 山东大学硕士学位沦文 瞄，= 咒，鬟叭 眨z s ， 下面给出定理1 的证明 证明：首先，如果6 + = 0 ，易知定理成立，以下证明占+ 0 的情况 ( i ) 必要性设问题( 2 1 7 ) 的解存在，记为理+ ，则旺也是如下无约束问题的解， m i n m a 。x 。 l , v ( a ) ，石) i e ( ，u ) 1 j ， ( 2 2 4 ) 否则- 必存在证。使得成立： j 脚) l e n l ? ， 5 2 ( 2 2 5 ) i 巧p ( c o ) l e ( c o ，位。) i 占+ ， 山q ， 由( 2 2 5 ) 式可见q 。a 。而且有 r ? 紧妒( ) e ( 甜，。) 1 r ? 爨c 妒( 珊) i ( 珊，。) i ， ( 2 2 6 ) 这与n 是问题( 2 1 7 ) 的解相矛盾，所以也是问题( 2 2 4 ) 的解对于无约柬i 司题 ( 2 2 。4 ) 由交错点组定理知。存在至少r + 1 个按升序排列的频率点k ) 二。c ( n u f i ) 满 足： 矿( ，占+ ) e ( c o 。，a ) = ( - 07 + 。占，i = 0 , 1 ，2 r ( 2 2 7 ) 其中f 为常数取0 或1 可见，( 2 2 7 ) 式与( 2 2 1 ) 式等价，必要性得证 ( i i ) 充分性、假设问题( 2 1 7 ) 的解存在，且存在旺+ a ，。和r + 1 个频率点 妇 二c ( q u 矗) 满足( 2 2 1 ) ( 2 2 2 ) 式如果并非问题( 2 1 7 ) 的唯一解，定存在 证。a ，1 满足： 嘴杪( 国) f e ( 印，q 。) | j 0 如果设 q 二在区间( 西，西j + ，) 上有七个点，当k 为偶数或0 时，由( 2 2 1 ) 式，则有 e ( 西，n + ) ( 面川，n + ) 0 ，从而立( 面，) 童( 亩川) o e l r 14 定义4 ： g ( x ，q 。) = 口0 ( 。+ c ( o x 一) ，x 0 其中： a “k ：。雹”d ( ；”) 6 7 = 。( 一1 ) ( j 。1 ) ，r “= l i j 。q c 。= 。，( 一1 ) 7 ，p ( 国j ”) ， 【n = j 脚j ”五 。= 枣c c 。s 一c 。s y ， ，r = 。上一，r 1 fl ( 2 3 1 ) ( 2 3 2 ) ( 2 3 3 ) ( 2 3 4 ) ( 2 3 5 ) ( 2 3 6 ) 并用q ) - 扣矗。表示在求解无约束问题 m i n m 。a 。x ，。 l 矿( c o ，j ) i e ( n ，) i ( 2 3 7 ) 的过程中根据r e m e z 算法对点组q ( 进行更新而得到的新点组 由于对于问题( 2 3 7 ) 用r e m e z 算法求解时，每次迭代中离散集n 上的最优逼近误 0 山东大学硕士学位论文 差的计算式为 渺l l = l：。“d ( j ”)i i ：。( 一1 ) 捌”i 矿科，j “) l 所以，根据定义3 ，定义4 可以得到 厂( x ，q “) = l g ( x q f ) ) 1 ( 2 3 8 ) ( 2 3 9 ) 2 3 。1 增广r e m e z 算法i 及收敛性证明 依据定理i ，这里首先给出增广r e m e z 算法i 来解决滤波器设计问题( 2 1 7 ) ，这种 算法设计简单，与r e m e z 算法和文献 3 0 中的迭代r e m e z 算法都有些相似算法的主要 过程是对给定的一个初始值万“、 0 和点组q “，执行用r e m e z 算法求解问题( 2 3 7 ) 时 的一次迭代，得到j ”1 和q f r ”后更新加权函数为驴( ，占n ”) ，然后在重复以上过程直 到找到问题的解为止，与r e m e z 算法不同之处在于它的每次迭代中都要更新加权函数， 迭代r e m e z 算法虽然也更新加权函数但是它是在对问题( 2 3 7 ) 执行完整个r e m e z 算法后 再更新的，所以其总的点组更新次数要多子本文算法，后面的仿真中会给出比较下面 先给出算法步骤，然后再证明其收敛性 令i = 0 ，给定一个迭代初始值占 0 ，允许精度误差 0 在q u q 上取个 ，1 初始频率点，o 硝 p 矽冗，并记其集合为q “= 扣j ”f - o 计算( 2 2 3 ) 至( 2 2 6 ) 式，令5 = g ( 巧，q “) 更新加权为矿( 占“) 后，求出在点集q “上的加权最佳逼近函数珂“( ) 先确 定频率点q 【”上“) 的值： f ? 5 = d ( c o ；7 ) 一( 一1 ) 艿痧( 国：“占“) ，i ：0 , 1 2 ，一1 再利用重心拉格朗日插值公式： 气咖髦筹， i l 其中：j ) = lt ( c o s 叫“一c o s 0 4 ”) 1 ，f = o ，l ，- 一，一1 瞄 根据用r e m e z 算法求解无约束问题( 2 3 ，7 ) 时点组交换规则进行一次点组更新， 得到一组新的频率点：o ? 钏 巧记q “”= 如，” 二，若 q “”= q 川且i 一嘲扣l 。，则结束：否则，令子“= 蚓，1 = 1 + 1 并返回 增广r e m e z 算法i 最终能够收敛到问题( 2 ，1 ，7 ) 的解，以下证明此算法的收敛性，首 先给出一些引理 山东大学硕士学位论文 引理1 ：对于给定的点组q “，关于x 的函数f ( x ，q 在正半轴单调递增 证明：任取0 x 1 x 2 ，设加权为矿，r ，) 和妒沏，x 2 ) 时d ( c o ) 在q 7 上的加权最佳 逼近函数分别为h ( c o ，a 。) 和h ( c o ，：) 根据离散点上最佳逼近函数的性质及定义3 ，任 意j ) q ( 7 满足： f ( x l , q ”) = 驴( 0 , x i ) l ( ”，证。l ，( x ：，q ( o ) = 驴( ”，x ：) i e ( m “，珏：) 再根据最佳逼近的唯性，必定存在脚，q “，使得： f ( x 。，q d ) 矿( 甜j ”，x ) i e ( j “，：) l ， 即： 厂( x ，q “) w ( o p ) i e ( 吐) ：“，2 ) i 或f ( x ，q “1 ) x p - 1 ( ，) i e ( ，n ：) i ， 成立而由假设可知： ( 凹p ) i e ( j “，：) i = f ( x 2 ，q “1 ) ， 一户“( j 7 ) l e ( 棚j i ) ，i j t2 ) x 2 p 。1 ( 功j f ) ) l e ( 甜j “，a ，) l = 厂( x 2 , q j ) ) ， 所以f ( x 。，q 厂( x ：，q