数值计算相关方法（求根）

作者：村山羊

本文针对数值计算求根方法做出matlab的编程实现，并给出效果图和相对误差分析图（又可以水一篇博客了233）。 --------------------------

目录

序言

读者须知

1、交叉法求根

Ⅰ、逐步搜索法

Ⅱ、二分法

Ⅲ、比例求根法

2、迭代法求根

Ⅰ、牛顿法

Ⅱ、弦截法

参考文献

附录

---

序言

要求一个方程的根，这个经典的数学问题在初中就已经出现了，随着学历的增长，我们接触到了许多奇奇怪怪的方程，像n元m次方程等。我们求解这些方程的方式一般是利用数学的方式计算，但在工程数学中，很多时候我们不需要知道他们的确解，而是只要计算出他们的近似解就行，这种计算近似解的方法是数值计算要求掌握的。

读者须知

(1)本文中所提到的观点纯属自己理解，有适当参考文献，并在文中标出引用，在文本参考文献提到；
(2)本文中提到的相对误差指的是|迭代当前值-收敛值/收敛值|；
(3)本文所著权归@村山羊，转载请联系QQ：1036814872，如有不足，欢迎提出；
(4)文中所用matlab为正版，所用程序可在matlab及相似环境中运行，全程序可供下载，具体移步文末附录；
(5)如有其他问题（如法务等），请及时联系本文作者，联系方式如上。
一个有解的方程有他的实根，但很多情况下我们解不出来（想起了高中的隐函数问题了吗hh）。这里以cosx-x=0和x¹²-1=0这两个方程为例。

1、交叉法求根

交叉法其实在英文中为Bracketing Method，顾名思义，就是用括号去“括”根所在的区间，这里介绍两种方法。

Ⅰ、逐步搜索法

设有连续可导函数f(x)，存在区间x∈[a,b]，使得f(x)=0，x称为f(x)=0在[a,b]上的根。那么我们将a到b之间分为n等分，每一份求出其x对应的f(x)的值，根据零点存在定理[1]可以确定f(x)符号相反的相邻两点间存在方程的解，所以我们继续将这两个点作为新的区间，再重复上述步骤，直到得到最后的结果。 例：编程求cosx-x=0在x∈[0,1]间的解。 这里在区间中插入4个值，用matlab编程，代码如下：

%设定端点值 a,b
%设定迭代次数 i
%设定步长（间隔距离）h
%设定函数值 fc
%设定空数组 k ,用于储存搜索区间内各值（迭代后清空）
a = 0;
b = 1;

i = 0; 
h = (b-a)/5;

c = a; %结果及计算过程用c表示

fc = cos(c)-c;

k = [];

while i < 20, %设定迭代20次，也可用det误差设定条件
    i = i + 1; %迭代次数+1
    %求出搜索区间中各值
    for j = 0:5,
        c = a + h*j;
        fc = cos(c)-c;
        k = [k,fc];
    end
    
    for j1 = 1:5,
        if k(j1)*k(j1+1) < 0,
            b = a + h*j1;
            a = a + h*(j1-1);
        end
    end
    h = (b-a)/5;
    k = [];
    det(i) = abs(0.739085133215171 - c)/0.739085133215171; %相对误差
end

需要注意的是，matlab中相对误差是估算出来的，便于计算迭代效率。

最终结果为

c =

   0.739085133215171

迭代次数-相对损失折线图如下：

结果非常amazing啊，这个程序不到6次就近乎收敛，现在我们求另一个方程x¹²-1=0的正根。
例：编程求x¹²-1=0的正根。
相同地，我们对上面地程序进行改动，即将

fc = cos(c)-c;
det(i) = abs(0.739085133215171 - c)/0.739085133215171;

改成

fc = c^12-1;
det(i) = abs(1 - c)/1;

运行，刚好得到收敛的值

c =

   1.000000000000053

这里的误差是计算机产生的，无法避免

同样，迭代次数-相对损失折线图如下：

也是不到几次就近乎收敛。

Ⅱ、二分法

现在来介绍二分法的相关内容。 二分法这种方法其实在初等数学的学习中就已经掌握了，大学无非是对其做一个编程实现，重提下原理：设一连续可导函数f(x)，其f(x)=0的根存在[a,b]中，那么我们先将a到b的这块区间对半分((a+b)/2)，将其设为c，根据之前提到的零点定理求出根所在的区间，改变区域的值（是不是和之前的做法很像？），从而进一步缩小范围，直到足够逼近解。 例：编程求cosx-x=0在x∈[0,1]间的解。

