算法的乐趣之迭代法

发布 : 2019-03-24 浏览 :

迭代法

迭代法和递推法的关系

迭代法一般用于求解数学问题,比如求解一元高次方程、线性和非线性方程组和曲线拟合等问题。
迭代法作为很多数学问题的求解算法,是解决数学问题的一种常用的算法模式,可以独立构成解决问题的算法。递推法作为一种设计算法的常用思想,没有固定的算法实现模式,通常是与其他算法模式配合形成算法实现。比如线性动态规划问题,一般都有明确的子问题最优解递推公式,递推思想常常作为算法实现的一部分融入到动态规划算法的实现中。

迭代法的基本思想

迭代法的实现,一般需要确定以下三个要点。

  • 确定迭代变量:迭代变量一般就是要求解的问题的解,利用迭代递推公式可以不断地由旧值递推出新值。根据问题的不同,迭代变量可以是一个,也可以是多个。确定迭代变量,通常还要根据迭代递推关系给出迭代变量的初始值,这一点也很重要。
  • 确定迭代递推关系:迭代递推关系是根据旧值计算新值的关系或公式,这是迭代法实现的关键,如果不能确定迭代关系,则无法用迭代法实现算法。
  • 确定迭代终止条件:迭代终止条件是控制迭代过程退出的关键条件。迭代不可能无休止地进行,必须设置迭代终止条件,在适当的时候退出迭代。迭代终止条件一般有三种假设:其一是迭代变量已经求得问题的精确值;其二是迭代变量无法得到精确值,但是某个迭代的值的精度已经满足要求;其三是指定明确的迭代计算次数。迭代算法的具体实现,可根据问题的类型选择迭代终止条件。一般情况下,为了防止迭代关系在某个区间上发散(不收敛)使得算法进入死循环,都会把第三个条件作为异常退出条件和其他迭代终止条件配合使用,也就是说,即使无法得到符合条件的解,只要迭代计算次数达到某个限制值,也退出迭代过程。

计算一个数的平方根,数学上一般用迭代法,常用的迭代递推公式是:
$$x_{n+1}=\frac{1}{2}(x_{n}+\frac{a}{x_{n}})$$
以下是代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include<cmath>

const int LOOP_LIMIT = 1000;

std::pair<bool, double> cl_root(double a, double eps)
{
double xi = a / 2.0; //初始值用 a 的一半,很多人的选择
double xt;
int count = 0;
do
{
xt = xi;
xi = (xt + (a / xt)) / 2.0;
count++; //用于检查是否收敛的计数器
if (count >= LOOP_LIMIT)
{
return {false, 0.0}; //不收敛,返回失败
}
} while (std::fabs(xi - xt) > eps);

return { true, xi };
}

int main()
{
int a = 2;
std::pair<bool, double> rtn = cl_root(a, 0.0000001);

if (rtn.first)
{
std::cout << "root of " << a << " is " << rtn.second << std::endl;
}
else
{
std::cout << "fail to get the root of " << a << std::endl;
}

return 0;
}

本文作者 : HeoLis
原文链接 : http://ishero.net/算法的乐趣之迭代法.html
版权声明 : 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!

学习、记录、分享、获得

微信扫一扫, 向我投食

微信扫一扫, 向我投食