1.2方程求根之不定点迭代法

作者: 张一根 | 来源:发表于2019-02-18 14:31 被阅读0次

前言

本章节讲的是另一种基础的求解方程的方法，不定点迭代法。

（一）不定点迭代法的分析

1.定义：

一般地，为了求解非线性方程：
$f(x)=0$
将其转换为等价的形式：
$x = \varphi(x)$
其中 $\varphi(x)$ 称为迭代函数。由于（1）与（2）具有相同的解：

则构造迭代公式有：
$x_{k+1} = \varphi(x_k), k=0,1,2···$
给定初值 $x_0$ ,并且 $\varphi(x)$ 是连续函数，则有：
$x^* = \lim_{k \to \infty} x_{k+1} = \lim_{k \to \infty} \varphi(x_{k})= \varphi(\lim_{k \to \infty} x_{k}) = \varphi(x^*)$

可得 $x^*$ 是方程的（4）的解，也是方程（1） $f(x)=0$ 的解。

上面的方法就称为：不定点迭代法

2.条件：

$\varphi(x)$ 在[a,b]内连续，在(a,b)内可导。

对于任意的 $x \in [a,b]$ ,则有 $\varphi(x) \in [a,b]$

在[a,b]内，存在一个常数L(0<L<1),使得 $|\varphi\prime(x)|\leq L < 1$ ,局部收敛

3.思想：

在收敛函数的前提下，不断的逼近真实值，直到满足我们的精度要求。

如下图，我们可以看到，给定初始值 $p_0$ 后，经过几次的迭代，取值P很逼近两函数的交点，也就是方程的解。

思想.jpg

4.误差：

要使 $x^*-x_k \leq \varepsilon$ ，只需要 $|x_{k+1}-x_k| \leq \varepsilon$

即可以用迭代前后两次的近似根的绝对值大小，来判断 $x_k$ 使否满足精度要求，从而终止迭代的条件。

（二）代码实现

1.流程图：

不定点迭代法.jpg

2.源代码：

（1）feval函数：

def feval(string, a):
    """
        根据值来计算数学表达式。
    :param string: 含有x未知数的数学表达式
    :param a: 自变量x的具体数值
    :return:  数学表达式的计算结果
    """
    count = string.count("x")
    string = string.replace('x', '%f')
    t = (a, ) * count
    result = eval(string % t)
    return result

（2）不定点迭代法：

"""
    不定点迭代法，不断的逼近求解的方法
"""
from my_math.func_math import feval


def item_fun(expr, x_0, r):
    """
        不定点迭代法求解方程的根
    :param expr: 迭代函数的表达式
    :param r: 误差
    :return: 结果值
    """
    k = 0
    # 第一次两点的差距
    x_1 = feval(expr, x_0)
    x_2 = feval(expr, x_1)
    f_1 = abs(x_2 - x_1)

    # 第二次两点的差距
    x_1 = feval(expr, x_2)
    x_2 = feval(expr, x_1)
    f_2 = abs(x_2 - x_1)

    # 判断迭代函数是否收敛
    if f_1 <=  f_2:
        print("函数不收敛")
        result = None
    else:
        while abs(x_2-x_1) > r:
            x_1 = feval(expr, x_2)
            x_2 = feval(expr, x_1)
            k += 1
            print('*' * 20)
            print("次数", k)
            print("x_k", x_1)
            print("x_(k+1)", x_2)
        result = x_2
    print("最后的结果是：", result)
    return result


if __name__ == '__main__':
    item_fun("1+1/(x**2)", 1.45, 10**-15)
    # 最后的结果是： 1.4655713791984073