重根を持つ 3 次多項式に対する Durand-Kerner 法の 大域収束性について

重根を持つ 3 ^{次多項式に対する} Durand-Kerner ^法の 大域収束性について

奥田昇

東京工業大学大学院理学院数学系 川平研究室修士課程二年

1 ^要旨

本論文では，複素一変数多項式に対する数値解法である

Durand-Kerner

Durand-Kerner

Newton

多項式

p

Newton

N p

z ∈ C

N p (z) = z − p ^′ (z) ^{− 1} p(z)

N p

を適当な初期値

z ∈ C

{ z , N _p (z) , N _p (N _p (z)) , . . . }

p

1

n

p(z) = ∏ _n

i = 1 (z − α i )

Durand-Kerner

F _p

F _p ( ζ ) B ζ −

( p( ζ i )

∏ _n

j = 1 j , i ( ζ i − ζ j ) ) n

i = 1

と定義され，

F _p

ζ ∈ C ⁿ

{ζ, F _p ( ζ ) , F _p (F _p ( ζ )) , . . . }

が

p

( α 1 , . . . , α n )

n

Newton

Durand-

Kerner

5

ように

Durand-Kerner

Newton

することが知られている．すなわち，

| z − α 1 |

z

{ z , N _p (z) , N _p (N _p (z)) , . . . }

α 1

|ζ − ( α 1 , . . . , α n ) |

ζ

{ζ, F _p ( ζ ) , F _p (F _p ( ζ )) , . . . }

( α 1 , . . . , α n )

一方，

Newton

N p

Durand-Kerner

F p

C

C ⁿ

z

ζ

p

α i

( α _τ (1) , . . . , α _τ (n) )

N _p

F _p

τ

7

Newton

Durand-Kerner

を持たない多項式の例は知られていない．したがって，

Durand-Kerner

「大域収束性」の有無は興味深い．

8

9

p

2

p(z) = z ³

Durand-Kerner

([1])

3

p

2

Durand-Kerner

F p

6

p(z) = ∑ _n

i=0 a _{n − i} z ⁱ

F _p ( ζ )

Dochev

H B {ζ ∈ C ⁿ |

∑ n

i = 1 ζ i = − a ₁ }

F _p

n

n − 1

2

F _p

1

p(z) = z ³

F _p

2

α ∈ C, ζ ∈ Dom(F _p )

F _p ( αζ ) = α F _p ( ζ ) . (1.1)

によってさらに

1

_p

1

1

p

2

p(z) = z ³

p

2

1

(1.1)

p

F _p

F _p

2 Durand-Kerner ^法の定義

この章では不動点，軌道などの用語と

Durand-Kerner

n ∈ N

定義

2.1. U ⊂ C ⁿ

F : U −→ C ⁿ

ζ ∈ U

F

F( ζ ) = ζ

ζ ∈ U

F ⁽⁰⁾ ( ζ ) B ζ

k ≥ 0

F ^(k) ( ζ ) ∈ U

F ^{(k + 1)} ( ζ ) B F(F ^(k) ( ζ ))

k ∈ N

F ^(k) ( ζ )

(F ^(k) ( ζ )) ^∞ _{k = 0}

ζ

F

定義

2.2. p

n > 1

a ₀ , . . . , a _n ∈ C, a ₀ = 1

z ∈ C

p(z) = ∑ n

i = 0 a _{n − i} z ⁱ

1 ≤ i < j ≤ n

ζ i , ζ j

であるような

ζ = ( ζ 1 , . . . , ζ n ) ∈ C ⁿ

F _p ( ζ ) B

(

ζ i − p( ζ i )

∏ _n

j = 1j , i ( ζ i − ζ j ) ) n

i = 1

(2.1)

F _p

p

Durand-Kerner

DK

Dom(F _p ) B {ζ = ( ζ 1 , . . . , ζ n ) ∈ C ⁿ | i , j

ζ i , ζ j }

α 1 , . . . , α n ∈ C, 0 ≤ i < j ≤ n

α i , α j , p(z) = ∏ _n

i = 1 (z − α i )

( α 1 , . . . , α n )

F _p

S _n B {τ : { 1 , . . . , n } −→ { 1 , . . . , n } | τ

}

とかき，

τ ∈ S _n

α τ B ( α τ(1) , . . . , α τ(n) )

α τ

F _p

図

1: 3

P(z) = z ³ − 1

( ζ ₁ ⁽⁰⁾ , ζ ₂ ⁽⁰⁾ , ζ ₃ ⁽⁰⁾ ) = (2e

^{π i} , 2e

^{π i} , 2e

^{π i} )

として

Durand-Kerner

MATLAB

成分，紫が第三成分を表す．

