數(shù)值分析(07)解線性代數(shù)方程組的直接解法

1、第二節(jié) 高斯消元法及其計(jì)算機(jī)實(shí)現(xiàn)第三節(jié) 用矩陣分解法求解線性方程組第四節(jié) 誤差分析和解的精度改進(jìn)第五節(jié) 大型稀疏方程組的迭代法第三章 線性代數(shù)方程組的數(shù)值解法第一節(jié) 求解線性代數(shù)方程組的基本定理第六節(jié) 極小化方法線性代數(shù)方程組的一般形式 第一節(jié) 求解線性代數(shù)方程組的基本定理MATLAB實(shí)現(xiàn): x=Ab 數(shù)值求解方法有以下三條途徑（三種框架） 直接法：利用Gauss消元或矩陣分解，通過有限次運(yùn)算 可求出精確解。迭代法：構(gòu)造迭代格式，產(chǎn)生迭代序列，通過無限 次迭代過程求解。有限次截?cái)嗟媒平狻O小化方法：構(gòu)造二次模函數(shù)，用迭代過程求二次 模函數(shù)的極小化問題，即變分法（經(jīng)n 次運(yùn)算，理論上得精確解）

2、要求A 對(duì)稱正定(S.P.D) 第二節(jié) 高斯消元法及其計(jì)算機(jī)實(shí)現(xiàn) A b U g 三角形方程組包括上三角形方程組和下三角形方程組，是最簡(jiǎn)單的線性方程組之一。上三角方程組的一般形式是： 一、三角形方程組的解法 為求解上三角方程組，從最后一個(gè)方程入手，先解出 xn=bn/ann, 然后按方程由后向前的順序，從方程中依次解出xn-1,xn-2,x1。這樣就完成了上三角方程組的求解過程。這個(gè)過程被稱為回代過程其計(jì)算步驟如下： function X=backsub(A,b)%InputA is an nn upper- triangular nonsingullar matrix% -b is an n

