相关文章推荐
朝气蓬勃的电脑桌  ·  清代学霸皇子养成记：早晨四点上学 一年歇六天 ...·  6 月前    · 
怕老婆的鸵鸟  ·  “旗手”雷声32强赛出局，这也是他奥运花剑个 ...·  1 年前    · 
怕老婆的匕首  ·  《舌尖上的中国》引发大众乡愁情绪_手机新浪网·  1 年前    · 
不羁的桔子  ·  【触摸2023·菏泽百姓身边的变化】完善城市 ...·  2 年前    · 
八块腹肌的机器猫  ·  关于公布研究生申请学位创新成果相关文件的通知 ...·  2 年前    · 
Code  ›  【机器学习】数值分析02——任意方程求根
数值分析 误差函数 一阶导数 不动点定理
https://juejin.cn/post/7065236870715670541
沉着的钢笔
2 年前

（Github）MachineLearning Math

方程和函数是代数数学中最为重要的内容之一，从初中直到大学，我们都在研究着方程与函数，甚至我们将图形代数化，从而发展出了代数几何、解析几何的内容。而在方程与函数中，我们研究其性质最多的，往往就是方程的根（零点），即使是研究方程的极值点、鞍点等，我们无非也只是研究其微商的零点。 我们在初等数学中已经学过许多简单初等函数、线性方程的求解方法，在本文中，我们重点讨论任意方程，尤其是计算困难的非线性方程的求根方法。

2.1分类和介绍

方程就是指含有未知数的等式。是表示两个数学式（如两个数、函数、量、运算）之间相等关系的一种等式，使等式成立的未知数的值称为“解”或“根”。在这里，根据一些性质的不同，我们将方程分成以下几类：

  • 线性方程：本质是等式两边乘以任何相同的非零数，方程的本质都不受影响。通常认为只含有一次项的方程。
  • 非线性方程：是因变量与自变量之间的关系不是线性的关系的方程。
  • 多项式方程
  • 超越方程：指含有未知量的超越式（指数、对数、三角函数、反三角函数等）的方程。换言之，超越方程中都有无法用含有未知数的多项式、分式或开方表示的式子。

    • 2.2方程的零点（根、解）

    若有一个值或一些值能够使得方程 f ( x ) = 0 f(x)=0

    若方程有且只有一个解 x ∗ x^* ，那么我们称方程有单根 x ∗ x^* 。

    若对于方程 f ( x ) = 0 f(x)=0

    PS：若方程是简单幂函数多项式组成，那么方程的解的数量应和最高此项的数值一致，因为存在虚根。

    3.求根方法

    求根的方法基本上大同小异，都是通过区间去逼近方程的根的点。

    首先我们说一个定理1：对于实函数方程 f ( x ) = 0 f(x)=0

    3.1二分法

    3.1.1普通二分法的原理及操作

    二分法和算法中的二分搜索法非常的类似，取定有根区间 [ a , b ] [a,b] 进行对分，求得 m i d = a + b 2 mid = \frac{a+b}{2}

    产生的截断误差为 ∣ e n − 1 ∣ = x n + 1 − x ∗ ≤ [ b n − a n ] = b 0 − a 0 2 n |e_{n-1}| = x_{n+1} - x^*\leq[b_n - a_n] = \frac{b_0 - a_0}{2^n}

    可以计算出最小迭代次数为 n = l g ( c 0 − a 0 ) − l g ϵ l g 2 n = \frac{lg(c_0-a_0)-lg\epsilon}{lg2}

    代码实现（更多语言的代码见仓库中Code文件夹）： 

    private static double epsilon = 0.001;
