第2章解線性方程組的直接解法_313007480

1、第章 解線性方程組的直接解法§0 引言若非奇異，即，方程組有唯一解。由Cramer法則，其解其中為用代替中第列所得的矩陣。當大時，個行列式計算量相當大，實際計算不現(xiàn)實。§1 Gauss消去法（I）Gauss消去法的例子（1）（2） 方程組與方程組同解得（3）由（3）得（3）的系數矩陣為，上三角矩陣。（II）Gauss消去法，矩陣三角分解 令第1次消去 ,令 作運算： 表示第個方程（第行） 如果令令 進行k-1步后，得 以上完成了消去過程，A非奇異；倒著求解這稱為回代過程。消去過程和回代過程結合起來稱為（順序）Gauss消去法，從消去過程可以得出。其中是一個上三角陣。記此矩陣

2、是對角線元素為1的下三角矩陣，稱其為單位下三角陣。 定義1.1 設 令是1至階行列式，稱為A的順序主子式。Gauss消去過程能進行下去的條件應為，而此條件必在消去過程中才能知道。定理1.2 全不為零的充分必要條件是A的順序主子式，其中 證明“”（必要性）設，則可進行消去過程的步，每步由A逐次實行的運算得到，這些運算不改變相應順序主子式的值，所以有“充分性”設命題對于k-1成立，現(xiàn)設。由歸納假設有，Gauss消去可以進行k-1步。化為其中為對角元為的上三角陣。由于是由A經“一行（方程）乘一數加至另一行（方程）”逐步得到的，因此A的k階順序主子式等于的k階順序主子式，即由 。 Gauss消去過程其

3、中L為單位下三角陣，為上三角陣。以后記為U，那么A=LU定理1.3非奇異矩陣，若其順序主子式，那么存在唯一的單位下三角陣L和上三角陣U，使得A=LU。證明 Gauss消去過程已給出L，U。下面證明唯一性設A有兩個分解，其中為單位下三角陣，為上三角陣，因A非奇異都可逆。仍為上三角陣，也是上三角陣，為單位下三角陣 可以證明，當A為奇異陣時，定理仍成立，A的LU分解，L為單位下三角陣，U為上三角陣，此分解稱Doolittle分解。若將上三角陣，其中D為對角陣，為單位上三角陣，并記 那么有其中為下三角陣，為單位上三角陣，此分解稱為Crout分解。其中L為單位下三角陣，D為對角陣，U為單位上三角陣，此稱

4、為A的LDU分解。定理1.4 非奇異陣有唯一的LDU分解（D為對角陣，L為單位下三角陣，U為單位上三角陣）的充分必要條件是A的順序主子式皆是非零。如果A奇異，上述定理也成立。§2 列主元Gauss消去法例2.1 用三位十進制浮點運算求解解 用（順序）Gauss消去法在3位十進制運算的限制下，得代回第一個方程得，此解不對 求解不對的原因是用小數作除數，使是個大數，在計算的值完全被掩蓋了：如果對方程組先作變換，再用Gauss消去法可以得。列主元消去法 進行第1步消去之前，在A的第1列中選出絕對值最大的元素 即，其中。由于A非奇異，有，這一步驟稱為選主元。如果， 則消去過程與順序Gauss

5、消去法一樣如果，則先進行換行，然后再Gauss消去運算，得。進行了k-1步選主元，換行和消去的步驟，得，第k步先選主元，使 由于非奇異，有若，則進行順序Gauss消去法的第k步若，則對先換行： ，然后再進行類似順序Gauss消去法的運算。如上進行n-1步選主元，換行與消去法運算，得，此方程組與Ax=b等價。為上三角陣，再回代求解。例2.2 用列主元法解方程組Ax=b，計算過程取5位數字，其中解 選主元，換行再作行變換得到 對選列主元，作換行，計算再作行變換，得到消去過程完。回代計算得解此題精確解為而不用列主元的順序Gauss消去法有§3 直接三角分解方法（I）Doolittle分解法

