第四章 解線性方程組的迭代法-數(shù)值

1、第四章第四章 解線性方程組的迭代法解線性方程組的迭代法 /* Iterative Techniques for Solving Linear Systems */求解求解bxA 思思路路與解與解 f (x)=0 的不動(dòng)點(diǎn)迭代相似的不動(dòng)點(diǎn)迭代相似 ，將，將 等價(jià)等價(jià)bxA 改寫為改寫為 形式，建立迭代形式，建立迭代 。從初值從初值 出發(fā)，得到序列出發(fā)，得到序列 。fxBx fxBxkk )()1()0(x)(kx計(jì)算精度可控，特別適用于求解系數(shù)為大型稀疏計(jì)算精度可控，特別適用于求解系數(shù)為大型稀疏矩陣矩陣 /* sparse matrices */ 的方程組。的方程組。研究研究 內(nèi)容：內(nèi)容： 如何

2、建立迭代格式？如何建立迭代格式？ 收斂速度？收斂速度？ 向量序列的收斂條件？向量序列的收斂條件？ 誤差估計(jì)？誤差估計(jì)？1 向量和矩陣范數(shù)向量和矩陣范數(shù) /* Norms of Vectors and Matrices */ 為了誤差的度量為了誤差的度量 向量范數(shù)向量范數(shù) /* vector norms */定義定義Rn空間的空間的向量范數(shù)向量范數(shù) | | 對任意對任意 滿足下列條件：滿足下列條件：nRyx ,00|;0|)1( xxx（正定性正定性 /* positive definite */ )|) 2(xx C 對任意對任意(齊次性齊次性 /* homogeneous */ ) |) 3

3、(yxyx （三角不等式三角不等式 /* triangle inequality */ )常用向量范數(shù)：常用向量范數(shù)： niixx11| niixx122| pnipipxx/11| |max|1inixx |limxxpp1 Norms of Vectors and Matrices Vector Norms定義定義向量序列向量序列 收斂收斂于向量于向量 是指對每一個(gè)是指對每一個(gè) 1 i n 都都有有 。)(kx*x*)(limikikxx 可以理解為可以理解為0|*|)( xxk定義定義若存在常數(shù)若存在常數(shù)C 0 使得對任意使得對任意 有有 , 則則稱稱范數(shù)范數(shù) | |A 比范數(shù)比范數(shù) |

4、 |B 強(qiáng)強(qiáng)。nRx BAxCx| 定義定義若范數(shù)若范數(shù) | |A 比比| |B 強(qiáng)，同時(shí)強(qiáng)，同時(shí)| |B 也比也比| |A 強(qiáng)，即強(qiáng)，即存在常數(shù)存在常數(shù) C1、C2 0 使得使得 ，則稱，則稱 | |A 和和| |B 等價(jià)等價(jià)。BABxCxxC|21 定理定理Rn 上一切范數(shù)都等價(jià)。上一切范數(shù)都等價(jià)?？梢岳斫鉃閷θ魏慰梢岳斫鉃閷θ魏蜗蛄糠稊?shù)都成立。向量范數(shù)都成立。HW: p.62 #6, #71 Norms of Vectors and Matrices Matrix Norms 矩陣范數(shù)矩陣范數(shù) /* matrix norms */定義定義Rm n空間的空間的矩陣范數(shù)矩陣范數(shù) | | 對任

5、意對任意 滿足：滿足：nmRBA ,00|;0|)1( AAA（正定性正定性 /* positive definite */ )|) 2(AA C 對任意對任意(齊次性齊次性 /* homogeneous */ ) |) 3(BABA （三角不等式三角不等式 /* triangle inequality */ )(4)* | AB | | A | | B | （相容相容 /* consistent */ 當(dāng)當(dāng) m = n 時(shí)時(shí))In general, if we have| AB | | A | | B | , thenthe 3 norms are said to be consistent

