非线性最小二乘问题数值迭代法的统一模型及其不适定性

第 24卷 第 2期 长 沙 交 通 学 院 学 报 Vo .l 24 No. 2 2 0 0 8年 6月 JOURNAL OF CHANGSHA COMMUNICATIONS UNIVERSITY Jun. 2008 文章编号: 1000- 9779( 2008) 02- 0039- 05 非线性最小二乘问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 数值迭代法的 统一模型及其不适定性 唐利民 1, 2, 朱建军2 ( 1. 长沙理工大学 交通运输工程学院, 湖南 长沙 410076; 2.中南大学 信息物理工程学院, 湖南 长沙 410083) 摘 要: 通过综合归纳在路面模量反算和测量平差等领域中求解非线性最小二乘问题的各 种数值迭代解法,建立了非线性最小二乘问题数值迭代法的统一模型.根据不适定问题理论, 结合非线性最小二乘问题,定义了非线性最小二乘问题的两种不适定性, 对产生这两种不适 定问题的现象进行了 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ,并给出了实例. 结果 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明,在 NLS问题上使用各种数值迭代解法 时,需考虑其迭代过程的不适定问题. 关键词: 路面模量反算; 测量平差; 非线性最小二乘; 数值迭代; 不适定 中图分类号: U416. 2; O241. 5 文献标识码: A 收稿日期: 2008- 04- 09 作者简介: 唐利民 ( 1978- ), 男,长沙理工大学助理实验师, 博士生. Unifiedmodel and il-l posed property of num erical iterative formula for solving nonlinear least squares problem TANG L-im in 1, 2 , ZHU Jian- jun 2 ( 1. Schoo l of T ra ffic and T ransportation Eng ineering, Chang sha Un iversity of Sc ience& Techno logy, Changsha 410076, Ch ina; 2. Co llege o f Info-Physics and G eom atics Eng ineer ing, C entra l South University, Changsha 410083, China) Abstract: A ll k inds of numerica l iterat ivem ethods for so lv ing non linear least squares prob lem s thatw idely ex- ists in inverse calcu lation of pavement modulus and survey ing ad justm ent fie lds were summarized, a un ified mode l of numerica l iterative formula for so lving non linear least squares problems w as proposed. A cco rd ing to il-l posed problem theory, comb ined w ith non linear least squares prob lem s, tw o il-l posed properties of nonlin- ear least squares problems w ere defined. The phenomenon of the tw o il-l posed properties w as analysis, and some examplesw ere g iven. The results show that it needs to consider the il-l posed prob lem in iterative process w hen all k inds of num erical iterative methods forNLS problems are used. Key words: inverse ca lculation of pavementmodulus; survey ing adjustmen;t non linear least squares; numer-i ca l iterat ive; il-l posed 1 引 言 在路面模量反算、测量平差和变形监测等领域中, 存在着大量的非线性最小二乘 (N on linear Least Squares, 简称 NLS)问题. 一般地,非线性观测方程可写为 [ 1] L = f (X ) + $. ( 1) 相应的误差方程为 V = f (X^ ) - L. ( 2) 于是, 残差平方和为 VcV = + V+ 2 = + f (X^ ) - L+ 2 = (f (X^ ) - L ) c(f (X^ ) - L ). ( 3) 定义 1 非线性模型式 ( 1)中参数 X的一个估计量 X^, 若满足 VcV= m in. ( 4) 则称 X^是 X的一个非线性最小二乘估计,用 X^NLS表示. 在不引起混淆的地方把它简记为 X^,其中 V 由式 ( 2)确定. 根据定义 1可知,求非线性模型式 ( 1)的最小二乘估计量, 就是求参数 X 的估值 X^, 使 VcV(X^ ) = (f (X^ ) - L ) c(f (X^ ) - L ) = fc(X^ ) f (X^ ) - 2f c(X^ ) L + L cL = m in, 由于 L cL是一常量,所以,该式等价于目标 函数 R (X^ )的非线性无约束最优化问题 [ 1] , 即 R (X^ ) = fc(X^ ) f (X^ ) - 2fc(X^ ) L = m in. ( 5) 求解式 ( 5)可能会存在非线性最小二乘不适定现象.有关线性最小二乘不适定的研究很早就开始 了,并建立了一系列解决理论和方法,其中以 T ikhonov A N正则化理论为主要代表. 非线性不适定问题 的研究也有大量成果,主要集中在第一类积分方程 [ 2]、非线性方程组、常微分方程以及偏微分方程领 域. T ikhonov A N主要针对第一类积分方程和偏微分方程作了讨论 [ 3] .最早对有关非线性最小二乘问题 的不适定性进行讨论的是前苏联学者 吉洪诺夫和 ƒ¡阿尔先宁,他们对关于求泛函极小值与求解 最优控制问题的稳定方法以及求解最优 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 (线性 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 )问题的稳定方法展开了讨论 [ 2] . 对于非线性最 小二乘问题的不适定性讨论,国内、外的有关文献并不多. 本研究对非线性最小二乘问题的两种不适定 性即求解式 ( 5)可能会存在的不适定性给出了定义. 为了方便讨论这两种可能存在的不适定性, 先建立 求解非线性最小二乘问题数值迭代法的统一模型. 2 求解非线性最小二乘问题数值迭代法的统一模型 求解 NLS的算法主要分为 3大类:近似解法、数值迭代解法和直接搜索算法. 数值迭代解法包括牛 顿法、信赖域法、拟牛顿法、最速下降法、高斯 - 牛顿法、改进的高斯 -牛顿法和阻尼最小二乘法等 [ 1] ; 直接搜索算法包括单纯形法、模拟退火算法、遗传算法、神经网络算法、蚁群算法和粒子群算法等. 对于非线性强度很强的非线性模型, 线性近似将会产生大于观测误差的模型误差,应采用迭代的方 法求解.由于 f (X^ )是 X^的非线性函数,对式 ( 5)求一阶偏导数, 并令该一阶偏导数为零, 使它得不到 X^ 的显表达式,也求不出 X^ 的解析解,因此,只能设法寻找某一近似解 X* ,使 R (X* ) [ R (X^ )成立,目前普 遍采用迭代法,寻找使 R (X* ) [ R (X^ )成立的近似解 X* . 设 X ( k)为当前迭代值, X ( k + 1 )为下一步迭代值.则非线性最小二乘问题的数值迭代法的统一模型为 X ( k+ 1) = X ( k) + K ( k) D (X ( k ) )Z (X ( k) ). ( 6) 式中: D (X ( k) )为迭代主矩阵; Z (X ( k ) )为迭代方向矩阵; K( k)为迭代修正步长. 表 1是统一模型与经典数值迭代法的各参数比较.根据表 1,进一步得到统一模型的迭代步骤为: 1) 选取初值 X ( 0) , 并令 k= 0; 2) 计算迭代方向矩阵 Z (X ( k) ),若 Z (X ( k) ) = 0则转至 7); 3) 计算迭代主矩阵 D (X ( k ) ); 4) 确定迭代修正步长 K( k)的值; 5) 按式 (6)计算新的近似值 X ( k) ; 40 长 沙 交 通 学 院 学 报 第 24卷 6) 计算目标函数值 R (X ( k+ 1) ),若 R (X ( k+ 1) )X R (X ( k) )则转至 2)继续迭代; 7) 终止迭代,输出 X ( k+ 1)和 R ( k) ,结束. 表 1 统一模型与经典数值迭代法的各参数比较 迭代方法 迭代公式 K(k ) D (X ( k) ) Z (X ( k) ) D (X ( k ) )求逆 统一模型 X ( k+ 1) =X ( k ) + K( k )D (X ( k ) )Z (X (k ) ) K(k ) D (X ( k) ) Z (X ( k) ) 牛顿法 X (k+ 1) =X (k ) + dX ( k ) =X ( k ) - G - 1k gc( k) 1 G- 1k gc( k ) 是 拟牛顿法 X ( k+ 1) =X ( k ) + dX ( k) = X ( k ) - Q - 1k gc( k ) 1 Q - 1k gc( k ) 是 最速下降法 X ( k+ 1) = X ( k ) + dX ( k) = X ( k ) - K( k )gc( k ) K(k ) I gc( k ) 否 高斯牛顿法 X (k+ 1) = X (k ) + (Bc(X ( k) )B (X ( k ) ) ) - 1 @ Bc(X ( k ) ) ( L - f(X (k ) ) ) 1 (Bc(X ( k ) ) @ B (X ( k ) ) ) - 1 B c(X ( k) ) @ (L - f (X ( k ) ) ) 是 改进的高 斯 -牛顿法 X ( k+ 1) = X ( k) + K(Bc(X (k ) )B (X ( k ) ) ) - 1 @ Bc(X ( k ) ) ( L - f(X (k ) ) ) K (Bc(X ( k ) ) @ B (X ( k ) ) ) - 1 B c(X ( k) ) @ (L - f (X ( k ) ) ) 是 阻尼最小 二乘法 X (k+ 1) = X (k ) + (Bc(X ( k ) )B (X ( k ) ) + A( k) I ) - 1Bc(X ( k ) ) ( L - f(X (k ) ) ) 1 (Bc(X ( k) )B (X ( k ) ) + A( k) I ) - 1 B c(X ( k) ) @ (L - f (X ( k ) ) ) 是 修正阻尼最 小二乘法 X ( k+ 1) = X ( k) + K(Bc(X (k ) )B (X ( k ) ) + A(k ) I ) - 1B c(X ( k) ) (L - f (X ( k ) ) K (Bc(X ( k ) )B (X (k ) ) + A( k) I ) - 1 B c(X ( k) ) @ (L - f (X ( k ) ) ) 是 建立了数值迭代法的统一模型后,就可以讨论求解非线性最小二乘问题可能存在的两种不适定性 的现象了. 3 非线性最小二乘问题的两种不适定性 非线性最小二乘问题, 实际上就是求解泛函 m inR (X^ ).在测量平差、变形监测和面模量反算等领域 中,求出达到泛函 R (X^ )最小值元素 X的问题属于对自变数求极小值的问题.在它们中间可能会遇到这 种问题,即其中极小化序列可以是非收敛序列.显然,在这种情况下, 取极小化序列的元素作为近似解. 把这个问题称为非稳定的或不适定的问题是自然的 [ 2] . 另外, 也可以从阿达玛对有关不适定的意见出 发得到这个问题是不适定的结论 [ 2] .阿达玛认为:数学问题的一个重要性质是原始数据变化不大时, 它 们的解应该保持稳定,不能满足这种稳定条件的问题称为不适定 ( il-l posed)问题.在非线性最小二乘问 题中, 这种不适定在实际工作中会经常碰到. 3. 1 非线性最小二乘问题的第一种不适定性 设在某度量空间 F内,给定连续泛函 R (X^ ), 在集 F上求泛函 R (X^ )极小值的问题在于寻求元素 X^ 0 I F,在这个元素上 R (X^ )达到其最小值 R0, 即 inf X^I F R [X^ ] = R [X^ 0 ] = R 0. 假定存在这个问题的唯一解 X^ 0,设 {X^n }为极小化序列,即 lim ny ] R {X^ n } = R0. 定义 2 如果所有的极小化序列 {X^ n }收敛 (在空间 F度量 )到 F空间的元素 X^ 0时, 则把求集 F内 泛函 R (X^ )极小值的问题称为稳定的问题 [ 2] . 定义 3 如果某种算法对于求集 F内泛函 R (X^ )极小值的问题是可解并且是稳定的, 则称这个算法 是适定的. 定义 4 对于某种求解非线性最小二乘问题的算法, 也即求集 F内泛函 R (X^ )极小值问题的算法, 如果这种算法对于求集 F内泛函 R (X^ )极小值的问题不可解或者不稳定,称之为非线性最小二乘问题 的第一种不适定性. 在算法不适定性中,存在不具稳定性求泛函极小值的问题,在这种问题中,有不收敛于元素 X^ 0的极 小化序列存在.例如, 数值迭代求解 NLS问题的牛顿法、信赖域法、拟牛顿法、高斯 -牛顿法、改进的高 斯 - 牛顿法、阻尼最小二乘法和正阻尼最小二乘法中, 对应于统一模型的 D (X ( k ) )都需要进行求逆运 算,当 D (X ( k) )是病态矩阵或者奇异矩阵时, 这几种算法都可能会导致产生不收敛于元素 X^ 0的极小化 41 第 2期 唐利民,等:非线性最小二乘问题数值迭代法的统一模型及其不适定性 序列. 也就是说, 这几种算法都会可能存在非线性最小二乘问题的第一种不适定性. 反映在本研究的统一模型中, 如果 X ( k+ 1) = X ( k) + K( k)D (X ( k ) )Z (X ( k) )不收敛于元素 X^ 0的极小化 序列,则统一模型是呈现第一种不适定性现象.图 1为采用高斯 -牛顿法解算文献 [ 1]中例 3- 3- 6时 Jacob ian矩阵的条件数和行列式值在迭代过程中的折线;图 2为采用修正高斯 -牛顿法解算文献 [ 5]例 7- 17时 Jacobian矩阵的条件数和行列式值在迭代过程中的折线. 从图 1, 2可以看出,判断矩阵是否病态的两大指标条件数和行列式值 (尤其是条件数 )在两个例子 的解算过程中,不管是采用高斯 -牛顿法还是修正高斯 -牛顿法都比较大. 例题 7- 17的条件数甚至达 到 1011量级,其迭代过程中的 Jacobian矩阵为严重病态,从而导致解产生第一种不适定性现象. 3. 2 非线性最小二乘问题的第二种不适定性 非线性最小二乘问题实际上也是最优设计与数学规划 (线性与非线性 )的问题.这些问题是不稳定 的,因为原始资料的变化不会引起解的很大变化 [ 2] . NLS问题实际是:从 X n中找出向量 X^,使在集 R上的函数 R (X^ )极小化, 即 R (X^ ) = m in X I X n R (X^ ). ( 8) 函数 R (X^ )称为式 ( 8)的目标函数.在实际中, 函数 R ( X^ )的信息具有近似性质.在测量领域,观测数据 总是带有某种误差,因此, 可以取任意的 RD(X^ )来代替 R (X^ ),即 +RD(X^ ) - R (X^ ) + [ D. 定义 5 设 X^为式 (8)的解, X^D为近似问题 RD (X^ )的解,如果存在 B > 0, 使得对任一 D> 0, 满足 +X^D- X^+ \B,则称式 ( 8)为非线性最小二乘问题的第二种不适定性. 目标函数m inR (X^ )的较少扰动将引起解 X^的巨大变化,且这种变化不在控制范围内,或者说, X^的 变化不可估计.这样一来, 这类问题的精确解便不能作为具有近似原始资料的最优设计问题的可靠方 法.当利用诸多算法解 NLS问题时, 在计算过程中常常发生定义 5的情况.也就是说, 尽管 X^和 X^D迥 异,但目标函数 m inR (X^ )和 m inRD(X^ )的值却差别不大.文献 [ 2]列举了一个线性规划的例子且说明第 42 长 沙 交 通 学 院 学 报 第 24卷 二种不适定问题. 总体来说, NLS问题的第一种不适定性是指由于算法的不适定性,找不到收敛序列收敛到目标函数 m inR (X^ );第二种不适定性是指在一些算法下, 目标函数 m inR (X^ )和 m inRD (X^ )的值相差较小时会引起 解 X^的巨大变化,这对于以 R (X* ) [ R (X^ )为终止收敛条件的算法来说,在计算机上由于字长的限制, 是比较容易产生第二种不适定性问题的. 文献 [ 6, 7]给出了有关例子,并建立了正则化和神经网络相结 合的方法来解算具有第二种不适定性的非线性最小二乘问题. 4 结 语 路面模量反算和测量领域中存在着大量的不适定问题 [ 8- 9, 11- 13] .王振杰 [ 9 ]着重阐述了测量平差模 型中的不适定问题,这些问题本质上是由于矩阵病态和奇异引起的,属于本研究中所提的第一种不适定 性范围.魏木生 [ 10]系统地研究了广义最小二乘问题的理论和计算.本研究建立的非线性最小二乘问题 数值迭代法的统一模型,是对数值迭代类方法的归纳和统一. 在此基础上,定义了非线性最小二乘问题 的两种不适定性.由此可知,在 NLS问题上使用各种数值迭代解法时,需考虑其迭代过程的不适定问 题.由于不适定理论出现时间还不长,国内、外文献主要集中在线性问题、第一类积分方程和偏微分方程 的不适定性研究,对非线性最小二乘问题,则鲜有文献论及. 随着科学技术的发展,非线性最小二乘模型 的应用日益广泛,非常有必要讨论其不适定性. 紧跟本研究的工作是研究如何求解 NLS不适定问题的 解算方法.比如: 采用正则化方法或者正则同伦方法来建立问题的稳定解算方法等, 有关研究结果将另 文发表. 参考文献: [ 1] 王新洲. 非线性模型参数估计理论与应用 [ M ].武汉 :武汉大学出版社, 2002. [ 2] 吉洪诺夫, ƒ¡ 阿尔先宁.不适定问题的解法 [M ]. 王秉忱译.北京: 地质出版社, 1979. [ 3] T ikhonovA N. Nonlinear il-l posed problem s[M ]. London: Chapm an & H a l,l 1998. [ 4] 刘继军. 不适定问题的正则化方法及应用 [ M ].北京 :科学出版社, 2005. [ 5] 高士纯, 于正林.测量平差基础习题集 [M ]. 北京:测绘出版社 , 1983. [ 6] Eriksson J. Optim ization and regular iza tion o f nonlinear least-squares prob lem s[ D ]. Um ea, Sweden: Um ea Un iversity, 1996. [ 7] Er iksson J, W ed in P A, Gu lliksson M E, et a.l Regu la rization m ethods for un iform ly rank-deficien t nonlinear least-squa res prob lem s[ J]. Journa l o f Optim ization Theo ry and Applica tions, 2005, 127( 1): 1- 26. [ 8] 查旭东, 王秉纲.基于同伦方法的路面模量反算研究 [ J]. 中国公路学报, 2003, 16( 1): 1- 5. [ 9] 王振杰. 测量中不适定问题的正则化解法 [ M ].北京 :科学出版社, 2006. [ 10] 魏木生.广义最小二乘问题的理论和计算 [M ]. 北京:科学出版社, 2006. [ 11] 欧吉坤.测量平差中不适定问题解的统一表达与选权拟合法 [ J]. 测绘学报, 2004, 33( 4): 283- 288. [ 12] 沈云中,胡雷鸣, 李博峰. Bursa模型用于局部区域坐标变换的病态问题及其解法 [ J]. 测绘学报, 2006, 35( 2): 95- 98. [ 13] 王振杰,欧吉坤, 柳林涛.单频 GPS快速定位中病态问题的解法研究 [ J] .测绘学报, 2005, 34( 3): 196- 201. 43 第 2期 唐利民,等:非线性最小二乘问题数值迭代法的统一模型及其不适定性