问题描述
在[a,b]区间内寻找方程x**5-2*x-1=0的根的初始近似值位置，确定不动点迭代的初始点（可能有多个），然后使用不动点迭代法求方程的根（可能有多个根）。前后两次迭代的差的绝对值小于delta后停止迭代。
输入形式
在屏幕上输入3个数，依次为区间左端点值a、右端点值b和所求根的精度值。各数间都以一个空格分隔。根据输入的所求根的精度值可求得delta.
输出形式
每一行输出一个根（精确到小数点后3位）
样例1输入
-1.2 1.5 3
样例1输出
-1.000

-0.519

1.291
样例1说明
输入：左端点a值为-1.2，右端点b值为1.5，前后两次迭代的差的绝对值小于delta=10**(-3)后停止迭代。输出：从小到大顺序输出三个根的值。
代码
import numpy as np

def f(x):
    return x ** 5 - 2 * x - 1

def g1(x):
    return (x**5-1)/2

def g2(x):
    result = (abs(2 * x + 1))**(1 / 5)
    if (2 * x - 1) < 0:
        return -result
    return result

def getEpsilon(x, epsilon):
    maxY = minY = x[0]
    for each in x:
        maxY = max(f(each), maxY)
        minY = min((f(each), minY))
    epsilon = (maxY - minY) * epsilon
    return epsilon

def getInitialVal(x, N, step, epsilon):
    initalVal = []
    for i in range(N + 1):
        y1, y2, y3 = f(x - step), f(x), f(x + step)
        if (y1 * y2 < 0) and (i != 0):
            initalVal.append((x + x - step) / 2)
        if ((y2 - y1) * (y3 - y2) < 0) and (abs(y2) < epsilon):
            initalVal.append(x)
        x += step

    return initalVal

def findFixedPoint(initalVal, delta,epsilon):
    points = []
    for each in initalVal:
        if (abs(g1(each)) < 1):
            points.append(iteration(each, g1, delta,epsilon))
        else:
            points.append(iteration(each, g2, delta,epsilon))
    return points

def iteration(p1, g, delta,epsilon):
    while True:
        p2 = g(p1)
        err =abs(p2-p1)
        relerr = err/(abs(p2)+epsilon)
        if err<delta or relerr<delta:
            return p2
        p1 = p2
                    
def main():
    a, b, c = input().split(' ')
    a = float(a)
    b = float(b)
    c = int(c)
    delta = 10 ** (-c)
    N = 8
    epsilon = 0.01
    step = (b - a) / N
    x = np.arange(a, b + epsilon, epsilon)
    
    epsilon2 = getEpsilon(x,epsilon)
    initalVal = getInitialVal(a, N, step, epsilon2)
    ans = findFixedPoint(initalVal, delta,epsilon)

    for each in ans:
        print('%.3f' % each)
        
if __name__ == '__main__':
    main()

一 不动点是什么？

不动点，其实定义比较简单，对于一些方程，例如f(x)=cosx，那么令cosx=x的点就是函数的不动点，说白了，就是y=x这条直线与函数曲线的交点。这个不动点有什么用呢？请继续往下看。

二 不动点迭代法的实现

不动点迭代法，是求方程的迭代方法。为什么要迭代的求，直接法不好吗？直接法显然比较好，但是存在弊端，比如函数形式较复杂时，求解器不容易直接求得。利用不动点的性质，可以将函数的求解问题转化为不动点方程，从而使用有限次迭代求得方程的解。

其实不动点迭代的代码相对简单而且易懂：

x0=3;

x=x0;

k=10;

ezplot(@(x,f)f-((x-1).^2+1))       %画出函数图像

%构造的不动点方程为：x=2-x,斜率不行，构造其他的本次是两边同时加x^2

axis([-5,5,-3,10])       %固定坐标轴

hold on

