【正文】 高斯消去法是 穩(wěn)定的反對(duì)角占優(yōu)矩陣 阿蘭 .喬治 和 KHAKIM D. IKRAMOV 摘要 : 假設(shè) B∈ Mn (C) 是一個(gè)行對(duì)角占優(yōu)矩陣 , 即 , ,n,1i,bb nij 1jijiii ??? ???? 當(dāng) 0≤ ? ＜ 1， i = 1,? ,n, 且 ? = ni1max ?? i? ， 我們的分析表明 ,當(dāng)高斯消去 法 被 應(yīng)用 于1??BA 時(shí)， 沒有旋轉(zhuǎn)是必要的 。此外， 增長因子 A不會(huì)超過 ??1 .同樣的結(jié)果顯示行對(duì)角優(yōu)勢的確會(huì)被列對(duì)角優(yōu)勢所取代 . 1. 引言 我們開始了一個(gè)報(bào)價(jià)從 N海厄姆的論文 [ 1 ]： 當(dāng)計(jì)算一 LU因式分解時(shí)，主要有三類矩陣 是已知的 沒有 安全 軸的 ：矩陣對(duì)角占優(yōu)的行或列， 厄米 正定矩陣，和完全非負(fù)矩陣?！弊髡?繼續(xù)說道 “確定另一類矩陣非?？扇〉膶傩裕簭?fù)雜對(duì)稱矩陣的實(shí)部和虛部都是正定的?！北疚奈覀償U(kuò)展 的矩陣具有此屬性包括矩陣的逆矩陣對(duì)角占優(yōu)的行或列， 由此 我 們 得出， 生長因子等矩陣的。讀者會(huì) 在 3節(jié) 發(fā)現(xiàn)證明， 在 2節(jié)發(fā)現(xiàn) 初步證明所需材料 。 令 A∈ Mn(C), 一套復(fù)雜的 n n 矩陣 . 索引集 ? ?n,1??? ,我們的主要矩陣表示 A 位于行和列索引 ? 以及 A(? ) 并且與其互補(bǔ)的主矩陣為 A( 39。a ).接下來最重要是引理 3。 引理 A∈ Mn(C) 是一個(gè)非奇異矩陣 , 并且 B = 1A . 令 ? 是 ? ?n,1? 的一個(gè)子集 .不等式如下： (1) )(d e t)(d e td e t /??? AAA 　　? 一個(gè)積極的標(biāo)量 ? 反之，如果類似的不等式： (2) )(d e t)(d e td e t /??? Ｂ　?。拢?? 則通過矩陣 B證明 ， 不等式 (2)只不過是 不等式 (1)的另外 一種形式 . 這可以由以下關(guān)系得出 ： AB det1det ?, AAB de t )(de t)(de t 39。?? ?, AAB de t )(de t)(de t 39。 ?? ?, 最后兩個(gè)等式是一般情況下的在 A和 B之間的特別案例 。 (參見 [2, 章 1]的 (33)). 由此我們可以說 B∈ Mn(C)是一個(gè) (行 )對(duì)角線占優(yōu)矩陣 (矩陣證明略 )如果： (3) ,n,1i,bb nij 1jijiii ??? ???? 在 0≤ ? ＜ 1, i = 1,? , 下，可以得到不等式： (4) ? = ni1max ?? i? B將被稱之為顯性因素 。 引理 2. 令 B是一個(gè) , 并且令 1B = A = (aij ):然后，讓 i = 1,… ,n, (5) ，iiib)1(de t BB I??? 那么 Bi 是 bii的余因子 , 然 后 (6) .aa iijji ｉ，　　　?。??? ? 之前的這兩個(gè)引理都可以在不等式一書的 [3,節(jié) 4, 6, 和 7].被發(fā)現(xiàn) (6) 由此我們可以說，每一列的 逆矩陣 元素的最大，而模數(shù)是主對(duì)角線。 假設(shè)一個(gè)非奇異 的 n n的矩陣 A進(jìn)行不旋轉(zhuǎn)的高斯消去 ，當(dāng)經(jīng)過 k步的排除完成之后 , 我們會(huì)得到一個(gè)尚未處理的 nk矩陣。 這個(gè)矩陣有個(gè)另外的稱呼 源矩陣(經(jīng)過 k步之后 ) 或者稱之為 Schur補(bǔ) . 在后一種情況下，它是指 A/A(? )。當(dāng) (7) ? ?.,...,1 k?? 引理 認(rèn)為 (8)\ ? ?? ? ? ?,39。/ 1 ?? BAA ?? 當(dāng) B = 1?A : 高斯消元法 這是一的眾所周知的聯(lián)系 (看 , 舉個(gè)例子 [4, Sec. ]). 令 ? ?? ?nkjia kij ,. .. ,1, ?? 是 Schur補(bǔ)的這項(xiàng)。 )(/ ?AA ,? 是指數(shù)集 (7). 不等式如下： (9) ijjikijkjin aaA,)(,m a xm a x( ?）? A被稱為生長因子。 。 我們將會(huì)在第三節(jié)陳 述以下我們需要的引理 引理 B∈ Mn(C) 是一個(gè) i? (見 (3)). 然后我們可以得出 : (1) 高斯消去法在任何對(duì)角旋轉(zhuǎn)規(guī)則下適用于 B。 (2) 對(duì)角占優(yōu)矩陣具有積極的遺傳屬性。 換句話說，每個(gè) Schur 補(bǔ) B/B(? )同樣是一個(gè) .此外 ,對(duì)每一個(gè) i 來說， 行優(yōu)勢因子 i? . 是超越不了 B/B(? )的。這個(gè)相應(yīng)的因子 i? 也是超越不了 B 的 (假設(shè)原始行指數(shù) B 在行 B/B(? )留下了 ”attached). 3. 主要結(jié)果 現(xiàn)在我們開始證明： 定理 1. 令 A∈ Mn(C)是一個(gè)非奇異矩陣，比如說 B = 1A 是一個(gè)具有行優(yōu)勢因子? (看 (4)) 的 。然后我們可以得出： (10) ?? ??1n ）（ A 證明： 由引理 2可以得出， a11 是在第一列最大的模數(shù)記錄。于是可以得出， a11可以作為最關(guān)鍵的第一步消除。設(shè)定 ? =??1 ,我們可以從 (8)看到 A/A??? 與 . 矩陣 B( ‘? )互逆 . 因此我們可以得出 ,在 A/A??? 中 ）（ 122a 和第一列最大的模數(shù)記錄一致并且可以作為重要的第二步消去。重復(fù)上述步驟，我們可以得出以下結(jié)論 在 A中，沒有有排列需要執(zhí)行高斯消去法 .而且高斯消去法應(yīng)用于 A時(shí)的旋轉(zhuǎn)不完全和 A的部分旋轉(zhuǎn)相同。 事實(shí)上 , 關(guān)系 (6)的真正意思是在所有的矩陣 A中 ，這項(xiàng)最大模數(shù)是 主對(duì)角線 . 這個(gè)結(jié)論在 Schur補(bǔ) A/A??? 中同樣成立。由 此可見，在 )n A（? 之下 我們不得不在對(duì)角項(xiàng)的排除過程中只檢查這種行為。 由此我們假定： )(,max tretsr aM 　? 在 r = s = i。 t = k的情況下實(shí)現(xiàn)。 我們 規(guī)定 ? ?,...,1 k?? ??,i???? 然后 得出 (11) M = ? ?? ???detAdetA 與 A(? )互逆的是 B/B? ?‘? .并且通過引理 4, B/B? ?‘? 是一個(gè) , 并且這個(gè)