数理解析研究所講究録
第 848 巻 1993 年 120-131120

幾何学的手法による Newton 写像の収束鉢の幅の評価
上智大学大学院理工学研究科数学専攻
上智大学理工学部数学科

藤付雅代
西沢清子

(Masayo FUJIMURA)(Kiyoko NISHIZAWA)

Newton 法は、方程式の根の近似を求める有効なアルゴリズムである。 ここでは多項式の Newton 写像の性質を複素力学系の立場で考察する。
Newton 写像において、根の直接鉢の無限遠点に伸びる各水路の幅の評価はすでにえられた [NF92][NF]。しかし、各水路の幅に対する次数のみによる下限は存在しない。すな
わち、 いくらでも細い水路を持つ直接鉢が存在する。

よって、今回は直接鉢の幅の定義をしなおす必要が生じた。直接鉢の幅を評価するときに、 このような細い水路ではなく、 ほかの太い水路でするのが自然である。
ここでは、 3 次多項式について、 その方法を述べる。
最後に、多項式の次数のみで、直接鉢の幅を評価する Manning [Man86] の方法を紹介する。

1. 諸定義多項式 $p(z)$ の Newton 写像 (Newton maP) を$N(z)=z- \frac{p(z)}{p(z)}$によって定める。
は (super-)attracting fixed point にの根において、多項式 の Newton 写豫なる。 錦の iteration により根に収束するような点の集合$N_{p}$$P$$p$$\alpha$$\alpha$$\{z\in C|N_{p}^{n}arrow\alpha, narrow\infty\}$の収束鉢 (attracting basin) という。 また、 attracting basin のうち結成分を直接鉢 (immediate basin) といいと書く。
Newton 写像には、次のような性質がある。
を根$\alpha$$\alpha$を含む連$B(\alpha)$は単連結である。 ([Prz89])$\bullet$$B(\alpha)$$\bullet$$\infty$$\bullet$$N|_{B(\alpha)}$は $p(z)$ の各根の直接鉢の境界上にある。 ([Fat20])の局所次数が $sk$ らば、([Prz89])$B(\alpha)$は。
。に伸びる $s-1$ 個の水路をもつ。

121
2. Misiurewicz point
21. 細い水路をもつ直接鉢の直接鉢の境界と、 それの吸引鉢の境界が交わることがあるか ? と
この節では、根いうことを考える。視覚的な面から簡単にいえぱ、 「直接鉢に、 自分と同じ色のコブがつくか ? 」 ということである。 もしこのようなことが生じれば、にのびるいくらでも細$\alpha$$\infty$

い水路をもつ直接鉢がえられる。 従って、 直接鉢の水路の幅を、 多項式の次数のみで下から評価することは出来ない。
ここでの直接鉢の水路の幅とは ‘ 原点を中心とする半径 $R$ の円上に中心を持ち根 の直接鉢にすっぽりはいるような円の直径のことをさすことにする。 (Fig. 1 参照)$\alpha$

直接鉢が \infty 。にのびるいくつかの水路をもつとき、最も幅の広い水路の幅を、定義 1直接鉢の幅と定義する。
このとき、 多項式の次数のみで、 直接鉢の幅を下から評価することが出来ないだろうか$\circ$Fig. 1. width of a channel$B(\alpha)$

以下では 3 次多項式に話を限る。共役性により次の Thurston model を用いて一般性を失わない。
$\{p_{\lambda}(z)=(z-1)(z+\frac{1}{2}+\lambda)(z+\frac{1}{2}-\lambda)\}$$\{p_{\lambda}\}$に対する Newton 写像族は次のようになる。
$\{N_{p_{\lambda}}(z)=\frac{2z^{3}+\lambda^{2}-\frac{1}{4}}{3z^{2}-(\lambda^{2}+\frac{3}{4})}\}$

ここで Aを、A:$[- \frac{1}{2},$$\frac{1}{2}]\cup\{-\frac{1}{2}+e^{i\theta}$;$0 \leq\theta\leq\frac{\pi}{3}\}\cup\{\frac{1}{2}+e^{i\theta}$;$\frac{2\tau}{3}\leq\theta\leq\pi\}$のようにすれば、 A は、 この 3 次 Newton 写豫のパラメータ平面の基本領域である [Tan]。

すなわち任意の$N_{p}$にたいして、共役となる$N_{p_{\lambda}},$$\lambda\in\Lambda$が存在する。 (Fig. 2 参照)

