（计算数学专业论文）数值计算的加速算法与编程技巧.pdf

2 0 0 4 年上海大学硕士学位论文 摘要 本文包括两个部分。第一部分提出了用于在w i n o g r a d 矩阵乘法算 法中处理奇数阶矩阵的新方法一非等阶“十”字架划分方法；第二部分 研究r 小波分析在求解偏微分方程定解问题中的应用。 本文共分五章。第一章在w i n o g r a d 矩阵乘法算法的基础巴提出了 一种非等价“十”字架划分方法。该方法对奇数阶矩阵的处理非常有效。 它能大大减少无效的计算量，从而缩短计算时间、实现数值计算的加速 运算。计算实例也显示该方法是有效的。第二章简单介绍了小波分析的 一些基本概念以及本论文用到的小波。第三章以小波分析求解欧氏期权 定价问题数值解为例，说明小波分析求解偏微分方程数值解的过程。其 计算结果说明本方法与差分法相比，不仅提高了精度，并且明显缩短了 计算时间。第四章是小波分析在求解含有间断点的偏微分方程定解问题 e 的应用，并指出怎样利用偏微分方程的特性选取适当的小波基函数； 还提出一种小范围加密方法可以缩短计算时间并提高计算精度。第五章 是小波分析应用于非线性方程。 关键调矩阵乘法，w i n o g r a d 算法，“十”字架划分方法，小波变 换，偏微分方程 本课题得到国家自然基金资助( 基金号：1 0 2 7 1 0 7 2 ) 2 0 0 4 年上海大学硕士学位论文i i a b s t r a c t t h e r ea r et w op a r t si nt h i st h e s i s i np a r to n e ，w e r e p o r to i l ad y n a m i cc r o s s s c h e m et oh a n d l eo d d s i z e dm a t r i c e st oa p p l yi nt h em a t r i xm u l t i p l i c a t i o no fw i n o g r a d a l g o r i t h m i np a r tt w o ，w es t u d yt h ea p p l i c a t i o n so fw a v e l e ta n a l y s i si ns o l v i n g p a i t i md i f f e r e n t i a le q u a t i o n sw i t hb o u n d m yc o n d i t i o n s t h et h e s i sc o n t a i n sf i v e c h a p t e r s i nc h a p t e r1 ，w ep r e s e n tad y n a m i cc r o s s s d a e m eb a s e do nt h ew i n o g r a d sv a r i a n to fs t r a s s e n sa l g o r i t h m i tw o r k s e f f e c t i v e l y t oh ar n d l eo d d - s i z e dm a t r i c e sb e c a u s ei t c a nm i n i m i z ep a d d i n ga n dm a x i m i z et h e p e r f o r m a n c eo ft h ea l g o r i t h m s ot h es c h e m ec a l ls h o r t e nt h ec o m p u t i n gt i m ea n d s p e e du pt h ed a t ac o m p u t a t i o n t h ep e r f o r m a n c ec o m p a r i s o n sa l s oc a nc o n f i r mi t i nc h a p t e r2 w es i m p l yi n t r o d u c es o m eb a s i ck n o w l e d g ei nw a v e l e ta n a l y s i sw h i d l a len e e d e di nt h ef u r t h e rr e s e a r c hw o r ki nc h a p t e r3 w es h o wh o wt os o l v ep d e s b yu s i n gt h ep r o c e s so fs o l v i n gt h ee u r o p e a no p t i o nv a l u a t i o np r o b e l r n c o m p a r e d w i t ht h er e s u l to fu s i n gt h ed i f f e r e n c em e t h o d ，i th a si n c r e a s e dt h ea c c u r a t ed i g i t s w h i l es h o r t e n i n gt h ec o m p u t i n gt i m ei nc h a p t e r4 ，w ed i s c u s st h ea p p l i c a t i o no f w a v e t si np d e sw i t hs i n g u l a rp o i n t s ，w h i c hw e p o i n to u th o wt oc h o o s eo n ep r o p e r w a v e l e tb a s e do ni t sc h a r a c t e r i s t i c w ea l s op r e s e n to n et h i c k e n i n gm e t h o di no n e s m a l ld o m a i nt oh a n d l et h i sk i n do fp d e s t h e p e r f o r e m a n c ea l s os h o wi t c a r t s h o r t e nt h ec o m p u t i n gt i m ew h i l ei n c r e a s i n gt h ea c c u r a t ed i g i t s i nc h a p t e r5 ，w e d i s c u s si t sa p p l i c a t i o n si nt h en o n l i n e a rp d e s k e yw o r d s ：m a t r i xm u l t i p l i c a t i o n 、w i n o g r a d sv a r i a n to fs t r a s s e n sa l g o r i t h m ，w a v e l e ta n a l y s i s ，p a r t i a ld i f f e r e n t i a le q u a t i o n 原创性声明 本人声明：所呈交的论文是本人在导师指导f 进行的研究 ：作。 除- r 文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：型壅型日期星鲤丝塑苎目 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅：学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：垒l 垄型导师签名：奠壁垄日期：垒竺垒：z 垒 2 0 0 4 年上海大学硕士学位论文 第一章“+ ”字架划分方法 矩阵乘法是一种应用十分广泛的基本运算，提高矩阵乘法的运算速度可以实 现数值计算的加速运算，从而减少计算问题的时间耗费。这在理论上和实际应用 中都是非常有用的 矩阵乘法中著名的s t r m s s e n 算法及其改进的w i n o g r a d 算法都是用分而治之 的方法把矩阵乘法的时间复杂性由传统的o ( 一) 改进到o ( n ”n7 ) 。但是对于奇 数阶矩阵，在划分子矩阵时，必须要作特殊处理才能继续使用此算法。 本章提出了一种非等阶“十”字架划分方法，它可以最少化填零，最大化性 能，使得奇数阶矩阵乘法的时间复杂性更加接近于偶数阶矩阵乘法的效果。计算 实例显示该方法是有效的。 1 1 背景介绍 矩阵乘法是线性代数和科学计算领域中最基本的运算之一，在各类科学研究 以及工程技术问题的计算中经常涉及到大量的矩阵乘法运算。因此，提高矩阵乘 法的计算速度、实现矩阵乘法的快速算法是许多计算问题的关键，也是计算数学 研究的一个重要领域 很长时间以来，矩阵乘法的快速算法在计算机科学中受到高度重视，特别是 文献， 发表之后，更引起了许多学者的关注一方面，因为常规的矩阵乘法运算 对于那些高阶矩阵相乘的时间耗费是令人难以忍受的；另一方面，实际工作中又 往往需要这些运算。例如某仪器制造公司曾提出在仪器中安装数值计算的软件， 以达到进行数据分析的功能，其中经常会遇到高阶矩阵相乘等基本运算。如果应 用常规算法耗时则太多，不能满足要求；若采用现成的m a t l a b 等商业软件，虽能 提高运算速度，但费用昂贵，也会增加仪器的成本。因此必须要寻找快速算法才 能使仪器经济实用。经过一百多年的努力，该领域已有许多研究成果，其中较著 名的是s t r a s s e n 算法【2 及其改进的w i n o g r a d 算法。 这些算法一般都采用分治法( d i v i d e 。a x , d c o n q u e r ) 技术，分治法的设计思想 是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个 2 0 0 4 年上海大学硕士学位论文 9 击破，分而治之。 如果原问题可分割成k 个子问题，1 1 这种形式的递归方程在求分治法算法的时间复杂度时经常遇到，一般可以直 接用m a s t e r 定理来求解。 m a s t e r 定理：设a 1 ，b l 为常数，( r ) 为函数，丁( n ) = a 7 1 ( n 6 ) + 厂( n ) ， 其中，( n ) ，t ( n ) 为非负整数， 1 如果存在 0 ，使得，( n ) = o ( n “”8 ) ，那么t ( n ) = e ( n ”g a 。) 。 2 如果，( n ) = ( 忆l o g n “) ，那么t ( n ) = ( n l o g no l o g b 忆) 。 3 如果存在 0 ，使得f ( n ) = n ( n ”g b 。+ 5 ) ，且对于某个常数c 1 根据m a s t e r 定理，其解为t ( n ) = o ( n “9 27 ) o ( n 28 1 ) 。这说明s t r a s s e n 矩 阵乘法的乘法运算次数比普通矩阵乘法的乘法运算次数有阶的改进。 如果要进一步加进算法中的加减运算量，由于每个乘法运算都伴随一个加法 运算，每次递归中还引入1 8 ( 2 ) 2 次加减运算，那么s t r a s s e n 算法中的加减法运 算次数t ( n ) 应满足下面的递归方程： 2 0 0 4 年上海大学硕士学位论文 5 j 7 1 ( 2 ) ) i 丁( ) = 7 t ( n 2 ) + 1 8 ( n 2 ) 2 n 2 由于1 8 ( r 。2 ) 2 = o ( n 2 ) = o ( n ”g 。7 _ 3 ) ，根据m a s t e r 定理，其解还是t ( n ) = o ( n i 。9 27 ) 。由此可见，s t r a s s e n 矩阵乘法的计算时间复杂性已由传统矩阵乘法的 o ( n3 ) 改进到o ( n ”g z7 ) 。 是否还能减少乘法的运算次数呢? 有人曾列举了计算2 个2 阶矩阵乘法的3 6 种不同方法，但所有的方法都要做7 次乘法。除非能找到一种计算2 阶方阵乘积 的算法，使乘法的计算次数少于7 次，按上述思路才有可能进一步改进矩阵乘积 的计算时间的上界。但是h o p c r o f t 和k e r r ( 1 9 7 ) 目已经证明：计算2 个2 2 矩阵 的乘积，7 次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不 能再寄希望于计算2 2 矩阵的乘法次数的减少。或许应当研究3 x3 或5 5 矩阵 的更好算法。在s t r a s s e n 之后又有许多算法改进了矩阵乘法的计算时间复杂性。 目前最好的计算时间上界是o ( n 2 ”7 ) 。而最好的下界仍是它的平凡下界n ( 舻) 。 因此到目前为止还无法确切知道矩阵乘法的时间复杂性。关于这一研究课题还有 许多工作可做。 w m o g r a d 算法 4 1 是s t r a s s e n 算法的变形，它也需要7 次子矩阵乘法运算， 但是只需要1 5 次子矩阵加、减法运算。这个方法非常著名是因为它是所有基于将 矩阵2 2 分块的递归矩阵乘法中使用乘法和加、减法运算次数最少的算法 w i n o g r a d 算法如下： 2 0 0 4 年上海大学硕十学位论文 = p 1 + 岛 =b+r = + 如 = u 3 + p 7 = + b = 巩+ p 3 = 巩+ p 6 p 1 = a 1 1 b 娲= a 12 b 2 ls 1 = a 2 l + a 2 2 乃= j e 1 2 b b = s 五s 2 = s l a 1 1 乃= b 2 2 7 j 尸4 = 岛l j 岛= a n a 2 1 乃= 岛2 一b 1 2 p 5 = 乳码岛= a 1 2 一岛噩= b 2 1 一死 r = & 岛2( 1 16 ) p 7 = a 2 2 蜀 上面的算法对于非方阵也成立，即矩阵a 、b 、c 可分别为( n m ) 、 ) 、( n k ) 阶矩阵，n 、r n 、k 全为偶数。为了叙述方便，下文只对方 阵进行讨论。 另一个要说明的是，对于阶数比较小的矩阵乘法，上述算法虽然减少了乘法 运算，但是由于在运算中都引入了子矩阵加、减法运算，反而会降低计算速度。 解决的方法是当阶数小于某个珊时结束递归，改用常规矩阵乘法。这个n o 称为 递归段截断点，一般它的取值范围是3 2 到1 2 8 。至于何时结束递归最好，在文献 5 1 中有专门的讨论。 上面的算法中都要求矩阵为偶数阶矩阵，但是对于n 不为偶数时则需要进行 处理之后才能使用。一般有如下三种处理方法： 方法一是静态填充法。这是s t r a s s e n 本人介绍的方法，有许多书本中都引用 此方法。其思想是在计算之前对矩阵a 、b 进行填0 ，使之以后的每次迭代计算 中都为偶数阶矩阵。这种方法容易导致大量的填0 ，从而增加了内存消耗和无效 的计算极端的例子是n = 2 + 1 ，此时要填充为n + 2 “一1 ，这里d 为计算的 迭代深度。此方法容易导致矩阵元素的成倍增加。它比较适合于n = 2 一1 的情 况。该方法的优点是程序相对简单。 巩巩魄砜魄 | _ 一 | | | _ 渤 强 m 2 0 0 4 年上海大学硕士学位论文 7 静态填充法的一个变形是动态填充法，它不是一次性填充大量的0 ，而是在 每次递归之前填充1 行l 列o ，把奇数阶矩阵变为增加一阶的偶数阶矩阵。不过， 南f 乘法运算只在最后一级进行，此方法的乘法计算量与静态填充法的计算量一 样，只是减少小量的加减运算，其计算速度与静态填充法的计算速度近似相等。 方法二是动态重叠法这种方法分解出来的子矩阵概念上会有l 行或1 列重 叠，在迭代中同时计算重叠行或列，最后忽略其中一个。此方法与动态填充法一 样，也会增加额外的计算量。它的计算速度与静态填充法的计算速度近似相等。 其优点是可以节省内存的消耗量，但程序比较复杂。 方法三是动态去边法此方法把矩阵划分出4 个( n 一1 ) 2 阶的子矩阵，对余下 的边再单独计算。这样对边的计算不能再利用w i n o g r a d 算法来减少计算量了。极 端的例子是n = 2 。一1 ，此时每次迭代都要进行去边处理。它比较适合n = 2 2 + 1 的情况。这种方法比较节省内存，是目前用得较多的方法，该方法的缺点是程序 复杂。 2 0 0 4 年上海大学硕士学位论文 1 2 “+ ”字架划分方法 8 我们希望能够找到一种既能不额外增加无效计算量，又能充分利用w i n o g r a d 算法来减少计算量的方法首先我们采用类似动态去边的策略，但是去掉的不是 边，而是去掉1 个“十”字架，即矩阵中间的1 行1 列；其次我们尽量把“十”字 架的部分计算归并到( 11 6 ) 式中尸l 到p 7 的计算中去。 下面具体介绍“十”字架划分方法【6 ： 设以，口，c 均为n 阶方阵，其中n = 2 m + 1 为奇数，对矩阵a b ，e 作如下 分块： 州乏 c ：( ：f i ；i m ( m + 1 ) 阶子矩阵 是m 阶方阵，a c ：，k m 阶子矩阵 x 1 2 ，h 2 是 c c 。( t = 1 ，2 ) 、 黜叭勋 q m 吃 6 6 6 即扪跏 ， | | 、 地h 圪 ，一 = 日 、， 钆 毗如 q m 眈 n 1 2 x x ，l、 】| 4 、， 叻锄 昀 嘞 是 = 埘 阵为筏黻阶的时 “此 是 2 0 0 4 年上海大学硕十学位论文 9 g ： = r= ( ，1 ，4 f 。2 c 1 “2 l + a 2 2s 2 = s l a l l岛= a l l a 2 1 b 12 一日l it 2 = b 2 2 一t 1死= b 锄一b 1 2 = a 1 2 一s 2 ，j = b 2 l t 2 t r i = 6 r 2 一b 7 l( 1 4 = b c 2 一b c f ，q 1 2 k a 1 2 b 2 1岛= s l 乃十a c 2 饥 印l l + b = a 1 1 b l l + a c l b r l + b q 1 l + g l lu 3 = u 2 + p 5 g 1 2 g 2 2j p 7 = a 2 2 t 4 + 岛u 5 = u 3 + p 3u 6 = u 2 + p 3 u 7 = u 6 十p 6 0 1 2 + g 1 2 + a 2 2 t 。4t 2 = q 2 l + g 2 1 + s t 4 b 2 2 ( 1 2 1 ) q 1 2 + a 1 2 6 。2r l = q 2 l + a t 2 b 2 1m m = q 2 2 + a t 2 b c 2 定理1 1在上述条件下，有下述结论 c l l = 岛1 = u 4 ，岛2 = u 5 、c 1 2 = u 7 c c l = c 1 ，c t l = t 1 ， c m2 m m ，c c 25c 2 ，c t 2 。r 2 ( 1 2 2 ) 、 h 溉 l l r 帕 a 打 毗 l r h 既玩 y 1 l 以 刚 r， n q 吼嘞如 ，、 | | & 、| 晒咖r 乃曲o ，打 卜 、，x 篙叫岛川蝎咒i昆 2 0 0 4 年上海大学硕士学位论文l u s l a 1 1 = 4 2 l + a 2 2 一a a 12 s 2 = a a 2 一a 2 l a 2 2 + a l l b 2 2 一乃= 曰2 2 一疗1 2 + 日l l b “一乃= b 2 l b 2 2 + b 1 2 一日 1 q l l + p 2 = a l l b n + 。1 b r l + a 1 2 b 2 l = q l 2 十p 5 = q 1 l + g + 玮 a n 日1 】+ n c l b r l 斗岛乃+ s 。3 t r l + s 3 t j + s c 3 6 7 2 a t l 凹1 1 + a c l b r l 十( a z l + a 2 z a 1 1 ) ( b 2 2 一b 1 2 + b 1 1 ) + ( a c l a c 2 ) ( b r 2 6 n ) + ( a l l a 2 1 ) ( 岛2 一日1 2 ) + ( a t l 一。c 2 ) ( 一6 您) a 2 1 b n + a 2 2 ( b 2 2 一b 1 2 + b 1 1 ) + 。c 2 b r l ， f ，3 + p 7 = 2 1 3 + a 2 2 t 4 = + a 2 2 ( b 2 1 一b 2 2 + b 1 2 一b 1 1 ) a 2 1 b n + a 2 2 b 2 1 + n 。2 b r 】= q 1 厂3 + p 3 = a 2 t b l l + a 2 2 ( b 2 2 一b 1 2 + b 1 1 ) 十口q 打j + s i 乃+ 口。2 打、 a 2 1 b n + a 2 2 ( b 2 2 b 1 2 + b ) + a c 2 打1 + ( a 2 1 + a 2 2 ) ( b 1 2 一b 1 1 ) + a c 2 ( b r 2 一b r l ) a 2 1 b 1 2 + a 2 2 b 2 2 + 。2 b r 2 = ( 毛2 + p 6 = 此+ b + p 6 q n + g l l + s 1 二r j + 0 0 2 打l + 岛b 2 2 a l l b l l + n c l 6 r l 十( a 2 l + a 2 2 一a 1 1 ) ( 上毛2 一b 1 2 + b ) + ( a c l o c 2 ) ( b r 2 一b r l ) + ( a 2 1 + a 2 2 ) ( b 1 2 一b 1 1 ) + a c 2 ( b r 2 一b r l ) + ( a 1 2 一( a 2 1 + a 2 2 一a 1 1 ) ) x b 2 2 a u b n + 。l 6 也+ a 2 1 b 2 2 = c 1 2 孔 【| l | | | = = | | = = | | | | = = = | | = = | 蚕 岛 & 乃 玛 乩 魄 u 巩 2 0 0 4 年上海大学硕士学位论文 定理得证 q 1 2 + a 1 2 b c 2 = a 1 】b c l + c b c l b m + a 1 2 b e ：2 = ( 。c 1 q 2 1 + n 7 2 b m = 7 2 b 2 1 = c t l q 2 2 + a t 2 b c 2 = 一a l lxb c l + n m b v a + 0 7 2 xb c 2 = c ? n q 1 2 + g 1 2 + a 2 2x t c 4 a uxb e l + a c lxb m + 岛xb c j + ( 一5 c 3 ) xb m a 2 2 ( b c 2 一b q ) = c c 2 q 2 1 + g 2 1 + s t 4 b 2 2 口r 1 b n + a ? t t b r l 一r 1 码+ m ( 一t r l ) + s t 4xb 2 2 = c 7 2 1 3 计算结果与讨论 由于动态重叠法和静态填充法的计算效果近似，在实际计算性能比较中，仅 比较“十”字架划分方法、动态去边法、和静态填充法三种方法的计算效果现 应用c 语言在w i n d o w s2 0 0 0 ”下实现了这三种算法，对于静态填充法，在比较 时，直接计算n + 2 4 1 矩阵。在配置为p 4 ( 24 g ) ，2 5 6 ms d r a m 的计算机上计 算，实际计算时间由表1 1 列出： 矩阵阶数n迭代深度静态填充法动态去边法叫“字架划分方法 5 1 l3f n = 5 1 2 103 303 5o3 4 5 1 33 ( n = 5 2 0 ) 0 3 6 0 3 50 3 5 1 0 2 34 ( n = 1 0 2 4 ) 23 9 2 4 12 3 6 i1 0 2 54 ( 1 1 = 1 0 4 0 ) 2 8 1 24 324 4 2 0 5 15 ( n = 2 0 8 0 ) 2 2 5 42 1 0 11 97 5 表i - 1 从上表可以看出“十”字架划分方法一般比静态填充法和动态去边法要快 2 0 0 4 年上海大学硕士学位论文 1 2 对f 此结果可以给f 如下的解析： 设2 个n 阶矩阵乘法的算术乘法运算计算量为c ( n ) 对于动态去边法：c ( 2 m 十 1 ) = 7 c ( m ) - e 8 m 2 + ( ) ( m ) ；对于“卜 ，字架划分方法：c ( 2 m + 1 ) = 2 c ( m + 1 ) + s c ( m ) + 6 m 2 + o ( m ) 。如果是在最后一级调用传统矩阵乘法算法，此时c ( m ) = m 3 ；不难 看出二者的乘法运算计算量都为c ( 2 m + 1 ) = 7 , m 3 + 8 m 2 + o ( m ) 即如果m + 1 为 偶数，则可以充分利用迭代调用w i n o g r a d 算法来减少计算量，即使r n + 1 为奇 数，“卜 字架划分方法也不会比动态去边法增加计算量。 下面再对n = 2 一1 和n = 2 + 1 的情况进行分析。对于n = 2 一1 的情 况，第一级迭代；仁有2 个偶数阶子矩阵乘法计算和5 个奇数阶子矩阵乘法计算， 需要进行1 次奇数阶处理第二级迭代中由于2 个n = 2 “1 阶矩阵乘法不会再产 生新的奇数阶子矩阵乘法，2 7 + 5 2 = 2 4 个偶数阶子矩阵乘法计算、5 5 个奇数 阶子矩阵乘法计算，需要进行5 次奇数阶处理。继续下去，不难看出这是一个等 比数列，每级迭代需要进行5 “1 次奇数阶处理，而动态去边法则需要7 “1 次奇数 阶处理。对于n = 2 + l 的情况，动态去边法只需要1 次奇数阶处理，“十”字 架划分方法每级迭代需要进行2 “1 次奇数阶处理，此时动态去边法稍优。 1 4 进一步的工作 分块矩阵算法一般会引入一些辅助矩阵这就引入一个问题，即如何存储这 些中辅助矩阵以减少程序的存储空间开销。这方面也有一些文章讨论过，不过没 有得到最优的结论，还有待作进一步的工作。 另一方面，如文献 1 指出在不同的计算机系统中s t r a s s e n 的实际运算效率 以及递归截断点的选取都不一样。如何结合一些实际计算机系统来实现算法的优 化，如某些智能仪器设备中常用的c p u ，也还有待作进一步的工作。 2 0 0 4 年上海大学硕士学位论文 1 3 第二章小波分析中的基本概念 长期以来，人们一直在寻找具有各种优良性质的特殊函数来分解任意函数。 在这方面，f o u r i e r 分析不可否认地占据着垄断地位。但是，傅立叶分析也不是 完美无缺的，它的主要缺陷有： ( 1 ) 三角函数基在时域上没有局部化，因此不宜作局部分析，全局基给计算带 来不便 ( 2 ) 傅立叶分析只在l 2 ( r ) 有效，对于p 2 的驴( r ) 空间，傅立叶级数只是 形式上展开，而不能刻划函数的性态。 ( 3 ) 分辨率不高，在傅立叶级数中，由于频谱点的等距分布，不能很好地反映 一些具有突变的非平稳信号。 目前兴起的小波分析既能保持傅立叶分析的特点，又能改进它的不足之处 这在理论上是重大突破，在实际中也是有重要意义。由于小波分析克服了傅立叶 分析的不足，在时域和频域上同时具有良好的局部化性质，并且它对高频采取逐 步精细的时域步长，从而可以聚焦到被分析的任意信号，因此它被誉为分析信号 的“数学显微镜”。 本章介绍了小波分析中的基本概念，并简单介绍了本论文用到的两种小波的 性质。 2 1 常用符号和定义 为r 研究问题的方便，我们首先简单地介绍一些常用的常用符号 只：表示实数全体，即r = ( 一o 。，+ o 。) z ：表示整数全体，即z = o ，1 ，士2 ，土3 ，) 。 驴( r ) ( 1 p o 。) ：表示满足i f ( x ) l ，d x o o 的全体函数构成的空间。 j 一。 万：若a 为一点集，则以万记为其闭包，即a 与其极限点之并。 支集：如果，( z ) 是定义在r 上的函数( 可以取复数值) ，那么称集合s u p p f 再矿石f 事可为，( z ) 的支集如果s u p p f 是紧集 那么就称函数f ( x ) 为支集紧 2 0 0 4 年上海大学硕士学位论文 1 4 或具有紧支集。 正交：当( ，g ) = o ( 或( n9 ) = 0 ) 时，则称，与g ( 或z 与g ) 正交。 f o u r i e r 变换：在l 1 ( r ) 中定义f o u r i e r 变换为 f ，( 。) 一( f ，) ( 。) ：，( 。) ：n 。，( 。) 。一z u z d 。 ( 2 l 1 ) j 一。 2 2 小波基本理论 2 2 1 小波的定义 顾名思义，“小波”就是小的波形。所谓“小”，是指它的衰减性，譬如它是局 部非零的；称之为“波”，则是指它的波动性，即其振幅呈正负相间的震荡形式。 下面我们引进小波母函数的定义及允许性条件 定义2 1 如果函数妒( t ) l 2 ( 只) 满足容许性条件： q ：n 。掣幽 o ，那么妒( t ) 满足允许性条件( 2 21 - 1 ) 即砂( t ) 是一个 小波母函数。 因此，当允许性条件( 2 2 1 1 ) 判别比较困难时，可考虑条件1 妒( t ) i c r 南) ”5 是否满足，从而来进行判别函数是否是小波母函数。 小波母函数妒( t ) 经过位置的平移与尺度收缩便形成了一个小波函数族 砂山( ) = 击妒( 警) ) ，其中。0 为尺度因子，b 为位移。在不同尺度下小波的分析时段随 t z 的增大而增宽，幅度则与面成反比缩小，但小波的形状不变。位移b 则是通过 改变分析时段的中心位置使信号的分析区间发生变化。 2 0 0 4 年上海大学硕士学位论文 1 5 2 2 2 连续小波变换 定义2 3 令 妒。，6 ( t ) = 一1 ，。( t - 。b v ) ，n ，b r ，n 。 则仉( ) 称为由母函数妒( t ) 生成的依赖于参数n ，b 的连续小波。 定义2 4 设，( t ) l 2 ( r ) ，妒( t ) 是一个小波母函数，则内积 ( ，) = 巾) 蕊硇t 称为，( ) 关于吵( ) 的连续小波变换，记为，( 。，b ) 或( w 勺，) ( “，b ) 连续小波变化具有下面的性质 1 2 1 1 1 目： 线性性：设，( t ) = a f l ( t ) + ；3 h ( t ) ，则 ( ，) ( n ，b ) = a ( w 口f 1 ) ( a ，b ) + 卢( w 勺，。) ( 。，b ) 平移不变性： ( w c f ) ( a ，b r ) = ( w 勺，( t ) ) ( 哦b r ) 伸缩共变性： ( w e f ( d ) ) ( n ，6 ) 。丧( 吼m ) ) ( 。，。6 ) 微分运算性： ( 吼( 掣) ) ( m h - 1 ) ”e 巾) 器丽出 f 222 1 ) ( 22 22 ) ( 2223 ) ( 2224 ) ( 2 225 ) f 222 6 1 与f o u r i e r 变换相类似，连续小波变换也有反演公式及p a r s e v a , 1 等式。 定理2 5 1 q 设，( t ) ，9 ( t ) l 2 ( r ) ，令妒( t ) 是一个小波母函数，且 q ：。哮扎。 那么等式 厂厂( 0 ，b ) 丽i 警：q ( f 埘 ( 2227 ) ( 。，b ) 丽i 等2 q ( ，9 ) ( 2227 ) 2 0 0 4 年上海大学硕士学位论文 成立。 特别地，当f ( t ) = g ( t ) 时，( 2 , 2 27 ) 可写成 壶仁仁州删2 一d 万a d b = 仁i 巾坪此( 2 2 2 8 ) 如果f ( t ) 在t r 足连续的，那么由定理2 5 得到下面的定理。 i i i ! i | 2 6 【1 4 1 设，( f ) ，9 ( t ) l 2 ( f t ) ，令咖( ) 是一个小波母函数，且 铲仁咩山， 那么在f ( t 1 的连续点t 兄有 巾) = 瓦1 仁仁帅，丁d a d b 。( 2 2 2 9 ) 根据定理2 , 6 ，任意一个函数可以由它的小波变换来进行重构。这为我们的 研究带来了方便， 2 2 3 二进离散 定义2 7 设v a t ) 是一个小波母函数，取a = 2 ，b = 1 ，记 奶( ) ：2 j 7 2 妒( 2 j t 一女) ，k z ， ( 223 1 ) 定义2 8 设f ( t ) l 2 ( 月) ，记 q ( j ，) = ( ，奶，) = 坤) 面丽d t ， 32 ) j 一。 则称此离散的 q ( k ) ) ，女。z 为，( t ) 关于奶，e ( t ) 的离散小波变换，也称为小波系 数。 定理2 9 1 2 】设，( ) l 2 ( 只) ，令妒( ) 是个小波母函数，并设 q ( j 1 ) h 艇z 为，( ) 关于也，( ) 的离散小波变换，那么 o 。 ) = c s ( j ，) 奶，k ( t ) ( 2233 ) 2 0 0 4 年j 二海大学硕士学位论文 在实际应用中，经常用到的是正交小波、半正交小波和双正交小波。由于它 们各自满足的条件不同，因而具有不同的性质，应用范围也就不同。 定义2 1 0 如果一个连续小波砒， ( ) 经离散化以后得到的 “_ ，( f ) ) 构成空问 l 2 ( 尺) 的一组标准正交基，即 “巩札撕) ) = = = 蜊厕出哳氓m = 。1 轰忙”。巾2 34 ) 则称函数w ( t ) 为一个正交小波。 定义2 1 1 如果一个连续小波札6 ( f ) 经离散化以后得到的f 奶* ( ) ，构成空问 f ，2 ( 打) 的一组基，并且 ，。l 17 = f ( 魄“- 幽m ( f ) ) 2 上o 。蛾“咖m ) d 。2 屯f 21 o 妻他 q 23 j o 。 l 4 则称函数妒( t ) 为一个半正交小波。 定理2 1 2 “令州t ) 为个半正交小波，通过设定 - 些生一， ( 2236 ) 。c 、”， ( ei 妒( w + 2 k ) 1 2 ) 1 2 * 可以证明西1 为一个正交小波。 定义2 1 3 如果一个小波 坞，。( t ) ) 及其对偶羁，( t ) 满足如下性质 ( 也，k ( ) ，佤，。( t ) ) = 如，f 民。 ( 223 7 ) 则称函数妒( t ) 为一个双正交小波。 根据定理2 6 知，若函数( t ) l 2 ( r ) 关于妒( ) 的连续小波变换，( ，6 ) ，a ，b r ，o 0 已知，可由公式( 2 22 9 ) 唯一确定函数，( ) 。而对于i ( t ) l 2 ( r ) 的离 散小波变换 q ( j ，) ) 批。z ，当奶， ( ) 为正交小波基时，有以下展开式 m ) = q ( j ，k ) 也 ( t ) ( 2238 ) 2 0 0 4 年上海大学硕士学位论文 1 8 此时由 q ( ， ) ) ，肛z 完全确定函数，( ) 这种由一个函数的平移和伸缩构成的正 交基及展开式( 2238 ) 在理论上和实际中都是非常有用的。 从数学角度来看，f o u r i e r 变换，连续小波变换和离散小波变换都是将所研究 的函数在一组特定的基函数上展开的分解问题。由于基函数不同，因此就有了不 同的分辨率性质。 2 2 4 多分辨分析 多分辨分析( m u l t i r e s o l u t i o na n a l y s i s ) 简称m r a ，是sm a l l a t 在1 9 8 8 年提 “；的，利用它可以得到构造小渡的方法 定义2 1 4 ”我们称满足下列性质的l 2 ( r ) 中的一系列子空间 巧) ，e z 和函 数西( ) 为一个正交m r a o e 交多分辨分析) ： ( 1 ) 一致单调性：cu 2cu 1c cv lck c ； ( 2 ) 渐近完全性：uk = l 2 ( 月) ，n 嵋= o ) ； ( 3 ) 伸缩规则性：f ( t ) 铮f ( 2 t ) 巧、f ( t ) 等f ( t 一) v o ： ( 4 ) 基的存在性：基的存在性：存在( t ) ，使得 ( 一) ，k z ) 是 的标准正交基 定理2 1 5 设 k ) 及( ) 为一个正交的m r a ，令 ，k ( t ) = 2 i 2 0 ( 2 a t 一女) ，j ，z ， 则函数系 钙，* ( t ) ) 卅；z 构成空间岣的一组标准正交基， 性质( 3 ) ，( 4 ) 表明f ( t ) v o 甘f ( 2 a t ) b 因而定理2 1 5 成立 设是k 在嵋+ 中的正交补空间，即上，且岣+ l = ko 。显 然，对任意的j ，j7 z ，j j7 ，子空间 屹与，是相互正交的 由于 = w t 0 w m 一= 。0 一。o 一= 0 0 o 嘶一。0 一z o 一 ( 2 241 ) 2 0 0 4 年上海大学硕士学位论文 根据性质( 1 ) ，( 2 ) ，令m o o ，n 一一。，即得 l 2 ( r ) = o ， ( 2242 ) 一 且上式右方是正交分解。因此，如果存在这么一个函数妒( t ) ，使它的整数平移 “o ，t ( t ) ) * 。z 构成空间w j 的标准正交基，则 屿，k ( t ) l ，k e z 是驴( r ) 的标准正交 基，那么此函数“，( f ) 称为是一个正交小波母函数构造正交小波母函数妒( ) 的方 法将由以下定理来阐述 定理2 1 6 1 5 设 巧) ，z 及p ( t ) 是一个正交m r a ，由于咖( ) cm ，而 如( 2 一) ) 挺z 是u 的标准正交基，所以 ( t ) = e h k 妒( 2 t m ) ( 2243 ) z 称式( 2 2 4 3 ) 为双尺度方程，令 妒( ) = e ( 一1 ) 2 瓦1 一女妒( 2 t 一) k e z 及由式( 2 2 3 1 ) 可以证明 奶，k ( t ) ) k t z 是l 2 ( 兄) 的标准正交基 基 奶、k ( c ) ) k 。z 张成的空间，即 = s p a z l 2 ( r ) 也，k ，z ， 刚 ( 2244 ) 并且记为由 ( 2 245 ) 上，o y j = k 助z ， 且当j j7 时，w j 上，( 证明见【1 6 1 ) 定理21 6 不仅讲述了构造正交小波的方法，还给出了尺度函数咖( t ) 与正交小 波母函数砂( t ) 之间的关系，因此可将构造正交小波母函数妒( t ) 使它的整数平移 妒( t 一) ) 。；。构成空间w o 的标准正交基的问题转化为利用m r a 构造相应的尺 度函数西( ) 的问题 根据2 241 式和2 2 4 2 式，对于l 2 ( r ) 中的任意函数，( z ) 都可以用一个 厂( z ) 来非常接近地逼近，可以分解为 2 0 0 4 年上海大学硕士学位论文 即 ，= g 14 - g g2 + + g ml + vm ，v j ，厶k ，乳w 0 【2 2 46 ) ，( z ) j o , k c j 。，k ( z ) + 岛， 蛳( z ) 、j 。2 一m ( 2 n 47 ) ，= j o 其中c ，。和岛，k 为待定系数，m ，和的选取由实际计算的精度要求以及小波 的紧支集来决定。 2 4 本论文用到的小波 2 4 1d a u b e c h i e s 小波 d a u b e c h i e s 小波是一种具有良好性质的正交小波 1 4 1 ( 1 ，在实际中有着广泛 的应用。 对于序号为n 的d a u b e c h i e s 小波，其小波函数妒( z ) 和尺度函数( z ) 的紧 支集的长度都为2 n 一1 ，其中小波函数妒( z ) 的紧支集为 1 一n ，尺度函数 $ ( c ) 的紧支集为【0 ，2 n 一1 。图2 1 和图2 2 分别为n = 9 时的小波函数和 r 度函数的波形图。 fi fl | if l 1 1 n j1 。i r 一 图2 1 尺度函数0 ( 。) 图2 2 小波函数妒( z ) 2 0 0 4 年上海大学硕士学位论文 2 4 2 双正交小波 双正交小波f 1 1 在m a t l a b 软件中一般表示为b i o f n rn d 的形式，这里n d 表 示分解的层数，r 表示重构的层数。西( c ) ，p ( z ) 分别是9