6、根據A的元素來確定L.U中的元素 L，U的元素可由n步直接計算定出，其中第k步定出U的第k行，L的第k列。第1步 ，得出U的第1行元素。得出L的第1列的元素。第k步：假定已定出U的第1行到第k-1行的元素與L的第1列到第k-1列的元素。利用矩陣乘法有計算U的第k行 （1）對于 計算L的第k列 （2）由第1步，第2步，第n-1步就完成A=LU，解方程組 Ax=b , LUX=b 分兩步 Ly=b y=L-1b其實，L為單位下三角陣，逐次向前代入 Ux=y x=U-1y 其實，U為上三角陣，逐次向后回代定理3.1非奇異,，那么Ax=b可用直接分解方法來求解。例3.2求矩陣 的LU分解 解 先求出U

7、的第1行 求出L的第1列： U的第2行 L的第2列 U的第3行定理3.3 非奇異陣，若其順序主子式皆非零，則存在唯一的單位下三角陣L和上三角陣U，使得A=LU同樣地有A有唯一的分解，A=LDU；A非奇異條件不加，定理還真，L為單位下三角陣，D為對角陣，U為單位上三角陣。單位上三角陣A=LU（L單位下三角陣，U上三角陣），此分解稱為Doolittle分解。如果把A=LDU（LD）U=LU（L下三角陣，U單位上三角陣），此分解稱crout分解（II）直接三角分解法解線性代數方程組A非奇異，令 求解 等價于求解 例3.4 用Doolittle分解法解方程組 Ax=b, 其中解 （III） 三對角方程

8、組的追趕法設方程組 A為三對角矩陣如果A滿足LU分解條件，那么可以進行Doolittle分解。A是三對角陣，L，U有如下形式利用A=LU，及矩陣乘法有依次計算 解原來方程組可分成兩步 計算公式為：這個過程稱為解三對角方程線的追趕法。例 用追趕法解利用矩陣乘法有 追趕法在西方用Thomas算法的名稱定理3.5 其元素滿足 A非奇異，A分解中元素滿足定理可以看出，0， 用追趕法可以進行計算。又有的估計式，即追趕法中，中間變量有界，不會產生很大變化，由此可以有效計算出結果，即計算是穩(wěn)定的。定理條件即為追趕法穩(wěn)定計算的條件。（IV）對稱正定矩陣的cholesky分解解法 稱A正定A對稱正定A的全部特征

9、值為正A對稱正定A的順序主子式;由于A對稱正定，因此A有唯一的LU分解，定理3.6 ，對稱，且A的順序主子式 ，那么A可以唯一分解為 ，其中D為對角陣，L為單位下三角陣證 ，L為單位下三角陣，為單位上三角陣,由于 由LU分解的唯一性，從而有定理3.7 設 對稱正定，則存在唯一的對角元為正的下三角陣L使 這種分解稱為Cholesky分解證 利用上一定理知A有唯一分解 ，其中為單位下三角陣。 A對稱正定，A的順序主子式 。而 ，從而有 令 ，那么有 。具體分解方法當 時 由于求解過程中，需開方，因此稱其為平方根法。方程組求解（1） （2） 例3.8 用Cholesky方法求解方程組其中解 A對稱，

10、 ；A對稱正定 ， §4 矩陣范數（I）向量范數定義 如果向量（或）的某個實值函數，滿足條件：（1）充分必要條件（2）（3） ，三角不等式則稱是上的一個向量范數（或上的一個范數），一般用表示。 常用的向量范數向量的-范數 向量的1-范數 向量的2-范數例 計算向量 的范數。解 定理 4.1 ，非奇異，上一個范數，令 ，那么上的一個范數證 滿足條件 任 ； （A非奇異） 對任 上的一個范數定理4.2 設為上的一個向量范數，那么是的分量的連續(xù)函數。定義4.3 設為上兩個向量范數，若存在使得對任 有那么稱是等價的?？梢宰C明（II）矩陣范數定義4.4 設 上實值函數，對任有唯一的數相對應，如

