【机器学习】数值分析(1)—— 任意方程求根

任意方程求根 简介

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

方程 分类和介绍

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

单个方程

线性方程:本质是等式两边乘以任何相同的非零数,方程的本质都不受影响。通常认为只含有一次项的方程。

非线性方程:是因变量与自变量之间的关系不是线性的关系的方程。

多项式方程

超越方程:指含有未知量的超越式(指数、对数、三角函数、反三角函数等)的方程。换言之,超越方程中都有无法用含有未知数的多项式、分式或开方表示的式子。

多个方程

线性方程组

非线性方程组

方程的零点(根、解)

若有一个值或一些值能够使得方程 \(f(x)=0\) 成立,那么这个值就被成为方程的解,也常常被叫做零点和根。

若方程有且只有一个解\(x^*\),那么我们称方程有单根\(x^*\)

若对于方程\(f(x)=0\),有\(f(x^*) = 0,f^{'}(x^*)=f^{''}(x^*)=\cdots=f^{(k)}(x^*)=0,f^{(k+1)}(x^*)\neq0\),那么称\(x^*\)为方程的k+1重根

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

求根方法

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

首先我们说一个定理1:对于实函数方程\(f(x)=0\),当\(x\in(a,b)\),且\(f(x)\)\(x\in(a,b)\)时单调且连续,若\(f(a)\cdot f(b)<0\),则方程在\(x\in(a,b)\)有且只有一个根。

二分法

二分法和算法中的二分搜索法非常的类似,取定有根区间\([a,b]\)进行对分,求得\(mid = \frac{a+b}{2}\)进行判断含根区间,如果\(f(a)\cdot f(mid)<0\),则令\(b=mid\);反之若\(f(b)\cdot f(mid)<0\),则令\(a=mid\)。当\(|b_n-a_n|<\epsilon\)停止计算返回结果。

产生的截断误差为\(|e_{n-1}| = x_{n+1} - x^*\leq[b_n - a_n] = \frac{b_0 - a_0}{2^n}\)

可以计算出最小迭代次数为\(n = \frac{lg(c_0-a_0)-lg\epsilon}{lg2}\)
代码实现:

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); } 一般迭代法

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

操作方法如下:首先将方程\(f(x)=0\)改写成\(x = \varphi(x)\)的形式,这样就可以将方程的解看成是函数\(y=x\)\(y=\varphi(x)\)的交点。给定初始值\(x_0\)后,则\(x_1 = \varphi(x_0)\),不断重复这个过程,若\(\displaystyle \lim_{k \to \infty}x_k\)存在,则迭代便可以达到使得\(x_k\)趋于交点。

通常,我们需要保证迭代函数在指定的含根区间内的导数值\(|\varphi^{'}(x)|<1\),否则迭代函数将会不收敛。

迭代过程如下图所示:

avatar

迭代法的收敛性证明

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

前提条件:设函数\(\varphi(x), x\in[a,b]\)有连续的一阶导数,并且满足以下条件:

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

\(\exist L \in (0,1),\forall x\in[a,b],|\varphi^{'}(x)|\leq L\)

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

\(x\in[a,b],\exist x^*,\varphi(x^*) = 0\)

\(\forall x_0\in[a,b]\),迭代过程\(x_{k+1} = \varphi(x_k)\)均收敛与\(x^*\)

求解误差分析式

现在开始证明

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

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wspdjp.html