abstract

前回のまとめが長くなってtexのレンダリングに時間がかかるので、分割。
内容は、karitonov's theoremに関して。

introduction

多項式係数に誤差が含まれている場合に、誤差領域のどの位置にあっても多項式がフルビッツ安定であることを確認する方法について。

フルビッツ安定(Hurwits stable)

実多項式$P(s)=\sum p_is^i$がフルビッツ安定であるとは、その根の実部がすべて負であることとである。フルビッツ安定な多項式はフルビッツ多項式とよぶ。

このとき、実多項式は2次以下の多項式の積に分解できることを考えれば、

性質１

$P$の係数が全て同一符号を持つ。

また、明らかに

性質2

$P(iw)$の偏角は、$w$が$-\infty$から$\infty$へと変化するとき狭義単調に増加し、
その増加量は$n\pi$となる。

さて、多項式の偶数項、奇数項だけを取り出したものをこのように書こう。

P^{even}(s):= p_0+p_2s^2+p_4s^4+...\\
P^{odd}(s):= p_1s+p_3s^3+p_5s^5+...

さらに、

P^e(\omega):=P^{even}(i\omega)\\
P^o(\omega):=\frac{P^{odd}(i\omega)}{i\omega}

と書く。これらも実多項式になることに注意。この２つは当然$\omega^2$の多項式となるので、根はそれぞれ原点対称に配置する。

補題A

$P^{even},P^{odd}$の根がすべて相異なり虚軸上で隔離することは以下と同値

$P^{e},P^{o}$の根がすべて相異なり、の正の根が実軸上で隔離し、最も原点に近いのは$P^{e}$の根である。

証：
$P^{even},P^{odd}$の根がすべて相異なり虚軸上で隔離するとしよう。

P^{even}(i\omega)=P^e(\omega)\\
P^{odd}(i\omega)/i\omega = P^o(\omega)

より、$P^{even},P^{odd}$の根に$-i$をかけたものは$P^{e},P^{o}$の根となる。
$P^{odd}(0)=0$に注意すれば、$P^{even},P^{odd}$の根で最も原点に近いのは、原点を除けば$P^{even}$の根である。$-i$をかけることが複素平面上で$-\frac{\pi}{2}$の回転と等価であることを考えれば、$P^{e},P^{o}$の根もそれに従い、実軸上にならび隔離する。
逆に、$P^{e},P^{o}$の根がすべて相異なり、の正の根が実軸上で隔離し、最も原点に近いのは$P^{e}$の根であるとしよう。先に述べたように、$P^{e},P^{o}$と$P^{even},P^{odd}$根の間には$\pi/2$回転の関係があるので、同じく根はすべて相異なり、虚軸上で隔離し、原点には$P^{even}$の根が最も近い。ところで、$P^{e},P^{o}$の根が原点対称であることを思い出せば、負の根でも同様の議論がなりたち、$P^{odd}(0)=0$によって正しく隔離される。

インタレース性

とは、以下の双方が成り立つこと。
a)$P^{even},P^{odd}$の最高次係数の符号が等しい。
b)$P^{even},P^{odd}$の根はそれぞれ相異なり、虚軸上に交互にならぶ。

さて、以下の定理が示せる

定理１．７

実多項式$P$がフルビッツ安定であることは、インタレース性を持つことと同値。

(=>)$P$が安定だとしよう。
$P$の係数はすべて同符号であり、a)は明らか。すべての係数が正と仮定しても一般性を失わない。
b)を示そう。
$arg(P(i\omega))$は狭義単調に増加することに注意しよう。
また、$P$の根は実軸に対して対称なので、$\omega$が$0$から$\infty$まで増加するときと、$-\infty$から$0$まで増加するときの$P(i\omega)$の偏角の増加は等しく、$\frac{n\pi}{2}$であり、そもそも$P(0)$は明らかに正の実数である。
従って、$P(i\omega)$は$\omega:0 \rightarrow \infty$で原点を$\frac{n\pi}{2}$だけ回転し、その間には原点を通らない。($P$の根は虚軸上に存在しないから。)
なので、虚軸上を$[\frac{n}{2}]$回横切らねばならない。そのとき実部は0となる。このときの$\omega$を$[\omega_{R,i}]$と書こう。
同様に、$P(i\omega)$は実軸を,$[\frac{n-1}{2}]$回横切るので、これらの$\omega$を$[\omega_{I,i}]$と書こう。
これらは、偏角の単調増加性より、明らかに交互にならぶことに注意しよう。また、最も原点に近いのは$[\omega_{R,1}]$であることにも同様に注意しよう。
補題Aより、$P^{even},P^{odd}$の根は虚軸上に交互に並ぶことがわかる。
(<=)また、逆にインタレース性が満たされるとき、補題Aより、$P^{e},P^{o}$の正の根が実軸上で隔離し、最も原点に近いのは$P^{e}$の根となる。$P^e$の正の根を昇順に$\omega^P_{e,i}$、同様に$P^o$の正の根を$\omega^P_{o,i}$と書くことにしよう、

