Matematika | Felsőoktatás » Galántai Aurél - Projekciós módszerek lineáris és nemlineáris egyenletek megoldására

Projekciós módszerek lineáris és nemlineáris egyenletek megoldására MTA Doktori értekezés tézisei Galántai Aurél Miskolci Egyetem 2003 1 I. A kitu ý zött kutatási feladat rövid összefoglalása Az értekezés Ax = b alakú lineáris és F (x) = 0 ¢ ¡ A ∈ Rm×m , det (A) 6= 0 ´ ³ T F : Rm Rm , F (x) = [f1 (x) , . , fm (x)] (1) (2) alakú nemlineáris egyenletrendszerek projekciós numerikus módszereit vizsgálja. A vizsgálatok célja: hatékony numerikus módszerosztályok kifejlesztése, kvalitatív tulajdonságaik (konvergencia, stabilitás, hatásmechanizmus, hatékonyság, stb.) feltárása, valamint speciális tulajdonságú algoritmusok elýoállítása A tanulmányozott projekciós módszereket olyan konjugált irány módszerekként is lehet jellemezni, amelyekben a konjugált irányok elýoállítása az Egerváry-féle rangszámcsökkentýo eljárás [32] segítségével történik. Ez a kapcsolat szükségessé tette az Egerváry-féle

rangszámcsökkentýo eljárás, valamint mátrixok multiplikatív háromszög felbontásainak a vizsgálatát A rangszámcsökkentéssel és a háromszög felbontásokkal kapcsolatban elért eredmények önmagukban is érdekesek és sok egyéb területen felhasználhatók. A vizsgált numerikus módszerek két további aspektusát is tanulmányozzuk az értekezésben. A kapott numerikus megoldások jóságának ellenýorzésére Auchmuty [10] utólagos hibabecslýo eljárását vizsgáljuk és terjesztjük ki nemlináris egyenletrendszerek esetére is. A Neumann János és mások ¡ ¢ által kifejlesztett alternáló ortogonális projekciók módszerének [29] konvergencia sebességére O n3 mý uveletigényýu felsýo becsléseket adunk a véges n-dimenziós esetben. II. Az elýozmények, az elvégzett vizsgálatok, kisérletek és a feldolgozás módszerei Az értekezés második fejezetében mátrixok multiplikatív háromszög felbontásait vizsgáljuk. A háromszög

felbontások (faktorizációk) a Gauss tipusú egyenletrendszer megoldó eljárások elýotérbe kerülésével váltak fontossá. A Gauss-féle eliminációs eljárás hasznosságát az 1940-es években ismerték fel Hotelling, Neumann János, Goldstine, Turing, Fox, Huskey és Wilkinson munkásságának nyomán. Neumann János és Goldstine [90], valamint Turing [103] azt is felfedezték, hogy a Gauss elimináció impliciten egy LU (LDU ) felbontást számít ki általános A mátrix esetén és egy LDLT felbontást szimmetrikus pozitív deÞnit A mátrix esetén. Egy A ∈ Rn×n mátrix LU felbontásán a mátrix A = LU alakú szorzatfelbontását értjük, ahol L alsó és U felsýo háromszög alakú mátrix. Az LU felbontás, ha létezik, nem egyértelmý u. Turing [103] igazolta a következýo ismert eredmény elégséges részét: A nemszinguláris A ∈ Rn×n mátrixnak akkor és csak akkor létezik egyértelmý u A = LU felbontása, ahol L egység alsó és U felsý o ¢ ¡

,k ominor mátrixa nemszinguláris (v.ö [65], [72], [71]) Ha háromszög mátrix, ha A összes A 1,. 1,. ,k fý egy nemszinguláris mátrixnak van LU felbontása, akkor a mátrixot erýosen nemszingulárisnak is nevezzük. Az egyértelmý u A = LDU (A = LDLT ) felbontásban L egység alsó háromszög mátrix, D diagonális, U pedig egység felsýo háromszög mátrix. Egy szimmetrikus és pozitív deÞnit A ∈ Rn×n mátrix Cholesky felbontásán az A = LLT szorzatfelbontást értjük, ahol L alsó háromszög mátrix. A háromszög felbontásokon alapuló numerikus eljárások (Gauss-tipusú egyenletrendszer megoldók, a sajátérték probléma LR módszere, rangszámítási eljárások, stb.) numerikus stabilitását a háromszögfelbontások perturbációi erýosen befolyásolják. Háromszögfelbontások elsýo perturbáció analízisét Neumann és Goldstine [90], [91], valamint Turing [103] adták, habár implicit formában. 2 Broyden [14] mutatta meg elsýoként, hogy az

LU felbontás tényezýoi erýosen rosszul kondícionáltak lehetnek még jól kondícionált mátrixok esetén is. Háromszög felbontások perturbációit Barrlund [11], Bhatia [12], Chang és Paige [19], [20], Chang, Paige, Stewart [21], Drmaÿc, Omladiÿc, Veseliÿc [31], Stewart [98], [99] és Sun [100], [101], [102] vizsgálták (lásd még [71]). Eredményeik bizonyos nemlineáris perturbációs egyenletek megoldásainak felsýo becslései, vagy linearizáción alapuló közelítýo felsýo korlátok. Az értekezésben megoldjuk az LU , LDU, LDLT és Cholesky faktorizácók nemlineáris pertubációs egyenleteit és elméletileg pontosan megadjuk a faktorok perturbációit. Az eredmények minden olyan perturbáció esetén érvényesek, amelyben a nemszingularitás és az LU felbonthatóság fennmarad. Az egzakt perturbációs eredményeket felsýo (norma és komponensenkénti) korlátok levezetésére is felhasználjuk A kapott felsýo korlátok az esetek többségében

javítják az ismert korábbi felsýo korlátokat. A lokális komponensenkénti felsýo korlátok iteratív úton is megkaphatók, amelyek bizonyos esetekben monotonok a részben rendezésben. Az LDU felbontásra korábban perturbációs eredmény nem volt ismert. Az értekezés harmadik fejezetében az Egerváry-féle rangszámcsökkentýo eljárást vizsgáljuk. A rangszámcsökkentýo eljárást elsýoként Wedderburn [104] fedezte fel kvadratikus alakok Lagrange-féle redukciójával kapcsolatban. Egerváry a róla elnevezett algoritmust egy sor dolgozatban fejlesztette ki 1953 és 1956 között. A rangszámcsökkentést a lineáris algebra számos területén használják Az eljárás történetét nagyjából tényszerý uen tartalmazza Hubert, Meulman és Heiser [82] dolgozata. Egerváry szerepének további pontosítását is tartalmazzák az [57] és [59] dolgozatok. Legyen H1 = H, Xi ∈ Rn×li , Yi ∈ Rm×li , li ≥ 1 és tegyük fel, hogy YiT Hi Xi nemszinguláris i = 1,

2, . , k esetén A rangszámcsökkentý o eljárás: ahol rank (H) ≥ Minthogy ¡ ¢−1 T Yi Hi Hi+1 = Hi − Hi Xi YiT Hi Xi (i = 1, 2, . , k) , (3) Pk i=1 li . rank (Hi+1 ) = rank (Hi ) − li = rank (H) − az eljárás befejezýodik, ha Hk+1 = 0. Ekkor rank (H) = A Hk+1 mátrix az Pk i X lj , j=1 i=1 li . Hk+1 = H1 − QD−1 P T , alakba írható, ahol és £ ¤ P = H1T Y1 , . , HkT Yk , Ha Hk+1 = 0, akkor a Q = [H1 X1 , . , Hk Xk ] ¡ ¢ D = diag Y1T H1 X1 , . , YkT Hk Xk H = QD−1 P T bázisfaktorizációt kapjuk. 3 (4) (5) (6) A rangszámcsökkentýo eljárás iránti megújult érdeklýodést (lásd pl. [23], [24]) az ABS módszerek [5], [7], [8] megjelenése váltotta ki. Az ABS módszerek konjugálási eljárása a rangszámcsökkentésen alapul. Az ABS módszerek kutatása [47], [43], [45] tette szükségessé a rangszámcsökkentýo eljárás értekezésben foglalt további vizsgálatát. A rangszámcsökkentý o eljárást

zérusosztó mentesnek (breakdown free) nevezzük, ha YiT Hi Xi nemszinguláris minden i = 1, 2, . , k esetén A harmadik fejezetben szükséges és elégséges feltételt adunk a rangszámcsökkentýo eljárás zérusosztó mentességére, megadjuk a Hk mátrixok két kanonikus alakját és az eljárás által elýoállított bázisfaktorizációt a paraméterek függvényében. Ezt az eredményt felhasználva szükséges és elégségséges feltételeket adunk bizonyos nevezetes faktorizációk elýoállíthatóságára, valamint jellemezzük a rangszámcsökkentýo eljárás meglepýo belsýo konjugálási tulajdonságait. Valójában azt az eredményt kapjuk, hogy minden bázisfaktorizáció egy LDU felbontáshoz kapcsolódik és így a rangszámcsökkentéssel történýo konjugálás háromszög felbontáson alapul. Ugyancsak megmutatjuk, hogy a rangszámcsökkentés alkalmas szimmetrikus mátrixok inerciájának a meghatározására és speciális esetként tartalmazza a

Cottle-féle inercia számító eljárást is [25]. Az értekezés negyedik fejezetében a konjugált irány módszereket vizsgáljuk, amelyek véges befejezésý u projekciós módszerek. A konjugált irány módszerek fejlesztését Hestenes, Stiefel, Lánczos és mások munkássága indította el az 1950-es években [34], [67]. 1973-ban Stewart [97] megadta a véges befejezésýu konjugált irány módszerek lehetséges legáltalánosabb osztályát. 82. DeÞníció Legyen A ∈ Rm×n , V T AU nemszinguláris, U = [U1 , U2 , , Ur ] ( Ui ∈ Rn×li ) és V = [V1 , V2 , . , Vr ] ( Vi ∈ Rm×li )£ Az (U,¤V ) mátrixpár blokk A-konjugált (az {l1 , l2 , , lr } r partíció szerint), ha az L = V T AU = ViT AUj i,j=1 mátrix blokk alsó háromszög alakú. Az (U, V ) mátrixpárt blokk A-biortogonálisnak (bikonjugáltnak) nevezzük, ha az L = V T AU mátrix blokk diagonális. A P mátrix A-ortogonális, ha a (P, P ) mátrixpár A-biortogonális. Tegyük fel, hogy A, U, V ∈

Rm×m nemszingulárisak és az (U, V ) mátrixpár blokk A-konjugált az {m1 , m2 , . , mr } partíció szerint (1 ≤ r ≤ m) CDM algoritmus (Konjugált irány módszer) x0 ∈ Rm for k = 1, . , r rk−1 = Axk−1 − b dk = (VkT AUk )−1 VkT rk−1 xk = xk−1 − Uk dk end Stewart [97] és Broyden [16] igazolták, hogy a CDM algoritmus tetszý oleges x0 ∈ Rm esetén akkor és csak akkor fejezý odik be legfeljebb r lépésben ( Axr = b), ha az (U, V ) mátrixpár A-konjugált. Az Abaffy, Broyden és Spedicato [2], [5], [6], [7], [8] által kifejlesztett ABS módszer a konjugált irány módszer és a rangszámcsökkentésen alapuló ”ABS konjugálás” kombinációja. Az ABS módszer blokk változata [3] a következýo: Blokk ABS módszer x1 ∈ Rm , H1 = I for k = 1, . , r Pk = HkT Zk (Zk ∈ Rm×mk ) ¡ ¢−1 T V (Axk − b) xk+1 = xk − Pk VkT APk ¡ T k T ¢−1 T T Hk+1 = Hk − Hk A Vk Wk Hk A Vk Wk Hk (Wk ∈ Rm×mk ) end 4 Egy partikuláris ABS módszert

