计算机科学

首页 > 计算机科学

收敛速度

2018-08-27 10:41:51     所属分类:最优化算法

在数值分析中, 一个收敛序列向其极限逼近的速度称为收敛速度. 该概念多用于最优化算法中; 其被定义为一个迭代序列向其局部最优值逼近 (假设计算过程收敛, 并能逹到最优值) 的速度, 是评价一个迭代法于该问题中发挥的性能的一个重要指针.

目录

  • 1 定义
    • 1.1 商收敛因子及商收敛阶
    • 1.2 根收敛因子及根收敛阶
    • 1.3 两种收敛阶的联系
  • 2 实例
    • 2.1 数列
    • 2.2 向量列
    • 2.3 优化算法的迭代点列
      • 2.3.1 牛顿法
  • 3 参考文献

定义

收敛速度以收敛阶衡量, 亦可以收敛因子描述; 依计算方法的不同, 有下述两种收敛阶及收敛阶.[1]

商收敛因子及商收敛阶

  • 商收敛因子的定义式如下:

商收敛因子也称Q—因子, 商收敛阶也称Q—收敛阶. 利用商收敛因子, 对收敛速度进行描述的方式如下:

  1. 如果, 则称Q—超线性收敛; 如果, 则称Q—线性收敛; 如果, 则称Q—次线性收敛.
  2. 如果, 则称Q—超平方收敛; 如果, 则称Q—平方收敛; 如果, 则称Q—次平方收敛.

注意: Q—线性收敛与Q—平方收敛, 以及Q—次线性收敛与Q—次平方收敛的评判标准有些微差别. “Q—平方收敛”也称为“Q—二次收敛”.

依照Q—平方收敛 (不是Q—线性收敛) 的定义, 可以定义Q—立方收敛 (将改为), Q—四次方收敛等更高Q—收敛阶.


  • 商收敛阶的定义式如下:

对比商收敛因子的描述, 商收敛阶是指求出一个数 (不一定是整数), 使得对于, 点列都是Q—次次方收于, 且对于, 都是Q次方收敛. 而这个数就是点列的商收敛阶.


根收敛因子及根收敛阶

  • 根收敛因子的定义式如下:

根收敛因子也称R—因子, 根收敛阶也称R—收敛阶. 利用根收敛因子, 对收敛速度进行描述的方式如下:

  1. 如果, 则称R—超线性收敛; 如果, 则称R—线性收敛; 如果, 则称R—次线性收敛.
  2. 如果, 则称R—超平方收敛; 如果, 则称R—平方收敛; 如果, 则称R—次平方收敛.

注意: R—次线性收敛与R—次平方收敛的评判标准有些微差别. “R—平方收敛”也称为“R—二次收敛”.

依照R—平方收敛 (不是R—线性收敛) 的定义, 可以定义R—立方收敛 (将改为), R—四次方收敛等更高R—收敛阶.


  • 根收敛阶的定义式如下:

对比根收敛因子的描述, 根收敛阶是指求出一个数 (不一定是整数), 使得对于, 点列都是R—次次方收于, 且对于, 都是R次方收敛. 而这个数就是点列的根收敛阶.


两种收敛阶的联系

对于一个收敛点列而言, 其Q—收敛阶不大于其R—收敛阶, 即

有时, 一个数列的R—收敛阶可能很高, 但其Q—收敛阶可能很低. 当然可以证明, 一个R—收敛阶高的点列至少比某些Q—收敛低的点列收敛得更快.

实例

数列

有如下数列:

容易计算: , 故该数列是Q线性收敛的; 满足的集合为, 此集合的下确界为, 故该数列的收敛阶为. 而同理, 可计算得该数列是R线性收性, Q收敛阶为'.

向量列

有如下向量列:

.

据上作出计算如下,

故数列为Q线性收敛; Q收敛阶为;

故数列为R线性收敛; R收敛阶为.

优化算法的迭代点列

牛顿法

注: 此处的牛顿法指应用于最优化的牛顿法.

可以证明, 如果牛顿法的目标函数的二阶导数在其收敛点处Lipschitz连续, 则满足不等式

此说明牛顿法的迭代点列是Q平方收敛; 另言之, 牛顿法的收敛速度是二次的. [2]

参考文献

  1. ^ Ortega, J R; Rheinboldt, WC. Iterative Solution of Nonlinear Equations in Several Variables. London: Academic Press. 
  2. ^ 袁亚湘. 非线性优化计算方法. 北京: 科学出版社. 2008年2月: 17. ISBN 978-7-03-020883-5 (中文(简体)‎). 
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/339728.html

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
支付宝扫一扫赏金或者微信支付5毛钱,阅读全文

打开微信扫一扫,即可进行阅读全文哦


上一篇:共轭梯度法
下一篇:次梯度法
相关推荐
爱淘宝