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

Question

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

\n\n

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

\n\n

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

\n\n

测试看起来像：

\n\n

if sign of g(x0) is opposite of sign of g(x1)\nthen return true\nelse return false\n

\n\n

对于多变量情况，有Poincar\xc3\xa9\xe2\x80\x93Miranda 定理，但我在阅读链接的文章时很难正确实现测试。

\n\n

给定两个二次二元函数：

\n\n

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

\n\n

和一个矩形区域 [x0, x1] x [y0, y1]，如何检查该区域中是否至少有一个根？

\n\n

我的意思是，我认为测试应该看起来有点像（这不起作用）：

\n\n

if (sign of g1(x0, y0) is opposite of sign of g1(x1, y0) and\n    sign of g1(x0, y1) is opposite of sign of g1(x0, y1) and\n    sign of g2(x0, y0) is opposite of sign of g2(x1, y0) and\n    sign of g2(x0, y1) is opposite of sign of g2(x0, y1))\nthen return true\nelse return false\n

\n\n

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

\n

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 个案例的所有 4 个边界采样值即可完成此操作。例如，对于 g1(x0,y) 的第一个条件，只需将 x0 代入 x，即可获得 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)。如果所有条件成立，则米兰达检验成立，并且两个函数有重合根。如果不是，那么你就处于“也许”的情况 - 这些函数可能仍然有一个共同的根，但你必须使用不同的方法来证明存在。