a V = [V1 , . , Vr ], Z = [Z1 , , Zr ] és W = [W1 , , Wr ] paraméter mátrixok (és az {m1 , m2 , . , mr } partíció) deÞniálnak Az ABS konjugálási algoritmus alakja: ABS konjugálás H1 ∈ Rm×m , det (H1 ) 6= 0 for k = 1, . , r Pk = HkT Zk ¡ ¢−1 T Hk+1 = Hk − Hk AT Vk WkT Hk AT Vk Wk Hk end Itt a Hk mátrixok számítása a rangszámcsökkentýo eljárással történik az Xk = AT Vk és Yi = Wi (k = 1, . , r) paraméterválasztás mellett Könnyen belátható, hogy a (P, V ) mátrixpár Akonjugált A negyedik fejezetben megmutatjuk, hogy a konjugált irány módszerek rekurzív GaljorkinPetrov projekciós módszerekként is megkaphatók. Ugyancsak igazolunk néhány, a konjugált irány módszerek abszolút, ill. reziduális hibájára vonatkozó becslést DeÞniáljuk az ABS módszerek két részosztályát (általánosított implicit LU, szimmetrizált konjugált irány ABS), amelyekre kvalitatív jellegýu tételeket igazolunk. Broyden [15], [16], [17]

nyomán vizsgáljuk a konjugált irány módszerek stabilitását. Igazoljuk a rangszámcsökkentésen alapuló konjugálási (bázisfaktorizációs) eljárás stabilitását A rangszámcsökkentésen alapuló konjugálási eljárás azonos az általánosított implicit LU ABS módszer konjugálásával. Az ötödik fejezetben nemlineáris egyenletrendszerek projekciós módszereit vizsgáljuk. Vizsgálatainkban a Householder-Bauer féle projekciós módszer [73] alábbi nemlineáris általánosításából indulunk ki: ¡ ¢−1 T xk+1 = xk − Pk VkT Ak Pk Vk F (xk ) (k = 0, 1, . ) , (7) ahol Ak ∈ Rm×m , Pk , Vk ∈ Rm×mk és mk ≤ m. Ez az iteráció magában foglalja a Newtonés Newton-szerý u módszereket, a nemlineáris Kaczmarz módszert, valamint a nemlineáris ABS módszereket és általánosításaikat. Ha az Im m × m egységmátrix az ¡ ¢ Ei ∈ Rm×mi , i = 1, . , r (8) Im = [E1 , . , Er ] alakban van partícionálva, akkor a relaxált nemlineáris blokk

Kaczmarz módszer £ ¤−1 T Ei F (xk ) , xk+1 = xk − µAT (xk ) Ei EiT A (xk ) AT (xk ) Ei (9) alakú, ahol k ≥ 0, 0 < µ < 2 és i ≡ k (mod m) + 1. A nemlineáris ABS módszerek elsýo alakját Abaffy, Galántai és Spedicato [4], ennek blokkosított általánosítását pedig Abaffy és Galántai [3] fejlesztette ki. A nemlineáris ABS módszerek tovább fejlesztései Abaffy [1], Deng, Chen [26], [27], Galántai, Jeney [61], [62], Huang [75], [74], [76], [77], [81], [78], [79], [80], Jeney [84], [83], [85], [86], [88], Ge Rendong [66], Spedicato, Chen, Deng [96], [22] és Zhu [106] nevéhez fý uzýodnek. Az ötödik fejezetben megadjuk a konjugált irány módszerek egy olyan nemlineáris általánosítását, amely tartalmazza a nemlineáris ABS módszerek különbözýo változatait. Igazoljuk a Kaczmarz módszer és a nemlineáris konjugált irány módszerek lokális konvergenciáját lényegében a Newtonmódszer konvergencia feltételei mellett. A

konvergencia bizonyítás, amely egy speciális projekciós technikán alapul, lehetýové teszi nemcsak az iterációk hatásmechanizmusának leirását, hanem a 5 Kaczmarz tipusú módszerek és a nemlineáris konjugált irány módszerek eltérýo konvergencia tulajdonságainak magyarázatát is. Részletesen tárgyaljuk a nemlineáris ABS módszerek lokális konvergencia tulajdonságait Az ABS módszerek egy részosztálya esetében konvergenciát igazolunk részben rendezésben és megmutatjuk, hogy egy speciális esetben az eljárás a Newton módszernél nem lassúbb. Részletesen tárgyaljuk az [61], [62] dolgozatokban kifejlesztett kvázi-Newton ABS módszereket és a rájuk vonatkozó számítógépes összehasonlító teszteléseket. Ez utóbbi eljárások egyikének FORTRAN nyelvý u programja az értekezés függelékében megtalálható. A fejezetben a blokk implicit LU ABS módszerek két alkalmazását mutatjuk be speciális egyenletrendszerek és optimalizálási

feladatok megoldására. A hatodik fejezetben lineáris egyenletrendszerek közelítýo megoldásainak Auchmuty-féle utólagos hibabecslésével, valamint az alternáló projekciók módszerének konvergencia sebességével foglalkozunk. Legyen ω = A−1 b az Ax = b egyenlet pontos megoldása, x ∈ Rn pedig egy tetszýoleges közelítýo megoldás (r (x) 6= 0). Auchmuty [10] hibabecslése a következýo: µ 1 ≤ p ≤ ∞, kr (x)k22 kx − ωkp = c T kA r (x)kq ahol 1 ≤ c ≤ Cp (A) és Cp (A) = sup y6=0 ° T ° ° −1 ° °A y ° °A y ° q p kyk22 ¶ 1 1 + =1 , p q (10) . (11) Az alternáló projekciók módszerének számos alakja és alkalmazása létezik [29], [37]. Legyenek M1 , M2 ,. , Mk a H valós Hilbert-tér zárt alterei, M = ∩ki=1 Mi és Pi = PMi (i = 1, , k) A PM ortogonális projekciót metszet projekciónak nevezzük. Tetszýoleges x ∈ H esetén a PM x projekciót az alternáló projekciók módszere úgy közelíti, hogy a pontot ciklikusan

projektálja az egyedi alterekbe. A módszer alakja tehát a következýo: x0 = x, xj+1 = Pi xj (i ≡ j (mod k) + 1) . (12) A következýo tétel, amelyet Halperin [69] igazolt, Neumann János k = 2 esetre vonatkozó eredményének általánosítása. 151. Tétel (Halperin) Legyenek M1 , M2 , , Mk a H valós Hilbert-tér zárt alterei, M = ∩ki=1 Mi , és Pi = PMi ( i = 1, . , k) Tetszý oleges x ∈ H esetén fennáll, hogy n lim (Pk Pk−1 · · · P1 ) x = PM x. n∞ (13) A konvergencia sebességét Aronszajn [9], Deutsch [28], Franchetti és Light [35], Smith, Solmon és Wagner [94], Kayalar és Weinert [89], valamit Deutsch és Hundal [30] becsülték az alábbi altér szög fogalom alkalmazásával. 152. DeÞníció (Friedrichs) A H Hilbert-tér M és N alterei közötti α (M, N ) ∈ [0, π/2] szöget a n c (M, N ) = sup |hx, yi| | x ∈ M ∩ (M ∩ N )⊥ , kxk ≤ 1, o (14) ⊥ y ∈ N ∩ (M ∩ N ) , kyk ≤ 1 mennyiséggel deÞniáljuk, ahol c (M, N) = cos

(α (M, N )). A k ≥ 2 esetben a legismertebb sebesség becslés a következýo [94]. 6 154. Tétel (Smith, Solmon, Wagner) Legyenek M1 , M2 , , Mk a H valós Hilbert-tér zárt alterei, M = ∩ki=1¡Mi , és Pi = P¢Mi ( i = 1, . , k) Legyen továbbá PM H ortogonális projekciója M -en. Ha θj =α Mj , ∩ki=j+1 Mi , akkor minden x ∈ H és n ≥ 1 egész szám esetén fennáll, hogy k(Pk · · · P2 P1 )n x − PM xk ≤ cnSSW kx − PM xk (15) ´1/2 ³ Q 2 ahol cSSW = 1 − k−1 . j=1 sin θj Ez a becslés igen hasznos a számítógépes tomográÞában és egyéb alkalmazásokban [94], [70]. Alkalmazásának a nehézségét az jelenti, hogy a θj szögek számítása még véges dimenziós terek esetén is komoly probléma. A hatodik fejezetben az Auchmuty-féle hibabecslés különféle tulajdonságait elemezzük és részben elméleti vizsgálatokkal, részben pedig összehasonlító számítógépes tesztelésekkel megmutatjuk ¡ ¢ a hibabecslýo eljárás

gyakorlati értékét. Végül pedig O n3 mýuvelettel kiszámítható felsýo becsléseket adunk az alternáló projekciós módszer konvergencia sebességére véges n-dimenziós terek esetén. Az értekezésben felhasznált vizsgálati módszerek a lineáris algebra, a mátrix analízis, a numerikus analízis és az optimalizálás körébe tartoznak, amelyeket ”numerikus szoftvermérnöki” technikák (programfejlesztés, tesztelés) egészítenek ki. III. A tudományos eredmények rövid összefoglalása és az eredmények alkalmazása 3.1 Háromszög faktorizációk A következýo jelöléseket használjuk. Adott A mátrix esetén Ak , A|k , Ak és Ak| jelöli az A elsýo k sorából, elsýo k oszlopából, utolsó k sorából, ill. utolsó k oszlopából álló részmátrixot Legyen A = [aij ]ni,j=1 . Ekkor diag (A) = diag (a11 , a22 , . , ann ) , tril (A, l) = [αij ]ni,j=1 , (16) αij = ½ aij , i ≥ j − l , 0, i < j − l (0 ≤ |l| < n) (17) βij = ½

aij , i ≤ j − l , 0, i > j − l (0 ≤ |l| < n) . (18) és n triu (A, l) = [βij ]i,j=1 , Speciális esetekben a tril (A) = tril (A, 0), tril∗ (A) = tril (A, −1), triu (A) = triu (A, 0) és triu∗ (A) = triu (A, 1) jelöléseket használjuk. Legyen ei ∈ Rn az i-ik egységvektor, I (k) = Pk Pn T (k) = 0 (k ≤ 0). Hasonlóképpen legyen I(k) = i=k+1 ei eTi (0 ≤ k < n), i=1 ei ei (1 ≤ k ≤ n), I I(k) = 0 (k ≥ n). Vegyük észre, hogy I (n) = I = I(0) és I(k) + I (k) = I Tetszýoleges A ∈ Rm×n esetén legyen m,n |A| = [|aij |]i,j=1 ∈ Rm×n . Valós vektorok és mátrixok részben rendezését a következýoképpen deÞniáljuk. 7 (19) 163. DeÞníció Legyen A, B ∈ Rm×n A ≤ B akkor és csak akkor, ha aij ≤ bij ( i = 1, , m, j = 1, . , n) Az M -mátrixok LU és LDU felbontásának monotonitását mondja ki a következýo eredmény. 9. Tétel Legyen A és B M-mátrix, amelyre A ≤ B Tegyük fel, hogy A nemszinguláris, vagy

