講演名 | 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 |
発行日 |