// func为函数，写法如x=>x*x+2*x-1，a，b必须为有效的含根开区间
public static double Binary(Func<double, double> func, double a, double b)
    var f1 = func.Invoke(a);
    var f2 = func.Invoke(b);
    if (f1 * f2 > 0)
        throw new ArgumentException("此区间无根或根不唯一");
    double mid = (a + b) / (double)2;
    var fm = func.Invoke(mid);
    if (fm == 0)
        return fm;
    if (f1 * fm < 0)
        b = mid;
    else if (f2 * fm < 0)
        a = mid;
    if (Math.Abs(b - a) <= epsilon)
        return (a + b) / (double)2;
    return Binary(func, a, b);

    3.1.2普通二分法准确度及速度分析
    

    假设[a,b]\left[a,b\right]是二分法的初始区间，在进行n此二分之后，得到的最终根的分布区间[an,bn][a_n,b_n]
    

    e=∣xc−r∣<b−a2n+1e = \left|x_c-r\right|<\frac{b-a}{2^{n+1}}
    

    若e<12×10−pe<\frac{1}{2}\times10^{-p}
    

    事实上我们也可以简单的计算出函数执行的次数为n+2次。
    

    3.2浅谈迭代
    

    3.2.1 迭代是什么
    

    迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。
重复执行一系列运算步骤，从前面的量依次求出后面的量的过程。此过程的每一次结果，都是由对前一次所得结果施行相同的运算步骤得到的。这篇文章中对于迭代有一个非常不错的概述究竟什么是迭代？
    

    3.2.2 不动点的定义
    

    各位可以尝试以下操作，
    

  • 随意输入一个数字λ\lambda
    • 

  • 然后对其进行cosλcos\lambda运算，
    • 

  • 将运算结果作为新的值传回cosxcosx函数之中
    • 

    当你一直重复以上三个操作，你会发现数字最后会定格在0.73908513左右不动了。这是一个非常有趣的现象，事实上我们的这个操作就是xn=cosxn−1x_n = cosx_{n-1}
    

    这就是我们不动点的一种实际情况，不动点原理是数学上一个重要的原理，也叫压缩映像原理或巴拿赫（Banach）不动点定理，完整的表达：完备的度量空间上，到自身的一个压缩映射存在唯一的不动点。用初等数学可以这么理解：连续映射ff的定义域包含值域，则存在一个xx使得f(x)=xf(x)=x
    

    若某函数满足f(λ)=λ,λ∈Rf(\lambda)=\lambda,\lambda \in R
    

    不动点的存在定理：若某函数y=f(x)y=f(x)
    

    3.2.3 函数的相似性
    

    我们常常说图形之间的相似，事实上函数也有其相似的定义。若函数f(x)f(x)对其换元，令t=φ(x),x=φ−1(t),f(x)=>f(φ−1(t))t = \varphi(x),x=\varphi^{-1}(t),f(x)=>f(\varphi^{-1}(t))
    

    现在做出如下变换，将外层的f(x)f(x)换元为f(φ−1(t))f(\varphi^{-1}(t))，那么二次迭代式就变成了g(t)=φ(f(φ−1(t)))g(t) = \varphi(f(\varphi^{-1}(t)))
    

    我们在这给出总结和定义：若函数g(x),f(x),φ(x)g(x),f(x),\varphi(x)
    

    若函数g(x)的不动点为x0，则有若函数g(x)的不动点为x_0，则有
    

    g(x0)=x0=φ(f(φ−1(x0)))g(x_0)=x_0=\varphi(f(\varphi^{-1}(x_0)))
    

    根据反函数性质有φ(φ−1(x))=x根据反函数性质有\varphi(\varphi^{-1}(x))=x




    

    

    故f(φ−1(x0))=φ−1(x0)=x0,φ−1(x0)是f(x)的一个不动点故f(\varphi^{-1}(x_0)) = \varphi^{-1}(x_0)=x_0,\varphi^{-1}(x_0)是f(x)的一个不动点
    

    通过上述得出的不动点，很容易通过刚才讲的内容得出φ−1(x0)\varphi^{-1}(x_0)
    

    3.2.4 迭代收敛速度
    

    迭代是一种逼近、利用数列、函数收敛的性质进行求解的方法，那么对于收敛的速度，我们很难直接从数值看出速度，因为收敛过程中，误差的变化是越来越小的，因此我们再次进行一个比阶。
    

    ∃p∈N&C>0,lim⁡k→∞ek+1ekp=C\exists p\in N \And C>0,\displaystyle \lim_{k \to \infty}\frac{e_{k+1}}{e_k^p} = C
    

    ek=∣xk−x∗∣e_k = |x_k-x^*|
    

    p={p=1,线性收敛p=2,平方收敛p>2,高阶收敛p=
\begin{cases}
p=1,线性收敛\\
p=2,平方收敛\\
p>2,高阶收敛
\end{cases}
    

    并且有一个定理：若φ(x)\varphi(x)在所求的根x∗x^*邻域有连续的二阶导数，并且有∣φ′(x)∣<1|\varphi^{'}(x)|<1
    

    当φ′(x)≠0\varphi^{'}(x)\neq0
    

    当φ′(x)=0,φ′′(x)≠0\varphi^{'}(x)=0,\varphi^{''}(x)\neq0
    

    证明过程留给读者，只需要利用泰勒展开是便可以证明该定理。
    

    3.3不动点迭代法
    

    3.3.1不动点迭代法的原理及操作
    

    迭代法是将方程求根问题转换成了函数求交点问题再转换成数列求极限的问题，这个过程中，对方程进行一个巧妙的变换之后，方程就可以在若干次迭代之后解出一个近似解。
    

    操作方法如下：首先将方程f(x)=0f(x)=0
    

    我们即使构造出了x=g(x)x=g(x)
    

    迭代过程收敛的情况如下图所示：

    如果说我们的导数不满足条件，那么我们的迭代将会发散：
    

    // func是迭代函数而不是实际函数
public static double Iterative(Func<double, double> func, double x)
    double temp = func.Invoke(x);
    if (Math.Abs(temp - x) <= epsilon)
        return temp;
    x = temp;
    return Iterative(func, x);

    3.3.2迭代法的收敛性证明
    

    在这里，我们将证明迭代法求根的合理性和可行性。
    

    前提条件：设函数φ(x),x∈[a,b]\varphi(x), x\in[a,b]
    

    ∀x∈[a,b],φ(x)∈[a,b]\forall x\in [a,b],\varphi(x)\in[a,b]
    

    ∃L∈(0,1),∀x∈[a,b],∣φ′(x)∣≤L\exists L \in (0,1),\forall x\in[a,b],|\varphi^{'}(x)|\leq L
    

    要证明和解决以下命题和问题：
    

    在x∈[a,b],∃x∗,φ(x∗)=0x\in[a,b],\exists x^*,\varphi(x^*) = 0
    

    ∀x0∈[a,b]\forall x_0\in[a,b]
    

    求解误差分析式
    

    现在开始证明
    

    1：证明在区间内有且只有一个根存在：
    

    证：在x∈[a,b]x \in [a,b]
    

    又因为φ(x)∈[a,b]\varphi(x) \in [a,b]
    

    利用反证法：若在[a,b]上还有一实根xˉ\bar{x}
    

    x∗−xˉ=φ(x∗)−φ(xˉ)=φ′(ξ)(x∗−xˉ)⟹φ′(ξ)=1x^*-\bar{x} = \varphi(x^*)-\varphi(\bar{x}) = \varphi^{'}(\xi)(x^*-\bar{x})\Longrightarrow \varphi^{'}(\xi) = 1
    

    显然与假设不符合。
    

    2：证明这个根收敛于x∗x^*
    

    根据拉格朗日中值定理，容易知道
    

    x∗−xk+1=φ(x∗)−φ(xk)=φ′(ξ)(x∗−xk)x^*-x_{k+1} = \varphi(x^*)-\varphi(x_k) = \varphi^{'}(\xi)(x^*-x_k)
    

    又因∣φ′(x)∣≤L|\varphi^{'}(x)|\leq L
    

    ∣x∗−xk+1∣≤∣L(x∗−xk)∣=∣L2(x∗−xk−1)=⋯=∣Lk(x∗−x0)∣|x^*-x_{k+1}|\leq|L(x^*-x_k)|=|L^2(x^*-x_{k-1})=\cdots=|L^k(x^*-x_0)|
    

    因为lim⁡k→∞Lk=0\displaystyle \lim_{k \to \infty}L^k=0
    

    3:迭代法的误差式：
    

    设某一次迭代后误差为ϵ\epsilon，则可以推出：
    

    ∣xk+1−xk∣=∣(x∗−xk)−(x∗−xk+1)≥∣x∗−xk∣−∣x∗−xk+1∣≥∣x∗−xk∣−L∣x∗−xk∣|x_{k+1}-x_{k}| = |(x^*-x_k)-(x^*-x_{k+1})\geq|x^*-x_k|-|x^*-x_{k+1}|\geq|x^*-x_k|-L|x^*-x_k|
    

    其中从∣x∗−xk+1∣≤L∣x∗−xk∣|x^*-x_{k+1}| \leq L|x^*-x_k|
    

    故可以轻松的计算出误差估计式为：
    

    ∣x∗−xk∣≤11−L∣xk+1−xk∣|x^*-x_k|\leq\frac{1}{1-L}|x_{k+1}-x_k|
    

    通过中值定理，又可以推出：
    

    ∣xk+1−xk∣=∣φ′(ξ)(xk−xk−1)∣|x_{k+1}-x_k| = |\varphi'(\xi)(x_k-x_{k-1})|
    

    因为∣φ′(ξ)∣≤L|\varphi'(\xi)|\leq L
    

    ∣x∗−xk∣≤Lk1−L∣x1−x0∣|x^*-x_k|\leq\frac{L^k}{1-L}|x_1-x_0|
    

    其中L可以近似的看作是一个足够接近方程解的函数导数的值。
    

    3.3.3不动点迭代法的收敛速度
    

    首先我们先直接给出一个结论：在不动点迭代过程中，第i步迭代和第i+1步迭代的表达式分别为ei,ei+1e_i,e_{i+1}
    

    如何能证明我们的算法是一个线性收敛的函数呢？实际上非常简单。证明过程如下：
    

    若φ(x)连续可微,不动点的一个足够近似的值为x0，xi+1和xi是两次迭代的估计值若\varphi(x)连续可微,不动点的一个足够近似的值为x_0，x_{i+1}和x_i是两次迭代的估计值
    

    根据中值定理，∃r∈(xi,r),φ(xi)−x0xi−x0=φ′(r)根据中值定理，\exists r\in (x_i,r),\frac{\varphi(x_i)-x_0}{x_i-x_0}=\varphi'(r)
    

    φ(xi)=xi+1,故xi+1−r=φ′(r)(xi−r)\varphi(x_i) = x_{i+1},故x_{i+1}-r = \varphi'(r)(x_i-r)
    

    ei+1=∣φ′(r)∣ei，即S=∣φ′(r)∣为常数e_{i+1}=\left|\varphi'(r)\right|e_i，即S=\left|\varphi'(r)\right|为常数
    

    我们可以在这里举几个例子，例如我们希望求函数f(x)=x3+x−1=0f(x) = x^3+x-1=0
    

    //todo 图片
    

    再举一个例子，函数f(x)=cosx−sinx=0f(x) = cosx-sinx=0
    

    不难看出我们的eiei−1\frac{e_i}{e_{i-1}}
    

    迭代的终止
    

    3.4牛顿法
    

    牛顿在整个微积分、数值分析中都有着举足轻重的地位，这里阐述的牛顿法，全名牛顿-拉夫逊法，就是Taylor展开式的一部分。牛顿迭代法的核心思想就是：设法将一个非线性方程f(x)=0f(x)=0
    

    p1(x)=f(xk)+f′(xk)(x−xk)p_1(x) = f(x_k)+f^{'}(x_k)(x-x_k)
    

    3.4.1普通牛顿法
    

    从上述公式中我们知道，其中p1(x)p_1(x)
    

    xk+1=xk−f(xk)f′(xk)x_{k+1} = x_k - \frac{f(x_k)}{f^{'}(x_k)}
    

    这就是普通牛顿法的迭代公式。在几何意义上，他就是一个切线与x轴的交点去逼近零点，如图：
    

    我们不断的通过迭代这个过程，就能让我们的值越来越精确。
    

    3.4.2牛顿下山法
    

    所有的迭代法都有一个无法逃过的缺点，如果选取的初始值离根太远，则会导致迭代过程次数过多，并且有可能导致迭代发散，因为迭代法只具有局部收敛性。
    

    为了避免迭代失败或时间过长，我们加上这样一个条件用于保证数值稳定下降
    

    ∣f(xk+1)∣<∣f(xk)∣|f(x_{k+1})|<|f(x_k)|
    

    将这个条件和牛顿法结合再一起，即再保证数值稳定下降的过程中，利用牛顿法加快迭代，这就是牛顿下山法。具体的操作如下：
    

    将牛顿法的结果xˉk+1\bar{x}_{k+1}
    

    xk+1=λxˉk+1+(1−λ)xkx_{k+1} = \lambda\bar{x}_{k+1} + (1-\lambda)x_k
    

    其中λ(0≤λ<1)\lambda(0\leq\lambda<1)
    

    3.4.3简单牛顿法
    

    牛顿法可以说是一个非常有效的计算方法，准确度和迭代次数上都要比普通的迭代法要好得多，但是牛顿法最大的问题是我们需要求方程的导数，对于某些极其复杂的函数而言，导数是无法通过人工的方式计算，假如我们使用微积分的方式去求解导数，这对整个程序的性能会有比较大的影响，因此我们可以利用一个常数值λ\lambda来代替方程中的导数项。此时迭代公式为：
    

    xk+1=xk−f(xk)λx_{k+1} =x_k - \frac{f(x_k)}{\lambda}
    

    不过对于常数λ\lambda的取值是有限制的，因为我们需要保证迭代函数的收敛性，如果函数不收敛于x∗x^*，那么一切都没有意义。于是有：
    

    φ(x)=x−f(x)λ⟹φ′(x)=1−f′(x)λ\varphi(x) = x - \frac{f(x)}{\lambda}\Longrightarrow\varphi^{'}(x) = 1-\frac{f^{'}(x)}{\lambda}




    

    

    牛顿迭代法的收敛性遵循前文中普通迭代法的收敛性，于是可以得到：
    

    ∣φ′(x)∣=∣1−f′(x)λ∣⟹0<f′(x)c<2|\varphi^{'}(x)| = |1-\frac{f^{'}(x)}{\lambda}|\Longrightarrow0<\frac{f^{'}(x)}{c}<2
    

    这样我们就可以很轻松的确定下c的值了。
    

    简单牛顿法的几何意义就简单许多了，和我们之前讨论的普通迭代法一致，只不过普通迭代法是将函数值和y=xy=x
    

    ///这里只写普通牛顿法，另外的函数由读者自己思考
// 其中f1x为导数
public static double Newtown(Func<double, double> fx, Func<double, double> f1x, double x)
    var temp = f1x.Invoke(x);
    if (temp == 0)
        throw new ArgumentException();
    x = x - fx.Invoke(x) / temp;
    if (Math.Abs(fx.Invoke(x)) <= epsilon)
        return x;
    return Newtown(fx, f1x, x);

    3.4.4 改进牛顿法——弦截法
    

    弦截法是牛顿法的一种改进，保留了牛顿法中收敛速度快的优点，还克服了再牛顿法中需要计算函数导数值f′f^{'}
    

    弦截法中，我们用差商
    

    f(xk)−f(xk−1)xk−xk−1\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}
    

    去代替牛顿法中的导数值，于是可以得到以下离散化的迭代
    

    xk+1=xk−f(xk)f(xk)−f(xk−1)(xk−xk−1)x_{k+1} = x_k - \frac{f(x_k)}{f(x_k)-f(x_{k-1})}(x_k-x_{k-1})
    

    这种方法叫做双点弦截法，如图所示：
    

    从图中可以知道，弦截法一直利用两点之间的连线作为迭代的内容，那么，他的合理性在哪里呢？
    

    整个迭代法都离不开中值定理，这里也是这样，事实上，这个差商之所以可以对导数值进行替代，是因为中值定理中说过，连续函数中两函数上的点的连线的斜率必为两点之间某一点的导数值，并且迭代过程中，这两点的中值会越来越逼近函数零点，事实上这已经说明了弦截法是牛顿法的改进方法了。
    

    不过，如果将函数中xk−1x_{k-1}
    

    //这里就对双点弦截法进行编程
public static double StringCut(Func<double, double> func, double x1, double x2)
    var temp = x1 - (func.Invoke(x1) / (func.Invoke(x1) - func.Invoke(x2))) * (x1 - x2);
    x2 = x1;
    x1 = temp;
    if (Math.Abs(func.Invoke(x1)) <= epsilon)
        return x1;
    return StringCut(func, x1, x2);

    3.4.5 牛顿法的收敛性
    

    牛顿法的收敛性有可能是一阶收敛也有可能是二阶收敛，具体要看我们的迭代函数。我们首先讲讲牛顿法二次收敛的情形。
    

    假定我们牛顿法的迭代函数为g(x)=x−f(x)f′(x)g(x) = x-\frac{f(x)}{f'(x)}
    

    我们再将f(r)f(r)进行泰勒展开，取xix_i
    

    f(r)=f(xi)+(r−xi)f′(xi)+(r−xi)22f′′(ξ),ξ∈(xi,r)f(r) = f(x_i)+(r-x_i)f'(x_i)+\frac{(r-x_i)^2}{2}f''(\xi),\xi \in (x_i,r)
    

    f(r)=0=>xi−f(xi)f′(xi)−r=(r−xi)22f′′(ξ)f′(xi)f(r) = 0 =>x_i-\frac{f(x_i)}{f'(x_i)} -r = \frac{(r-x_i)^2}{2}\frac{f''(\xi)}{f'(x_i)}




    

    

    若f′(xi)≠0f'(x_i)\neq0
    

    xi+1−r=ei2f′′(ξ)2f′(xi)x_{i+1}-r=e_i^2\frac{f''(\xi)}{2f'(x_i)}
    

    ei+1=ei2∣f′′(ξ)2f′(xi)∣e_{i+1} = e_i^2\left|\frac{f''(\xi)}{2f'(x_i)}\right|
    

    这样我们就得到了牛顿法的二阶收敛的定义，对于二阶收敛，我们要求是需要在该处的一阶导数值不为0。
    

    不过我们的牛顿法并不是总为二次收敛的，在面临多重根的时候，牛顿法往往会倒退到线性收敛的速度。，例如函数f(x)=xmf(x)=x^m
    

    xi+1=xi−ximmxim−1=m−1mxix_{i+1} = x_i-\frac{x_i^m}{mx_i^{m-1}}=\frac{m-1}{m}x_i
    

    唯一的根是0，但是0是一个m-1重根，因此得到
    

    ei+1=Sei,S=m−1me_{i+1} = Se_i,S=\frac{m-1}{m}
    

    我们这里可以给出一个定义，若m+1阶连续可微函数有一个m重根，那么利用牛顿法会线性局部收敛，误差式如上。
    

    收敛迭代的加速与精度
    

    利用迭代法进行收敛的计算时，往往面临一个很麻烦的问题，就是当运行足够多次迭代的时候，我们的精度往往会不降反升，这是因为一种类似摇摆的问题出现，例如我规定此刻你站在坐标1上，我希望你走到坐标0上，你每次可以向左或者向右走三步，那么第一次你向左走三步之后，得到的迭代结果时-2，反而离精确值更远了。这是一个令人糟心的问题。这里我们对这种现象进行一次解释。
    

    收敛的精度
    

    y还是x？
    

    事实上我们的误差分为了前向误差和后向误差，什么是前向误差呢？实际上就是我们要求解的根与实际的差值，假设f(r)=0f(r)=0
    

    对于计算机而言，存储的精度是有极限的，假定我们现在有一台古老的计算机，他的存储精度最多就到小数点后4位，那么假设我们的迭代函数是f(x)=x2f(x)=x^2
    

    这其实就是我们后向误差足够小，但是前向误差并不够小导致的。我们在实际的代码编写的时候，一定要注意的一个地方就是我们的误差在什么时候应当利用前向误差进行终止，什么时候又应该利用后向误差进行求解。
    

    读者可以尝试将迭代初始值设置成我们方程实际的根进行迭代，按着我们正常人的理解，他应该立即停止迭代直接返回我们的初始值即可。但是算法往往是不尽人意的，在绝大多数工具或语言的内置求根函数中，即使我们传入的初始值是根，往往得到的结果反而是一个不精确的解。例如著名的威尔金森多项式：
    

    W(x)=(x−1)(x−2)...(x−20)W(x) = (x-1)(x-2)...(x-20)
    

    如果我们利用这个已经因式分解好了的式子进行求根运算，这似乎没有必要，我们可以得到一个非常工整的方程根，他就是1-20之间所有的自然数组成，一旦我们将其展开后投入运算，由于存在许多大数字，很多大数字会因为存储、计算等过程中产生损失和误差，这些误差实际上是很小的数字，但是却对我们的计算结果产生了很大的误差，最终我们难以得到一个精确解。这就是对于求根过程中对数字扰动的敏感性问题。
    

    我们进一步去探索一下究竟是什么导致了误差放大，并且能粗略的计算出这些误差究竟有多少，我们假设是寻找一个函数f(x)=0f(x)=0
    

    f(r+Δr)+ϵg(r+Δr)=0f(r+\Delta r)+\epsilon g(r+\Delta r) = 0
    

    将上式统统泰勒展开
    

    f(r)+(Δr)f′(r)+ϵg(r)+ϵ(Δr)g′(r)+O((Δr)2)=0,其中O((Δr)2)→0,Δr→0f(r)+(\Delta r)f'(r)+\epsilon g(r)+\epsilon(\Delta r)g'(r)+O((\Delta r)^2) = 0,其中\displaystyle O((\Delta r)^2) \to 0,\Delta r \to 0
    

    忽略后面的高阶无穷小，同时r又是根，于是可以得到一个关于r的变化值的近似




    

    

    Δr(f′(r)+ϵg′(r))≈−f(r)−ϵg(r)=−ϵg(r)\Delta r (f'(r)+\epsilon g'(r)) \approx -f(r)-\epsilon g(r) =-\epsilon g(r)
    

    又因为ϵ\epsilon也是一个很小的值（需要远小于f′(r)f'(r)），我们直接认为他就是0，得到了Δr\Delta r的最终估计:
    

    Δr≈−ϵg(r)f′(r)\Delta r \approx -\epsilon\frac{g(r)}{f'(r)}
    

    这就是我们根的敏感性公式，利用这个公式，我们可以得出，如果出现了某些数字的扰动，根会如何变化。
    

    这里举一个黄皮书上的例子，如果函数P(x)=(x−1)(x−2)...(x−6)−10−6x7P(x) = (x-1)(x-2)...(x-6)-10^{-6}x^7
    

    那么我们直接设近似函数为f(x)=(x−1)(x−2)...(x−6)f(x)=(x-1)(x-2)...(x-6)
    

    Δr≈−ϵg(r)f′(r)=2332.8×10−6\Delta r \approx -\epsilon\frac{g(r)}{f'(r)} = 2332.8\times 10^{-6}
    

    因此我们估计的最大根应当是6.0023328左右，读者可以自行使用迭代法去求解最大根，最后得出的结果与这个估计值是极度接近的。这里我们定义一个新东西误差放大因子，也就是我们的∣g(r)rf′(r)∣\left|\frac{g(r)}{rf'(r)}\right|
    

    普通迭代加速
    

    对于迭代过程，利用中值定理有
    

    x∗−xk+1=φ(x∗)−φ(xk)=φ′(ξ)(x∗−xk)x^*-x_{k+1} = \varphi(x^*)-\varphi(x_k) = \varphi^{'}(\xi)(x^*-x_k)
    

    当Δx→0\Delta x \rightarrow0
    

    λ(x∗−xk)=x∗−xk+1⟶x∗=11−λxˉk+1−λ1−λxk\lambda(x^*-x_k) = x^*-x_{k+1}\longrightarrow x^* = \frac{1}{1-\lambda}\bar{x}_{k+1}-\frac{\lambda}{1-\lambda}x_k
    

    故可以推出最终的迭代公式为
    

    {xˉk+1=φ(xk)xk+1=xˉk+1+λ1−λ(xˉk+1−xk)\begin{cases}
\bar{x}_{k+1} = \varphi(x_k)\\
x_{k+1} = \bar{x}_{k+1} + \frac{\lambda}{1-\lambda}(\bar{x}_{k+1}-x_k)
\end{cases}
    

    利用这种方式的好处就是再求得xkx_k
    

    Atiken加速法
    

    Atiken加速法其实就是再普通加速迭代公式上在进行一次迭代，这里直接写出公式：
    

    {xˉk+1=φ(xk)xˉˉk+1=φ(xˉk+1)xk+1=xˉˉk+1−(xˉˉk+1−xˉk+1)xˉˉk+1−2xˉk+1+xk\begin{cases}
\bar{x}_{k+1} = \varphi(x_k)\\
\bar{\bar{x}}_{k+1} = \varphi(\bar{x}_{k+1})\\
x_{k+1} = \bar{\bar{x}}_{k+1} - \frac{(\bar{\bar{x}}_{k+1}-\bar{x}_{k+1})}{\bar{\bar{x}}_{k+1} - 2\bar{x}_{k+1}+x_k}
\end{cases}
    

  • 试着不借助计算器计算2\sqrt{2}
    • 

  • 试着证明f(x)=ax+bf(x)=ax+b
    • 

  • 编程题：由一个高度为10m的圆柱构成的发射井顶部是一个半球，体积400m3400m^3，确定发射井底部班级
    • 

  • 设函数为f(x)=xn−axn−1,g(x)=xnf(x)=x^n-ax^{n-1},g(x)=x^n
    • 

    Reference
    

    《数值分析》（原书第二版） —— Timothy Sauer
    

    《数值计算方法》（清华大学出版社） —— 吕同富等
    
  
    分类：
     人工智能
     
    标签：
     
    机器学习
     
      
         
     
    
    小陈的学习记录
     
    推荐文章
    朝气蓬勃的电脑桌  ·  清代学霸皇子养成记：早晨四点上学 一年歇六天半--时政--人民网
    6 月前
    怕老婆的鸵鸟  ·  “旗手”雷声32强赛出局，这也是他奥运花剑个人赛最差战绩
    1 年前
    怕老婆的匕首  ·  《舌尖上的中国》引发大众乡愁情绪_手机新浪网
    1 年前
    不羁的桔子  ·  【触摸2023·菏泽百姓身边的变化】完善城市路网，让出行更便捷_媒体_澎湃新闻-The Paper
    2 年前
    八块腹肌的机器猫  ·  关于公布研究生申请学位创新成果相关文件的通知-西南交通大学-研究生院
    2 年前
    今天看啥   ·   Py中国   ·   codingpro   ·   小百科   ·   link之家   ·   卧龙AI搜索
    删除内容请联系邮箱 2879853325@qq.com
    Code - 代码工具平台
    © 2024 ~ 沪ICP备11025650号