精华内容
下载资源
问答
  • 在[a,b]区间内寻找方程x**5-2*x-1=0的根的初始近似值位置,确定不动点迭代的初始点(可能有多个),然后使用不动点迭代法求方程的根(可能有多个根)。前后两次迭代的差的绝对值小于delta后停止迭代。 输入形式 在...

    问题描述

    在[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求解函数f(x)=(x-1)^{2}+1的极小值。我们知道,该函数的极值在驻点处,也就是一阶导数为0的地方,求导得f^{'}(x)=2(x-1)=0。其实一眼就看出来的解,这里只是作为说明,以简单的例子说明一般问题。到这一步了,如何构造FPI呢?其实只需将x剥离出来,也就是:

    f^{'}(x)=2(x-1)=0 \rightarrow x=2-x \rightarrow x_{k+1}=2-x_{k}=g(x_{k})

    但是FPI收敛的条件是:

    |g^{'}(x_{0})|<1

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

    x+x^{2}=2-x+x^{2}\rightarrow x(x+1)=2-x+x^{2} \rightarrow x=\frac{2-x+x^{2}}{(x+1)} \rightarrow x_{k+1}=\frac{2-x_{k}+x_{k}^{2}}{(x_{k}+1)}

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

    三 不动点迭代法的作用

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

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

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

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

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

    最终:

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

     

     

     

     

     

     

     

    展开全文
  • 方程根的常用迭代法有:二分法、不动点迭代、牛顿、弦截 不动点迭代法 简单迭代法或基本迭代法又称不动点迭代法 1、不动点(FixedPoint) 首先来看一下什么是不动点: 换句话说,函数φ的不动点是y=φ(x)与y

    迭代法的作用

    许多复杂的求解问题,都可以转换成方程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语言实现

    不动点迭代法 一元非线性方程求根 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;
    }
    

    实验结果:
    output

    展开全文
  • 不动点迭代法求方程根

    千次阅读 2019-03-05 10:40:25
    反之亦然,我们称为函数的一个不动点f(x)的零点就等价于g(x)的不动点,选择一个初始近似值,将其带入右端,即,反复迭代之后得到,g(x)称为迭代函数,而且当k-&gt;∞, 例题: 方程在附近的根 x=1.5;...
  • 以下介绍方法单独使用时并不实用,只是利用由浅入深的原理形成知识体系。...二、 不动点迭代法 三、牛顿迭代法 牛顿迭代法的实际应用: 四、弦截 ...
  • 1)在区间[0,1]内用二分法方程ex+10∗x−2e^x+10*x-2ex+10∗x−2的近似根,要求误差超过0.5×10−30.5\times10^{-3}0.5×10−3。 2)取初值x0=0x_0=0x0​=0,用迭代公式xk+1=2−exk10,(k=0,1,2,...)x_{...
  • 方程根:二分法--不动点迭代--牛顿--弦截

    万次阅读 多人点赞 2018-03-09 11:41:54
    方程根:二分法--不动点迭代--牛顿--弦截1.问题概述 许多复杂的求解问题,都可以转换成方程f(x)=0的求解问题。这一系列的解叫做方程的根。对于非线性方程的求解,在自变量范围内往往有多个解,我们将此变化...
  • 不动点迭代法求方程f(x)=x^3-2*x-1=0的根,按以下两种方案实现,分析迭代函数对收敛性的影响。要求输出每次的迭代结果并统计所用的迭代次数,取精度c=0.5*10^(-5),x0=2. 方案一:化方程为等价方程x=pow(2*x+1,...
  • 不动点迭代法求方程的根:是迭代法解方程的根当中经典的方法。 将求解f(x) = 0的问题变成x = h(x)这样的问题。 转变的方程很简单,一般是移项,平方,开根号什么的。 难点: 问题难点就得到的对应不动点迭代方程...
  • 可以得到x0=b/(1-a) 所以f(x)可以变化为这样的形式,f(x)=a*(x-x0)+x0,这样我们可以直接推高次的迭代函数不动点,而不需要采用数学归纳: f(x)=a*(a*x+b)+b Go f(x)=a*{a*(x-x0)+x0}+b ...
  • 单个方程的不动点迭代法

    千次阅读 2018-06-18 09:48:55
    1. 不动点不动点迭代法设 f 是连续函数,为了解方程 把方程变换为等价的方程 其中φ 是连续函数。若x* 是f 的零点,即f(x*)=0 则有 x*称为函数φ 的一个不动点.构造的迭代法 这称为一种...
  • 非线性方程求解 不动点迭代法

    千次阅读 2020-03-23 20:46:15
    非线性方程求解 不动点迭代法 Solution Knowledge 收敛定理一 可以尝试证明一下 1、不动点的存在性 2、不动点的唯一性 3、序列收敛 收敛定理二 这个的条件2更加简洁 可以尝试证明 1、不动点的存在性(其实同定理...
  • 不动点迭代以及其收敛性

    千次阅读 2019-06-08 15:12:52
    不动点迭代以及其收敛性对于迭代的理解不动点迭代迭代的收敛性区间收敛局部收敛 对于迭代的理解   所谓迭代就是反复使用执行某一个过程,并且用本次执行该过程的结果作为下一次执行的起点,不断推进,直到得到满足...
  • [数值分析]不动点迭代法

    千次阅读 2018-09-11 17:25:31
    1.1.1.不动点不动点迭代法 对于方程 f(x)=0(1.1)(1.1)f(x)=0f(x) = 0\tag{1.1} 改写成 x=φ(x)(1.2)(1.2)x=φ(x) x = \varphi(x)\tag{1.2} 若要求x∗x∗x^*满足f(x∗)=0f(x∗)=0f(x^*) = 0,则x∗=φ(x∗)x∗...
  • 简单迭代法不动点迭代

    千次阅读 2018-04-17 22:40:00
    看高斯赛尔德迭代https://blog.csdn.net/zengxyuyu/article/details/53056453,看到简单迭代法: f(x)=0 改写为x=g(x)不断迭代。 https://wenku.baidu.com/view/6c501ba20029bd64783e2c87.html ...
  • 关于不动点迭代和二分法、试值的本质区别,在[上一篇介绍二分法、试值]的博客中提到了(https://blog.csdn.net/weixin_42572826/article/details/104934857),理论上不动点迭代,只能对给定的一个近似解迭代找到...
  • 不动点迭代 function xc = fpi( g, x0, tol ) x(1) = x0; i = 1; while 1 x(i + 1) = g(x(i)); if(abs(x(i+1) - x(i)) < tol) break end i = i + 1; end...
  • 不动点迭代之安德森加速

    千次阅读 2019-10-21 18:36:40
    在数学中,函数不动点(Fixed point, or shortened tofixpoint, also knowns asinvariant point),指的是在函数定义域内的某一个值,经过函数映射后的值还是其本身。在科学和工程领域中,很多问题可以归结为不动点...
  • 在对第4题第3问进行分析的过程中,发现matlab程序能够更加直观的求解计算这个问题。 clc; clear; x=2; m=0.00001; N=60; for k=1:N y=x-1/2/sqrt(3)*(x^2-3); if (abs(x-y))>...程序中x(迭代初始值),m
  • 不动点迭代(Fixed Point Iteration)

    万次阅读 多人点赞 2016-09-07 15:30:14
    题目:不动点迭代(Fixed Point Iteration)  本篇介绍不动点迭代(Fixed Point Iteration)。之所以学习不动点迭代是由于近来看到了FPC算法,即Fixed PointContinuation,有关FPC后面再详述。  从搜索到的资料来...
  • 出f(x)=3x2−ex=0f(x)=3x2−ex=0f(x) = 3x^2-e^x = 0的根,精确到小数点后的第4位。 解 首先我们利用matlab绘图确定出根的大致区域。 由图可知存在三个有根区间[−1,0],[0,1],[3,4][−1,0],[0,1],[3,4][-1,0]...
  • Java练习:牛顿迭代法 Vs. 不动点

    千次阅读 2016-06-12 18:50:46
    SICP中,说明了功能抽象的一种类型:一般化函数的设计。通用函数在通常的Java/C语言的教学中,通常放在后面作为高级内容。如在讲解C的函数指针、Java的模板方法模式的时候。
  • 本科课程参见:《软件学院那些课》 牛顿迭代公式 设已知方程f(x)=0的近似根x0 ,则在x0附近f(x)可用一阶泰勒多项式近似代替....用x1表示p(x)=0的根,它...这就是著名的牛顿迭代公式,它相应的不动点方程为 Jaco...
  • 牛顿迭代公式 设已知方程f(x)=0的近似根x0 ,则在x0附近f(x)可用一阶泰勒多项式近似代替.... 方程f(x)=0可近似地表示为p(x)=0。用x1表示p(x)=0的根,它与f(x)=0的根...这就是著名的牛顿迭代公式,它相应的不动点方程为
  • 【源码】牛顿迭代法求根的matlab实现

    千次阅读 多人点赞 2020-10-06 10:46:20
    牛顿迭代法本质上是一种特殊的不动点迭代,只不过它的迭代函数的构造比较特殊,所以就代码上来看,和不动点迭代法求根的是完全一样的,所不同的是,其输入的不动点迭代函数满足f_x=x-f(x)/f’(x).下面是简要证明 ...
  • 不动点迭代法的具体步骤: 1.选择以个初始点x0,可求得: 2.如此反复的迭代计算可得 3.直到满足精度要求 ,理论上要迭代无穷次。 迭代法有一个点需要注意,不是每一次的迭代都能找都解,因为并不是所有的迭代...
  • 本节书摘来自华章出版社《数值...1.2 不动点迭代 使用计算器或者计算机以一个任意初值开始不断计算函数cos.也就是说,对于一个任意初值应用cos函数,然后对于结果再计算cos,然后得到一个新结果,周而复始.(如果...
  • 方程根:二分法–不动点迭代–牛顿–弦截

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 120,403
精华内容 48,161
关键字:

不动点法求函数迭代