TRU Mathematics 19−1 （1983〕 SECANT UPI］VITII］S OF QUAS I−nmN ME’ll−K）DS FOR SOLVING sPARsE NoNLINEAR EQuATIoNs Hiroshi YABE， Satoru TAKAHASHI and Naokazu YAMAKI （Received May 6， 1983） Abstract：The problem of finding the solution of a systen of nonlinear equations by the quasi−Newton metbOd is considered． This paper is concerned with the construction of the卿tes which preselve the sparsity pattem of the Jacobian matrix． These results．include the updates of SdhUbert， Toint
and Shanno． Furthermre， it is s㎞m血t t輪alg。ri㎞propsed卵nt，
whidh uses the update derived variationaユ1y with．anondiagonally weighted Frobenius noτm， generates the sequence whidh converges locally and sUPer− 1inearly to the solution under some conditions．1．Introducti㎝
伽sider the prob1㎝of finding the solution of a systen of nonlinear equatlons （1．1） grxノ＝0．9・r ． Rn with t｝ie・Jac・bi・n m・t・ix♂ω・Rnxn． Tl・i・ ・y・t㎝i・a1。。 referred t。 th。 gradient equations in the nonlinear optimization problems． Let x t be the solution of the above equations． One of the mst efficient numerical methods fbr solvi皿g the syst㎝〔1．1） is the quasi−Newton method， which is based upon the iterative process （…）x、，、 一・xゼ・k・i’9k・r Xk＋、一・ゼc・kH、9だk−・．2。…。Wh・・e・k飢d・Hk・・e・he a卿・㎞・i・鵬…ω孤d・ω一1…k， respe・ti…y，
αkis a suitab1・・匂・i・e ・nd gk 一 gr・k）・th・噛tes・f th・ma・・i・e・Bk・・ 与a「e defined by the f°ll・蜘g re1・ti㎝・顧・h・par・me・・r ve…r ・k； ∂k・・＝8瓦・・「Bk・8だ〃だUkノ゜「Hk＋、＝㌦、「Hだ・た・yだUkノ・ （1・3） 8k ＝ Xk＋1 一 Xk and Yk＝9k．ユー9た ’and （1．4） Bk＋18k ＝ Ykor
Hk＋IYk＝8だ 7576 H．YABE， S． TAKAHASHI AND N． YAMAKI which is．called the secant condition． lhere｝・・ve bee・・in th・・ece・t・P・・t， the st血・・fb・th・ intere・t卿t。 algorithn preservi皿g the sparsity pattem of the Jacobian matrix．血s is areasonable work since it occurs usually for the Jacobian matrix to have ㎜yzero e1㎝ents in㎞omμ）sitions in the case whenηis very large． This enables us to save storage and computation， and ensures that．the method can be applied to the problems with large size． In whidl case， it would be desi「able t°c°n・id・・th・順・・iX・た・a・her ・h・n ・k・ince・・he・i・verse・f・ spa「se matrlx ls n◎t generally sparse． 乙 For nonlinear equations， Sdhubert 【13］ modified the update derived by Broyden 【1】 sudl that the sparsity pattern is maintained． ㎞ ［9］ and Marwi1 【10］ showed the local and superlinear convergence of the Sdhubert method． For the gradient equations， the Jacobian matrix is symmetric． Recently， Toint 【15］，［17］ and Shamo ［14］ have dbtained independently the symmetric口pdates which satisfy the secant condition and preserve the sparsity pattem， by using variational approach which was first discussed by Greenstadt［8］． Demis and Sdhnabe1 14］ have also discussed the sparse symmetric update methods． Furthermre， Demis and Walker ［5】 and Toint ［16】 have proved independently the local and superlinear c㎝vergence of the Toint（or refeπed to the sparse s）metric Broyd㎝）method（［15］）． The first purpose of this paper is to present general fOrms of the sparse trpdate and the sparse s）㎜etric update． Our updates include the resuユts of Schubert， T（）int and Shanno．随〕reover， it will be shown that the algorit㎞ proposed by Toint 【17］，which uses the update derived variationally with anondiagonally weighted Frobenius norm， generates the sequence which converges locally and strPerlinearly to the solution under some conditions． th…gh・・t thi・p・per・w・・us・th…t・ti㎝… f・11・w・・L・t l卜1』d㎝・t・ the 2−nom． The imer product of two Inatrices A and O is defined by rA診の＝ tra・・rACTノ・r r・．・ゲ鋤・・rガ1・〆♂ノ，Where・・i・a・Y・・me・・i・P。・i・iVe defi”ite mat「ix飢d the s）励・I T d・n・tes th・t・・n・p・・iti㎝・th・n・m・ll M llF 三d』・S，ll認：：、：蕊：二。1°ス隠。：：、漂ted F「°ben’ °m°f a㎜t「’x ll〃ll。一｛励・r・，・fT・｝：／2飢・ll〃ll酬一悟…醜一’，・T・｝1／2・ ・・一・ff血…b・e・鴻・f 「xn…tP／A、．飢d％．“d・n・t・th・・曲・g・na・ P「°jecti㎝s㎝t°鴻桓’th・・ense・f th・㎞・・p・・du・t r°・り紐d r’・りPt
re・pecti…y・晦一・・…咳ゴ・−P／A。． an・％バ・−P／A．−d r㌧・・
the a，ゴノ．element of the matrix〃．sE㎝T UPDATEs oF QUAsI−NEwTON METHODS 2． SParse 町》dates fbr Quasi−Newtσn Mbthod L・t Bk b・the current est㎞・t・・f the Jac・）bi・n mat・i・・In thi・p・p・r・th・
mat・ixβたis嘩t・d in the fbm ・
Bk＋1＝βた＋Ek °「 βた＋1＝WkBk ＋ Ek・ 曲・・e・kis a・calar par・鵬t…nd Ek i・飢・×・c・rrecti・m m・t・i・・th・n th・ sparsity constraint is expressed by（2・1） 「BUσ＝°fb「卿「ち」ノ・Z・
Where Z is a set of ordered pairs of integers in the range ヱ toη． 1」et θbe aset of ordered pairs of integers， fbr the Jacobian matrix， su（虫 that〔・・2）r・ωノガ・f・・a・y・x・♂if飢d㎝・yif rちゴノEG・
Then we consider the set Z included inσ． 1、et Z be defined by Z＝｛ri♪ゴノξi＝13・●・，72 andゴ・＝1，・●●3n｝−Z． For the set Z， the fbllowing sUbspaces of 1∼lxn are considered；〔…）Ar・ノー｛〃・RnXn・r〃ノ、ゴー・鋤rち」ノ・Z｝
and （2．4） ／Arの＝｛〃、♂×η、r〃ノ．．−Of。rrちゴノ、σ｝． zg Of many available， we use n xη diagonal matrices 5．3 i ＝ ユ3・．・3η， where th・Z−th di・g・na1・1㎝・nt・f Si i・・er・if「i・・V・Z ・nd unity・th・mise・血en we have， fbr anηxηmatrix M」 〔…）P／A・、、．・〃一 A1、・i・1〃・i孤・咳，、、．・ 、i、・i・；〃・・一・e・ 砲e「e・Zis旭一th c°1um v（∋ct°「°f the identity mat・i・エ・If％rZノノ＝妬 then〃 is said to haりθ the 8Pα㌘8itY pattern o了Z・ Th・pu・pOse・f this secti・n i・t・find t｝馴at・ix∂た＋1 su・th th・t （2・6） Bk．、 E／A「Z） nQ「yだ8たノ・ th・t i・・㌔・ati・fies t｝・e・ec・nt・・nditi・n ・nd h・・t｝・e・par・ity p・tt・m・f Z・where
（…）・・Yk・・∂一｛〃・「×”・〃・、−Yk｝・ ・…；” ＝・i・、飢・・f・r・a・ca・ar・…tβ＋b…／・・fβ≠・an・…h・rw・・e・ Setting 7778 H．YABE， S． TAKtliIASHI AND N． YAMM（1
（…）与一wrll・（1／1膓．…．ll・鯛，・
鵬』ve the輪re−P・nr・・e generali・ed麺v・・se・f M （・・9）幸wr・ll・｛1／1彦・†．…．rll・ln／1θ＋ノ・ L・tting rV（・∂一｛M・r×n・M・k ＝・｝，孤y・・㎝㎝・・f・h・・affin・・Ub・et 膚「幻・Q「〃k・・k）㎝b・r⑤・esented by・1血ea「㎝由inati㎝゜f a specia1・1㎝・nt inA（Zノ・Q「〃k・・∂飢d・n・1㎝・nt in th・ sUbspace／A「Zハβ「・たノ・It is als・ ㎞㎝・d聡tth・Sd眠rt卿t・〔【13］〕i・。n・in A「Zノ・Q「yk・・kノ・砲i・血i・giv・n by the fbm〔［10］） （・…）・k。、一・k・・、A，、、。、1・1・Yk、一・k・k・・1］ ∈膚r幻．Thus we have the ne）戊t｝leoren．fbrβ k 田EO眼11・488碗・that Bk ha・th・ ・par・鋤ρ・カカ・「’n・了Z・ha・・α卿・「aZ upclate プ’o「mlZa whioハz sati8了乞θ8 the σondition r2・6／ is θiVen by the fom∫ （・…〕・k．、9・k．、・・だ・、・yだΩ、・ −P、A，、九．【・凸］・・、A，、九、【鵬・yズP、A，、、．、・・k…S・k…k・・菱】・ is anηxηar・bitrary m力漉． 1∂hereΩ k PROOF・L・t B・b・・u・th th・t・f・r giv・nΩk・ （…2）．・、−PA，、、．、［・ピ・趨，、、ノ・k・・、・；］・ ・・i・t・・・・…ha・・．・／A・・…血ce％，、、．．1・・；］・、−M・ ・・一…♂・鵬have
B・・、一・・−A、＾1・P、A，、、。・エ・、】・らi、・・箒幻〃・−M・1…一・・ 伽・・B・ ・A「z） nM「・kノ・ ・ C㎝ver・ely・1・t B・・ be any・1㎝㎝t・f／A「Zノ・舶瓦九『血㎝β・・㎝b・ Tepresented by ・に％伽［・、に彪，、、．．・・tt・・k・1］・・曲抽i・afbm give・by・ettmgΩk＝B緑in〔2・12〕・
th・・efbre・any・1㎝・nt・f A「Zノ・ρωk・8k／can b・fOm・d by ｛・、・PA，、、．．［・；・yガ・、・k・・；】｝・・Pm，、、．．【・ズ・趨，、、．．・・k）・k・1］・ 吻ich yields （2．11）．「 一・’79 SECANT UPDATES OF QUASI−NE㎜MmHOOS ・ It should be nρted that the．卿te （2．11〕ca巫be written by the foτm −
B・・；・−P／A…．砲・1］％・…卿，・［劔∵ 』
ぬere％，、、。、［転・；」・・／A・・）・M・・k・・⊥・・／A・・胸・Yk・・k〃．孤・・． 『 ・・z…卿．・【Bk・Ωk】一％・z・．・［・B・・Ωk・一彪・・九・佃・・wl］・ 、． ’ T”us・ 刀E’s a輌e s°1・t’？・t°th・…b1㎝・f・r・’v・n， Stk・、 （2’13）c㌶ll 8ジ「B・’Stk’II・ sub」eet t°ぷZ／nQ「yだs・九一
・、，・gh慧麟：1㌶㌶｝｝；’．’㌫；，き瓢；？驚、．
・nly’f P／A・・M・、・。・［・；1ノ】−P／A綱・・、・．・［・；2ノ］・by（…3）・・fΩ・is set． t°the㎞゜m dense．c・r「ecti・n mat・i・tV3k・・th・・Bk．、 i・the c1・sest・p・士se ・pd…t・・h・㎞。岨d㎝・e輌・・Bk・ABk ’i・・h・F・・b・hi・s n・m・F・・i・・t紐ce・ setting Stk be th・ c・「recti・n m・t・i・・f th・B・・yd・n・XPd・t・（［1Dgives〔2」10〕； 3・ Sparse Symmetric し8）dates fbr （∼uasi−Newton Method 、 Since the Jacobian・matrix is s）㎜etric for the gradient equations， it is desi「able f°「the ’rPdate mat「ix．tg be sym｝ey「i・・Hence・we als°assume that （3．1〕 rZ，ゴ2 ∈ Z if alld only if （ゴ， iノ ε Z， …md furthermore，（i．幻〆Z． The purpose of this secti㎝is to find the matrix Bk．1曲i・h・ati・fi・・ （…〕Bk．、・／A・・ノ・Qryk・Sk・・／A。・ Where ／A．・｛M・RnX4・f−〃｝・ 佃yele鵬nt°f the affi”・ subset A「Zノ・Q「Yk・・k／nA．㎜be r印・esent・d by a linea「c°mbinati・n・f a speci・1・1・me・t i・A（Zノ・Qryk・Sたノ・膚。 and飢 element in．the subspace ／A「Z」 ・M「skノ・／A．・It i・㎞・m th・t th・T・i・t平bt・ （［15D i・・n・i・／A「Z／n』ρ「yだ・kノ・／A．・砲i・hi・．giv・nbyth・f・n・ ’@ 『
（…〕・、。、一’Eピ％，、九．［・k・；r；］・ ・
whe「e vk is a・・1・ti・n t・th・1inear・y・t・m・f・rβ丘r庖rZノ； 〔…〕・k・、一・ゼ・、・だ Φk−A、・P／A，、）．、［・k・；］・ N°te th・t the c・effi・i・nt m・t・i・Φk i・ ・Yi・MI・t・i・・nd・POssesses th・ ・par・ity80 ﹁ H．YABE， S． TAKAHASHI・AND．N．tt． YAMAKI
霊e霊二三蕊：三：隠tぷ51。㌢lfΦ：声；°漂煕煕
…y｛” ・n・V｛2」 be・・b・pace・・’spam’ ed by ’th−・…sθパ・h迦d・ha・ ・；’）≠・・…；’？一・，…Pe・t・…y・［lhen・占1ノー鵬㌔・・、％2に・−th・ ㎜・・i・・、・・P・・i・i舳f血・…n・he・・b・pace媛1ノ・・㎞ce・、・Ar・方曲・・・；・Yk−．・k・∂一・f…ゴdl2ノ・ 『．『
Thus the linear system （3．4） is consistent， which i㎎）1ies that v can be 瓦 expressed by（…）・ゼ・；・Yk 一・、・、・， ’
砲・・e層・Φ夏・・th・㎞re−P㎝…e・9・nera・土・ed・−se・f・k・地・・w’・b・・血・h・ n6xt theorem to defive the‘sparse sy㎜etric．update．・ 刑iO剛2・4・・鋤召微力Bピ・・y励・カぬ鋤』．・励・P・・S物限カカ醐・τ 、Z・．，批・α9・n・？・．Z ・pd・t・カm・鋤拗・qti・β・鋤・σ・nditi・・（3・2／i・9鋤・by ， the f・・m｛s．・ ， 、 ． ．． 、 、
（・・6）』㌦、・Bk…k・Yk．・、！ ．．．一％、，、九．［Bk・・、］・P、A，、九．［・、・；r菱］・ wh・・e Dk Z・α・鋤鋤卿・…〃mmetri・mdt・ix・nd‘ （…〕・、一・1・〃ピ％，，、．、［・、叫・k）・ 『 PROOF・L・t Bi b・・ueh that・f・・gi・・n Dた・〔・・8）．・・一％，、、．、［・k…k・｛・・kλ｛］’ ．
where
（…）・・λゼ．一Φ趨，、九．［・、］・k・ ． ・． ・
It is evident．thqt e・・／A「Zノ・／A。 by the sy㎜・t・ic st「uctu「e°f Z・孤d it ir easily ve「ified that °kλk ＝−P／A rZノ。Z［Dk］・たby the same a「gm・nt as the ab°鴨・ ・・nce P／A，、九．［・k・1・・kλ｛】・、一・kλk・‥・・B．・、一・・…．∈／A・・祠・、・・／A。・ C・nve「・ely・1・t・B…b・孤y・1㎝・・t・f／A「乞ノ・聴たノ・／A。・［ll・en・B・・ can・b・ written by ・に％，、九．【・緑・・k・菱 ＋・k・；］顧・h・、一一Φ払，、、．、．【B．．］・だSECANT UPDATES OF’qUASI−NEWTON「METHOI）S WhiCh is a ff°nn give・bγ・etti・g Dた一B・・ in（3・8レ lhe「efb「e・孤y・1㎝・武・f／A（Zノ・Qryk，・たノ・4。㎝・b・f・n・ed・by ． “｛・k・P、、（、、．．［㍊・Sk・1】｝・・／A，、、。、［D、 ＋・、・1・・、・；】・ Lettingμゼ・k・ Xk・・h・p・・rf i・c・nrp1・t・・ As mentioned in the previous section， the trpdate〔3．6）can be冊itten by
the fbm
B…−P／A…．エ［・羅・…｛yk・T］ ・ ・／・r・・咋・・／・。，・1・凸］・’ Wh・・eP／A、、、．．［・；・、・｛＋・〆・；〃ゾ】・・／4・・刷・k・・／A。戸・幽・…だ・k・・／A。・． ［［11us・㌔is a mi卯…1・ti・n・・th・p・・b・㎝・f・・gi・…だ 〔3・10）@ ：Z：㌘《》 ll Bt−rβた≠Dz∼1じ subゴeot to B＋ε ノtA・（Zノ ∩ Qryk． sたノ∩ ノtAs． 十 ’ ・t・・a・…h・岨・ha・・k．、・・だ・枠・；1り一・、。、・・k・・W・；2’，．・f孤・…y・fP／A脚・・、咋【・；1）］一％…咋・・／・。，・［・12ノ］・ 』∵
If Z is empty， that is， no sparsity condition is i町x）sed， we have ・ゼ［Z−s、・Tk／・・ll・、 ll；・］［Yk−Bk・ズDk・k】／dl・、 lrZ・． − Let°たsatisfy the「elati°n Dk・k ＝ yk 一 Bk・た・th・n・左一・・飢d・k．ヱーBk・．・た・ Hence， we have the s）㎜etric sparsification of the㎞om dense頑ate by 1・tting Dk b・th・㎞・wn’рр獅唐?@c…ecti㎝㎜t・i・in〔3・6）・［n・en・thi・i・th・ closest s）㎜etric sparse trpdate to the㎞oぬdense叩date in the Frobenius nom（Shanno I 14D． In the remainder of this section， some special updates are giv6n． EX卿LE 3． Toint［17］has consideredψe prob1㎝of findi㎎the matrix・1儒ご・嘘漂。W蒜灘三’蒜愁ζ1三蹴、罐t°
two modificatiOn of the identity matrix wh《）se inverse can、be written ln thefOm
〔・…）％1…・、・k・；・Y、・・羅咋・5
f・r・㎝eτだ・k・R ・nd hk・Rn・Th・n』i・eXPressib・・．q・・ 81．82・ ’ ．．Hc．’YABE，こS；．TAKAHASHI AND．N． YAMAKI・ （…2）Bk＋・一％・・・…、、。Sk・・験8・一∫・・ナ・P／A…．・［…；．・．・ぱ・一・・】・ satisfies the linear system Whereμ た Φkμた＝Yk−8た・た％rz九τ［P？’Sk’ ． ・kL−・幽一・、・、咋咋・Yk−・k・k・T・・ ・ ．yi−・・Yk−・、・ノ・瓦嘱・
．．．． ．・YI・（Y．k r・、・W（…；咋・ゑ．
孤dΦki・gi・・n i・（3・4）・1・parti・曲・the case°f㌦＝踊s discussed、 in ［15】， which is the update．（3．3）． The． ab◎ve result・is obtained by letting D瓦一一五k in（3：6〕・ 臥岨E4・A・p・gifi・砿・i・pk、甲y， e・qble．・・t・°btal” an eXPIicit． update． For instance， setting ’−・、一一、1、・瀬zうTA｛・Y・ ・・ Bk・k）］・ r’㌶rl’1＝rl騨た二。1；「餐「籔二’vesΦ酋鞠・s没
’ ・、．、一・、・・k・．P／A，、、，．［・k・菱r；］・ EXAMPLE 5． Oren and I・uenberger ［12］ have propose（l an effective familyll二tli隠1：’、。Bl二s隠he c°nc印t岬’t！’〔［IP’t｛e°f
〔…3）・、ゴ峡一・、・、羅r』ナ撤ル・』］』鞠㌶・、・ ．．
where ．’ ・ … 』 ・ ヒ ．． ・． 』 ‘ 』 ’．Vk一骸一・・』礁ノyだ． 、 ’
飢加た・φk are・calar・param・ter・・ln・th・ case・f・ゼ1・this fa「nily bec°mes the Davidon−Fletcher−Powe11 ．（DFP） update （｛7D．and the Broyden−Fletdhet− G・1df・・b・S㎞・（BFGS）卿t・（団）’f・r’．φた』一・孤dφに・・respecti・・ly’・． c…ide・顧i・stead・f・たi・（3・6）・L・tti・g・k b・・he c・rrectiO・ matrix of the Oren and『Luenberger family 〔3．13）．， we have the・s）㎜etric sparsification of the Oren and Lvlenberger fa珊ily． Note that a suitable choice ・f・h・parameter wk est・bli・h・・th麺V・τi㎝ワt・alinea「scaling°f the obj ective function f（x／ such that了r⑳ノ ＝of（x／ for some positive constant o， 砲en・鴨・th・i・i・i・1・mat・i・B、 i・伽・e・i・d⑤・nd・ntly・f th・fmcti°n飢d the same starting Point is used． Following to Oren ［11］，we can also present83． SECANT UPDATES OF QUASI−mm METHODS such w in the fbm． た ・、一・・一θ、咋㍍係、・ ・・k・y；・k／s｛・、・kl’・…k・［・，・】・ This invariancy property seems to be practical for the problems with large size・ However， it is an open problem whether the sparse update preserves the positive definiteness・ So it is questionable whether this sparse ㎎）date has the self−scaling property for the quadratic fmction． 4． Local and Superlinear Convergence Tt is卿ortant to show that an algorithm using the sparse quasi−Newton updates generates a sequence of points which converge to a solution x x． Lam［9］has sho㊥， by the bounded deterioration theorem of Broyden，［bnnis and肋r6［2］and the results of Demis and％rε［3］， that the Schubert method gene「ates the sequence｛・・た減i・h・・nverges 1・cally・・nd q−・uperlinearly t・xt・ Marwi1 ［10］ also proved， by the Kantorovich analysis， the local and q−super− 1inear convergence of this method． Toint ［16］ has shown that the sparse symmetric Broyden method， which employs a trust−region procedure to solve for the descent direction， converges superlinearly mder’ 唐盾高?@condiτions． Further， Demis and Walker［5］have proved’the local and q−superlinear convergence of the Schubert method and the sparse symmetric Broyden method， respectively， by an mified approach using the principle of l）omded deterioration． This section is concemed with the convergence of the method given血 EXAMPLE 3 0f the previous section． To analyze the convergence， we assume that 〔a〕 there exist ξ ≧ O and p ∈ rO3ヱ］ such that， for x ∈ 」V（xx）。 〔4・・〕 ll・ω一・rが川、・ξ ll x一司1》， ぬere N rx t） is an open convex neighborhood of⑳t， and that （b） ♂（xt） is non− singular． we need the f（）110wing result which is a special case of a more general theorem proved in ［2］ and ［5］．
・n・澱ン×㍗；i㌶；。sl蕊㌫㌘；1㌶㌘1㌶1。二
”ヱ⊂「u（x”）鋤ル2・・nt・in・・吻・…ing・Z・ny・m・t・i・… A・・ua・that th・㌘・αre n°nnega’iV?A6°nstants B・αnd・B・ sueh that for each「鋤♂唖鋤 ゜，Z・・−Bgω・
satisfies eVe「y B≠c u「x・ B） （4・・） ll・≠一・剛レ・r・・β、ar・・xゾノll・B−・r・ ・） 11F・β、・rx・xゾ カ・＠・≠ノー頑ll・一・斗H2・ll…≠一がll2｝・，84 、 へ ＾HごYABE元．．S．‘TAKmaSHI．AND N6．；YAMAKI und・㌘輪・・々P・』…拘r卿r・ro・力・th・r・ent・t・・nst・ηカ・ε〆δr ・励微ぽ」x、一・刈⊆・ε。鋤．．ll Bゴ」倒ll2＜δ。・』・擁・・θ＝・・rヱ・2ノ ＝1is wezz defined迦d conveTges q−ZineavZY to xt with
withα
た ，．∵： ：預・．「ぽ㌧1≧・ll・ぺ〆11・・、．．‥1．．：』∫．巴．・城』・・…｛ll・kl』｝・nd｛・ll・；11』｝卿卿伽・y b・唖・… ’
・L・t・た一・rxだxk＋ノ・．N・w w・have th・fb11・輌g th・・rem・ i：’．THEOREM 7ピ．Suppose that J satisfies the．’aSszanptions「αノαnd「わノ’ 」アτだ ふYk・nd hk’L．卿吻sθ… that3 f・r・ZZ lk・≡． ’： 』1”
・「・抽戸・．・鋤・ρ・n・1・nt・f・だ．”．』噛 ・滅i：≦・、ll・、“El−21・・‥、1≦』、ll・、IIZニヱfb）’ ・6；・ne9・t…．・…τ・nt・ ・．・・Pl・ρ2・・ゴ．1ほたll 2−・・． ・1 ．．ド．’・ ’． th・・垣c吻9励勿．d・fin・d・by「1・2／t・ith qk＝ヱand「3・12ノ．gene「ates a sequenee 励働・・n？．・tt9・r・Z9・α兄〃碗9rz仇θαw垣虎・ ・・R・・・…i・・c・・ar， by〔・），・ha…h・㎜・・…1’・…r・−2・m・…gen一 当u・s・Lett’n・ X… and X・ax’be the㎜11est孤d． the la「gest−e’genva’ues°f ， respectively， we have ． ． ・ ・ ．∴．㌔、。一・・ご｛・菱・・、・kt・W−ll・魂ll・、・k・・Y∼、ll、｝… and ジ ． ． ・＿一・・S｛・｛r・、・、・・Yk・、ノ・ll・kll、ll・k・k ＋・Ykhkll、｝… ・・f・・1㎝・麺・he ass卿・i・n（d）， fg・・mP・・il・k II、・． t坤t ・菱r・k・、・・W… ll・k l』ll・、・、・・Y．khk・ll，・ …ぬ・d四・飢te・・th・Pe・i・i・・d・f血・・…5・・f尼 ．
・mce ll吃111、一・＿…ll・、11，ll・k・、…khkll，・1州、一・／・n、、η ≦1／で1− D1・kllall・k・k ’ 2Ykhkll・ノ飢d ll・kll・r2σ瓦・the「e exist n°nnegative・・n・t孤・・ζ、ahd C2 by〔d）・・Ch・that ．t．．・
（…） IL吃ヱII、・…、磁飢d｜1・・、・ll、…ζ2咳・．
F・r”・／A「zノ・Q「yだ・k／n／A。・ ． ．SECtSNT UP］〕ATES OF・qUASI−NEWTON ME「田OI冶 〔4．4〕 ≦ ・ ’ 1 By the ’nean value the°「em・・Yk＝ B」「Xk≠tSk’dt］sズ
and・E・ ＝〃一・・が・血（…）…螂・‖耐’1
11・llF’・． w・・hav・㌧’：
〔4・5）@ ≦ 一♂剛1・。％
≦ 1子 ≦ where K is a constant such that ≦ By’（4．3）have・fb・s㎝・ζ3≧0孤dζ4≧0・
ll・k，、−」r釧いr・・．ζ3●11’βゼ・r釧いζ4媛・ Therefbre， the theorem is proVed． llβ・ガ刷1・． ・k ll％・・∫・輪旭．．Wk「Bk’♂「勒1㌧％・’ 1咳 ．Wk・”一働・llp．・k・ ［∫ ・・t〃一∫；…、…t・k・・dt lr㌦ll211’cl：1’P’ ’・nd’ ”一・ll…ll・ll・ll・ぺ・r・d”×n・ −『二』
ll・、ガ・剛1。／11・、U、 ll㌔ ‥
11・Bk 一♂酬ll互1已
ll吃111、・II ・k−♂r… ll。・’・ll・、ll，九 ll鴨・ll・・kll、・”迦・（…），・・ To obtain yhe．qrsXperlinear．convergence of the． algorithm，．． we use、 the、 、the°「en given by Dennis．皿d吻「6［3］・ ．．．．’ ，．
U…跡8・SUPP・8θ微力、」・ati・fies協αS8鋤P励η8ωand r●ノ・αη4鋤 s°me Xl E N侮tノ・the seq・e・eθ「ヱ・2ノ励肋た＝1 i・ ・u・れ泌咋d「がノZs ωθZZ繊鴫苫た綱αη4｛Xk｝°°nve「ges・q−Zi・・α吻力・・⑭・・…’・「°・1ノ・ 』｛Xk｝・・・…g・・q−・up・・況…吻力・xt with紗・・仁司 ／1・ダxt11・7°、、．、
分αη40nZyザ 』 1ド・ 1「 ゴ ”− 一 ．．・．
（4・6〕忽ll’βゼ」「xt））skll・／ll s・1』’＝°・ ・ 馳』．
Then we have the next resUlt fbllowing to Dennis and Wall（er ［5］． THBOREM 9． SupPose th zt theαsszollF）tions oアTheor醐 7 heZd． 1ワ昭n the seque・・θ｛Xk｝⑭・繊・d’b91 th’e dZg・ni伽f・．・2励幼αゼ・・nd’Y3・・2ゾ⑳⑭gθs q−superzinea吻力・xt． 8586 H． YABE↓ S． TAKAHASH．I AND N． YAMAKI PROOF． Since ． ． ． ・ ． ’ ll・Bk−・・当ll・／ll・・lia−ll％・・賊’βズ♂「・t”・・ll・／ll・・k ll・
．，、 ．≦K’・岬夏・ll％卿、・Bk−．・剛1・．． ・i
曲ere K’i・ac・n・t飢・・uCh・’・h・t腫1』≦K’1叫f・TM・♂×n・i・i・・ ・uff’・’・nt t・p・・v・・ha・忽ll％・・、・．blk「Bk−♂剛1・． ・、 ’一゜・． By us’ng the ・血ilar p「°°f as The°「em 4・‘川5］・We c皿P「°ve this中e°「e匝・ S’nce P／A・…卿・／As・残％・・、・ぺ＝P／A・・M・k・・／A。・㍗孤d 〔…）ll％・・備〃II・． ・k・ll叫％−ll ph・・幽・ll多．・、／・・ll・11・．Wklf・…Rn×η・w・・ha…f・r〃−Bk−」rが九 、 一．．．
II・Bk・ゴ」「当ぺll％・・k・．Vk「βズ」剛Fぺll亙蝿 ≦ll・Bk−」副セペll互lk喉・ −ll碗・・凸・・ズ…り・1亘履…‖・ズ刷蹴
． Furthe士tn（）re， the s imilar evaluation．as the proof in Theorem 7 yields （…）・、．、・・…、・2〃・・ζ2・；川k・・、・・’・・、・；）・2 士w 』・ ・…． 一解ζ2吻ψi／・・・…、・￡川k・
k ”．一 ； 1k 』… ’
’‘「、三、「2≠・・6争「！’ζ2弓ノノ「・・r・・ゴ三、σ5ノ・、 lthere ・・k−ll％・・凸・Bk−・・叫ペゼ1甲‘・川じ㎝dζ・＝・ξ「1’・・’Zノ・ Since｛xk｝・・nverg・・q−・inear・y・・xS i・劔・0・・th・t中ere・・xi・t・a・・n− ・・g・tive c・n・t孤t n・・ch t｝温tηた≦ηf・r k．＝ユ・2・…・Then・by（4・8）・ ． ψi／［・・…、弓川・nk−nk．、・ζ6鵬 ・ ぬere・，一・ζ、・・、・・1ζ2・？i…ζ5…ζ28、・…P・eq・・n・・y・⊇・・ 2、￠・［・・・・…e川】・…6三磁 ’Wh’ch麺1’es that 噬ﾕ・＝°・th’s c°’「「P’e・tes the P「°°f’ 「』87 SI］CANT UPDATES OF QUASI一㎜METHODS