122

Fig. 2.

Parameter plane of Thurston modelに共通にThurston model では族
critical point である o その critical$\{N_{p_{\lambda}}\}_{\lambda}$$\infty$

はいつでも反発的不動点であり、$value-\frac{\lambda^{2}-1/4}{\lambda^{2}+3/4}$$0,$

は freeの存在範囲は境界は $x^{2}-y^{2}> \frac{1}{2}(x>$$z=x+iy$ ) である。
ここで $0$ が前周期点になるようなパラメータ$\lambda$$0$と$0arrow N_{p_{\lambda}}(0)arrow N_{p\lambda}(N_{p\lambda}(0))arrow\infty$となる$\lambda$

たとえぼ、 $0arrow N_{p_{\lambda}}(0)arrow\infty$ となるを数式処理システム MACSYMA で求め、$\lambda$

ると次のような答えを得る。
$0arrow N_{p_{\lambda}}(O)arrow\infty$について$\lambda=\{\begin{array}{l}0\pm 0.2686733i\pm(1.05190170\pm 0.8339091i)\end{array}$$0arrow N_{p_{\lambda}}(O)arrow N_{p_{\lambda}}(N_{p_{\lambda}}(0))arrow\infty$について$\lambda=\{\begin{array}{l}0\pm 0.12156018i0\pm 0.30070562i0\pm 0.44270458i\pm(0.62110802\pm 0.9926393i)\pm(1.38840381\pm 0.4590628i)\pm(0.968757l6\pm 0.8833270i)\end{array}$

このパラメータに対するの鉢の様子は Fig. 3 のようになり、 直接鉢に、吸引鉢がついている様子がみられる。
方程式の根 は、 いわゆる Misiurewicz point である。 この点において、 2 次多項式族$\{z^{2}+c\}$ 。と同じように、 この値を中心にしたパラメータ平面は、くり込みに対して自己$N_{p}$$\lambda$

123Fig. 3.

Same colored lumps stick to the inmediate basin

相似であることが観察される。 同様に、

$N_{p_{\lambda}}(0)$を中心にしたダイナミカル平面でも同じことがおこる。

2 次写像族では Misiurewicz point で他者相似性があることが知られている [Tan85]。
Thurston model でも Misiurewicz point で Tan Lei [Tan85] の意味で (Hausdorff distance) 他者相似性が観測される。 (Fig.
Fig. 5 参照。)
こののとするとを少し摂動させてfree critical point が直接鉢の中に入ってしたがって直接鉢はに延びる新たな細い水路ができる。に延びる 2 本の水路を持つ。
$4$、$\lambda$$\tau$$N_{p_{r}}$$\infty$$\infty$$\tau$の取り方によってこの水路の幅はいくらでも小さくすることができる。すなわち、前節に近づくような例をつくることができるのである。 (Fig. 6 参の鉢の幅がいくらでも照。)$0$

このように 2 本以上の水路がある場合には、 \infty 。の近傍で直接鉢のセクターを取るときに太い方を取ることは自然である。 直接鉢の水路の幅は、 free critical point のある場所によって決まるのではないかと考えられる。

3. Width of basin次多項式として centered な多項式について考える。任意の多項式はこのような多項式と共役になるので、 Newton 法を研究するときにはに属するcentered な多項式のみを考えれば十分である。
ここでは、

$d$

$\mathcal{P}_{d}(1)$$\mathcal{P}_{d}(1)$3.1. 直接鉢の水路の幅り、 項式のManning $[Man86]$ Sutherland [Sut90] おの結
Newton およびの結果より、多項式の、$x\sigma^{\vee}[NF93]$$\ovalbox{\tt\small REJECT} X$$^{\mathscr{J}}$t24

Fig. 4.

“Misiurewicz point” ofFig. 5.

“Misiurewicz point” of$N_{p}$: Parameter plane$N_{p}$: Dynamical plane

125

Fig. 6.

Immediate basin with a narrow channel

写像の直接鉢の水路の幅の下からの評価が得られている。
Newton 写豫に対して、根 の直接鉢は単連結であることが知られている
よって、 Riemann の写像定理より単位円板からをに移すような解析的微分同相写豫がある。 これを用いて、とブラシュケ積 $M$ を共役にすることがで$B(\alpha)$$\alpha$$[Prz89]_{\circ}$$D$$B(\alpha)$

へ$0$$\alpha$$N|_{B(\alpha)}$き6$[Bur79]_{0}$$arrow^{N|_{B(\alpha)}}$$B_{h\uparrow}(\alpha)$$B(\alpha_{h})\uparrow$

$D$

$D$
$arrow^{M}$$M(z)=ze^{i\theta} \prod_{j=1}^{s}\frac{z-\mu_{j}}{1-\overline{\mu}_{j^{Z}}}$$M(z)$ は$0$つ。特に$\alpha$を吸引的不動点として持ち、単位円上のを反発的不動点として持が free critical point を含まないとき、 $M(z)=z^{2}$ になる。
が単根で定理 1 $([NF93])$$\xi_{1},$$\cdots,$$\xi_{s}$$B(\alpha)$

を $M(z)$ の不動点とするとき、 $B(\alpha)$ は, すくなくとも、 中心が$t_{\xi}\in B(\alpha),$ $(|t_{\xi}|=R>2(d+1)/(d-1))$, で半径$\xi$$\frac{(R-2)}{3d(1+\sqrt{(M(\xi))})}$の円を含む。

126
3.2. Blashke Product の性質
定理 2 (Lucas test for Blashke product),$M(z)=ze^{i\theta} \prod_{j=1}^{s}\frac{z-\mu_{j}}{1-\overline{\mu}j^{Z}}$のとき $M(z)$ の単位円内のすべての critical poin は根の convex hull$t$$\langle\{\mu_{j}\}\rangle$に含まれている。

証明$M’(z)=e^{i\theta} \prod_{j=1}^{s}\frac{z-\mu j}{1-\overline{\mu}j^{Z}}+ze^{i\theta}\sum_{k=1}^{s}\frac{1-|\mu_{k}|^{2}}{(1-\overline{\mu}_{k}z)^{2}}\prod_{j\neq k}\frac{z-\mu j}{1-\overline{\mu}_{j^{Z}}}$$= \frac{1}{z}M(z)+M(z)\sum_{k=1}^{s}\frac{1-|\mu_{k}|^{2}1}{1-\overline{\mu}_{k}zz-\mu_{k}}$convex hull の外側の$M(\beta)\neq 0$$\beta$で、 $M’(\beta)=0$ になるものが存在したとする。

より

$(*)$

$\frac{1}{\beta}+\sum_{k=1}^{s}\frac{1-|\mu_{k}|^{2}1}{1-\overline{\mu}_{k}\beta\beta-\mu_{k}}=0$$\mu_{0}=0$

とおいて、$\sum_{k=0}^{s}\frac{1-|\mu_{k}|^{2}1}{1-\overline{\mu}_{k}\beta\beta-\mu_{k}}=0$$\frac{1-|\mu_{k}|^{2}1}{1-\overline{\mu}_{k}\beta\beta-\mu_{k}}=\frac{1-|\mu_{k}|^{2}1-\mu_{k}\overline{\beta}}{1-|\mu_{k}\beta|^{2}\beta-\mu_{k}}$ここで $|\beta|<1$なら$0<\underline{1-|\mu_{k}|^{2}}<1$$1-|\mu_{k}\beta|^{2}-$よって$\frac{1-\mu_{k}\overline{\beta}}{\beta-\mu_{k}}$の存在範囲を調べればよいが、 ここでその逆数$\frac{\beta-\mu_{k}}{1-\mu_{k}\overline{\beta}}$を考える。
$\beta$と convex hull を分離する単位円の直交円をとる。 それを$\frac{\beta-z}{1-\overline{\beta}z}$で写せば、 Fig. 7 のようになり、$\frac{\beta-\mu_{k}}{1-\mu_{k}\overline{\beta}}>0$

よって $(*)$ に矛盾。

1127

Fig. 7.
命題 1 (Blashke product の fixed point の eigenvalue の評価)
$M(z)=ze^{i\theta} \prod_{j=1}^{s}\frac{z-\mu_{j}}{1-\overline{\mu}j^{Z}}$のとき $M(z)$ の単位円上の不動点$\xi_{i},$$(i=0,1, \cdots, s)$ のeigenval ue は$M’( \xi_{i})=1+\sum_{k=1}^{s}\frac{1-|\mu_{k}|^{2}}{|\xi_{i}-\mu_{k}|^{2}}$で与えられる。

証明$\xi_{1},$$\cdots,$$\xi_{s}$が単位円上の不動点であることから$M( \xi_{i})=\xi_{i}e^{i\theta}\prod_{j=1}^{s}\frac{\xi_{i}-\mu_{j}}{1-\overline{\mu}_{j}\xi_{i}}=\xi_{i}$ここで$M’(z)=e^{1\theta} \prod_{j=1}^{s}\frac{z-\mu j}{1-\overline{\mu}j^{Z}}+ze^{i\theta}\sum_{k=1}^{\theta}\frac{1-\mu_{k}\overline{\mu}_{k}}{(1-\overline{\mu}_{k}z)^{2}}\prod_{j\neq k}\frac{z-\mu_{j}}{1-\overline{\mu}_{j}z}$

ゆえに$M’( \xi_{i})=1+\sum_{k=1}^{s}\xi_{\dot{t}}e^{i\theta}(\prod_{j=1}^{s}\frac{\xi_{i}-\mu_{j}}{1-\overline{\mu}j\xi_{i}})\frac{1-\mu_{k}\overline{\mu}_{k}1}{1-\overline{\mu}_{k}\xi_{i}\xi_{i}-\mu_{k}}$$=1+ \sum_{k=1}^{s}\xi_{i}\frac{1-|\mu_{k}|^{2}}{(1-\overline{\mu}_{k}\xi_{i})(\xi_{i}-\mu_{k})}$$\xi_{i}\overline{\xi}_{i}=1$

より$=1+ \sum_{k=1}^{s}\frac{1-|\mu_{k}|^{2}}{(\overline{\xi}_{i}-\overline{\mu}_{k})(\xi_{i}-\mu_{k})}$$=1+ \sum_{k=1}^{s}\frac{1-|\mu_{k}|^{2}}{|\xi_{i}-\mu_{k}|^{2}}$

128
ゆえに
$M’( \xi_{1})=1+\sum_{k=1}^{s}\frac{1-|\mu_{k}|^{2}}{|\xi_{i}-\mu_{k}|^{2}}$1$\xi_{i}$の方向でのセクターが大になるためには$M’(\xi_{i})$が小であることが必要である。すなが大でなければならない。
わち、
これにより、 各との距離が一番遠い を選べぱ、 そこでのセクターが最大であるこ$|1-\overline{\mu}_{j}\xi_{k}|^{2}$$\xi$$\mu_{i}$とがわかる。 Fig.

$8$、Fig. 9 参照。

3.3. 3 次方程式の直接鉢の幅
まず、 $p(z)$ の根$\alpha$が単根で、 その直接鉢に free critical point を 1 っ含むときを考える。

錦と共役なブラシュケ積は次のような形をしている。
$M(z)=z^{2} \frac{z-\mu}{1-\overline{\mu}z}$

この $M(z)$ の単位円上での不動点を計算すると、$\xi_{1}=ib+\sqrt{1-b^{2}},$となる。 そ$\dot{\text{こ}}$$\xi_{2}=ib-\sqrt{1-b^{2}}$,

ただし $\mu=a+ib$での固有値を計算すると$M’( \xi_{1})=2+\frac{1-a^{2}-b^{2}}{(\sqrt{1-b^{2}}-a)^{2}}$,$M’( \xi_{2})=2+\frac{1-a^{2}-b^{2}}{(-\sqrt{1-b^{2}}-a)^{2}}$ここで、 $a>0$ なら $3\geq M’(\xi_{1})>M’(\xi_{2})$に対する方が opening modulus が大きいことがとなる o また free critical point を含わかる。 この大きいほうの modulus の最小値はであである。すなわちまない直接鉢のセクターの opening modulus はしたがって、 セクターを考えるとき、$\xi_{2}$$\frac{\pi}{\log 3}$$\frac{\pi}{\log 3}<\frac{\pi}{\log 2}$$\frac{\pi}{\log 2}$

る。

定理 1 の $R$ として $R>3$ と取れる。
いま、 $R=3,$ $d=3,$ $M’(\xi)=3klarrow$ て、 $\frac{2}{9(1+\sqrt{3})}k’F$ る$\circ$にのびるいくつかの水路のうちで最も幅の広い水路の幅をもって、 その直接鉢の幅とすれば次の定理を得る。
$\infty$定理 33 つの相異なる根を持つ centered $g_{3}$ 次多項式を

心 $t,$ $|t|=3$ 上の直接鉢の幅は、$\frac{1}{9(2+\sqrt{3})}$である。

$P\in \mathcal{P}_{d}(1)$とすると き、 中

129Fig. 8.

Blashke product of

Fig. 9.

Blashke product of$M(z)=z^{2} \frac{z-\lambda}{\ovalbox{\tt\small REJECT}-\lambda z}\frac{z-p}{1-\overline{\mu}z}\lambda=0.6-0.8i,$$M(z)=z^{2} \frac{z-\lambda}{1-\lambda z}\frac{z-\mu}{1-\overline{\mu}z}\lambda=-6\mathfrak{s}\ovalbox{\tt\small REJECT}+0.75i,$$\mu=0.7+0.6i$$\mu=0.4+0.8i$

130
4. Manning のアルゴリズム$i$

次の結果は\mbox{\boldmath $\tau$} Manning による、多項式の次数のみによって決まる直接鉢の幅である。のをを次数 $d(>10)$ の centered な多項式とし、定理 ([Man86])$exp$ os $ed$ root とする。 このとき、$|t|\leq d,$が存在して、$|N^{-1}(t)|>d$ をみたす
は中心 t、半径$p(\in \mathcal{P}_{d}(1))$$\alpha$$p$$B(\alpha)$$t$$\frac{0.0738|t|}{d\log d}$の円板を含む。
これをもとにした ‘Manning のアルゴリズムを紹介する。

アルゴリズム$p(z)=z^{d}+a_{d-2}z^{d-2}+\cdots+a_{0}$,$d\geq 10,$$|a_{i}|\leq 1$$\epsilon>0$

Put$R=(19.2d\log d+2)\pi$
to $= \exp(\frac{2\pi i}{R})$$\rho=1-\text{う^{}\pi}$

Array

A

$=^{ef}\{\dot{\mu}d\omega^{k}$; $0 \leq j<-(\frac{R}{2\pi})\log(1-\frac{1}{d}-\frac{2}{d^{2}})+1,0\leq k<R\}$

各 $(j, k)$ に対し、 $w=N^{l}(p^{;}d\omega^{k}),$If $|w-N(w)|< \frac{\epsilon}{d}$ Then
Else 次の $(j, k)$ を計算。
このアルゴリズムから\mbox{\boldmath $\tau$}$w$$1 \leq l\leq d\log\frac{d^{3}}{\epsilon}$を計算が根である。

Neweton 法の計算回数としては、多くても$cd^{2}( \log d)^{2}\log(\frac{d^{3}}{\epsilon}I$となるような、 $c<800$ が存在する。

参考文献[Bur79] R. Burckel. An Introduction to Classical Complex Analysis, 1979. Academic Press,New York.

[Fat20]P. Fatou. Sur les Equations fonctionnelles. Bull. Soc. Math. France, 48:208-304, 1920.

[Man86] A. Manning. How to be Sure of Solving a Complex Polynomial using Newton’s Method,
1986. preprint, Math.Inst., Univ. Warwick.
[NF]

K. Nishizawa and M. Fujimura. Global Convergence Behavior of Newton’s Method. 数理解析研究所講究録 (京都大学), to appear.

131[NF92]

K. Nishizawa and M. Fujimura. Families of Rational Maps and Convergence Basins of
Newton’s Method. Proc. Japan Acad., 68(6), 1992.

[NF93]

K. Nishizawa and M. Fujimura. Families of Rational Maps and Geometruc Method inNewton Map. In Chaotic Dynamical Systems, S. Ushiki, editor, World Scientific Pub.,
1993. to appear.

[Prz89]F. Przytycki. Remarks on the Simple Connectedness of basins of Sinks for Iterations ofRational Maps. Dynamical Systems and Ergodic theory, PWN-Polish Scientific Pub.,pages 229-235, 1989.

[Sut90]S. Sutherland. Finding Roots of Complex Polynomials with Newton’s Method, 1990.
1990/7, SUNY Stony Brook.
Preprint
$\#$

[Tan]

L. Tan. Cubic Newton’s method of Thurston’s type. preprint.

[Tan85] L. Tan. Ressemblance entre l’Ensemble de Mandelbrot et l’Ensemble de Julia auVoisinage d’un Point de Misurewicz. In \’Etude Dynamique des Polyn\^omes Complexes,
A. Douady and J. H. Hubbard, editors, pages 139-154. Publications Mathematiquesd’Orsay, 1985.