3 ^準備

この章では吸引的不動点や共役などの用語の定義をする．

[2]

6

n ∈ N

定義

3.1. U ⊂ C ⁿ

F : U −→ C ⁿ

Φ : U ∪ F(U) −→ Φ (U ∪ F(U)) ⊂ C ⁿ

F

Φ

G : Φ (U) −→ Φ (F(U))

ζ ∈ Φ (U)

G( ζ ) = Φ ◦ F ◦ Φ ^{− 1} ( ζ )

定義

3.2. U , V ⊂ C ⁿ

F : U −→ C ⁿ , G : V −→ C ⁿ

F

G

Φ : U ∪ F(U) −→ Φ (U ∪ F(U)) ⊂ C ⁿ

G

F

Φ

命題

3.3. U , V ⊂ C ⁿ

F : U −→ C ⁿ , G : V −→ C ⁿ

F

G

命題

3.4. U ⊂ C ⁿ

F : U −→ C ⁿ

Φ : U ∪ F(U) −→ Φ (U ∪ F(U )) ⊂ C ⁿ , F

Φ

G

(i) , (ii)

(i) ζ ∈ U

F

(ii) Φ ( ζ ) ∈ Φ (U )

G

定義

3.5. U ⊂ C ⁿ

α ∈ U

F : U −→ C ⁿ

α

F

F ^′ ( α )

1

α

F

α

{ζ ∈ C ⁿ | lim _k→∞ F ^(k) ( ζ ) = α}

命題

3.6. U ⊂ C ⁿ

α ∈ U

F : U −→ C ⁿ

D

α

0 < s < 1

0 < δ

(i)

(iii)

(i) |α − ζ| < δ

| F( ζ ) − α| < s |α − ζ|.

(ii) {ζ ∈ C ⁿ | |α − ζ| < δ} ⊂ D .

(iii) D

命題

3.7. U ⊂ C ⁿ

F : U −→ C ⁿ

Φ : U ∪ F(U) −→ Φ (U ∪ F(U)) ⊂ C ⁿ , F

Φ

G

(i),(ii)

(i) α

F

(ii) Φ ( α )

G

また，

α

F

(iii),(vi)

(iii) D

α

F

(vi) Φ (D)

Φ ( α )

G

4 Durand-Kerner ^{法の一般的な性質}

Duraand-Kerner

n ∈ N, p

n > 1

α 1 , . . . , α n ∈ C

z ∈ C

p(z) = ∏ _n

i = 1 (z − α i )

命題

4.1. τ ∈ S _n

Φ : C ⁿ −→ C ⁿ

Φ ( ζ 1 , . . . , ζ n ) B ( ζ _τ (1) , . . . , ζ _τ (n) )

ζ ∈ Dom(F p )

Φ ◦ F _p ◦ Φ ^{− 1} ( ζ ) = F _p ( ζ ) . (4.1) Proof.

Φ ◦ F _p ◦ Φ ^{− 1} ( ζ ) = Φ ◦ F _p ( ζ τ(1) , . . . , ζ τ(n) )

= Φ (

ζ _τ

(i) − p( ζ _τ

(i) )

∏ _n

j = 1 , j , i ( ζ _τ

(i) − ζ _τ

(j) ) ) n

i = 1

= (

ζ _τ

( τ (i)) − p( ζ _τ

( τ (i)) )

∏ _n

j = 1 , j , i ( ζ τ

(τ(i)) − ζ τ

(τ( j)) ) ) n

i = 1

= (

ζ i − p( ζ i )

∏ _n

j = 1 , j , i ( ζ i − ζ j ) ) n

i = 1

.

□

命題

4.2. α ∈ C

φ : C −→ C

φ (z) B z + α

Φ : C ⁿ −→ C ⁿ

Φ ( ζ ) B ( ζ i + α ) ⁿ _{i = 1}

ζ ∈ Dom(F _p )

Φ ◦ F _{p ◦φ} ◦ Φ ^{− 1} ( ζ ) = F _p ( ζ ) . (4.2) Proof.

Φ ◦ F _{p ◦φ} ◦ Φ ⁻¹ ( ζ ) = Φ (

ζ i − α − p ◦ φ ( ζ i − α )

∏ _n

j = 1 , j , i (( ζ i − α ) − ( ζ j − α )) ) n

i = 1

= (

ζ i − α − p ◦ φ ( ζ i − α )

∏ _n

j = 1 , j , i (( ζ i − α ) − ( ζ j − α )) + α ) n

i = 1

= (

ζ i − p( ζ i )

∏ n

j=1,j,i ( ζ i − ζ j ) ) n

i = 1

.

□

4.3. t ∈ C

q(z) = ∏ _n