irreducibilis szinguláris és B nemszinguláris. Legyenek A = LA VA és B = LB VB az A és B LU felbontásai, amelyekben LA és LB egység alsó háromszög mátrixok. Ekkor fennáll, hogy LA ≤ LB , VA ≤ V B . (20) o háromszög mátrixok, DA és DB Ha VA = DA UA és VB = DB UB , ahol UA és UB egység felsý diagonális mátrixok, akkor DA ≤ DB , UA ≤ UB . (21) eL eT Stieltjes mátrixok a hozzájuk tartozó Cholesky 11. Következmény Ha A = LLT és B = L e felbontásokkal és A ≤ B, akkor L ≤ L. Tetszýoleges nemszinguláris A ∈ Rn×n márix esetén létezik az A = QA RA egyértelmý u QRfaktorizáció, ahol az RA fýoátlója csak pozitív elemeket tartalmaz. Legyen M, N ⊂ Rn két altér Az alterek távolságát a d (M, N ) = kPM − PN k2 (22) mennyiséggel deÞniáljuk, ahol PM és PN ortogonális projektorok az M, ill. N alterekre Jelölje továbbá θk (M, N) a k-ik altérszöget az M és N altér között. A Turing-féle algebrai karakterizációtól

eltérýo geometriai jellemzést adunk mátrixok LU felbontásának létezésére 15. Tétel A nemszinguláris A ∈´ Rn×n mátrixnak akkor és csak akkor van LU felbontása, ha QA ³ ³ ´ ¡ ¢ kielégíti az θk R QkA , R I |k < π/2 feltételt minden k = 1, . , n − 1 esetén Ezzel ekvivalens a ³ ³ ´ ³ ´´ d R QkA , R I |k < 1 (k = 1, . , n − 1) (23) feltétel. Ismeretes, hogy ha egy nemszinguláris A mátrixnak nincs LU felbontása, akkor mindig van egy P permutáció mátrix, hogy a P A mátrixnak már van LU felbontása. Minthogy P A = (P QA ) RA szintén egy QR-felbontás, a P -vel való szorzás (tkp. sorcsere) a mátrix QA ortogonális részét ”javítja”, amennyiben távoltartja a π/2 szöget mint altérszöget. Jelöljön a továbbiakban L1 egység alsó, U1 pedig egység felsýo háromszög mátrixokat és legyen ³ ´−1 Pk (B) = I(k) I + BI (k) (k = 1, . , n) (24) A Pk (B) mátrix n − k rangú projektor. A következýo tételek

multiplikatív háromszög felbontások elméletileg pontos perturbációit adják meg. 19. Tétel Tegyük fel, hogy A és A + δA nemszinguláris és létezik A = L1 U és A + δA = −1 (L1 + δL1 ) (U + δU ) alakú LU felbontásuk. Legyen B = L−1 . Ekkor a δL1 és δU perturbá1 δA U ciókat a δL1 = L1 X1 és δU = Y U kifejezések adják meg, ahol X1 ek = Pk (B) Bek (k = 1, . , n) (25) és £ ¡ ¢¤T eTk Y = eTk B Pk−1 B T 8 (k = 1, . , n) (26) A korábbi perturbáció becslések a kBk < 1, illetve ρ (|B|) < 1 feltételek mellett érvényesek. Mi csak az tesszük fel, hogy I + B nemszinguláris és van LU felbontása. 25. Tétel Tegyük fel, hogy A és A + δA nemszinguláris és létezik A = L1 DU1 és A + δA = −1 . Ekkor a δL1 , δD (L1 + δL1 ) (D + δD ) (U1 + δU1 ) alakú LDU felbontásuk. Legyen B = L−1 1 δA U és δU1 perturbációkat a δL1 = L1 X1 , δD = ΓD és δU1 = Y1 U1 kifejezések adják meg, ahol X1 ek = Pk (B) Bek és (k =

1, . , n) , ¡ ¢¤T £ eTk Γ = eTk B Pk−1 B T ek eTk £ ¡ ¢¤T D eTk Y1 = eTk D−1 B Pk B T (27) (k = 1, . , n) (28) (k = 1, . , n) (29) 26. Tétel Tegyük fel, hogy A ∈ Rn×n és A + δA ∈ Rn×n szimmetrikus, pozitív deÞnit mátrixok, amelyeknek Cholesky faktorizációi A = RT R és A + δA = (R + δR )T (R + δR ) alakúak. Legyen b = R−T δA R−1 . A δR perturbációt a δR = ΩR kifejezés adja meg, ahol B és ³ ´T ³ ´ b b k B eTk Ω = (1 + γk )1/2 − 1 eTk + (1 + γk )1/2 eTk BP ³ ´T b ek b k−1 B γk = eTk BP (k = 1, . , n) (k = 1, . , n) Legyen p (B) = max0≤k≤n kPk (B)k2 . Megmutatható, hogy s kBk22 p (B) ≤ 1 + (kBk2 < 1) . (1 − kBk2 )2 Ha I + B nemszinguláris és van I + B = LI+B UI+B alakú LU felbontása, akkor a ° ° ° ° ° kPk (B)k2 ≤ °I(k) LI+B °2 °I(k) L−1 I+B ≤ κ2 (LI+B ) (30) (31) (32) (33) és ¯¯ ¯ ¯ ¯ −1 ¯ ¡ −1 ¢ ¯ ¯ ¯ |Pk (B)| ≤ ¯I(k) LI+B ¯ ¯I(k) L−1 I+B ≤

|LI+B | LI+B = κSkeel LI+B (34) korlátok ”minden” B-re érvényesek. Az egzakt perturbáció kifejezésekbýol normában az alábbi felsýo korlátokat vezethetjük le. 36. Tétel Tegyük fel, hogy A és A + δA nemszinguláris és létezik A = L1 U és A + δA = −1 . Ekkor fennáll, (L1 + δL1 ) (U + δU ) alakú LU felbontásuk. Legyen B = L−1 1 δA U ¡ hogy ¢ kδL1 kF ≤ kL1 k2 kX1 kF és kδU kF ≤ kUk2 kY kF , ahol kX1 kF ≤ p (B) kBkF és kY kF ≤ p B T kBkF . Fennállnak továbbá az kδL1 − L1 tril∗ (B)kF ≤ kL1 k2 p (B) kBk2 ktriu (B)kF (35) és ¡ ¢ kδU − triu (B) U kF ≤ kU k2 p B T kBk2 ktril∗ (B)kF 9 (36) becslések is. 37. Tétel Tegyük fel, hogy A és A + δA nemszinguláris és létezik A = L1 DU1 és A + δA = −1 (L1 + δL1 ) (D + δD ) (U1 + δU1 ) alakú LDU felbontásuk. Legyen B = L−1 . Ekkor fennáll, 1 δA U hogy kδL1 kF ≤ kL1 k2 kX1 kF , kδD kF ≤ kDk2 kΓkF és ahol kX1 kF ≤ p (B) kBkF , kΓkF továbbá az

kδU1 kF ≤ kU1 k2 kY1 kF , ¡ ¢ ¡ ¢ ≤ p B T kBkF és kY1 kF ≤ κ2 (D) p B T kBkF . Fennállnak kδL1 − L1 tril∗ (B)kF ≤ kL1 k2 p (B) kBk2 ktriu (B)kF , és (37) ¡ ¢ kδD − diag (B) DkF ≤ kDk2 p B T kBk2 ktril∗ (B)kF (38) ° ° ¡ ¢ ° ¡ ¢ ¢° ¡ °δU − triu∗ D−1 BD U1 ° ≤ kU1 k kDk p B T kBk °tril D−1 B ° 1 2 2 2 F F (39) becslések is. 38. Tétel Tegyük fel, hogy A ∈ Rn×n és A + δA ∈ Rn×n szimmetrikus, pozitív deÞnit mátrixok, amelyeknek Cholesky faktorizációi A = RT R és A + δA = (R + δR )T (R + δR ) alakúak. Legyen b = R−T δA R−1 . Ekkor fennáll, hogy B ³ ³ ´° ° ´ ³ ´° ° b° b° b ° b ° (40) kδR kF ≤ θ p B ° kRk2 , ° p B °B °B 2 F ahol √ 1+x−1 √ + 1+x θ (x) = x (x ≥ 0) . (41) Legyen Up (Z) = triu∗ (Z) + pdiag (Z) (0 ≤ p ≤ 1). 42. Tétel Tegyük fel, hogy A ∈ Rn×n és A + δA ∈ Rn×n szimmetrikus, pozitív deÞnit mátrixok, amelyeknek Cholesky faktorizációi A =

RT R és A + δA = (R + δR )T (R + δR ) alakúak. Legyen b = R−T δA R−1 . Ekkor fennáll, hogy B ° ³ ´ ° ³° ° ³ ´´ ³ ´ ° °2 ° ° b° b° b R° b p B b ° (42) ° ,p B ° , °δR − U1/2 B ° ≤ kRk2 φ °B °B F ahol F ¶ µ 1 1 + y + xy 2 . φ (x, y) = 1 + √ 2 2 2 F (43) A fenti norma becslések minden megengedett perturbáció esetén érvényesek. A komponensenkénti felsýo becslések, amelyek több tekintetben informatívabbak, a következýok 43. Tétel Tegyük fel, hogy A és A + δA nemszinguláris és létezik A = L1 U és A + δA = −1 . Ekkor fennáll (L1 + δL1 ) (U + δU ) alakú LU felbontásuk. Legyen B = L−1 1 δA U |δL1 | ≤ |L1 | tril∗ (|F |) , 10 |δU | ≤ triu (|G|) |U| , (44) ahol F és G az F = B − Btriu(F ) és G = B − tril∗ (G) B egyenletek megoldásai. Ha ρ (|B|) < 1, akkor ¡ ¡ ¢ ¢ |δL1 | ≤ |L1 | tril∗ F b,1 , |δU | ≤ triu Gb,1 |U | , (45) ahol F b,1 és Gb,1 az G = |B| + tril∗ (G) |B| F =

|B| + |B| triu (F ) , (46) egyenletek egyértelmý u megoldásai. 46. Tétel Tegyük fel, hogy A és A + δA nemszinguláris és van A = L1 DU1 és A + δA = −1 e = L−1 δA U −1 . (L1 + δL1 ) (D + δD ) (U1 + δU1 ) alakú LDU felbontásuk. Legyen B = L−1 és B 1 δA U 1 Ekkor fennáll, hogy ³¯ ¯´ ¯ ¯ |δL1 | ≤ |L1 | tril∗ (|F |) , |δD | ≤ diag (|G|) |D| , |δU1 | ≤ triu∗ ¯Fe¯ |U1 | , (47) ³ ´ e − tril Fe B e egyenletek ahol F , G és Fe az F = B − Btriu(F ), G = B − tril∗ (G) B és Fe = B ³¯ ¯´ ¯ e¯ megoldásai. Ha ρ (|B|) < 1 és ρ ¯B ¯ < 1, akkor ³ ´ ¡ ¡ ¢ ¢ |δL1 | ≤ |L1 | tril∗ F b,1 , |δD | ≤ diag Gb,1 |D| , |δU1 | ≤ triu∗ Feb,1 |U1 | , (48) u megoldásai és Feb,1 az ahol F b,1 és Gb,1 a (46) egyenletek egyértelmý ¯ ¯ ³ ´¯ ¯ ¯ e¯ ¯ e¯ Fe = ¯B ¯ ¯ + tril Fe ¯B (49) egyenlet egyértelmý u megoldása. 49. Tétel Tegyük fel, hogy A ∈ Rn×n és A + δA ∈ Rn×n szimmetrikus, pozitív

