The main two algorithms for computing the numerical radius are the level-set method of Mengi and Overton and the cutting-plane method of Uhlig. Via new analyses, we explain why the cutting-plane approach is sometimes much faster or much slower than the level-set one and then propose a new hybrid algorithm that remains efficient in all cases. For matrices whose fields of values are a circular disk centered at the origin, we show that the cost of Uhlig's method blows up with respect to the desired relative accuracy. More generally, we also analyze the local behavior of Uhlig's cutting procedure at outermost points in the field of values, showing that it often has a fast Q-linear rate of convergence and is Q-superlinear at corners. Finally, we identify and address inefficiencies in both the level-set and cutting-plane approaches and propose refined versions of these techniques.
翻译:计算数字半径的主要两种算法是Mengi和Overton的定级法和Uhlig的切开飞机法。 通过新的分析,我们解释切开飞机法有时比定级法快得多或慢得多的原因,然后提出新的混合算法,在所有情况中都保持效率。对于其价值领域是圆盘的矩阵,我们显示Ulig方法的成本在所期望的相对准确性方面会爆炸。更一般地说,我们还分析Ulig在价值领域最外围点的切开程序的地方行为,表明它往往具有快速的Q-线性趋同率,在角是Q-线性。最后,我们发现和解决定级法和切开板方法效率低下的问题,并提出这些技术的精细版本。