i = 1 (z − t α i ),

T : C ⁿ −→ C ⁿ

T ( ζ ) B (t ζ i ) ⁿ _{i = 1}

ζ ∈ Dom(F _p )

T ◦ F p ◦ T ^{− 1} ( ζ ) = F q ( ζ ) . (4.3) Proof.

T ◦ F _p ◦ T ^{− 1} ( ζ ) = T (

t ^{− 1} ζ i − p(t ^{− 1} ζ i )

∏ _n

j = 1 , j , i (t ^{− 1} ζ i − t ^{− 1} ζ j ) ) n

i = 1

= (

ζ i − t p(t ⁻¹ ζ i )

∏ _n

j = 1 , j , i (t ^{− 1} ζ i − t ^{− 1} ζ j ) ) n

i = 1

= (

ζ i − t ∏ _n

i=1 (t ^{− 1} ζ i − α i ) (t ^{− (n − 1)} ∏ n

j=1, j,i ( ζ i − ζ j )) ) n

i = 1

= (

ζ i −

∏ n

i=1 ( ζ i − t α i )

∏ n

j = 1 , j , i ( ζ i − ζ j ) ) n

i=1

.

□

4.4. p

n ≥ 3

q(z) B ∏ _{n − 1}

i = 1 (z − α i )

Q : {ζ = ( ζ 1 , . . . , ζ n ) ∈ C ⁿ | ζ n = α n } −→ C ⁿ⁻¹

Q( ζ ) B ( ζ i ) ⁿ⁻¹ _{i = 1}

ζ ∈ Dom(F _q )

Q ◦ F _p ◦ Q ^{− 1} ( ζ ) = F _q ( ζ ) . (4.4) Proof.

Q ◦ F _p ◦ Q ^{− 1} ( ζ ) = Q ◦ F _p ( ζ 1 , . . . , ζ n − 1 , α n )

= Q (

ζ i − p( ζ i )

∏ _n

j = 1 , j , i ( ζ i − ζ j ) ) n

i = 1

_ζ

n

=α

= (

ζ i − p( ζ i )

∏ _n

j=1, j,i ( ζ i − ζ j ) ) n − 1

i = 1

_ζ

n

=α

=

 

 ζ i − q( ζ i )( ζ n − α n ) ( ζ n − α n ) ∏ n − 1

j=1,j,i ( ζ i − ζ j )

 



n − 1

i=1

=

 

 ζ i − q( ζ i )

∏ n − 1

j=1, j,i ( ζ i − ζ j )

 



n − 1

i=1

.

□

5 Durand-Kerner ^法と Newton ^法

多項式

p

Durand-Kerner

は

Duranad-Kerner

Newton

はこのことを見る．

n ∈ N

定義

5.1. U

C ⁿ

G : U −→ C ⁿ

G ^′ ( ζ )

ζ ∈ U

N _G ( ζ ) = ζ − G ^′ ( ζ ) ^{− 1} G( ζ )

と定め，

N _G

G

Newton

定理

5.2. U

C ⁿ

G : U −→ C ⁿ

β ∈ U

G( β ) = (0 , . . . , 0)

G ^′ ( β )

β

N _G

不動点であり，さらに

N _G

β

δ, c > 0

ζ ∈ U

|ζ − β| < δ

| N G ( ζ ) − β| ≤ c |ζ − β| ² . Proof.

n

m

A

|| A || B max {| A ξ| | ξ ∈ C ^m , |ξ| = 1 }

と定める．すると

det(G ^′ ( α )) , 0

|| G ^′ ( α ) || , 0

G ^′ ( ζ )

ζ

δ > 0

|ζ − α| < δ

δ

|| G ^′ ( ζ ) || > || G ^′ ( α ) ||

2 (5.1)

となる．そこで

|ζ − α| < δ

|α − ( ζ − G ^′ ( ζ ) ^{− 1} G( ζ )) | = | G ^′ ( ζ ) ^{− 1} (G ^′ ( ζ )( α − ζ ) + G( ζ )) |

≤ || G ^′ ( ζ ) ^{− 1} || | G ^′ ( ζ )( α − ζ ) + G( ζ ) | (5.2)

G = (G ₁ , . . . , G _n )

i ∈ { 1 , . . . , n }

G _i

ν = ( ν 1 , . . . , ν n ) ∈ ( N ∪ { 0 } ) ⁿ

|ν| B

∑ n k = 1

ν k

c _{i ,ν} B 1 ν 1 ! · · · ν n !

∂ G _i ( α )

∂ζ ₁ ^ν

· · · ∂ζ n ^ν

とかくと

G _i ( ζ ) = ∑

ν

,...,ν

≥ 0

