任意次根的计算机算法

smallbaby

假设N等于3次及3次根以上，任意数的N次根怎么用计算机程序计算出来？ 高人是否可以讲下数学上的算法，谢谢！

比如求5的3次根，或6次根

mathe

使用牛顿迭代法可以求出任意次多项式方程的一个解。
牛顿迭代法的原理是对于任意一个函数f(x),迭代过程
$x_{n+1}=x_n - {f(x_n)}/{f'(x_n)}$
通常可以收敛到f(x)的一个解，其中第一项$x_0$可以任意选取。
其中$f'(x)$是函数$f(x)$的导数。
对于没有重根的多项式，通常这种方法非常有效。
当然对于某些特殊的$x_0$有可能迭代不收敛
比如对于方程$f(x)=x^2+1$,选择任意实数$x_0$迭代都不会收敛。
为了应付这种情况，我们可以对随机选择的迭代起始点，如果迭代多次后发现不收敛，那么在复平面上可以重新选择一个点开始迭代。
在求出一个解$x=x_1$以后，对于多项式，我们可以通过辗转相除法计算出$f(x)/(x-x_1)$,这是一个次数低一次的多项式，然后我们可以再次使用牛顿迭代法求余下的解。
而为了处理含有重根的多项式，我们可以先通过辗转相除法计算
$f(x)$和$f'(x)$的公因式，如果存在公因式$d(x)$，那么重根都必然包含在公因式$d(x)$里面。
然后我们只要计算${f(x)}/{d(x)}$的根就可以得到所有的根了。继续分析$d(x)$可以知道每个重根的重数。

无心人

楼上的降次不是一个好方法啦
可能造成精度丢失

gxqcn

mathe 将理论讲得很透彻了。具体到楼主的提问，可如下处理：

假设要求 A 的 r 次算术根 x，即 $x = A^{1/r}$（$r>=2, rinNN$）
令 $f(x) = x^r - A$，则 $f'(x) = r*x^(r-1)$，
$x_{n+1} = x_n - f(x)/f'(x) = {(r-1)x_n + A/x_n^{r-1}}/r$
$x_0$ 可通过不等式预估出来。

以上方法是高精度计算高次根的通用方法，
但 r=2 时，该法收敛较慢，且迭代易震荡，应改用其它算法，这是我的一点经验之谈。

无心人

不慢的吧
是二次收敛

曾经在我们学校图书馆
找过一本方程求根的旧书
上面有个四次收敛的

可惜啊
还掉了啊
除了我看，估计到图书馆关门那天也没人看

无心人

$x_0 = 10^{[log(A)/2]}$

mathe

原帖由 无心人 于 2008-4-5 14:53 发表
楼上的降次不是一个好方法啦
可能造成精度丢失

这个不是大问题。可以找到一个比较好的近似解后作为初始只然后继续使用原方程迭代就可以了。
需要注意的是如果方程有重根，在重根附件不是二次收敛，收敛速度会比较慢。所以先计算$d(x)=(f(x),f'(x))$,然后求${f(x)}/{d(x)}$是非常必要的

无心人

老弟还没仔细读楼主的要求啊
他要求计算的是A的n次方根
是最简单的方程

gxqcn

高次收敛，需要高次求导即可。

无心人

如果每次都进行适当的修正
是否可有二次收敛但超越二次的收敛速度?