計(jì)算方法3線性方程組數(shù)值解法

12學(xué)習(xí)要點(diǎn)消去法：包括高斯順序消去法和列主元高斯消去法；三對(duì)角方程組的追趕法；各種向量范數(shù)和矩陣范數(shù)的概念；解線性方程組的迭代法：Jacobi迭代法；Gauss-Seidel迭代法；迭代法的收斂性判斷；33.1問題的提出在自然科學(xué)和工程技術(shù)中很多問題的解決常常歸結(jié)為解線性代數(shù)方程組。例如:建筑工程中的結(jié)構(gòu)力學(xué)問題;用最小二乘法求實(shí)驗(yàn)數(shù)據(jù)的曲線擬合問題;用差分法或者有限元法解常微分方程，偏微分方程邊值問題等都導(dǎo)致求解線性方程組而且后面幾種情況常常歸結(jié)為求解大型線性方程組。4線性代數(shù)方面的計(jì)算方法就是研究求解線性方程組的一些數(shù)值解法與研究計(jì)算矩陣的特征值及特征向量的數(shù)值方法。5

式中，aij，bi為已知常數(shù)，xi為待求的未知量。記設(shè)有線性方程組6

則式（3.1）可寫出矩陣形式Ax=b

也可以把式（3.1）寫成增廣矩陣形式7關(guān)于線性方程組的數(shù)值解法一般有兩類：直接法：經(jīng)過有限步算術(shù)運(yùn)算，可求得方程組的精確解的方法（若在計(jì)算過程中沒有舍入誤差）迭代法：用某種極限過程去逐步逼近線性方程組精確解的方法，迭代法具有占存儲(chǔ)單元少，程序設(shè)計(jì)簡(jiǎn)單，原始系數(shù)矩陣在迭代過程中不變等優(yōu)點(diǎn)，但存在收斂性及收斂速度等問題83.2消去法一上三角方程組的解法設(shè)9寫出矩陣形式為：Ux=y其中U稱為上三角矩陣10若uii≠0（i=1,2,……n）,則由下至上依次回代得11二高斯消去法其中aij(1)=aij,ai,n+1(1)=bi1≤i,j≤n1、第1步消元。設(shè)a11(1)≠0,將的第一行乘以-li1(li1=ai1(1)/a11(1))，加到i行記原線性方程組為12其中

aij(2)=aij(1)-li1a1j(1)

，2≤i≤n；2≤j≤n+1

得到同解方程組13

從運(yùn)算過程來看，上面相當(dāng)于用矩陣左乘即

14若已經(jīng)進(jìn)行了k-1步次消元，同解方程組為：15其中，

aij(k+1)=aij(k)-likakj(k)

，k+1≤i≤n；k+1≤j≥n+1第k步消元：16即

第k步消元，也相當(dāng)于用矩陣左乘17

一直作到n-1步，得到同解方程組記則線性方程組為

：Ux=y18

例1用高斯消去法解線性方程組19解：20因此得到與原方程同解的三角方程組為通過回代，可以得到解為：X3=-3, x2=2, x1=121三列主元高斯消去法

≠0（k=1,2,……n-1）;若很小，也不適用；高斯消去法的問題：列主元消去法：與高斯消去法相似；防止舍入誤差的增長；選列主元，進(jìn)行行交換。22具體過程：設(shè)k-1步消元得到：23在進(jìn)行第k步消元前，選出第k列中位于對(duì)角線及其以下元素絕對(duì)值中的最大值者，即確定t使得將第t行和第k行互相交換；再按高斯消去法進(jìn)行第k步消元；若系數(shù)矩陣為對(duì)稱正定或嚴(yán)格對(duì)角占優(yōu)的方程組，不必選主元24

例2用列主元高斯消去法解線性方程組253.3追趕法其系數(shù)矩陣為三對(duì)角形，元素滿足以下條件：|b1|>|c1|>0|bi|≥|ai|+|ci|，且aici≠0i=2，3，……n-1;|bn|≥|an|>0。可以采用追趕法求解26消元過程:追趕273.4向量范數(shù)和矩陣范數(shù)為了研究線性方程組近似解的誤差估計(jì)和迭代法的收斂性，我們需要對(duì)Rn(n維向量空間)中的向量或Rnxn中矩陣的“大小”引入一種度量——向量和矩陣的范數(shù)。28向量范數(shù)對(duì)空間直角坐標(biāo)系任意向量其長度為：29它滿足如下3個(gè)條件