0<\omega^P_{e,1}<\omega^P_{o,1}<\omega^P_{e,2}<\omega^P_{o,2}<...

となる。
$P^e,P^o$の根は原点対称なので、

P^e(\omega)=p_e\prod (\omega^2-(\omega^P_{e,i})^2)\\
P^o(\omega)=p_o\prod (\omega^2-(\omega^P_{o,i})^2)

ここで、すべての係数が正であり、次数がnである安定多項式$Q(s)=\sum q_is^i$を考える。
定理の前半より、$Q^e$は$[\frac{n}{2}]$個の正根を、 $Q^o$は$[\frac{n-1}{2}]$個の正根を持ち、相隔離する。
よって、以下のようにかけて、

Q^e(\omega)=q_e\prod(\omega^2-(\omega^q_{e,i})^2)\\
Q^o(\omega)=q_o\prod(\omega^2-(\omega^q_{o,i})^2)

となる。

ここで、多項式$P_\lambda(s)$

P_\lambda^e(\omega)=((1-\lambda)q_e+\lambda p_e)\prod^m_{i=1}(\omega^2-((1-\lambda)(\omega^q_{e,i})^2)+\lambda((\omega^p_{e,i})^2))\\
P_\lambda^o(\omega)=((1-\lambda)q_o+\lambda p_o)\prod^{m-1}_{i=1}(\omega^2-((1-\lambda)(\omega^q_{o,i})^2)+\lambda((\omega^p_{o,i})^2))

明らかに、$P_\lambda$の各係数は[0:1]で連続で、

P_0 = Q\\
P_1=P

である。

$P$が安定でないとすれば、境界横断定理(boundary crossing theorem)より、
$(0:1]$の範囲のどこかで、$P_\lambda$が虚軸上に根を持つような$\lambda$が存在する。
しかし、$P_\lambda$が虚軸上に根を持つことと、$P_\lambda^e,P^o_\lambda$が共通の実根を持つことは同値だが、

(\omega^\lambda_{e,i})^2=(1-\lambda)(\omega^q_{e,i})^2+\lambda (\omega^p_{e,i})^2\\
(\omega^\lambda_{o,i})^2=(1-\lambda)(\omega^q_{o,i})^2+\lambda (\omega^p_{o,i})^2

であることと、

0<\omega^P_{e,1}<\omega^P_{o,1}<\omega^P_{e,2}<\omega^P_{o,2}<...

より、$1-\lambda,\lambda\geq 0$に注意すれば、

\omega^\lambda_{o,i}<\omega^\lambda_{o,j}

となるから、共通の根は持つことができない。
よって、背理的に証明された。

Kharitonov の定理

$\delta_i:=[x_i,y_i]$として、
$P:=\{p|p(z)=\sum a_iz^i,a_i\in \delta_i\}$と定義する。
また、$\delta := [\delta_i]$なる数列としよう。
さらに、$\Delta$を、$\delta$から導かれる超矩形としよう。
$p$は$P$に属する多項式を表す。
また、最高次係数は0にならないと仮定しよう。つまり、$0\not \in\delta_n$とする。
$P$は実区間多項式族(real interval polynomial family)とよばれ、Kharitonov の定理はこれが安定であることを簡単に判定する。

定理：
$P$のすべての要素が安定であることは、以下の４多項式が全て安定であることと同値。

