Poincaré-Miranda定理的实现

Question

测试连续函数在给定区间 [x0, x1] 内是否有一个简单根是相对容易的：根据 介值定理，当函数在 x0 处的值与 x1 处的值符号相反时，就存在（至少）一个根。

例如，给定一个二次函数：

g(x): a*x**2 + b*x + c = 0

测试看起来像这样：

if sign of g(x0) is opposite of sign of g(x1)
then return true
else return false

对于多元情况，有坡松-米兰达定理，但是我在阅读链接文章时实施测试遇到了一些困难。

给定两个二次双变量函数：

g1(x, y): a1*x**2 + b1*y**2 + c1*x*y + d1*x + e1*y + f1 = 0
g2(x, y): a2*x**2 + b2*y**2 + c2*x*y + d2*x + e2*y + f2 = 0

给定一个矩形区域 [x0, x1] x [y0, y1]，如何检查该区域内是否至少存在一个根？

我的意思是，我认为测试应该类似于以下内容（这不起作用）：

if (sign of g1(x0, y0) is opposite of sign of g1(x1, y0) and
    sign of g1(x0, y1) is opposite of sign of g1(x0, y1) and
    sign of g2(x0, y0) is opposite of sign of g2(x1, y0) and
    sign of g2(x0, y1) is opposite of sign of g2(x0, y1))
then return true
else return false

请问有人知道需要检查哪些函数对、区间端点和逻辑运算符，以及以什么顺序进行检查吗？

- Ecir Hana

---

你的一维测试失败了，例如 g(x) = x**2 - 1，x0 = -2，x1 = 2。 - David Eisenstat

@DavidEisenstat 我理解你的意思，但是“一个根”是指描述“一个”根。你的例子在区间内有两个根。 - Ecir Hana

Answer 1

你需要检查你的双变量函数

g1(x, y): a1*x**2 + b1*y**2 + c1*x*y + d1*x + e1*y + f1 = 0
g2(x, y): a2*x**2 + b2*y**2 + c2*x*y + d2*x + e2*y + f2 = 0

满足

I).  g1(x0,y) < 0, for all y in [y0,y1]
II). g2(x,y0) < 0, for all x in [x0,x1]

并且

III). g1(x1,y) > 0, for all y in [y0,y1]
IV).  g2(x,y1) > 0, for all x in [x0,x1]

您的函数是二次的，因此可以在不沿着4个边界取样的情况下完成。例如，对于g1（x0，y）的第一个条件，只需将x0代入x，得到关于y的二次方程：

G1(y) = b1*y**2 + c1*x0*y + e1*y + (f1 + d1*x0 + a1*x0**2)

