III11
IFORSjTIMS
国際会議から (4)111111111111111111111111111111111111111111111111不動点 Algorithm とその収束
1967 年に Scarf [5J が Brouwer の不動点の近似計
算をする algorithm を発表して以来，不動点問題に対
する解法は L 、ちじるしい発展をとげ，“ Fixed
Point and
Complementarity
Theory" とよばれる数理計画法の一 分野を形成するにいたっている. TIMS 国際会議でも， Stanford 大学の Eaves 教授を座長とした session で7 つの研究が発表された そのうちの 2 つ (Charnes ，
Garcia and Lemke
[2J と Saigal [4J) は， Merri11が1972 年に学位論文[3J のなかで提案した不動点 algo・ rithm の非線形連立方程式への適用に関するものであっ た. ここで・は， この algorithm と [4J を簡単に紹介す る. 1 を n 次元 Euclid 空間 Rη から同じ空間への非線形 連続関数として l(x)=O
(
1
)
なる方程式を考える. Merri11の algorithm は Scarf
[5J を土台としてはいるが，計算効率を高めるための新 しい工夫が導入されており，これ以後に発達した数多く の algorithm の原型となっている. この algorithm で は ， t ε[O， IJ をパラメータ x εR凡を変数とする方程 式の族
L
(x,
t) =0 (2) が重要な役割j をはたしている.ここで ， L は Rηx[0,
1
J
で定義され Rη の値をとる連続関数で，条件 L(x,
1) =l(x) (xERη) ，(
-1)
あるが ERn に対して ， L(xO,
0) =0(
i
i
)
を満たす • XO は既知であると仮定する . (2) は既知な解 討をもっ方程式 L(x， O)=O を方程式 (1) に連続的に変形 する方程式の族とみなすことができる . S を (2) を満た すすべての (x， t) E三 Rnx[0,
1J からなる集合， C を (XO， O) ES を含む S の連結成分とする.ある適当な条件を仮定 すると， C は (XO ， O) と(忌， 1) を結ぶ Rnx[0,
1J 内の曲線 となる.ここで，語は方程式 (1) の未知な解である.この 場合，既知な (XO， O) を初期点として， (2) を満たす (x，t) の軌跡 C を追し、かけることによって， (x ，1) に到達する 小島政和 ことができる.これが Merrill の algorithm の基本的 な考え方になっている. この考え方は Newton 法を原 点とする解析的な algorithm のいくつかではすでに採 用されている(たとえば，Broyden
[IJ). それらの解析 的な algorithm では， C を追跡するために微分方程式 の初期値問題:ゴ
ιFL副仰州
(<p
刷
v判(川
t
の近似解法が使われている.この初期値問題が区間 [0 ， 1J で解けるためには，r
I日i 線 C が t に関して単調であ る J ，すなわち， rC={(<p(t),
t): tE[O,
1J} とあらわさ れる j ことが必要である.したがって ， L が微分可能で、 あったとしても， C が t に関して単調で、ない場合には解 析的な手法を用いて C を追跡することは困難であろう. Merri11の algorithm では解析的手法のこの欠点、は克服 されており， C が t に関して単調にならない場合のみな らず， C が l 本の曲線にならないような場合もあっかう ことができる.これは Merri11の algorithm の特筆す べき利点、であり Brouwer や角谷の不動点の近似計算 を可能にしている.しかし「パラメータ t に関して単調 に収束する」という解析的手法のいい点一一解への収束 を判定するためには非常に有用 は一般には保証され ない. Merrill の algorithm では L(x,
t)=
(l-t)r(x) +tl(x) ((x， t) εRηx[0
,
1
J
)
なる L が用いられている.ここで ， r(x) =Ax-a(xE Rn),
A は河 Xn の正則行列 ， a は n 次元ベクトルである(Merr
i
1
1
[3J では A として単位行列がとられている). L を，各端点 (x， t) が Rnx {O} あるいは Rnx {1} 上に ある Rnx[0,
1J の単体分割 I を用いて，区分的線形関数 F で近似する .σ を I に含まれる (n+1) 次元単体とする と ， F は σ 内で線形であり (r(x) ; (x,
O) は σ dのコ止封端i出此品ι" F( ♂， tめ)=j
ll(x) ; (x， l) は σ の端点2
8
2
111111 川川川 1111111111111111 フォーラム 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 川川 オベレーションズ・リサーチ © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.‘ 11111111111111111111111111111111111111111111111111111111111I11I111111111111111 ・ 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 ・ 111111111111111111111111111111111111
によって完全に決定される . 1 を構成する (11+1) 次元単
体の Rnx {O} 上への正射最多の直径の最大値を I の mesh
size と土ぶ . 1 の mesh size が 0 に収束するとき F
(x
,
t) は L(x， t) に収束する.したがって， (2) は F(x,
t)=0
(
3
)
で、近似される A-1a は線形方程式 F(x， O)=:=Ax-a=O の唯一の解となる.よって ， P を (3) を満たす (x， t) の集 合の (A-1a， 0) を含む連結成分とすれば ， P は Rnx {O} と 唯一つの点 (A-1a， 0) で交わる . P は上述の C の近似に なっている.さらに， (3)に対する非退化の仮定と P が 有界であることを保証する条件のもとで ， Pは (A-1a， 0) と (ÿ， l) を結ぶ有限個の節点をもっ区分的に線形な曲線 となる.ここで ，'ÍÍは(1)の近似解である.この場合には，(A-1a， 0) を出発点として，
complementary
pivoting を(3)に施すことによって ， P の節点の有限列 れこ収束 一一ーを生成することができる. (1)のより精度の高い近 似解を求めるためには， (fj， 0) が初期値となるように F をつくり直して上述の過程を繰り返す.以上が Merrill の algorithm の概略である.
S
a
i
g
a
l
[4J では ， 1 ヵ， Rη の各点 z において連続な Jacobi 行列 Dl (x) をもっ場合が扱われ， I どのような条 件が C の t に関する単調性を保証するか J ，そして， I そ の単調性はどの程度 P に反映するか」が主題となってい 行なっている. (1) の近似解宮が既知であると仮定して， より精度の高い近似解を Merrill の algorithm で計算 する場合を考える. まず，求める近似解の精度にみあう mesh size をも っ Rηx[0,
lJ の単体分割を作る. (iJ， O) を含む π 次元単 体 σ cRηx {O} を選ぶ.σ のすべての端点 (v， O) に対し て ， Av-a=l(v) を満たすように A と a を定める.こ のとき ， Dl(語)が正則で宮が忌に十分近ければ条件 (a) が成立する.したがって， (b) および (c) が満たされれ ば C は t に関して単調になり， (4) も成立する.(
(
c) は Ax-a(xERn) が忌に十分近い宮での t の線形近似であ ることにより正当化されるものと思われる). さらに， Saigal は C が (A-1a， 0) と(云， 1) を結ぶ直線 (すなわち ， (A-1a， 0) と(云， 1) を結ぶ最短路)に非常に近 いことを示唆している. \，、くつかの数値例について A を単位行列に選んだ場合との比較がなされており，上述 の A と a の選択法が有効なことが裏づけられている. [4J では，このほかに J が線形である場合と，ある積 の単調性をもっている場合も考察されている. 参芳文献[
1
J
c
.
G. Broyden
,
A New Method o
f
Solving
る x を(1)の解， W を x を含む Rη の関凸集合とする Nonlinear
Simultaneous Equations
,
Computer
つぎの (a) ， (b) を仮定する Journal
1
2
(
1
9
6
9
)
94-99.
(a)
任意の XEW に対して， IIX Il行列 A-1Dl (x) の[
2
J A. Charnes
,
C
.
B
.
Garcia and C
.
E
.
Lemke
,
実国有f直がすべて正である Constructive
Proofs and A
p
p
l
i
c
a
t
i
o
n
s
Relating
(b)
ある K>O に対してt
o
Nonlinear Systems :
F(x)=y
,
TIMS Meeting
I! Dl(♂)一 Dl(γ)11壬 Kl1x ーが!
(X
,
yEW)(
1
975).このとき
[3 J
o
.
H. 乱1errill ，A
p
p
l
i
c
a
t
i
o
n
s
and Extensions
(c)
十分小さな占 >0 に対して ， l!x-A-1al!<o
f
an Algorithm t
h
a
t
Computes Fixed P
o
i
n
t
s
ならば， C は A一切と云を結ぶ t に関して単調な曲線と
o
f
CertainUpper Semi-Continuous Point t
o
S
e
t
なる .P と C の問には
Mappings,
Ph. D. Dissertation
,
U
n
i
v
e
r
s
i
t
y
o
f
Iy-xll壬 Klε ((y， t)EP， (X
,
t)EC)
(
4
)
Michigan
,
1972.
が成立する.ここで ， K
1
はAとDl (x) (xEHつに依存[
4
J R. Saigal
,
On Paths Generated by Fixed
する正数， ε は I の mesh size である .P が t に関し
Point Algorithms
,
B
e
l
l
Telephone Laboratories
,
て単調であることは示されてはいないが， (4) は P が 1975.
に関して単調な曲線 C の K
1
õ-近傍にあることを意味し[5 J
H
.
Scarf,
The Approximation o
f
Fixed P
o
i
n
t
s
ている of
a Continuous Mapping
,
SIAM Journal on
Merrill の algorithm を用いて (1) の近似解を求める
Applied Mathematics 1
5
(
1
9
6
7
)
1328ー 1343.とき ， nXn 行列 A と n 次元ベクトル a をどのように 選べば解への収束が速いかということは噴要な問題であ (こじま・まさかず東京工業大学建学部) る. Saigal は上の結果にもとづいてつぎのような提案を 川 1111111111111111111111 川 111 川 111 川川川川 111川川川川 1111111111111111 山川川川 11111111111111111111111111111111111111111111111111111111111111 川 11111111111111
