庞加莱-米兰达定理的实现

Question

检验一个连续函数在给定区间[x0,x1]内是否有~~一个根~~一个单根比较容易：根据Intermediate value theorem当符号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

对于多变量情况，有 Poincaré–Miranda theorem 但我在阅读链接文章后很难正确实施测试。

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

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

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

Answer 1

首先，您最初基于 "intermediate value" 的代码并没有完全按照广告宣传的那样去做：

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 指出的那样，"test" 存在片面错误。如果符号确实相反，那么 return true 是可以的，但如果符号不相反，那么 return false 可能应该是 return maybe 之类的...

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

Consider n continuous functions of n variables. Assume that for every variable x_i, the function f_i is constantly negative when x_i = 0 and constantly positive when x_i = 1. Then there is a point in the n-dimensional unit cube in which all functions are simultaneously equal to 0.

如果某个区域的连续函数"constantly negative"，则没有黑盒测试。

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

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

我会做的很简单，根据需要在每个函数中代入 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)

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

Answer 2

您需要检查您的双变量功能是否正常

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 个案例的所有 4 个边界采样值即可完成此操作。例如，对于g1(x0,y)的第一个条件，只需将x代入x0，得到y的二次方程：

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

我们需要检查 G1 是否对 [y0,y1] 中的 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)可以用类似的方式进行测试。如果所有条件都成立，则米兰达检验成立，并且您有两个函数的重合根。如果不是，那么您属于 "maybe" 情况 - 函数可能仍然有一个共同的根，但您必须使用不同的方法来证明存在。

庞加莱-米兰达定理的实现

Implementation of Poincaré–Miranda theorem

algorithm

math

polynomial-math

polynomials