1、第2章 解線性代數(shù)方程組的迭代法,求解線性代數(shù)方程組主要有直接法和迭代法兩種常見方法。直接法一般適合小型的系數(shù)矩陣，為了求解現(xiàn)實當中常見的大型稀疏矩陣，下面我們將重點介紹迭代法。它是一種不斷套用一個迭代公式，逐步逼近方程的解的方法。 將討論兩類主要方法,一類是逐步逼近法，另一類是下降法，包括最速下降法和共軛梯度法,2.1 向量、矩陣范數(shù)與譜半徑,2.1.1 向量的范數(shù),定義2.1：設 ，（或 ）， 為 的實值函數(shù)，若 它滿足下列條件 ：,（1）非負性：,(2) 齊次性,(3) 三角不等式,則稱,則稱,則稱 為 上的一個向量范數(shù)， 的值稱為向量x的范數(shù)、,收斂于向量,的充要條件是,2.1.2 矩

2、陣的范數(shù),2.1.1 向量的范數(shù),定義2.3：設 ，（或 ）， 為 的實值函數(shù)，若 它滿足下列條件 ：,（1）非負性：,(2) 齊次性,(3) 三角不等式,則稱,則稱,則稱 為 上的一個向量范數(shù)， 的值稱為矩陣A的范數(shù)、,相容范數(shù),定理2.1 由（2.1.15）式所定義的矩陣范數(shù)為相容范數(shù),定理2.2 由（2.1.15）式所定義的矩陣范數(shù)為相容范數(shù)，下列等式成立,2.1.3 譜半徑,定理2.3 對任意 ，有,2.2 迭代法的一般形式與收斂性定理,2.2.1 迭代法的一般形式,已知線性代數(shù)方程組,首先將方程組（2.2.1）式改寫成等價的形式,從而建立迭代式：,稱 為迭代序列，并稱H為迭代矩陣。當

3、給定初始向量 后,可得到迭代向量序列 ，若,則 是線性方程組Ax=b的解,引理2.1：迭代法（2.2.3）式對任何初始近似 均收斂的充分必要條件是,引理2.2： 的充分必要條件是H的譜半徑,2.2.3 迭代法的收斂速度,定理2.5 當 時，由迭代法（2.2.3）式所定義的序列 滿足如下估計式：,2.3 Jacabi方法與GaussSeidel方法,2.3.1 Jacabi方法,設A=D-L-U, 則,即迭代格式為,也可改寫為,迭代矩陣為,分量形式為,2.3.2 GaussSeidel方法,在用簡單迭代法計算第i個新分量 時，前i-1個均已求出,一般來說，后算出來的值為更好的近似，因此可以用這些

4、新值來計算,利用最新值進行計算的方法稱為Seidel迭代法,對Jacabi迭代法運用Seidel技巧得到,其矩陣形式為,整理成一般迭代法的形式為,例題：P43 例2.1,2.3.3 對角占優(yōu)矩陣與不可約矩陣,2.4 松弛法,用 Jacobi迭代法和Gauss-Seidel迭代法解線性代數(shù)方程組時，有時收斂速度很慢，因此引入松弛法，只要松弛因子選取適當，算出的近似值就會更快地接近方程組的解，從而達到加快收斂的目的。,2.4.1 Richardson 迭代,2.4.2 Jacobi松弛法,2.4.3 SOR方法,對Gauss-Seidel方法引入?yún)?shù),得到迭代格式,稱(2.4.6)為解方程組Ax=

5、b的超松弛方法,簡記為SOR方法,矩陣形式為:,其迭代矩陣為,2.5 共軛梯度法,在松弛法中含有松弛因子，能使SOR迭代法收斂最快的松弛因子稱為最佳松弛因子，記為，但是最佳松弛因子的選擇往往很困難。因此引入共軛梯度法，它是一種不必選擇松弛因子而且收斂速度至少不低于SOR迭代法的一種迭代算法。它是50年代初期由Hestenes和Stiefel首先提出來的，目前有關(guān)的方法和理論已經(jīng)相當成熟，并且已成為求解大型稀疏線性方程組最受歡迎的一類方法。,2.5.1 等價的極值問題,設,是方程組Ax=b的精確解，即,如果A是對稱正定矩陣,則當且僅當 時,二次函數(shù),達到極小值 ,而 和二次函數(shù),它們的極小值是相同的，所以求解方程組Ax=b 等價于求二次函數(shù)H（x）的極小值點,2.5.2 最速下降法,從某個初始點 出發(fā)，沿H（x）在 點處負梯度方向,求得H(x) 的極小點 ,即,然后從 出發(fā)，重復上述過程得到 ，如此繼續(xù)下去，得到序列 ，使得,最速下降法的迭代格式為：,2.5.3 共軛梯度法,按照最速下降法從 出發(fā)得到新的近似 ，是直線,被橢球面的 中點,而且有,所以具體的基本步驟是：在點 處選取新的搜索方向 ， 使其與前一次的搜索方向 關(guān)于A共軛，即,然后從點 出發(fā)，在直線上 ，沿方向 求得H(x) 的極小點,由此得到方程組Ax