主题
Search

格拉夫法


一种求根方法,曾在 19 和 20 世纪寻找单变量多项式根时是最流行的方法之一。 它由格拉夫、丹德林和罗巴切夫斯基独立发明(Householder 1959, Malajovich and Zubelli 2001)。 格拉夫法有许多缺点,其中包括其常用公式会导致指数超出浮点运算允许的最大值,并且它还可以将良态多项式映射为病态多项式。 然而,Malajovich 和 Zubelli (2001) 在一个高效的实现中避免了这些限制。

该方法通过将多项式 f(x) 乘以 f(-x) 并注意到

f(x)=(x-a_1)(x-a_2)...(x-a_n)
(1)
f(-x)=(-1)^n(x+a_1)(x+a_2)...(x+a_n)
(2)

因此结果是

 f(x)f(-x)=(-1)^n(x^2-a_1^2)(x^2-a_2^2)...(x^2-a_n^2).
(3)

重复 nu 次,然后将其写成以下形式

 y^n+b_1y^(n-1)+...+b_n=0
(4)

其中 y=x^(2nu)。 由于系数由韦达公式给出

b_1=-(y_1+y_2+...+y_n)
(5)
b_2=(y_1y_2+y_1y_3+...+y_(n-1)y_n)
(6)
b_n=(-1)^ny_1y_2...y_n,
(7)

并且由于平方过程已经分离了根,因此第一项大于其余项。 因此,

b_1 approx -y_1
(8)
b_2 approx y_1y_2
(9)
b_n approx (-1)^ny_1y_2...y_n,
(10)

得到

y_1 approx -b_1
(11)
y_2 approx -(b_2)/(b_1)
(12)
y_n approx -(b_n)/(b_(n-1)).
(13)

求解原始根得到

a_1 approx RadicalBox[{-, {b, _, 1}}, {2, nu}]
(14)
a_2 approx RadicalBox[{-, {{(, {b, _, 2}, )}, /, {(, {b, _, 1}, )}}}, {2, nu}]
(15)
a_n approx RadicalBox[{-, {{(, {b, _, n}, )}, /, {(, {b, _, {(, {n, -, 1}, )}}, )}}}, {2, nu}].
(16)

如果所有根都是实数,则此方法效果特别好。


使用 Wolfram|Alpha 探索

参考文献

Bini, D. and Pan, V. Y. "格拉夫、切比雪夫类和 Cardinal 过程用于将多项式分解为因子。" J. Complexity 12, 492-511, 1996.Brodetsky, S. and Smeal, G. "关于格拉夫法求解代数方程的复根。" Proc. Cambridge Philos. Soc. 22, 83-87, 1924.Cajori, F. "丹德林-格拉夫法。" 数学史,第 5 版。 New York: Chelsea, p. 364, 1962.Dedieu, J.-P. "À Propos de la méthode de Dandelin-Graeffe." C. R. Acad. Sci. Paris Sér. I Math 309, 1019-1022, 1989.Grau, A. A. "关于在使用格拉夫过程时减少数值范围。" J. Assoc. Comput. Mach. 10, 538-544, 1963.Householder, A. S. "丹德林、罗巴切夫斯基还是格拉夫?" Amer. Math. Monthly 66, 464-466, 1959.Jana, P. and Sinha, B. "格拉夫平方根的快速并行算法。" Comput. Math. Appl. 35, 71-80, 1998.Kármán, T. Von and Biot, M. a. "平方根(格拉夫法)。" §5.8.C in 工程数学方法:工程问题数学处理导论。 New York: Mcgraw-Hill, pp. 194-196, 1940.Malajovich, G. and Zubelli, J. P. "切线格拉夫迭代。" 27 Aug 1999. http://arxiv.org/abs/math.AG/9908150.Malajovich, G. and Zubelli, J. P. "关于格拉夫迭代的几何。" J. Complexity 17, 541-573, 2001.Ostrowski, A. "Recherches sur la méthode de Graeffe et les zéros des polynomes et des séries de Laurent." Acta Math. 72, 99-155, 1940.Ostrowski, A. "Recherches sur la méthode de Graeffe et les zéros des polynomes et des séries de Laurent. Chapitres III et IV." Acta Math. 72, 157-257, 1940.Pan, V. Y. "解多项式方程:一些历史和最新进展。" SIAM Rev. 39, 187-220, 1997.Runge, C. "丹德林-格拉夫法。" In Praxis der Gleichungen. Berlin and Leipzig, Germany: de Gruyter, pp. 136-158, 1921.Whittaker, E. T. and Robinson, G. "丹德林、罗巴切夫斯基和格拉夫的平方根方法。" §54 in 观测微积分:数值数学论著,第 4 版。 New York: Dover, pp. 106-112, 1967.

在 Wolfram|Alpha 中引用

格拉夫法

请引用为

Weisstein, Eric W. "格拉夫法。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/GraeffesMethod.html

主题分类