6、.Oh havent I had enough of new concepts? What do I need the consistency for?When you have to analyze the error bound of AB imagine you doing it without a consistent matrix norm1 Norms of Vectors and Matrices Matrix Norms常用矩陣范數(shù)：常用矩陣范數(shù)：Frobenius 范數(shù)范數(shù) ninjijFaA112| 向量向量| |2的直接推廣的直接推廣 對方陣對方陣 以及以及 有有nnRA

7、 nRx 22|xAxAF 利用利用Cauchy 不等式不等式 可證?？勺C。22|yxyx 算子范數(shù)算子范數(shù)/* operator norm */ 由向量范數(shù)由向量范數(shù) | |p 導(dǎo)出關(guān)于矩陣導(dǎo)出關(guān)于矩陣 A Rn n 的的 p 范數(shù)范數(shù):pxpppxAxxAApx|max|max|10| 則則ppppppxAxABAAB| 特別有：特別有： njijaAni1|max|1（行和范數(shù)行和范數(shù)） niijaAnj11|max|1（列和范數(shù)列和范數(shù)）)(|max2AAAT （譜范數(shù)譜范數(shù) /* spectral norm */ ）矩陣矩陣 ATA 的最大的最大特征根特征根 /* eigenvalu

8、e */HW: p.62 #2, #4, #51 Norms of Vectors and Matrices Matrix Norms注：注： Frobenius 范數(shù)范數(shù)不是不是算子范數(shù)。算子范數(shù)。 我們只關(guān)心有相容性的范數(shù)，我們只關(guān)心有相容性的范數(shù)，算子范數(shù)算子范數(shù)總是相容的?？偸窍嗳莸摹?即使即使 A中元素全為實(shí)數(shù)，其特征根和相應(yīng)特征向量中元素全為實(shí)數(shù)，其特征根和相應(yīng)特征向量 /* eigenvector */ 仍可能是復(fù)數(shù)。將上述定義中絕對值換仍可能是復(fù)數(shù)。將上述定義中絕對值換成成復(fù)數(shù)模復(fù)數(shù)模均成立。均成立。若不然，則必存在某個(gè)向量范數(shù)若不然，則必存在某個(gè)向量范數(shù)| |v 使得使得 對

9、任意對任意A 成立。成立。vvFxxAAx|max|0 Counterexample ?1|max|0 vvFxxIInx 譜半徑譜半徑 /* spectral radius */定義定義矩陣矩陣A的的譜半徑譜半徑記為記為 (A) = ，其中，其中 i 為為 A 的特征根。的特征根。|max1ini ReIm (A)1 Norms of Vectors and Matrices Spectral Radius定理定理對任意算子范數(shù)對任意算子范數(shù) | | 有有|)(AA 證明：證明：由算子范數(shù)的相容性，得到由算子范數(shù)的相容性，得到|xAxA 將任意一個(gè)特征根將任意一個(gè)特征根 所對應(yīng)的特征向量所對

10、應(yīng)的特征向量 代入代入u|uAuA |uu 定理定理若若A對稱，則有對稱，則有)(|2AA 證明：證明：)()(|2maxmax2AAAAT A對稱對稱若若 是是 A 的一個(gè)特征根，則的一個(gè)特征根，則 2 必是必是 A2 的特征根。的特征根。又：對稱矩陣的特征根為實(shí)數(shù)，即又：對稱矩陣的特征根為實(shí)數(shù)，即 2(A) 為非負(fù)實(shí)數(shù)，為非負(fù)實(shí)數(shù)，故得證。故得證。)()(22maxAA 對某個(gè)對某個(gè) A 的特征根的特征根 成立成立所以所以2-范數(shù)亦稱為范數(shù)亦稱為譜范數(shù)譜范數(shù)。1 Norms of Vectors and Matrices Spectral Radius定理定理若矩陣若矩陣 B 對某個(gè)算子范數(shù)滿足對某個(gè)算子范數(shù)滿足 |B