デュラン＝カーナー法（デュラン＝カーナーほう、Durand-Kerner method、 DK法、ブルガリアではWeierstrass-Dochev法と呼ばれる）はカール・ワイエルシュトラスが1891年に発見し[1]、Durand(1960)[2]、Dochev(1962)、Presic(1966)、Kerner(1966)[3]がそれぞれ独立に再発見した多項式に対する求根アルゴリズム、反復法であり、ニュートン法の進化形といえる[4][5]。Dk法の命名はAberth(1973)による。DK法に対してAberth(1973)[6]の提案した初期値を用いる手法はDKA法（Durand-Kerner-Aberth method）と称される。DKA法は山本哲郎による命名である[7]。
DKA法の誤差評価
DKA法の誤差評価はSmith(1970)で与えられた[8][9]。Smithの定理では与えられた多項式のすべての根がある閉円板の合併に含まれ、その連結成分の1つがm個の閉円板からなればその中にちょうどm個の根があると示された。この定理の証明は『数値解析入門』(山本、2003年)の付録に詳述されている。
DK法の続行が不可能となるような初期値の存在
Kjurkchiev-Andreev(1985)はある段階でDK法の続行が不可能となるような初期値が必ず存在することを証明した[10]。しかし多くの数値実験によってDK法はほとんどすべての初期値に対して反復列は解に収束すると予想されている。この予想は2次元多項式の時は正しい(Small, 1976)。3次元多項式の場合は特別な場合で示されている（山岸義和、1991年）。しかし一般の場合は未解決である。
脚注
- ^ 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, 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.
- ^ Kerner, I. O. (1966). "Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen". Numerische Mathematik. 8: 290–294. doi:10.1007/BF02162564
- ^ Petković, M. (1989). Iterative methods for simultaneous inclusion of polynomial zeros. Berlin [u.a.]: Springer. pp. 31–32. (ISBN 978-3-540-51485-5).
- ^ 山本哲朗『数値解析入門』（増訂版）サイエンス社〈サイエンスライブラリ 現代数学への入門 14〉、2003年6月。ISBN (4-7819-1038-6)。
- ^ Aberth, O.(1973), Iteration Methods for Finding all Zeros of a Polynomials Simultaneously, Math Comp., Vol27, 339-344.
- ^ 山本哲郎「ある代数方程式解法と解の事後評価法」『数理科学』第14巻第7号、1976年、52-57頁、(NDLJP):3213068。
- ^ Smith, B. T. (1970). Error bounds for zeros of a polynomial based upon Gerschgorin's theorems. Journal of the ACM (JACM), 17(4), 661-674.
- ^ DKA法とSmithの定理を組み合わせることで代数方程式の精度保証付き数値計算を行うことができる。
- ^ Kyurkchiev N. V., A. Andreev (1985) Compt. rend. Acad. bulg. Sci., 38, No 11, 1461–1463 (ロシア語)
関連文献
和文
- 小野令美. (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 法