主題
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)

如果所有根都是實數，則此方法效果特別好。

使用 探索

參考文獻

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.

在 中引用

格拉夫法

請引用為

Weisstein, Eric W. "格拉夫法。" 來自 —— 資源。 https://mathworld.tw/GraeffesMethod.html

主題分類