c _i,ν ( ζ 1 − α 1 ) ^ν

· · · ( ζ n − α n ) ^ν

= G i ( α ) +

∑ n k = 1

∂ G _i ( α )

∂ζ k

( ζ k − α k ) + ∑

ν

,...,ν

≥ 0

|ν|> 1

c i ,ν ( ζ 1 − α 1 ) ^ν

· · · ( ζ n − α n ) ^ν

である．したがって

E( ζ ) = G ^′ ( α )( α − ζ ) + G( ζ )

E

α

c > 0

|ζ − α| < δ

| E( ζ ) | ≤ c |ζ − α| ² .

(5.2)

(5.1)

|α − ( ζ − G ^′ ( ζ ) ⁻¹ G( ζ )) | ≤ || G ^′ ( ζ ) ⁻¹ || | G ^′ ( ζ )( α − ζ ) + G( ζ ) |

≤ || G ^′ ( ζ ) ^{− 1} || c |ζ − α| ²

≤ 2c || G ^′ ( α ) ^{− 1} || |ζ − α| ² .

□

5.3 ([3]). p

n > 1

a ₀ , . . . , a _n ∈ C, a ₀ = 1

z ∈ C

p(z) = ∑ _n

i = 0 a _{n − i} z ⁱ

, l ∈ N, m ≤ l

φ m ( ζ 1 , . . . , ζ l ) B ∑

1 ≤ i

<···< i

≤ l

ζ i

· · · ζ i

(5.3)

とおき，

1 ≤ i ≤ n

f _i ( ζ ) B ( − 1) ⁱ φ i ( ζ 1 , . . . , ζ n ) − a _i (5.4)

G( ζ ) B ( f 1 ( ζ ) , . . . , f n ( ζ )) (5.5)

G ^′

G

( ∂ f _i /∂ζ j ) _{i j}

ζ ∈ Dom(F _p )

F _p ( ζ ) = ζ − G ^′ ( ζ ) ^{− 1} G( ζ ) = N _G ( ζ ) . (5.6) Proof.

G ^′ ( ζ ) ^{− 1} =

 

 −ζ _i ^{n− j} / ∏ ⁿ

k = 1 , k , i

( ζ i − ζ k )

 



i, j

(5.7)

(5.7)

(5.7)

G ^′ ( ζ ) ⁻¹ G( ζ ) =

 



∑ n

j=1 ( −ζ _i ^{n − j} f _j ( ζ ))

∏ _n

k = 1 , k , i ( ζ i − ζ k )

 



n

i = 1

である．第

i

∑ n j=1

( −ζ _i ^n−j f _j ( ζ )) =

∑ n j=1

( −ζ _i ^{n− j} ( − 1) ^j φ j ( ζ 1 , . . . , ζ n )) +

∑ n j=1

ζ _i ^n−j a _j

= −

∏ n j = 1

( ζ i − ζ j ) + p( ζ i )

= p( ζ i ) .

よって

G ^′ ( ζ ) ^{− 1} G( ζ ) =

( p( ζ i )

∏ n

k = 1 , k , i ( ζ i − ζ k ) ) n

i = 1

がいえた．

□

定理

5.4. p

n > 1

α 1 , . . . , α n ∈ C, p(z) = ∏ n

i = 1 (z − α i )

1 ≤ i < j ≤ n

α i , α j

τ ∈ S _n

α _τ B ( α _τ (1) , . . . , α _τ (n) )

δ, c > 0

ζ ∈ C ⁿ

|ζ − α τ | < δ

| F _p ( ζ ) − α τ | ≤ c |ζ − α τ | ²

Proof.

5.3

Newton

5.2

□

Durand-Kerner

系

5.5. p

n > 1

α 1 , . . . , α n ∈ C, p(z) = ∏ n

i = 1 (z − α i )

1 ≤ i < j ≤ n

α i , α j

τ ∈ S _n

δ > 0

ζ ∈ C ⁿ

|ζ − α τ | < δ

lim

k →∞ F ^(k) _p ( ζ ) = α τ .

6 Dochev ^平面

Durand-Kerner

F _p ( ζ )

Dochev

Durand-Kerner

Dom(F p )

Dochev

[3]

p

n > 1

a ₀ , . . . , a _n ∈ C, a _n = 1

z ∈ C

p(z) = ∑ n

i = 0 a _n−i z ⁱ

定理

6.1. ζ ∈ Dom(F p )

F p ( ζ ) = ( ζ ₁ ⁽¹⁾ , . . . , ζ n ⁽¹⁾ )

∑ n i = 1

ζ _i ⁽¹⁾ = − a 1 . (6.1)

Proof. G

5.3

5.3

