（计算数学专业论文）求解非线性不适定问题的共轭梯度法.pdf

摘要 许多实际应用领域归结为非线性反问题( 比如说参数识别问题，反散射问题， 逆s t u r m l i o u v i l l e 问题以及非线性第一类f r e d h o l m 方程的求解问题等) 的求解关 于非线性反问题研究的难点在于它的非线性性、不适定性及无限维性目前， 关于线性反问题理论工作已经相对比较完善，在实际应用中也取得良好效果；而 非线性反问题的理论和实践都还有许多需要完善的地方 本文主要讨论非线性反问题的共轭梯度解法首先我们直接用非线性共轭梯 度法对问题进行求解，并比较了四种非线性共轭梯度法在解决问题时的表现，数 值算例表明这四种算法是有效的其次我们用牛顿一共轭梯度法( n e w t o n - c o 方法) 对问题进行求解，在内迭代中使用了新的终止准则，并且我们首次采用了重要参 数c 2 随外迭代步数变动的选取方法。并与h a n k e 后验选取准则进行了比较，从数 值算例中我们可以看出n e w t o n - c o 算法的有效性和新准则的优越性 关键词；非线性反问题，不适定性，正则化方法，非线性共轭梯度法，c 外) 迭 代终止准则，n e w t o n c g 方法，内迭代终止准则 a b s t r a c t i nt h i st h e s i s , w eh a v ed i s c u s s e dt h ec o n j u g a t eg r a d i e n tm e t h o d sf b rs o l v i n gt h en o n l i n e a r i n v e m ep r o b l e m s t h ep r o b l e m si nm a n ya p p l i e dd o m a i no f t e n nb ef o r m u l a t e da san o n l i n e a r i n v e r s ep r o b l e m ( f o re x a m p l e ，p a r a m e t e ri d e n t i f i c a t i o np r o b l e m ，i n v e r s es c a t t i n gp r o b l e m ，i n v e r s e s t o r m - l i n u v i l l ep r o b l e ma n dt h ef i r s tn o n l i n e a rf r e d h o l me q u a t i o ne t c ) p r e s e t l y , t h et h e o r yo f l i n e a ri n v e r s ep r o b l e mh a sb e e nr e l a t i v e l yp e r f e c ta n dh a sf a v o r a b l ee f f e c ti nt h e a c t u a la p p l i c a t i o n h o w e v e r , t h et h e o r ya n dt h ep r a c t i c eo fn o n l i n e a ri n v e r s ep r o b l e mh a v em a n yd o m a i n st ob e p e r f e c t e d i nt h i st h e s i s , w et r yt ou t h ec o n j u g a t eg r a d i e n tm e t h o d st os o l v et h en o n l i n e a r i n v e r s ep r o b l e m s f 的l yw eu s et h en o n l i n e a rc o n j u g a t eg r a d i e n tm e t h o d st os o l v et h ep r o b l e m d i r e c t l y , a n dt h en u m e r i c a le x a m p l e ss h o wt h ee f f e c t i v e n e s so ft h em e t h o d a n dt h e nw ea d d o p t n e w t o n - c gm e t h o dt os o l v et h ep r o b l e m an e wi n n e rp o s t e r i o r is t o p p i n gm l ei su s e da n dw e c o m p a r ei tw mh a n k em l e n u m e r i c a le x a m p l e ss h o wt h es u p e r i o r i t yo f t h en c ws t o p p i n gr u l e k e y w o r d s ：n o n l i n e a ri n v e r s ep r o b l e m 1 1 1 - p o s o d n e s s , r e g u l a r i z a t i o nm e t l l o c t , n o n l i n e a rc o n j u - g 缸eg r a d i o n tm e t i l o d , o u t e l s t o p p i n gr u l e , n e w t o n - c gm e t h o d , i n n e rs t o p p i n gr u l e 1 1 原创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作除了文中特别 加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果参与 同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示 了谢意 签恕叁派遣日期；刀t 厂正幻 本论文使用授权说明 本人完全了解上海大学有关保留，使用学位论文的规定，即t 学校有权保留论 文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容 ( 保密的论文在解密后应遵守此规定) 签名舀投热獬，栅躲吖f 加 2 0 0 7 上海大学硕士学位论文 第一章预备知识 1 1 引言 近二十多年来，数学物理反问题已成为应用数学中发展和成长最快的领域之 一；之所以如此，在很大程度上是受其他学科与众多工程技术领域的应用中产生 的迫切需求所驱动【8 】8 在许多应用科学与工程技术研究领域，如生命科学、地球 物理、地质勘探、图像重建与恢复、材料科学遥感技术、最优控制和最优设计中 都存在反问题( i n v e r s ep r o b l e m s ) j 4 2 1 2 】【5 1 1 1 5 3 1 1 5 6 1 那么什么是反问题呢? 粗略地 说，反问题是相对于正问题( d i r e c tp r o b l e m s ) 而言的按照j b k e l l e r 2 6 】的提法，若 在两个问题中，一个问题的表述或包含了有关另一个问题的全部或部分的知识， 我们称其中一个为正问题。另一个为反问题进而，我们称一个先前被研究得相 对充分或完备的问题为正问题，而称与此相对的另一个问题为反问题 数学物理反问题的求解已发展了各种方法，诸如脉冲技术( p s t ) 广义脉冲技 术( g p s t ) ，最佳摄动量法，蒙特卡罗法( m o n t ec a r l om e t h o d ) 、各种优化方法和正则 化方法等；其中，最具普适性在理论上最完备而且行之有效的方法就是由著名 学者t i k h o n o v 以第一类算子( 譬别是积分算子) 方程为基本数学框架，于2 0 世纪6 0 年代初创造性地提出，后来得到深入发展的正则化方法其基本思想是，用一族 与原问题相邻近的适定问题的解去逼近原问题的解我们已粗略地看出，如何构 造。邻近。的问题( 即如何构造正则算子) ，以及如何控制与原问题的。邻近程度” 而决定于原始资料的误差水平相匹配的正则参数，将成为正则化理论或方法的两 大核心问题 设x 和y 均为度量空间份别称之为解空间与数据空间) ，算子a ：x y 映x 到y ，以上所举反问题均可写成如下算子方程形式t a x = y ，x e 置y e y ( i i ，1 ) 其中a 可为积分算子、微分算子或矩阵，或者说a 可为线性或非线性映射 今后，我们将把式( 1 1 1 ) 当作处理反问题的一般数学框架；当a 为线性算子 2 0 0 7 上海大学硕士学位论文 2 时，称其为线性反问题，否则称其为非线性反问题( 此时a 记为f ) 考虑线性算子方程( 1 1 1 ) ，其中a 是h i l b e r t 空间x 到h i l b e r t 空间的有界线 性算子( 1 】1 ) 有解当且仅当yer ( a ) ；( 1 i 1 ) 的解唯一当且仅当n ( a ) = 1 0 j ；若 ( 1 1 i ) 解存在且唯一，a 1 存在，( 1 i 1 ) 的解具有稳定性等价于a - 1 连续【4 2 】而 我们要得到( 1 1 1 ) 的解，条件y er ( a ) 和n ( a ) = o j 过于苛刻，因此我们通过引入a 的m o o r e - p e n r o s e 广义逆【s 1 1 4 2 1 ，来拓广( 1 1 1 ) 的解空间的范围 定义1 i i 我们称x ex 为( i 1 1 ) 的最小范数最小二乘解，如果 h ，d j = i n f t l l z l lj a z 一叫j = m i n l l l a x 一) 1 i ，x e x ” ( i i 2 ) 我们知道最小范数最小二乘解的概念与a 的m o o r e - p e n x o s e 广义逆紧密相关，即 m o o r e - p e n r o s e 广义逆算子是将y 映射到( 1 i 1 ) 的最小范数最小二乘解的解算子 定义1 1 2a el 饼，的m o o r e - p e l l f o 广义逆a t 定义为膏1 的唯一线性延拓， 其定义域为 d ( a t ) = r ( a ) + r ( a ) 1 其中n ( a t ) = r ( a ) 1 ，五= 州n ( 斛：n ( a r h h ) 定理i i 3 设y e d ( a t ) ，则( i i i ) 的最小范数最：b - - - - 乘解为 x t = a t y ( 1 1 2 ) 这样方程( 1 1 i ) 的最小二乘解的集合为x t + n ( a ) 定理1 i 4 设ye d ( a t ) ，则x e x 是a x = y 的最小范数最小二乘解当且仅当下 述法方程成立 a a x = a y ( 1 1 3 ) 通常情况下，方程( 1 , 1 1 ) 的右端数据y 不是精确给出的，我们只知道它的测量 数据，且满足 i b ，一旷i l 6( 1 1 4 ) ，称为扰动数据。6 称为误差水平相应地，方程( 1 i 1 ) 变为 a x = 旷( 1 1 s ) 我们希望对( 1 i 5 ) 所求得的解能逼近( 1 i 1 ) 的最小范数最小二乘解在不适定的情 况下，由于a t 无界，a t 矿不能很好地逼近a t y 5 因此我们要寻求x t 的近似， 2 0 0 7 上海大学硕士学位论文 3 它应连续依赖于扰动数据，这样我们可对其稳定求解；另一方面它应满足当6 趋于零和取合适的正则参数。时，趋于x t 我们构造一依赖参数的连续算子族 k 来正则化a t 。把= k 矿作为x t 的近 似，其中a 满足当d 一0 时，_ + x t 我们将看到。正则化参数口必与6 或，有 关，并可能与a 或y 的信息有关正则化算子的构造和正则化参数的选取构成了解 一类方程的正则化方法【6 】6 定义1 1 5 令a ：x 一为h i l b e r t 空间x 到h i l b e r t 空间y 的有界线性算子， 劬e ( o ，+ 叫，对任意口( o ，蜘) ，令 l o ：j h x 为一连续算子族( 不一定线1 勃对任意的yed ( a t ) 。若存在一个参数选取准则 口= o 慨，) 使得下式成立 娅s u p ，矿一a t 川，y ，旷一y l ls 研= o ( 1 i 6 ) 则算子族 r 口l 称为a t 的正则化或正则化算子，其中 口：r 卜( o ，a o )( 1 1 7 ) 满足 舰s u p 砸，) j ，e y 旷一州田= 0 ( 1 1 8 ) 对于具体的y ed ( a t ) ，若( 1 。i 6 ) 和( 1 1 8 ) 成立，( k ，叻称为( 收惫妗正则化方法 除右端数据扰动的情况外，我们可以把定义i i 5 扩展到包括算子扰动的情 形我们假设只得到a 的扰动算子 盯，且满足 a a 川口( 1 i 9 ) 对于具体y d ( a t ) 和算予a ，存在参数选取准则口= 口 玑矿， 玎) ，满足( 1 i 6 ) ，其 中。满足 扣始墨。s u p l 口( 反仉，) l ，只l 似，y ) i l ，一y l l 6i i a 一- 1 1 o 是定义于r + 上的一族分段连续的有界函数，如果它 满足下面的条件 i ) c 口= s u p、， i 踟u x 0 l e ( o i 门 i i ) 记r 。( ) = i g a q m ，有 慨r e ( a ) 2 o ， 0 i i j ) 存在正常数c o ，使得 ，u 鼬( 删s c o ，v 口， 0 则称踟u ) 为正则化逼近函数，r 。为残量函数 设鼬( ) 是一个正则化逼近函数，定义y x 的线性算予族 f 1 l a n z r 口= 踟( a a ) a = j 8 a ( 2 ) d e , i a j 0 其中e 是a a 的谱系，我们可以证明r 口是a t 的正则化算子 ( 一) 连续型正则化方法 i t i k h o n o v 正则化方法( t i k h o n o vr e g u l a r i z a t i o n ) 【1 2 4 1 8 】 按原始定义，它是由变分法导出的对于。，0 ，定义x 上的二次泛函 如( x ) = i i a x 一，2 + d ，i f ( 1 2 1 ) 2 0 0 7 上海大学硕士学位论文 t i k h o n o v 正则化方法是以( x ) 的极小点作为方程( 1 i 5 ) 的正则化解。其中。称 为正则化参数对于h i l b e r t 空间x ，和有界线性算子a ：x 卜+ ，由( 1 2 1 ) 的凸 性可知满足方程 ( a a + 口i ) ) 名= a ? ， ( 1 2 2 ) 从而有 瑶= ( a a + a 1 ) - 1a ， ( 1 2 3 ) k = ( a a + a 1 ) - a 称为t d l 【h o n o v 正则化算子，对应的逼近函数为 鼬( ) 2 而1 0 2 4 ) 2 a - 光滑正则化方法( a s m o o t hr e g u l a r i z a t i o n ) 5 0 】 设p 0 ，x e x ，则x 的p 阶a - 导数定义为 - ( a a ) - x( 1 2 5 ) 在拖上定义泛函 。( x ) = i i a x 一，炉+ 口l i 2 ( i 2 6 ) 其中) 是x 的p 阶a 导数a 光滑正则化方法是以钆，( ，o 的极小点也作为方 程( 1 1 5 ) 的正则化解对于h i l b c r t 空间x ，y 和有界线性算子a ：x y ，我们可 证在拖上。缸( x ) 存在唯一的极小元，它满足方程 【( r a y f + 口i 】屯= ( ”a y a ， ( 1 2 7 ) 由此可得 ) 乇f = 【( a 缈+ 1 + 口i 】- l ( a 缈a ，r 口， ( 1 2 8 ) 其中r 口。为u 阶a - 光滑正则化算子，对应的逼近函数为 g 口，( 舢= 万芸毛 ( 1 2 9 ) 当；0 时，上式退化为t i k h o n o v 正则化逼近函数( 1 2 4 ) ，此时即为t i k h o n o v 正则 化方法 ( 二) 迭代型正则化方法 1 l a n d w e b e r 迭代法【8 】【5 6 1 2 0 0 7 上海大学硕士学位论文 6 l a n d w e b e r 建议使用如下的迭代格式， 砘= x l , 一l 4 - u a o a ) q 卜1 )( 1 2 1 0 ) 来求解第一类算子方程的近似解，其中0 0 的假定式0 3 i ) 是一个适定问题，则在式 ( 1 3 6 x 1 3 7 ) 有解的情况下，当p _ + * 时，洳一x t 。x t 为式( 1 i 1 ) 的真解但式 2 0 0 7 上海大学硕士学位论文 9 ( 1 3 1 ) 往往是不适定的，而且右端项为带有噪音6 的观测数据广，这时约束集合 i x ：f ( x ) = y l 可能为空集，因此式( 1 3 6 x i 3 7 ) 可能无解故经典的二次罚函数法求 解( 1 3 1 ) 并不能凑效 这里我们仍考虑式( 1 3 5 ) ，并给出如下稳定的正则化方法- 算法给定充分大的初始参数锄 0 ，初始猜测值缘e x ，f e ( o 1 ) ，f 0 以及 观测数据，；在第k 步t ( a ) 运用某种无约束优化方法( 如n e w t o n 法，拟n e w t o n 法等) 求解式( 1 3 5 ) 并 求得一局部解奄； 若叭盎) 一巾sf ，则接受奄；r 作为式( 1 3 5 ) 的近似解，停机；否则按 下一节所给的参数选择决定参数f f k + l ，并同时求得近似解； ( c ) 若式j 满足f | f ( 蛊j ) 一蜘蔓f 则停机；否则令盔= 氆i i ，a o = f t 2 k + l 返回步 骤( a ) 对于无约束优化问题( 1 3 5 ) ，其梯度和h e s s e n 矩阵是很容易精确地求出的， 因此我们也可以用优化中其他方法求解( 1 3 5 ) ，比如信赖域方法由于信赖域方 法的强适性( 全局收敛性) ，一定可以获得( 1 3 5 ) 的稳定近似解 2 约束最s j l - - 乘法 给定参数b 0 ，选取x be x 使得它是如下极小化问题一 卿u f ( x ) 一卅0 3 9 ) s t i l x l lsb( 1 3 t o ) 的解 定义约束函数c b ( x ) = 旧p b 2 ，则式( 1 3 9 x 1 3 1 0 ) 的l a n g r a n g e 函数可表为 【七( x 田= i i f ( x ) 一y i p + _ c b ( x )( 1 3 1 i ) 这里 0 为l a n g r a n g e 乘子利用一阶必要条件可以求得式( 1 3 9 x i 3 1 0 ) 的一个 解，但这未必是使得目标函数最小的个解，因此我们还得考虑其他有效的算法 一个强适性的算法是序列二次规划法( s q p ) 给定初始猜测值，考虑如下迭代， 聋l _ 碡+ 蹴，k = o ，j ，0 3 ，1 2 ) 2 0 0 7 上海大学硕士学位论文 l o 其中6 碡为下列二次规划问题： 卿肝( 碡) + f ，( 碡) s 一州2 ( n 1 3 ) s t c b ( x ：) + v c b ( x ：) t s 0 ( 1 3 1 4 ) 的解 当然我们也可以利用求解约束优化问题的信赖域方法求解式( 1 3 9 x 1 3 1 0 ) ( 二) 迭代法 1 l a n d w e b e r 迭代法【8 1 设x o = r 给定，在第k 步( 1 c = l ，2 ，) 我们计算 = - 】+ f ( 1 ) 一f ( i ) ) ( 1 3 1 5 ) 显然，若f ( x ) = a x ，a 为线性算子，则式( 1 3 1 5 ) 将导致我们熟悉的线性l a n d w e b e r 迭代法关于迭代格式( 1 3 1 5 ) 的详细讨论可参阅【8 】 2 l e v e n b e r g - m a r q u a d t 方法【1 6 1 ， i m b e l g m a r q u a d t 方法可以看作是对非线性问题( 1 3 1 ) 作先线性化后正则化 的过程该方法最初是由l e v e n b e r g 3 0 和m a r q u a d t 3 2 用来求解下述非线性最小二 乘问题的t 驰u f ( x ) 一殉2 o 3 1 6 ) 该算法的基本形式是：给定初始猜测值x o x ，在第k 步，令 + l = + 6 x k ，k = 0 ，i ， 其中幽。为执行拟n e w t o n 步的结果 5 礅= ( f7 ( ) f c 4 ) + o d ) - 。f ( ) ( y f c 4 ) ) ( 1 3 ，1 7 ) 其中a k 0 称为l - m 参数在l e v e n b e r g - m a r q u a r d t 方法中，关键的一步是选取参数 毗 l e v c n b e r g m a r q u a r d t 方法也可看作是把线性t i k h o n o v 方法应用到( 1 3 9 ) ，即最 小化 ，一f ( ) 一f ( x x 一) 2 + u kj i x 一1 1 2 0 3 1 8 ) 2 0 0 7 上海大学硕士学位论文 所得l m 方法也可看作是信赖域方法的雏形，考虑( 1 3 1 6 ) 的线性化形式 卿似s ) = f ( ) + f ( ) s 一广2 可以证明【5 8 1 ，l - m 方法与下述约束极小化问题： r a 硝i n “s ) s t i m 2 等价的；其中r k ，0 为球半径，或称为信赖域半径 3 b a k u s h i n s k i i 正则化方法( 又称为g a u s s - n e w t o n 迭代法i l l 3 1 在此我们考虑求解( 1 3 1 ) 的形式 f7 ( ，x 十l x o ) = 一f ( ) 一广一f ( 一x o ) b a k u s h i n s k i i i 】给出了求解( 1 3 2 2 ) 的迭代格式 l = + ( f ( ) f ( ) + 毗i ) - i f ( ) 一f ( ) ) + 口k ( 靳一) 】 迭代序列 l 也就是最小化 l l ，一f ( ) 一f7 ( x x 一) 酽+ a k l l x - 2 所得在此方法中，正则化参数龟满足如下条件 口k 0 o 订等虬i r a o 1 , = 0 毗 在f ( ) 满足一定的条件下，可以证明此方法的收敛性和收敛速度【3 1 求解非线性不适定向题的方法还有信赖域方法【4 8 1 1 4 9 1 等 1 4 几种正则化参数选取准则 ( 1 3 1 9 ) ( 1 3 2 0 ) ( i 3 2 0 f 1 3 2 2 ) ( 1 3 2 3 ) ( 1 3 2 4 ) 正则化方法的艺术在于如何在近似解的精确性和稳定性之间进行甲衡和折 中；这就牵涉到正则化参数的选取问题下面介绍两种误差水平已知的正则化参 数选取准则，m o r o z o v 残差准则和a r c a n g e l i 准则和两种误差水平未知的正则化参数 选取准则，拟最优准则和l 曲线准则 2 0 0 7 上海大学硕士学位论文 1 2 1 m o r o z o v 残差准贝1 j 3 3 残差准则是一种被广泛应用的后验选取正则化参数的方法它是由m o r o z o v 首 先提出 3 3 1 ，现在这个准则的几种变形可参阅【4 3 】【卅这里我们采用以下形式来 定义正则化参数 啦，) ：= s u p 口 0 ：l i a 一，1 l 妄f 研( 1 4 i ) 其中 f s u p l r , t ( a ) llf l , 0 ， e 【o a l l 2 】l( 1 4 2 ) 若对所有的口 0 ，a 一广ns 晒，则砸，) = * ，此时岳) 可被理解为当a 佃 时的极限对口 0 ，令g 。：= s u p f l 鼬( o ： 【o 恻p 】i j ，若 一舰= 0 由上可知，残差准则是通过比较残量( 残差) i i 一，与已知误差水甲界6 来确 定正则参数的 2 改进的后验准则a r c a n g e l i 于1 9 6 6 年几乎与m o r o z o v 同时但独立地提出了一 个正则化参数的选取方法，他主张下式 心一巾一去= o ( 1 4 4 ) 来确定正则参数对于每个固定的d0 ，函数 “口) = 诟i l a 一如 对口是连续的，单调递增的，且有 慨p 啦) 20 。l 。i r a 。“口) 2 ” 故存在唯一一个口= a 口 e 一口 v l口 g 财数常为 o c 中其 2 0 0 7 上海大学硬士学位论文 1 3 来确定未知参数其基本思想是让正则参数口以及正则解对该参数的变化率同时 稳定在尽可能小的水乎上记 p q c a ) = 鲁2 。a ，o 则风( 易由下述公式 口鲁；一0 ( ”a + 口i ) _ k 算得注意到在有限维情形总有p q ( o ) = 0 ，因此在实际计算时应该将初始值a o 设 的大一些 4 l 曲线准则 它是由h n 2 0 提出的它的主要思想是，对定义在一个较大区间内的各口 值，在l o g - l o g 比例下画出l l 瑶相对于妒一a l i 的曲线通常我们得到的这一曲线总 体上像字母。l 。故称其为l - c t b v c ，而这一正则化参数的选取方法就称为 p c i m y e 准则( l c l w ec r i t e r i o n ) 故我们寻找此l - c m v e 上的一个角点( c 0 1 t i e i ) ，对应的口 作为相应的正则化参数的近似解 关于l - c u r v e 方法的个实际困难是曲线上在角点附近的点对应的正则化参数 的范围很广。因此角点不应该靠视觉来选择，而应依据一些数值最优规律来选择 h a n k e 1 9 】等建议定义l 曲线的角点为l 曲线在l o g - l o g 尺度下具有最大曲率的 点令 p = l o g 妒一a 宅 口= l o g i i 则该曲率作为参数a 的函数定义为 悱篇 ( ( p ，) 2 + ( 酽) 2 ) l 其中表示关于。的微分。 e n g l 在文献【7 1 中指出，在相当多的情况下，l 曲线准则可通过极小化泛函 口( 口) = “洲，一a 瑶 来实现，即取矿使得 2 0 0 7 上海大学项士学位论文 1 4 这一准则更便于在数值上加以实施其实。我们也可以从另一角度来诠释该准则 的含义t 对于任意口 0 ，正则化解瑶是数值稳定的，因而极小化残差i t 一a 是合理的此外，由于我们要求的是具有极小模的最小二乘解，故使极小化 亦在情理之中综上所述，极小化乘积l 酽一a 0 便可同时达到上述目的 迄今为止，人们尚未获得关于l 曲线准则的收敛性结果，事实上有人已举出 反例指出了l 曲线准则的不收敛性【删，但数值结果【1 9 】表明l 曲线准则具有很强 的适应性。正则参数具体选取方法另外还有a r c a n g e l i 准则【1 3 】拟最优准则【4 1 1 广义a r c a n g e l i 准则【7 1 等 2 0 0 7 上海大学硕士学位论文 第二章非线性共轭梯度法 2 1 非线性共轭梯度法介绍 共轭梯度法首先由h c s t e n e s 和s t i c f e l ( 1 9 5 2 ) 提出来作为解线性方程组的方法 1 9 6 4 年f l e t c h e r 和r e e v e s 将其推广到非线性优化领域共轭梯度法本质上就是使得 搜索方向具有共轭性，从而提高算法的有效性 对于无约束优化问题 罂船f ( x ) ( 2 i i ) 给出一初始值x i ，算法迭代产生x 2 ，x 3 希望某一轧是( 2 1 1 ) 的解或者点列收敛 于解在第k 次迭代，当前迭代点为桃，线搜索型的方法将产生一搜索方向d ker n 然后下一个迭代点 ) l2 轧+ c r k d k( 2 i 2 ) 其中呱 0 是步长因子，它满足某些线搜索条件 个线搜索型的方法的每步迭代主要由两部分组成， 算；第二是步长因子毗的计算 搜索方向氐通常要求是下降方向，即 d ：v f ( x k ) 0 上式保证一定存在l a ，0 ，使得 第一是搜索方向也的计 ( 2 1 3 ) “砘+ 口d k ) “x k ) ( 2 i ，4 ) 也就是说，沿着d k 方向搜索，一定可找到比獠更好的点记g ( x ) = v f ( x ) 以及 g k = g ( x k ) 求解问题( 2 i 1 ) 的共轭梯度法是从求解线性方程组( 2 1 4 ) 的线性共轭梯度法 推广而来的，其搜索方向是负梯度方向与上一次迭代的搜索方向的线性组合，它 表示为 血= 一氨+ 风d k i( 2 1 5 ) 2 0 0 7 上海大学硬士学位论文 1 6 线搜索型的共轭梯度算法可描述如下： 算法2 1 ，l 徘线性共轭梯度法) 【5 9 】 ( a ) 给出初值x le r n ，0 ；d l = - g l ，k ：= 1 ( b ) 如果g k i i g ，则停； 利用某种非精确线搜索求矾； 翘+ l 昌强+ 钒d k ( c ) 利用某种公式计算参数风+ l ； d k + l 。- - g k + l + 风+ 1 d t ； k ：= k + i ；转步 方向d k 的计算主要是确定风，凤的计算主要有以下几种方法【5 9 】 步长毗的计算对个线搜索型方法也至关重要简单说来，它是从砘沿d k 方 向寻找一个”好”的点作为下一个迭代点显然。最好的点是在这个方向函数值达 到最小的点，即要求 “砘+ a k d d = m i n “+ o ，血)( 2 1 6 ) 这时，我们称线搜索为精确线搜索精确线搜索需要求个单变量函数的极小值， 计算量较大故在实际计算中常常进行非精确搜索下面介绍几种非线性线搜索 f 5 8 】 g o l d s t e i n 线搜索，令f ( + 毗) = “，预先指定两个数o i 和o 2 ，满足0 o - i c 0 2 1 。用以下两式限定口 j i p ( 。) 5 “o ) + 矿1 0 矿( 0 ) ( 2 1 7 ) l “口) 2 “o ) + 眈叫( o ) g o l d s t e i n 线搜索算法步骤； s t e p lt 给定初始数据，在搜索区间【o ，口。j 上任意选取初始点a o ， 给定可接系数0 口1 观 i ，令t “n = 0 s t e p 2 。若“s 州o ) + 唧7 ( o ) ，则转s t e p 4 ；否则转下一步 2 0 0 7 上海大学硕士学位论文 1 7 s t e p 3i 令x = 口，转s t e p 6 s t e p 4 t 若“烈o ) + 观叩( 0 ) 。转s t e p s 否则转下一步 s t e p 5 l 令口i 血2 口 s t e p 6 l 当o r a l x 4 - o o 时，令口= 抽皆“； 当x = + 时，令口= p a n s t e p 7 l 转s t e p 2 s t e p 8 ，令口= 口，计算停止 w o l f e - p o w e l l 线搜索：预先指定两个数和0 - 2 。 两式限定口 i “口，“o ) + o - j a 妒 ( o ) i 矿( 口) 0 2 矿( o ) 满足0 o i 0 2 0 ，最大迭代 步数n 后。有预处理的h s 算法步骤为 ( 1 ) 令k ：= o ，计算g o = v q ( a o ) 若l ig d 临s ，则停止迭代，a = a o ；否则， 令d o = 一h o g o ，其中h o 为单位矩阵 ( 2 ) 沿d k 方向线搜索砂 o ，使得q ( a 。+ 一d 。) = 嘧q ( a k + o t d 。) ； 令a k + = a 。+ d d o 。k ：= “1 ( 3 ) 由方程( 2 2 8 ) 计算u ，若u 一一1 1 0 ，令a o = a 。，转( 1 ) ；否则转( 2 ) 其它方法当中d 的选择如f ff r 方法：d 。= 一旷1 9 k 一赫w - 协d p r p 方法：d k = - w - 1 9 k 一蛀龄芦d “。 【c d 方法：d 。= 一w _ 1 9 k + 弗w 卅d 上述n l c g 算法采用了预处理，这是因为预处理可以提高算法的效率r o d i 和m a c k i e ( 2 0 0 0 ) 3 9 的发现表明预处理可以显著改善n l c g 法的效率预处理矩阵 我们采用如下的b f g s 校正f 5 8 】 吣( b f ，g s ) - ( i - h k ”蓑) + 蓑 ( 2 3 1 ) 其中札= a k + i a k 在步骤( 2 ) 中我们使用g o l d s t e i n 不精确线搜索 使用自动控制理论中的伴随状态法求梯度【5 7 】对于问题( 2 2 8 ) ，引入伴随 状态矢量a = ( 扎赴，。 ) t ，定义l a g r a n g e 算子a ：a = q + k t o ) u p ， ) ，取a 的全 微分 a = 喜筹妣+ 善n 石0 a 舢+ 善n 石0 a 岫 2 0 0 7 上海大学硕士学位论文 因( p ，u ) 须满足( 2 2 8 ) 式，此时有，a = q ，瓦8 a = o ，v i = l ，2 ，n 故有 = 喜筹舢+ 善 丽0 a 嘶 固 如果我们适当选择 使得( 2 3 2 ) 式右端第一项为零，即使得 m ) t = 一【筹，蓑，瓦o q 7 ( 2 3 3 ) 即可得q 的第j 个分量的表达式 舞= 坠= ，百0 k ( p ) e o i u ) 帆印。 。 ( 2 3 3 ) 就是所谓的伴随状态方程因此求q 在一点矿的值只需联合求解状态方 程( 2 2 8 ) 和伴随状态方程( 2 3 3 ) 。然后由( 2 3 4 ) 式即可导出q 在算法的步骤( 3 ) 中我们使用了m o r o z o v 残差准则【8 】，即迭代次数n = n ( 回= n 瓶一) 是满足 hf ( a ：f 西) 一一i i 1 6 1 1f ( a f 旧) 一u 6i l ，、，n l l ( 毋 ( 2 3 5 ) 的整数，此时取a 作为方程( 2 2 4 ) 的近似解 2 4 数值算例 问题( 2 2 1 ) 等价于下面的变分问题 求u eh 3 【o ，l 】使得 o ( u ，v ) 一f ( v ) ；0 ，v v h j 【o ，l 】( 2 4 1 ) 其中 d ( 1 1 v ) = j ：( a ( x ) 五d u 赢d v ) d x ，l f ( v ) = j “x m x ) d x 将区间( o 1 ) 2 n 等分，分点为【i = i h ( i = 0 ，l - - , 2 n ) ，h = 击为步长取h j 【o i 1 的基朔，忱，矿h 一2 ，妒! ，其中 2 0 d 7 上海大学硕士学位论文 2 1 奶( x ) = 0 sx k 1 宁斗l 5 。 蝻( i ：i 2 ，2 n 一1 )阱2 ) 鱼咭= 兰k 董x k “ 0x i + t x sx 2 n 令u = u l 妒l + u 2 忱+ + u 2 n l 妒2 n - i 再取h t o 。l 】的基如，们，一1 ，“，其中 10 吒s x l “对= 睾2 i = 1 , 2 , - - , n - 1 ) 【0 硌isx s 删： 掌巧“? 弓 10 吒s o sx l “柚筝= 羔碥 其中h ，= 2 h ，= i h ( i = 0 ，l ，n ) ，令a = a o 妒o + a i 奶+ + a n 如则用下面的 问题去逼近问题( 2 4 1 ) 求实数u 1 u 2 ，一l ，使得 d ( “l 妒l + u 2 忱+ + t 砣n l 妒2 - ，一i ，仍) = f ( 蚋) ，( j = 1 2 ，2 n 1 ) ( 2 4 4 ) 于是有方程组 d ( p l ，妒1 ) d ( 眈妒1 ) d ( 蛳一1 ，妒 ) d ( | pe 妒i ) d ( 忱，朔) d ( 纯n 一1 妒i ) d ( p 1 妒i ) d ( 仡，们) d ( 妒2 n i ，妒i ) u u 2 f i ) f 和2 ) f 如2 n _ 1 ) 我们采用四种共轭梯度法对问题的两个例子进行求解 例2 4 1 ；在方程( 2 2 1 ) 中我们取“x ) = x 2 s i n n x ，反问题的解为a = 1 0 ，此时 u ( x ) = s i n ，r x ，扰动右端取为 u ? = u + v 互6 c o s l o n x 2 0 0 7 上海大学硕士学位论文 a 5 ( x ) 是试验初值，初值下的数代表初始误差j ia 8 一a ，f = 1 i 当6 = 0 ，当数 据精确时，外层迭代终止准则( 2 3 5 ) 不能应用，n ( 毋由下式确定 l if ( a ：( 毋) - u 6 1 1 i o 一。 f ( a ：) 一一，y n ( n ( o d ( 2 4 5 ) 试验数据如表2 4 i f r 方法p r p 方法 a 5 占 迭代次数i ia 2 一a i i a 5 6 迭代次数 i ia ：一a i i 1 0 28 67 5 2 e - 21 0 26 l 5 4 7 e - 2 a + - i 4 o x o 一蚋 1 0 + 34 8 9 6 0 2 e - 2 a “o x o n 1 0 33 0 54 0 7 e _ 2 ( o 7 3 ) 1 0 - 4 1 7 2 29 1 l e 3 ( 0 7 3 ) 1 0