随机多项式空间和计算复杂性理论 |
| |
引用本文: | 王兴华,宣晓华.随机多项式空间和计算复杂性理论[J].中国科学A辑,1987,30(1):34-43. |
| |
作者姓名: | 王兴华 宣晓华 |
| |
作者单位: | 杭州大学教学系 |
| |
摘 要: | 按照Smale对随机多项式空间概率分布的约定,讨论了多项式零点计算的复杂性.指出:(1)王则柯和徐森林的研究并没有表明Kuhn算法比Newton迭代好;(2)通过“二阶逼近零点”而不是“逼近零点”的概念把Kuhn算法和Newton迭代组合起来的话,王和徐的结果并经某些高维复区域的体积计算表明这是一个有效的算法;(3)进一步的分析表明稍加改进的Lehmer算法的估计成本比Kuhn算法的估计成本更低;(4)这种改进的Lehmer算法和一种并行圆盘迭代组合比Kuhn算法和Newton迭代组合的估计成本更低,并且不存在Wilkinson所说的“降次、精炼”中的困难,因而值得推荐.
|
|
| 点击此处可从《中国科学A辑》浏览原始摘要信息 |
| 点击此处可从《中国科学A辑》下载免费的PDF全文 |
|