對(duì)任意x屬于R3，|x|≥0，|x|=0當(dāng)且僅當(dāng)x=0;

對(duì)任意常數(shù)c屬于R和任意x屬于R3，有|cx|=|c|·|x|;對(duì)任意x屬于R3，y屬于R3，有|x+y|≤|x|+|y|;這三個(gè)條件分別稱為向量長度的非負(fù)性、齊次性和三角不等式，推廣此概念即可得到向量范數(shù)30定義

設(shè)f(x)=||x||是定義在Rn上的實(shí)函數(shù)，如果它滿足如下條件：1對(duì)對(duì)任意x屬于Rn，||x||≥0，||x||=0當(dāng)且僅當(dāng)x=0;2對(duì)任意實(shí)常數(shù)c和任意x屬于Rn，有||cx||=|c|·||x||;3對(duì)任意x屬于Rn，y屬于Rn，有 ||x+y||≤||x||+||y||;

則稱||·||為Rn上的向量范數(shù)31

最常用的是三種范數(shù)：向量的1-范數(shù)：向量的2-范數(shù)：向量的∞-范數(shù)：示例(-5，-3，4)T的三種范數(shù)分別為：32定義設(shè)向量x,y屬于Rn上，則稱||x-y||為x和y之間的距離三種范數(shù)之間的關(guān)系33矩陣范數(shù)定義:

設(shè)A屬于Rn×n，||·||是Rn上的任一向量范數(shù)，稱為A的矩陣范數(shù)，記作Rn×n表示所有n×n階矩陣組成的實(shí)線性空間。34

最常用的三種矩陣范數(shù)：35矩陣范數(shù)的五個(gè)性質(zhì)：36定理:設(shè)A∈R，||·||為一種矩陣范數(shù)，則ρ(A)≤||A||證明：設(shè)λ為A的按模最大的特征值，x為相對(duì)應(yīng)的特征向量，則37例5設(shè)A=

383.5迭代法迭代法及其收斂性思路：與方程求根的迭代法思想類似，對(duì)于線性方程組：39通過變形，找到同解方程組：x=Bx+f建立迭代公式x(k+1)=Bx(k)+f若給定初始向量x(0)，就可以按迭代公式解出向量序列{x(k)}40定義：

設(shè)x(0)，x(1)，x(2),……是Rn中的一個(gè)向量序列，c屬于Rn是一個(gè)常向量。如果迭代矩陣則稱向量序列收斂于c，并記為如果向量序列{x(k)}收斂于x*，對(duì)迭代函數(shù)兩邊取極限，得

x*=Bx*+f41定理(充分條件)：對(duì)給定方程組x=Bx+f，如果||B||<1，則（1）此方程組有唯一解x*;（2）對(duì)任意向量x(0)屬于Rn，迭代格式x(k+1)=Bx(k)+f收斂于x*,且有||x(k+1)–x*||≤||B||||x(k)–x*||

k=0,1,2……（3）（4）42定理3.3

：對(duì)給定方程組x=Bx+f，迭代格式x(k+1)=Bx(k)+f對(duì)任意的初始值x(0)都收斂的充要條件為ρ(B)<1例

用迭代法解線性方程組43雅可比（Jacobi）迭代法由以下方程組的第i個(gè)方程解出xi(i=1,2……n),44得到一個(gè)同解的方程組,取初始向量x(0)=(x1(0),x2(0)x……

xn(0))T,利用迭代式反復(fù)迭代可以得到一個(gè)向量序列{x(k)}，稱為雅可比迭代格式，稱用此迭代格式求解方程組的方法為雅可比迭代法45可以將矩陣A分解為其中A=LUD46雅可比迭代格式的表達(dá)式為

Jacobi

迭代陣迭代矩陣稱為雅可比矩陣47例

用雅可比迭代法求解線性方程組，并分析迭代格式的收斂性48高斯-賽德爾（Gauss-Seidel）迭代法在雅可比迭代中，用新值及時(shí)取代舊值，即在求xi(k+1)時(shí)，用x1(k+1)，x2(k+1)，x3(k+1)，……

xi-1(k+1)進(jìn)分別代替x1(k)，x2(k)，x3(k)，……

xi-1(k)行進(jìn)行迭代計(jì)算49矩陣表示形式為G就被稱為高斯-賽德爾迭代矩陣50例

用高斯-賽德爾迭代法求