K^1(s):=x_0+x_1s+y_2s^2+y_3s^3+...\\
K^2(s):=x_0+y_1s+y_2s^2+x_3s^3+...\\
K^3(s):=y_0+x_1s+x_2s^2+y_3s^3+...\\
K^4(s):=y_0+y_1s+x_2s^2+x_3s^3+...\\

この証明のために補題を導入する

補題5.1

同じ偶数次項と異なる奇数次項をもつ２つの多項式を

P_1(s)=P^{even}(s)+P_1^{odd}(s)\\
P_2(s)=P^{even}(s)+P_2^{odd}(s)

とし、かつ$\omega \in [0,\infty]$に対して

P_1^o(\omega)\leq P_2^o(\omega)(5.4)

が成り立つとする。このとき、$\omega \in [0,\infty]$に対して

P_1^o(\omega)\leq P^o(\omega)\leq P_2^o(\omega)

となるならば、任意の$P^{odd}$に対して$P=P^{even}+O^{odd}$は安定。
また、奇数次項が等しく偶数次項が異なるような$p_1,P_2$に対しても同様にである。

　証明

$P_1,P_2$は安定なので、共通の$P^e$に対してインターレース性を持つ。
特に、$P_1^o,P_2^o$の次数が異なっていても、ともに$P^e$の最高次係数と同符号の最高次係数をもっていることに注意しよう。従って、$P^o$の最高次係数も同符号でなければ条件式を満たせない。
さらに、(5.4)によって、$P^o$は$P^e$に対してインタレース性をもつので、定理1.7より、$P$は安定。

ただし、補題5.1は、第２章で述べられたVertex Lemmaの特殊な場合にすぎない。

本題の証明

上で示した$K_1,K_2,K_3,K_4$は以下に示す4つの式で構成できる。

K^{even}_{min}(s):=y_0+x_2s^2+y_4s^4+...\\
K^{even}_{max}(s):=x_0+y_2s^2+x_4s^4+...\\
K^{odd}_{min}(s):=y_1s+x_3s^3+y_5s^5+...\\
K^{odd}_{max}(s):=x_1s+y_3s^3+x_5s^5+...\\

$p=p^{even}+p^{odd}$として、非負の$\omega$に対して

K^e_{min}(w)\leq p^e(w)\leq K^e_{max}(w)\\
K^o_{min}(w)\leq p^o(w)\leq K^o_{max}(w)

は明らか。従って、

R(\omega):=\left\{(a+bi)|K^e_{min}(w)\leq a\leq K^e_{max}(w),K^o_{min}(w)\leq b\leq K^o_{max}(w)\right\}

として矩形を定義すれば、$0\leq\omega$で

p(\omega)\in R(\omega)

となる。

さて、$P$が安定であれば、$K^1,,,K^4\in P$より、これらも安定であるのは明らか。
逆に、$K^1,,,K^4$が安定だとしよう。

K^1=K^{even}_{min}+K^{odd}_{min}\\
K^2=K^{even}_{min}+K^{odd}_{max}\\
K^3=K^{even}_{max}+K^{odd}_{min}\\
K^4=K^{even}_{max}+K^{odd}_{max}

であることを思い出し、$K^1,K^2$より補題5.1によって、

K^{even}_{min}+p^{odd}

は安定。同様に$K^3,K^4$より、$K^{even}_{max}+p^{odd}$も安定。
この２式より、$p^{even}+p^{odd}$も安定となる。

おまけ

$p$のインタレース性は、$f=p^e,f_1=p^o$に対して、生成した互除列が

V(0)-V(\infty)=-[n/2]

となり、かつ$p^e(0)p^o(0)>0$となることと同値。

略証：
$p^e,p^o$がインタレース性を持つとしよう。
$f=p^e,f_1=p^o$とすれば、$deg(p^e)\geq deg(p^o)$より互除列が生成できる。
$p^e$は相異なる正の根を$[n/2]$個持つので、$|V(0)-V(\infty)|\leq [n/2]$となる。
$p^e,p^o$の根は隔離するので、$p^e(0),p^o(0)>0$に注意すれば、$V(0)-V(\infty)=-[n/2]$となる。

