从不动点定理到计算复杂性

多项式求根的库恩算法

复平面对\(C\times[0,\infty)\)做单纯剖分,越往上剖分越细
对剖分的顶点按照w=f(z)做如下整数标号

IMG_3332
对于\(C\times[0,\infty)\)上的顶点,按照\(f(z)=z^n\)进行标号
IMG_3335

易知计算只在半空间的一个大圆筒内进行
每个四面体只能穿行一次
算法的可行性

计算复杂性论题

IMG_3336
IMG_3338
IMG_3339

牛顿方法(初始的选取)