Why Does Information-Based Complexity Use the Real Number Model?
Why Does Information-Based Complexity Use the Real Number Model?
复制标题
为什么基于信息的复杂性使用实数模型？
DOI：
10.1016/s0304-3975(98)00300-4
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
H. Wozniakowski
中科院分区：
文献类型：
--
作者：
H. Wozniakowski
我们解释了为什么基于信息的复杂性使用真实的数模型。在真实的数模型中的结果基本上与具有固定精度模的浮点运算中的结果相同，这两个重要假设是：·我们仅使用稳定算法，·与条件数、浮点运算的循环单位和稳定算法的累积常数的乘积相比，近似误差不会太小。我们说明了这一点的一个例子，解决非线性方程的二分法。我们还表明可能的复杂性和稳定性之间的权衡，以及需要使用多个或不同的精度病态的问题。
We explain why information-based complexity uses the real number model. Results in the real number model are essentially the same as in floating point arithmetic with fixed precision modulo two important assumptions, namely • we use only stable algorithms, • the approximation error is not too small, compared to the product of the condition number, the roundoff unit of floating point arithmetic, and the accumulation constant of a stable algorithm. We illustrate this by an example of solving nonlinear equations by bisection. We also indicate the possible tradeoffs between complexity and stability, and the need of using multiple or varying precision for ill-conditioned problems.
影响因子：
2.1
作者：
通讯作者：
--