我们需要检查在[y0,y1]范围内，G1是否曾经对y为正。由于G1是二次的，它的最大值可能出现在{G1'=0, G1''<0}处或者在端点处。因此：

a. express G1' analytically, use simple bisection to find a root in [y0,y1]
b. if there is one, say y*, express G1'' analytically and compute G1''(y*)
c. if G1''(y*) is also < 0 then you have your maximum y*
d. if G1(y*) > 0 then the condition are violated, you may break
e. if not, then test the endpoints G1(y0), G1(y1).
f. if any of those are > 0 then break.

如果您的函数通过这些测试而没有出现错误，那么您已经满足了上述4个条件中的第一个条件（I）。类似地，可以以类似的方式测试条件（II-IV）。如果所有条件都成立，则Miranda测试成立，并且您有两个函数的重合根。如果不是，则您处于“可能”的情况 - 这些函数可能仍然具有共同的根，但您必须使用不同的方法来证明存在性。

- Charles Pehlivanian

---

非常感谢！请问我还有几个问题：1. 所有的测试都是由“AND”连接的吗？我的意思是，if g1(x0,y0) < 0 AND g1(x0,y1) < 0 AND g2(x0,y0) < 0 AND g2(x1,y0) < 0 AND g1(x1,y0) > 0 AND g1(x1,y1) > 0 AND g2(x0,y1) > 0 AND g2(x1,y1) > 0？2. 当你说“<”（在I和II中）和“>”（在III和IV中）时，你真正的意思是应该有相反的符号，所以即使是“>”和“<”，也算对吧？ - Ecir Hana

3. 二次函数只是一个例子，如果是三次或更高次的情况该怎么办呢？我的意思是，随着阶数的增加，“a.-f.”变得越来越难处理，难道没有一种通用的技巧吗？
4. 如果是“可能”的情况怎么办？将区域分成四个象限？也许有其他测试可以与M.-P.结合使用，以区分“可能”的情况？
5. 如果我知道在该区域内有零个或一个根，这会改变情况或有所帮助吗？

- Ecir Hana

是的 - 并且 - 所有测试都必须满足。是的，相反的符号会像你所描述的那样。 - Charles Pehlivanian

如果函数不是二次函数而是多项式函数，测试就更加困难。例如对于四次方程，您仍然需要验证测试I中的最大值<0。现在导数有3个可能的零点，您必须通过二分法、巧妙地窗口化和二分法找到它们。然后进行类似的过程。对于一般函数，没有确定的方法可以确定整个边界上的函数是否<0，这是@Chris Beck上面提到的问题。 - Charles Pehlivanian

Answer 2

首先，您原始的基于“中间值”的代码并没有完全实现它所宣传的功能：

To test whether a continuous function has a root in a given interval [x0, x1] is relatively easy: according to Intermediate value theorem when the sign of function value at x0 is opposite to the sign at x1, there is (at least) one root.

The test looks like:

if sign of g(x0) is opposite of sign of g(x1)
then return true
else return false

这个“测试”存在单向误差，正如David Eisenstat所指出的那样。如果符号确实相反，则return true是可以的，但如果符号不相反，则return false可能应该是return maybe或其他类似的东西...

---

其次，关于Poincare Miranda定理，在高维度中仅比较几个点的符号不足以提供足够的信息应用该定理。

考虑n个变量的n个连续函数。假设对于每个变量xi，当xi=0时函数fi恒为负，当xi=1时函数fi恒为正。那么在n维单位立方体中存在一个点，使得所有函数同时等于0。

如果一个连续函数在某个区域内“恒为负”，则没有黑盒测试可用。

你需要假设更多的内容，例如，你假设它实际上是一个低次多项式，并在足够多的点上对其进行采样以发现其系数等。

---

如果我们像您所说的假设我们有两个双变量二次方程，并且我们实际上有（或推断出）系数...这是可能的。

我会简单地将x_i的值替换到每个函数中，使其化简为单变量二次方程，然后使用我们在小学学习的二次公式解决其根（如果有）。然后检查它们是否出现在感兴趣的区域内。然后测试根之间的点以确定符号。然后你就会知道定理是否适用。

有可能你可以求解一个封闭形式的精确条件，但我不确定这是否会真正帮助你编写更好（更简单/更高效）的实现。

以下是伪代码：

 def quadratic_positive_in_region(p, x_0, x_1)
   ASSERT(p is univariate)
   ASSERT(x_0 <= x_1)

   // If one of the roots lies in the region then
   // we are zero there, and thus not positive
   def roots = quadratic_formula(p)
   for r in roots:
     if x_0 <= r and r <= x_1 then return false

   // If there are no roots in the region then
   // we are either always positive or always negative,
   // so test a single point to determine.
   if p(x_0 + x_1 / 2) > 0 then return true       
   return false

 def poincare_miranda(g1, g2, x_0, x_1, y_0, y_1)
   return quadratic_positive_in_region(-g1 | y = y_0, x_0, x_1) and
          quadratic_positive_in_region( g1 | y = y_1, x_0, x_1) and
          quadratic_positive_in_region(-g2 | x = x_0, y_0, y_1) and
          quadratic_positive_in_region( g2 | x = x_1, y_0, y_1)

 def generalized_test(g1, g2, x_0, x_1, y_0, y_1)
   return poincare_miranda( g1,  g2, x_0, x_1, y_0, y_1) or
          poincare_miranda(-g1,  g2, x_0, x_1, y_0, y_1) or
          poincare_miranda(-g1, -g2, x_0, x_1, y_0, y_1) or
          poincare_miranda( g1, -g2, x_0, x_1, y_0, y_1)

我在这里使用一些符号，其中-运算符可应用于多项式，而|符号表示将值替换为多项式中的变量。

- Chris Beck

---

如果我允许“可能”的答案，2D测试会是什么样子？类似于1D情况，如果该区域中只有一个根，测试是否有效？最后，通过“替换”和二次方程，我不会得到四次方程，而不是“一元二次方程”吗？ - Ecir Hana

当然可以，但我的主要问题是这样的二维测试会是什么样子？ - Ecir Hana

我在我的回答中描述了2D测试，但我会进行编辑以提供更多细节。 - Chris Beck

非常感谢您的编辑，但这不是我要问的。我不想解二次方程：“Poincaré-Miranda定理的主要意义在于它能够保证函数存在一个零点，而无需明确地解决一个零点”（来自链接文章参考文献）。你说的“我们实际上有（或推导出）系数”是什么意思？这两个函数具有已知的系数。同样，类似于1D情况（没有“单侧误差”），如果只有一个根，为什么不能使用该定理呢？ - Ecir Hana

（1）根据所示的例子，1D情况确实有单侧误差。即：如果 f(x_0) 和f(x_1) 的符号不同且 f 连续，则确实在 x_0 和x_1 之间存在某个零点。但反之亦然——连续函数f 可能在 x_0 和 x_1 之间具有零点，而 x_0 和 x_1 的符号也相同。如果假设全局函数最多只有一个根，则它将变为当且仅当，但这不再是中值定理，而是其他事物。 - Chris Beck