F p ( ζ ) = ζ − G ^′ ( ζ ) ^{− 1} G( ζ )

G ^′ ( ζ )

G ^′ ( ζ )(F _p ( ζ ) − ζ ) = − G( ζ ) (6.2)

G

G

f ₁ ( ζ ) = − ∑ _n

i = 1 ζ i − a ₁

G ^′ ( ζ )

1

( ∂ f ₁ /∂ζ 1 , . . . , ∂ f ₁ /∂ζ n ) = ( − 1 , . . . , − 1)

(6.2)

∑ n

i = 1 ( − ( ζ _i ⁽¹⁾ − ζ i ))

(6.2)

∑ n i=1

( − ( ζ _i ⁽¹⁾ − ζ i )) = − f ₁ ( ζ )

=

∑ n i=1

ζ i + a ₁ .

□

定義

6.2.

H _p B  

 ζ ∈ C ⁿ

∑ n i = 1

ζ i = − a ₁  



とおき

H _p

F _p

Dochev

p

なとき，

p

H

系

6.3. ζ ∈ Dom(F p )

F _p ( ζ ) ∈ H _p .

7 ^{大域収束性}

大域収束性を定義し

Newton

[4]

定義

7.1. p

n > 1

α 1 , . . . , α n ∈ C, p(z) = ∏ _n

i = 1 (z − α i )

Newton

N _p

a.e. z ∈ C

j

lim k →∞ N ^(k) _p (z) = α j

Durand-Kerner

F p

a.e. ζ ∈ C ⁿ

τ ∈ S _n

lim _{k →∞} F ^(k) _p ( ζ ) = α _τ

Newton

定義

7.2. n ∈ N, U ⊂ C ⁿ

F : U −→ C ⁿ

k ∈ N

α ∈ U

F

k

F ^(k) ( α ) = α

0 ≤ j < k

j

F ^{( j)} ( α ) , α

α

F

k

{ F ⁽⁰⁾ ( α ) , . . . , F ^(k−1) ( α ) }

F

k

O = {α 0 , . . . , α k − 1 }

F

k

O

F

k

F ^(k)′ ( α j )

1

命題

7.3. n , k ∈ N, U ⊂ C ⁿ

O = { F ⁽⁰⁾ ( α ) , . . . , F ^(k−1) ( α ) }

F : U −→ C ⁿ

k

0 < s < 1

0 < δ

(i)

(ii)

(i)

j

| F ^{( j)} ( α ) − ζ| < δ

| F ^{( j + k)} ( ζ ) − α| ≤ s | F ^{( j)} ( ζ ) − α|.

(ii)

j

| F ^{( j)} ( α ) − ζ| < δ

lim

i→∞ F ^{( j + ik)} ( ζ ) = F ^(j) ( α ) .

例

7.4 ([4]). n = 1

p

p(z) = z ³ − 2z + 2

α 1 , α 2 , α 3

を

p

O ⊂ C

z ∈ O

z

p

Newton

(N ^(k) _p (z)) ^∞ _{k = 0}

α 1 , α 2 , α 3

Proof.

p(z) = z ³ − 2z + 2

Newton

f = N _p

f (z) = z − z ³ − 2z + 2 3z ² − 2

である．

f

f (0) = 1 , f (1) = 0

{ 0 , 1 }

f

{ 0 , 1 }

| f ^′ (0) f ^′ (1) | < 1

f ^′ (z) = (6z ⁴ − 12z ² + 12z) / (3z ² − 2) ²

f ^′ (0) = 0

f ^′ (0) f ^′ (1) = 0

{ 0 , 1 }

2

ことがいえた．

□

8 2 ^{次多項式に対する} Durand-Kerner ^{法の大域収束性}

定理

8.1. α 1 , α 2 ∈ C

p(z) = (z − α 1 )(z − α 2 )

a . e . ζ ∈ C ²

τ ∈ S ₂

n lim →∞ F ⁽ⁿ⁾ _p ( ζ ) = ( α τ (1) , α τ (2) ) . Proof. (1) α 1 = α 2

q(z) = z ² , Φ ( ζ ) B ( ζ 1 + α 1 , ζ 2 + α 1 )

4.2

ζ ∈ Dom(F _p )

Φ ◦ F q ◦ Φ ^{− 1} ( ζ ) = F p ( ζ ) .

よって

F _p

F _q

p(z) = z ²

α 1 = α 2 = 0

p

Durand-Kerner

F _p

F p ( ζ ) = ζ − ( ζ ₁ ²

ζ 1 − ζ 2

, ζ ₂ ² ζ 2 − ζ 1

)

であり

Dochev

H = {ζ ∈ C ² | ζ 1 + ζ 2 = 0 }

である．いま

