（计算数学专业论文）带限函数外推算法研究.pdf

中文摘要 摘要：函数f ( f r ) 能量有限，即r f ( t ) 1 2 t 时，f ( t ) 的值为零。若在频域中以不 大于寺的频域间隔对( f ) 的频谱7 ( 缈) 进行采样，则采样后的频谱夕( 等) 可以唯 一的表示f ( e o ) 其重构公式为 7 ( 咖量夕( 等) 篙署 2 2 带限信号基本，性质 带限信号是我们经常遇到的一种信号，在采样定理、离散傅氏变换、带限信 号外推以及各种数字信号处理中主要的对象就是带限信号，它也称为频谱有限信 4 号。本节主要讨论与带限函数有关的一些基本定义及带限信号的一些基本性质， 以便为后面的讨论及数值模拟打下基础。 2 2 1 频谱有限连续信号的定义 定义2 2 1 t 1 1 1 对f ( t ) ，t ( - - o o ，o o ) ，若f ( t ) 厶( - - o o ，c o ) ，而且其傅氏变换( 缈) 满足 f ( c o ) = 0 ，lc o l o r ，则f ( t ) 称为o r 频谱有限连续信号。 这里，f ( t ) 厶( 一0 0 ，) 是指( ，) ，t ( - - o o ，o o ) 为能量有限，即 ii ( f ) j 2 d t 将全体盯频谱有限连续信号形成的空问记为嚣，它是一个希尔伯特空间，是 厶( 一0 0 ，o o ) 中的一个线性子空问，与厶( 一o r ，仃) 同构。 2 2 。2 仃频谱有限连续信号的性质 性质2 2 。2 1 任何仃频谱有限连续信号的傅氏变换夕( 缈) 在( 一仃，盯) 中是平方可积的，而且也 是绝对可积的。 因为从定义可知( ) = 去e 夕( 彩弦妇d 彩，由于( f ) l z ( - - o o ，o o ) ，又根据 p a r s e v a l 定理可知，7 ( 缈) 一定在( 一仃，盯) 中是平方可积的。即 石1e m 脚彩= i ( ，廊 丑 a o _ r l i ma = 0 。 ( 2 3 2 ) - + 0 0 ( 2 ) 若将对应的五的特征函数记为唬( f ) ，则么( f ) 具有以下的正交性： 纰肌肛颤= z 篓 胁肌舻耻 耄 亿3 ( 3 ) 函数织( f ) 等于其自身的傅立叶变换的截断： 珊，付赤删懒b - j 等扣三 识( f ) 弓( f ) hb 佩( b o j )( 2 3 4 ) 其中 只c 缈，= ￥i ：i 苫： 黔洲品 ( 4 ) 织( f ) ， 们) 等等把枞 ( 5 ) 对任何( f ) 碍，有厂( f ) = o o 口。么( f ) ，其中q = e 厂( f 溉( f ) 出， 故有 i if ( t ) 1 1 2 = e i 巾) 1 2 如= 蠢 ( 6 ) 对任何g ( f ) l 2 ( - t ，r ) ，则在( 一r ，t ) 中，g ( t ) 可以展开为 其中 及有 g ( f ) = b k 痧k ( t ) ，i t l 0 ( v x 彳) ，忙l l - 0 营j = 0 ( 正定性) ； ( 2 ) f i x + y i i 0 ，使对一切工x 都有i | a f i ：c l l x l l ，则称丁是有界的。 如上的c 之下确界称为r 的范数，记作i l r i | 显然 i i 丁| i = s u pi ia l | 2 i i = i 记全体从x 到y 的有界线性算子为l ( x ) 。 对每一个从h 。到日：的有界线性算子r ，总存在一个从h ：到h 。的有界线性算 子r ，使 ( t x ，y ) = ( 工，t y ) ，v x h i ，y h 2 成立。 定义2 4 5 t 1 3 】自伴算子 设t ( h ) ，若t = t ，则称7 为自伴算子( 或自共轭算子) 。 定理2 4 6 t 1 3 】 设x ，】，都是线性赋范空阳j ，丁是x 到y 的线性算子。则下述条件等价： ( 1 ) r 在x 中某点连续； ( 2 ) 丁在x 中所有点连续； ( 3 ) r 是有界的。 定义2 4 7 t 1 2 】紧算子 设x ，y 是b 空问，设a ：x 专y 线性，称a 是紧算子，如果彳( e ) 在l ，中是紧 集，其中最是x 中的单位球。 定理2 4 8 1 3 ( s c h w a r z 不等式) 对内积空间x 中任意两个向量五y 都有 i ( 工，y ) 酬z 川i y i i 定理2 4 9 【1 3 】 如果t ( ) ，则丁是自伴的( a ，工) ，x h ，恒为实数，即 ( 7 x ，工) = ( x ，t x ) = ( t x ，z ) 定理2 4 10 1 4 1 h i l b e r t s c h m i d t 定理 设a 是h i l b e r t 空间h 上的自伴紧算子，则存在对应于特征值f 以) ( 以0 ) 的特 征向量构成的标准证交系 巳) ，使得每一个元石h 可唯一表示为 工5 乙口t e k + x o ，j _1 k 其中，毛( 彳) ，即满足“= 0 ，同时 血= 五吼气 并且如果包) 是无穷的，则 l i m 五= 0o n + 定义2 4 1 1 1 1 8 】如果c 1 ( 即存在l 阶连续导数) 类函数厂在区域q 上处处满足下列 条件 a f ：0 ， a z 那么厂称为q 上的全纯函数。 定义2 4 1 2 【18 】般来说，解析延拓就是扩充全纯函数的定义区域，设以( z ) 是定 义在区域d o 上的全纯函数，如果存在区域q3d o ，以及定义在q 上的全纯函数 厂( z ) ，使得厂( z ) = f o ( z ) ，v z , 9 0 ，那么就称厂( z ) 是f o ( z ) 到q 上的解析延拓。 2 5 正则化方法的相关理论 带限外推问题当已知的数据包含噪声或干扰时，此时带限外推是一个不适定 问题。对于不适定问题的解决，一个普遍的框架是采用证则化方法( 策略) ，即：用 一簇与原问题相“邻近”的适定问题的解去逼近原问题的真解。例如，若a 为正 定算子，则第二类算子方程 a z + 岱z = “，口 0 ( 2 5 1 ) 当参数口较小时与第一类算子方程 a z = u 是相“邻近”的；而此时算子方程( 2 6 1 ) 对于任何口 0 都是适定的。又如，若令 m ( z ，u ) 爿ia z ui j 2 ，m “( z ，u ) ：i ia z u1 1 2 + 口忙1 1 2 ，则极小化问题 m i n m 。( z ，“) ， 口 0 当参数口较小时与下述问题： m i n m ( z ，“) ， 是相“邻近”的。 显然，从逼近的角度来看，参数口不能取得太大；否则，辅助问题将与原问 题相差太远。然而，从数值稳定性的角度来考虑，参数口又不可取的太小；否则， 将因把原问题的不适定性“继承”太多而难于处理。 t i k h o n o v 于1 9 6 3 年在其开创性的工作 2 1 1 1 2 2 提出了求解不适定问题的正 则化方法( r e g u l a r i z a t i o nm e t h o d ) 。 考虑如下的算子方程： a z = “， z f ，u u ( 2 5 2 ) 的求解问题；其中a 是由度量空间( f ，, o f ) 到度量空i 、日j ( u ，) 的连续算子，其逆 算子a 。存在、单值但不连续，且a 叫不是在整个空间u 上有定义，此为一个不适 9 定问题。 设z ，是对应于方程的准确右端项的精确解 a z 7 = u 7 - ， z 7 f ，u r u 在u r 不能准确给出时，只能得到它的具有误差水平万0 的近似：p ( u r ，) s 6 。 在这种情况下只能寻求式( 2 5 2 ) 的近似解，即刁的按度量p f 的近似，从而关键是 如何定义与计算近似解。t i k h o n o v 首先提出了用正则化算子给出近似解的思想。 定义2 5 1称一个由度量空间u 到度量空间f ，且依赖于参数口 0 的算子 r ( u ，口) 为方程( 2 5 2 ) 在u = u r 的邻域内的正则算子，假如它满足下述两个条件： ( 1 ) 存在4 0 ，使算子r ( u ，口) 对于所有的口 0 和满足条件p u ( u ，u 。) 万4 的任 意的u u 都有定义； ( 2 ) 存在这样的万的函数口= 口( 万) ，对于任给的g 0 ，存在万( f ) 艿，若 ( ，u r ) j ( s ) ( v u j u ) ，便有p f ( z 。，刁) 占，其中= r ( u j ，口( 万) ) 。 按照上述定义，若p v ( u 占，u ，) 万，则可取z c t = r ( u j ，口) 作为具有近似右端项1 , l 占 的方程a z = u ；的近似解，式中口= a ( 8 ) 与原始数据及其误差万有关。称这个解 为方程a z = u 的f 则解，口为正则参数，我们称由j 下则算子得到的近似解的方法为 j 下则化方法( 策略) 。 当然，可用上面的两个定义来判断算子r ( u ，口) 是否是正则的，我们希望在与 参数口有关，并且对所有u u 和任意口 0 的定义的实现映u 到f 的算子r ( u ，口) 中问，能直接和方便的划分出对u u 连续的算子。 在t i k h o n o v 正则化方法中，由于j 下则解，= 见夕由下述e u l e r 方程 ( 彳彳+ a e ) x = a y ，v a 0 所决定，故j 下则算子可表示为 如：= ( 彳a + 口e ) - 1 a ：y 专x 基于紧算子a 的奇异系统 ( 旯，“，v ，) ) ，我们得到心j ，的下述表示： r a y = a + - - 巧2 ( y , _ ) “，y y ， 于是，只需取g 似，名) = 去，代入上式即得 萎癞1 吵，= 姜掣协脚 这个函数g 被称为正则滤波器。 l o 3 1 引言 3 带限函数的外推算法 带限函数外推问题是一类经典的信号恢复问题，在许多领域都有应用，例如 频谱估计【7 l ，限制角的图像重建问题【3 5 j ，和数据压缩方面都有很强的应用价值。带 限信号外推是一类经典的信号恢复问题，包括频域带限信号在时域上的外推和时 域上带限在频域上两种情况的外推。本章首先筒述频域上和时域上的外推问题， 然后给出经典的g p 算法和s a n z h u a n g 的定理。之后，提出两种求解带限外推问 题的算法，l a n d w e b e r 迭代算法和共轭梯度算法，并在理论上证明提出的两种算 法对于外推问题的收敛性，同时证明g p 算法实际上等价于l a n d w e b e r 算法求解 外推问题时，松弛因子取1 时的迭代情况。实际上，本文提出的算法对于频域上 和时域上的外推问题都适用，本文仅就时域上的外推问题展丌证明。 3 1 1 频域上连续外推问题 设函数厂( f ) ，t r 的f o u r i e r 变换形式是 f ( o ) = f ) ( 功) = lf ( t ) e 1 “以，缈r ( 3 1 1 ) 进一步假设f ( t 0 ) ，彩r ，已知。那么方程( 3 1 1 ) 为第一类积分方程。它的解f ( t ) 易 于从f o u r i e r 逆变换得到， 1m ，、 f ( t ) = f 1 厂) o ) = 二ll 厂( 缈) p 1 “d 缈，r ( 3 1 2 ) z 7 一” 现在我们考虑厂( 缈) 只知道有限区域【_ 盯，盯】，其为尺的子域。我们用( 彩) 表示 在区间卜仉盯】上的函数值。f ( t ) = 0 , ta - t ，t 】，卜丁，z 】为只的子域。频域上的带限 外推问题为，已知( 力) ，缈【- - o ，盯】，求解厂( 缈) ，国( 咱，o o ) 。 3 1 2 时域上外推问题 本文主要研究时域上( 频域带限) 的外推问题，所以分别说明时域外推时，连续 外推问题和离散外推问题。 设函数厂( 缈) ，国r 的f o u r i e r 逆变换是 1m6 厂( f ) = f 叫) o ) = 圭1 f ( o j ) e 泐d o ，t r ( 3 1 3 ) 假设厂( f ) ，t r 已知，( 3 1 3 ) 为第一类积分方程。它的解f ( c o ) ，易由f o u r i e r 变换 得到， f ( c o ) = f ( f x a o = if ( t ) e 叫甜出，缈r( 3 1 4 ) 进而，我们有p a r s e v a l 关系， l f ( t ) g ( f ) 出2 寺 厂( 缈) g ( m ) d c o ( 3 1 5 ) 其中，表示复共轭。 厂( f ) 是带限函数，即( 脚) = l ”f ( t ) e 一泐d t = 0 ，当1 7 0 引一仃，仃】。b ( f ) 是区间 卜丁，刀的特征函数，e ( 缈) 是区间卜仃，盯】的特征函数， b c ，= ￥i ：i 吾； e c 国，= ￥l ：i 吾： c 3 6 ， 带限外推问题即，设f ：r 哼r 是带限函数，r 是一个币常数，给定有限区间 上g ( t ) = f ( t ) p r ( f ) ，找出厂( f ) ，t ( 一o o ，o o ) 。 带限外推问题可由下面的第一类积分方程表示 亡if ( c o ) e d t o = 厂( f ) ，t - t ，t 】 ( 3 1 7 ) ，口w * - - o 其中( f ) ，t 一t ，卅已知，e 7 耐已知，7 ( 国) 未知。由方程( 3 1 7 ) 解出夕( 彩) ，再对7 ( 缈) 作f o u r i e r 逆变换，即得( ，) ，t ( 咱，o o ) 。 下面简单介绍离散外推问题： 离散序列带限：给定一列y ( j ) ，一n j ，在卜，一k o 上带限，即 n 2 x i j k y ( j ) e 肘= o ，k o _ - t k 阵n ，m = 2 n + i ，d f t n f b 度。 离散外推问题可描述为，对于带限于【一，一】的序n y ( j ) ，一n 5 j n ，给定 一段x ( j ) = y ( ) ，- l j l 其中l n ，得出y ( ) ，一n j n 。 本文主要研究时域上的外推问题，带限函数外推方面的研究有许多经典的成 果，如g p 算法，s a n z h u a n g 的定理，j 下则化外推算法等，本文将在前人的理论 基础上提出两种新的外推算法l a n d w e b e r 算法和共轭梯度算法。 3 26 - p 迭代算法简介 3 2 16 - p 迭代算法 对于3 1 2 节叙述的连续情况的外推问题，已知g ( f ) = 片( f ) 厂( f ) ，其中 渺跚蝴吐吲，。 g p 算法迭代过程【1 】 1 2 g ( 缈) = 瓯( 缈) = f r g o p 一“d t ，g o ) = g 。( f ) 夕。( 缈) = g - i ( 缈) 弓( 缈) ，其中层( 缈) = ￥i ：l 吾： 于是 z ( f ) = 7 。( c o ) e 砌d 彩 g 。( f ) = z ( ，) 十【厂( f ) 一z ( 纠弓( f ) = g ( f ) + 1 弓( f ) 】正( f ) r n “ 厂。( 缈) = 厂，t ( 彩) + 上丁e 1 纠 g ( f ) 一l p 删。一t ( 国) d 缈】出) 只( 国) = 死( 珊) + 只( ) p 咖【g ( ，) 一e e 砌死( o ) d o d t ，( 7 。( 功) = o ) ( 3 2 1 ) z ( f ) = z 一- ( f ) + g ( r ) 皇善竺 子! d f l 五一。( f ) 墅云竺 了尘d f 】 ( 3 2 2 ) 对于3 1 2 节中的离散外推问题，由 1 5 】我们知道，如果= l ，下面的步骤是 离散问题的迭代算法： ) 2 击量础) e k o - 础) ：互风的p 一，i 引k 【o , k o 七 胁 捌嚣鲫 b 2 对于3 1 2 节叙述的连续情况的外推问题，在进行离散计算时，离散迭代算法中的 参数可选择如下石( ) ：g ( _ ，) ，一j l ：【三】，：【罢警】：，【】表示的整数部 分a 为；莎长。 3 2 2g - p 算法收敛性 如文 1 】，为了证明迭代算法的收敛性，我们把带限函数f ( t ) 展开为 f ( t ) = 吼唬( f ) ( 3 2 4 ) 其中吮( f ) 是长球函数。 忙。 定理3 2 1 【1 1 第n 次迭代的函数无( f ) 可以写作 z ( f ) = ( f ) 一q ( 1 一以) 4 织( f ) ( 3 2 5 ) 五是( 2 3 1 ) 的特征值，与特征函数么( f ) 相对应。 证明：首先，假设， f ( t ) = 吮( f ) 我们需要归纳 z ( f ) = 4 峻( f ) ，以= 1 - ( i 一五) “( 3 2 6 ) 妻实上，( j 2 6 ) 对于玎= 1 成立。假设其对于某个刀1 成立。然后，根据( 3 2 1 ) ，( 3 2 2 ) 和( 2 3 1 ) 有 g 。( ) = 4 噍( f ) + ( 1 4 ) 噍( f ) 弓( f )( 3 2 7 ) 将( 2 3 1 ) 和( 2 3 5 ) 插入( 3 2 2 ) ，得到 + i ( ) = 4 欢( f ) + l 一4 ) 2 k 痧k ( t )( 3 2 8 ) 因此 + 。( z ) = 4 + 。氟( f ) 其中 4 + ，= 4 + ( 1 4 ) 五， 拄l ( 3 2 9 ) 以初始条件为4 = 五，解递归方程( 3 2 9 ) ，得到( 3 2 6 ) 。 将( 3 2 6 ) 应用于( 3 2 4 ) 的每一项，我们推出 z ( f ) = 吼 1 一( 1 以) ”】唬( f ) 于是得至l j ( 3 2 5 1 。 3 2 3 正则化的带限外推算法 许多算法对于观测数掘包括噪声或者不准确的时候， 厶( f ) = f ( t ) + r l a ( t ) ，t 一t ，t 】 重建的效果不是很好，其中r l a ( t ) 是噪声，它满足 眦) 1 2 t i t _ 6 2 文献 5 中，提出了下面的j 下则化迭代算法，其迭代格式如下： f o ( f ) = 百芴p r i f ( t 历) 芦 对刀= o ，i ，2 ， l + i ( f ) = 而p r f ( t ) + 警帮 这种迭代与g p 算法相似，但使用了币则化傅立叶变换取代了傅立叶变换。对于口 的选取，文章 5 中也推荐了一些策略。试验证明这种f 则化算法有比较好的抗噪 声，抗干扰的效果。 3 3s a n z h u a n g 的定理 g - p 迭代是一个漂亮的结果，但由于带限函数是解析函数，所以用原来的g p 迭代离散计算时，并不能收敛到原来的函数，所以有s a n z ，h u a n g 的结果。 定理3 3 1 1 4 使g ：卜t ，t 卜c 是仃一带限函数厂的一部分，使是一个正整数，满足 m ：望等是一个整数，如果z ( 七) ，一七满足 砌) 2 万1 。至z ( 七) 一一绑氏 ( 3 3 1 ) 工( ，) ：g ( 歹) ，：【尝】： 那么函数 啪) 2 万1 。荟狮矽 当专0 时，在r 上的每个紧集一致收敛于厂( f ) 。 这样带限函数外推的问题就转换为了求解方程组( 3 3 1 ) 的问题，如果方程 组解的结果较好则重建效果较好，同时如果解方程组的算法收敛速度快，则相应 外推算法收敛速度也会提高。 对于二维的外推问题，z h o u 和x i a 提出了下面的理论。 定理3 3 。2 使厂( f i ，乞) 是空i nl 2 ( r 2 ) 上( q ，吒) 的连续带限函数。石，互为两个f 数，使 眠z ) m 2 炳个收奸啪莉l j ，且使= 罢和吁嚣2 对所有的 j 下整数m 。，m ：都为j 下整数，对每对整数( m 。，掰：) ，让 。u ：芝芝啦( k 七：) e 1 2 州i 村：乙+ ：乙 ( 3 3 2 ) 。：( o f 2 ) = 艺z 叩：( 毛，七2 ) e 吨锄。 ( 3 3 2 ) 屯2 一k 州k 2 2 一女啊2 其中 o 警坛：= 【芝争】 乙啦( 局，屯) ) ，如为下面线性系统的解： m 以：) ：芝芝(毛，岛)j2州面警+k2tl_zmlm2 - - j l ( 3 3 3 ) 厂( 啊。，以：) = 艺 ( 毛，岛) i 啊帆肼j ，1 2 唧 ( 3 3 ) 上1 2 一 2 一t 叼 一吒，刀，k ，j = 1 ，2 ， 当m 。，m 2 专，在紧集r 2 上m 一致收敛于。 对于高维问题也应有类似的结果。 3 4l a n d w e b e r 迭代算法 本节介绍l a n d w e b e r 迭代算法的实现，以及该算法应用于带限函数外推问题 与g p 算法的联系。 3 4 1l a n d w e b e r 迭代算法 许多图像问题都可归结为下面的线性方程 a x = b ( 3 4 1 ) 其中观测数据为b = ( 岛) k 肘，并且图像是z = ( h ) k 数域k 可以是实 数域r 或者复数域c 矩阵a = ( 4 ，) 是非零的m 矩阵。图像重建问题是从观测数 据b 重建原始数据工。 1 9 5 1 年l a n d w e b e r 提出的l a n d w e b e r 迭代是 工= x 一1 + 彳r ( 6 一彳j 一) x 表示第k 次迭代后的x 值，丁表示转置。当j | a r a | | ： 0 ， ( 1 ) 如果( 3 4 1 ) 是相容的， 对于所有七0 有1 1 4i i 州，对于扛l ，s ，并且 0 p 2 以2 下面的条件成立 1 6 m i n ( p 2 以，2 - p 2 熊) = 佃 ( 3 4 7 ) 那么序列 x “) 是由( 3 4 6 ) 生成的，收敛于。( 彳，6 ) + e ( 么) ( 2 ) 如果( 3 4 4 ) 是不相交的，而且有下面的条件成立， ! i 。m 。l t k = o 并且以= 佃。 (38) 那么序列 x 佃) 是由( 4 容。 推论3 4 2 假e p = 1 1a l l i ，如果对七o ，0 p 2 以2 那么定理3 4 1 对于任何分割集合 都成立。 定理3 4 3 p = t t a l l 。，如果对七o ，0 p 2 终2 并且条件( 3 4 7 ) 成立，那么由( 3 4 3 ) 生成 的序列收敛于。( 彳，6 ) + 只( 彳) 工，即使( 3 4 1 ) 不相容。 3 。4 2l a n d w e b e r 迭代是一种正则化迭代 l a n d w e b e r ，f r i d m a n ，b i a l y 提出了求解方程k x = y 的f 则解的一种迭代算法 ( 以迭代参数m 的倒数二为币则化参数口对应于过滤函数 ，挖 i q ( a ，五) = l ( 1 一肌) 口，0 0 并用迭代法解此方程，即 妒= 0 和x 4 = ( 一, u k + k ) x 叫+ i r k + y ，m = 1 ( 3 4 9 ) 该迭代实际是求解二次泛函j - - * 1 lk x y1 1 2 极小值的步长为的最速下降法如下面 定理所说。 定理3 4 4 让序列 x ”) 定义如( 3 4 9 ) ，并且定义函数 l 伊：x r ，缈( z ) = j j k x - yj j 2 ，工x 它在z x ，的f r e c h e t 导数 矽( z ) j = r e ( k z j ，k x ) = r e ( k ( c z - y ) ，工) ，x x 在h i l b e r t 空间工，矽( z ) 可被看作与k ( g z y ) x 一致，因此 工“= z ”一t k ( k x ”一一y ) 是步长为的最速下降迭代序列 1 i e n - 二次式公式服从于烈z + 工) 一缈( z ) 一r e ( k z - y ，纠= 妄l | k x l l 2 并且因此 l 缈( z + x ) 一t p ( z ) - r e ( k z y ， j ) i i 1l i k i 石1 1 2 证明了映射x 哼r ( k z y ，g x ) 是缈在z 点f r e c h e t 导数。 方程( 3 4 9 ) 是f f y x ”的线性迭代公式，通过对，z 的归纳，可看出，有，= ry ，算 子 吃：y x 定义为 吃：= ( i - p k 足) k ，m = 1 ，2 ( 3 4 1 0 ) 紧算子k 奇异值系统( 毛，x j ，y j ) ，可以看出ry 有下面的形式 吃y = 乃( ，一叫) ( y ，y j ) x j = 1 一( 1 一所) ”从y ) x j j f l “j ：主掣( j ，川一 n 2 0 。、j 其中过滤函数 q ( m ，彳，) = 【l - 0 一a ；) ”】。 定理3 4 5 ( a ) 使k ：x 一】，为一个紧算子，并且使0 1 l lk1 1 2 空1 1 ( 3 4 1 0 ) 定义线性有界 算子如：y x 。这些算子心定义了一种离散f 则化方法，参数口= 1 m ，m n ， 并且i i 如临朋。序y l jx 帆占= ry 占如( 3 4 9 ) 那样迭代计算，也就是 x o 声= 0 并r x 彬= ( ，一1 2 k k ) x 剃，j + p k y 5 对m = 1 ，2 每个m ( j ) 一0 ( 万一0 ) 且万2 聊( 万) 一o ( 万一0 ) 是符合条件的。 ( b ) 使工= k z k ( y ) 当l fz | i e ，且0 q c 2 。对每个r e ( j ) 的选择 c 。万e 驯哪乞詈c 一万m ( 万) 乞了 下面的估计有效 i i 工”占 y j l 阵c 3 万e c 3 依赖于c 。，c 2 和。因此，对于i l ( k ) 。1i l el a n d w e b e r 迭代是最佳的 ( c ) 现使石= k + k z k + k ( x ) 且忙临e ，0 c l o ，我们能够找到一个整数，使 口；g 当k 专c o 时，特征值五 1 且单调趋于0 。因此卜以 l ，并且 1 一乒暖 1 一声阴w ，k n 从上面我们可以推出 e = 口：( 1 一以) 2 ”+ 日；( 1 一以) 2 ” ( 1 - p a n ) 2 “口：+ 厂( f ) 。 3 4 5 截断误差 如果l a n d w e b e r 算法在第n 步的均方误差为 e = 口；( 1 一以) h ，o 朋 1 ，由( 2 3 2 ) 得，当k o 有，l 一以= 鱼 o ，以 a ， 1 一以 卜五，l e = 口；( 1 一以) 2 4 口；( 1 - 五) h = e 。 可知，l a n d w e b e r 算法如较好的选取松弛因子，相同迭代次数下，l a n d w e b e r 算法的误差小于经典g p 算法的误差。 3 5 共轭梯度算法( c g 算法) 3 。5 1 共轭梯度算法简介 共轭梯度法 设血= 6 ，其中彳尺删为对称正定矩阵，或厂( 曲= l ( a x ，z ) 一( 6 ，工) 用共轭梯 度法解，或求m 舢i n 。f ( x ) = 厂( x ) 极值问题，且产生 z t ) 近似序列， 以) 共轭方向 序列，瓴) 剩余向量序歹i j 。 纯) ， 以) ，也) 都是向量序列，对于刀= l ，2 n = 耥涵曲； 乙+ i = z 。+ 吃；毛= 0 ； r + i = r z 。a d ；r l = 6 ； 以= 一专芋：雪舅；以+ 。= ，：，+ + 尾吃 算法中n 为迭代次数。 在适当的条件下共轭梯度法是币则化方法，对此的证明是相当复杂的，请参 看【2 3 】。 3 5 2 预处理共轭梯度法 我们在运用共轭梯度法解决外推问题时，常常会遇到系数矩阵条件数较大的 时候，即方程组为病态方程时，为提高运算效率则用预处理的共轭梯度法。即对 方程组系数矩阵进行预处理，预处理方法【1 9 】如下所述： 设n 阶线性方程组为 a x = b ( 3 5 1 ) 式中，x 为n 阶未知列向量，a 为行以阶对称讵定矩阵，b 为胆阶己知右端列向量。 求线性方程组( 3 5 1 ) 的共轭梯度算法的迭代公式上面已经列出。让脚是矩 阵a 的不完全c h o l e s k y 分解，其中为下三角矩阵，d 为对角矩阵。 从以上迭代公式可以看出，共轭梯度算法只需存储矩阵a 的非零元素，使计 算机内存占用量最小。但是，当矩阵a 的条件数很大时，舍入误差造成这个算法 难于收敛，限制了该算法的实际应用。 i c c g 算法【2 0 】采用预处理技术，将大条件数矩阵迭代计算转化为小条件数矩阵 迭代计算，提高了算法的收敛速度。由于这个算法计算机内存占用量较小，收敛 快，已在实际中广泛得到应用。但是，这个算法需要存储与矩阵a 同样元素数目 的矩阵和d ，即比共轭梯度算法多存储一个矩阵a 。 由上所述知，共轭梯度算法收敛慢的原因在于矩阵a 的条件数太大。对称正 ， 定矩阵a 的条件数为c o n d a = 1 , n l a “，式中k 和九诅分别为矩阵么的最大和最小特 i l l 征值，显然，矩阵a 的k 。和以；。相差越悬殊，条件数c o n d , 4 越大，共轭梯度法也 就愈难于收敛。因此，加速该算法收敛的重要途径就是要设法把大条件数矩阵a 迭代计算转化为小条件数矩阵迭代计算，即设法通过变换降低k ，提高。使两 者彼此接近。 彳。皇( t 。! 主 三：j ；： t ! j 主 f a , l b ? l a i 4 b l 。匕1 = j i： l i a l 4 b i 。玩。a 4 4 圪j 匀，产生较均匀的特征值分布取瑶= 1 , i = 1 ，2 ，3 ，4 ，则得到= 辜，i = 1 ，2 ，3 ，4 。 新生矩阵a 中任一元素为口：= 包i 口，j 0