deÞnit mátrixok, amelyeknek Cholesky faktorizációi A = RT R és A + δA = (R + δR )T (R + δR ) alakúak. Legyen ³¯ ¯´ ¯ ¯ b¯ < 1, akkor b = R−T δA R−1 . Ha ρ ¯B B |δR | ≤ Ωb,1 |R| , (50) ¯ ¯³ ¯ ¯´−1 ¯ b¯ ¯ b¯ I(k−1) . ahol eTk Ωb,1 = eTk ¯B ¯ I − I (k) ¯B ¯ A komponensenkénti becslések bizonyos esetekben élesek. Megmutatható, hogy a fenti becslések részben rendezésben jobbak mint Sun [101] hasonló becslései Meghatároztunk olyan komponensenkénti becsléseket is amelyek ”minden” B esetén érvényesek Ezek közül az alábbi eredményt idézzük. 45. Tétel Tegyük fel, hogy A és A + δA nemszinguláris és létezik A = L1 U és A + δA = −1 (L1 + δL1 ) (U + δU ) alakú LU felbontásuk. Legyen B = L−1 . Ekkor fennáll, hogy 1 δA U ¡ ¡ ¢ ¢ (51) |δL1 | ≤ |L1 | tril∗ κSkeel L−1 |δU | ≤ triu (|B| κSkeel (UI+B )) |U | , I+B |B| , ahol I + B = LI+B UI+B . A komponensenkénti felsýo korlátok expliciten

és iteratív úton is megkaphatók. Az iterációk bizonyos esetekben monotonok a részben rendezésben. 52. Tétel Tekintsük a W = C + Btriu (W, l) egyenletet, ahol B, C, W ∈ Rn×n és l ≥ 0 Ha ρ (|B|) < 1, akkor minden W0 ∈ Rn×n mátrix esetén a Wk+1 = C + Btriu (Wk , l) sorozat a W megoldáshoz konvergál és |Wk − W | ≤ (I − |B|)−1 |B|k |W1 − W0 | 11 (k = 1, 2, . ) (52) Ha még B ≥ 0 és C ≥ 0 is fennáll, akkor X0 = 0 és Y0 = (I − B)−1 C esetén Xk+1 = C + Btriu (Xk , l) és Yk+1 = C + Btriu (Yk , l) ( k ≥ 0) monoton sorozatok, amelyekre fennáll a −1 0 ≤ Xk ≤ Xk+1 ≤ W ≤ Yk+1 ≤ Yk ≤ (I − B) egyenlý otlenség. Ha B ≥ 0 és C ≤ 0, akkor az X0 = (I − B) kiindulva az {Xk } és {Yk } sorozat kielégíti az −1 (I − B) −1 C (53) C és Y0 = 0 kezdeti értékekbý ol C ≤ Xk ≤ Xk+1 ≤ W ≤ Yk+1 ≤ Yk ≤ 0 (k ≥ 0) (54) egyenlý otlenséget. 53. Tétel Tekintsük a W = C + tril (W, −l) B egyenletet,

ahol B, C, W ∈ Rn×n és l ≥ 0 Ha ρ (|B|) < 1, akkor minden W0 ∈ Rn×n mátrix esetén a Wk+1 = C + tril (Wk , −l) B sorozat a W megoldáshoz konvergál és |Wk − W | ≤ |W1 − W0 | |B|k (I − |B|)−1 (k = 1, 2, . ) (55) −1 Ha még B ≥ 0 és C ≥ 0 is fennáll, akkor X0 = 0 és Y0 = C (I − B) esetén Xk+1 = C + tril (Xk , −l) B és Yk+1 = C + tril (Yk , −l) B ( k ≥ 0) monoton sorozatok amelyekre fennáll a −1 0 ≤ Xk ≤ Xk+1 ≤ W ≤ Yk+1 ≤ Yk ≤ C (I − B) (56) ol egyenlý otlenség. Ha B ≥ 0 és C ≤ 0, akkor az X0 = C (I − B)−1 és Y0 = 0 kezedeti értékekbý kiindulva az {Xk } és {Yk } sorozat kielégíti a C (I − B)−1 ≤ Xk ≤ Xk+1 ≤ W ≤ Yk+1 ≤ Yk ≤ 0 (k ≥ 0) (57) egyenlý otlenséget. Legyen például φ0 = (I − |B|)−1 |B| = |B| (I − |B|)−1 = ψ0 , φi+1 = |B| + |B| triu (φi ) (i ≥ 0) és ψi+1 = |B| + tril∗ (ψi ) |B| (i ≥ 0). Ekkor az LU felbontás perturbációjára fennáll a ¡ ¢

(58) |δL1 | ≤ |L1 | tril∗ F b,1 ≤ |L1 | tril∗ (φi+1 ) ≤ |L1 | tril∗ (φi ) (i ≥ 0) és ¡ ¢ |δU | ≤ triu Gb,1 |U| ≤ triu (ψi+1 ) |U | ≤ triu (ψi ) |U | (i ≥ 0) (59) felsýo becslések lánca. 3.2 Egerváry rangszámcsökkentý o eljárása o eljárás akkor és 69. Tétel Legyen X = [X1 , , Xk ] és Y = [Y1 , , Yk ] A rangszámcsökkentý £ ¤k osen nemszinguláris. csak akkor zérusosztó mentes, ha az Y T HX = YiT HXj i,j=1 mátrix blokk erý Ebben az esetben a rangszámcsökkentý o eljárás kanonikus alakja ¡ ¢−1 T Y H. Hk+1 = H − HX Y T HX (60) Tegyük fel, hogy Hk+1 = 0 és Y T HX blokk erýosen nemszinguláris. Legyen továbbá X (i) = [X1 , . , Xi ] és Y (i) = [Y1 , , Yi ] 12 71. Tétel Ha Y T HX blokk erý osen nemszinguláris és Hk+1 = 0, akkor Hi+1 a következý o kanonikus alakba írható ¸¶ µ · ¡ ¢ (i)T (i) −1 ¡ T ¢−1 HX 0 Y Hi+1 = HX Y HX Y T H (i = 1, . , k) − (61) 0 0 Ez a kanonikus alak azt

mutatja, hogy a rangszámcsökkentýo eljárás implicit formában az Y T HX inverzét közelíti a fýoátlóra támaszkodó fýominorok invezeivel, amelyeket alkalmas méretý u zérus mátrixok szegélyeznek. P Tegyük fel, hogy ki=1 li = rank (H). Legyen továbbá B = LB DB UB a B ∈ Rm×m mátrix egyértelmý u LDU felbontása, ahol LB blokk egység alsó, DB blokk diagonális és UB blokk egység felsýo háromszög mátrixok. Igaz a következýo eredmény 72. Tétel Legyen Y T HX blokk erý osen nemszinguláris. Ekkor a (6) bázisfaktorizáció komponensei a következý ok: , P = H T Y L−T Y T HX Q = HXUY−1T HX , D = DY T HX . (62) A tételbýol következik, hogy minden bázisfaktorizáció elýoállítható a rangszámcsökkentýo eljárással. A tétel további fontosabb következményeit az alábbiakban foglalhatjuk össze 74. Állítás P ( Q) akkor és csak akkor blokk alsó háromszögmátrix, ha X ( Y ) blokk felsý o háromszögmátrix. 76. Állítás Legyen B

∈ Rm×m szimmetrikus és pozitív mátrix P akkor és csak akkor Bortogonális, ha X = BH T Y U , ahol Y tetszý oleges nemszinguláris és U nemszinguláris felsý o háromszög mátrix. 77. Következmény P diagonális skálázástól eltekintve ortogonális és Q alsó háromszög alakú, akkor és csak akkor, ha X = H T Y U , ahol U és Y tetszý oleges nemszinguláris felsý o háromszög mátrixok. Ebben az esetben a (6) bázisfaktorizáció a H mátrix LQ felbontása 80. Állítás P akkor csak akkor blokk felsý o Hessenberg mátrix, ha H T Y is blokk felsý o Hessenberg. Q akkor és csak akkor blokk felsý o Hessenberg, ha HX is blokk felsý o Hessenberg. Ha H = I, akkor fennáll az I = QD−1 P T reciprok összefüggés, azaz ¢−1 ¡ . (63) QT = P D−1 Ekkor a rangszámcsökkentýo eljárás diagonális skálázástól eltekintve egyszerre állítja elýo P -t és P −1 inverzét. Ez a tény a Lánczos-féle tridiagonális ki. ¤ £ redukcióban használható 81.

Tétel Legyen Y1 ∈ Rm olyan hogy Y = Y1 , BY1 , , B¡m−1 Y1 ¢nemszinguláris Ha H = I és o X olyan, amelyre Y T X erý osen nemszinguláris, akkor QT B P Di−1 a B mátrixhoz hasonló felsý h ¢ ¡ T ¢m−1 ¡ T T −1 Hessenberg mátrix. Ha még X = X1 , B X1 , , B X1 is fennáll, akkor Q B P D tridiagonális mátrix, amely hasonló B-hez. Tegyük fel, hogy H ∈ Rm×n , X és Y olyan, hogy Y T HX blokk erýosen nemszinguláris. A következýo eredmények azt mutatják, hogy a rangszámcsökkentýo eljárás lényegében egy konjugálási algoritmus, amellyel minden konjugált irányt elýo lehet állítani. 83. Állítás Ha X = AT V és Y = B T W , akkor a (P, V ) mátrixpár blokk A-konjugált, a (Q, W ) mátrixpár pedig blokk B-konjugált. 84. Állítás Teszý oleges (P, V ) blokk A-konjugált mátrixpár esetén létezik olyan Y , amelynek oszlopai ortogonálisak és a (3) rangszámcsökkentý o eljárás a H = I, X = AT V és Y paraméterekkel pontosan ezt a P

mátrixot állítja elý o. Az 83. és 84 Állítás alapján a rangszámcsökkentýo eljárás a következýo formában használható konjugálásra. 13 Rangszámcsökentéses konjugálás H1 = H for i = 1, . , k Pi = HiT Yi ¡ ¢−1 T Hi+1 = Hi − Hi AT Vi YiT Hi AT Vi Yi Hi end Az eljárással kapott P iránymátrixra fennáll, hogy −1 T P = [P1 , . , Pr ] = H T Y L−T Y T HAT V = H Y UV T AH T Y . (64) oleges (1)-inverze. Ekkor a ( Q, P ) mátrixpár blokk 85. Állítás Legyen H − a H mátrix tetszý H − -bikonjugált. ¡ ¢−1 T Ha H-nak a B mátrix Egerváry-féle reßexív inverzét választjuk, azaz H = X Y T BX Y , akkor a rangszámcsökkentýo eljárás speciális eseteként levezethetjük a következýo bikonjugálási eljárást. Kétoldali blokk Gram-Schmidt eljárás P1 = Y1 , Q1 = X1 for i = 1, . , k − 1 ¡ ¢−1 T T P Pi+1 = Yi+1 − ij=1 Pj QTj B T Pj Qj B Yi+1 ¡ T ¢−1 T Pi Qi+1 = Xi+1 − j=1 Qj Pj BQj Pj BXi+1 end 86. Állítás A (Q, P

) mátrixpár blokk B-bikonjugált és P = Y L−T Y T BX , Q = XUY−1T BX . Tegyük fel, hogy H ∈ Rn×n szimmetrikus és legyen in (H) = (i+ , i− , i0 ) a H mátrix inerciája, ahol i+ , i− és i0 rendre a pozitív, a negatív és a zérus sajátértékek számát jelöli. 87. Tétel Ha H szimmetrikus, akkor ³ ¡ ¢−1 T ´ ¡ ¢ in H − HX X T HX X H = in (H) − in X T HX + (0, 0, k) . (65) Tekintsük most a szimmetrikus rangszámcsökkentýo eljárást: Legyen H1 = H, ¡ ¢−1 T Hi+1 = Hi − Hi Xi XiT Hi Xi Xi Hi ¢ ¡ Xi ∈ Rn×li , i = 1, . , k (66) Pk és rank (H) = i=1 li = r. 88. Tétel Tetszý oleges szimmetrikus H ∈ Rn×n mátrix esetén in (H) = k X i=1 ¡ ¢ in XiT Hi Xi + (0, 0, n − r) . (67) A szimmetrikus esetben a (6) bázisfaktorizáció tényezýoi: −1 P = Q = HXUX T HX , D = DX T HX . (68) Tehát a kapcsolódó H = QD−1 QT bázisfaktorizáció egyfajta LDLT felbontás, noha Q nem szükségképpen alsó háromszög alakú. Ha az Xi