F _p

H

F _H B F _p | H

( ζ 1 , −ζ 1 ) ∈ Dom(F _H )

F _H ( ζ 1 , −ζ 1 ) = 2 ^{− 1} ζ 1 (1 , − 1) .

そこで

P : H −→ C, P( ζ 1 , −ζ 1 ) = ζ 1

F _H

G B P ◦ F _H ◦ P ^{− 1}

z ∈ C − { 0 }

G(z) = 2 ^{− 1} z .

よって

F _H

z 7−→ z / 2

z ∈ C − { 0 }

G ⁽ⁿ⁾ (z) → 0 (n → ∞ )

ζ ∈ Dom(F _H ) = H ∩ Dom(F _p ) = { ( ζ 1 , −ζ 1 ) ∈ C ² | ζ 1 , 0 }

F ⁽ⁿ⁾ _H ( ζ ) → P ^{− 1} (0) = (0 , 0) (n → ∞ )

F p ( ζ ) , (0 , 0)

F ⁽ⁿ⁾ _p ( ζ ) → (0 , 0) (n → ∞ )

F _p ( ζ ) < Dom(F _H )

F _p ( ζ ) = (0 , 0)

ζ

{ζ 1 = 0 } ∪ {ζ 2 = 0 }

0

(2) α 1 , α 2

q(z) = (z − ( α 1 − α 2 ) / 2)(z − ( α 2 − α 1 ) / 2) , Φ ( ζ ) B ζ + (( α 1 + α 2 ) / 2 , ( α 1 + α 2 ) / 2)

4.2

Φ ◦ F q ◦ Φ ^{− 1} = F p

ゆえ

F _p

F _q

r(z) = (z + 1)(z − 1) , Ψ ( ζ ) B (( α 1 − α 2 ) / 2) ⁻¹ ζ

4.3

Ψ ◦ F _q ◦ Ψ = F _r

ゆえ

F q

F r

F p

F r

α 1 = 1 , α 2 = − 1

ζ ∈ Dom(F _p )

F _p ( ζ ) = ζ −

( ζ ₁ ² − 1 ζ 1 − ζ 2

, ζ ₂ ² − 1 ζ 2 − ζ 1

)

であり，

Dochev

H = {ζ ∈ C ² | ζ 1 + ζ 2 = 0 }

F _p

H

F H B F p | H

F H ( ζ ) = F H ( ζ 1 , −ζ 1 ) = ζ ₁ ² + 1 2 ζ 1

(1 , − 1)

である．そこで

α 1 = α 2

P

G B P ◦ F _H ◦ P ⁻¹

G(z) = (z ² + 1) / 2z

である．さらにメビウス変換

φ (z) = (z + 1) / (z − 1)

g B φ ◦ G ◦ φ ⁻¹

g(w) = w ²

である．以上から

F H

w 7→ w ²

C ˆ

w 7→ w ²

0 , ∞

∞

{ w ∈ C | | w | > 1 }

0

{ w ∈ C | | w | < 1 }

F _H

(1 , − 1) , ( − 1 , 1)

(1 , − 1)

{ζ ∈ C ² | Re( ζ 1 ) > 0 }

( − 1 , 1)

{ζ ∈ C ² | Re( ζ 1 ) < 0 }

F ⁻ _p ¹ ( {ζ ∈ C ² | Re( ζ 1 ) = 0 } )

0

a . e . ζ ∈ C ²

F ⁽ⁿ⁾ _p → (1 , − 1)

F ⁽ⁿ⁾ _p → ( − 1 , 1) (n → ∞ )

□

9 3 ^{重根を持つ} 3 ^{次多項式に対する} Durand-Kerner ^法の 大域収束性

[1]

p(z) = z ³

Durand-Kerner

図

2: balanced

定理

9.1 ([1]). p(z) = z ³

a . e . ζ ∈ C ³

n lim →∞ F ⁽ⁿ⁾ _p ( ζ ) = (0 , 0 , 0) .

Proof. p

Durand-Kerner

F p

ζ ∈ Dom(F p )

F p ( ζ ) = ζ −

( ζ ₁ ³

( ζ 1 − ζ 2 )( ζ 1 − ζ 3 ) , ζ ₂ ³

( ζ 2 − ζ 1 )( ζ 2 − ζ 3 ) , ζ ₃ ³

( ζ 3 − ζ 1 )( ζ 3 − ζ 2 ) )

.

F p

ζ ∈ Dom(F p ) , α ∈ C

F _p ( αζ ) = α F _p ( ζ ) (9.1)

ω = exp(2 π i / 3)

α ∈ C

ζ = α (1 , ω, ω ² )

ζ = α (1 , ω ² , ω )

ζ

