抽象的
分段代数曲线是双变量样条函数的零的集合，是经典代数曲线的概括。在本文中，提出了一种算法来计算两条分段代数曲线的真实解。它主要基于Krawczyk-Moore迭代算法和良好的初始迭代间隔搜索算法。提出的算法相对易于实现。
1.简介
让成为一个连接区域。在中使用有限数量的不可还原代数曲线，我们划分该地区分为几个简单地连接的区域，称为分区单元。表示该地区的分区，这是所有分区单元的结合。
表示分段多项式的集合关于分区如下： 在哪里表示总学位的双变量多项式集。
用于整数， 我们说 是平滑度的双变量样条空间和学位实际系数。
为一个，零集 称为真正的分段代数曲线，表示。显然，分段代数曲线是经典代数曲线的概括。但是，很难研究分段代数曲线，这不仅是因为分区的复杂性，而且还因为有可能。
分段代数曲线最初是由王在多变量样条插值研究中引入的。他指出，只有当它们不在非零分段代数曲线中时，给定的插值结出适当提出[1]。近年来，Wang和他的研究小组在分段代数曲线上做了重要的工作（请参阅[见[1-8]）。例如，bēzout的定理[2，，，，4]，noether-type定理[5，，，，7]，Cayley-Bacharach定理[6]和Riemann-Roch型定理[7]建立了分段代数曲线。此外，分段代数曲线还与显着的四色猜想有关[4]。实际上，当且仅当存在三个线性分段代数曲线时，四色的猜想才能保持，而这些线性分段代数曲线的结合等于任意三角形中所有三角形的所有中心线的结合。
分段代数曲线是计算机辅助几何设计和计算几何形状的一个新的重要主题，并且在各个领域都有许多应用。有必要研究分段代数曲线的相关问题。但是，上述Bēzout定理为分段代数曲线的相交点的数量提供了理论上的界限。因此，重要的是要计算或隔离给定的分段代数曲线的真实零（分段代数品种）。2008年，王和吴[9]提出了一种算法，用于根据笛卡尔的符号规则隔离单变量花键的真实零。后来，王和张[10]通过介绍间隔迭代算法，讨论了分段代数品种的计算问题- 撤离解决方案。最近，张和王[11]讨论了在多面体分区上分段代数品种的真正根部隔离。朗和王[12]提出了基于groebner碱基的分段代数曲线的相交点算法。但是，这些算法存在一个共同的缺陷，我们不知道是否存在两个给定的分段代数曲线的相交点。这将导致巨大的计算浪费。
在本文中，我们提供了用于隔离两个分段代数曲线的实际解的算法，该曲线主要基于krawczyk-moore间隔迭代算法和良好的初始迭代间隔搜索算法。与现有方法相比，提出的方法可以大大降低计算成本[11，，，，12]。更重要的是，提出的算法易于实现。
本文的其余部分安排如下。在节中2召回了间隔迭代算法的几种概念和结果。在节中3，给出了良好的初始迭代间隔搜索算法，这是本文的关键。在节中4，概述了隔离两个分段代数曲线的实际解的主要算法。一节提供了一个说明示例5并在部分中得出结论6。
2.间隔迭代算法
摩尔引入了非线性系统的间隔迭代算法[13]，在论文中开发和修改[14-16]。回顾了有关间隔算术和间隔迭代算法的几个基本概念和结果。
定义2.1。间隔，宽度，中点，绝对价值和标志分别定义为和为-1 if;1如果和0否则。
定义2.2。表示是所有间隔的集合。为了， 和，一个定义
定义2.3。对于间隔矩阵 每个地方是间隔，然后是中点，宽度和规范分别定义为
定义2.4。让成为多项式的算术表达。一个代替了所有操作数间隔并替换所有操作作为间隔操作，结果用。然后，称为间隔评估。
现在，我们回想起Krawczyk算法的摩尔形式及其基本结果。
让成为非线性方程式变量。摩尔的间隔牛顿算法由 在哪里是包含间隔矩阵反转的间隔矩阵和是单调的间隔评估。
Krawczyk提出了改进的Interval Newton方法的版本，该方法不需要间隔矩阵的反转。Krawczyk算法具有形式 在哪里从该地区选择， 和是一个任意的非矩阵。
特别是和被选为和，分别是摩尔的摩尔形式的krawczyk算法变为 Krawczyk算法的摩尔形式具有以下三个基本属性。（1）如果是零的， 然后。（2）如果， 然后没有零。（3）如果， 然后有零。
因此，krawczyk-moore间隔迭代算法为
对于存在非线性方程的解决方案，摩尔证明了以下结果。
定理2.5（请参阅[14]）。如果两个条件 同时满意，然后存在一个独特的解决方案的在和序列至少线性收敛到。
实际上，摩尔进一步证明了第二种条件在该算法方面并不是必需的。因此，该定理在删除它后仍然存在[15]。因此，我们介绍以下定义，以促进以后的使用。
定义2.6。如果， 然后称为良好的初始迭代间隔。
很难找到良好的初始迭代间隔，我们经常可以获得经过大量迭代。
3.良好的初始迭代间隔搜索算法
Krawczyk算法中的一个重要问题是如何选择满足唯一限制的初始间隔。通常是和如果经过大量迭代后，无法满足被选为任意。也就是说，即使在没有零在这种情况下，该算法令人沮丧。如果我们能确定在规定的域中具有真正的零，并找到所有良好的初始间隔，然后将大大降低间隔迭代算法的计算成本。
为了确定是否存在代数曲线的真实解决方案和在给定的区域，我们首先介绍矢量场的旋转度方法。
封闭曲线的旋转度在矢量场，表示，等于 给定区域被封闭的曲线盘旋。
我们介绍了矢量场旋转度的主要结果。
定理3.1。如果没有代数曲线的相交点和在域中通过封闭曲线盘旋，然后是封闭曲线的旋转度在矢量场等于零。相反，如果封闭曲线的旋转度在矢量场不等于零，然后和在域中有相交点。
证明。等式（3.1）可以写为
在哪里，
可以很容易地检查
因此，如果有任何意义在满足，然后是我们拥有的绿色公式
（1）这种情况等同于和没有交叉点。转换的证明是显而易见的。
备注3.2。指出封闭曲线的旋转程度在矢量场可以方便地计算。在这种情况下，简化的旋转形式为 封闭曲线的旋转程度以逆时针方向测量正方向。我们表示矢量场的旋转程度每当这不会引起任何混乱。
现在，良好的初始迭代间隔搜索算法，概述了两种代数曲线，如下所示。
算法3.3。良好的初始迭代间隔搜索算法。
输入两条代数曲线和在任意地区。
输出所有优质初始迭代间隔的集合。
步骤1。放然后让是包含最小矩形区域。
第2步。如果，然后停下来。否则，计算。如果， 然后没有真正的解决方案并停止；如果和， 然后是一个很好的初始迭代间隔，;否则，在中点分为四个较小的矩形，由然后踏上脚步3。
步骤3。放然后踏上脚步2。
真实解决方案的数量是有限的，可以保证该算法将在有限步骤后终止。在没有一般性的情况下，我们以一个简单的例子说明了这一点。
示例3.4。让并假设
放和计算。同时，我们有。自从，那么无法得出结论，并且在中点分为四个较小的矩形，由（请参阅图1）。
然后我们有和。同时，我们计算。因此，是一个很好的初始迭代间隔，因为。此外，在是仅在三个迭代步骤之后。
但是，如果我们直接将Krawczyk-Moore算法与初始迭代间隔直接使用，那么我们有五个迭代步骤之后。因此，我们只能得出结论有一个真正的解决方案而且我们不知道是否存在真正的解决方案以外。
4.主算法
给定两条分段代数曲线，这些曲线由两个双变量花键定义和假定为零维，也就是说，它仅由有限的点组成。在这里，所有细胞假定处于“总体位置”，这意味着没有任何零位于其边界上。我们要解决的问题是隔离。
众所周知，每个内部可以描述为 在哪里，是不可还原的代数曲线。
经过和我们表示代表双变量多项式和在细胞中， 分别。隔离实际解决方案的问题在等同于隔离以下半缘系统的实际解决方案 通过上述准备，我们可以轻松地提出主要算法，用于隔离两个分段代数曲线的真实交点和在。
算法4.1。隔离分段代数曲线的实际解。
输入两个双变量花键和一个小的宽容。
输出所有隔离间隔的集合。
步骤1。放然后让做一个空套。
第2步。执行良好的初始间隔搜索算法3.3为了在并获得所有良好的迭代间隔。每个，计算， 在哪里是一个间隔评估并考虑以下三个案例。
情况1。如果对于一些， 删除。
案例2。如果对于一些，然后我们计算反复直到或者。
案例3。如果对全部和，然后设置并停下来。否则，如果我们让和计算反复直到，然后设置并停下来。
步骤3。放， 如果然后去踩2。否则，停止并输出所有隔离间隔的集合。
5.数值示例
在本节中，提供了一个示例来说明所提出的算法灵活且易于实现。
示例5.1。让成为五角大楼的凸多面体分区在， 在哪里（请参阅图2）。让和定义如下：（我）在细胞上 （ii）在细胞上 （iii）在细胞上 （iv）在细胞上
分区数，旋转程度的计算数和计算数量在每个单元格上为了找到良好的初始迭代间隔，表格在表中1。
因此，隔离间隔在是经过三个迭代步骤，具有良好的初始迭代间隔在细胞中。
备注5.2。示例中需要计算的旋转程度和迭代步骤的总数5.1分别为15和6。但是，如果我们在[10] 计算在全球范围内，需要超过三千个迭代步骤才能以相同的精度获得结果。
备注5.3。与[11，，，，12]，我们提出的方法不需要将系统转换为某些三角系统并计算多项式或间隔多项式的真实零。
6.结论和未来工作
本文提出了一种用于隔离两个分段代数曲线的实际解的算法。它主要基于krawczyk-moore间隔迭代算法和良好的初始间隔搜索算法。提出的算法易于实施，并降低了计算成本。
我们知道分段代数曲线的数字来自Bezout的数字，我们知道分段代数曲线的相交点的数量不仅取决于花纹的程度，而且还严重取决于分区的几何结构。但是，所提出的算法不使用固有特征和双变量花键的关系，而是独立地在每个细胞上执行。因此，在执行我们提出的算法之前，在相邻单元格之间建立相交点数之间的关系至关重要。这仍然是我们未来的工作。
致谢
本文得到了中国国家自然科学基金会（第11101366号和11026086）的支持，并得到了审省的自然科学基金会（Q12A010064和Y6090211）的支持。