逆に、$V(0)-V(\infty)=-[n/2]$であるとすれば、$p^e$の根は高々$[n/2]$しかないので、これらは相異なる。また、すべての根$\omega$で、$\chi(\omega)=-1$でなければならず、重根が存在しないことを考えれば、$p^e$の隣り合う根の間で$p^o$の符号が変化しているので、その間に$p^o$の根が必ず存在する。
一方で、$p^e$の根は$[n/2]$個なので、その隣り合う項の間に$p^o$の根があるとすれば、最低でも$[n/2]$個の根が必要になるので、$p^o$の根は$p^e$の根の間に1つずつしか存在し得ない。

真面目な証明：
(=>)$p^e,p^o$がインタレース性を持つとすれば、$P^{e},P^{o}$の根はすべて相異なり、正の根が実軸上で隔離し、最も原点に近いのは$P^{e}$の根である。
$P^e$の$[n/2]$個の正の根を$\omega_i$と書こう。
$V(0)-V(\infty)=\sum \chi(\omega_i)$であり、

\sigma(\omega)=\frac{P^e(\omega)}{P^o(\omega)}

と書くならば、

\chi(\omega_i)=\begin{cases}
    0 & (\sigma(\omega_i-\epsilon)\sigma(\omega_i+\epsilon)>0) \\
    1 & (\sigma(\omega_i-\epsilon)<0,\sigma(\omega_i+\epsilon)>0)\\
    -1 & (\sigma(\omega_i-\epsilon)>0,\sigma(\omega_i+\epsilon)<0)\\
  \end{cases}

となることを思い出そう。(A)
さて、$p$の係数が全て正だとしても一般性を失わない。
そうであれば、明らかに$P^e(0)>0,P^o(0)>0$となる。
$\omega_i$より小さな$P^o$の正の根は存在しないので、$P^o(\omega_1)>0$であり、$P^e$は$\omega_1$を通過すると符号が正から負に変化する。
従って$\chi(\omega_1)=-1$である。
同様に$\omega_2$では$P^e$の符号は逆に負から正に変化するが、$P^e,P^o$の根が隔離していることから、$P^o(\omega_2)<0$となり符号が交代する。従って$\chi(\omega_2)=-1$であり、以下同様に全て$\chi(\omega_i)=-1$となるので、$V(0)-V(\infty)=-[n/2]$である。
(<=)
$V(0)-V(\infty)=-[n/2]$かつ$P^e(0)P^o(0)>0$であるとしよう。
$V(0)-V(\infty)=\sum \chi(\omega_i)$と(A)より、これは$P^e$が重根を持たず、かつ

\forall i,\chi(\omega_i)=-1

であることと同値。

$P^e$は$\omega_i$を通過するとき、単根を通過するので符号が変化する。
このとき$\chi(\omega_i)=-1$であるためには、$\omega_i$の直前で$P^o$が$P^e$と同符号であればよい。
$\omega_1$の直前で$P^o$が$P^e$と同符号であるためには、$P^e(0),P^o(0)$が同符号であることを考えると、$(0,\omega_1)$の中に$P^o$の根が偶数個存在する。この個数を$\kappa_0$と書こう。
同様に、$\omega_i$を通過するたびに$P^e$の符号が変化することに注意すれば、$\chi(\omega_i)=-1$であるためには$[\omega_i,\omega_{i+1}]$の中に$P^o$の根は奇数個存在するのでこの個数を$\kappa_i$と書こう。$\kappa_i\geq1$に注意。
ところで、

\sum_{i=1}^{[n/2]-1}\kappa_i \geq [n/2]-1

だから、$P^o$は高々$[\frac{n-1}{2}]$個の根を持つことを考えれば、
$[\frac{n-1}{2}]=[n/2]-1$のとき**($\alpha$)**、

\sum_{i=1}^{[n/2]-1}\kappa_i = [n/2]-1

従って、$\kappa_i=1\ (i=1,2,3,,,[n/2])$で$\kappa_0=0$。
$[\frac{n-1}{2}]=[n/2]$のとき**($\beta$)**、
$\kappa_i$は2づつ跳ぶ離散値しか取れないので、

\sum_{i=1}^{[n/2]-1}\kappa_i = [n/2]-1

となり、のこりの根はひとつしかないので$\kappa_0=0$とならざるをえず、残りの根は$(\omega_{[n/2]},\infty)$にしか存在し得ない。

結局どちらの場合でも補題Aよりインタレース性が導かれる。よって示された。