デュラン＝カーナー法

デュラン＝カーナー法（デュラン＝カーナーほう、Durand-Kerner method、 DK法、ブルガリアではWeierstrass-Dochev法と呼ばれる）はカール・ワイエルシュトラスが1891年に発見しWeierstraß, K. (1891). "Neuer Beweis des Satzes, dass jede ganze rationale Function einer Veränderlichen dargestellt werden kann als ein Product aus linearen Functionen derselben Veränderlichen". Sitzungsberichte der königlich preussischen Akademie der Wissenschaften zu Berlin.、Durand(1960)Durand, E. (1960). "Equations du type F(x) = 0: Racines d'un polynome". In Masson et al. Solutions Numériques des Equations Algébriques, vol. 1.、Dochev(1962)、Presic(1966)、Kerner(1966)がそれぞれ独立に再発見した多項式に対する求根アルゴリズム、反復法であり、ニュートン法の進化形といえるPetković, M. (1989). Iterative methods for simultaneous inclusion of polynomial zeros. Berlin [u.a.]: Springer. pp. 31–32. ISBN 978-3-540-51485-5.。Dk法の命名はAberth(1973)による。DK法に対してAberth(1973)の提案した初期値を用いる手法はDKA法（Durand-Kerner-Aberth method）と称される。DKA法は山本哲朗による命名である。

DKA法の誤差評価
DKA法の誤差評価はSmith(1970)で与えられたDKA法とSmithの定理を組み合わせることで代数方程式の精度保証付き数値計算を行うことができる。。Smithの定理では与えられた多項式のすべての根がある閉円板の合併に含まれ、その連結成分の1つがm個の閉円板からなればその中にちょうどm個の根があると示された。この定理の証明は『数値解析入門』の付録に詳述されている。

DK法の続行が不可能となるような初期値の存在
Kjurkchiev-Andreev(1985)はある段階でDK法の続行が不可能となるような初期値が必ず存在することを証明したKyurkchiev N. V., A. Andreev (1985) Compt. rend. Acad. bulg. Sci., 38, No 11, 1461–1463 (ロシア語)。しかし多くの数値実験によってDK法はほとんどすべての初期値に対して反復列は解に収束すると予想されている。この予想は2次多項式の時は正しい(Small, 1976)。3次多項式の場合は特別な場合で示されている（山岸義和、1991年）。しかし一般の場合は未解決である。

 Bernhard Reinke, Dierk Schleicher and Michael Stoll: "The Weierstrass-Durand-Kerner root finder is not generally convergent", Math. Comp. vol.92 (2023), pp.839-866. DOI: https://doi.org/10.1090/mcom/3783

脚注

関連文献
和文
 伊理正夫、山下浩、寺野隆雄、小野令美：「大域的収束性をもつ代数方程式の解法」、京都大学数理解析研究所講究録、No.339, pp.43-69 (1978).
 小野令美. (1979). Durand-Kerner 法と Aberth 法を用いた超高次方程式の数値計算. 情報処理学会論文誌, 20(5), 399-404.
 小野令美. (1981). Durand-Kerner-Aberth 法を用いたある種の超高次方程式の解の数値計算. 情報処理学会論文誌, 22(2), 165-168.
 中田多美, 川本則行, & 名取亮. (1988). 代数方程式に対する Durand-Kerner 法の初期値の改良. 情報処理学会論文誌, 29(12), 1200-1201.
 山本哲朗, 古金卯太郎, & 野倉久美. (1977). 代数方程式を解く Durand-Kerner 法と Aberth 法. 情報処理, 18(6).
 山本哲朗, & 菅野幸夫. (1994). Durand-Kerner 法に関する注意. 日本応用数理学会論文誌, 4(3), 251-258.
 菅野幸夫, 劉文, & 山本哲朗. (1995). Durand-Kerner 法とその加速 (数値計算アルゴリズムの現状と展望 II). 京都大学数理解析研究所講究録.
 Durand-Kerner法の効率的な初期値の簡単な設定法 (日本応用数理学会論文誌 Vol.3,No.4,1993,pp.451-464) 小澤一文
 Durand-Kerner型補助関数を用いた非線形方程式の多段反復解法 (日本応用数理学会論文誌 Vol.4,No.2,1994,pp.67-80) 櫻井鉄也, 杉浦洋, 鳥居達生


英文
 Guggenheimer, H. (1986). Initial approximations in Durand-Kerner's root finding method. :en:BIT Numerical Mathematics, 26(4), 537-539. 
 Fraigniaud, P. (1991). The Durand-Kerner polynomials roots-finding method in case of multiple roots. :en:BIT Numerical Mathematics, 31(1), 112-123.
 Kjellberg, G. (1984). Two observations on Durand-Kerner's root-finding method. :en:BIT Numerical Mathematics, 24(4), 556-559.
 Deren, W., & Fengguang, Z. (1991). On the determination of the safe initial approximation for the Durand-Kerner algorithm. :en:Journal of Computational and Applied Mathematics, 38(1-3), 447-456.
 Batra, P. (1998). Improvement of a convergence condition for the Durand-Kerner iteration. :en:Journal of computational and applied mathematics, 96(2), 117-125.

外部リンク
DKA法 - PukiWiki for PBCG Lab
連立法, 特に Durand-Kerner 法

Category:応用数学
Category:求根アルゴリズム
Category:数値解析
Category:数学に関する記事
Category:数学のエポニム