方程求解算法 -凯发k8网页登录

  • 文档
main content

方程求解算法

方程求解定义

给定一组（n 个）非线性函数 fi(x)，其中 n 是向量 x 中的分量数，方程求解的目标是找到使所有 fi(x) = 0 的向量 x。

尝试通过最小化分量的平方和来求解方程组。如果平方和为零，则方程组得到求解。fsolve 有三种算法：

  • 信赖域

  • 信赖域 dogleg

  • levenberg-marquardt

所有算法均为大规模的；请参阅大规模算法与中等规模算法。

函数求解单个一维方程。

函数对一个线性方程组求解。

信赖域算法

optimization toolbox™ 求解器中使用的许多方法都基于信赖域，这是一个简单而功能强大的优化概念。

要理解信赖域优化方法，请考虑无约束最小化问题，最小化 f(x)，该函数接受向量参数并返回标量。假设当前点是 n 维空间中的 x，您要通过移至函数值较低的点来寻求改进。为此，该算法使用较简单的函数 q 来逼近 f，该函数需能充分反映函数 f 在点 x 的邻域 n 中的行为。此邻域是信赖域。求解器通过最小化（或近似最小化）n 来计算试探步 s。信赖域子问题是

mins{q(s), s∈n}.

如果 f(x s) < f(x)，求解器将当前点更新为 x s；否则，当前点保持不变，求解器收缩 n（信赖域）并再次计算试探步。

在定义特定信赖域方法以最小化 f(x) 的过程中，关键问题是如何选择和计算逼近 q（在当前点 x 上定义）、如何选择和修改信赖域 n，以及如何准确求解信赖域子问题。

在标准信赖域方法 () 中，二次逼近 q 由 f 在 x 处的泰勒逼近的前两项定义。邻域 n 通常是球形或椭圆形。以数学语言表述，信赖域子问题通常写作

min{12sths stg  such that  ‖ds‖≤δ},(1)

其中，g 是 f 在当前点 x 处的梯度，h 是 hessian 矩阵（二阶导数的对称矩阵），d 是对角缩放矩阵，δ 是正标量，∥ . ∥ 是 2-范数。为了求解公式 1，一种算法（请参阅）会计算 h 的所有特征值，然后将牛顿法应用于以下久期方程

1δ−1‖s‖=0.

这种算法提供 公式 1 的精确解。但是，这需要耗费与 h 的几个分解成比例的时间。因此，处理信赖域问题需要另一种方法。文献（ 和 ）提出了几种基于公式 1 的逼近和启发式策略。optimization toolbox 求解器采用一种逼近方法，将信赖域子问题限制在二维子空间 s 内（ 和 ）。在求解器计算出子空间 s 后，求解公式 1 的工作量是微不足道的，因为在子空间中，问题只是二维的。现在的主要工作转移到子空间的确定上。

求解器借助预条件共轭梯度法（将在下一节中说明）确定二维子空间 s。求解器将 s 定义为由 s1 和 s2 确定的线性空间，其中 s1 是梯度 g 的方向，s2 是近似牛顿方向，即下式的解

h⋅s2=−g,

或是负曲率的方向，

s2t⋅h⋅s2<0.

以此种方式选择 s 背后的理念是强制全局收敛（通过最陡下降方向或负曲率方向）并实现快速局部收敛（通过牛顿步，如果它存在）。

现在，我们可以很容易地指定基于信赖域方法的无约束最小化过程：

  1. 构造二维信赖域子问题。

  2. 求解公式 1 以确定试探步 s。

  3. 如果 f(x s) < f(x)，则 x = x s。

  4. 调整 δ。

求解器重复这四个步骤，直到收敛，从而根据标准规则调整信赖域维度 δ。具体来说，当 f(x s) ≥ f(x) 时，求解器不接受试探步，并减小信赖域大小。有关这方面的讨论，请参阅 和 。

optimization toolbox 求解器用专用函数处理 f 的重要实例：非线性最小二乘、二次函数和线性最小二乘。然而，其底层算法思路与一般情况相同。

预条件共轭梯度法

求解大型对称正定线性方程组 hp = –g 的一种常用方法是预条件共轭梯度法 (pcg)。这种迭代方法需要能够计算 h·v 形式的矩阵-向量积，其中 v 是任意向量。对称正定矩阵 m 是 h 的预条件子。也就是说，m = c2，其中 c–1hc–1 是良态矩阵或具有聚类特征值的矩阵。

在最小化上下文中，您可以假设 hessian 矩阵 h 是对称矩阵。然而，只有在强最小解的邻域内才能保证 h 是正定矩阵。算法 pcg 在遇到负（或零）曲率方向（即 dthd ≤ 0）时退出。pcg 输出方向 p 要么是负曲率方向，要么是牛顿方程组 hp = –g 的近似解。无论哪种情况，p 都有助于定义在非线性最小化信赖域方法中讨论的信赖域方法中使用的二维子空间。

