计算多项式零点的Graeffe平方根方法

发布的克里夫硅藻土，2016年7月11日

150次观看(过去30天)|0喜欢|1评论

在一个minisymposium纪念查理·范洛恩SIAM年会，我将描述几种计算多项式零点的可疑方法。其中一种方法是格拉夫平方根法，我将用我最喜欢的立方x^3-2x-5美元来演示。

内容

该方法

今天我们常说的格拉夫平方根法是由丹德林、洛巴切夫斯基和格拉夫在1826年、1834年和1837年分别独立发现的。下面引用的Alston Householder 1959年的一篇文章理顺了这段历史。

这个想法是操纵一个多项式的系数来产生第二个多项式，它的根是第一个多项式根的平方和。如果原根有一个支配性的实根，它将变得更加支配性。当这个过程被迭代时，你最终会到达一个点，在这个点上，主根可以被读取为前两个系数的比值。剩下的就是取n个根来撤销迭代。

Graffe.m

这是一个优雅的代码，用于生成一个立方，其根是给定立方的根的平方和。

类型graeffe

函数b = graeffe(a) % a = a(1)*x^3 +…+ a(4)是立方。% b = graffe(a)是一个三次数，其根是a的根的平方和。b = [a(1)²-a(2)²+ 2*a(1)*a(3) a(3)²- 2*a(2)*a(4) -a(4)²];

历史悠久的立方体

我在一系列帖子中讨论了我最喜欢的立方，$z^3-2z-5$历史悠久的立方体去年12月21日。

在平面的一个正方形区域上，这个立方的大小等高线图显示了大约$x=2.09$的主导实根和大约$|z|=1.55$的较小大小的一对复共轭根。

图形

基本的迭代

变换的重复应用本质上是系数的平方。所以问题是溢出。当我第一次在Burroughs B205上运行时，我有一个有限的浮点指数范围，溢出是一个严重的限制。今天有了IEEE的替身，我们的情况有所好转。

一个例子

这是我的立方。我只是展示了多项式系数的几位有效数字因为重要的是它们的指数。

A = [1 0 -2 -5];K = 0;f ='%5.0f %4.0f %5.0f %8.3e %8.3e %8.3e %20.15f \n'；流(f, k, 1,正);而All (isfinite(a)) k = k+1;A = graeffe(A);N = 2^k;R = (-a(2))^(1/n);流(f, k, n, r)结束

11 1 0.000e+00 -2.000e+00 -4.000e+00 -4.000e+00 -2.500e+01 2.000000000000000 e+02 -6.250e+02 1.681792830507429 38 1 -4.320e+02 2.386e+04 -3.906e+05 2.316e+ 04 - 1.1526e +11 2.096144583759898 5 32 1 -1.883e+10 1.125e+16 -2.328e+22 2.094553555747412 6 64 1 -3.547e+20 -7.504e+32 -5.421e+44 2.094551481347086 7 128 1 -1.582e+82 -4.203e+ 89 2.094551481542327 8 256 1 -1.582e+82 -4.203e+130 -8.636e+1782.094551481542327 9 512 1 -2.504e+164 -9.665e+260 -Inf 2.094551481542327

因此，在七步之后，我们已经计算了两倍精度的主导根，但需要第八步来确认这一点。九步之后，我们超出了指数范围。