牛顿方法及其推广

第四十章

牛顿方法及其推广

40.1牛顿实变函数法

在第39章中，我们研究了确定赋范向量空间e的某些开子集Ω上定义的函数j:Ω→r何时具有局部极值的问题。命题39.1给出了当j可微时的一个必要条件：如果j在u∈Ω处有一个局部极值，那么我们必须

j0（u）=0。

因此我们得到了求导数零点的问题。

j0:Ω→e0，

式中，e0=l（e；r）是从e到r的一组线性连续函数，即e的对偶，如命题39.7后的注释所定义。

这使我们以一种更一般的形式来考虑这个问题，即：给定一个函数f:Ω→y，从赋范向量空间x的开子集Ω到赋范向量空间y，发现

(i) 保证函数f的零点存在的充分条件；即元素a∈Ω，使f（a）=0。

(ii) 一种近似这样一个A的算法，也就是说，其极限是A的Ω点序列（XK）。

当x=y=r时，我们可以使用牛顿方法。我们选取一些初始元素X0∈R“足够接近”F的零点A，并用

，

对于所有k≥0，前提是f0（xk）=06。其思想是将xk+1定义为x轴与点（xk，f（xk））处函数x 7→f（x）图形的切线的交点。实际上，这条切线的方程是

Y−F（XK）=F0（XK）（X−XK）

当y=0时，得到它与x轴的交点，得出

，

如要求。

例如，如果α>0且f（x）=x2−α，牛顿方法得出序列

计算α的平方根√α。可以看出，对于任何X0>0，该方法收敛到√α。实际上，当x0<0时，该方法也会收敛！找出限制是什么。

实数函数的情况表明，用Ωx求函数f:Ω→y的零点的方法如下：给定起点X0∈Ω，序列（Xk）由xk+1=xk−（f0（xk））−1（f（xk））定义。

所有k≥0。

为了使上述内容合理化，必须确保

(1) 所有点XK保持在Ω范围内。

(2) 功能F在Ω范围内可区分。

(3) 导数f0（x）是所有x∈Ω的x到y的双射。

这些条件相当苛刻，但有足够的条件保证它们得到满足。另一个实际问题是，在每个迭代步骤中计算（f0（xk））-1可能非常昂贵。在下一节中，我们将研究牛顿方法的推广，它解决了我们刚刚讨论的问题。

40.2牛顿法的推广

假设F:Ω→Rn由n个函数fi:Ω→R给出，其中，ΩRn。在这种情况下，找到f的零点a等于解系统。

f1（a1…，an）=0 f2（a1…，an）=0

…

fn（a1…，an）=0.

牛顿方法的一次迭代就是求解线性系统。

，

然后设置

，

式中）是x k处f的雅可比矩阵。

一般来说，在每次迭代中计算j（f）（xk），然后求解相应的线性系统是非常昂贵的。如果该方法收敛，则连续向量xk与相应矩阵j（f）（xk）之间的差异应较小。因此，我们得到了牛顿方法的一种变体，它包括保持p连续步骤的相同矩阵（其中p是一些固定整数≥2）：

网络错误
网络错误	网络错误

也可以设置p=∞，也就是说，对所有迭代使用相同的矩阵f0（x0），这将导致表单的迭代。

XK+1=XK−（F0（X0））−1（F（XK）），K≥0，

或者甚至用一个特别的矩阵a0来代替f0（x0），这个矩阵a0很容易反转：

xk+1=xk−a−0 1f（xk），k≥0。

在最后两种情况下，如果可能的话，我们使用f0（x0）或a0的lu因子分解来加速该方法。在某些情况下，甚至可以设置a0=i。

上述考虑使我们得到了广义牛顿法的定义，如Ciarlet[41]所述（第7章）。回想一下，线性映射f∈l（e；f）被称为同构，如果f是连续的、双射的，并且f−1也是连续的。

定义40.1.如果x和y是两个赋范向量空间，如果f:Ω→y是x的某个开子集Ω的函数，则求f的零点的广义牛顿方法包括

(1) 从x到y的线性同构族（a k（x））的序列，对于所有x∈Ω和所有整数k≥0；

(2) 某起点X0∈Ω；

(3) Ω点的序列（XK），定义如下：

x k+1=xk−（ak（x`）−1（f（xk）），k≥0，

其中，对于每个整数k≥0，整数满足条件

0≤`≤K。

函数ak（x）通常取决于f0。

定义40.1给了我们足够的灵活性来捕捉我们之前讨论过的所有情况：

网络错误	网络错误
网络错误网络错误

ak（x）=a0，

其中a0是从x到y的线性同构。第一种情况对应于牛顿的原始方法，其他情况对应于我们刚才讨论的变体。我们也可以得到AK（x）=AK，一个独立于x∈Ω的固定线性同构。

以下由牛顿-康托罗维奇定理启发而来的定理给出了保证由广义牛顿方法构造的序列（XK）收敛到接近X0的F零点的充分条件。尽管技术上很好，但这些条件并不令人惊讶。