-k parciális permutáció mátrixok, az algoritmus ekvivalens Cottle [25] nevezetes inercia számító algoritmusával 14 3.3 Véges projekciós módszerek lineáris egyenletrendszerek megoldására ¡ ¢−1 T Legyen sk = xk − ω (ω = A−1 b), Rk = Uk VkT AUk Vk A és Qk = (I − Rk ) (I − Rk−1 ) . (I − R1 ) (69) A konjugált irány módszerekre vonatkoznak az alábbi eredmények. 97. Állítás A CDM algoritmus abszolút hibájára fennáll, hogy ksk k ≤ kQk k ks0 k (k = 1, . , r) (70) Tetszý oleges unitér invariáns mátrixnormában kQk k akkor és csak akkor minimális minden k értékre, ha U ortogonális. Bármely szubmultiplikatív unitér invariáns mátrixnormában kQk k ≤ cond (U ) (k = 1, . , r) (71) 98. Állítás A CDM algoritmus reziduális hibájára fennáll, hogy ek projektor és ahol Q Következésképpen ek r0 , rk = Q ³ ´ ³ ´ ek = R (AU )r−k| , R Q ° ° °e ° krk k ≤ °Q k ° kr0 k (72) ³ ´ ³ ´ ek = R (AU

)|k . N Q (73) (k = 1, . , r) ° ° °e ° Tetszý oleges unitér invariáns mátrixnormában °Q k ° akkor és csak akkor minimális minden k értékre, ha az U mátrix AT A-ortogonális. Bármely szubmultiplikatív unitér invariáns mátrixnormában ° ° °e ° (74) °Qk ° ≤ cond (AU) (k = 1, . , r) 99. Következmény A CDM algoritmus iteráltjai kielégítik a kxk k ≤ kI − Qk k kωk + kQk k kx0 k (k = 1, . , r) (75) egyenlý otlenséget. Ha a mátrixnorma szubmultiplikatív unitér invariáns, akkor kxk k ≤ cond (U ) (kωk + kx0 k) (k = 1, . , r) (76) DeÞniáljuk az ABS módszerek alábbi részosztályát [43], [45]. 102. DeÞníció A Zk = Wk ( k = 1, , r) esetben az ABS módszert általánosított implicit LU ABS (GILUABS) módszernek nevezzük. A GILUABS módszerek esetén az ABS konjugálás azonos a rangszámcsökkentésen alapuló konjugálással. Ezért a 83-86 Állítások érvényben maradnak Ennek megfelelýoen a GILUABS módszerek

akkor és csak akkor zérusosztómentesek, ha V T AH1T W blokk erýosen nemszinguláris, amely esetben a P iránymátrix a következýo: P = [P1 , . , Pr ] = H1T W UV−1T AH T W 1 15 (77) Az ABS módszerek S2-S5 részosztályainak [5] közös általánosítása a szimmetrizált konjugált irány módszer [43], [45]. 104. DeÞníció A szimmetrizált konjugált irány (SCD) ABS módszert a W = Z = Q és V = F P paraméterek deÞniálják, ahol G = F T A szimmetrikus és pozitív deÞnit. 105. Tétel A szimmetrizált konjugált irány ABS módszer akkor és csak akkor zérusosztómentes, ha Q nemszinguláris. Ebben az esetben −1 P = QUQ T GQ , −1 V = F QUQ T GQ . (78) A szimmetrizált konjugált irány ABS módszerek A-biortogonális (P, V ) párokat generálnak. Írjuk a CDM algoritmust a ¡ ¢−1 T xk = (I − Rk )xk−1 + dk (dk = Uk VkT AUk Vk b, k = 1, . , r) (79) alakba és vezessük be Qk,j = ½ (I − Rk ) · · · (I − Rj ) I (k < j) . (k ≥ j),

(80) mátrixot. Tegyük fel, hogy a j-ik lépésben (0 ≤ j ≤ r −1) hiba lép fel és xj helyett az x0j perturbált értéket kapjuk. Tegyük fel továbbá, hogy ez a hiba terjed tovább és (79) helyett a módosított x0k = (I − Rk ) x0k−1 + dk (k = j + 1, . , r) (81) sorozatot számoljuk. Ekkor az utolsó lépésben fellépýo hiba ω − x0r = xr − x0r = Qr,j+1 (xj − x0j ), amelyre fennáll a ° ° kω − x0r k ≤ kQr,j+1 k °xj − x0j ° . (82) egyenlýotlenség 107. DeÞníció (Broyden) Egy partikuláris CDM algoritmust optimálisan stabilisnak nevezünk, ha kQr,j+1 k minimális minden j értékre. 109. Tétel Egy CDM algoritmus akkor és csak akkor optimálisan stabilis, AT Vi ⊥ AT Vj ( i 6= j), vagy ekvivalensen V T AAT V = D, ahol D diagonális. 110. Tétel Az (81) hibaterjedési modell esetén fennáll hogy ° ° ° ° kω − x0r k ≤ cond(V T A) °xj − x0j ° ≤ cond(V )cond(A) °xj − x0j ° (83) tetszý oleges szubmultiplikatív unitér

invariáns mátrixnormában. A reziduális perturbációt a rk0 = A(xk − x0k ) mennyiség deÞniálja. 112. Tétel A reziduális hibára teljesül, hogy °° ° ° ° ° krr0 k ≤ °AQr,j+1 A−1 ° °rj0 ° ≤ cond (V ) °rj0 ° (84) ° ° minden j esetén. A °AQr,j+1 A−1 ° hibakonstans minimális minden j értékre, akkor és csak akkor, ha V T V = D, ahol D blokk diagonális mátrix. A CDM algoritmusok szerkezete lehetýové teszi a (81) hibaterjedési modell egy egyszerý u kiterjesztését. Tegyük fel, hogy a k-ik lépésben az εk hiba lép fel és a (79) rekurzió helyett a ¡ ¢ (85) x0k = (I − Rk ) x0k−1 + εk−1 + dk (k = 1, . , r) 16 módosított rekurziót használjuk. Azt is feltesszük, hogy az εk hibák egymástól függetlenek 113. Tétel A kiterjesztett (85) hibaterjedési modellre fennáll, hogy r r X ¡ ¢X kω − x0r k ≤ cond V T A kεi−1 k ≤ cond (V ) cond (A) kεi−1 k . i=1 i=1 Az optimálisan stabilis módszer esetén az ennél

élesebb kω − x0r k ≤ r X i=1 kεi−1 k2 (86) becslés áll fenn. A rangszámcsökkentéses eljárás stabilitása valójában a (6) bázisfaktorizáció stabilitását jelenti. Igaz a következýo e = Q−1 δH P −T D. Ha a δH perturbáció olyan, hogy 114. Tétel Legyen B = DQ−1 δH P −T és B T T T Y HX és Y HX + Y δH X nemszinguláris és van LU felbontása, akkor ³ ´ e , (87) δP T = triu (G) P T , δD = diag (G) D, δQ = Qtril G ³ ´ ∗ e e az G = B − tril∗ (G) B és G e=B e − Btriu e G egyenletek egyértelmý u megoldásai. ahol G és G Következésképpen ³¯ ¯´ ¯ T¯ ¯ ¯ e¯¯ . ¯δP ¯ ≤ triu (|G|) ¯P T ¯ , |δD| ≤ diag (|G|) |D| , |δQ| ≤ |Q| tril ¯¯G (88) ³¯ ¯´ ¯ e¯ Ha ρ (|B|) < 1 és ρ ¯B ¯ < 1, akkor ´ ³ ¯ T¯ ¡ ¡ ¢¯ ¯ ¢ eb,1 , ¯δP ¯ ≤ triu Gb,1 ¯P T ¯ , |δD| ≤ diag Gb,1 |D| , |δQ| ≤ |Q| tril G eb,1 a ahol Gb,1 és G G = |B| + tril∗ (G) |B| ¯ ¯ ¯ ¯ ³ ´ e ¯¯ triu∗ G e ¯¯

+ ¯¯B e , e = ¯¯B and G (89) (90) egyenletek egyértelmý u megoldásai. ³¯ ¯´ ¯ e¯ o becslések érvényesek: 115. Megjegyzés Ha ρ (|B|) < 1 és ρ ¯B ¯ < 1, akkor az alábbi durva felsý Gb,1 ≤ |B| (I − |B|)−1 ¯ ¯´−1 ¯ ¯ ³ ¯ e¯ e ¯¯ eb,1 ≤ I − ¯¯B G ¯B ¯ . A tétel alapján Egerváry eljárása stabilis, ha a megfelelýo háromszögfelbontás is az. 17 3.4 Projekciós módszerek nemlineáris egyenletrendszerek megoldására Jelölje F 0 (x) = [∂fi (x) /∂xj ]m i,j=1 = A (x) (91) az F : Rm Rm leképezés Jacobi mátrixát, ω ∈ Rm pedig az F (x) = 0 egyenlet tetszýoleges megoldását. Tegyük fel, hogy teljesülnek a ∃A (x)−1 (x ∈ S (ω, δ0 )) , kF (x) − F (y)k ≤ K0 kx − yk (92) (x, y ∈ S (ω, δ0 )) (93) (x, y ∈ S (ω, δ0 )) (94) és α kA (x) − A (y)k ≤ K1 kx − yk feltételek, ahol K0 , K1 ≥ 0, 0 < α ≤ 1 és δ0 > 0. 120. Tétel Tegyük fel, hogy a (92)-(94) feltételek

teljesülnek és 0 < µ < 2 Létezik egy 0 < δ ∗ < δ0 szám úgy, hogy minden x0 ∈ S (ω, δ ∗ ) esetén a (9) relaxált Kaczmarz módszer konvergál ω-hoz lineáris sebességgel. A Kaczmarz módszer konvergenciája a (I − µRr ) · · · (I − µR1 ) szorzatmátrixtól függ, amely általában nem zérusmátrix. A konvergencia ráta közelítýoleg k(I − µRr ) · · · (I − µR1 )k. Ennek a ¡ ¢ uvelettel számítható becslését adjuk meg az utolsó fejezetben. mennyiségnek egy O n3 mý A konjugált irány módszerek következýo nemlineáris általánosítását deÞniáltuk. Tegyük fel, Pr(i) (i) hogy 1 ≤ r (i) ≤ m, k=1 mk = m, (i) (i) Pk , Vk (i) ∈ Rm×mk (i)T Vj (i) (i) (k = 1, . , r (i)), Aj Pk = 0 (j < k) , (95) (96) és ´ ³ (i)T (i) (i) 6= 0 det Vk Ak Pk (k = 1, . , r (i)) (97) A két utolsó feltételbýol következik, hogy ir(i) h (i)T (i) (i) Vj Aj Pk j,k=1 nemszinguláris blokk alsó háromszögmátrix.

