（计算数学专业论文）非线性奇异值问题的计算.pdf

复旦：赶学硕士些业论文 摘要 奇异值分解( s v d ) 在科学活动中有着广泛的应用，如信号处理，图象压缩，模式识别 它作为一个有利的分析工具为我们揭示了数据之问的本质特征本文讨论一种非线性奇异 值问题，并给出三种新的算法在第一章介绍了非线性奇异值问题的由来在第二章我们 给出了几种求解非线性奇异值问题的算法：乘幂法，n e w t , o nr a p h s o n 迭代，r a y l e i g h 商迭 代和特征向量法，并对其中的n e w , o nr a p h s o n 迭代和特征向量法的收敛性进行分析，最后 给出数值例子验汪r 我们给出的n e w t o ni a p h s o n 迭代在精度，时间上的优越性 关键字：非线性奇异值分解；最小二乘法；n e w t o nr a p h s o n 迭代 复旦大学硕圭毕业论文 2 a b s t r a c t s v dh a sa g r e a td e a lo fa p p l i c a t i o n si nm a n y a r e a ss u c ha ss i g n a lp r o c e s s i n g ，d a t ac o m p r e s s i o n ， p a t t e r nr e c o g n i t i o n a sap o w e r f u la n a l y t i c a lm e t h o d ，i ts h o w st h ee s s e n t i a lc h a r a c t e r i s t i c sa m o n g d a t a s i nt h i sp a p e r ，w ed i s c u s sak i n do fn o n l i n e a rs v d p r o b l e m sa n dp r o p o s ean e wm e t h o d w h i c hi sq u a d r a t i c a l l yc o n v e r g e n ti nc h a p t e rl ，w ep r o p o s et h en o n l i n e a rs v d p r o b l e m sa n dg i v e s o i l l ep r e l i m i n a r i e s i nc h a p t e r2 ，p o w e rm e t h o d ，n e w t o nr a p h s o ni t e r a t i o n ，r a y l e i g hq u o t i e n t i t e r a t i o na n de i g e n v a l u em e t h o da r ep r o v i d e d t h ec o n v e r g e n c e a n a l y s i so fn e w t o nr a p h s o n i t e r a t i o na n de i g e n v a l u em e t h o da r ed i s c u s s e d s e v e r a ln u m e r i c a le x a m p l e s3 x ea l s og i v e d k e y w o r d s ：n o n l i n e a rs v d ；s t l s ；n e w t o nr a p h s o nm e t h o d 第一章背景介绍 1 ，1 问题的来源 本节先给出一般的数学模型，从而推导出所要求解的问题， 先讨论如下问题： 脚捌气呻惮一引 s t - b y 2 0 ，y t y2 1 显然，由限制条件知b 是秩亏的，所以这不是一个凸最优问题现用l a g r a n g e 乘子法求 解这一问题定义函数： 其中! 彤，a r 对其求导得如下方程 a b = l y t ，b 7 k a ，b y = 0 ，y t y = l 注意a b 是秩一阵，由2 7 1 b y = 0 知a = 0由( a b ) = f 7 ，( a b ) t ! = f ( f 。1 f ) 知 a y = f ，a t b ( 2 7 f ) ，y t y = 1 设z = l l lz l ，一= 1 可得 a y = 。口，z 7 2 9 = l a t z = y g y t y 。1 这说明( z o - ，) 是矩阵a 的奇异三元组( 即左奇异向量，奇异值，右奇异向量) 由- 4b = i y 7 知j i a b 慷= 口2 所以我们需要的是对应最小奇异值的三元组所求的矩阵b = a x g y 丁 是a 的秩一修正 考虑如下形式的结构全局最小二乘问题( s t l s ) ： 锄r a 哪i n ( 口t “t ) 2 一邶( 6 ) 2 o ，f y - 1 其中b ( b ) = b o + b l b l + + b 。b 。殿。目为以向量b r ”作参数的仿射矩阵函数， 马舻”，i = 0 ，1 ，m 为给定的矩阵按上面的方法定义函数 ( b ，y ，2 ，a ) = ( n 。一b 。) 2 + 2 1 t ( b o + b l b l + + 6 m b m ) 掣+ a ( 1 一y t 掣) ， 。2 l 4 毗 。雠 ， = a v 口 复旦大学硕士毕业论文 其中f 1 7 1 、a 几对其求导得 v 七：吼一= 2 t b k y ，( b o + b l b l + b m b m ) 掣= 0 ， h 1 1 1 i ( b 彳+ b l b + + 6 m b i ；：) f = y k ， y t y = 1 由f 7 b ( b ) y = 0 知a ；o 由b = a 一l t b e y 知 ( a l b l +十o 。b 。) g = ( i t b l g ) b l + ( t b 。y ) b 。 9 ，( 12 ) ( a 1 日 + + a m b t ) l = ( 1 r b l y ) u t + + ( i t b 。) 日磊( 13 ) 通过观察可以发现玩已被消去，( 12 ) 式的右边关于y 是二次的，关于f 是线性的 ( 13 ) 式的右边关于f 是二次的，关于y 是线性的不失一般性，考虑( 11 ) 式右边的第一 项定义为日l 的第( i ，j ) 个元素，- - b 。 1 为b 1 的第i 行有： 因此 b 1 9 ( f t b l y ) = y t 1 旷5 ： y 了瓦 p ( 拶t 碱岛) z ， 注意等式右边作用在f 上的矩阵是一个向量和自身的外积，是一个秩一的矩阵，是非负定 的显然对( 1 i ) 式右边每一项重复以上过程，则( 12 ) 式右边可写成 m b dz 丁b ；) g = d 2 ( 1 ，4 ) 2 = 1 因此d 。是一个非负或正定阵，它的元素是关于向量y 的元素的二次函数同理可得( 1 3 ) 式的右边： 孵( 2 t b ，洲= d z y ， ( 15 ) t = i d 。是一个非负或正定阵，它的元素是关于向量 的元素的二次函数 设z = f i ，盯= d ：按d f 方式定义，即出现在d z 中的f 的元素用。中的对应元素 代替，由于上) 2 是关于向量f 的元素的二次函数。所以d i = d 。口2 定义a = a b 。印” 弘 r辟 ，脚， 玢 反 。皿 j j 曲 b t 萝 b 吖 砖疵船ee 复旦大学硕士毕业论文 有 伽= d y x a , z 7 z = 1 ， a t 。= d 。y a ，y t y = 1 、 定理1 1 1 9 t l s 问题 蜓毋i n m 萎( 。一玩) 2 一t b ( b ) y 2 o ：r _ 1 其中a i 、i = 1 ，m 是向量a r ”的元素b ( b ) = 日o + 6 l b l + 6 。b 。兄p 。为以 向量b r m 作参数的仿射矩阵函数，晟印“，i = 0 ：1 ，m 为给定的矩阵则它的解 由下面生成： f 叫找到满足下面条件最小的f 及其对应的u ，u a v = d u 丁，u t d 口u = l ， a 丁u = d “ 丁，y t d u 口= 1 、 其中 = i 曼= 1 鼠d “由d 。u = 圣曰 ( t t b ) “定义 d 。是一个正定或非负定矩阵，d 。 的元素关于u 的元素是二次的d 。由d 。u = b 。( “t b 。v ) v 定义d ，是一个正定或非 负定矩阵，d 。的元素关于7 3 的元素是二次的 俐向量y = u 川u m 忙向量b 的元素b k = 。一“t b k f ，七二l ，仃。 证明由( 16 ) 得 ，a y = y t a 7 z = x t d 目3 ：0 - = y t d 。y a( i8 ) 由( 1 1 ) 得 曼( 啦“。) 2 ：( 1 t b 。) 2 ：曼( x t b l t bx t b 。) 2 口2( 啦“。) 2 =。) 2 = 。) 2 口2 2 2 1 ：。1 ：t i 曼 b 。( 。丁鼠i m y l ) 】矿。：x t d y z 。z ：z r 4 。 ( 19 ) ：，曼限( 。丁鼠y ) 】矿2 ：z a z ：，4 一 叫 t = 1 如果( 珏，r ，u ) 是( 1 7 ) 的解那么 将u ，u 标准化得 r a v = ( u 于d u 札) 丁= 丁 4 南= 蒜静川i ) ( 11 0 ) 复旦大学硕士毕业论x d t 兰： 1 1 1 v = | 【口 i ：盯= 丁l | l i l | ”i i 赫南圳) 由( 1 9 ) ，( 11 0 ) 得 7 。7 却a = 篙a 南( r 忆i ii i 刮) = 高需( r ) 2 = r 2 - ( 1 1 1 ) 这表明我们要找最小的r 由( 2 ) 得 k = 。t 一赢取丽v 。2 - - u t b k v t 1 2 器础知识 正交性一组向量 z l ，。2 ，z p r ”是正交的当对任意i ，都有z 巧= 0 如果 z t q ：6 。则称为单位正交直观的说，正交向量是最无关的，因为它们指向完全不同的向 量 r m 中一组子空间s 1 ，岛称为相互正交的，如果对i j 都有z t y = o ( z & 、9 s ，) s 兄“的正交补是由 s 1 = f y r ：y t z = 0 ，v x s ) 所定义，不难证明r a n ( a ) 1 = n u l l ( a t ) 如果向量v l ，讥是单位正交且张成彤“中的子 空间s ，则它们形成s 的一组单位正交基 如果q r m m 满足q t q = ，则称其为正交的如果q = q l ， ， 是正交的， 则吼形成r m 的单位正交基如果u 彤具有单位正交列，则存在即。”。使得 v = f k1 纠是正交的，且r n ( h ) 1 = 7 1 。n ( ) 2 范数在正交变换下是不变的，这是因为若q t q = ，则i i q - z l l ! = z 了1 q 7 q z = z 7 1 z = 巨矩阵的2 范数和f r o b e n i u s 范数关于正交变换也是不变的特别的，对于维数适当 的正交阵q 和z ，有i i q a z l b = i i a i l f 和1 q a z i i 。= i i a i l 2 定理2 6 倚异值分解p v d ) j 设a 是实m n 矩阵，则必存在正交阵 u = ”，u 。 驴一 口 使得 复旦大学硬士垡业论文 v = v l ，仉。 r “ u t a v ：d i a g ( a l ，、唧) r m 竹p = m i n v n ，n 其中盯l2 盯222 仃口 0 定理3 6 设为c “上的酉不变范数，则有 知 a b 1 1 i a i l 21 _ b m v a c ”。”，v b c 。” a b l l 曼 i a i | | i sh v a c “，v b g “” 定理4 【4 设a ，b = a + e c “，a ，b 和e 皆为h e r r n i t e 阵，它们的特征值分别为 a 1 2a 。，肛1 肛。，1 三e 。 a 。+ e 。胁a 。+ 5 1 ，i = 1 8 定义1 c “内所有f 维列空间的全体，记作g 7 定理5 【4 】如果是c “上的范数，则i i p h ( z ) 一尸k ( w ) | | 是g ? 上的度量，其中z ，w 凹， 如果1 是c ”上的酉不变范数，则 i r r ( z ) 一p r ( w ) | l 是g r 上的酉不变度量 供中p r ( z ) 斥( w 分别表示到咒( z ) ，r ( ) 上的正交投影箅子j 定义2 设z ，w 凹。令 z 1 = z ( z ”z ) 一，l = w ( w ”w ) 定义 e ( z ，w ) = a r c c o s ( z f 阢w 甲z 1 ) 0 定理6 4 对于谱范数，有等式 | | s i n e ( z ，w ) h = i i 屹一p 怯vz ，w 曰 第二章算法分析 2 1算法推导 由第一章知我们需要求解非线性奇异值问题 a y = d z 口，x t x = 1 4 7 z = d z y o 、y t y = 1 即求奇异三元组( x ，正g ) 使之满足以上方程 通过观察可以发现( 2 1 ) 等价于求解非线性特征值问题 ( ，：，吾) ( ：) = ( 气9 。羔) ( 。y ) 盯，z r z = ，v r v = - 其中d 。，d g 为对称正定或正半定矩阵，且关于z ，y 是二次的 2 1 1 乘幂法 在文【1 中给出了基于q r 分解的反幂法它是如下算法的一个改进形式 算法1 乘幂法 j 选取z o ，y o ， o ，且lz o | | = 1 ，| | ，o | _ = 1 2 迭代计算，f o rk = l ，2 ，d d 形成矩阵d 。，d 。 计算x k + l = a d 。k y ， 规范化吼12 赫 计算玑+ l = a _ 。d ”k x k + 1 ， 计算a 女+ 1 = j 弧+ 1j j ， 规范化肌l ：赫 以下我们给出三种新算法 2 1 2n e w t o nr a p h s o n 迭代 ( 2 1 ) ( 22 ) 由于牛顿法在非线性问题中的广泛应用，以下我们考虑用n e w t o nr a p h s o n 迭代来求 9 复旦大学项毕业论文 解非线性奇异值问题对问题( 22 ) n e w t o r a p h s o n 迭代可以写成 其中 ( + a ) a 悖十可) = d ”+ 。( z + z ) ，( z + z ) t ( z + 。) = l ( a 十a a ) a 7 0 + a x ) = d 。+ 。白+ ) ，( y + a y ) r + a y ) = l 先考虑d 。的第一项有 所以 d 。= b i y ( 3 。g ) 7 ，d 。 b 1 ( y + a y ) ( y + y ) 丁b f = b l ( 掣掣r + y d x y 丁+ a y y t + a y a y t ) b r b l y y 了1 b t + 口1 y a y 了1 b + b 1a y y t 口 + b 1 s y a y 丁b ， l ( ) b l ( v + a y ) ( 可+ 可) r b _ + 。) = ( 日l y y t b t + s l y a y r b f + 日l g y y r b t + b l a y a y t b f ) ( z + 。) b l y y 丁口 z + b 1 y a y t b f z + b l d a y y t b f z + b l a y a y 7 1 b t x + b l y 可t b l z + b 1 y a y ，b f z + b 1 a y y t b z + b l a y s y 丁b j z 保留一阶项可得 b 1 ( g + g ) 国+ a y ) r b f 0 + a x ) b l y y r 曰 。+ b l y a y r b 。+ b 1 a y y t b z + b 1 y y r 日l z 综上有 = b 1 y y r b 。+ b l y x r b l a y + y t b t ：r b i a y + 口i y y 7 茸1 z mmmm d * + ( z + z ) b i y y r b t z + b i y x t b 。g + y t b t x b i a y + b i y y t b ，z l = 1i = 1t = 1l = 1 同理可得 mm 县。g 可t b z + ( b 。g 。7 b ：+ t = lo = 1 mm e t b 。b 。) z x v + b ，可9 t b ，。 l = lz = 1 d z + a 。佰十g ) b t x z 丁b 。+ ( b x y r 口 + t = 10 = l mm z7 1 b ；日_ ) z + b - z z ? 置 2 = l2 = 1 7 z 丁0 日z 丁0 口 m 复旦大学硕圭毕业论文 又因为 ( + a ) 。4 ( f 十a y ) = a a y + a a a y4 - a a a y + a a a a y a 4 y + a a a y4 - a y a a ( a + a a ) a t ( 。+ z ) = a a r z + a a 丁a x + a a a r z + a a a r 。 a a r z + a a 了1 a z + a t g a 由( z + a x ) 于( 茁+ a x ) = 1 知x t a x = 0 所以可得迭代方程 m，nm d y z + ( b i y z t b 。+ 1 b ，。b 。) 可+ b 。g g t s a x = a a y + a a a y + a y a a t = 1t = l z = 1 即 mm d 。g + ( s z v 7 b + x t b 。y b t ) a x + 1 b z z t b 。a y = a a t x + 入4 t z + 4 ，z a t = 1 z 7 a z ：0 mm d f a x + ( 兰b y x 7 _ b ，+ 至y t b ，z b 。一a a ) a y a y a a = a a y d 口z ( ks z z ，醪+ 墨，b 。g b ，一a a t ) z + 仇一舻z a a = a j 4 7 。一仉g ( 23 ) x t a z ：0 算法2 n e w t o nr a p h s o n 迭代 f 给定初值x o ，o ，a o 2 迭代计算，f o rk = l ，2 ，d o 由迭代方程( 23 ) 计算a x k ，a y e ，k 计算。k + l = 。女+ z k ，可e 十l = y k + a y m ，a k + 1 = a 七+ a 。 规范化2 鼢，蚍- 2 赫 2 1 3r a y l e i g h 商迭代 由于r a y l e i g h 商迭代是求解对称特征值问题的有效算法，我们考虑将r a y l e i g h 商迭代 作如下推广 复旦大学硕士毕业论塞 对非线性特征值问题( 22 ) 定义它的t g a y l c i g h , 商为 定义矩阵 p ( z ，可) 兰：丝望望三墨：兰 x t d 9 z4 - y t d z y 注意万是对称正定阵 算法3 r a y l e i g h 商迭代 给定初值z o ，o 且忙o i l = 1 ，i9 0 | | = 1 2 迭代计算，f o rk = 1 ，2 ，d o ： 形成矩阵d 。，d ，。 使 由公式( 24 ) 计- gp ( x ky k ) 解a o ) - - p ( x k , y k ) d y 0 ) ) 规范化= 翻胁+ ，2 赫 该迭代的数学基础是 一 p 。丽 ，( p ) = 幅z p 晚恬 达到最小，其中n 恬定义为峪喙= 。t 晚 2 1 4 特征向量法 1 2 ( 24 ) ( 2 ，5 ) ( ：) 当d 。d 。固定时原问题可看成广义特征值问题，因此我们考虑如下算法 算法4 特征向量速代法 给定初值z o ，o 且忙o l i = 1 ，【| 加i i = 1 2 迭代计算，f o rk = 1 ，2 ，d 。j 形成矩阵d 。，d “ 、 z o d0 ，一 = 一d 、， 4 oo 驴 ，、 | | 一a 、，ll l 1 + + r y ， 复旦大学硕士毕业论又 由等式 计算出x k + l 规范化z k + 1 玑+ 1 使其为对应最小口的特征向量 翻胁+ t 2 2 算法收敛性 2 2 1 n e w t o nr a p h s o n 迭代收敛- 陛分析 舰隹卜降麓 1 3 记c = 曼l i b 。| | 2 + h a i l 若对所有的，d i l 存在且一致有界，即l i d ；1 i i d 则当 d g | i z o 】| 0 ，使得 i i a i l 2 茎。，忖1 i i ：而1 ， 则对于c ”“上的任一种酉不变范数l ，有 s 掣 证明由定理2 和题设条件，有 i l x l lsi i b - ji i 。陋x l l 墨掣， 因而 i | b x i l ( q + d ) i l x 毗 复旦大学硕士毕业论文 另一方面，有 x a i l | i a i t 2 1 x 1 。i | x l l c i i 日x i i l i a x i l 6 | | z 定理8 - l 2a ，a = a + e c “皆为h e r r r d t e 阵，a l 是a 的单特征值，。1 是相应 的特征向i - ，# i - 且1 l 。1 1 1 2 = 1 并假定x = ( 3 7 1 ，x 2 ) 与x = ( 孟1 ，x 2 ) 为n 阶酉阵，x l 与 亩l c “，使得 x 日4 x = ( ：三。) ，趸w 五更= ( ：羔：) 令r = a x l 一z l a l 如果 a 1 = o + 6 ，a ( a 2 2 ) 8 ， 则对于g 上的任一酉不变范数川l ，有 i i s i n 0 ( 巩训忪学 证明由条件知 r = a 。，一z 。- 。= t i - ，叉；，( ：差。) ( 霎；) 茁一z ，a t = j 1 窑1 童f 。l + 瓦五2 2 j 碍。1 一z 1 a 1 因而 霹r = a 2 2 ( 霹z 。) 一( 稆。) ， 令z = x 岁9 1 它满足方程 a 2 2 z z a l = x 夕r 其中a i l = 百 石墨i ，t l a - i l z 曼a 由引理2 及( 霹r ) h ( 霹r ) s r ”兄有 s 掣掣 由引理1 知 l is i n 0 ( m _ 1 ，量，) l l = 忙 复旦大学硕士毕业论又 1 6 定理9 h 设ae c ”a 1 是，l 的单特征值，3 5 1 是相应的特征向量，并且f z lj2 = 1 设x = ( z ”y 2 ) 是一酉阵，使得 x ”a x = ( ：4 a h 盟) ，x ”e x = le 1 1 易f s 。) d = 1 1 ( 一4 2 2 ) 1 i i ；1 ，= l i e i l 2 ，q = l 。，7 = i g l l z 如果 并且 吖( 叩+ ) f 占一2 1 2 1 五 则存在p c ”一。，满足i l p l l 2 丁暨矗，使得叠1 = x l 十x 2 p 张成a + e 的不变子空间 只 1 ) 与冗 ，) 之间的距离 s i n 邺( 训，脚1 ) ) 而斋 反= ( ：”墨) ，a = ( 0：) ，。= ( i ) 有 玩k z + 1 = h a 魂+ 1 ，a 一1 z z k + l = a k 。“1 其中a 。是a 一- 反。的最大特征值，z k + 1 对应的特征向量令 则有 从而有 0 = s i n ( z ，z k + 1 ) z k + 1 = 巩4 - a z ，i a z l | 口 d ，= d 。+ a d ；。，忪d “| i 4 c 2 咖( z k + l ，z k - - 2 ) e r r m i算法乘幂法 n e w t o nr a p h s o n 迭代 r a y l e i g h 商迭代特征向量法 l 误差( ” 1 5 1 0 4 e 一0 1 110 3 1 8 e 0 1 129 0 0 8 e 一0 1 114 8 2 8 e 一0 1 1 i时间( s ) 90 6 3 05 2 9 7 063 2 9 02 54 0 7 0 i 迭代步数 1 4456 所求得的奇异值为： 2 8 97 4 7 8 我们将迭代的误差曲线图绘制如下：细实线代表n e w t o nr a p h s o n 迭代，”+ ”曲线代 表r a y l e i g h 商迭代，”曲线代表特征向量法，”o ”曲线代表乘幂法 ，。、 有上可知乘幂法具有线性收敛速度，n e w t o nr a p h s o n 迭代，r a y l e i g h 商迭代和特征 向量法具有二次收敛速度其中n e w t o nr a p h s o n 迭代和r a y l e i g h 商迭代所得的解与初始 值的选取有关我们可用乘幂法迭代到n e w t o nr a p h s o n 迭代的局部收敛域，再用n e w t o n r a p h s o n 迭代进行加速 复旦大学硕亡毕业论x 参考文献 1 b d em o o r 、s t r u c t u r e dt o t a ll e a s ts q u a r e sa n dl 2a p p r o x i m a t i o n a 1 9 e b r oa p p l ，1 8 8 1 8 9 ( 1 9 9 3 ) 1 6 3 2 0 5 2 a k eb j 6 r e k 。ph e g g e r n e s 、a n dpm a t s t o m s ，m e t h o d sf o rl a r g es c a l et o t a l e a 。s ts q u a r e s p r o b l e m s ，s i a mjm a t r i za n a l a p p l ，2 2 ( 2 0 0 0 ) ，p p4 1 3