for i=1:k                %迭代k次

    x=(2-x0+1*x0^2)/(1*x0+1);                         %-2*x为梯度反方向，step为步长，！最速下降法！

    f_current=(x-1)^2+1;

    f_error=abs((x-1)^2-(x0-1)^2);

    plot(x,f_current,'ro','markersize',7) %标记当前的位置

    drawnow;pause(0.2);

    x0=x;

    if f_error<0.000001

        break;

    end

end

上述代码是利用FPI求解函数的极小值。我们知道，该函数的极值在驻点处，也就是一阶导数为0的地方，求导得。其实一眼就看出来的解，这里只是作为说明，以简单的例子说明一般问题。到这一步了，如何构造FPI呢？其实只需将x剥离出来，也就是:



但是FPI收敛的条件是:



因此，我们需要对迭代方程进行改造。我们在方程两侧加上一项x^2:



这样，得到的FPI即可满足要求。为什么加x^2？其实我也是偶然凑出来的。

三 不动点迭代法的作用

受FPI算法思想的影响，可以创造出一些有趣的算法，用于求类似的方程或方程组的解。

其实之前也不了解该方法，只是看书的时候遇见了一个IRLS-based Iteration shrinkage算法，里面用到了不动点迭代法的思想，加深理解。

书中的问题也是寻找方程组的驻点：



其实使用共轭梯度法或者直接法也能求出解，作为一种新的想法，Adeyemi and Davies将方程两侧均加入了cx，使用构造不动点方程：



将x归纳后，一部分移至一侧，加入迭代索引：



最终：



其中W是对角矩阵，因此其逆就等于是将W的对角元素取倒数即可。但是该方法有个痛点，也就是一旦W对角元素为0，那么它就永远为0了，算法可能就会陷入尴尬的境地。

 

 

 

 

 

 

 

迭代法的作用
许多复杂的求解问题，都可以转换成方程f(x)=0的求解问题。这一系列的解叫做方程的根。对于非线性方程的求解，在自变量范围内往往有多个解，我们将此变化区域分为多个小的子区间，对每个区间进行分别求解。我们在求解过程中，选取一个近似值或者近似区间，然后运用迭代方法逐步逼近真实解。

方程求根的常用迭代法有：二分法、不动点迭代、牛顿法、弦截法
不动点迭代法
简单迭代法或基本迭代法又称不动点迭代法

1、不动点（FixedPoint）

首先来看一下什么是不动点：



换句话说，函数φ的不动点是y=φ(x)与y=x的交点，下图画出了函数y=cos(x)与y=x在区间[0,π/2]的交点，即cos(x)的不动点：



2、不动点迭代（Fixed Point Iteration）

不动点迭代的基本思想：



也就是说，为了求解方程f(x)=0，首先将方程转换为x=g(x)，然后初始化x0，循环迭代xi+1=g(xi)，直到满足收敛收件。

这里将方程f(x)=0转换为x=g(x)是很容易的，比如对于f(x)=x-cos(x)，求解f(x)=0即为求解x-cos(x)=0，即x=cos(x)，因此g(x)=cos(x)。

再例如对于方程：



可以等价为



还可以等价为



也就是说，将方程f(x)=0转换为x=g(x)有不同的方式，因此对方程f(x)=0来说，g(x)也不是唯一的。

3、不动点迭代的收敛性

这个迭代过程是很简单的，但这里有个关键性的问题：迭代收敛么？即经过N次迭代后是否会收敛于不动点？



通俗点讲，若要使不动点迭代收敛，则要求φ(x)在区间[a,b]上的函数值也在此区间内，另外还要求φ(x)的斜率绝对值不大于1。其证明过程比较复杂，有兴趣的可以查阅一些相关文献。
例题
求方程式：x3 - 0.165 × x2 + 3.993 × 10-4 = 0在（0，0.11）上的根
先看看不用迭代法计算的结果
from sympy import *
from sympy.abc import x

def func(x):
    return x**3 - 0.165*x**2 + 3.993*10**(-4)
result = solveset(func(x), x, Interval(0, 0.11))
print(result)

结果：
FiniteSet(0.0623775815137495)


