算法的乐趣之迭代法

迭代法

迭代法和递推法的关系

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

迭代法的基本思想

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

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

计算一个数的平方根，数学上一般用迭代法，常用的迭代递推公式是：

$$x_{n+1}=\frac{1}{2}(x_n+\frac{a}{x_n})$$

以下是代码实现：

#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;
}