1. Algoritmus (Nemlineáris konjugált irány módszer) x1 ∈ Rm for i = 1, 2, . y1 = xi for k = 1, . , r (i) ³ ´−1 (i) (i)T (i) (i) (i)T yk+1 = yk − Pk Vk Ak Pk Vk F (yk ) end 18 (98) xi+1 = yr(i)+1 end (1) Ha F (x) = Ax − b és Aj = A (j = 1, . , r (1)), akkor az algoritmus megegyezik az eredeti (i) konjugált irány módszerrel és véges lépésben befejezýodik. Ha a Vk mátrixok parciális permutáció mátrixok, akkor az 1. Algoritmus un ”row-action” módszer (vö [18]). o n (i) (i) (i) (i) Megjegyezzük, hogy az r (i), a Pk , Vk mátrixok és a m1 , . , mr(i) partíció az i-edik iterációban változhatnak. Az egyszerý uség kedvéért a felsýo i indexet elhagyjuk és csak az r (i)-t használjuk mint emlékeztetýo jelölést. 121. Tétel Tegyük fel, hogy a (92)-(94) feltételek teljesülnek és a Vk , Pk mátrixok olyanok, amelyekre fennáll, hogy ° ¡ ¢−1 T ° ° ° Vk ° ≤ K2 (k = 1, . , r (i) ; i ≥ 1) (99) °Pk VkT Ak Pk Ekkor

léteznek olyan Γ∗ , δ ∗ > 0 számok, hogy kAk − A (ω)k ≤ Γ∗ (k = 1, . , r (i) ; i ≥ 1) (100) és x1 ∈ S (ω, δ ∗ ) esetén az 1. Algoritmus lineáris sebességgel konvergál ω-hoz Ha kAk − A (ω)k ≤ K6 kxi − ωkα ( k = 1, . , r (i), i ≥ 1), akkor a konvergencia sebesség rendje legalább 1 + α A 121. Tételbýol egy sor eljárás lokális konvergenciája, illetve korábbi konvergencia tétele következik. A tétel bizonyítása megadja a belsýo iterációk struktúrális jellemzését, amelynek érdekes következményei lehetnek az un. ”inexact” Newton-módszerek körében Ugyancsak ez a jellemzés teszi lehetýové a Kaczmarz tipusú módszerek és konjugált irány módszerek eltérýo konvergencia tulajdonságainak magyarázatát. A nemlineáris ABS módszerek elsýo változatát Abaffy, Galántai és Spedicato [4] fejlesztette ki. Ezt Abaffy és Galántai [3] a következýo formában általánosította. 5. Algoritmus (Blokk

nemlineáris ABS módszer) x1 ∈ Rm for i = 1, 2, . y1 = xi , H1 = I for k = 1, . , r (i) ³ ´ P Pk uk = kj=1 τjk yj τjk ≥ 0, j=1 τjk = 1 Pk = HkT Zk ¡ ¢−1 T yk+1 = yk − Pk VkT A (uk ) Pk V F (yk ) ¡ T k T ¢−1 T T Hk+1 = Hk − Hk A (uk ) Vk Wk Hk A (uk ) Vk Wk Hk end xi+1 = yr(i)+1 end A 121. Tétel alapján az 5 Algoritmus lokális konvergenciája legalább 1 + α rendý u. Galántai és Jeney [61], [62] javasolt egy általános kvázi-Newton ABS módszert (QNABS1), amelynek a következýo két módszer speciális esete. 2. Kvázi-Newton ABS módszer (QNABS2) y1 = xk −T Calculate P = A−1 k V for i = 1, . , m yi+1 = yi − viT F (yi ) pi 19 end xk+1 = ym+1 sk = xk+1 − xk Yk = F (xk+1 ) − F (xk ) Ak+1 = φ (Ak , sk , Yk ) 3. Kvázi-Newton ABS módszer (QNABS3) y1 = xk , Calculate QR = ATk V and set P = Q for i = 1, . , m yi+1 = yi − viT F (yi ) pi /rii end xk+1 = ym+1 sk = xk+1 − xk Yk = F (xk+1 ) − F (xk ) Ak+1 = φ (Ak , sk , Yk ) A Ak+1 =

φ (Ak , sk , Yk ) formula a Jacobi mátrix tetszýoleges egyrangú kvázi-Newton közelítését ¡ ¢ jelöli. A QNABS2 és QNABS3 algoritmusok lépésenkénti számításigénye O m2 ßop és 2 függvény behívás feltéve, hogy V diagonális mátrix, vagy annak permutáltja. Az eljárás konvergenciáját Broyden [13] ¡ ¢ φ (Ak , sk , Yk ) = Ak + (yk − Ak sk ) sTk / sTk sk (101) alakú kvázi-Newton update formulájára igazoljuk. 135. Tétel Tegyük fel, hogy teljesülnek a (92)-(94) feltételek az α = 1° értékkel és°a {pi }ni=1 irányok kielégítik a (99) feltételt. Léteznek a ε, δ1 > 0 számok, hogy °A(1) − A (ω)° ≤ δ1 és kx1 − ω k ≤ ε esetén a QNABS1 algoritmus lineáris sebességgel konvergál ω-hoz. 136. Következmény Ha δ1 > 0 elég kicsi és V nemszinguláris, akkor a QNABS2 algoritmus lineárisan konvergens. 136. Következmény Ha δ1 > 0 elég kicsi és V nemszinguláris, akkor a QNABS3 algoritmus lineárisan konvergens.

Szintén deÞniáltuk a QNABS2 és QNABS3 algoritmusok többlépéses változatait. Az algoritmusokkal végzett számítógépes összehasonlító tesztelések [61], [62], [64], [87] azt mutatják, hogy a kvázi-Newton ABS módszerek versenyképesek még a legjobbnak tartott Broyden módszerrel is összehasonlítva. A QNABS3 algoritmus FORTRAN 77 programját [63] az értekezés függeléke tartalmazza. A nemlineáris ABS módszerek monoton konvergenciáját az alábbi feltételek mellett igazoljuk: (a) F : Rm Rm folytonosan differenciálható és konvex az Rm téren; (b) A (x) = F 0 (x) nemszinguláris M -mátrix minden x ∈ Rm értékre és A : Rm Rm×m izoton. Az 5. Algoritmus alábbi (GILUABS) részosztályát vizsgáljuk  y1 = xi   ³ ´−1 T T (i ≥ 1) , (102) yk+1 = yk − pk ek Ãi pk ek F (yk ) (k = 1, . , m)   xi+1 = ym+1 H1 Hk+1 pk = I ) ³ ´−1 = Hk − Hk ÃTi ek zkT Hk ÃTi ek zkT Hk = HkT zk 20 (k = 1, . , m) , (103) ahol Ãi = [AT

(u1 )e1 , . , AT (um )em ]T 141. Tétel Tegyük fel, hogy (i) F kielégíti az (a) és (b) feltételeket; (ii) Z = Qi ( i ≥ 1); (iii) A Qi mátrixok nemnegatívak és fennáll rájuk a Q−1 ≥ Di A(xi ) feltétel, ahol Di ≥ 0 nemi szinguláris diagonális mátrix ( i ≥ 1); (iv) Létezik két nemszinguláris mátrix Q∞ és D∞ , amelyekre Qi ≥ Q∞ ≥ 0 és Di ≥ D∞ ≥ 0 ( i ≥ 1); Ha x1 ∈ Rm tetszý oleges olyan pont, amelyre F (x1 ) ≥ 0, akkor a (102)-(103) algoritmusra fennáll, hogy ω ≤ xi+1 = ym+1 ≤ ym ≤ · · · ≤ y1 = xi (i ≥ 1) (104) és xi ω ( i +∞). −1 Tetszýoleges x0 ∈ Rm esetén x1 = x0 − [F 0 (x0 )] F (x0 ) kielégíti az F (x1 ) ≥ 0 feltételt (v.ö [92]). Ezért a 141 Tétel lényegében egy globális konvergencia tétel Tegyük fel, hogy a z1 ∈ Rm pontra teljesül, hogy F (z1 ) ≤ 0. A (102)-(103) algoritmushoz hozzárendeljük a  w1 = zi   ³ ´−1 T e T (i ≥ 1) , (105) wk+1 = wk − pk ek Ai pk ek F

(wk ) (k = 1, . , m)   zi+1 = wm+1 algoritmust, ahol a ³ ´−1 ei pk eTk ψk = ψk (uk ) = pk eTk A (k = 1, . , m) mennyiséget a (102)-(103) módszer deÞniálja. 142. Tétel Tegyük fel, hogy a 141 Tétel feltételei teljesülnek és van olyan z1 pont, amelyre F (z1 ) ≤ 0. Ekkor (105) algoritmusra fennáll, hogy ω ≥ zi+1 = wm+1 ≥ wm ≥ · · · ≥ w1 = zi (i ≥ 1) (106) és zi ω ( i +∞). Tehát a (102)-(103) és (105) algoritmusok az ω megoldás zi ≤ zi+1 ≤ ω ≤ xi+1 ≤ xi (i = 1, 2, . ) alakú kétoldali közelítéseit állítják elýo. 143. Tétel A 141 és 142 Tételek feltételei mellett a h i −1 −1 −1 zi − Qi UA−1 D F (z ), x − Q U D F (x ) i i i i e Q e Q e Q e Q A A A i i i i i i i (107) (108) i intervallum befedi az ω megoldást tartalmazó [zi+1 , xi+1 ] intervallumot. 144. Tétel Tegyük fel, hogy a 141 Tétel feltételei teljesülnek, [τij ]m i,j=1 = [e1 , . , e1 ] és Qi = o (102)-(103) algoritmus a

részben renA−1 (xi )D1 , ahol D1 ≥ 0 diagonális. Ekkor a megfelelý dezésben gyorsabb mint a Newton módszer feltéve, hogy a két módszer ugyanabból az x1 pontból indul. 21 3.5 Konvergencia és hibabecslések Az Auchmuty-féle utólagos hibabecslést a p = q = 2 esetben vizsgáljuk. Megmutatjuk, hogy a hibabecslés a Kantorovics egyenlýotlenség következménye, a 2 kr (x)k22 1 σ12 + σn2 kr (x)k2 ≤ kx − ωk ≤ 2 kAT r (x)k2 2 σ1 σn kAT r (x)k2 (109) alakba írható, a felsýo korlát pontos és C2 (A) = 1 σ12 + σn2 1 = 2 σ1 σn 2 µ κ2 (A) + 1 κ2 (A) ¶ . (110) A Greub-Rheinboldt-Kantorovics egyenlýotlenség felhasználásával igazoljuk a becslés következýo geometriai jellemzését. 150. Tétel Az abszolút hibára fennáll, hogy 2 ¡ ¢ kr (x)k2 = cos AT Ae, e kek2 , T kA r (x)k2 ahol ¢ ¡ 1 ≥ cos AT Ae, e ≥ 1 = cos AT A. C2 (A) (111) (112) Az A operátor koszinuszát a cos (A) = xT Ax x6=0,Ax6=0 kAxk kxk inf ¢ ¡ A ∈ Rn×n

