方程求解算法
方程求解定义
给定一组n非线性函数F<年代ub>我(x),n向量中分量的个数是多少x,方程求解的目标是找到一个向量x这就是全部F<年代ub>我(x) = 0。
fsolve
试图通过最小化各分量的平方和来解一个方程组。如果平方和为零,方程组解出。fsolve有三种算法:
信赖域
Trust-region-dogleg
Levenberg-Marquardt
所有算法都是大规模的;看到大规模vs.中等规模算法。
的fzero函数解一个一维方程。
的mldivide函数解线性方程组。
信赖域算法
优化工具箱™求解器中使用的许多方法都基于<年代pan class="emphasis">信任区域,优化中的一个简单而强大的概念。
为了理解信赖域优化方法,考虑无约束最小化问题,最小化f(x),其中函数接受矢量参数并返回标量。假设当前点是x在n-空间,你想通过移动到一个函数值更小的点来改进。为此,算法进行近似f用一个更简单的函数问,合理地反映了函数的行为f在一个社区里N围绕点x。这个社区是托管区。求解器计算一个试步年代通过最小化(或近似最小化)N。可信区域子问题为
求解器将当前点更新为x+年代如果<年代pan class="inlineequation">f(x+年代) <f(x);否则,当前点保持不变,求解器收缩N(信任域),并重复试步计算。
定义特定的信任区域最小化方法的关键问题f(x)是如何选择和计算近似值问(在当前点定义)x),如何选择和修改信任区域N,以及如何准确地解决信任区域子问题。
在标准信任区域方法([48]),即二次逼近问是由泰勒近似的前两项定义的F在x。附近N通常呈球形或椭球状。在数学上,典型地表述了信任区域子问题
(1)
在哪里g的梯度是f在当前点上x,H为黑森矩阵(二阶导数的对称矩阵),D为对角缩放矩阵,Δ为正标量,‖。‖是2标准。来解决方程1,算法(参见[48])可以计算出的所有特征值H然后应用牛顿过程特征方程
这种算法提供了一个精确的解方程1。然而,这需要的时间正比于若干因数分解H。因此,信任区域问题需要一种不同的方法。几种近似和启发式策略,基于方程1,已在文献中提出([42]和[50]).优化工具箱求解器遵循一种近似方法,该方法将信任区域子问题限制为二维子空间年代([39]和[42]).在求解器计算出子空间之后年代,要解的功方程1是平凡的,因为在子空间中,问题是二维的。现在主要的工作转移到确定子空间。
求解器确定二维子空间年代借助预条件共轭梯度法(下一节描述)。求解器定义了年代作为张成的线性空间年代1和年代2,在那里年代1在梯度方向上吗g,年代2要么是近似值牛顿方向,也就是一个解
或者方向负曲率,
这种选择背后的哲学年代是强制全局收敛(通过最陡下降方向或负曲率方向),并实现快速局部收敛(通过牛顿步,当它存在时)。
使用信任区域方法的无约束最小化过程现在很容易指定:
给出二维信任域子问题的公式。
解决方程1确定试验步长年代。
如果<年代pan class="inlineequation">f(x+年代) <f(x),然后<年代pan class="inlineequation">x=x+年代。
Δ调整。
求解器重复这四个步骤直到收敛,并根据标准规则调整信任域维度Δ。特别地,求解器在不接受试步时减小信任区域大小,当<年代pan class="inlineequation">f(x+年代)≥f(x)。看到[46]和[49]进行这方面的讨论。
优化工具箱求解器处理的重要案例f具有专门的函数:非线性最小二乘,二次函数和线性最小二乘。然而,基本的算法思想与一般情况是相同的。
预条件共轭梯度法
求解大型对称正定线性方程组的常用方法<年代pan class="inlineequation">惠普= -g是预条件共轭梯度法(PCG)。这种迭代方法要求能够计算这种形式的矩阵向量乘积下载188bet金宝搏H·v在哪里v是一个任意向量。对称正定矩阵米是一个<年代pan class="emphasis">预调节器为H。也就是说,<年代pan class="inlineequation">米=C2,在那里<年代pan class="inlineequation">C1HC1是一个条件良好的矩阵或具有聚类特征值的矩阵。
在最小化的情况下,你可以假设Hessian矩阵H是对称的。然而,H仅在强最小器的邻域中保证是正定的。算法PCG在遇到负(或零)曲率方向时退出,即<年代pan class="inlineequation">d<年代up>T高清≤0。PCG输出方向p是负曲率的方向还是牛顿系统的近似解<年代pan class="inlineequation">惠普= -g。无论哪种情况,p帮助定义中讨论的信任区域方法中使用的二维子空间非线性最小化的信赖域方法。
Trust-Region-Dogleg算法
另一种方法是通过求解线性方程组来确定搜索方向。牛顿法规定求解搜索方向d<年代ub>k这样
J(x<年代ub>k )d<年代ub>k= -F(x<年代ub>k)xk+ 1=x<年代ub>k +d<年代ub>k ,
在哪里J(x<年代ub>k)是n——- - - - - -n雅可比矩阵
牛顿的方法是有问题的。J(x<年代ub>k)可能是奇异的,在这种情况下牛顿步d<年代ub>k甚至没有定义。同样,牛顿步d<年代ub>k计算起来可能很昂贵。另外,如果起点离解较远,牛顿法可能不收敛。
使用可信区域技术(在非线性最小化的信赖域方法)处理下列情况J(x<年代ub>k)是奇异的,并且在起点远离解时提高鲁棒性。要使用信任区域策略,您需要一个价值函数来决定是否xk+ 1比好还是比坏x<年代ub>k 。一个可能的选择是
但至少是f(d)不一定是…的词根F(x).
牛顿步d<年代ub>k是的词根
米(x<年代ub>k +d) =F(x<年代ub>k) +J(x<年代ub>k)d,
所以它也是最小值米(d),
(2)
米(d)是一个更好的选择价值函数f(d),则信任区域子问题为
(3)
这样<年代pan class="inlineequation">‖D·d‖≤Δ。你可以使用狗腿策略有效地解决这个子问题。
有关信任区域方法的概述,请参阅Conn[4]和Nocedal[31]。
Trust-Region-Dogleg实现
信任区域狗腿算法的关键特点是使用Powell狗腿过程来计算步长d,使方程3。有关详细说明,请参见Powell[34]。
算法构造步骤d由柯西阶跃(沿最陡下降方向的阶跃)和高斯-牛顿阶跃的凸组合而成f(x).柯西步长计算为
d<年代ub>C = -αJ(x<年代ub>k)<年代up>TF(x<年代ub>k ),
在哪里α最小化方程2。
高斯-牛顿阶跃是通过求解得到的
J(x<年代ub>k )·d<年代ub>GN= -F(x<年代ub>k),
使用MATLAB<年代up>®mldivide
(矩阵左除)算子。
算法选择步长d如此......以至于......
d=d<年代ub>C +λ(d<年代ub>GN- - - - - -d<年代ub>C),
在哪里λ区间[0,1]中的最大值是否满足<年代pan class="inlineequation">‖d‖≤Δ。如果J<年代ub>k
是(几乎)单数,d就是柯西方向。
信任区域狗腿算法是高效的,因为它每次迭代只需要一次线性求解(用于计算高斯-牛顿步骤)。此外,该算法比使用高斯-牛顿法进行直线搜索具有更强的鲁棒性。
方程求解定义
给定一组n非线性函数F<年代ub>我(x),n向量中分量的个数是多少x,方程求解的目标是找到一个向量x这就是全部F<年代ub>我(x) = 0。
fsolve
试图通过最小化各分量的平方和来解一个方程组。如果平方和为零,方程组解出。fsolve有三种算法:
信赖域
Trust-region-dogleg
Levenberg-Marquardt
所有算法都是大规模的;看到大规模vs.中等规模算法。
的fzero函数解一个一维方程。
的mldivide函数解线性方程组。
给定一组 信赖域 Trust-region-dogleg Levenberg-Marquardt 所有算法都是大规模的;看到 的 的fsolve
试图通过最小化各分量的平方和来解一个方程组。如果平方和为零,方程组解出。
fzero
mldivide
信赖域算法
优化工具箱™求解器中使用的许多方法都基于<年代pan class="emphasis">信任区域,优化中的一个简单而强大的概念。
为了理解信赖域优化方法,考虑无约束最小化问题,最小化f(x),其中函数接受矢量参数并返回标量。假设当前点是x在n-空间,你想通过移动到一个函数值更小的点来改进。为此,算法进行近似f用一个更简单的函数问,合理地反映了函数的行为f在一个社区里N围绕点x。这个社区是托管区。求解器计算一个试步年代通过最小化(或近似最小化)N。可信区域子问题为
求解器将当前点更新为x+年代如果<年代pan class="inlineequation">f(x+年代) <f(x);否则,当前点保持不变,求解器收缩N(信任域),并重复试步计算。
定义特定的信任区域最小化方法的关键问题f(x)是如何选择和计算近似值问(在当前点定义)x),如何选择和修改信任区域N,以及如何准确地解决信任区域子问题。
在标准信任区域方法([48]),即二次逼近问是由泰勒近似的前两项定义的F在x。附近N通常呈球形或椭球状。在数学上,典型地表述了信任区域子问题
(1)
在哪里g的梯度是f在当前点上x,H为黑森矩阵(二阶导数的对称矩阵),D为对角缩放矩阵,Δ为正标量,‖。‖是2标准。来解决方程1,算法(参见[48])可以计算出的所有特征值H然后应用牛顿过程特征方程
这种算法提供了一个精确的解方程1。然而,这需要的时间正比于若干因数分解H。因此,信任区域问题需要一种不同的方法。几种近似和启发式策略,基于方程1,已在文献中提出([42]和[50]).优化工具箱求解器遵循一种近似方法,该方法将信任区域子问题限制为二维子空间年代([39]和[42]).在求解器计算出子空间之后年代,要解的功方程1是平凡的,因为在子空间中,问题是二维的。现在主要的工作转移到确定子空间。
求解器确定二维子空间年代借助预条件共轭梯度法(下一节描述)。求解器定义了年代作为张成的线性空间年代1和年代2,在那里年代1在梯度方向上吗g,年代2要么是近似值牛顿方向,也就是一个解
或者方向负曲率,
这种选择背后的哲学年代是强制全局收敛(通过最陡下降方向或负曲率方向),并实现快速局部收敛(通过牛顿步,当它存在时)。
使用信任区域方法的无约束最小化过程现在很容易指定:
给出二维信任域子问题的公式。
解决方程1确定试验步长年代。
如果<年代pan class="inlineequation">f(x+年代) <f(x),然后<年代pan class="inlineequation">x=x+年代。
Δ调整。
求解器重复这四个步骤直到收敛,并根据标准规则调整信任域维度Δ。特别地,求解器在不接受试步时减小信任区域大小,当<年代pan class="inlineequation">f(x+年代)≥f(x)。看到[46]和[49]进行这方面的讨论。
优化工具箱求解器处理的重要案例f具有专门的函数:非线性最小二乘,二次函数和线性最小二乘。然而,基本的算法思想与一般情况是相同的。
预条件共轭梯度法
求解大型对称正定线性方程组的常用方法<年代pan class="inlineequation">惠普= -g是预条件共轭梯度法(PCG)。这种迭代方法要求能够计算这种形式的矩阵向量乘积下载188bet金宝搏H·v在哪里v是一个任意向量。对称正定矩阵米是一个<年代pan class="emphasis">预调节器为H。也就是说,<年代pan class="inlineequation">米=C2,在那里<年代pan class="inlineequation">C1HC1是一个条件良好的矩阵或具有聚类特征值的矩阵。
在最小化的情况下,你可以假设Hessian矩阵H是对称的。然而,H仅在强最小器的邻域中保证是正定的。算法PCG在遇到负(或零)曲率方向时退出,即<年代pan class="inlineequation">d<年代up>T高清≤0。PCG输出方向p是负曲率的方向还是牛顿系统的近似解<年代pan class="inlineequation">惠普= -g。无论哪种情况,p帮助定义中讨论的信任区域方法中使用的二维子空间非线性最小化的信赖域方法。
优化工具箱™求解器中使用的许多方法都基于<年代pan class="emphasis">信任区域, 为了理解信赖域优化方法,考虑无约束最小化问题,最小化
求解器将当前点更新为 定义特定的信任区域最小化方法的关键问题 在标准信任区域方法( 在哪里
这种算法提供了一个精确的解 求解器确定二维子空间
或者方向
这种选择背后的哲学 使用信任区域方法的无约束最小化过程现在很容易指定: 给出二维信任域子问题的公式。 解决 如果<年代pan class="inlineequation">f Δ调整。 求解器重复这四个步骤直到收敛,并根据标准规则调整信任域维度Δ。特别地,求解器在不接受试步时减小信任区域大小,当<年代pan class="inlineequation">f 优化工具箱求解器处理的重要案例 求解大型对称正定线性方程组的常用方法<年代pan class="inlineequation">惠普 在最小化的情况下,你可以假设Hessian矩阵
(1)
预条件共轭梯度法
Trust-Region-Dogleg算法
另一种方法是通过求解线性方程组来确定搜索方向。牛顿法规定求解搜索方向d<年代ub>k这样
J(x<年代ub>k )d<年代ub>k= -F(x<年代ub>k)xk+ 1=x<年代ub>k +d<年代ub>k ,
在哪里J(x<年代ub>k)是n——- - - - - -n雅可比矩阵
牛顿的方法是有问题的。J(x<年代ub>k)可能是奇异的,在这种情况下牛顿步d<年代ub>k甚至没有定义。同样,牛顿步d<年代ub>k计算起来可能很昂贵。另外,如果起点离解较远,牛顿法可能不收敛。
使用可信区域技术(在非线性最小化的信赖域方法)处理下列情况J(x<年代ub>k)是奇异的,并且在起点远离解时提高鲁棒性。要使用信任区域策略,您需要一个价值函数来决定是否xk+ 1比好还是比坏x<年代ub>k 。一个可能的选择是
但至少是f(d)不一定是…的词根F(x).
牛顿步d<年代ub>k是的词根
米(x<年代ub>k +d) =F(x<年代ub>k) +J(x<年代ub>k)d,
所以它也是最小值米(d),
(2)
米(d)是一个更好的选择价值函数f(d),则信任区域子问题为
(3)
这样<年代pan class="inlineequation">‖D·d‖≤Δ。你可以使用狗腿策略有效地解决这个子问题。
有关信任区域方法的概述,请参阅Conn[4]和Nocedal[31]。
Trust-Region-Dogleg实现
信任区域狗腿算法的关键特点是使用Powell狗腿过程来计算步长d,使方程3。有关详细说明,请参见Powell[34]。
算法构造步骤d由柯西阶跃(沿最陡下降方向的阶跃)和高斯-牛顿阶跃的凸组合而成f(x).柯西步长计算为
d<年代ub>C = -αJ(x<年代ub>k)<年代up>TF(x<年代ub>k ),
在哪里α最小化方程2。
高斯-牛顿阶跃是通过求解得到的
J(x<年代ub>k )·d<年代ub>GN= -F(x<年代ub>k),
使用MATLAB<年代up>®mldivide
(矩阵左除)算子。
算法选择步长d如此......以至于......
d=d<年代ub>C +λ(d<年代ub>GN- - - - - -d<年代ub>C),
在哪里λ区间[0,1]中的最大值是否满足<年代pan class="inlineequation">‖d‖≤Δ。如果J<年代ub>k
是(几乎)单数,d就是柯西方向。
信任区域狗腿算法是高效的,因为它每次迭代只需要一次线性求解(用于计算高斯-牛顿步骤)。此外,该算法比使用高斯-牛顿法进行直线搜索具有更强的鲁棒性。
另一种方法是通过求解线性方程组来确定搜索方向。牛顿法规定求解搜索方向 J 在哪里
牛顿的方法是有问题的。 使用可信区域技术(在
但至少是 牛顿步 米 所以它也是最小值 米 这样<年代pan class="inlineequation">‖ 有关信任区域方法的概述,请参阅Conn 信任区域狗腿算法的关键特点是使用Powell狗腿过程来计算步长 算法构造步骤 d<年代ub>C 在哪里 高斯-牛顿阶跃是通过求解得到的 J 使用MATLAB<年代up>® 算法选择步长 d 在哪里 信任区域狗腿算法是高效的,因为它每次迭代只需要一次线性求解(用于计算高斯-牛顿步骤)。此外,该算法比使用高斯-牛顿法进行直线搜索具有更强的鲁棒性。
(2)
(3)
Trust-Region-Dogleg实现
mldivide
(矩阵左除)算子。
Levenberg-Marquardt方法
Levenberg-Marquardt算法([25],[27])使用的搜索方向是线性方程组的解
(4)
或者,任意地,方程
(5)
其中标量λ<年代ub>k的大小和方向d<年代ub>k。设置fsolve选项ScaleProblem来“没有”使用方程4,或将此选项设置为的雅可比矩阵使用方程5。
当λ<年代ub>k方向是0吗d<年代ub>k是高斯-牛顿法。作为λ<年代ub>k趋于无穷,d<年代ub>k趋向于最陡的下降方向,大小趋向于零。这意味着,对于一些足够大的λ<年代ub>k,术语<年代pan class="inlineequation">F(x<年代ub>k +d<年代ub>k) <F(x<年代ub>k)适用。因此,该算法可以对项进行控制λ<年代ub>k尽管二阶项限制了高斯-牛顿方法的效率,但仍能保证下降。因此,Levenberg-Marquardt算法使用介于高斯-牛顿方向和最陡下降方向之间的搜索方向。有关详细信息,请参见Levenberg-Marquardt方法在最小二乘文档中。
Levenberg-Marquardt算法( 或者,任意地,方程 其中标量 当
(4)
(5)
fzero算法
fzero试图找到标量函数的根f标量变量的x。
fzero在初始点周围寻找一个区间,这样f(x)改变标志。如果你指定一个初始间隔而不是初始点,fzero检查以确保f(x)在区间的端点处有不同的符号。初始区间必须是有限的;它不能包含±正。
fzero使用区间对分、线性插值和逆二次插值的组合来定位的根f(x).看到fzero了解更多信息。
fzero
fzero
fzero
fzero
\算法
的\算法的描述在MATLAB运算符部分为mldivide。
的mldivide
另请参阅
fsolve
|<年代pan itemscope itemtype="//www.tatmou.com/help/schema/MathWorksDocPage/SeeAlso" itemprop="seealso">fzero
相关的话题
fsolve
|<年代pan itemscope itemtype="//www.tatmou.com/help/schema/MathWorksDocPage/SeeAlso" itemprop="seealso">fzero