结式 resultant
2023年11月30日
#analysis
介绍
结式用来计算曲线的交点、消元、找参数化曲线的隐含方程。
为了引出定义，思考如下问题：
f
(
x
)
=
x
2
−
5
x
+
6
g
(
x
)
=
x
3
−
x
+
6
\begin{align*} f(x)=&x^2-5x+6 \\ \\ g(x)=&x^3-x+6 \end{align*}
f(x)=g(x)=x2−5x+6x3−x+6
这两个多项式在复平面上是否有相同的零点？我们该如何知道它们是否有相同的根？直接计算是不太可能的，因为没有具体的公式去计算高次方程的零点。所以需要其他的方法，比如将根看成是方程的因子。
f
(
x
)
g
(
x
)
x
−
α
=
f
(
x
)
x
−
α
g
(
x
)
f(x) \frac{g(x)}{x- \alpha }= \frac{f(x)}{x- \alpha }g(x)
f(x)x−αg(x)=x−αf(x)g(x)
多项式
f
,
g
{f,g}
f,g 有相同的零点，当且仅当存在不等于
0
{0}
0 的多项式
r
,
s
{r,s}
r,s ，使得
f
(
x
)
r
(
x
)
=
s
(
x
)
g
(
x
)
f(x)r(x)=s(x)g(x)
f(x)r(x)=s(x)g(x)
deg
r
<
deg
g
,
deg
s
<
deg
f
\deg r<\deg g \,\,,\,\, \deg s< \deg f
degr<degg,degs<degf
仍以上面两个多项式为例，
r
{r}
r 的次数最大为
2
{2}
2 ，设
r
(
x
)
f
(
x
)
=
(
a
2
x
2
+
a
1
x
+
a
0
)
(
1
x
2
−
5
x
+
6
)
=
a
2
⋅
1
x
4
+
a
2
⋅
(
−
5
)
x
3
+
a
2
⋅
6
x
2
+
a
1
⋅
1
x
3
+
a
1
⋅
(
−
5
)
x
2
+
a
1
⋅
6
x
+
a
0
⋅
1
x
2
+
a
0
⋅
(
−
5
)
x
+
a
0
⋅
6
=
[
a
2
a
1
a
0
]
[
1
−
5
6
0
0
0
1
−
5
6
0
0
0
1
−
5
6
]
[
x
4
x
3
x
2
x
1
x
0
]
\begin{align*} r(x)f(x)=&(a_2x^2+a_1x+a_0)(1x^2-5x+6) \\ \\ =&a_2 \cdot 1x^4+a_2 \cdot (-5)x^3+a_2 \cdot 6x^2 \\ \\ &+a_1 \cdot 1x^3+a_1 \cdot (-5)x^2+a_1 \cdot 6x \\ \\ &+a_0 \cdot 1x^2+a_0 \cdot (-5)x+a_0 \cdot 6 \\ \\ =&[a_2 \,\,\, a_1 \,\,\, a_0] \begin{bmatrix} 1&-5&6&0&0\\0&1&-5&6&0\\0&0&1&-5&6 \end{bmatrix} \begin{bmatrix} x^4\\x^3\\x^2\\x^1\\x^0 \end{bmatrix} \end{align*}
r(x)f(x)===(a2x2+a1x+a0)(1x2−5x+6)a2⋅1x4+a2⋅(−5)x3+a2⋅6x2+a1⋅1x3+a1⋅(−5)x2+a1⋅6x+a0⋅1x2+a0⋅(−5)x+a0⋅6[a2a1a0]
100−5106−5106−5006
x4x3x2x1x0
同理，
s
{s}
s 的最大次数为
1
{1}
1 ，设
s
(
x
)
g
(
x
)
=
(
b
1
x
+
b
0
)
(
1
x
2
−
1
x
+
6
)
=
b
1
⋅
1
x
4
+
0
x
3
+
b
1
⋅
(
−
1
)
x
2
+
b
1
⋅
6
x
+
b
0
⋅
1
x
3
+
0
x
2
+
b
0
⋅
(
−
1
)
x
+
b
0
⋅
6
=
[
b
1
b
0
]
[
1
0
−
1
6
0
0
1
0
−
1
6
]
[
x
4
x
3
x
2
x
1
x
0
]
\begin{align*} s(x)g(x)=&(b_1x+b_0)(1x^2-1x+6) \\ \\ =&b_1 \cdot 1x^4+ 0x^3+ b_1 \cdot (-1)x^2+b_1 \cdot 6x \\ \\ &+b_0 \cdot 1x^3+0x^2+ b_0 \cdot (-1)x + b_0 \cdot 6 \\ \\ =&[b_1 \,\,\, b_0] \begin{bmatrix} 1&0&-1&6&0\\0&1&0&-1&6 \end{bmatrix} \begin{bmatrix} x^4\\x^3\\x^2\\x^1\\x^0 \end{bmatrix} \end{align*}
s(x)g(x)===(b1x+b0)(1x2−1x+6)b1⋅1x4+0x3+b1⋅(−1)x2+b1⋅6x+b0⋅1x3+0x2+b0⋅(−1)x+b0⋅6[b1b0][1001−106−106]
x4x3x2x1x0
写到一起，有
[
a
2
a
1
a
0
∣
−
b
1
−
b
0
]
[
1
−
5
6
0
0
0
1
−
5
6
0
0
0
1
−
5
6
1
0
−
1
6
0
0
1
0
−
1
6
]
[a_2 \,\,\, a_1 \,\,\, a_0 | \,\,\, -b_1 \,\,\, -b_0] \begin{bmatrix} 1&-5&6&0&0\\0&1&-5&6&0\\0&0&1&-5&6\\1&0&-1&6&0\\0&1&0&-1&6 \end{bmatrix}
[a2a1a0∣−b1−b0]
10010−510016−51−1006−56−100606
实际上，
r
,
s
{r,s}
r,s 就是
f
,
g
{f,g}
f,g 消去了相同零点因式后的多项式，
a
i
,
b
i
{a_i,b_i}
ai,bi 就是消去了相同零点因式后的多项式的系数。
Sylvester矩阵
f
(
x
)
=
α
m
x
m
+
α
m
−
1
x
m
−
1
+
⋯
+
α
0
g
(
x
)
=
β
n
x
n
+
β
n
−
1
x
n
−
1
+
⋯
+
β
0
\begin{align*} f(x)=& \alpha_mx^m+ \alpha_{m-1}x^{m-1}+ \cdots + \alpha_0 \\ \\ g(x)=& \beta_nx^n+ \beta_{n-1}x^{n-1}+ \cdots + \beta_0 \end{align*}
f(x)=g(x)=αmxm+αm−1xm−1+⋯+α0βnxn+βn−1xn−1+⋯+β0
西尔韦斯特矩阵为：
S
(
f
,
g
,
x
)
=
[
α
m
α
m
−
1
⋯
α
0
α
m
α
m
−
1
⋯
α
0
⋯
−
−
−
−
−
−
β
n
β
n
−
1
⋯
β
0
β
n
β
n
−
1
⋯
β
0
⋯
]
(
m
+
n
)
×
(
m
+
n
)
S(f,g,x)= \begin{bmatrix} \alpha_m & \alpha_{m-1} &\cdots &\alpha_0&&\\ & \alpha_m& \alpha_{m-1}& \cdots & \alpha_0&\\ && \cdots \\ -&-&-&-&-&-\\ \beta_n& \beta_{n-1}& \cdots & \beta_0&&\\ & \beta_n& \beta_{n-1}& \cdots & \beta_0&&\\ && \cdots \end{bmatrix}_{(m+n) \times (m+n)}
S(f,g,x)=
αm−βnαm−1αm−βn−1βn⋯αm−1⋯−⋯βn−1⋯α0⋯−β0⋯α0−β0−
(m+n)×(m+n)
西尔韦斯特结式定义为西尔韦斯特矩阵的行列式，记作：
Res
(
f
,
g
,
x
)
:
=
det
(
S
(
f
,
g
,
x
)
)
\text{Res}(f,g,x):=\det(S(f,g,x))
Res(f,g,x):=det(S(f,g,x))
f
,
g
{f,g}
f,g 有相同的零点，等价于
Res
(
f
,
g
,
x
)
=
0
\text{Res}(f,g,x)=0
Res(f,g,x)=0
应用
在消元中的应用
设有参数方程
C
{C}
C ：
x
=
t
2
y
=
t
2
(
t
+
1
)
\begin{align*} x=&t^2 \\ \\ y=& t^2(t+1) \end{align*}
x=y=t2t2(t+1)
(
x
0
,
y
0
)
∈
C
⟺
∃
t
0
s
.
t
.
{
x
0
=
t
0
2
y
0
=
t
0
2
(
t
0
+
1
)
(x_0,y_0)\in C \iff \exists t_0 \,\,\, s.t. \,\,\, \begin{cases} x_0=t_0^2\\ y_0=t_0^2(t_0+1) \end{cases}
(x0,y0)∈C⟺∃t0s.t.{x0=t02y0=t02(t0+1)
方程组存在相同零点
⟺
Res
(
t
2
−
x
0
,
t
3
+
t
2
−
y
0
,
t
)
=
0
\iff \text{Res}(t^2-x_0,t^3+t^2-y_0,t)=0
⟺Res(t2−x0,t3+t2−y0,t)=0
f
(
t
)
=
t
2
+
0
t
−
x
g
(
t
)
=
t
3
+
t
2
+
0
t
−
y
\begin{align*} f(t)=&t^2+0t-x \\ \\ g(t)=&t^3+t^2+0t-y \end{align*}
f(t)=g(t)=t2+0t−xt3+t2+0t−y
Res
(
f
,
g
,
t
)
=
det
(
[
1
0
−
x
1
0
−
x
1
0
−
x
1
1
0
−
y
1
1
0
−
y
]
)
=
−
x
3
+
y
2
−
2
x
y
+
x
2
\begin{align*} \text{Res}(f,g,t)=& \det( \begin{bmatrix} 1&0&-x \\ &1&0&-x \\ &&1&0&-x\\ 1&1&0&-y\\ &1&1&0&-y \end{bmatrix}) \\ \\ =&-x^3+y^2-2xy+x^2 \end{align*}
Res(f,g,t)==det(
110111−x0101−x0−y0−x−y
)−x3+y2−2xy+x2
传递函数的化简
设传递函数分子为
N
(
s
)
{N(s)}
N(s) ，分母为
D
(
s
)
{D(s)}
D(s) ，化简后的传递函数分子为
N
‾
(
s
)
{\overline{ N}(s)}
N(s) ，分母为
D
‾
(
s
)
{ \overline{D} (s)}
D(s) 。
N
(
s
)
=
α
m
s
m
+
α
m
−
1
s
m
−
1
+
⋯
+
α
0
D
(
s
)
=
β
n
s
n
+
β
n
−
1
s
n
−
1
+
⋯
+
β
0
\begin{align*} N(s)=& \alpha_ms^m+ \alpha_{m-1}s^{m-1}+ \cdots + \alpha_0 \\ \\ D(s)=& \beta_ns^n+ \beta_{n-1}s^{n-1}+ \cdots + \beta_0 \end{align*}
N(s)=D(s)=αmsm+αm−1sm−1+⋯+α0βnsn+βn−1sn−1+⋯+β0
N
‾
(
s
)
=
a
k
s
k
+
a
k
−
1
s
k
−
1
+
⋯
+
a
0
D
‾
(
s
)
=
b
l
s
l
+
b
l
−
1
s
l
−
1
+
⋯
+
b
0
\begin{align*} \overline{N} (s)=& a_ks^k+ a_{k-1}s^{k-1}+ \cdots +a_0 \\ \\ \overline{D}(s)=& b_ls^l+ b_{l-1}s^{l-1}+ \cdots + b_0 \end{align*}
N(s)=D(s)=aksk+ak−1sk−1+⋯+a0blsl+bl−1sl−1+⋯+b0
由前面的分析，可知
[
a
k
⋯
a
0
∣
b
l
⋯
b
0
]
S
(
N
,
D
,
s
)
=
0
[a_k \cdots a_0|b_l \cdots b_0]S(N,D,s)=0
[ak⋯a0∣bl⋯b0]S(N,D,s)=0
∴
S
(
N
,
D
,
s
)
T
[
a
k
⋮
a
0
b
l
⋮
b
0
]
=
0
\therefore S(N,D,s)^ \mathrm T \begin{bmatrix} a_k \\ \vdots \\ a_0 \\ b_l \\ \vdots \\b_0 \end{bmatrix}=0
∴S(N,D,s)T
ak⋮a0bl⋮b0
=0
所以求西尔韦斯特矩阵转置矩阵的零空间就能得到简化传递函数的系数。
![[算法每日一练]-双指针 （保姆级教程篇 1） #A-B数对 #求和 #元音字母 #最短连续子数组 #无重复字符的最长子串 #最小子串覆盖 #方块桶](https://img-blog.csdnimg.cn/direct/0f587523dead4d158a3c637428eddd91.png)
