abstract

卒論をちゃんとまとめる前に概論をまとめる。
内容は理論の概説であり、深い証明には立ち入らない。
これを元になにかして、論文にする。

introduction

研究室での講義内容は大別して３つ

1. sturmの定理による、任意の単純閉曲線内に与えられた多項式の根の個数を判定するアルゴリズムとその実装（教科書のやつ）
2. schur-cohn：上と同じことをする別のアルゴリズム。
3. kharitonovの定理：多項式の係数が範囲として含まれるとき、その範囲内のすべての多項式が安定？か確認する方法。

このドキュメントでは1と2の概説をまとめる。3は分割した。

@略は証明を略している。

いくつかの定義

以降、特に注意しなければ以下の意味である。
$P$:あるn次多項式
$C$:ある単純閉曲線
根の個数を数えるときは重複度も考慮する。

Cの中にPの根がいくつあるのか？

求めたいもの：(根の重複度も含めた)個数

Cの内部にある根の個数とPの偏角の関係

代数学の基本定理によって、$P$には根が$n$個存在する。@略
それらの根を$\{r_i\}$と呼べば、$P$は一次式の積に分解され、@略

P=\prod (x-r_i)

となる。$r_1...r_k$は$C$の内部にあり、$C$上にはどの$r_i$も存在しないとしよう。
$z$が$C$上を正の向きに一周するとき、$P(z)$の偏角の変化を考えれば、

arg(P(z))=\sum arg(z-r_i)

であり、

arg(z-r_i)=\begin{cases}
    2\pi & (i\leq k) \\
    0 & (otherwise)
  \end{cases}

は明らか。@略
したがって、$P$の偏角は$2\pi k$増加する。

Pの偏角の増加を数える方法

$P$は$C$上に根を持たないとしよう。
$z$が$C$上を動くとき、$P(z)$は虚軸を偶数回横切る。(つまり、$P(z)$の実部の符号が変化する)@略
２回横切るごとに始点に直線で戻るとすれば、$C$を虚軸を２回だけ横切るいくつかの単純閉曲線$C_i$に分割できる。
横切った２点は原点ではないので、$Re(P(z))Im(P(z))$の符号が存在し、必ず変化している。@略
$z$が$C_i$を一周するとき、$P(z)$の偏角の変化量は、$Re(P(z))Im(P(z))$の変化が正から負の場合と逆の場合を考えると、

• ２回とも正から負:$2\pi$
• 一度づつ:$0$
• ２回とも負から正:$-2\pi$

となる@略
$C$全体での偏角の変化はこの総和である。

Cが有理曲線なら

前項の総和をsturmの定理により計算できる場合がある。@略
$z=z(t)$とおけば、ある実多項式$\Phi,\Psi$と多項式$\Theta$があって

P(z(t))=\frac{\Phi(t)+i\Psi(t)}{\Theta(t)}

だから、

arg(P(z(t)))=arg(\Phi(t)+i\Psi(t))-arg(\Theta(t))

となって、$arg(\Theta(t))$が明らかなら、$f=\Phi(z),f_1=\Psi(z)$としてsturmの定理に帰着する。

応用

前項より、$C$を矩形としてもsturmの定理によって計算可能であり、@略
特定矩形領域を小矩形に分割し再帰的に適用することで、それぞれの根の位置を特定できる。
この実装はmathematicaにより行った。

schur-cohnのアルゴリズム

$z_0$をある複素数、$\rho >0$として、$D$は$z_0$の$\rho$閉近傍としよう。

• Dの内部にいくつ根があるか？

という問題を解く。

明らかに$D$の内部の根は、

q(z):=P(z_0+\rho z),|z|\le 1

の根と等しい。

$P$は、

P(z)=\sum_{i=0}^{n} b_i(z-z_0)^i

とテイラー展開されるので、

q(z)=\sum_{i=0}^{n} b_i(\rho z)^i

となる。したがって、Dを単位円としても等価であるとわかる。

相反多項式

さて、$P(z):=\sum a_i z^i$の相反多項式を以下のように定義する

P^*(z):=\sum \overline{a_{n-i}}z^i

(係数の順が逆になり共役になってる)
$P$が実際に$n$次以下なら、足りない根は$\infty$と考えよう。

常に、

P^*(z):=z^n\overline{P(1/\overline{z})} 

となる6.8-3(ただし$z\neq0$)@自明

$|z|=1$なら、$\overline{z}=\frac{1}{z}$だから、
$|P(z)|=|P^*(z)|$となる。
また

したがって、一般に、(lemma6.8a)
$P$の根を$w_i$とすると、$P^*$の根は$(\overline{w_i})^{-1}$である。@略

Schur変換

さて、$n$次多項式$p:=\sum a_kz^k$に対して、$n-1$次多項式を返す演算子$T$を定義しよう。

Tp:=\overline{a_0}p-a_np^*

を定義しよう。

Tp(z)=\sum_{k=0}^{n-1} (\overline{a_0}a_k-a_n\overline{a_{n-k}})z^k

は明らか。これを$P$のSchur変換と呼ぶ。
0多項式のSchur変換は0多項式である。
この変換はpだけでなく、pをの次数をいくつと見るかにも依存することに注意せよ。

Tp(0)=\overline{a_0}a_0-a_n\overline{a_n}=|a_0|^2-|a_n|^2

は常に実数である。
便宜上

T^kp:=T(T^{k-1}p)

と書こう。$T^0p:=p$である。
さらに、

\gamma_k:=T^kp(0)

と略記する。

定理6.8

0多項式でない多項式Pのすべての根が閉単位円外にあることは次と同値。

\forall k, \gamma_k>0