约定一个误差，当误差小于某个数值的时候，迭代停止
代码：
xl = 0  #区间下限
xu = 0.11  #区间上限
x = (xl+xu)/2  #迭代初始值
x_list = [x]
i = 0

while True:
    x = x ** 3 - 0.165 * x ** 2 + 3.993 * 10 ** (-4) + x
    x_list.append(x)
    if len(x_list) > 1:
        i += 1
        error = abs((x_list[-1] - x_list[-2]) / x_list[-1])
        if error < 10**(-6):
            print(f'迭代第{i}次后，误差小于10^-6')
            break
    else:
        pass

结果：
迭代第777次后，误差小于10^-6
所求方程式的根为0.062370654088088

迭代至电脑默认误差为0
xl = 0  #区间下限
xu = 0.11  #区间上限
x = (xl+xu)/2  #迭代初始值
x_list = [x]
i = 0

while True:
    x = x ** 3 - 0.165 * x ** 2 + 3.993 * 10 ** (-4) + x
    x_list.append(x)
    if len(x_list) > 1:
        i += 1
        error = abs((x_list[-1] - x_list[-2]) / x_list[-1])
        if error == 0:
            print(f'迭代第{i}次后，误差为0')
            break
    else:
        pass

print(f'所求方程式的根为{x_list[-1]}')

结果：
迭代第3402次后，误差为0
所求方程式的根为0.062377581513749114

画迭代法
import matplotlib.pyplot as plt
xl = 0  #区间下限
xu = 0.11  #区间上限
x = (xl+xu)/2  #迭代初始值
x_list = [x]
i = 0

x_values = []
y_values = []
while True:
    x = x ** 3 - 0.165 * x ** 2 + 3.993 * 10 ** (-4) + x
    x_list.append(x)
    if len(x_list) > 1:
        i += 1
        error = abs((x_list[-1] - x_list[-2]) / x_list[-1])
        x_values.append(i)
        y_values.append(error)
        if error == 0:
            print(f'迭代第{i}次后，误差为0')
            break
    else:
        pass

print(f'所求方程式的根为{x_list[-1]}')

#设置绘图风格
plt.style.use('ggplot')
#处理中文乱码
plt.rcParams['font.sans-serif'] = ['Microsoft YaHei']
#坐标轴负号的处理
plt.rcParams['axes.unicode_minus']=False
#横坐标是迭代次数
#纵坐标是误差值
plt.plot(x_values,
         y_values,
         color = 'steelblue', # 折线颜色
         marker = 'o', # 折线图中添加圆点
         markersize = 1, # 点的大小
         )
# 修改x轴和y轴标签
plt.xlabel('迭代次数')
plt.ylabel('误差值')
# 显示图形
plt.show()

结果：
迭代第3402次后，误差为0
所求方程式的根为0.062377581513749114


对比牛顿迭代法，牛顿迭代法要快很多，而且准确率也高

牛顿迭代法（Newton’s Method）迭代求根的Python程序

不动点迭代法 一元非线性方程求根 C语言实现



标签：计算方法实验



/*
    本实验用迭代法求方程f(x) = e^(-x) - x + 1的根。
*/
#include <stdio.h>
#include <math.h>

#define maxrept 1000  //最大迭代次数

double fa(double x){  //迭代函数fa(x)
    return exp(-x) + 1;
}

int main(){
    double x1, d;
    double x0 = 100;  //迭代初值x0
    double eps = 0.0005;  //求解精度eps
    int k = 0;  //迭代次数

    do{
        k++;
        x1 = fa(x0);
        printf("%d    %f\n", k, x1);
        d = fabs(x1 - x0);
        x0 = x1;
    }while(d >= eps && k < maxrept);
    if(k < maxrept)  printf("the root of f(x) = 0 is x = %f, k = %d\n", x1, k);
    else  printf("the iteration is failed!\n");  //要求迭代公式收敛，否则会出现溢出

    return 0;
}


实验结果：