「デュラン＝カーナー法」の版間の差分
削除された内容 追加された内容
編集の要約なし |
編集の要約なし |
||
| 1行目: | 1行目: | ||
'''デュラン＝カーナー法'''（デュラン＝カーナーほう、Durand-Kerner method、 DK法、[[ブルガリア]]ではWeierstrass-Dochev法と呼ばれる）は[[カール・ワイエルシュトラス]]が1891年に発見し<ref>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.</ref>、Durand(1960)<ref>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.</ref>、Dochev(1962)、Presic(1966)、Kerner(1966)<ref>Kerner, |
'''デュラン＝カーナー法'''（デュラン＝カーナーほう、Durand-Kerner method、 DK法、[[ブルガリア]]ではWeierstrass-Dochev法と呼ばれる）は[[カール・ワイエルシュトラス]]が1891年に発見し<ref>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.</ref>、Durand(1960)<ref>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.</ref>、Dochev(1962)、Presic(1966)、Kerner(1966)<ref>{{Cite journal |author=Kerner, Immo O |year=1966 |url=https://doi.org/10.1007/BF02162564 |title=Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen |journal=Numerische Mathematik |volume=8 |issue=3 |pages=290-294 |publisher=Springer |doi=10.1007/BF02162564}}</ref>がそれぞれ独立に再発見した[[多項式]]に対する[[求根アルゴリズム]]、[[反復法 (数値計算)|反復法]]であり、[[ニュートン法]]の進化形といえる<ref>Petković, M. (1989). Iterative methods for simultaneous inclusion of polynomial zeros. Berlin [u.a.]: Springer. pp. 31–32. ISBN 978-3-540-51485-5.</ref><ref>{{Cite book |和書 |author=山本哲朗 |title=数値解析入門 |edition=増訂版 |date=2003-06 |publisher=[[サイエンス社]] |series=サイエンスライブラリ 現代数学への入門 14 |ISBN=4-7819-1038-6}}</ref>。Dk法の命名はAberth(1973)による。DK法に対してAberth(1973)<ref>{{cite journal |author=Aberth, Oliver |year=1973 |title=Iteration methods for finding all zeros of a polynomial simultaneously |journal=Mathematics of computation |volume=27 |issue=122 |pages=339-344 |url=https://www.ams.org/journals/mcom/1973-27-122/S0025-5718-1973-0329236-7/}} |
||
</ref>の提案した初期値を用いる手法はDKA法（Durand-Kerner-Aberth method）と称される。DKA法は山本哲朗による命名である<ref>{{Cite journal|和書|author=山本哲朗|year=1976|title=ある代数方程式解法と解の事後評価法|journal=数理科学|volume=14|issue=7|pages=52-57|id={{NDLJP|3213068}}}}</ref>。 |
|||
==DKA法の誤差評価== |
==DKA法の誤差評価== |
||
DKA法の誤差評価はSmith(1970)で与えられた<ref>Smith, |
DKA法の誤差評価はSmith(1970)で与えられた<ref>{{Cite journal |author=Smith, Brian T |year=1970 |title=Error bounds for zeros of a polynomial based upon Gerschgorin's theorems |url=https://doi.org/10.1145/321607.321615 |journal=Journal of the ACM (JACM) |volume=17 |issue=4 |pages=661-674 |publisher=ACM New York, NY, USA |doi=10.1145/321607.321615}}</ref><ref>DKA法とSmithの定理を組み合わせることで代数方程式の[[精度保証付き数値計算]]を行うことができる。</ref>。Smithの定理では与えられた多項式のすべての根がある閉円板の合併に含まれ、その連結成分の1つがm個の閉円板からなればその中にちょうどm個の根があると示された。この定理の証明は『数値解析入門』{{harv|山本|2003}}の付録に詳述されている。 |
||
==DK法の続行が不可能となるような初期値の存在== |
==DK法の続行が不可能となるような初期値の存在== |
||
| 10行目: | 12行目: | ||
{{脚注ヘルプ}} |
{{脚注ヘルプ}} |
||
{{reflist}} |
{{reflist}} |
||
==関連文献== |
==関連文献== |
||
===和文=== |
===和文=== |
||
| 20行目: | 23行目: | ||
* Durand-Kerner法の効率的な初期値の簡単な設定法 ([[日本応用数理学会]]論文誌 Vol.3,No.4,1993,pp.451-464) 小澤一文 |
* Durand-Kerner法の効率的な初期値の簡単な設定法 ([[日本応用数理学会]]論文誌 Vol.3,No.4,1993,pp.451-464) 小澤一文 |
||
* Durand-Kerner型補助関数を用いた非線形方程式の多段反復解法 ([[日本応用数理学会]]論文誌 Vol.4,No.2,1994,pp.67-80) 櫻井鉄也, 杉浦洋, 鳥居達生 |
* Durand-Kerner型補助関数を用いた非線形方程式の多段反復解法 ([[日本応用数理学会]]論文誌 Vol.4,No.2,1994,pp.67-80) 櫻井鉄也, 杉浦洋, 鳥居達生 |
||
* {{Cite book|和書|author=山本哲朗 |title=数値解析入門 |publisher=サイエンス社 |year=2003 |edition=増訂版 |series=サイエンスライブラリ現代数学への入門 |ISBN=4781910386 |id={{国立国会図書館書誌ID|000004165606}} |url=https://id.ndl.go.jp/bib/000004165606 |ref={{harvid|山本|2003}}}} |
|||
===英文=== |
===英文=== |
||
* Guggenheimer, H. (1986). Initial approximations in Durand-Kerner's root finding method. [[:en:BIT Numerical Mathematics]], 26(4), 537-539. |
* Guggenheimer, H. (1986). Initial approximations in Durand-Kerner's root finding method. [[:en:BIT Numerical Mathematics]], 26(4), 537-539. |
||
2024年1月5日 (金) 03:15時点における最新版
デュラン＝カーナー法（デュラン＝カーナーほう、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, Immo O (1966). “Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen”. Numerische Mathematik (Springer) 8 (3): 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, Oliver (1973). “Iteration methods for finding all zeros of a polynomial simultaneously”. Mathematics of computation 27 (122): 339-344.
- ^ 山本哲朗「ある代数方程式解法と解の事後評価法」『数理科学』第14巻第7号、1976年、52-57頁、NDLJP:3213068。
- ^ Smith, Brian T (1970). “Error bounds for zeros of a polynomial based upon Gerschgorin's theorems”. Journal of the ACM (JACM) (ACM New York, NY, USA) 17 (4): 661-674. doi:10.1145/321607.321615.
- ^ 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) 櫻井鉄也, 杉浦洋, 鳥居達生
- 山本哲朗『数値解析入門』（増訂版）サイエンス社〈サイエンスライブラリ現代数学への入門〉、2003年。ISBN 4781910386。国立国会図書館書誌ID:000004165606。
英文
[編集]- 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.
外部リンク
[編集]
 | この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。 |