証：
閉単位円を$D$と呼ぼう。$p$は$n$次である、

(=>) $T^kp(z)=\sum_{i=0}^{n-k} a_i^{(k)}z^i$が$D$内に根を持たないと仮定すれば、vieta's formula(解と係数の関係のやつ)に従い、根を$x_k$と書いて、

```math
\Pi x_k = (-1)^n \frac{a^{(k)}_0}{a^{(k)}_{n-k}}

となり、左辺の絶対値は明らかに１より大きいので、

\left|\frac{a^{(k)}_0}{a^{(k)}_{n-k}}\right|>1

よって、

\left|a^{(k)}_0\right|>\left|a^{(k)}_{n-k}\right|

定義より、$\gamma_k>0$
ここで、$z$が単位円内を動くなら、$|z|=1$であり、$\left| T^kp(z)\right|=\left| (T^kp)^*(z)\right|$となるので、
6.8-3より、

\left|\overline{a^{(k)}_0}T^kp(z)\right|>\left|a^{(k)}_{n-k}(T^kp)^*(z)\right|

となる。左辺は仮定より根をD内に持たず、
教科書p.55 Roucheの定理より、

\overline{a^{(k)}_0}T^kp(z)-a^{(k)}_{n-k}(T^kp)^*(z)=T^{k+1}p(z)

も$D$内には根を持たない。
従って$p=T^0p$が$D$内に根を持たなければ、任意の$T^kp$もそうであり、$\gamma_k>0$となる。

(<=)$\forall \gamma_k>0$と仮定しよう。これは明らかに、

\left|a^{(k)}_0\right|>\left|a^{(k)}_{n-k}\right|

と同値。先と同様に、$T^kp$と$T^{k+1}p$は$D$内に同数の根を持つ。
一方、$T^np=\gamma_n$なので$D$内に根を持たず、従って$p=T^0p$も同じである。 Q.E.D.

$\gamma_k$を計算することをschur-cohnアルゴリズムという。
これで$D$内に多項式が根を持つのか判定できる。

定理6.8c

先と同様に、$\forall k,\gamma_k\neq 0$として、$k=0,1,,,n$から$\gamma_k<0$となるものを取り出した部分列$k_j$を定義する。

このとき、$p$が$D$内に持つ根の個数$h(p)$は以下を満たす

h(p) = \sum (-1)^{j-1}(n+1-k_j)

証明：
前提として、単位円周上で$T^kp$は$0$にならないことに注意。
なぜなら、単位円周上の点$e^{i\theta}$である$T^kp$が0となるとき、当然その相反多項式も$0$となるので、$e^{i\theta}$は$T^{k+1}p$の零点でもあり、よって以降の$T^kp$すべての零点でもあるが、これは$T^np=\gamma_n$にも言えて$\gamma_n=0$となるが$\forall k,\gamma_k\neq 0$に矛盾するからである。

さて、$\gamma_{k+1}\neq 0$であれば、

\left|a_0^{(k)}\right|\neq \left|a_{n-k}^{(k)}\right|

であり、単位円上では

\left|T^kp(z)\right|=\left|(T^kp)^*(z)\right|

なので、$\overline{a_0^{(k)}}T^kp$と$a_{n-k}^{(k)}(T^kp)^*$の間に絶対値においてどちらかの不等号が成り立ちRocheの定理の条件を満たす。$\gamma_{k+1}>0$なら

h(T^{k+1}p)=h(T^kp)

となり、$\gamma_{k+1}<0$なら不等号が逆転し、

h(T^{k+1}p)=h((T^kp)^*)

となる。相反多項式の根は、元の多項式の根の共役逆数なので、$h((T^kp)^*)$は$T^kp$の$D$の外部にある根の数に等しい。つまり、この場合、

h(T^{k+1})=h((T^kp)^*)=n-k-h(T^kp)

と書ける。
まとめると、

h(T^{k-1}p)=\begin{cases}
    h(T^kp) & (\gamma_k>0) \\
    n+1-k-h(T^kp) & (\gamma_k<0)
  \end{cases}

よって、$h(T^np)=0$に注意すれば、$h(p)$から再帰的に辿って結論を得る。

少し簡略化した書き方ができる。

\sum^{m} (-1)^{j-1}(n+1-k_j)
\\=\sum^{m} (-1)^{j-1}(n+1)+\sum^{m} (-1)^jk_j
\\=\begin{cases}
    \sum^{m} (-1)^jk_j & (m\ is\ even) \\
    n+1+\sum^{m} (-1)^jk_j & (m\ is\ odd)
  \end{cases}

また、$\pi_k:=\Pi^k_{i=1}\gamma_i$とすると、数列$\pi_k$の負項の数は、普通に数えて

(k_2-k_1)+...+\begin{cases}
    k_m-k_{m-1} & (m\ is\ even) \\
    n+1-k_m & (m\ is\ odd)
  \end{cases}

となるが、明らかに$h$の式と全く等価である。
また、

\epsilon_k:=\gamma_k \gamma_{k-2} \gamma_{k-4}...

と定義すれば、$\pi_k = \epsilon_k\epsilon_{k-1}$となるので、数列$\pi_k$の負項の数は数列$\epsilon_k$の符号変化回数に一致する。すなわち、$h$は符号変化を数えているともいえる。

この定理によって、単位円内にある根の数を数えられる。
この定理は、$\gamma_k$が全て非ゼロであることが前提なのでそうでなければ使えない。
その状況は、pが単位円周上の根を持つ場合だけでなく、一般に、ある$T^kp$が自己相反となるときにも起きる。また、任意の$\gamma_k$は$p$の係数のみの行列式で表現可能である。@略