balanced

balanced

F _p

2 / 3

F _p ( α (1 , ω, ω ² )) = (2 / 3) α (1 , ω, ω ² ) . (9.2)

F _p

balanced

F ⁽ⁿ⁾ _p ( α (1 , ω, ω ² )) = (2 / 3) ⁿ α (1 , ω, ω ² ) (9.3)

F ⁽ⁿ⁾ _p ( ζ ) → (0 , 0 , 0) (n → ∞ )

また，

| F _p (1 , ω, ω ² ) |

| (1 , ω, ω ² ) | = 2 3

で，

| F _p ( ζ ) ||ζ| ^{− 1}

(1 , ω, ω ² )

2 / 3 < s < 1

δ > 0

|ζ − (1 , ω, ω ² ) | < δ

| F _p ( ζ ) |

|ζ| < s (9.4)

であることに注意する．さて

F _p

Dochev

H

{ζ ∈ C ³ | ζ 1 + ζ 2 + ζ 3 = 0 }

F _p

H

F _H B F _p | H

任意の

ζ ∈ {ζ ∈ C ³ | Im( ζ 2 /ζ 1 ) , 0 , ζ 1 , 0 }

lim

n →∞ F ⁽ⁿ⁾ _H ( ζ ) = (0 , 0 , 0) . (9.5)

P : H −→ C ² , P( ζ 1 , ζ 2 , ζ 3 ) −→ ( ζ 1 , ζ 2 )

F _C

B P ◦ F _H ◦ P ^{− 1}

ρ = ( ρ 1 , ρ 2 ) ∈ Dom(F _C

)

F _C

( ρ ) = ρ −

( ρ ³ ₁

( ρ 1 − ρ 2 )(2 ρ 1 + ρ 2 ) , ρ ³ ₂

( ρ 2 − ρ 1 )( ρ 1 + 2 ρ 2 ) )

である．

P

(9.1)

F _C

α ∈ C, ρ ∈ Dom(F _C

)

F _C

( αρ ) = α F _C

( ρ ) . (9.6)

C ² − { (0 , 0) }

∼

ρ, σ ∈ C ²

σ = αρ

α ∈ C −{ (0 , 0) }

ρ ∼ σ

F _C

(0 , 0)

(9.6)

Q : C ² − { (0 , 0) } −→ ( C ² − { (0 , 0) } ) / ∼, Q( ρ ) = [ ρ ] = [ ρ 1 , ρ 2 ]

ρ = ( ρ 1 , ρ 2 )

Q ◦ F _C

= G ◦ Q

G

R : ( C ² − { (0 , 0) } ) / ∼−→ C ˆ

R[ ρ 1 , ρ 2 ] =  

 ρ 2 /ρ 1 ρ 1 , 0

∞ ρ 1 = 0

(9.7)

とし，

f ˆ B R ◦ G ◦ R ^{− 1}

f ˆ : ˆ C−{ 1 , − 2 , − 1 / 2 } −→ C ˆ

u ∈ C−{ ˆ 1 , − 2 , − 1 / 2 , ∞}

に対し

f ˆ (u) = R ◦ G[1 , u]

= R[F _C

(1 , u)]

= R

[ (1 − u − u ² )

(1 − u)(2 + u) , (u ³ − u ² − u) (u − 1)(1 + 2u)

]

= u(2 + u)(u ² − u − 1) (1 + 2u)(u ² + u − 1)

(9.8)

であるから

f ˆ

f ˆ (u) = u(2 + u)(u ² − u − 1) (1 + 2u)(u ² + u − 1)

である．さてメビウス変換

φ : ˆ C −→ C ˆ

φ (z) = (z − ω ² ) / (z − ω )

f = φ◦ f ˆ ◦φ ^{− 1}

f

Blaschke

f (v) = v(2v ³ + 1) v ³ + 2

である．この右辺は有理関数だから，

{φ (1) , φ ( − 2) , φ ( − 1 / 2) }

f

C ˆ

f ˜

f ˜

0 , ∞

0

は

D ₀ = { v ∈ C | | v | < 1 }

∞

D _∞ = { v ∈ C | | v | > 1 } ∪ {∞}

C = { v ∈ C | | v | = 1 }, D ₀ , D _∞

f ˜

φ ( { Im(u) = 0 } ) = C

φ (1) , φ ( − 2) , φ ( − 1 / 2) ∈ C

f

0 , ∞

D ₀ , D _∞

f ˆ

f

φ ^{− 1}

f ˆ

φ ^{− 1} (0) = ω ² , φ ^{− 1} ( ∞ ) = ω

ω ² , ω

φ (D ₀ ) = { u ∈ C | Im(u) < 0 }, φ ⁻¹ (D _∞ ) = { u ∈ C | Im(u) > 0 }

