講演名 1998/3/13
あるクラスの非線形方程式に対する線形計画法を用いたすべての解を求めるアルゴリズム
山村 清隆, 西澤 真樹,
PDFダウンロードページ PDFダウンロードページへ
抄録(和) 区間解析は非線形方程式のすべての解を求める代表的な方法として知られている.しかし区間解析は一般に計算効率が非常に悪く, 問題の次元の増加とともに計算時間が指数関数的に増大するという欠点をもつ.前回の報告では, 区間解析に線形計画法を導入した.非線形方程式の新しい全解探索法を提案した.この方法の基本的なアイデアは, 与えられた領域に対し区間拡張を用いて非線形関数の上限と下限を求め, 非線形関数を補助変数と線形不等式に置き換えることにより線形計画問題を定式化し, それに単体法を適用することにより解の非存在を効率よく判定するというものである.本報告では, 回路方程式を含むあるクラスの非線形方程式に対して, この方法の計算効率を大幅に改善するいくつかの手法を提案する.提案手法の導入により, 100変数方程式やトランジスタ回路方程式などのすべての解を効率よく求めることに成功している.
抄録(英) Recently, a new computational test has been proposed for nonexistence of a solution to a system of nonlinear equations using linear programming. This test is termed the LP test. It has been shown that the LP test is much more powerful than the conventional nonexistence test if the system of nonlinear equations consists of many linear terms and a relatively small number of nonlinear terms. By introducing the LP test to interval analysis, all solutions of nonlinear equations can be found very efficiently. In this paper, we propose some techniques for improving the computational efficiency of the LP test in some special cases. Using the proposed techniques, all solutions of a special class of nonlinear equations(including circuit equations)can be found very efficiently.
キーワード(和) 非線形方程式 / 区間解析 / 全解探索 / 線形計画法
キーワード(英) nonlinear equations / interval analysis / finding all solutions / linear programming
資料番号
発行日

研究会情報
研究会 NLP
開催期間 1998/3/13(から1日開催)
開催地(和)
開催地(英)
テーマ(和)
テーマ(英)
委員長氏名(和)
委員長氏名(英)
副委員長氏名(和)
副委員長氏名(英)
幹事氏名(和)
幹事氏名(英)
幹事補佐氏名(和)
幹事補佐氏名(英)

講演論文情報詳細
申込み研究会 Nonlinear Problems (NLP)
本文の言語 JPN
タイトル(和) あるクラスの非線形方程式に対する線形計画法を用いたすべての解を求めるアルゴリズム
サブタイトル(和)
タイトル(英) Interval Solution of a Class of Nonlinear Equations Using Linear Programming
サブタイトル(和)
キーワード(1)(和/英) 非線形方程式 / nonlinear equations
キーワード(2)(和/英) 区間解析 / interval analysis
キーワード(3)(和/英) 全解探索 / finding all solutions
キーワード(4)(和/英) 線形計画法 / linear programming
第 1 著者 氏名(和/英) 山村 清隆 / Kiyotaka YAMAMURA
第 1 著者 所属(和/英) 群馬大学工学部情報工学科
Department of Computer Science, Faculty of Engineering, Gunma University
第 2 著者 氏名(和/英) 西澤 真樹 / Masaki NISHIZAWA
第 2 著者 所属(和/英) 群馬大学工学部情報工学科
Department of Computer Science, Faculty of Engineering, Gunma University
発表年月日 1998/3/13
資料番号
巻番号(vol) vol.97
号番号(no) 592
ページ範囲 pp.-
ページ数 8
発行日