%设定端点值 a,b
%设定迭代次数 i
%设定步长（间隔距离）h
%设定函数值 fc
%设定空数组 k ,用于储存搜索区间内各值（迭代后清空）
a = 0;
b = 1;

i = 0; 

c = (a+b)/2; 
fa = cos(a)-a;
fb = cos(b)-b;
fc = cos(c)-c;

while i < 20, %设定迭代20次，也可用det误差设定条件
    i = i + 1; %迭代次数+1
    if fa*fc < 0,
        b = c;
    end
    if fb*fc < 0,
        a = c;
    end
    c = (a+b)/2;
    fa = cos(a)-a;
    fb = cos(b)-b;
    fc = cos(c)-c;
    det(i) = abs(0.739085133216 - c)/0.739085133216; %相对误差
end

输出为：

c =

   0.739084720611572

误差图为：

另一实例同理，这些程序将在文末的附录中给出。
例：编程求x¹²-1=0的正根。
程序见附录①，结果为

c =

     1

误差图如下：

一次即收敛！这是因为我用区间[0,2]来使用二分法，必然一次收敛。

Ⅲ、比例求根法

经过前面两个方法，其实大家对交叉法的三个子方法应该有所了解了，这个比例求根法（据我所见）其实是对逐步搜索法和二分法的一个优化，将搜索的效率提高了。原理与二分法相同，只是不是真正地“二分”，而是按比例分割，这里仍以cosx-x=0及x¹²-1=0为例，代码见附录②及附录③，误差图如下：

cosx-x=0

x¹²-1=0

值得注意的是，这里的比例求根似乎不能发挥他的功能，迭代了越4000次才收敛，由于没有论证比例求根法的原理，故不做说明。

由此，交叉法求根完结。

2、迭代法求根

除了使用缩小区间的方式外，是否有其他方法求根？答案是肯定的，这就是迭代法。迭代法的思想在牛顿的那个时代早已提出，思想大概是这样的：先在要求根的附近取一点，然后根据这一点或相近两点的“陡峭程度”确定根的方向，并相对应地移向那里（是不是感觉和梯度下降很像？）。这里介绍两种方法。

Ⅰ、牛顿法

牛顿法的原理与泰勒展开式有关[2]，这里不再赘述，我们主要阐述其公式含义：

这个式子由选定点处的切线引出，与x轴相交后选定该点作为新点，之后的x由前一个x更新，直到f’(x)（选定点的切线斜率）趋于0后，右式后一项趋于无穷大，左式趋于0，精度达到要求后，迭代完毕。可能有点难理解，这里有找y=x²零点（x=0）的部分迭代图：

步骤一：选定点(5,25)，做切线与x轴交于x=2.5处。 

步骤二：选定点(2.5,6.25)，做切线与x轴交于下一个点处，以此循环，直到斜率趋向0。

这里的例子与之后的方法合起来进行对比，同样的，你可以在附录③与附录④中找到代码。

Ⅱ、弦截法

弦截法其实和牛顿法十分相像，只是弦截法是利用两个点做出一条直线与x轴相交，而牛顿法只使用一个点的切线作为直线，故选取点时要使用两个点（这一点老师在上课时与百度百科[3]中说的不太一样，百科中认为两个点围成的区间必须包括根，而课上所展示的PPT没有此意，故程序中均选取了十分相近的两点），弦截法迭代公式如下：

应该注意到，我们必须迭代三个值而不是牛顿法中的两个

下相对误差图用于比较牛顿法与弦截法：

参考文献

[1]同济大学数学系.高等数学[M].北京:高等教育出版社,2014:68-69.

[2]Pikachu5808.牛顿法和拟牛顿法[DB/OL].https://zhuanlan.zhihu.com/p/46536960,2020

[3]弦截法_百度百科[DB/OL].https://baike.baidu.com/item/%E5%BC%A6%E6%88%AA%E6%B3%95/1195626?fr=aladdin

附录

附录①：二分法实例-x¹²-1=0

附录②：比例求根法实例-cosx-x=0

附录③：比例求根法实例-x¹²-1=0

附录④：牛顿法求根

附录⑤：弦截法求根