(113) mennyiség deÞniálja (Gustafson, Rao alsó hibabecslése az e ¢ [68]). A tétel alapján Auchmuty ¡ ¢ ¡ hibavektort merýolegesen a R AT Ae = R(AT r) altérre vetíti. Az AT Ae, e ] szög határozza meg a becslés jóságát. Az F (x) = 0 alakó nemlináris egyenletrendszerekre levezetjük a kF (x)k22 ° kx − ωk2 = c ° ° ° 0 T °F (x) F (x)° (114) 2 közelítýo hibabecslést, ahol 1 / c / C2 (F 0 (x)). A eredmény a Newton típusú módszerekkel együtt használható. A részletesen is ismertetett számítógépes tesztelések alapján a hiba utólagos becslésére a ° ° kx − ωk2 / 0.5 dim (A) kr (x)k22 / °AT r (x)°2 (115) tapasztalati formulát javasoljuk. Az alternáló projekciók módszerére a következýo sebesség becsléseket igazoltuk. 158. Tétel Tegyük fel, hogy Xj ∈ Rm×nj , XjT Xj = I ( j = 1, , k) és X = [X1 , , Xk ] maximális oszloprangú. Ekkor minden l ≥ 1 esetén fennáll, hogy ° °£¡ ° ° ¢ ¡ ¢¤l ° ° (116) ° I

− Xk XkT . I − X1 X1T y − PR⊥ (X) y ° ≤ clGM °PR(X) y ° (y ∈ Rm ) , 22 ¡ ¡ ¢¢1/2 ahol cGM = 1 − det X T X , cGM ≥ cSSW és cGM = cSSW ha nj = 1 minden j = 1, . , k esetén. ¡ ¢ Ha X maximális oszloprangú és minden oszlopvektor normalizált, akkor 0 < det X T X ≤ 1 és 0 ≤ cGM < 1. (117) A cGM konstans értéke X rangjával növekedik. 161. Tétel Tegyük fel, hogy Xj ∈ Rm×nj , XjT Xj = I, 0 < µj < 2 ( j = 1, , k) és X = [X1 , . , Xk ] maximális oszloprangú Ekkor minden l ≥ 1 esetén fennáll, hogy °£¡ ° ° ° ¢ ¡ ¢¤l ° ° (118) ° I − µk Xk XkT . I − µ1 X1 X1T y − PR⊥ (X) y ° ≤ clAGM °PR(X) y ° (y ∈ Rm ) , ahol cAGM = !1/2 k h i Y ¡ T ¢ 2 1 − (1 − µi ) det X X 1− . à (119) i=1 ¡ ¢ A fenti becslések a Gram determináns értékét igénylik, amely a Gauss módszerrel O n3 (n = Pk uvelettel meghatározható (v.ö Pan, Yu és Stewart [93]) j=1 nj ) aritmetikai mý 3.6 Az

eredmények alkalmazása A kidolgozott algoritmusok mindenütt alkalmazhatók, ahol lineáris, vagy nemlineáris egyenletrendszert kell megoldani. Két konkrét alkalmazást az értekezés 55 Fejezetében be is mutatunk Az elsýo alkalmazás speciális blokk nyílhegy alakú együttható vagy Jacobi mátrixú lineáris, ill. nemlineáris egyenletrendszerek megoldása. A másik alkalmazás feltételes optimalizálási feladatok megoldása a Kuhn-Tucker egyenleteken keresztül Az utólagos hibabecslýo eljárások közelítýo eljárásokkal együtt használhatók a kapott közelítés jóságának becslésére. Az alternáló projekciók módszerének sebesség becslése a módszerrel együtt használható. A háromszög felbontásokkal és a rangszámcsökkentéssel kapcsolatban kapott eredmények többsége az értekezésben alkalmazásra került. További alkalmazási lehetýoségeket jelenthet a multiplikatív faktorizációkon alapuló egyéb algoritmusok perturbáció analízise,

valamint a H-mátrixokkal kapcsolatos eljárások. A rangszámcsökkentési eredmények eddigi optimalizálási alkalmazásait a [95], [105], [33] munkák foglalják össze, jelezve egyúttal a további alkalmazási lehetýoségeket is. IV. Publikációk Az értekezés témakörébýol készített közlemények: [4], [3], [39], [41], [40], [43], [42], [44], [46], [45], [47], [48], [49], [50], [52], [54], [53], [51], [55], [57], [56], [58], [59], [60], [36], [38], [37], [61], [62], [64], [63]. Hivatkozások [1] Abaffy, J.: 1992, ‘Superlinear Convergence Theorems for Newton-Type Methods for Nonlinear Systems of Equations’. JOTA 73(2), 269277 23 [2] Abaffy, J., C Broyden, and E Spedicato: 1984, ‘A class of direct methods for linear equations’ Numerische Mathematik 45, 361376. [3] Abaffy, J. and A Galántai: 1987, ‘Conjugate Direction Methods for Linear and Nonlinear Systems of Algebraic Equations’. In: P Rózsa (ed): Colloquia Mathematica Soc János Bolyai, 50.

Numerical Methods, Miskolc (Hungary) 1986 Amsterdam, pp 481502 [4] Abaffy, J., A Galántai, and E Spedicato: 1987, ‘The local convergence of ABS methods for nonlinear algebraic equations’. Numerische Mathematik 51, 429439 [5] Abaffy, J. and E Spedicato: 1989, ABS-Projection Algorithms: Mathematical Techniques for Linear and Nonlinear Algebraic Equations. Chichester: Ellis Horwood [6] Abaffy, J. and E Spedicato: 1990, ‘A Class of Scaled Direct Methods for Linear Systems’ Ann. Inst Stat 42(1), 187201 [7] Abaffy, J. and E Spedicato: 1991, ABS Projection Algorithms: Mathematical Techniques for Linear and Nonlinear Equations. Beijing Polytechnic University Press Chinese [8] Abaffy, J. and E Spedicato: 1996, Matematicheskie Metodi Dlja Lineinikh I Nelineinikh Uravnenii; Proekcionnie ABS-Algoritmi. Moscow: Mir Russian [9] Aronszajn, N.: 1950, ‘Theory of reproducing kernels’ Trans Amer Math Soc 68, 337404 [10] Auchmuty, G.: 1992, ‘A Posteriori Error Estimates for Linear

Equations’ Numerische Mathematik 61, 16 [11] Barrlund, A.: 1991, ‘Perturbation Bounds for the LDLH and LU Decompositions’ BIT 31, 358363. [12] Bhatia, R.: 1994, ‘Matrix Factorizations and their Perturbations’ Linear Algebra and its Applications 197-198, 245276. [13] Broyden, C.: 1965, ‘A Class of Methods for Solving Nonlinear Simultaneous Equations’ Mathematics of Computation 19, 557593. [14] Broyden, C.: 1973, ‘Some Condition-Number Bounds for the Gaussian Elimination Process’ J. Inst Maths Applics 12, 273286 [15] Broyden, C.: 1974, ‘Error Propagation in Numerical Processes’ Journal of the Institute of Mathematics and Its Applications 14, 131140. [16] Broyden, C.: 1985, ‘On the numerical stability of Huang’s and related methods’ JOTA 47, 401412. [17] Broyden, C.: 1989, ‘On the Numerical Stability of Huang’s Update’ Calcolo 26, 303311 [18] Censor, Y.: 1981, ‘Row-action methods for huge and sparse systems and their applications’ SIAM Review 23(4),

444466. [19] Chang, X.-W and C Paige: 1998a, ‘On the Sensitivity of the LU Factorization’ BIT 38, 486501. [20] Chang, X.-W and C Paige: 1998b, ‘Sensitivity Analyses for Factorizations of Sparse or Structured Matrices’. Linear Algebra and its Applications 284, 5371 24 [21] Chang, X.-W, C Paige, and G Stewart: 1996, ‘New Perturbation Analyses for the Cholesky Factorization’. IMA J Numer Anal 16, 457484 [22] Chen, Z., N Deng, and E Spedicato: 2000, ‘Truncated Difference ABS-Type Methods for Nonlinear Systems of Equations’. Optimization Methods and Software 13, 263274 [23] Chu, M., R Funderlic, and G Golub: 1995, ‘A Rank-One Reduction Formula and its Applications to Matrix Factorizations’ SIAM Review 37, 512530 [24] Chu, M., R Funderlic, and G Golub: 1998, ‘Rank ModiÞcations of SemideÞnite Matrices Associated with a Secant Update Formula’. SIAM J Matrix Anal Appl 20, 428436 [25] Cottle, R.: 1974, ‘Manifestations of the Schur Complement’ Lin Alg Appl 8,

189211 [26] Deng, N. and Z Chen: 1990, ‘Truncated Nonlinear ABS Algorithm and Its Convergence Property’. Computing 45, 169173 [27] Deng, N. and Z Chen: 1998, ‘A New Nonlinear ABS-Type Algorithm and its Efficiency Analysis’. Optimization Methods and Software 10, 7185 [28] Deutsch, F.: 1984, ‘Rate of convergence of the method of alternating projections’ In: International Series of Numerical Mathematics, Vol 72 Basel, pp 96107 [29] Deutsch, F.: 1992, ‘The Method of Alternating Orthogonal Projections’ In: S P Singh (ed): Approximation Theory, Spline Functions and Applications. pp 105121 [30] Deutsch, F. and H Hundal: 1997, ‘The rate of convergence for the method of alternating projections. II’ Journal of Mathematical Analysis and Applications 205, 381405 [31] Drmaÿc, Z., M Omladiÿc, and K Veseliÿc: 1994, ‘On the Perturbation of the Cholesky Factorization’ SIAM J Matrix Anal Appl 15, 13191332 [32] Egerváry, E.: 1960, ‘On Rank-Diminishing Operations and their

Applications to the Solution of Linear Equations’. ZAMP 11, 376386 [33] Feng, E., X Wang, and L Wang: 1997, ‘On the Application of the ABS Algorithm to Linear Programming and Linear Complementarity’. Optimization Methods and Software 8, 133142 [34] Forsythe, G.: 1953, ‘Solving linear algebraic equations can be interesting’ Bull Amer Math Soc. 59, 299329 [35] Franchetti, C. and W Light: 1986, ‘On the von Neumann alternating algorithm in Hilbert space’. Journal of Mathematical Analysis and Applications 114, 305314 [36] Galántai, A., ‘Perturbation Bounds for Triangular and Full Rank Factorizations’ Computers and Mathematics with Applications. submitted [37] Galántai, A., Projectors and Projection Methods Kluwer 2004 [38] Galántai, A., ‘Rank Reduction: Theory and Applications’ Int Journal of Mathematics, Game Theory and Algebra. to appear 25 [39] Galántai, A.: 1990, ‘Block ABS Methods for Nonlinear Systems of Algebraic Equations’ In: E. Allgower and K

Georg (eds): Computational Solution of Nonlinear Systems of Equations (AMS-SIAM Summer Seminar on the Computational Solution of Nonlinear Systems of Equations, Fort Collins, Colorado, 1988), Lectures in Applied Mathematics, 26. Providence, RI, pp. 181187 [40] Galántai, A.: 1991a, ‘Analysis of error propagation in the ABS class for linear systems’ Ann Inst. Statist Math 43, 597603 [41] Galántai, A.: 1991b, ‘Convergence Theorems for the Nonlinear ABS-Methods’ In: D Greenspan and P. Rózsa (eds): Colloquia Mathematica Soc János Bolyai, 59 Numerical Methods, Miskolc (Hungary) 1990. Amsterdam, pp 6579 [42] Galántai, A.: 1993a, ‘ABS Methods on Large Nonlinear Systems with Banded Jacobian Structure’ Technical report, University of Bergamo Quaderni DMSIA, 1993/14 [43] Galántai, A.: 1993b, ‘Generalized Implicit LU Algorithms in the Class of ABS Methods for Linear and Nonlinear Systems of Algebraic Equations’. Technical report, University of Bergamo. Quaderni DMSIA, 1993/5,