3、1 matrix%OutputX is the solution to the system AX=b函數(shù)名返回變量參數(shù)表n=length(b);X=zeros(n,1);X(n)=b(n)/A(n,n);for i=n-1:-1:1 X(i)=(b(i)-A(i,i+1:n)* X(i+1:n)/A(i,i);endA的第i行、第i+1到n列元素構(gòu)成的行向量for j = n : 1 : 2 b ( j ) = b ( j ) / A ( j , j ); b (1: j - 1 ) = b (1: j - 1 ) - b ( j ) *A (1: j - 1 , j ) ; end b (

4、 1 ) = b ( 1 ) / A ( 1 ,1 );求解上三角方程組 Ax=b 高斯消元法是一個(gè)古老的直接法,由它改進(jìn)得到的選主元法,是目前計(jì)算機(jī)上常用于求低階稠密矩陣方程組的有效方法,其特點(diǎn)就是通過消元將一般線性方程組的求解問題轉(zhuǎn)化為三角方程組的求解問題。 高斯消元法的求解過程,可大致分為兩個(gè)階段:首先,把原方程組化為上三角形方程組,稱之為“消元”過程;然后,用逆次序逐一求出上三角方程組(原方程組的等價(jià)方程組)的解,稱之為“回代”過程. 高斯“消元”過程可通過矩陣運(yùn)算來實(shí)現(xiàn)。具體過程如下：二、高斯消元法解：將方程組Ax=b的系數(shù)矩陣與右端項(xiàng)合并為 進(jìn)行到第k步消元時(shí) 用回代過程求解上三角

5、方程組，即可得解向量 ( x1*,x2*, ,xn* )T.求解的全過程包括兩個(gè)步驟：消元和回代1 . 順序消元2 . 回代求解function X=gauss(A,b)%InputA is an nn nonsingullar matrix% -b is an n1 matrix%OutputX is the solution to the system AX=bMATLAB For Gaussian Eliminationn n=size(A); % 確定A的維數(shù)X=zeros(n,1);for k=1:n-1 for i=k+1:n % 消元過程 m=A(i,k)/ A(k,k); %

6、A(k,k) 0 A(i,k+1:n)= A(i,k+1:n)-m*A(k,k+1:n); b(i)= b(i)-m*b(k); endendX=backsub(A, b); %回代求解function X=gauss(A,b)%InputA is an nn nonsingullar matrix% -b is an n1 matrix%OutputX is the solution to the system AX=bMATLAB For Gaussian Eliminationn n=size(A); % 確定A的維數(shù)X=zeros(n,1);for k=1:n-1 for i=k+1:

7、n % 消元過程 A(i,k) =A(i,k)/ A(k,k); % A(k,k) 0 A(i,k+1:n)= A(i,k+1:n)- A(i,k) *A(k,k+1:n); b(i)= b(i)- A(i,k) *b(k); endendX=backsub(A, b); %回代求解 高斯消元法的計(jì)算量分析高斯消元法的乘除總運(yùn)算分析為消元次數(shù)k 消元乘法次數(shù) 消元除法次數(shù) 回代乘除法次數(shù) 1 n(n-1) n-1 2 (n-1)(n-2) n-2 . k (n-k+1)(n-k) n-k . n-1 2*1 1 n(n+1)/2高斯消元法的計(jì)算量為 乘 除 回代 當(dāng) n 充分大時(shí)為 Nn3/3

8、 消元法是解線性方程組的基本方法，具有計(jì)算簡(jiǎn)單的優(yōu)點(diǎn)，但有時(shí)由于主元過小，使得計(jì)算結(jié)果嚴(yán)重失真,實(shí)際中常采用選主元高斯消元法。例4:討論下面方程組的解法0.0001x1+x2=1 x1+x2=2假設(shè)求解是在四位浮點(diǎn)十進(jìn)制數(shù)的計(jì)算機(jī)上進(jìn)行0.100010-3 x1 + 0.1000 101 x2 = 0.1000 1010.1000 101 x1 +0.1000 101 x2 = 0.2000 101 解:本題用機(jī)器數(shù)系表示為 a11 =0.0001, m21=a21/a11=1/0.0001= 104, 消元得 回代解得 x2=1 , x1=0 嚴(yán)重失真! (本題的準(zhǔn)確解為 x1= 10000

9、/9999, x2=9998/9999 ）a22(2)= 0.1000 101 - 104 0.1000 101 = 0.00001 105 - 0.1000 105 (對(duì)階計(jì)算) = - 0.1000 105 0.100010-3 x1 + 0.1000 101 x2 = 0.1000 101 -0.1000 105 x2 = -0.1000 105 主元a11過小 選主元基本思想 用高斯消元法求解線性方程組時(shí),為避免小的主元.在進(jìn)行第k步消元前,應(yīng)該在第k列元素 (i=k,n)中找出第一個(gè)出現(xiàn)的絕對(duì)值最大者,例如 ， 再把第ik個(gè)方程與第k個(gè)方程組進(jìn)行交換,使 成為主元.我們稱這個(gè)過程為選

10、主元.由于只在第k列元素中選主元,通常也稱為按列選主元. 如果在第k步消元前,在第k個(gè)方程到第n個(gè)方程所有的xk到xn的系數(shù) (i=k,n;j=k,n)中,找出絕對(duì)值最大者,例如 三、選主元高斯消元法再交換第k,ik兩個(gè)方程和第k,jk列,使 成為主元. 稱這個(gè)過程為完全選主元. 不論是哪種方式選出主元,而后再按上面介紹的計(jì) 算步驟進(jìn)行消元的計(jì)算,一般都稱為選主元的高斯消元法.在實(shí)際計(jì)算中,常用按列選主元的高斯消元法.算法 列主元高斯消元法解線性方程組 Ax = b具體執(zhí)行行交換要通過工作單元 T。假設(shè)求解是在四位浮點(diǎn)十進(jìn)制數(shù)的計(jì)算機(jī)上進(jìn)行0.0001x1+x2=1 x1+x2=2將兩個(gè)方程對(duì)調(diào)，得 x1+x2=2 0.0001x1+x2=1在四位浮點(diǎn)十進(jìn)制數(shù)的計(jì)算機(jī)上,上式為 x1+x