数值方法解方程之终极算法
By 苏剑林 | 2010-04-04 | 43007位读者 |呵呵,做了一回标题党,可能说得夸张了一点。说是“终极算法”,主要是因为它可以任意提高精度、而且几乎可以应付任何非线性方程(至少理论上是这样),提高精度是已知的迭代式上添加一些项,而不是完全改变迭代式的形式,当然在提高精度的同时,计算量也会随之增大。其理论基础依旧是泰勒级数。
我们考虑方程$x=f(y)$,已知y求x是很容易的,但是已知x求y并不容易。我们考虑把y在$(x_0,y_0)$处展开成x的的泰勒级数。关键是求出y的n阶导数$\frac{d^n y}{dx^n}$。我们记$f^{(n)}(y)=\frac{d^n x}{dy^n}$,并且有
$$\frac{dy}{dx}=\frac{1}{(\frac{dx}{dy})}=f'(y)^{-1}$$
并且根据公式:$y^{(n)}=y'\frac{dy^{(n-1)}}{dy}$,可以继续求出二阶导数、三阶导数:
$$\begin{aligned}\frac{d^2 y}{dx^2}=\frac{d(f'(y)^{-1})}{dy}\cdot \frac{dy}{dx}=\frac{-f''(y)}{f'(y)^3} \\ \frac{d^3 y}{dx^3}=\frac{d(\frac{-f''(y)}{f'(y)^3})}{dy}\cdot \frac{dy}{dx}=\frac{3f''(y)^2}{f'(y)^5}-\frac{f'''(y)}{f'(y)^4}\end{aligned}$$
......
那么我们可以写出
$$y=y_0+\frac{x-x_0}{f'(y_0)}-\frac{f''(y_0)}{f'(y_0)^3}\frac{(x-x_0)^2}{2!}+(\frac{3f''(y_0)^2}{f'(y_0)^5}-\frac{f'''(y_0)}{f'(y_0)^4})\frac{(x-x_0)^3}{3!}+...$$
并注意到$x_0=f(y_0)$,那么我们实则就写出了方程根的递推公式
$$\begin{aligned}y_{n+1}=y_n+\frac{x-f(y_n)}{f'(y_n)}-\frac{f''(y_n)}{f'(y_n)^3}\frac{(x-f(y_n))^2}{2!}+ \\ (\frac{3f''(y_n)^2}{f'(y_n)^5}-\frac{f'''(y_n)}{f'(y_n)^4})\frac{(x-f(y_n))^3}{3!}+...\end{aligned}$$
在应用中不用求太多项,只需要用到前几项即可(多了计算量会暴增)。如果只取前面两项,就成为了我们应用广泛的“牛顿法”。而我们多取几项,则可以加快收敛,并且提高稳定性。
好了,对此,科学空间已经介绍了两种“新”的方程数值算法(前面一种是“切抛物线法”),以后基本上不会再去研究代数方程的数值解法了。BoJone觉得,要求解方程,本帖的“终极算法”已经足够了,这里引用一下阿基米德的语气:“给我一道方程,我可以撬出方程的根!”......
转载到请包括本文地址:https://kexue.fm/archives/590
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Apr. 04, 2010). 《数值方法解方程之终极算法 》[Blog post]. Retrieved from https://kexue.fm/archives/590
@online{kexuefm-590,
title={数值方法解方程之终极算法},
author={苏剑林},
year={2010},
month={Apr},
url={\url{https://kexue.fm/archives/590}},
}
June 16th, 2010
汗颜- -taylor展开式还可以这样用- -
微积分的作用之大本来就令人汗颜...科学哪个领域不见微积分的踪影的?
我还是喜欢数论
December 28th, 2010
在实际应用的时候多是用牛顿法(也就是你这里阶段到第二项)来求解的,因为需要考虑两个实际的问题:1、计算高阶导数代价很大,费时费力。2、高阶导数对误差将更敏感,导致在计算中误差会被放大。
当然,如果本身导数的解析表达式可以求得,那就无所谓了~
对的,因题而异。不过这方法对于n次代数方程很有效,呵呵。
December 16th, 2019
但是无法解出$n$个根啊