A Computational Aspect f6r the Inclusion Theorem
in tems of Euclidean Norrn for a vector．
Klコlnio OSHIMA （Received Mlardh 10， 1981〕 Abstract： In his dissertation ［5 ］，Oshima proves that there exists an inverse iteration to find an eigenvalue and it，s eigenvector for a nolmalizable matrix． This paper is intended to develop Corollary 2二7． ［5， PP 13 ］ in suCh a way that it does mt require the no㎝alizability of a matrix， and to study the problem of constructing a program for the procedure and of examihing it．s practicability on a c（耶puter． 1．Introduction． Let l l．・llbe a vector nom， x be a vector amdλbe a number such that H l（A一λ1）x l l is sma11． A classical questi㎝concerns the neamess ofλto an eigenvalue of a given matrix A． This questi㎝is the starting Point of Wielanピs study ［6 ］． In their paper ［3 L Householder and Bauer prove the fbllowing result： If A is a nonnalizable matrix， A＝SDS衰， S is 皿itary， D i， di。g。na・， l l。ll・〔。H。〕1／2 i9 th。 ve。t。r＿， and 11 A I I・ max llAx ll／llxll is the matTix nom subordinate to the vβctor norm， then x≠0 2 2 1δi一λ1≦llSll、’llS★ll、’ll（A←λ1）・ll、． for at least one eigenvalueλand D＝diag（δ1・δ2・°・．・δn）・ 2． Previous results and definitions． Throughout this paper， scalars， column vectors， and square matrices will l）e denoted by lower Greek letters， lower L・tin 1・tter・， and・・pit・1 L・tin letter・， respectively． The s）柚・1・C，（i”， and Mn〔C）are the set・f the c。mPlex field・th・・et・f the c卿1・x n−dim・nsi・nal vectors， and the s6t of the complex n x n matrices， respectively． Defi・iti・n 2・1・A皿ltiplicati…mat「ix n°「m°n M／。（C）iS ．a ”gnnegative real v・1u・d㎞・ti・n d・fined・n Mn〔C）・ati・fying・（1）A・O if・and。・iyif llA11・Ofb・・nyA・M。（C）
（II）ll刷1・1λ1・lrAllf。・al1A・M。（C）・・d・X・C
〔III）llA・Bll≦llAll・llBllf。ral1A・B・M。〔C）
〔Iv〕．．ll． ABII≦llAl1・llB目f・・al；・A・B・Mri（c）・ ． Note that・the ．gultiplicati’ve axi㎝〔IV）is not㎞posed by s㎝e authors． The reseach of this author was strppOrted in part by the Minister of Education under Grant 403−8005−57094 in 1980．47
K．OS田刊A Miniti・n 2．2． A ve・t・・mm ll引。n♂i・ca11・d m・・t㎝i・if fb・紐y diagonal matrix D，
1 票1園1／1国1＝呼IFδil・・’
The fb11σwings are岨1㎞oWnρn“．are． ing！uded．pr迦qrily・ ，to／， ，，lay grom蜘rk fbr what follows・ For more detailed treatments， see 【1 】， ［3 】， 【 5 】， a血d ［7］． th・。・㎝2・3． lf l卜lri・ave・t・r．η。m㎝（i「’， then th・fC11・輌9・・ndi− tions are equivalent： 〔・）日・lli・m・nbt。。i。．’ ．1’． 〔b）ll刈r・lll．？・ ll．lfCra11・．ε．♂・、，、≡．．，．，．．．〔・．）1・1、≦1 y．1麺・i・・lr・ll．≦1．1，y’ll・ ．、， 、
，．ぽt⊥㍑［yi認l l讐1’1ぷ；i篭α竺ll竺三
Definition 2．4． A matrix．孕Dm l l一川is．called consistent． with the Vector・・mll・口P士・vid・dll倒1≦日All・｜．
b・1．P，晦・r61・．・．巴鋼A咋（￠）・
D・finiti・n 2・5・Let l l・llbe a・m・t・ix n・m c㎝・i・t・nt・with・th・v・，・t・r−1い．U・・f・飴・eV・ry㎜・・i・A・Mn〔C），血ere i・aV・ct。・x≠・鋤
血・ll酬1・1川．1川・ll，・h・nt輪・・mi・ca…dと㎜・・iX・・m⑭・−
dinate to the vector norm l l ・ ll． Theorem 2．6． The matrix nornl defined l）y ． ．． llAll− max目Axll＝max・llAx．ll／llx．ll llxll＝1 x≠O is consistent田1d subordinate． such a matrix nom is called an qperator ho㎝． Th…㎝2．7． If a vect・r・・m i…mt・ni・， x・♂川・1ド1，・nd D・＝di・g（δ・・δ・・．…・、δn）・th・n ． ・
mg・．1δil≧lrih・ 11≧輌1δil・． ． ・ ． 1 、 ． 1・3・（leneralized・e・・1t・It i・鳩11㎞㎜血t響y A・M。〔C）・飢b・
drc。叩。sed int・af・rmA・s（D・M）s★砲・r・si・u・ita・y， D i・．diag。na1，飢d M ls@an UPPe「 t「1angular matrix曲ose rnqin diagonal element『 are all zero・ In thiscgmecti㎝・the f・ll・wing・th・。・㎝i・given・ ． 、 ．
th…㎝3・…e・A・S（D．珊S輪・dec卿sed聰・・血㎝． Mn国・・lf
lいIli・飢・p・τ・t・・mm飢d仙evect・・n・mi・．㎜・。師C顧thU・IPlfb・
x・♂，t輪n脳， have
輌1δi一λ1≦11・．S 1い11 S・ ll・1． P．（A−．λ・）・1閨IMI．lf・頭・λ・C．
1 ’ ． P・・。f・Since、 th・・e eXi・tS’・Ve・t・r x≠0・ud・dぬt・・Sb・th・n Ax 一 λx＝ASb「一 λSb ＝ S（ D＋’M）b 一λSb＝ St D十M’； λ1．）b， ”so that ．．． ． 1 ． ’
llAx一λxl1＝．llS〔．D二λ1＋M）bll≧ll（D一λ1◆M）bll！llS★ll・
Let y；b／llbll，it fbllows froni the rrKonotonicity…and Theoren 2．7． thatllSll・目S★「1●llAxrλxll≧ll〔D一λ1’＋M〕bll／llbll
㎝d血tゆ1δi一λ1≦日Sll・ll S★ ll・日〔A・一λ1〕・ll＋llMll
1 ’fbr a11 λ ε C〔 Nbte that l l M日is．said to be the medsure of nqmonl頭ty of the matrix A， ．hence if 日 M l l ＝ 0， the resUlP． co桓cides with・Corollary 2・7・．［・．5，・pP 13．］・． Definition 3．2．−For fixed・λ， x，．餌d A the disk・｛δ： 1δ一λ1≦llSll・llS禽11・ll〔A一λ1）xll＋llM．llwherellxli＝1｝
is called a． mini頑zable disk and denoted by、△（λ， x） ［．cf 5．］白、、． ． ・ こ 1 4．A ccmputational aSpect．fbr the．nininizable disk ip tems of Euclidian vector nom．晦firSt note tllat the Euclidean． vector nom．is ．monotanic［3】， ［5 ］． It will be assumed， throughout this section， that the vector ngrm is・：，1。1：、；iixlxil1！1：r孟ξ遮le罵、1°：ご：ぷliよ蹴1・
In the mini皿izable disk， there are three potential ways tO control the size of the disk：To contro1 ．’ （ 1 ） The c6rtdition Ilumber， ll．S l l o ll・S★．． l l（2）The quantity llMll ． ・
〔3） The quantity ll〔A一λ1）x ll． Since 目 S l l ． 目 S★ l l ＝ 1， there is nothing to do with 〔 1 ） on the 2 2 vector no㎝． For our computation， we ma． y assumne that m＝inf I I M目 is sma11，麟・、軍、ぎ鵠，蕊：1；濡；・蕊：＝㌫，
・j f・・each j・He・ce（2）may・・n°t be taken血t°c㎝sidefati㎝・ For（3），the following result will be the base fbr the inverse iterati㎝ procedure that controls the、 size of the disk by cO証trolling the Ilumber； Il （A一λ1）x ll、t、、慧＝㌶9㌶1。leλ憲認i。認：＝；〔㌻
・ll（A−・・〕・1「 P、・With・hi・in Pma7． ． th・fb11・輌9．・h…㎝i・i・・曲・ed ［cf 5 ］． 』 ． ・ ’th・・rem・4・…e・A・Mn（．・）dnq・・ε♂・i・h・11・いl l、、m♂・・h・・th…exists x、ε♂with llx、 ll・1 sueh− th・t・．…・・ ．
2 、 ・ll（A二’λ2・）k−・．ll2r≦1．1（A一λ・「〕・1］、．‘．：1”砲ereλi・x呈A・i・f・・i・・，2・ 1
K．OS田刊A Proof：
Then
Let X、・x￥A。、 b。 ，calar、u。h th。tO≠II〔A一λII）xlll ＝minll〔A一λ1）xlll．
2 λ 2 ・・ll・・ll、当（．A一λ・・）−1（A一λ・・〕x・ H2 ・ll〔A−…〕−1 ll、・ll（A一λ・・〕・・ll、・hence
Since
1／ll（A一λII） there exi・t・y・♂with l l ll（A一λ11 it follows by setting z＝〔A一λ！I ll（A一λII）x2目 2 ＝ilyll／Hzll 2 2 Therefore ・ ll （A一 λII ）x2 This result brings us ’ fbllows inductively． 5． Co㎎）utational experience． flowchart， necessary subroutines， 一1 11≦ll（A一λII〕Xlll． 2 2 y ll ＝ 1 such that）−il1・ご Il〔A一λ、・）’1yll，
211yl1＝1 2
2 ）−ly 。nd。、・・／H・口th・t 2 ＝ll（A一λII）zll ／ llz ll ・・／U（A一λ、・2〕−111．2 2 ll ≦日（A一λII）Xz 。。、t。r。ti。n 6Y2・：tt血9λ、・撫，， ll． 2 and the1teratlon
In this section， we will give a possibe and s㎝e colmnents on the algorit㎞．FL㎝CHART
start
rea A， x 〔a）一舎 （b〕一 〔c〕；… c 一 輪 ． 一 ． ・ ⇒ ● ● ● 一 一 一 ● 一 ● ●λ＝xHAx
／．．． ． 圃 一1 ’＼．no
■一 一゜、’1−’一一 、ユA一λ1〕／
．．．♪一一づstop
yes
∴．．i ．@ 1n y wlt
ﾚ（A一λ1）−1
@ 2 y 撃戟≠撃 ＝1suc2（A−．λ1tat
j−1y 日 2 。・〔A一λ1）−1y／ll 2 （A一λ1 〕−1yll Constructing such a program may require the following subroutines：〔i〕ll・11・1fb迦y・・♂・ ’ 昌．・』・
（ii）…（；），・h・q迦…y・HA・・fb・孤…♂孤d・・Mn（・）・
（iii） For〔h），to find an inverse of A・ （ iv ） For （ C ）， to find an eigenvector corresponding to the． maximU皿magni一加d。。f。ig。悩。1。。 fb。（A一λ1〕’1． ・ 馳
Mthough these sUbroutines are available in most co㎎旭ter libraries， the auth・r e）rPefi・nce・the p・・9r輌g by鵬・ns・f Ba・i・1’anguag・飴・匝cr・、C・mputer （1やple II plus 48k〕and examines the results on it．恥岨11， however，㎝it a list of the progr訓fr㎝this paper． ． 二．．・ C。mP・t・ti㎝・1・騨i・nce i・g蜘・・q・fb11。・・；th・ s卿1β1 is the apP「°xi一 ㎜ti・n t。λ・each・i i・紐叩P・㎝麺te ele鵬nt飴「an eigenYect°「・孤d the index i is the nu抽ber of the iterations． ’A＝
The eigenvalues of A areλl eigenvectors are x1＝ ［−15，』12， ’ ?堰@envalue 1 β． 1 0 0．33333334 1 」 P．00001014 2 0．99999996 i β． 1 0 一10 ．； 1 1．98194229 2 1．99999993 33， −24， −8， ＝1， ’4］T， 16， 72 −10，−57 r4，−17 λ2＝ X2 ＝ 2，λ3＝ 3，and the three corresponding ［−16，13，4］T 。nd’x，・．・［ −4，3，1］T． 一 ’ei「envector ‘ ． 1 0 ﹁ 11 2 一 α1．『 0 7U0．764589543’ 一〇．764470785 α2 0 0．611171611： 0．611576631 α3 ． 1 0．204626715 ・0．203858876 ﹁ i ’ Dβi 」・ 0 」Q6．1343284 1 3．00997705 5 3．00000004K．OSHIMA
A＝
6，−3，4， 4， 2，4， 4，−2，3， 4， 2，3， 1 0 1 1 The eigenvalues of Aもareλ1＝3＋rS，λ2 ／−5and the two corresponding eigenvectors are ・、・（rs，3・，，・’9’，2，6）T，。，・（一 ＝3＋A「， λ3 ＝ 3 一 ノF了， λg ＝3 一rs，3−rs，2，6〕T．
ei envalue i βi 0 8．5 1 5．30025985 4 5．23614277 el envector lw
0 1 4 α1 1 0．26882197 ． 0．26277146 α2 1 」 O．61470165 0．615298775 α3 1 0．23856702 0．235027528 α㎏ 1 0．702184244 0．705067824 ei envalue i β． 1 0 1 1 0．768902702 2 0．764029622 ． ?戟@envector ・ ． ・ @ 1 『w
b
1 2 α1 一1 0．329094253 0．331151528 α2 0 一〇・114611026 一〇．113177649 」 α3 0 一〇．293818106 一〇．296180477 α㎏ 1 一〇．89007427 一σ．888710645A＝
7．38， 0．05， 0．07， 0．．08」 0．08， 一〇．08， 7．29， −0．03， −0．04， −OcO4， The eigenvalues of A areλ1＝7．1， ＝ and the five corresponding eigemrectors are 、 ・、・（1，2，3，4，0〕T，。、・〔2，3， ・，・（：3，4，‘0，ジ1，2）T，。、・〔4，0， ．，・〔0，1，2，．3； 4）T．．・ 一〇．04， −0．07， 7．21， 0， 0， 0， −0．03， −0．05， 7．14， 0．04， 7．2，λ3 0．04 0．11 0．19 0．28 7．48 ＝7．3， λ4＝7．4， λ5＝7．5， 4，0，1）T， 1，2，3）T，ei envalue i β． 1 0 7．18 1 」 V．2
2
7．19999999 ・ ?撃№?鰍?モ狽盾 1 X 0 1 ． 2 ． ｿ1 ’0・ 「￨0．365148368 一〇．365148368 ． ｿ2 1 F￨0．547722552 一〇．547722552 ．α3 0 一〇．730296749 一〇．730296749 α鳥 ’ 1． 0 ． Ln 』 α5 0 一〇．182574184 一σ‘1：82574183■．．
゜、 ・馳 P 、．・D，． oi． 0 層V．37 1 7．4 2 ”．@．i 』 ． D7．4 ’ 二 ’ L ． 三 i β． 1 0 7．45 1 7．49390744 2 7．5 Co加匝ent： the iteration is fairly rapid and accuτate by coロparing with other iteratioms or proceduヱes fbr the purpose 【4，7 】；however， author e’甲eriences・nly the ca・e・n Mn〔R）s・Chat it may be very interesting t・ expe・i・nce the ca・e ・n Mn（C）fb・practicability・・ince th・・e i… th…etical restriction to use co叩1ex nuロbers on the iteration．K．．』 nSHI［MA 『 【1］