11、果滿足條件（1） （2）（3）（4）那么稱為上矩陣范數定理4.5 設是上的向量范數，那么定義4.6 對于上的任一種向量范數，由定理4.5確定的矩陣范數稱為從屬于向量范數的矩陣范數，即稱從屬范數，也稱算子范數。由定理可以得出滿足此條件，稱所給的矩陣范數與向量范數是相容的。設，如果對于R（或C）中一個數，存在中非零向量使得那么稱為矩陣A的特征值，稱為A的屬于特征值的一個特征向量。 稱為A的特征多項式。為A特征值 為特征多項式的根。為其特征值，令 稱為A的譜半徑。定理4.7 證：設為A的任一特征值，為相應的特征向量，那么有由定理4.5 可以得出，單位矩陣 有；常用范數有定理4.8 設 ，那么有 （1

12、） ， 行范數 （2） ， 列范數 （3） 證：（1）對任 由于 的任意性，有下面將證明 存在 使取 滿足推論4.9 如果A是對稱 稱為對稱；設為A的特征值，為相應的特征向量 例4.10 求解 的特征多項式 Jordan標準形設，矩陣稱為屬于特征值的Jordan塊(階)。由若干個Jordan塊，所構成的分塊對角陣 稱為一個Jordan形矩陣定理4.11 復數域上每一個矩陣都相似于一個Jordan形矩陣，這個Jordan形矩陣除了其中Jordan塊的排列次序外是由原矩陣唯一確定的，稱這個Jordan形矩陣為原矩陣的Jordan標準形。定義4.12 ，如果存在可逆矩陣使得則稱A與B是相似的 。定理

13、4.13 對任，實數，那么至少存在一種算子范數（從屬范數）使得證明 對任 ，存在非奇異陣 使J為A的Jordan標準形。對于給定 ，定義對角矩陣令 其中 取的范數注意到是非奇異陣。引入新的向量范數（定理4.1）由定理4.1 ， 為向量范數。令 。對于引入的范數，令 。矩陣范數還具有如下性質： 是A的元素的連續(xù)函數 （等價性）對于上任兩范數，存在常數使得對于常用矩陣范數有定理4.14 設 是上的算子范數，矩陣滿足，那么非奇異，并且證 用反證法。設I+B為奇異陣，那么存在使得。 為B的一個特征值。從而有，并，矛盾于定理條件，所以I+B非奇異。令 §5 誤差分析（I）引言準確解 若A，b作

14、微小的擾動準確解 A， b的微小擾動 。引起B(yǎng)， 了解的很大變化，其原因？（II）條件數定義5.1 設為可逆矩陣，為一種矩陣的算子范數。稱為A的條件數如果矩陣范數取為，那么記同樣地， ， 逆矩陣定義5.2 ，劃去A的元所在的第行，第列，剩下的個元素按原來排法組成的n-1級矩陣的行列式稱為A的元的余子式，記為。令稱是矩陣A的元的代數余子式定義5.3 設是級方陣，用表示A的元的代數余子式，矩陣稱為A的伴隨矩陣。記為例5.4 求 解 解 例5.5 ，求解 ； 定義5.6 設 ，如果A的條件數是一個大數，那么稱A是壞條件的或稱A為病態(tài)的。條件數性質 證： 若A為正交陣 ，那么證： 設U為正交陣，那么有證： 它們特征值相同，所以有 設分別為A的按模最大與最小的特征值，那么 特別，A對稱，那么有 證 注意 為A的特征值 為的特征值A對稱時 （III）擾動方程組解的誤差估計如果有一個擾動，有一個擾動，那么方程組的解必擾動，即有 分析 對的影響，即的大小。定義5.7 如果 很小，而很大，那么稱是病態(tài)方程組。反之，如果很小，也很小，那么稱是良態(tài)方程組。定理5.8 設非奇異， ，；（常數向量b的擾動引起解的擾動的一種估計）證： ， 對于 例5.9 其解 假定b有擾動。 解 解之 可以看出，是很大的。方程組是病態(tài)的。