定理40.1。设x为Banach空间，设f:Ω→y在开子集Ωx上可微，并假设有常数r、m、β>0，这样如果我们

B=X∈X KX−X0K≤RΩ，

然后

（1）

（2）β<1和

（3）

然后，序列（XK）由

x k+1=xk−a−k 1（x）（f（xk）），0≤≤k

完全包含在b中并收敛到f的零点a，这是f中唯一的零点。

B.此外，收敛是几何的，这意味着

定理40.1的证明可在Ciarlet[41]中找到（第7.5节）。这不是很困难，但技术性很强。

如果假设我们已经知道某个元素a∈Ω是f的零点，那么下一个定理给出了一个广义牛顿方法特殊版本收敛的充分条件。对于这种特殊的方法，线性同构ak（x）独立于x∈Ω。

定理40.2。设x为Banach空间，设f:Ω→y在开子集Ωx上是可微的。如果a∈Ω是一个点，使得f（a）=0，如果f0（a）是线性同构，并且如果有一些λ具有0<λ<1/2，这样

，

然后有一个中心A的闭球B，这样对于每一个X0∈B，序列（XK）定义为

xk+1=xk−a−k 1（f（xk）），k≥0，

完全包含在b中并收敛到a，a是b中f的唯一零。此外，收敛是几何的，这意味着

KXK−AK≤βK KX0−AK，

对于某些β<1。

定理40.2的证明也可在Ciarlet[41]中找到（第7.5节）。

为了完整起见，我们提出了牛顿-康托罗维奇定理的一个版本，它对应于ak（x）=f0（x）的情况。在这种情况下，可以得到更强大的结果，特别是关于上界，我们提出了一个版本，由于GRAGG和TAPIA出现在CIARLET问题7.5-4中[41]。

定理40.3。（Newton–Kantorovich）设x为Banach空间，设f:Ω→y在开子集Ωx上可微。假设存在三个正常数λ、礹、礹和一个点x0∈Ω，这样

，

如果我们让

，

那么bΩ，f0（x0）是l（x；y）的同构，并且

那么，f0（x）是l（x；y）对于所有x∈b的同构，并且序列定义为

xk+1=xk−（f0（xk））−1（f（xk）），k≥0

完全包含在球B中，并收敛到F的0 A，即Ω+中F的唯一0。最后，如果我们写θ=ρ−/ρ+，那么我们有以下界限：

如果

如果，

和

我们现在可以专门化定理40.1和40.2来搜索函数j:oz→r的导数j0:oz→e0的零点，其中有oz e。j的第二个导数j00是一个连续的双线性形式j00:e×e→r，但便于在l（e，e0）中将其看作一个线性映射；continuU线性形式j00（u）由j00（u）（v）=j00（u，v）给出。在下一个定理中，我们假设ak（x）是l（e，e0）中的同构。

定理40.4.设e为Banach空间，设j:Ω→r在开子集Ωe上是两倍可微的，并假设有常数r，m，β>0，这样如果我们

B=X∈E KX−X0K≤RΩ，

然后

（1）

（2）β<1和

（3）

然后，序列（XK）由

x k+1=xk−a−k 1（x）（j0（xk）），0≤≤k

完全包含在b中，并收敛到j0的零点A，这是b中j0的唯一零点。此外，收敛是几何的，这意味着

在下一个定理中，我们假设ak（x）是l（e，e0）中的同构，独立于x∈Ω。

定理40.5。设e为Banach空间，设j:Ω→r在开子集Ωe上是两次可微的。如果a∈Ω是一个点，使得j0（a）=0，如果j00（a）是一个线性同构，并且如果有一些具有0<λ<1/2的λ，那么

，

然后有一个中心为a的闭球b，这样对于每一个x0∈b，由xk+1=xk−a−k 1（j0（xk））定义的序列（xk），k≥0，

完全包含在B中并收敛到A，这是B中j0的唯一零。此外，收敛是几何的，这意味着

KXK−AK≤βK KX0−AK，

对于某些β<1。

当e=rn时，定理40.4给出的牛顿法给出了形式的迭代步骤。

x k+1=xk−a−k 1（x）j（xk），0≤≤k，

式中j（xk）是j在xk处的梯度（这里，我们用rn标识e0）。特别是牛顿的原始方法取ak=j00，迭代步骤为

XK+1=XK−（2J（XK））−1 J（XK），K≥0，

式中2j（xk）是j在xk的黑森。

如Ciarlet[41]所述（第7.5节），广义牛顿方法具有非常广泛的适用性。例如，各种版本的梯度下降法可以看作是牛顿法的实例。示例见第48.9节。

牛顿方法在凸优化特别是内点法中也起着重要作用。提出了牛顿法处理等式约束的一种新方法。我们请读者参考博伊德和范登堡[29]第10章和第11章，以全面阐述这些主题。

40.3总结

本章的主要概念和结果如下：

• 牛顿函数法f:r→r。

• 广义牛顿方法。

• 牛顿-康托罗维奇定理。