信赖域 dogleg 算法

另一种方法是求解线性方程组以找到搜索方向。牛顿法指定求解搜索方向 dk，满足

j(xk)dk = –f(xk)
xk 1 = xk dk，

其中，j(xk) 是 n×n jacobian 矩阵

j(xk)=[∇f1(xk)t∇f2(xk)t⋮∇fn(xk)t].

牛顿法可能存在问题。j(xk) 可能是奇异的，在这种情况下，牛顿步 dk 甚至没有定义。精确的牛顿步 dk 的计算成本也可能很高昂。此外，如果起点与解的距离较远，牛顿法可能不会收敛。

使用信赖域方法（在非线性最小化信赖域方法中介绍）处理 j(xk) 为奇异时的情况，并提高在起点与解的距离较远时的稳健性。要使用信赖域策略，您需要评价函数来决定 xk 1 比 xk 更好还是更差。一种可能的选择是

mindf(d)=12f(xk d)tf(xk d).

但 f(d) 的最小值不一定是 f(x) 的根。

牛顿步 dk 是下式的根

m(xk d) = f(xk) j(xk)d，

因此它也是 m(d) 的最小值，其中

mindm(d)=12‖m(xk d)‖22=12‖f(xk) j(xk)d‖22=12f(xk)tf(xk) dtj(xk)tf(xk) 12dtj(xk)tj(xk)d.(2)

m(d) 是优于 f(d) 的评价函数选择，因此信赖域子问题是

mind[12f(xk)tf(xk) dtj(xk)tf(xk) 12dtj(xk)tj(xk)d],(3)

满足 ‖d·d‖ ≤ δ。您可以使用 dogleg 策略高效求解此子问题。

有关信赖域方法的概述，请参阅 conn 的论著 和 nocedal 的论著 。

信赖域 dogleg 实现

信赖域 dogleg 算法的关键特征是使用 powell dogleg 过程来计算步 d，从而最小化公式 3。有关详细说明，请参阅 powell 的论著·。

该算法基于 cauchy 步（沿最陡下降方向的步）和高斯-牛顿步的凸组合来为 f(x) 构造步 d。cauchy 步的计算如下

dc = –αj(xk)tf(xk)，

其中 α 最小化公式 2。

高斯-牛顿步通过求解下式来计算

j(xk)·dgn = –f(xk)，

在计算中使用 matlab® （矩阵左除）运算符。

该算法选择步 d，满足

d = dc λ(dgn – dc)，

其中 λ 是区间 [0,1] 中的最大值，使得 ‖d‖ ≤ δ。如果 jk 是（或几乎是）奇异的，则 d 就是 cauchy 方向。

信赖域 dogleg 算法很高效，因为它每次迭代只需进行一次线性求解（用于计算高斯-牛顿步）。此外，该算法比基于高斯-牛顿法的线搜索更稳健。

levenberg-marquardt 方法

levenberg-marquardt 算法（ 和 ）使用的搜索方向是以下线性方程组的解

(j(xk)tj(xk) λki)dk=−j(xk)tf(xk),(4)

也可以是以下方程的解

(j(xk)tj(xk) λkdiag(j(xk)tj(xk)))dk=−j(xk)tf(xk),(5)

其中标量 λk 控制 dk 的模和方向。将 fsolve 选项 scaleproblem 设置为 'none' 以使用公式 4，或将此选项设置为 'jacobian' 以使用公式 5。

当 λk 为零时，dk 方向是高斯-牛顿方向。随着 λk 趋向于无穷，dk 趋向于最陡下降方向，模趋向于零。这意味着，对于一些足够大的 λk，项 f(xk dk) < f(xk) 成立。因此，即便有二阶项对高斯-牛顿法的效率造成限制，该算法仍能控制项 λk 以确保下降。所以，levenberg-marquardt 算法使用的搜索方向综合了高斯-牛顿方向和最陡下降方向。有关详细信息，请参阅最小二乘法文档中的 levenberg-marquardt 方法。

fzero 算法

fzero 尝试计算标量变量 x 的标量函数 f 的根。

fzero 在初始点周围寻找区间，使 f(x) 更改符号。如果指定初始区间而不是初始点，fzero 会检查以确保 f(x) 在区间的端点处有不同符号。初始区间必须是有限的；它不能包含 ±inf。

fzero 综合使用区间二等分、线性插值和逆二次插值来确定 f(x) 的根。有关详细信息，请参阅 。

\ 算法

\ 算法在 matlab 算术运算符有关 的部分有述。

另请参阅

|

相关主题

网站地图