（应用数学专业论文）基于新拟牛顿方程的非线性最小二乘的一类新算法.pdf

ab s t r a e t withth e c o m p r e hen s i v eapp l i c at i o n o f non l inearl e ast s q u a r e s p ro b l e m s ， mor e a n d m o r e attent i o n s 1 1 a v e b e e n g i v e n tothe s 1 u d y o f th e al g o ri t lun， a l l d m a n y n ew m e th o dsar e a d v anc e d i n re c e n t years the fi r st p art o f this p aperg o e s 仍a th o ro u gh re v i ew o f s t u d 1 e s on m e t h 0 d s fo r non l inearl east s q t la r e s p r o b l e m s ， whi c h are th e n ， fr o mthe p er sp e c t iv e o f arit 1 1 i1 1 e t i c d e s i 助， c l as s i fi edi nt o fi v e m aj o r type s : met h o d s b a s e d o n q u as i 一e 从 唯 o n e q u at i o n ， h y b ri d m etho d s ， 伪 c t oriz e d q u as i 一 n e wto n m etho d ， trus t 一 re g io n m etho d s ， and s e l f- s c al i ngm e thodthe s e c o n d p axto f this p ap e r to rn s th e fo c ust o w ard a ty p e o f n e wal g o r l t 】1 n 1 s for n o n 1 inearl e as t s q u ar e s pro b l ems b as e d o n n e wq uasi 一e ， 注 o n e q u at i o n . i nth i s p ape r，the newq u a s l 一 n e 节 沈 o ne 叩at i on 3 6 ， p r o p o s ed by zha ll ga n d o th e rsi n 2 0 0 l b y usi n g the te n s o r m e th o d and bel o 雌t o h u ang ， s quas i 一e v 沈 o n ， 1 5 e mp10 y e d tor e p l ac e th e q u as i 一 n e wto n e q u a t i o n i n c hen ， s p ap e r 3 9 . thenc h e n ， 5 a l g o ri t lim i s g e n e r a l i z e d tob ro y d e n ， 5 勿叩p l y i ngthe dualp rinc i p l e aswe1 l asthe s truc n 1 r ep ri nci p l eo f t h es e c ant m e th o d . u n d e rs u c had e s i gn， th ea l g or i t ll n l i s inv胡ant und e r ano rtho g o n alm atri x i r a n s fo rma t i o n o n v 丽abl e s a n d b e i nvu l ner abl e tothe g o o d o r b a d qual i tyo f p ro b l e m s inthe p r o c e s s o f a c t u alc al c u l atio n . a fter th 叭 t l甘 e e c o rres p o ndi n ga l g o r i t h 旧 s are p re s e nt e d ， fo l l o wed b ya t e s t i m o ny tosh o wth at al l the threeal g o ri t h m s o wn l o c alan d s u p e 卜 l inearc o nve rg e ncef i n al l 苏numeri c ai e xperim e nt s are c o n duc 沈 d tod e m o n s t r a t e th atal l the t hr e e al g o ri 1 h n l s s hown i n th i s p ap erar e b e tt e r th anth ati nc h en，s p ap e r 3 9 . i nadd i ti o 几im pe o v e m e ll t s o f the a l g o ri t 址 n s are gi v e n toe n ab l e th e mt o bel n u n une o f th e i nfluen ceo f th e i ni ti alp o i nt 汕d e ac h iter at i o n p o i nt ， a s o u n d e ffec t o f w h ic h h asb e ena p p r o v e d b y the n l 1m e n c al re s u l ts ， th use x p and in g t h e app 1 i c at i o n s c o p e o f s t ic h al g o ri t h m s . k e y w o r d s : n e w q u a s i 一 n e 节 八 o n e quat i o n ， c o n v e rg e n c e ， s upe r- l i n e arc o nve r g e n c e me tho d ， l o c a l l i 声明 本学位论文是我在导师的指导下取得的研究成果， 尽我所知， 在 本学位论文中， 除了加以标注和致谢的部分外， 不包含其他人己经发 表或公布过的研究成果， 也不包含我为获得任何教育机构的学位或学 历而使用过的材料。 与我一同工作的同事对本学位论文做出的贡献均 已 在论文中作了明 确的说明。 研究生签名:丝。沙 如 学位论文使用授权声明 南京理工大学有权保存本学 位论文的电子和纸质文档， 可以 借阅 或上网公布本学位论文的全部或部分内容， 可以向有关部门或机构 送 交并授权其保存、 借阅或上网公布本学位论文的全部或部分内 容。 对 于保密论文，按保密的 有关规定和程序处理。 研究生签名:乡 一月 之 俨 洲日 硕士论文基于新拟牛顿方程的非线性最小二乘的一类新算法 第一章 绪论 l l 研究目的和意义 非线性最小二乘4 01 是最优化问 题的一个重要分支， 在科学实验、 测绘设计与 工程技术等领域中， 我们经常要进行数据拟合， 参数估计和函数逼近， 这往往归结到 求解非线性最小二乘问题: f( x ) 一 告 r ( )r r (x )二 告 客 乙 ，” ( 1 . 1 ) 其 中 x r称为 决 策 变量， r( x)= ( rl(x) 几(x )，.， 、 ( x) 广 称 为 在点x 的 残向 量， f(x)称 为目 标函 数 ( 或者评价函数) ，f ( x)的梯度和 海森矩阵分别为: 9 ( x ) = 可( x ) = j ( x ) t 天 ( x ) ，( 1 . 2 ) g ( x ) = v ，f( x ) = j (x ) j ( x ) t + 艺。 (x ) v ， 。 (x ) = c ( x ) + 5 ( x ) ，( 1 3 ) 其 中 j ( x ) = 【 v 气 ( x ) ， v 几 ( x) ， 二 ， v ( x ) 从式 (l. 1) 一(l. 3) 可以看出非线性最小二乘是一类特殊的最优化问题，可以 运用无约束最优化问题的计算方法来求解， 但由于问题结构的特殊性， 所以结合问题 的 特殊性是求解非线性最小二乘行之有效的方法， 目 前一些比较流行的算法都是结合 问 题的 特殊结构提出的. 随着非线性最小二乘的 广泛应用，算法的研究越来越受到重 视，研究人员给出了大量的求解策略. 1 . 2研究现状 随着非线性最小二乘的广泛应用， 对于其求解方法的研究越来越深入， 尽管利用 无约束优化方法也可以求解， 但是一般我们结合问题的结构特点来求解， 本文将各种 算法分为基于拟牛顿修正的算法、 混合算法、 信赖域算法和分解拟牛顿法以及具有乘 积结 构的 算法 等. 1 . 2 . 1基于拟牛顿修正的算法 从非线性最小二乘的 海森矩阵表达式(l .3) 可以 看出， 矩阵的前半部分只包含函数 的一阶导数信息， 且这部分是容易通过计算得到， 矩阵的后半部分包含函数的二阶信 l 硕士论文 基于新拟牛顿方程的非线性最小二乖的一类新算法 息， 这部分计算起来比 较麻烦， 并且存储量较大. 另一方面，由于求解非线性最小二 乘 是 对气 ( x) ， t = 1 ， 2 ， ，二 ， 脚在 平 方 和 意 义 下取 得极 小， 极 有 可能以 x) ， 1 = 1 ， 2 ， . ， m 在 最 优 解戈 处的 取值为。( 零 残量问 题) 或取较小的 值 ( 小残量问 题) ， 这时(l.3) 中g ( x) 的 非 线 性 项 s( x)或 为0 或 者 同(l 3)中 的 c ( x)比 较 相 对 较 小 ， 因 此 在 x. 的 某 个 邻 域 内g (x ) 的 线性项c ( x)将是 海 森 矩阵g ( x)很好的 近似， 这就是 著 名的 高 斯牛 顿法 2 51 . 高斯一 牛顿法是解决非线性最小二乘的非常有效的方法，但是对于非零残量，效 果不好. 在非零残量问题中， 为了能够对于目 标函数的海森矩阵更好的近似， 需要考虑非 线 性 项 部 分5 ( x)的 大 小直 接计 算 s( x)是 不明 智的 ， 它的 计 算 量 太 大， 拟牛 顿 法 是 求 解最优化问 题的有效算法， 非线性最小二乘作为一种特殊的无约束优化问题， 其求解 方法随着拟牛顿法在一般优化问题中的应用而发展， 对于( 1 .3 ) 式 ， 1 9 7 1 年b ro wn 和d e nni 7 建 议 用b ro y den 在1 9 6 7 年 得出 的 对 称 秩 一 修 正 公 式 来 产 生 v z 以 x) 的 近 似 ， 设 叽是 护 : ( x) 的 近 似 ， 取 凡 = 艺: (x*) 叭， 他们给出了 算法的局部收敛性， 且 对于零残量问题给出了 局部二次收敛的结论， 但是 这样的方法不具有实用价值， 原因在于算法执行时，至少要存储m 个n 阶矩阵. 然而 他 们开 创了 用 拟牛 顿 法 确定s( 乓 ) 的 近似a( 乓 ) 的 思 想 基 于 拟 牛 顿 修 正 的 思 想 8 ， 对 于 s( 乓 十 1 ) 的 近 似 矩 阵 凡 + ， 应 该 满 足 拟 牛 顿 方 程 凡+1 乓= 八 ( 1 . 4 ) 因此用拟牛顿法求解非线性最小二乘，就转化为如何构造拟牛顿方程. 在 相当 长 的 一 段时 间 里， 求 解 非 线 性 最 小 二 乘的 研究 方向 就 是 对于(1 . 4)中 入 的 修 正， 如b ett s 1 1 ， o e nn is ，g a y 和wel s c h 1 5 ， g i l l ， 枷r r a y 1 3 ， 以 及 在其 中 加 入调比技术 1 7 . 1 ， 2 . 2混合算法 高斯一 牛顿法是求解零残量和小残量问题非常有效的 算法，并且该方法对于零残 量问 题具有二次收敛性， 对于小残量问题的收敛速度至少是线性的， 而拟牛顿法对于 硕士论文墓于新拟牛顿方程的非线性最小二乘的一 类新算法 求解大残量最小二乘是非常有效的方法，且该方法具有超线性收敛的 性质. 由以 上的 分析， 将两种方法结合起来，充分利用两类算法的优点，能设计出 更有效的算法， 这 就推动了混合算法的发展，而构造混合算法的关键在于开关准则的选取. 最早提出混合算法的是p owell 4 ， 他在1 9 70年将高斯一 牛顿法与最速下降法相结 合， 尽管证明该方法具有收敛性， 但由于最速下降法在实际上所固有的不足， 即最速下 降法仅有线性收敛率， 且计算效果不好. 1 9 8 5 年阿巴里和弗莱切【 1 8 提出了 基于高斯一 牛顿法和bfgs公式的混合算法，数 值表明该混合算法是相当有效的， 但是他们在迭代过程对两种算法的选取采用最大下 降方向的原则，即每一步的运算要分别 用高斯一 牛顿法和b f gs公式计算目 标函数的下 降量， 哪种方法使目 标函数具有更好的下降量就采用哪种方法计算迭代矩阵， 这种方 法计算量比 较大，且只有线性收敛性. 弗莱切和徐成贤 1 9在1 9 8 了 年对于混合算法作了修正， 给出了更加精确的开关准 则，在此混合算法开关准则下的算法具有超线收敛的性质. 徐成贤汇 21 于1 9 90年提出 用差分代替导数的 混合算法， 该 算法具有c n 一 b f g s 和有 限差分b f g s 算法的优点. 1 . 2 . 3分解拟牛顿法 1 9 9 1 年h i r o s h i y a b e 和t o s h i h i k o t a k a h a s h i 2 2 提出 分 解 拟牛 顿 法 ， 该 算 法结 合非线性最小二乘的结构特点和拟牛顿法， 将问 题转化为求解以下方程组的方法， 即 方向由下列的方程组给出: ( 人+ 几 ) 认+ 乓 ) t 气 = 一 jk t 凡，( 1 .5 ) 其 中人 几 r + 几 凡 了 十 人 人 r 是 海 森 矩 阵(l .3)中 的 非 线 性 项 部 分 s( 、 ) 的 近 似 . 该 方 法 的特点是保持了拟牛顿法所具有的线性变换不变性， 从而保证方法不受问题性态的影 响. 1 9 9 6年徐成贤 【 24 充分利用矩阵知识 10 提出了一族解决非线性最小二乘分 解拟牛顿法， 该方法包含t由h i r o s h i y a b e 和t o s h i h i k o t a k a h a s h i 提出的分解拟牛 顿法. 2 0 00年张建中 3 幻等利用j . husch 即5 【 2 3的技术提出了 新的 分解牛顿法， 该算法 保持了 具有乘积结构类算法对于零残量问 题具有二次性收敛性， 而对非零残量问 题具 有超线性收敛性. 20 01年由枷x ia of an g 【 3 51 等， 提出 稳 定 的 分 解 拟牛 顿 法， 该 方 法 是 将qr分 解 3 硕士论文基于新拟牛顿方程的非线性最小二乘的一类新算法 技 术 应 用 于 分 解 拟牛 顿 法， 把人 ， ， 分 解为人 ， 1 = 吼 习 凡 。 ， 其中级 ， ， 为阴x m方 阵 ，凡 +l 为脚x 刀 矩阵， 且前n 行组成了凡十 1 为n x n 上三角阵， 后m一 n为 零行， 于是用瓜+1 代 替 人 十 ， ， 用l k+ 1 代 替乓 十 t ， 该 方 法 在 是 在 线 性 搜 索 的 框 架中 实 现 的 ， 同 时 当 m n 时，节约很多计算花消， 很有实用价值， 且保持分解拟牛顿法具有的局部超收敛性. 1 . 2 . 4信赖域算法 l e v e n b e r g 一 m a r q u ard t法 1 找 z j 是对于高斯一 牛顿法的最早修正， l e v e n b e r g 一 m a r q u a r d t 法 是 属 于 信 赖域 法仁 2 5 2 7 . l e v e 汕 e 馆和m a r q u ar 由指出 ， 在非 线 性最小 二 乘问题求 解中， 使 得目 标函 数f ( x)下降的 最 好方向 应 该 在高 斯 一 牛 顿 法 和 最 速下 降 法 之间， 即 下降 方向 5 、 可以 由 方 程 组 j ( 乓 ) j ( x * ) t + 八 1 1 5 * = 一 j ( 乓 ) r ( 礼 )( 1 .6 ) 确定 ， 其 中 八 0 ， 这 种算 法的 关 键 在于 选 择合 适的 调 节 参数热 3 4 ， 使 得目 标函 数在 迭代 过程中 充 分地下 降， 数值实 验表 明， l ev e n b e r 兮 m ar q u a r d t 法比 高 斯 一 牛顿 法 更有效，并且对于零残量问题与高斯一 牛顿法具有相同的收敛性 1 ， 2 . 5 具有乘积结构类算法 j . huschens 23 于1 994 年在求解非线性最小二乘的过程中采用了 类似于 调比 技 术 的 方 法 ， 对 于 目 标 函 数 海 森 矩 阵 的 非 线 性 部 分 加 了 一 个 调 比 因 子 r( 乓 )il ， 即 将 目 标函数的海森矩阵写为如下形式: g ( x ) = j ( x ) t j ( x ) + !ir ( 凡 ) 1 艺: ( 乓 ) v ， : (毛 ) r ( 、 ) ( 1 . 7 ) 再结 合具 有割 线结构 方法的结构 原则 用凡去 逼近目 标函 数的 海森 矩阵吭 风= 人 t 几 斗 l r( 乓 )ll 人 ， ( 1 8 ) 其中 凡是艺 。 ( 、 ) v ， : ( 、 ) 1r ( 、 ) 的近似. 对于此类方法j . h uschens 证明了对于零残量问题具有二次收敛性， 而对于非零残 量问 题具 有超线性收敛性， h i r o s h i 丫 曲1 和h i d e h oo g a s 盯a r a 2 9 在1 9 9 5 年对于 4 硕士论文 基于新拟牛顿方程的非线性最小二乘的 一类新算法 j . huschens的 算法重新给出了 证明 . 2 0 03年张建中 3 8等又将此类算法结合新拟牛顿方程提出了新的算法， 他们还用 数值实验验证了该算法要优于h uschens 方法. 混合算法和具有结构类算法中都将求解非线性最小二乘划分为零残量和非零残 量来讨论， 都给出了很好的收敛性， 但是由 于混合算法需要计算开关准则， 增加了内 存量， 是用空间换时间的方法，因 此hus chens 类算法的 研究更加有实际意义 . 1 . 3本文的主要工作 本文利 用了 z h a n g 【 3 6 等人 2 0 01年提出 的 运 用张量的 方法得到的 新的 拟 牛顿 方 程， 该方程属于黄族拟牛顿方程， 摒弃了 c hen 3 9文中的拟牛顿方程， 再结合对偶原 则以 及割 线方法的 结构 原 则， 把 chen 3 9) 文中 算 法推广到整个 b ro y de n 族， 之后给出 相应的三种算法，即基于新拟牛顿方程具有割线结构的b f g s 算法、p s b 算法、 d f p 算法， 证明了此类算法具有在正交变化下的 不变性， 其次证明这三种算法都具有局部 超线性收敛性的性质， 最后进行数值试验， 数值结果表明基于新拟牛顿方程具有割线 结构的 b f g s 算法、 p s b 算法、 d f p 算法都比 c h en文中算法效果要好， 此外， 还对算 法提出了 进一步的改进， 使得算法不受初始点和每步迭代点的影响， 数值结果表明 算 法效果好，从而提高算法的适用范围 本文的结构安排:第一章介绍非线性最小二乘的研究目的和意义以及研究现状. 第二章给出了基于新拟牛顿方程具有割线结构的b f g s 算法、 p s b 算法、 d f p 算法. 第 三章 证明了 基于新拟牛顿方程具有割线结构的 b f g s 算法、 p s b 算法、 d f p 算法都具 有超线性收敛的性质 第四章数值试验，给出了与c hen 【 3 9文中算法的数值比较 硕士论文基于新拟牛顿方程的非线性最小二 乘的一类新算法 第二章 基于新拟牛顿方程的非线性最小二乘的一类新算法 这部分首先给出新的拟牛顿方程以及它的一些重要性质， 在此基础上， 结合对偶 原则以及割线方法的结构原则， 提出了基于新拟牛顿方程的非线性最小二乘的一类新 算法，最后证明了该算法具有在正交变换下的不变性 2 . 1新拟牛顿方程 拟牛顿法是求解非线性最小二乘非常有效的方法， 此类算法的关键是要求对目 标 函 数 的 海 森 矩阵 拟牛 顿 修正 ， 下 面 给出 由zhan g 汇 3 6 等 人 在2 0 01年 提出 的 利 用 张 量的 方法得到的新牛顿方程 假设目 标函 数f ( x)在 定 义 域内 充 分 光 滑， 利 用归几 y l or展 式有 ， (、 ) = ， (、 +1)一 9 及 1、 + 奋 :v z了 (、 )、 一 去 、 (: ，1*)、 + 0 (，、 4) ， ( 21 ) 、= 执 +】一 韶 、 (x ;)s+去 (l+ 剐 、 + o(il 、 ，际 ( 22 ) 其中兀 十 1 o r ” ” 是f 在乓 十 ， 的 张 量 4 4 ， 且才 兀 十 ，5 ; =全 了 ， 1 ， 1 = 1 护 f(气 卜， 一 一 浅 万 云 占 ， 电电粼 “ “ 这样 消 去 (2 . 1 ) (2，2 ) 式中 的双 + ; ， 可 得 可 v ， f ( 凡 ) 气 二 ( 及 二 ， 一 9 : ) t 凡 + 6 ( 人 一 人 + 1) 十 3 ( 9 、 + ， + 9 、 ) t 凡 + 0 ( 1 凡 ij ) ， 所以 用凡 习 乓 代 替 v 沙( 气 )s*得 可 风 。 乓 二 可 yk 十 入 ， 人 = 3( 及 + ; 十 9 、 ) r + 6( 人 一 人 十 1 ) ， 其 中凡 + 1 近 似 目 标 函 数 海 森 矩 阵 铲 厂 ( 凡 + 1 ) . “需 女 。 一凡 从1 u 月 坑+ ， 5 * =儿 +书 产一 u ， 凡配 七 取 、 = 、 得 凡 十15 、 = (1 + 平 ) 夕 * ， sk 少 、 令y * 二 儿十 儿 二 不 ，儿 ， 气少 飞 即 得新牛顿方 程 凡 ， lsx二 y * ( 2 . 3 ) 说明: ( 1) 新拟牛顿方程不但利用了函数值信息， 而且利用梯度信息， 从而对目 标函 数的h es si an有更高逼近精度， 6 硕士论文 基于新拟牛顿方程的非线性媛小二乘的一类新算法 ( 2 ) 新拟牛顿方程是属于黄族拟牛顿方程，从而保持了在线性变换下的不变 性 ( 3 )为了使新牛顿方程保持正定遗传性，使用下面得策略 当 、 : (二 一 1)5、 时 取 ; * 二 yk 十 共yk ， 凡儿 当 人 (e 一 1) 可 儿时 取y * 二 儿， 其中的 。 (0 ， 1) 的常数. 关于新拟牛顿方程对目 标函数的hess i an矩阵的逼近度有下面的定理: 假 设目 标函 数f ( x)充 分光滑， 如果“ skll 充 分 小， 则 有 5 二 q ， :乓 一 ， * = 0 ( 1 1 ) ， 可 队+ls*一 y*= o(i! 5111， ) . ( 2 .4 ) ( 2 . 5 ) 推论1 : 如 果f ( x)是线性或二次函 数则 gk+l 气一 y * = 0， q+l 凡一 儿= 0 . ( 26 ) ( 27 ) 推论2 :如果f(x)是三次函数则 s:gx+lsx一 y ， 卜0 . ( 2 . 8 ) 关于定理的证明见文献 3 6. 2 . 2 基于新拟牛顿方程的非线性最小二乘的 一类新算法 首先对本文中的一些符号进行说明: c ( x ) 尺 月 x ， 是v z f (x ) 在x 处的一阶信息量且c ( x ) = 了 ( x ) j t ( x ) ，h ( 气 ) 近似 v 2 f( x*)的 逆， 人= f ( xk ) ， 及= g( 、 ) ， 从二 h (x*) ， h (x.) = v z 广， ( 几 ) ， ij. ” 是 欧氏 范 数， 权重范 数! m; 利用对偶原理， 定 义 为i mll; = 寸 trac e ( 材 ， ) ， 11 11. 月 i h.至 只要v z f ( x ) 和c ( x ) 非 奇 异， 可 将v z f ( x ) 兰 c ( x ) + 5 ( x ) 表达为 v ， f 一 ， ( x ) 二 c 一 ， ( 小 a ( x ) ， 其 中 5 ( x ) ， 注 ( x ) 含 有 二 阶 信 息 ， 但是 难 于 计 算， 从 而 对月 ( x ) 进行逼近，则第k 次迭代有: 7 硕士论文基于新拟牛顿方程的非线 性最小二 乘的一类新算 法 从= c 一 ， (x ) + 凡， 其 中 凡= a( 从 ) 人 + ， y 、 = 刁， = 才 + c 一 ， ( 瓜 + : ) 夕 * ， 斌= c 一 ， 呀 )+人 ， 其 中 夏 取 值 在 乓 ， 、 十 1 之 间 凡 + ， = ak+ 2 ( y * ， ， ak ， v ) ， 从+ ， = c 一 ， ( 凡 + ， ) + 人 + : 二 c 一 ， ( 礼 ， ， ) + 凡+ 2 ( 夕 * ， 才 ， 凡 ， v ) 其中 2 (y， 5 ， a ， v) ( 5 一 ay) v t + v ( 5 一 办) t( 5 一 ay) t v t 夕( v t 夕 ) 2 势甲 ( 2 . 9 ) 可 以 容 易 地 看 出 2 (y * ， 才 ， 凡 ， v) = 2 (y * ， 5 * ， 斌， v) 所以 有从十 ， 二 砚+ 2 (y * ， 凡 ， 买， v) 对于其中的v ，若 v=y * ( 21 0 ) 则为p s b公式 ，可儿 石 一 “ 了(忘 特别地当公 = 0 时 斌y * ， 则为b ro y de n 族公 式 . v =人 ( 2 . 1 1 ) 即为b f g s 公式. 当公 = 1 时 一 _ _ . 叮 凡 f “ j k ， 、 : 了 - - - 二 一 丫 少 * 斌 y * 斌y k ( 2 . 1 2 ) 即为d f p公式. 对于上述的三种情况 凡+ ， 对应的 更新公式分 别为 八凡t点 ( 5 尝 一 人 y * 夕 。 + 少 、 ( 才 一 ak y 、 ) t 人+1之凡+ ( 哎 一 人 夕 、 ) 夕 、 夕 ， ( p s b公式) 订气 y * y 乏( 夕 * t 人 ( 夕 少 * ) 2 硕士论文基于新拟牛顿方程的非线性最小二乘的一 类新 算法 = 今 卫 已 迎 赴 选 二 生 丛 兰 _ 可 儿 ( 才 一 凡y ， ) 气 才 ( b f g s公式) t凡 ( 5 万 凡 ) ， 几r 人 ， : = 凡+ ( 叮 一 凡 夕 * ) v t + v ( 才 一 凡 ， ， ) t夕 ， (才 一 凡 夕 * ) 。 t v r 夕 ，( v t 少 * ) ， ( d f p 公式) 其 中 ， 二 、 * 除 客玛 y * . v 儿尽儿 下面给出基于新拟牛顿方程的非线性最小二乘的一类新算法: stepi : 给 定 初 始 点 xo ， 满 足c( x0 ) 非 奇 异 ， 凡 r ” ; stepz : 计 算乱= vf(xt) ， 如 果 “ 及卜0 ， 则凡 = 凡 停 止 ， 否 则 转st 叩 3 s t e p 3 : 计 算凡= c 一 ， ( xk ) 十 人和 吸= 一 凡跳， 由 一 维 线 性 搜 索 准 则 得气 从而 有= 气dk， 令凡 + ， = xk+ sk ; s te p4: 计 算儿= 及 + : 一 gk， 入= 3 ( 及 + ， + 及 ) t 凡 + 6 ( 人一 人 . 1 ) ， 0 + 共 )yk当 、 : ( 二 一 1)5 了 、 时 5 ， yk 当 儿 0， 对 于竹， x+ d有 li v z f ( x 十 ) 一 v ， f ( x ) 11 石 il x+一 x lj， ll f ( x+ ) 一 f ( x ) 1 l l x+一 x 1， “ g(x+ ) 一 g(x)阵 ll 戈一 xll， ll c 一 ， ( x+ ) 一 c 一 ， ( x ) 14 l !i x+ 一 x . ( a3) 存 在 常 数 。 0， 满 足m ax ll 。 一 x* !， ， 一 11 几 ， ( 几 凡 ) 有 上 11 ， 一 。 11国 i vf (u ) 一 可 (u ) 11: : jv 一 。 1( 3 .2 ) 成立 证明:参见文献 5. 引理32 : 假设引理31 成 立， 证 明 存在正 常 数。 2 ， p ， 使得 对于 vx* ， 礼 十 ， 满 足。 ( 乓 十 : ， 乓 ) 几 ， 有 合 一 卜 又 卜 : ，“占、“ ( 33 ) 成立. 证 明 : “ ” ， 由 引 ” 3 “ 去 1、 卜 1、 卜 、 1、 卜 所以 当 八 。 ， 对于 满 足 ll xo 一 x* ii二 的 任意 的 初始点xo， 以 及 满 足” 鸡一 瓜妇 ; 占 ， “ 凡一 属!1 万 的 任 意 的 凡。 渺 幼 ， 则 点 列 、 有 定 义 且 超 线 性 收 敛 到x. 证 明 : 设 、 (。 ，)，夕 。0，圣 ，m - v 2 f( x. )s， 选 择 ，占 充分 的 小 且 满 足 占 m in 于 鱼， 1 下 ， 4 l ( 3 . 6 ) e 而n 笼 月 ， 几， 似! 一肠l m一 ， 凡 4 去 ( il v ， f 一 ， ( x. ) 11 + 丈 ) ， 1 冬 ， ( 37 ) 刀一热 其 中 的凡有引 理3. 3 给出 ，al ， 气分 别 为 硕士论文基于新拟牛顿方程的非线性最小二乘的 一类新算法 。 = 哥 (l 一 。 一 、 ， 、 丽翠槛而 “ 、 = 偿 爷 糯 男 聋 ， ( 38 ) ( 3 夕) 其 中 的 凡有 引 理3 .4 给出. 下面利用数学归纳法证明下列 ( 1) (2)( 3) 对任意的k 已 n均成立. ( 1)” x*+， 一 x.i阵 川 乓一 x.l ; ( 2 ) ! 凡 十1 一 孟 1; : (抓蔺 + al ) 1 人 一 透 ，1二 + 二 。 (、 ， 1， xk ) ， ( 3 . 1 0 ) ( 31 1 ) ( 3 . 1 2 ) ，.j 目.且 飞一。0 r.l 任 刀一尸 为一声 = 一 归 卫 1 丛 二 二 里 口 匕;( 3 . 1 3 ) 中风 其且 1 人一 法iif ll m 一 ， 夕 川 ( 3 ) 11 凡 + : 一 a.l; 2 占 .( 3 . 1 4 ) “ )当k =0 时，对于 ( 1) 有: 11 xl一 x.!同xo+ 50 一 瓜1! 司xo一 从一 hog0u 到xo一 几 一 v z f 一 ， (x*x go一 9. )il+ll鸡一 a.ll.llgo一 9.” + i c 一 ， ( xo ) 一 c 一 ， ( x， ) 1111 局一 乡11 到v z f 一 ， (x.)ll.“ ( 90一 9. ) 一 v z f 一 (x.) (x0一 幼“ +( 协+ 尸 列lx0一 x*i ( il v ， f 一 ， ( x. ) 1 加+ l 占 + lz ) 1 xo 一 从 11 产 1 凡一 石!1 对于 ( 2 )由引理3 . 3 有 ” 城 一 m 一 ， yo114im一 ， 川 l yo 一 护f(幼501国m一 凡 。 (x.， xo)“ sojl ， 而 “ m 一 ， y 。 “ 州mso 一 ( mso 一 m 一 ， yo )ll 圳鸡 ” 一 ” mso 一 m 一 ， y 。 “ 之 ( 材 一 ， 1一 ， 一 i m 一 ， 11 戈 。 ( 从 ， xo ) ) 11 50 1 之 ( 11 材 一 1一 ， 一 ll m 一 11 凡 ) 11 50 11 . ( 3 . 1 5 ) 所 以 有 竺 脸 巡 二 五 丝 ” m 一 ， “ 戈 a(xl ， xo ) 1 m一 ， y 。 11 ji m一 ， 11一 ， 一 “一 ， 1 戈 = 热。 (x， xo ) ( 3 . 1 6 ) 硕士论文 基于新拟牛顿方程的非线性最小二乘的一类新算法 这样由( 3 . 7 ) 知 ll mso 一 m 一 ， y 。 11 ， 。 p ( 3 . 1 7 ) jl 万一 ， 夕 。 1 从而 根 据文 献 8 中 的 引理5 .2 ， 对于a.= 护f(x. 犷， 一 c 一 ( 瓜 ) 有 ，、 一 “ 。厂面 + 鲁 (卜 ， ) 一 ， “ ms。 一 m 一 ， y 。 11 11 材一 ， 少 。 1 1 1 凡一 瓜!; + 2 ( 1 + 2 杨) 11 好 1， 由 ( 3 . 15) ，( 3 . 1 6 )以及引理3 .4 ，进一步有 “ 叮 一 茂 川 !1 材一 ， 少 。 1 11 鸿 一 川; 到价一 a 嘴+ al 。 (xl， xo)ii 鸡一 引; + 久 试xl ， xo) 对 于(3 ) ， 由 1 鸡 一 法日 ; 针 碑 一 a 心+ al 。 (x ， ， xo