n ∈ N, ρ ∈ Dom(F _C

)

f ˆ ⁽ⁿ⁾ (R[ ρ ]) = R ◦ G ⁽ⁿ⁾ ◦ R ^{− 1} (R[ ρ ])

= R ◦ G ⁽ⁿ⁾ [ ρ ]

= R[F ⁽ⁿ⁾ _C

( ρ )] .

さらに

ρ

R[ ρ ] ∈ { Im(u) , 0 }

{ Im(u) , 0 }

f ˆ

f ˆ ⁽ⁿ⁾ (R[ ρ ]) ∈ { Im(u) , 0 }

f ˆ ⁽ⁿ⁾ (R[ ρ ]) , ∞

F _C ⁽ⁿ⁾

( ρ ) = (F _C ⁽ⁿ⁾

_{, 1} ( ρ ) , F ⁽ⁿ⁾ _C

_{, 2} ( ρ ))

F _C ⁽ⁿ⁾

, 1 ( ρ ) , 0

f ˆ ⁽ⁿ⁾ (R[ ρ ]) = R[F ⁽ⁿ⁾ _C

( ρ )]

= F ⁽ⁿ⁾ _C

_{, 2} ( ρ ) / F _C ⁽ⁿ⁾

_{, 1} ( ρ )

である．以上から

ζ ∈ Dom(F _H )

R[P( ζ )] ∈ { u ∈ C | Im(u) , 0 }

F ⁽ⁿ⁾ _H ( ζ ) = P ⁻¹ ◦ F _C ⁽ⁿ⁾

◦ P( ζ )

= (F ⁽ⁿ⁾ _C

_{, 1} (P( ζ )) , F ⁽ⁿ⁾ _C

_{, 2} (P( ζ )) , − F _C ⁽ⁿ⁾

_{, 1} (P( ζ )) − F _C ⁽ⁿ⁾

_{, 2} (P( ζ )))

= F ⁽ⁿ⁾ _C

_{, 1} (P( ζ )) (1 , f ˆ ⁽ⁿ⁾ (R[P( ζ )]) , − 1 − f ˆ ⁽ⁿ⁾ (R[P( ζ )])) . (1) R[P( ζ )] ∈ { u ∈ C | Im(u) > 0 }

R[P( ζ )]

f ˆ

ω

N ∈ N

n ≥ N

|ω − f ˆ ⁽ⁿ⁾ (R[P( ζ )]) | < 2 ^{− 1} δ

n ≥ N

| (1 , ω, ω ² ) − (1 , f ˆ ⁽ⁿ⁾ (R[P( ζ )]) , − 1 − f ˆ ⁽ⁿ⁾ (R[P( ζ )])) | < δ

n ≥ N

| F ⁽ⁿ _H ^{+ 1)} ( ζ ) | = | F _H (F _C ⁽ⁿ⁾

_{, 1} (P( ζ ))(1 , f ˆ ⁽ⁿ⁾ (R[P( ζ )]) , − 1 − f ˆ ⁽ⁿ⁾ (R[P( ζ )]))) |

≤ s | F _C ⁽ⁿ⁾

_{, 1} (P( ζ ))(1 , f ˆ ⁽ⁿ⁾ (R[P( ζ )]) , − 1 − f ˆ ⁽ⁿ⁾ (R[P( ζ )])) |

= s | F _H ⁽ⁿ⁾ ( ζ ) |.

よって任意の

j ≥ N

| F ^(N _H ^{+ j)} ( ζ ) | ≤ s ^j | F ^(N) _H ( ζ ) |

lim _n→∞ F _H ⁽ⁿ⁾ ( ζ ) = (0 , 0 , 0).

(2) R[P( ζ )] ∈ { u ∈ C | Im(u) < 0 }

(1)

lim _{n →∞} F _H ⁽ⁿ⁾ ( ζ ) = (0 , 0 , 0)

(1),(2)

(9.5)

a.e. ζ ∈ Dom(F _H )

lim _n→∞ F ⁽ⁿ⁾ _H ( ζ ) = (0 , 0 , 0)

ζ ∈ Dom(F _p )

F ^′ _p ( ζ ) = ( f _{i j} ( ζ ))

f ₁₂ ( ζ ) f ₂₃ ( ζ ) f ₃₁ ( ζ )

f 32 ( ζ ) f 13 ( ζ ) f 21 ( ζ ) = − 1 , 1

であることから

F ^′ _p ( ζ )

1

2

a.e. ζ ∈ Dom(F p )

lim n →∞ F ⁽ⁿ⁾ _p ( ζ ) = (0 , 0 , 0)

□