[44] Galántai, A.: 1993c, ‘Testing of Implicit LU ABS Methods on Large Nonlinear Systems with Banded Jacobian’. Technical report, University of Bergamo Quaderni DMSIA, 1993/19 [45] Galántai, A.: 1994a, ‘ABS Methods for the Solution of Linear and Nonlinear Systems of Algebraic Equations’. Habilitation dissertation, Technical University of Budapest [46] Galántai, A.: 1994b, ‘A Monotonicity Property of M -Matrices’ Publ Math Debrecen 44(3-4), 265268. [47] Galántai, A.: 1995, ‘The Global Convergence of the ABS Methods for a Class of Nonlinear Problems’. Optimization Methods and Software 4, 283295 [48] Galántai, A.: 1997a, ‘Hybrid Quasi-Newton ABS Methods for Nonlinear Equations’ Technical report, University of Bergamo. Quaderni DMSIA, 1997/11 [49] Galántai, A.: 1997b, ‘Hybrid Quasi-Newton ABS Methods for Nonlinear Equations’ In: F Cobos, J. Gómez, and F Mateos (eds): EAMA97 Meeting on Matrix Analysis and Applications, Sevilla, September 10-12, 1997 pp 221228

[50] Galántai, A.: 1997c, ‘The Local Convergence of Quasi-Newton ABS Methods’ Publ Univ of Miskolc, Series D. Natural Sciences 37, Mathematics, 3138 [51] Galántai, A.: 1997-99, ‘Rank Reduction and Conjugation’ Acta Technica Acad Sci Hung 108(12), 107130. appeared also in Mathematical Notes, Miskolc, Vol1, No1, (2000) 1133 [52] Galántai, A.: 1998, ‘A Note on Projector Norms’ Publ Univ of Miskolc, Series D Natural Sciences 38., Mathematics, 4149 [53] Galántai, A.: 1999a, ‘The Geometry of LU Decomposability’ Publ Univ of Miskolc, Series D. Natural Sciences 40, Mathematics, 2124 [54] Galántai, A.: 1999b, ‘Parallel ABS Projection Methods for Linear and Nonlinear Systems with Block Arrowhead Structure’. Computers and Mathematics with Applications 38, 1117 26 [55] Galántai, A.: 2000, ‘Componentwise Perturbation Bounds for the LU , LDU and LDLT Decompositions’. Mathematical Notes, Miskolc 1, 109118 [56] Galántai, A.: 2001a, ‘Rank Reduction and Bordered

Inversion’ Mathematical Notes, Miskolc 2(2), 117126. [57] Galántai, A.: 2001b, ‘Rank Reduction, Factorization and Conjugation’ Linear and Multilinear Algebra 49, 195207. [58] Galántai, A.: 2001c, ‘A Study of Auchmuty’s Error Estimate’ Computers and Mathematics with Applications 42, 10931102. [59] Galántai, A.: 2002, ‘Egerváry Rangszámcsökkentõ Algoritmusa És Alkalmazásai’ Szigma 33(12), 4555. [60] Galántai, A.: 2003, ‘Perturbations of Triangular Matrix Factorizations’ Linear and Multilinear Algebra 51, 175198 [61] Galántai, A. and A Jeney: 1993, ‘Quasi-Newton ABS Methods’ In: microCAD 93SYSTEM’93, Nemzetközi Számitástechnikai Találkozó, Miskolc, 1993, Március 2-6, M Szekció: Modern Numerikus Módszerek pp 6368 [62] Galántai, A. and A Jeney: 1996, ‘Quasi-Newton ABS Methods for Solving Nonlinear Algebraic Systems of Equations’ JOTA 89(3), 561573 [63] Galántai, A., A Jeney, and E Spedicato: 1993a, ‘A FORTRAN Code of a Quasi-Newton

Algorithm’. Technical report, University of Bergamo Quaderni DMSIA, 1993/7 [64] Galántai, A., A Jeney, and E Spedicato: 1993b, ‘Testing of ABS-Huang Methods on Moderately Large Nonlinear Systems’ Technical report, University of Bergamo Quaderni DMSIA, 1993/6. [65] Gantmacher, F.: 1959, The Theory of Matrices, Vol I-II New York: Chelsea [66] Ge, R.: 1997, ‘A Family of Broyden-ABS Type Methods for Solving Nonlinear Systems’ Technical report, University of Bergamo. Quaderni DMSIA, 1997/1 [67] Golub, G. and D O’Leary: 1989, ‘Some History of the Conjugate Gradient and Lanczos Algorithms: 1948-1976’. SIAM Review 31(1), 50102 [68] Gustafson, K. and D Rao: 1996, Numerical Range: The Field of Values of Linear Operators and Matrices. Springer [69] Halperin, I.: 1962, ‘The product of projection operators’ Acta Sci Math 23, 9699 [70] Hamaker, C. and D Solmon: 1978, ‘The angles between the null spaces of X rays’ Journal of Mathematical Analysis and Applications 62, 123.

[71] Higham, N.: 1996, Accuracy and Stability of Numerical Algorithms Philadelphia: SIAM [72] Horn, R. and C Johnson: 1985, Matrix Analysis Cambridge University Press [73] Householder, A.: 1964, The Theory of Matrices in Numerical Analysis Blaisdell Publishing Company. 27 [74] Huang, Z.: 1991a, ‘ModiÞed ABS Methods for Nonlinear Systems Without Evaluating Jacobian Matrices’ Numer Math J Chinese Univ 13(1), 6071 [75] Huang, Z.: 1991b, ‘Multi-Step Nonlinear ABS Methods and Their Efficiency Analysis’ Computing 46, 143153 [76] Huang, Z.: 1992a, ‘ABS Methods for Solving Nonlinear Least Squares Problems’ Communications on Applied Mathematics and Computation 6, 7585 [77] Huang, Z.: 1992b, ‘A Family of Discrete ABS Type Algorithms for Solving Systems of Nonlinear Equations’ Numerical Mathematics, a Journal of Chinese Universities 14, 130143 [78] Huang, Z.: 1993a, ‘Restart Row Update ABS Methods for Systems of Nonlinear Equations’ Computing 50, 229239. [79] Huang, Z.:

1993b, ‘Row Update ABS Methods for Solving Sparse Nonlinear Systems of Equations’ Optimization Methods and Software 2, 297309 [80] Huang, Z.: 1994a, ‘A New Method for Solving Nonlinear Underdetermined Systems’ Computational and Applied Mathematics 1, 3348 [81] Huang, Z.: 1994b, ‘Row Update ABS Methods for Systems of Nonlinear Equations’ Optimization Methods and Software 3, 4160 [82] Hubert, L., J Meulman, and W Heiser: 2000, ‘Two Purposes for Matrix Factorization: A Historical Appraisal’. SIAM Review 42, 6882 [83] Jeney, A.: 1991a, ‘Nemlineáris Egyenletrendszerek Megoldására Szolgáló ABS-Módszerek Egy Részosztályának Diszkretizációja’. Alkalmazott Matematikai Lapok 15 (1990-91)(34), 365 379. [84] Jeney, A.: 1991b, ‘Nemlineáris Egyenletrendszerek Megoldására Szolgáló ABS-Módszerek Numerikus Vizsgálata’ Alkalmazott Matematikai Lapok 15 (1990-91)(34), 353364 [85] Jeney, A.: 1992, ‘Diszkrét ABS-Módszerek Nemlineáris Egyenletrendszerekre’ In:

Micro-CAD-SYSTEM’ 92 Nemzetközi Számitástechnikai Találkozó, 1992. Február 25-29, Számítástechnika Mûszaki Alkalmazása Konferencia Elõadásai, II. Miskolc, pp 107110 [86] Jeney, A.: 1995, ‘The Convergence of Discrete ABS Methods and Numerical Investigations’ In: microCAD’95 International Computer Science Conference, February 23,1995, Miskolc, Section K: Modern Numerical Methods. pp 2225 [87] Jeney, A.: 1996, ‘Numerical Comparison of Multistep Quasi-Newton ABS Methods with the Multistep Broyden Method for Solving Systems of Nonlinear Equations’. Publ Univ of Miskolc, Series D, Natural Sciences 36(2, Mathematics), 4754. [88] Jeney, A.: 1997, ‘Multistep Discrete ABS Methods for Solving Systems of Nonlinear Equations’ Publ Univ of Miskolc, Series D Natural Sciences 37, Mathematics(3946) [89] Kayalar, S. and H Weinert: 1988, ‘Error bounds for the method of alternating projections’ Math. Control Signals Systems 1, 4359 [90] Neumann, J. V and H Goldstine: 1947,

‘Numerical Inverting of Matrices of High Order’ Bull. Amer Math Soc 53, 10211099 28 [91] Neumann, J. V and H Goldstine: 1951, ‘Numerical Inverting of Matrices of High Order II’ Proc. Amer Math Soc 2, 188202 [92] Ortega, J.: 1972, Numerical Analysis: A Second Course New York: Academic Press [93] Pan, V., Y Yu, and C Stewart: 1997, ‘Algebraic and Numerical Techniques for the Computation of Matrix Determinants’ Computers Math Applic 34(1), 4370 [94] Smith, K., D Solmon, and S Wagner: 1977, ‘Practical and mathematical aspects of the problem of reconstructing objects from radiographs’. Bull Am Math Soc 83(6), 12271270 [95] Spedicato, E.: 1995, Algoritmi Per Programazione Non Lineare Ed Equazioni Lineari e Non Lineari. Milano: RES Editrice Srl Italian [96] Spedicato, E., Z Chen, and N Deng: 1994, ‘A Class of Difference ABS-Type Algorithms for a Nonlinear System of Equations’. Numerical Linear Algebra with Applications 1(3), 313329 [97] Stewart, G.: 1973, ‘Conjugate

direction methods for solving systems of linear equations’ Numerische Mathematik 21, 285297. [98] Stewart, G.: 1993, ‘On the Perturbation of LU, Cholesky and QR Factorizations’ SIAM J Matrix. Anal Appl 14, 11411145 [99] Stewart, G.: 1997, ‘On the Perturbation of LU and Cholesky Factors’ IMA J Numer Anal 17, 16. [100] Sun, J.-G: 1991, ‘Perturbation Bounds for the Cholesky and QR Factorizations’ BIT 31, 341352. [101] Sun, J.-G: 1992a, ‘Componentwise Perturbation Bounds for some Matrix Decompositions’ BIT 32, 702714. [102] Sun, J.-G: 1992b, ‘Rounding-Error and Perturbation Bounds for the Cholesky and LDLT Factorizations’. Linear Algebra and its Applications 173, 7797 [103] Turing, A.: 1948, ‘Rounding-Off Errors in Matrix Processes’ Quart J Mech Appl Math 1, 287308. [104] Wedderburn, J.: 1934, Lectures on Matrices, Amer Math Soc Colloquium Publications, Vol. XVII AMS [105] Zhang, L., Z Xia, and E Feng: 1999, Introduction to ABS Methods in Optimization Dalian

University of Technology Press. Chinese [106] Zhu, M.: 1989, ‘A Generalization of Nonlinear ABS Algorithms and Its Convergence’ Journal of Beijing Polytechnic University 15(4), 2126. 29