牛顿迭代法为何收敛,牛顿迭代法的收敛性如何判断

首页 > 教育 > 作者:YD1662023-04-21 03:02:13

牛顿迭代法为何收敛,牛顿迭代法的收敛性如何判断(13)

图2:分别用复函数 f(x)=sin(cos(x)), sin(x3-1) 和 x(x3-1)2 做出的牛顿油画

回到“正则性”
至于牛顿法的正则性(regularity)条件,那更是大有文章可做了。
用通俗语言说,一个问题是正则的最一般的定义是,这个问题的解的变化上界跟问题数据扰动大小成比例。用数学语言说的话就是,问题的解利普希茨(Lipschitz)连续依赖于数据。
正则性是数学上的一个重要性质。在计算数学里更是重要到不可或缺的程度。可以说计算数学只能解决正则问题。非正则的问题又称为奇异(singular)问题。奇异问题跟数值计算水火不容。所以在计算数学教科书上基本上找不到任何奇异问题的数值解法。因为教科书上没说,一个秘密就有点鲜为人知:奇异问题常常可以正则化。至于怎么正则化,那就是施展聪明才智的时候了。寻找正则化方法,探索奇异问题的数值解是计算数学尚未充分开发而又前景广阔的处女地。
满足正则性的方程解必定是孤立点。而奇异解可能是孤立的重根,但更常见的情形是方程组的解是个高维流形,比如曲线和曲面,这些都属于所谓非孤立解。非孤立解在科学计算中十分常见。很多应用问题的关键就在奇异点上。回到牛顿-莱布尼茨微积分的基本思路,要求解非线性方程组 f(x) = 0 ,先把方程转换成线性逼近方程(4)。由于雅可比矩阵在解点奇异,不存在逆矩阵。要想扩展牛顿法,可能的突破口就在矩阵求逆。信手拈来有个广义逆矩阵。

牛顿迭代法为何收敛,牛顿迭代法的收敛性如何判断(14)

​并试图应用于求解奇异方程组。可是问题并不是把求逆上标“-1”换成求广义逆上标“†”这么简单。它需要一大串莫名其妙的条件才能保证收敛,因此难以成为通用算法。
直至1982 年,笔者的大师兄朱天照教授首次证明了迭代序列(3)对雅可比矩阵行满秩欠定方程组的局部收敛性。到了九十年代,在香港任教的陈小君和祁力群教授用更广义的所谓“外逆”取代穆尔-彭罗斯广义逆,在某些条件下证明了使用某种特殊外逆的牛顿法二阶收敛到一个驻点,然而不能保证驻点是解。例如,高斯牛顿法(5)形式上是广义牛顿法(6)在超定方程组的特例。而高斯牛顿法(5)收敛到的驻点只能保证满足最小二乘解的必要条件,一般来说不是 f(x) = 0 在通常意义下的解。

最新发展
问题的瓶颈在哪里呢?广义逆的一个特性是在奇异矩阵附近不连续,稍加扰动矩阵就成为坏条件可逆矩阵,所以在奇异解附近,广义牛顿法(6)退化成辛普森牛顿法(2),直接使用广义逆仅仅是把求解方程的奇异问题换成广义逆矩阵的奇异问题,并没有跳出奇异怪圈。再一个短板在于,正则解只有一种,奇异解的奇妙在于各有各的奇异性。企图一口吃个大胖子,一个方法横扫一切奇异解,天下哪有这种好事。

牛顿迭代法为何收敛,牛顿迭代法的收敛性如何判断(15)

​正则解是孤立解,维数是零。雅可比矩阵是满秩,秩损失也是零。秩损失有个专用词,叫零度(nullity)。正则解的维数不多不少刚好等于雅可比矩阵的秩损失这个现象不容易被注意到,因为都是零。非孤立解如果是曲线,则维数是1,曲面维数是2,超曲面的维数可以是3,4 等等。常见的非孤立解有个特性:雅可比矩阵在这些解的秩损失也刚好等于解的维数!换句话说,解曲面的切空间就是雅可比矩阵的零空间。也可以说,通常的非孤立解虽然奇异,但还是恋恋不舍地保留了正则解的一个关键特性。我们不妨把这类奇异解先分离出来,称为半正则解。利用半正则性,就可以证明在半正则条件下降秩牛顿法(7)收敛到

牛顿迭代法为何收敛,牛顿迭代法的收敛性如何判断(16)

上一页12345下一页

栏目热文

文档排行

本站推荐

Copyright © 2018 - 2021 www.yd166.com., All Rights Reserved.