線形計画法を援用した新しい区間演算方式に関する研究

一种新的线性规划区间计算方法研究

• 批准号: 09750458
• 负责人: 柏木 雅英
• 金额: $ 1.34万
• 依托单位: Waseda University (1998)Kyushu University (1997)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1997
• 资助国家: 日本
• 起止时间: 1997 至 1998
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-09750458/
• 关键词: 区間演算; 線形計画法; 精度保証付き数値計算; 単体法

計算機自身に数値計算を行うと同時に結果の精度の保証を行わせるという発想とその研究は古くから行われてきた。精度保証付き数値計算と呼ばれるようになったこの分野は、ドイツを中心として近年急速に発展し、今後の数値計算法のあるべき姿として世界的に注目を集めている。区間演算とは、一つの実数値を[下限,上限]のように2つの計算機で表現可能な数で挟んで演算を行う方式であり、計算誤差の把握のみならず一種の集合値演算を行うことが出来、精度保証付き数値計算を支える最も重要な技法の一つである。ところが、一方で評価が悲観的に過ぎ、確かに真の値を含む区間を得られるもののその幅はしばしば非現実的に大きくなってしまうという問題点を抱えている。本研究では、入力変数の線形和をデータメンバとする特殊な演算を定義し、線形計画法を用いることにより区間演算の過大評価の問題を解決し、一般的かつ超高性能な区間演算法を確立した。また、本手法で用いる線形計画法として一般的な単体法を用いた場合、本手法の中で解かれる複数の線形計画問題は共通の制約を数多く持つことから、計算方法を工夫することにより大幅に計算量を削減できることを示した。これにより、線形計画問題の許容解の一頂点を求めるいわゆるPhase-1を完全に省略できる。また、本手法を多くのプログラムに対して素直に適用可能な様に計算機上に実装し、その有効性を確認した。上記のライブラリを用いて、区間演算による値域の評価を基礎とした数多くのアルゴリズムに適用し、その効果を確認した。これにより、理論的には問題なくとも区間演算の過大評価が大き過ぎて実用には難しいと思われていた多くのアルゴリズムが救済されたと考えられる。また、本手法内で使用される線形計画法のアルゴリズム自身の精度保証の問題についても、新たな精度保証付き線形計画法のの開発によって解決することが出来た。

The computer's own numerical calculations are performed simultaneously, and the accuracy of the results is guaranteed. Accuracy guarantee: calculation of numerical value, call for attention, focus on attention, rapid development in recent years, calculation of numerical value, call for attention, focus on attention in the world Interval calculation, a set of numerical values,[lower limit, upper limit], 2 sets of computer performance, possible calculation, calculation, calculation error, calculation, accuracy, calculation, support, most important technique. The problem is that if you want to get rid of the problem, you can get rid of it. In this study, we define the special algorithm for linear sum of input force, solve the problem of over-evaluation of interval algorithm for linear planning, and establish the general algorithm for ultra-high performance interval algorithm. The linear planning method used in this method is different from the general linear planning method. When the linear planning method is used in this method, the common constraints of multiple linear planning problems in this method are many. The calculation method is time-consuming. The calculation amount is greatly reduced. A vertex of the linear planning problem is found in Phase-1, which is completely omitted. This method is applicable to a variety of applications, such as computer installation, and verification of its effectiveness. Note that the application of the above algorithm, interval calculation, evaluation of the domain, the number of applications, and the results are confirmed. This is a problem that we have to deal with. In this paper, the problem of precision assurance of linear planning method is solved.

项目成果

M.Kashiwagi: "An All Solution Algorithm using Affine Arithmetic" Proc.1998 Symposium on Nonlinear Theory and its Applications. 903-906 (1998)

M.Kashiwagi：“使用仿射算术的全解算法”Proc.1998 非线性理论及其应用研讨会。

M.Kashiwagi: "Simplex Method for Calculating Optimal Value with Guaranteed Accuracy" Proc.1997 Symposium on Nonlinear Theory and its Applications. 317-320 (1997)

M.Kashiwagi：“计算保证精度的最优值的单纯形方法”Proc.1997 非线性理论及其应用研讨会。

Masahide Kashiwagi: "Simplex Method for Calculating Optimul Valne with Gnaranteed Accuracy" Proc.1997 International Symposium on Nonlinear Theory and its Application. 317-320 (1997)

Masahide Kashiwagi：“Simplex Method for Calculate Optimul Valne with Gnaranteed Accuracy”Proc.1997 国际非线性理论及其应用研讨会。

神沢雄智,柏木雅英,大石進一: "パラメータ依存非線形方程式のすべての解を精度保証付きで求めるアルゴリズム" 電子情報通信学会論文誌(A). J80-A,6. 920-925 (1997)

Yutomo Kanzawa、Masahide Kashiwagi、Shinichi Oishi：“以保证精度找到参数相关非线性方程的所有解的算法”，电子、信息和通信工程师学会汇刊 (A)，6. J80-925 ( 1997）

神沢雄智,柏木雅英,大石進一,中村晴幸: "有限ステップで停止する非線形方程式のすべての解を精度保証付きで求めるアルゴリズム" 電子情報通信学会論文誌(A). J80-A,7. 1130-1137 (1997)

Yutomo Kanzawa、Masahide Kashiwagi、Shinichi Oishi、Haruyuki Nakamura：“以有限步长停止并保证精度的非线性方程的所有解的算法”，电子信息与通信工程师学会汇刊 (A)，7。 1130 -1137 (1997)