（运筹学与控制论专业论文）稳定iir数字滤波器的最小二乘算法研究.pdf

原刨性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究作出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：途良日期：丝! ! 垒墨丑 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意 学校保留或向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：j 邀鱼导师签名： ，ij ，lfr、 1 1 k 山东大学硕士学位论文 稳定l ir 数字滤波器的最小二乘算法研究 摘要 本文主要考虑了i i r 数字滤波器的设计问题，重点研究了迭代的加权最 小二乘算法。为满足滤波器的幅值响应要求，分别给不同频带加入幅值约束， 并分析了最大幅值误差参数对设计结果的影响。为达到误差等波纹的设计结 果，将迭代重加权技术应用到i i r 滤波器的设计问题中考虑到加权最小二 乘算法是求解一系列二次规划问题，为提高运算速度，又采用投影最小二乘 算法代替目前流行的有效集方法本论文共分为五个部分。 第一部分为引言，主要阐述了i i r 数字滤波器的优点，以及近年来对i i r 数字滤波器设计算法的研究现状，指出了本文对加权最小二乘算法的两种改 进，即加入幅值约束和引入迭代重加权思想，仿真表明了这两种改进的意义， 并说明了稳定性约束对t 滤波器设计的重要性，分析了几种稳定域描述的 优缺点，最后介绍了投影最t j 、- - 乘算法。 第二部分介绍了i i r 数字滤波器的基本概念，以及r 数字滤波器设计中 常用的两个设计准则，给出了基于加权最小二乘设计准则的问题描述，并将 频率响应的分母实部大于零，作为稳定性约束条件。 第三部分采用迭代的加权最小二乘算法，在考虑稳定性约束的基础上， 分别增加了对通带、阻带的最大幅值约束，并通过实例仿真分析了最大幅值 误差参数对设计结果的影响。 第四部分将迭代重加权技术应用到i i r 数字滤波器的设计问题中，通过 权函数的迭代得到等波纹的误差。本文在权函数的更新中使用了包络线方法 以提高收敛速度。对给定滤波器采用两种不同的设计方法，即m l a n g 论文 中的设计方法和前面描述的i r l s 设计方法，仿真表明了迭代重加权最小二乘 设计方法可以在保证满足设计要求的基础上达到更快的收敛速度。 第五部分考虑到本文中最小二乘算法需要求解一系列的二次规划问题， 用投影最小二乘算法解决二次规划( q p ) 问题，来提高设计算法的运算速度。 山东大学硕士学位论文 2 影最小二乘算法在f i r 数字滤波器设计问题中已经得到了很好的应用，本 把该算法应用到i i r 数字滤波器设计中。多数的算法仿真都证明，应用此 法后可以大大的加快算法的运算速度。 关键词：i i r 数字滤波器，加权最小二乘，迭代重加权，投影最小二乘 山东大学硕士学位论文 t h er e s e a r c ho fl e a s ts q u a r e st e c h e niq u e sf o r s t a b l ei i rd i g i t a lf i l t e r a b s t r a c t t h i sp a p e rc o n s i d e r st h ed e s i g no ft h ei i r ( i n f i n it ei m p u l s e r e s p o n s e ) d i g i t a lf i l t e r ，m a i n l yt h ei t e r a t i v ew e i g h t e dl e a s ts q u a r e s d e s i g nm e t h o d s i no r d e rt os a t i s f yt h ea m p l i t u d er e s p o n s eo ft h e f i l t e r ，w ea d dc o n s t r a i n t so fa m p l i t u d eo l ld i f f e r e n tf r e q u e n c yb a n d s ， a n da n a l y z et h ei n f l u e n c eo ft h em a x i m a la m p l i t u d ee r r o ro nt h ed e s i g n r e s u l t s t oo b t a i nb e t t e rd e s i g nr e s u l t sw i t he q u i r i p p l ee r r o r , w e a p p l yi t e r a t i v er e w e i g h t e dt e c h n i q u e st ot h ed e s i g no fi i rd i g i t a l f il t e r s s i n c eas u c c e s so fq u a d r a t i cp r o g r a n l n i n gn e e dt ob es o l v e d i nt h ew e i g h t e dl e a s ts q u a r e sa l g o r i t h m , t h ep r o j e c tl e a s ts q u a r e s a l g o r i t h ms u b s t i t u t e sf o rt h ep o p u l a ra c t i v es e tm e t h o d ss oa st og a i n af a s t e rs p e e d t h ep a p e ri sa r r a n g e di nf i v es e c t i o n s t h ef i r s ts e c t i o nm a i n l yi n t r o d u c e st h ea d v a n t a g e so fi i rd i g i t a l f i l t e r sa n dt h er e s e n tr e s e a r c ho fi i rd i g i t a lf i l t e r s i ta l s o p r e s e n t st w oi m p r o v e m e n t so fi t e r a t i v el e a s ts q u a r e sa l g o r i t h m , t h a t i s ，a d d i n ga m p l i t u d ec o n s t r a i n t sa n di n t r o d u c i n gi t e r a t i r er e w e i g h t e d t e c h n i q u e s 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 d t oi l l u s t r a t et h e p e r f o r m a n c e s o m ed i f f e r e n ts t a b l ec o n s t r a i n t sa r ea n a l y z e d ，a n dt h e i r i m p o r t a n c et oi i rd i g i t a lf i l t e r i ss h o w n l a s t l y ，i ti n t r o d u c e s p r o j e c tl e a s ts q u a r e sa l g o r i t h m t h es e c o n ds e c t i o ni n t r o d u c e ss o m ef u n d a m e n t a lc o n c e p t i o n sa n dt w o d e s i g nc r i t e r i o n so fi i rd i g i t a lf i l t e r i tf o r m u l a t e st h ed e s i g n p r o b l e mb a s e d o nw e i g h t e dl e a s ts q u a r e sd e s i g n c r i t e r i o n ，a n d e m p h a s i z e s t h es t a b l ec o n s t r a i n t st h a ti i rf i l t e r d e s i g n m u s t g u a r a n t e e 3 4 山东大学硕士学位论文 第一章引言 数字滤波器的设计问题是数字信号处理中的基本问题。近年来，由于数 字信号系统的广泛应用，数字滤波器的设计问题也引起了人们越来越多的关 注。根据结构的不同，数字滤波器分为无限冲击响应( i 瓜) 数字滤波器和有 限冲击响应( f m ) 数字滤波器 由于i i r 数字滤波器系统函数的极点可位于单位圆内任何地方，因此相 比较f i r 数字滤波器而言，i i r 数字滤波器具有更高的选频特性、更小的通带 群延迟，而且可以用更少的乘法单元来实现同样的频率特性，在高选频、小 延迟、需要快速处理的场合得到了广泛的应用。另一方面，由于非平凡的i i r 滤波器没有精确的线性相位和内禀稳定性，其设计问题形成的数学模型经常 是非线性约束非凸规划模型，如何对其进行优化设计的问题也无疑非常具有 挑战性。 对i i r 数字滤波器设计的研究已经有几十年，人们提出了许多有价值的 设计方法1 1 5 ，它们主要分为间接设计方法和直接设计方法两大类。其中间 接设计方法包含两种。一种是先设计一个合适的模拟滤波器，然后将其数字 化，通过变换得到i i r 数字滤波器。这种方法没有考虑线性相位约束，且只 能用于期望特性是标准类型的情况；一种是模拟约减法 2 3 1 1 4 ，即先设计一 个满足特性要求的f i r 滤波器，然后应用模型约减技术，得到低阶的f i r 滤 波器。但这种方法的逼近精度不易控制，且得不到更小的通带群延迟。第二 类直接设计方法是依据某些设计准则直接设计i i r 数字滤波器以使其满足期 望的频率响应特性。该类方法以往采用的有线性规划法和有理r e m e z 多重交 换算法，但这两种算法都存在缺点其中线性规划法存储量大，耗时多；而 有理r e m e z 多重交换算法，由于交错点的个数不能事先确定，故存在较严重 的收敛性问题。目前比较流行的是基于二次误差和p 一方误差最小准则的非 线性规划方法，它们大都采用迭代的技术，把问题转化为一系列有唯一解的 二次规划或二阶锥规划问题。本文研究了基于加权最小二乘误差准则的i i r 滤波器设计算法，分别给通带、阻带加入了幅值约束，分析幅值误差参数对 设计结果的影响；同时采用了迭代重加权最小二乘算法以得到幅值误差等波 5 i 一 蝌蝴 山东大学硕士学位论文 纹的设计结果。 与f i r 数字滤波器不同，i i r 数字滤波器的频率响应关于滤波器系数是非 线性的，故其频域加权最b - - 乘设计闯题关于系数变量也是非线性的。所以 在i i r 数字滤波器设计中，首先要考虑把设计问题转化为一系列线性规划或 二次规划等已知的最优化问题的形式。迭代的加权最4 x - - 乘算法就是将设计 问题转化为一系列二次规划闯题，通过迭代的方式得到最优解。该算法在文 4 献 1 6 】【l 弧1 8 】【1 9 】中已经应用到i 滤波器设计问题中，而且大量实例已经证 明比较有效。但在实际应用中，有时会要求通带或者阻带的幅值响应误差在 一定范围内，单一应用迭代的加权最小二乘设计算法可能达不到这样的设计 ：要求。文献【5 】 6 】中分别提到了在通带和阻带加入幅值约束的方法，虽然约束 应用在了基于不同设计准则的两种设计算法中，但都达到了满意的设计结果。 本文中将通带和阻带幅值约束应用到迭代的加权最4 , - 乘算法中，并分析了 在满足幅值响应误差要求的前提下，选择不同的最大幅值误差约束值对设计 结果产生的影响。 为达到c h e b y s h e v 设计指标，即要求误差在整个感兴趣的频带上均匀分 布，可以参考在f i r 数字滤波器设计中采用的方法。目前，迭代重加权最小 ；乘算法在f i r 数字滤波器的设计问题中得到了广泛的应用 7 2 0 1 1 2 1 ，它通 过计算一系列权函数不断更新的加权最小二乘问题，在迭代过程中不断利用 更新权函数来减小误差，并最终得到误差等波纹的设计结果。此算法的主要 优点还在于它的计算效率，由于每一次迭代都是求解一系列的等式方程，所 以即使收敛速度很慢，与线性规划算法相比较，需要的计算量还是8 1 i 4 , 的。 在文献【刀中也应用迭代重加权最小二乘算法设计f i r 数字滤波器，但却没有 考虑稳定性约束，所以设计的滤波器可能是不稳定的。 正如文献【7 】中的设计结果所表明的，r 数字滤波器设计的另一个困难 就是它不具有内禀的稳定性，所以一定要在设计中加入稳定性约束，以达到 稳定的设计结果。只有当设计的滤波器稳定时，设计才是有用的。对于一个 线性时不变离散滤波器，如果其传递函数的极点都在复平面的单位圆内，则 为稳定的。当然对于单位圆外的极点，可以在保证不改变滤波器幅值响应形 状的前提下，将其映射到单位圆内，得到稳定的滤波器。然而，若该极点距 6 山东大学硕士学位论文 离单位圆很近，映射的极点就会影响到滤波器的相位响应。因此，对于给定 幅值相位响应的i i r 数字滤波器设计问题，要想得到稳定的结果，必须使极 点约束在单位圆内。 对于稳定域的描述目前已经有许多种，m 1 a n g 在他的博士论文中，提出 了基于r o u c h e s 定理的稳定域。后来，w s l u 和t a k a oh i n a m o t o 在文献【8 】 中，又提到了基于鲁棒稳定性的约束条件。而b o g d a nd u l ：n i t r c s c u 和r i i t t a n i e m i s t o 在2 0 0 4 年的文献【9 】中，提出了基于正实性的稳定域。这些稳定域 描述都不容易线性化，推广性较差，而且通常运算时间也会比较长。 本文中，我们采用最常用的稳定性描述，即要求频率响应的分母实部大 于零 5 】 1 0 】。由于这一约束很容易转化为线性约束，所以简单，方便。通常 我们都考虑用此约束的离散形式，它在控制滤波器的稳定性方面更有弹性。 一方面，给定密集的离散格点，约束可以任意的逼近原条件以保证稳定性。一 另一方面，若选择稀疏的格点，则可以保证约束有效而且约束条件又不太苛一声，乞? t 刻。而且它在程序运行时间上要大大优越于其他的几种稳定性约束 ， ” “ 另外，可以看到本文所采用的设计算法是把滤波器设计问题转化为一系茹， 列二次规划( q p ) 问题。通常，我们都是借助于m a t l a b 优化工具箱中自带的节8 。 q u a d p r 0 9 0 函数来求解q p 问题，这个函数集成了目前最流行的有效集方法。 。 t 在【2 2 】中，针对一般约束的正定二次规划问题。提出了一种全新的高效算i 蠹篷 法投影最小二乘算法。该算法首先计算目标函数无约束极小化问题的解， 。 也可以称其为一个无约束最小二乘解，然后将此解逐次投影到有效约束确定 的可行域。算法的迭代过程就是一个个投影过程，所以每次迭代都只是一些 简单的投影运算，而流行的有效集方法，每次迭代都要解一个线性方程组以确 定搜索方向。相比之下，投影最小二乘算法的计算量要小得多。另外，投影 最小二乘算法不是内点算法，因此不需要初始点在可行域内，这就免去了寻： 找初始可行点的大量计算 本文将投影最小二乘算法应用到i i r 数字滤波器设计中，大量实例证明在 不改变滤波器设计方法的基础上，只需将q p 问题的求解用投影最小二乘算法 代替，就可以有效的改善现有算法的运算效率，大大缩短运算时间 ， 山东大学硕士学位论文 第二章ii r 数字滤波器设计基础 2 1i i r 数字滤波器的基本概念 酢，= 卷= 券删= - m 其中a ( n ) 和b ( m ) 为滤波器的系数，这里我们只考虑系数为实值的情况。为了 实际的需要，上式中m 和n 可以取任意非负整数，但m 不能小于n 。同时 我们定义函数a ( z ) 和b ( z ) 为关于孑- 1 的多项式，分别称a ( z ) 和b ( z ) 为分母多 项式和分子多项式。其中m 为分子多项式的阶数，称为分子阶数；同样定义 n 为分母阶数。 本文中所设计的滤波器为任意幅值相位响应的i i r 数字滤波器，通常取 m n ，也就是要求复平面原点外的零点个数比极点个数要多。对于理想的 滤波器而言，零点在通带的作用主要是使滤波器逼近期望的通带相位响应， 零点不仅影响通带同时还会影响阻带。而且，零点可能会在复平面的任一位 置，而极点则由于稳定性的要求只能在一个稳定域内。 i r 数字滤波器的频率响应为： 脚) = 器 跚) m 其中b ( m ) = b ( n ) e 一脾，彳 ) = 1 + 口( 珂) p 。胂 - o - l 关于i i k 数字滤波器设计问题，可以简单描述为求出一组系数a 和b ，使 得在规定的准则下，滤波器的响应可以逼近给定的特性。 2 2 设计准则 8 如今，随着最优化设计方法的发展，最优化方法也广泛应用到i i r 数字 山东大学硕士学位论文 滤波器设计问题中。当然，要衡量这些最优化设计结果的好坏，都需要有一 个指标，即一个物理量。常用的i i r 滤波器的设计准则有两种，即： 最小化最大误差准则 幽肚衄一 4 筹加c 叫 3 ， 基于最大误差最小化准则的滤波器设计称为c h c b y s h g v 设计，它可以使 最大加权误差达到最小，并使误差在整个感兴趣的频带上均匀分布，故又称 为等波纹设计。在文献【l1 】【2 3 】中分别用迭代的线性规划( l p ) 算法和连续影 射( s p ) 算法实现此设计准则。 加权最小二乘误差准则 础和，= r 忡，黯叫，1 2 如 ) 基于加权最小二乘准则的滤波器设计称为加权最小二乘设计，它可以使 加权平方误差达到最小，但逼近误差却不够均匀，需要通过权函数形) 来调 节。在文献【5 】 1 0 】 1 2 】中都是运用迭代的加权最小二乘算法来实现此设计准 则。 2 3 最小二乘设计问题描述 目前最小二乘算法已经被广泛的应用于科学工程的不同领域之中，而许 多数字滤波器设计方面的文章也都运用了最小二乘算法。该算法在f i r 数字 滤波器设计问题中的应用已经非常成熟。而在将加权最小二乘设计算法用于 解决i i r 数字滤波器设计问题时，首先要对最小二乘目标函数进行修正，从 而使修正的目标函数可以表示为关于滤波器系数的二次形式。因此，最小化 修正后目标函数的设计问题已经不再是真正的最小化平方误差的设计问题， 设计的结果也只是一个次优解。修正的方法如下： 式( 2 1 4 ) 可以表示为： 幽8 = r 崭m 叫妒( 圳2 如 叫) 卅 每i 一 一馥 l o 马：。= 一睨一。细。) r e ( d ，) q ，q 孑) 山东大学硕士学位论文 日五= 一) 瞰q o q 乒) 只。- - e 形, 一( c o ，h d ( 峨m 2r “q 。) 最i = 一矾。，) r d ( q ) _ 0 ) l 在数字滤波器设计中，由于i i r 数字滤波器本身的稳定性要求，需要首 先考虑稳定性约束。而实际应用中，通常还会有其它对通带或阻带的最大幅 值约束等限制条件，设第k 次迭代时约束条件可以表示为瓯( x ) 0 ，于是第 k 次迭代对问题可以写成如下的约束最优化问题： m i n e k 舒= 1 t f hk x k + p ：x t + c 二 s u b j e c t t o ：墨( s 0 2 4 稳定性约束 对于i i r 数字滤波器设计，首先考虑的问题就是要保证滤波器设计有效 的稳定性约束，并且要把约束条件线性化，使设计问题转化为二次规划等已 知的优化形式，从而借助于m a t l a b 中的优化包求解。 对于稳定性约束，其充要条件不可以线性化，通常只能线性化其充分条 件，所以最后得到的解只能是一个次优解。现有的研究f i r 数字滤波器设计 问题的文章大都考虑了稳定性条件，并且有不同的稳定域描述。一类是明确 描述稳定域，将稳定性条件转化为某种形式的约束加入到设计问题的数学模 型中。比较早的例子是在整个迭代最优化过程中要求频率响应分母的实部大 于零，即： r e a ( e j 4 ) 1 0 ，v 国 o ，万】 ( 2 2 1 ) 后来在文献 1 1 1 中采用了基于r o u c h e s 定理的稳定域描述，文献【9 】中利用传 递函数的正实性建立稳定域，并将它应用于多重交换算法。而在文献【7 】中应 用半定规划，其中的约束为基于l y a p u n o v 方程的线性矩阵不等式。这一类的 稳定域描述都需要选择合适的算法来表示。 另一类是隐含的稳定性描述。比如直接选择i i r 滤波器的系数使得传递 函数h ( z ) 为稳定的，例如 2 5 】。或者是在设计准则上加上限制函数，使其在 i 盘0 i - 。；韵 j 山东大学硕士学位论文 其中q = ，x ，m 也：o ， 石锝 扩，蚓7 【e 伽j 这样( 2 ，2 3 ) 可以方便的加入到二次规划，线性规划等模型中。 经上述分析，带有稳定性约束的加权最 b - 乘设计，其第k 次迭代的优 化问题可以描述为： r a i n 8 k 妥x ：h t x t + p ：x k + c 二 s j l e k ( 1 6 ) p 2 l 整个迭代算法的步骤为： 1 ) x o - - o0 o l 。州帅l ，g 椭) = l ，i = i ，2 工，s = l o 一，k - = l 为迭代次数。 些查盔兰堡主兰垡丝苎一 2 ) 计算h k ，p k ，o ，解二次规化问题得到x k 3 ) 更新权g 椭) = 4 ) 若l x 。一x 。- i 0 ，七0 为迭代序号 r n芒。，f n i ，、1 2 ， 4 仕= 鹕呼形”i e ( q ，酬 2 ) 彬t m ，：形c ”展( 峨) = 毒! 墨盟，i ：l ，2 ，m。嘞i 咿p ，口) i + 3 ) 七：= 七+ 1 ，返回l 。：一t p 擎! l a w s o n 算法1 2 9 的收敛速度很慢，而且如果在某些频率采样点上 i | e ( q ，口q ) f _ o ，那么该点新的权值也就变为零，这点的权函数在以后的迭代 + 2 过程中将一直为零不再改变。如果该点正好对应c h e b y s h e v 设计问题最优解 的极值频率，则必须重新启动算法。为避免彤。) = o 的传播，可以修正上面的 权函数 形“= ( 彤+ 五) 尾( q ) 其中a 为小的正常数，这样的改变虽然可以避免在下一次迭代中权函数仍然 为零，但是却无法避免形) = o 在【7 】中，介绍了一种新的权函数更新方法，它采用误差函数幅值的分段 线性包络线代替误差函数对权函数进行更新，这种新方法使得权函数在更新 过程中不会出现零值，不仅可以使权函数有效更新，而且也可以避免重新启 动算法。 误差函数及其包络线分别如图4 1 ( a ) 和图4 - i ( b ) 所示，显然用此包络线 山东大学硕士学位论文 数时，在某些点p ( q ，d ) o 时，对应的包络线q p ，) 线有两种形式，种是如图4 - l ( b ) 所示的分段线性的包 是阶梯型的。即统一用误差函数的局部极大点来表示该 两种包络线函数都可以得到近似的设计结果。本文我们 就采用图4 - 1 ( b ) 的分段线性包络线形式。 图4 - l ( a ) 误差函数图像图4 - 1 误差函数的包络线 首先计算误差函数的绝对值 慨) | = i 以q ) 一日 川 求出i e k ( c a , ) f 的局部极大值，并用圪( f ) = l 巨 州) ) l 表示局部极大值，即要求 l e k ( 州) ) l 限( 嘶( ) + 。) | ，极大值对应的频率点为：国州) ，i = 1 ，2 ，3 把一系 列极大值点的坐标表示为：l 吼( ，r 。( 0 1 对于吼( ，) 功 吼( i + i ) ，包络线q p ) 表示为： g 和) ；丑 哆，( i + 1 ) 一n 0 ( f )圪( f + 1 ) + 上坐譬 圪( f ) ( 4 2 1 ) d o j ( t + 1 ) 一吐，“ 当然，由于i i r 数字滤波器本身的通带，阻带分界，在上式中要求国删和奶( ，+ d 都在同一个频率带上。包络线g ) 只是定义了通带和阻带上的误差函数幅 值包络线，而对过渡带不加考虑。另外，为避免包络线c ) 太逼近零值， 对k ( o 的取值给了限制，即如果吒( f ) s o 1 , , m i n ( z t ( i i ) ，圪o + 1 ) ) ，就令 山东大学硕士学位论文 圪( o = o 1 w i n ( v , ( i 一1 ) ，圪o + 1 ) ) 。 在l a w s o n 算法中，权函数的更新尻( q ) 与恢( q ) i 成正比，导致收敛速 度很慢。实验表明，用如下的更新函数可以得到更快的收敛速度。 既+ ：职屏( q ) = 吸“寻t 三一) c ( 吼) 以) 一 l 朋c ) 其中指数1 口 2 ，指数口会影响设计算法的收敛性以及收敛速度。 4 3 迭代重加权最小二乘设计算法 根据前面的思路，下面给出整个算法流程； 0 ) 初始化：给出c h e b y s h e v 和w l s 两个设计准则中权的关系： 呒= 似。) 2 ，按照第二章中的加权最小二乘算法设计出滤波器。 1 ) 计算误差函数绝对值： l 反( 国叫= l d ( q ) 一日( 缈。) i 七= l ，2 三( 4 3 1 ) 2 ) 计算误差函数的包络线q ) ，更新权函数； 咧c 圭乏急f 洲 ， 其中0 会影响收敛速度，取值为1 口 2 。 3 ) 重新运用加权最小二乘准则设计滤波器。如果k 在更新权函数后 变化较小，则算法中止，否则返回l 。 4 4 算法仿真与比较 例4 1 设计一个低通的r 数字滤波器，其中刀= 1 4 ，m - - 1 0 ，国，= o 3 万， 彩。= 0 3 5 n ，初始权函数在有效频带上都取1 ，通带群延迟为9 。 “一d 山东大学硕士学位论文 图4 2 幅频函数曲线( 实线为i r l s 方法，点线为w l s 方法) 图4 - 3 ( a ) 幅值函数曲线图4 - 3 c o ) 幅频函数曲线 图4 4 滤波器的幅频函数曲线 山东大学硕士学位论文 仿真结果如图4 - 2 ，其中加权最j 、z 乘算法所用c p u 时间为1 3 1 2 0 s ，迭 代重加权最小二乘算法中取0 = 1 2 ，所用c p u 时间为1 9 0 6 0 s ，算法在2 次迭 代后就中止。 例4 2 设计一个高通的i i r 数字滤波器，其中露= 1 4 ，脚= 6 ，彩。= 0 3 5 1 r ， 国。= 0 4 0 ，r ，初始权函数在有效频率带上都取1 ，通带群延迟为9 。 得到的滤波器的幅值响应如图4 - 3 ( a ) ，幅频响应如图4 3 ( b ) 。算法中取 0 = 1 2 。在第2 次迭代后中止，所用c p u 时间为1 0 3 1 0 s 。 例4 3 设计一个带通的i i r 数字滤波器，其中疗= 1 6 ，肼= 1 0 ，阻带为【00 3 】 和【o 7 2l 】，通带为 0 3 20 7 】，初始权函数在有效频率带上都取1 ，通带群 延迟为1 0 。 得到的滤波器的幅频响应结果如图4 4 。算法中取0 = 1 1 ，在第2 次迭代 后中止，所用c p u 时间为2 2 5 0 0 s 。 通过上面的低通、高通和带通的三个i i r 滤波器设计实例，可以明显看 到迭代重加权最小二乘算法设计的结果呈现等波纹的特性。 下面将迭代重加权最小二乘算法与m r l a n g 论文中基于r o u c h e s 定理的 牛顿算法进行性能比较。 对于例3 2 ，设计一个低通i i r 数字滤波器，其中一= 1 2 ，m = 6 ，通带截止 频率m 。= 0 2 5 ，r ，且m 。= 0 3 0 ：t ，权函数在有效频率带上都取l ，通带群延迟 为9 。分别用迭代重加权最小二乘算法和m r l a n g 论文中的改进的牛顿算法 来设计，仿真比较结果如图舢5 ，4 6 。 其中迭代重加权最小二乘算法中取6 = 1 3 ，在第2 次迭代后中止，所用 c p u 时间为0 7 3 4 0 s ，m r l a n g 的算法则需要耗时9 6 2 5 0 s 。 在文献【1 2 】中，m r l a n g 通过大量的实例仿真证明他的算法在高频具有优 良特性，这点在图4 - 5 ，4 - 6 中也有体现，但是由于算法的稳定性条件是基于 r o u c h e s 定理的，所以稳定性约束比较复杂，必然会减慢算法的运行时间， 而本文中的迭代重加权最小二乘算法采用的是较简单方便的稳定性约束，即 频率响应的分母实部大于零，它可以在保证滤波器稳定性的前提下，更快的 得到较好的等波纹设计效果。而且通过对大量实例的仿真表明，本文算法的 图4 - 6 幅值函数曲线( 实线为i r l $ 算法，点线为牛顿算法) 山东大学硕士学位论文 第五章投影最, b - - 乘算法 5 1 投影最小= 乘问题的一般性描述 从前面几章的分析可以看到，用最小二乘准则设计i i r 滤波器时，最初的 设计准则经过处理后都转化为对二次规划问题求解的形式。而二次规划问题 也是最早被人们研究的一类较简单的非线性规划问题，它在多种工程问题如 滤波器设计等方面都有着广泛的应用。因此，提高二次规划算法的效率对许多 问题都有着重要的意义目前存在的解决二次规划问题的算法有有效集方法， 对偶方法和内点算法等，其中有效集方法是最流行的方法之一。m a t l a b 6 1 优 化工具箱的q u a d p r o g0 函数就集成了这种有效集方法。该方法通过有限个 等式约束二次规划问题来解决一般约束下的二次规划问题。每次迭代都确定 组有效约束，并把这组约束当作等式约束来处理j 用于确定搜索方向。在迭 代过程中，不断地调整有效约束，最终找出真正的有效约束集，并得到问题的 解。 而在 2 2 】中，针对一般约束的正定二次规划闯题，提出了一种全新的高效 算法投影最小二乘算法。该算法首先计算目标函数无约束极小化问题的 解，然后将此解逐次投影到有效约束的边界。算法的迭代过程是交替地更新有 效约束和向有效约束边界投影的过程。每次迭代都是一些简单的投影运算， 而流行的有效集方法，每次迭代都要解一个线性方程组以确定搜索方向。相比 之下。投影最小二乘算法的计算量要小得多。投影最小二乘算法的另一特点是 不需要初始可行点，免去了寻找初始可行点的大量计算。 一般约束二次规划问题描述为 r a i n 妻群吼五+ 彤j 耻+ c 一 ， ( 5 1 1 ) 二 s t4 x - - b , i = 1 ，2 ，m 。 ( 5 1 2 ) 4 x 6 ji = r r 。+ 1 ，小( 5 1 3 ) 有效集法是通过求解有限个等式约束二次规划问题来解决一般约束下的 二次规划问题。直观上，没有效的不等式约束在解的附近不起任何作用，可 山东大学硕士学位论文 以去掉不考虑；而有效的不等式约束，由于它在解处等于零，故我们可以用 等式约束来代替不等式约束。 投影最小二乘方法也是需要用迭代的方法求出问题的有效约束，在每次 迭代中都用投影最小二乘算法来解一个等式约束子问题。下面我们先介绍一 下用投影最小二乘方法解决等式约束问题。 5 2 等式约束的投影最小二乘算法 算法首先求出无约束极小化问题的解x ( o ) = 一日一p ，我们称之为一个最 小二乘解，然后就是将这个解逐次的投影到问题的可行域中，也就是使解逐 次满足一个有效约束，最终满足所有的有效约束，并得到问题的解。算法步 骤描述如下： 1 ) q ( 0 ) = 日一，x ( o ) = - q ( o ) p ( 5 2 1 ) 2 ) 对i = 1 ，2 ，m e ， x c d = x c ，一t ，+ 三 l ；i ! ；等p ，一4 x o 一- ， c s 。2 ， q ( 力= q ( f 1 ) 一q ( i - = - i 1 乏) a i i , r a ：, 6 q r ( i - i ) ( 5 2 3 ) 容易验证，对，= 1 ，2 ，i ，任意的向量s 都有彳，q ( i ) s = 0 ，因此q ( f ) 是 把任意向量投影到子空间p i a j s = 0 ，_ ，= 1 ，2 i 的投影算子矩阵 由上面的算法，可以得到如下的定理。 定理：若带等式约束的二次规划问题( 5 1 1 ) ( 5 1 2 ) 可行，而且矩i 蜂h i e 定， 那么算法可以收敛到该问题的唯一解。 证明：由于问题( 5 1 1 ) ( 5 1 2 ) 可行而且矩阵日正定，所以问题有唯一解 下面引进辅助的目标函数 三= h x x + i 1 旯篓( z 枷2 ；丢x r 旧+ “ +erlx 五羔彳6 l r x + 寻五兰6 1 2= 寺x 7 旧+ + 五彳6 l r + 寺五6 1 2 - l li j _ 加i i 根据外点罚函数理论，r 的极小点在旯趋于无穷时的极限就是问题 ( 5 1 1 ) ( 5 1 2 ) 的解。由于原问题解的唯一性，则定理得证。 5 3 不等式约束的投影最小二乘算法 用投影最小二乘算法解决一般约束问题的思路，类似有效集方法，重点 也是更新有效约束的过程。用，。= 1 ，2 ， n 。表示等式约束足标集，并用p 表 示第七次迭代不等式约束中的有效约束足标集。则第k 次迭代总有效约束足 标集为 ，( 的= j + ，“ 于是由，( 七) 中的约束组成的等式约束子阀题，可以用投影最小二乘算法来得 到。第_ | 次迭代得到的解设为牙( t ) ，对应的投影算子矩阵为虿( 七) 。如果又( _ j ) 破坏了某些不等式约束，就将破坏程度最大的那个不等式约束增加到有效约 束集中此时，“( 七+ 1 ) = p ) u 订，其中7 满足 彳i 承i ) 一岛= m 瓤“。( 4 j f ) 一6 ) q ( o = q o 1 ) 一o ( t _ - 乏o 乏i a f t a 二矿, q ( i - 1 ) 3 ) 求解非奇异线性系统 c 7 ( i ) a = 【廊( 七) + p 】 山东大学硕士学位论文 得到拉格朗日乘子向量a 。 4 ) 判断乘子五是否出现负值，如果出现，则将其中五最小者对应的约束 从有效集中删除，返回2 ) 如果得到的拉格朗日乘子向量名各元素都是正 的，且满足所有约束，那么迭代结束。 5 ) 而如果此时约束个数大于等于n ，或者类似线性规划中出现退化现象， 那么问题不可行，迭代结束。 6 ) 利用( 5 3 1 ) ，( 5 3 2 ) 计算岩( 七) 和豆沁) ，如果岩( 七) 破坏某些不等式约 束，则将破坏程度最大的那个不等式约束增加到有效约束集中，并返回3 ) 。 5 4 投影最小二乘算法在约束i i r 数字滤波器设计中的应用 论文前几章所描述的滤波器设计问题都是不等式约束问题，下面将投影 最小二乘算法应用到h r 数字滤波器设计问题中。 用投影最小二乘算法解二次规划问题的优势，可以在h r 数字滤波器设 计中有明显的体现。 对例3 1 ，投影最小二乘算法和m a t l a b6 1 优化工具箱中的q u a d p r o g0 有效集方法两者的性能比较如下： 6 9 q u a d p r o g0 投影最，、二乘 迭代次数c p u 时间迭代次数c p u 时间 o 17 51 4 9 0 6 25 13 o o o o 0 0 5 5 81 9 1 4 1 05 82 8 6 0 0 上图表显示当瓦= 0 1 时，用q u a d p r o g o 函数耗用的c p u 时间是投影最小 二乘算法的近5 倍，而当以= o 0 5 时，则达到了近6 7 倍。 对例3 2 ，取坑= o 1 时，用投影最小二乘算法求解二次规划问题时，耗 用c p u 时间为0 4 0 6 0 s ，而q u a d p r o g o 函数所耗用的c p u 时间为0 8 9 0 3 s ，是 其二倍还多。 对例4 1 ，用迭代重加权最j 、- - 乘算法求解，其中二次规划问题改用投影 最小二乘求解耗用c p u 时间为1 0 5 6 0 s ，也近似为q u a d p r o g o i 函数耗时1 9 0 6 0 s 一 ， 的一半。 3 l 山东大学硕士学位论文 另外在对其他实例进行程序仿真时也发现，不论在带幅值约束的加权最 t b - - 乘算法中，还是在迭代重加权最小二乘算法中，用投影最小二乘算法解 决二次规划问题都可以明显节省计算时间，提高运算效率。尤其对于例3 1 之类的需要多次迭代才可以收敛的情况，这种时间上的优越性就越发明显。 仔细分析投影最小二乘算法，可知其在时间上的优势是由其本身的优点所决 定的。 对于有效集方法，它需要一个满足约束条件的初始可行点来进行迭代， 于是首先应有一个寻找初始可行点的算法。q u a d p r o g o 函数是采用线性规划 算法来寻找初始可行点的。而对于投影最小二乘算法显然不需要初始的可行 点，而是以目标函数的无约束极小值点作为初始迭代点。这必然会大大节省 求初始点的运算时间。 另外，有效集方法每次迭代都需要重新求解一个线性方程组。而投影最 小二乘算法的迭代过程中，没有矩阵求逆运算，计算量也要比有效集方法小 得多。 最后，有效集方法是一种内点算法，每个迭代点都在可行域内而上面 的投影最小二乘算法是一个外点算法。初始点不在可行域内，通过不断迭代 将解投影到有效约束的边界。 综合以上对实例的程序仿真和算法的分析都可以清晰的得到，将投影最 小二乘算法应用n i i r 数字滤波器设计中必然会比直接调用q u a d p r o g o 函数 省时。 ， ) ， 产 一 山东大学硕士学位论文 结束语 本文主要研究了i i r 数字滤波器设计问题中的加权最小二乘算法，并采 用了频率响应分母实部大于零的稳定性条件。首先针对频带幅值误差有限制 的设计要求，对不同的频带加入了幅值约束，并分析了最大幅值误差参数的 选取对设计结果的影响。然后又对于要求达到c h e b y s h e v 设计准则的问题， 将在f i r 数字滤波器设计中比较成熟的迭代重加权最小二乘算法引入到r 数字滤波器设计中，仿真表明了此算法在运算速度上的优越性。最后由于本 文在解决一系列最小二乘问题时，将其近似转换为了二次规划问题，又采用 了投影最小二乘算法代替比较流行的有效集方法来解决q p 问题，从理论上 和实例仿真上都说明了它的高效性。 国 确 霸 1 ，： 山东大学硕士学位论文 参考文献 l r r a b i n e r ，n y g r a h a m ，a n dh d h e l m s ，“l i n e a rp r o g r a m m i n gd e s i g n o fi i rd i g i t a lf i l t e r sw i t ha r b i t r a r ym a g n i t u d ef u n c t i o n ”i e e e t r a n s a c o u s t ，s p e e c h ，s i g n a lp r o c e s s i n g ，v 0 1 a s s p - 2 2 ，a p r 1 9 7 4 p p1 1 7 1 2 3 v s r e e r a ma n dp a g a t h o k l i s ，“d e s i g no fl i n e a rp h a s ei i rf i l t e r s v i ai m p u l s er e s p o n s eg r a m i a n s ”i e e et r a n s s i g n a lp r o c e s s i n g ，v 0 1 4 0 ，f e b 1 9 9 2 ，p p3 8 9 3 9 4 b b e l i c z y n s k i ，j k a l e ，a n dg d c a i n ，“a p p r o x i m a t i o no ff i rb yi i r d i g i t a lf i l t e r s ：a na l g o r i t h mb a s e do nb a l a n c e dm o d e lr e d u c t i o n ” i e e et r a n s s i g n a lp r o c e s s i n g ，v 0 1 4 0 ，m a r 1 9 9 2 ，p p5 3 2