【正文】 } } 輸出解 x2 前次 計算結(jié)果 當(dāng)前 計算結(jié)果 原 系數(shù)矩陣 第 3章 線性代數(shù)計算方法 《計算方法》 Siedel迭代算法 輸入系數(shù)矩陣 M和向量 b，和誤差控制 eps x2={1,1,…..,1} // 賦初值 while( ||M*x2b||eps) { for(i=0。in。i++) { for(j=0。ji。j++) { x2[i] += M[i][j]*x2[j] } for(j=i+1。jn。j++) { x2[i] += M[i][j]*x2[j] } x2[i]=(b[i]x2[i])/M[i][i] } } 輸出解 x2 第 3章 線性代數(shù)計算方法 《計算方法》 第 3章 線性代數(shù)計算方法 《計算方法》 ? Siedel迭代收斂條件 定理：若 A滿足下列條件之一，則 Seidel迭代收斂。 ① A為行或列對角占優(yōu)陣 ② A對稱正定陣 注： 二種方法都存在 收斂性問題 。 有例子表明： Seidel法收斂時， Jacobi法可能不收斂；而 Jacobi法收斂時， Seidel法也可能不收斂。 第 3章 線性代數(shù)計算方法 《計算方法》 向量范數(shù) 在三維空間中 ,常用三種方法來衡量一個向量r=(x,y,z)T的 “ 長度 ” ,即 2 2 2 , , m a x ( , , )x y z x y z x y z? ? ? ?167。 7 迭代法的收斂性 這種衡量的方法可推廣到 n維空間的向量： x=(x1,x2,…,xn) 也即我們下面介紹的向量范數(shù) 。 T 第 3章 線性代數(shù)計算方法 《計算方法》 定義 1： 設(shè) n維向量 x∈ R ， 記對應(yīng)向量 x的一個實數(shù)為 ‖x‖,若 ‖x‖滿足下面三個性質(zhì) : (1)非負性 ， 即 ‖x‖≥0， 當(dāng)且僅當(dāng) x=0時 ， ‖x‖=0 (2)齊次性 ， ‖αx‖=｜ α｜ ‖x‖,α為任意實數(shù) (3)三角不等式性 ， ‖x+y‖≤‖x‖+‖y‖， y∈ Rn。 則稱該實數(shù) ‖x‖為向量 x的范數(shù) 。 可驗證 ， 對于不小于 1的正數(shù) p 11{}np piix??n 具有向量范數(shù)的三條基本性質(zhì)。 第 3章 線性代數(shù)計算方法 《計算方法》 稱上式為向量 x的 p范數(shù) ,記為 ‖x‖p， 即 11{}n ppipixx?? ?在 Rn中，常用的幾種向量范數(shù)有 : 121112 2 2 221221121...( ) . . .m a x { } m a x { , , . . . , }ninininiininx x x x xx x x x xx x x x x?????? ? ? ? ?? ? ? ? ?????第 3章 線性代數(shù)計算方法 《計算方法》 定義 2 設(shè) A為 n n階矩陣，定義 01s u p s u pxxAxA A xx????為矩陣 A的范數(shù) 。 可以證明 ， 矩陣范數(shù)滿足下列的幾個性質(zhì) : (1)非負性 ， ‖A‖≥0,當(dāng)且僅當(dāng) A= 0時 ,‖A‖=0 (2)齊次性 ， ‖αA‖=｜ α｜ ‖A‖,α為任意實數(shù) (3)三角不等式性 ,‖A+B‖≤‖A‖+‖B‖,B與 A為同階矩陣 (4)‖Ax‖≤‖A‖‖x‖ (5)‖AB‖≤‖A‖‖B‖ 第 3章 線性代數(shù)計算方法 《計算方法》 常見的矩陣范數(shù) 是 的最大特征值 第 3章 線性代數(shù)計算方法 《計算方法》 譜半徑： 設(shè) n n階矩陣 A的特征值為 λi(i=1,2,…,n),則稱 1( ) m a x iinA?????為矩陣 A的譜半徑 。 定理 3 設(shè) ρ(A)是矩陣 A的譜半徑 ， 則對于 A的任何一種范數(shù) ‖A‖,都有 ρ(A)≤‖A‖ 第 3章 線性代數(shù)計算方法 《計算方法》 定理 5 對于任意初始向量 x(0)和常數(shù)項 f,由迭代公式 x(k+1)=Ax(k)+f, k=0,1,2,… 收斂的充要條件是 ρ(A)＜ 1 通常 ρ(A)＜ 1很難證明，一般用 ‖A‖ ＜ 1來判斷迭代是否收斂 第 3章 線性代數(shù)計算方法 《計算方法》 167。 8 矩陣的特征值與特征向量的計算 求矩陣的特征值與特征向量是自然科學(xué)許多分支中一個重要的問題 。 n n階矩陣 A的特征值是其特征方程 det(AλI)=0 的根 ,而屬于特征值 λ的特征向量是線性方程組 (AλI)x= 0 的非零解 。 第 3章 線性代數(shù)計算方法 《計算方法》 乘冪法 在實際問題中 ,往往不需要求矩陣 A的全部特征值 ,而只要計算其按模最大或最小的特征值 ,也即只需求矩陣 A的部分特征值 。 乘冪法便是一種行之有效的方法 。 設(shè) n階實矩陣 A有 n個線性無關(guān)的特征向量 ,其特征值按模排列如下 : ｜ λ1｜ ≥｜ λ2｜ ≥…≥｜ λn｜ 其相應(yīng)的特征向量分別記為 x1,x2,…,xn 現(xiàn)求按模最大的特征值 λ1及其相應(yīng)的特征向量 x1。 第 3章 線性代數(shù)計算方法 《計算方法》 取非零初始向量 v0,作迭代構(gòu)成一向量序列 1022 1 021 2 0.........kk k kv A vv A v A vv A v A v A v???????????? ? ? ???? 因為特征向量 x1,x2,…,xn線性無關(guān) ,故 v0可以表示 成這 n個線性無關(guān)的向量的線性組合 ,即 v0=α1x1+α2x2+…+αnxn 第 3章 線性代數(shù)計算方法 《計算方法》 于是 vk=Ak(α1x1+α2x2+… +αnxn) =α1λ1kx1+α2λ2kx2+… +αnλnkxn 設(shè) λ1為實數(shù) ,將上式改寫成 21 1 1 2 211[ ( ) ( ) ]k k knk n nv a x a x a x???? ? ? ? 若｜ λ1｜＞｜ λ2｜ ,由上式有： 11 , 2 , 3 , 4 , ,i in?? ??第 3章 線性代數(shù)計算方法 《計算方法》 因此 ， 當(dāng) k充分大時 ， 只要 α1≠0,就有 vk≈λ1kα1x1 (1) (Aλ1I)vk≈α1λ1k (Aλ1I)x1=0 這說明 vk是相應(yīng)于特征值 λ1的特征向量的近似向量 。 由式 (1)， 當(dāng) k充分大時： v k+1≈λ1k+1α1x1=λ１ λ1kα1x1≈λ1vk 第 3章 線性代數(shù)計算方法 《計算方法》 例 10 求矩陣 2 1 01 2 10 1 2A?????? ? ??????的按模最大的特征值與相應(yīng)的特征向量 。 第 3章 線性代數(shù)計算方法 《計算方法》 (A6v0)1/(A5v0)1≈ (A6v0)2/(A5v0)2≈ (A6v0)3/(A5v0)3≈ (A7v0)1/(A6v0)1≈ (A7v0)2/(A6v0)2≈ (A7v0)3/(A6v0)3≈ 于是有 λ1≈ 相應(yīng)的特征向量為 x1≈(792,1120,792) 第 3章 線性代數(shù)計算方法 《計算方法》 若把 x1的第一個分量化為 1,則有 x1≈(1,1) 事實上 ,矩陣 A的特征值與相應(yīng)的特征向量為 1122332 2 ( 1 , 2 , 1 )2 ( 1 , 0 , 1 )2 2 ( 1 , 2 , 1 )TTTxxx???? ? ? ?? ? ?? ? ?第 3章 線性代數(shù)計算方法 《計算方法》 習(xí)題： 要求 : 習(xí)題三 ，２ ， 6 請盡力試著編寫程序 第 3章 線性代數(shù)計算方法 《計算方法》 1 1 212( ) 0...( ) 0nnnf x x xf x x x? ???? ??非 線 性 方 程 組 的 一 般 形 式， ， ... ， ， ... ，11(). . . ( ) 0()( ) 0nnx f xX F Xx f xFX? ? ? ?? ? ? ?? ? ?? ? ? ?? ? ? ?? ? ? ??令則 上 述 方 程 可 表 述 為非線性方程組的迭代法 第 3章 線性代數(shù)計算方法 《計算方法》 2221 0 8 01 0 8 0x x yx y x y? ? ? ? ???? ? ? ? ??1 2 2121[ ( ) ( ) 8]101[ ( ) 8]10k k kk k k kx x yy x y x???? ? ?????? ? ? ??例 解下列非線性方程組 k 0 1 2 … 18 19 x … y … k k 第 3章 線性代數(shù)計算方法 《計算方法》 11() ( ( ) ) ( )39。( )kk k k k kkFxX X X J X F XFx