方程(equation)在数学之中有着很高的地位,我们常见的有一次、二次和三次方程等等,并且我们还能通过部分方程的求根公式来进行求解方程的根。本文主要针对的是一般性的一元 n 次复系数方程,即是满足下图的方程:
那么由高斯定理可知,满足上式该 n 次系数方程的根就有且仅有 n 个。注意:根据伽罗瓦群理论,五次及五次以上方程没有求根公式,即不能以代数数的形式写出方程的根,但是不是说这种方程没有解,使用超越函数(如三角函数、对数函数等)还是可以表示该方程的解。但是有的时候我们求解某些方程过于繁琐,且存在约束条件的情况下并不需要完全求解方程,而且若是含有超越数(如圆周率 π、自然常数 e 等)的方程,求解过程也会略显困难。因此人们想要另辟蹊径,想要找寻其他高效的方式来求解方程,在此期间涌现出了大量的求解方法如:二分法、不动点迭代等。本文主要介绍另一种优化的不动点迭代法——牛顿迭代法(Newton-Iterative-Method)。
牛顿迭代法也称为牛顿-拉夫森(Newton-Raphson)迭代法,它不仅适用于方程或方程组的求解,还常用于微分方程和积分方程求解,可见它的重要性。其方法基本原理如下:
设 f(x) ∈ C² [m,n],对 f(x) 在 x₀ ∈ [m,n] 领域内对其进行泰勒展开,得如下结果:
舍去二次项,得到 f(x) 的线性近似式:
这也是关于 x₀ 这一点的切线方程,由此得到方程 f(x) = 0 的近似解:
即可得出关于 x 的迭代格式:
在此给出关于牛顿法的几何意义:牛顿迭代法也称为牛顿切线法,这是由于 f(x) 的线性化近似函数是曲线 y = f(x) 过点(x₀,f(x₀))的切线而得名的,将该零点代之 f(x) 的近似方程以求的零点,即切线 T 与 X 轴交点的横坐标,真实的根值为 X* ,牛顿迭代法实质上是一种线性化方法,其基本思想是将非线性方程逐步归结为某种线性方程来求解。
那么牛顿迭代法是收敛的吗?或者说是否对于任意的初始值 x₀ 都能够保证该迭代的结果收敛到 X* ?下面将通过代数解析的方式来说明其收敛性:
将牛顿迭代式写成如下形式,即可获得的不动点迭代形式:
这样就可以应用不动点迭代的收敛原则,只须证明在根 β 附近的迭代函数是一个压缩映象,即可证明其收敛性。由于
这里的根 β 是单根,即 f( β ) = 0 且 f ' (β) ≠ 0,于是:
由于 γ (x) 的连续性可知,存在一个领域( β - δ,β + δ ),对该领域内的任意 x ,都有 | γ' (x) < q |,其中 0<q<1,因此 γ (x) 为区间( β - δ,β + δ ) 上的一个压缩映像,于是我们可以得到如下结论:
由此可见,牛顿迭代法的局部收敛性较强,所以只有初值充分地接近,才能确保所迭代序列的收敛性。为了放宽对局部收敛性的限制,必须再增加能够使该序列收敛的充分条件,
上式可以化为以下几种情况:
其中 ① 保证了零点的存在性;② 保证了函数的单调性,同时也保证了在 区间[ a,b ] 内有唯一的零点;③ 保证函数的凹凸不会改变,④ 与 ③ 保证了每一次的迭代生成的值都在区间 [a,b] 之中;反映到图像上如下:
若选取初始值不满足上述条件时,会出现越迭代越远甚至死循环的情况,比如下图这些情况:
介绍完牛顿法的性质和原理,那么我们能够用它来做些什么呢?即前面说到可以用来进行方程的求解。假设给定正数 a ,建立如下关系式:
则 f(x) = 0 的正数解就是其算术平方根。那么用牛顿迭代公式可得:
由于当 x > 0 时,f ' (x) = 2x > 0,f '' (x) = 2 > 0,故由收敛定理可知,对于任意满足条件 x₀ > √a 的初始近似值,由选代公式所产生的序列必定收敛于 √a 。
下面我们使用程序(TypeScript)来进行开平方运算:
对于其他 n 次方的开方运算与上述类似,牛顿法在数学分析中使用非常广泛,在此不再一一介绍,喜欢其他关于数学与程序方面的小伙伴可以留言加关注,之后我将会进行讲解。我是童话君,小伙伴们拜拜~~~