擾動誤差分析.doc

第2章 線性代數(shù)方程組數(shù)值解法I：直接法考慮方程組 (非奇異， 且 ) (2.6.1)設(shè)有誤差 有誤差，則因此引起解有誤差，即有擾動方程組 現(xiàn)在來研究如何通過和對的影響作出估計。定理2.6.1 設(shè) 方程組(2.6.1)中分別有擾動，因而解向量有誤差;又足夠小，使得 ，則有誤差估計式 證明 由 兩邊取范數(shù)有得到 得到 又注意到有 從而得到 ，故上述不等式左邊乘以，右邊圓括號第一項(xiàng)乘以，第二項(xiàng)乘以，并從括號中提出，則得(2.6.3)定理的結(jié)果實(shí)際包含兩種特殊情形：(1) A精確，即 ，有擾動，從而 (2) 有擾動，精確，即，這時 當(dāng)很小時，上式可近似表示為 2條件數(shù)與病態(tài)方程組定義 2.6.1 設(shè)為非奇異矩陣，稱數(shù) 即 為矩陣的條件數(shù)。矩陣的條件數(shù)的一些基本性質(zhì)：(1) 任何非奇異矩陣，對任一算子范數(shù)均有 (2) 根據(jù)定義 ,可得 (3) 若 為正交陣，即，則 又非奇異，則(4)設(shè) 與為按模最大和最小的特征值，則 特別地，若（即A對稱），則 若對稱正定，則 證明 略定理 2.6.2 （事后誤差估計）設(shè)方程組 ,非奇異，是精確解，是近似解，剩余向量 ,則有估計式 證明： 因，得 ，從而，于是，又由 ，于是得估計式右端 類似地，由上述 ，得，或 ，由 得，綜合兩式得估計式兩端 例 2.6.13事后誤差估計定理 2.6.2 設(shè) 方程組，非奇異，非奇異，是精確解，是近似解，剩余向量 ,則 有估計式 例題講解2例題2.1 對方程組Ax=b, A非奇異不一定能作順序Gauss消去過程，或者說，A非奇異不一定有LU分解。證 這類命題只需舉一個反例即可。反例要盡可能簡單，這里可考慮2階、元素為1或0。構(gòu)造反例一般要經(jīng)過多次“失敗-修正”過程。考慮A= ，易見A非奇異。顯然，順序Gauss消去過程的第1步就不能進(jìn)行。從LU分解來看，設(shè)有A=LU分解，則有=于是有b=0和ab=1同時成立，這就自相矛盾了。例題2.2 設(shè)方程組 =試手算（或輔以計算器）分別用 （1）順序Guass消去法 （2）列主元Gauss消去法（3）直接三角分解法求解，要求計算中取4位有效數(shù)字，最后結(jié)果舍入成3位有效數(shù)字。上述方程組用4位浮點(diǎn)數(shù)進(jìn)行計算而舍入為3位有效數(shù)字的精確解為： 解 （1）順序Gauss消去過程計算有 第1步消元 第2步消元 回代過程求解并舍入得 （2）列主元Gauss消去過程計算有 選主元換行 第1步消元 選主元，仍為 第2步消元 回代過程求解并舍入 （3）令A(yù)=LU，用Doolittle分解計算得 由Ly=b 解得 有Ux=y 解得 與精確解比較可見，列主元Gauss消去法的解精確度最高；其他兩種方法的解精確度較差，但彼此接近（這正好符合兩種方法實(shí)質(zhì)是一樣的情況）。例題2.3 Gauss消去法的一種自然而又簡單的改進(jìn)是所謂Gauss-Jordan消去法。先考慮順序Gauss消去法過程的情形。它只是把a(bǔ)這一列中a下面的元素消為0，而Gauss-Jordan消去過程則把a(bǔ)這一列元素的a以外全部消去為0，并且約化a=1。為此，需進(jìn)行n步消元，第n列也消為只剩下一個元素1，其余均為0（因此，0在這里也是必要的）。這樣一來，不用回代過程，方程組的解就在b的位置上?，F(xiàn)在依據(jù)上述導(dǎo)引，做（1） 試用Gauss-Jordan消去法解方程組 =（2） 試給出Gauss-Jordan算法的核心部分。（3） 由上述兩點(diǎn)能得出什么思考？解（1）用增廣矩陣的演變來描述求解過程于是有x=（2，2，3）。 （2）Gauss-Jordan消去法算法的核心部分為： 對k=1,2,，n，做 a(j=k，k+1，n，n+1) 對k=1，2，nik,做 a a-aa(j=k+1,n,n+1) 輸出解x=a(i=1,2,n)（4） 從上述做法可引發(fā)如下思考：Gauss-Jordan消去過程自然也可考慮加上選主元和換行的技巧；就計算量而言，Gauss-Jordan消去過程顯然要大（可推導(dǎo)其乘除運(yùn)算次數(shù)為級，而順序Gauss消去過程乘除運(yùn)算次數(shù)為級）。因此，用Gauss-Jordan消去法解方程組并不經(jīng)濟(jì)。但它有什么用途呢？這又引出一個新的思考。例題2.4設(shè)LR為非奇異下三角陣，試（） 寫出求解方程組Lx=的計算公式；（） 統(tǒng)計上述求解過程的乘除法次數(shù)；（） 給出求L的計算公式。解（）這是解下三角方程組的遞推公式：（）乘除法運(yùn)算，第一式有次，第二次=2時有2次，=時有n次，故上述公式的乘除運(yùn)算次數(shù)有=/2 (次)（）因L非奇異，存在，且由矩陣知識知也為下三角陣，記由，即考慮I的對角線元素，顯然有于是得?？紤]I對角線以下的元素，即對，則有于是得例題2.5設(shè)A=（aij）Rn*n 對稱，其順序主子式i0(i=1,2,n),試（1） 證明分解A=LDLT存在唯一，其中L為單位下三角陣，D為對角陣；（2） 寫出利用此分解求解方程組Ax=b的步驟（這稱為改進(jìn)的平方根法）；（3） 用改進(jìn)的平方跟法解方程組解 （1）由A的順序主子式不為零，故存在唯一分解式A=LU，L為單位下三角陣，U為上三角陣。改寫A=LU=LDU0 ，D為對角陣，U0為單位上三角陣。由A對稱，有A=AT=（LDU0）T=（DLT），又由分解的唯一性即得=L或U0=LT，于是代入可得A=LU=LDU0=LDLT存在唯一。（2）將A=LDLT代入Ax=b得LDLTx=b，令DLTx=y（即LTx=D-1y），則Ly=b，改進(jìn)平方根法如下：1） 將A直接分解為A=LDLT，即求出L，D；2） 求解下三角方程組Ly=b，得y；3） 求解上三角方程組LTx=D-1y，得x。（3）令A(yù)=LDLT由矩陣乘法并對比等式兩邊得 d3=2/3解Ly=b即 得y=解LTx=D-1y即得x=（1，-1，2）T可見改進(jìn)平方根法比原始平方根法避免了開方運(yùn)算；另一方面，改進(jìn)平方根法對滿足LU分解條件的對稱矩陣（不一定要正定）都適用。例題2.6 已知方程組Ax=b的系數(shù)矩陣形如：A=其中A的n-1階、主子距陣，*為其實(shí)數(shù)，。試設(shè)計一個求解上述方程組基于追趕的解決方案解 把A記為A=其中Bn-1為A的n-1階（對三角型）主子距陣，V，UR. 對用追趕法可作三角分解=P-Q再對A作三角分解，A=其中ZR(N-1)由下三角方程組Pz=v求出，WR(N-1)由方程組Q=uT(即下三角方程組QtW=U)求出， 由+=算出。由此，求解上述方程組的解決方案如下：（1）對用追趕法求出P，Q；（2）解下三角方程組Pz=v,求出z；（3）解下三角方程組QtW=U求出W；（4）計算=-z;（5）前推解下三角方程組y=b求出y;（6）回代解上三角方程組x=y求出x；例題2.7 設(shè)三對角方程組Ax=b,其中A= x= d=(1) 試建立A的順序主子式(k=1,2,n)的逆推公式。(2) 試設(shè)計求解上述三對角方程組的另一種有別于一般追趕法(基于LU分解)的新算法。解 補(bǔ)充記=1，則顯然有 = =一般地，猜想 =(k=3,4,n)用歸納法證明：當(dāng)k=2時，上式成立?，F(xiàn)假設(shè)有=則由=可知上述猜想成立。綜上所述，可得遞推公式：(2)由Ax=d的第一個方程可得 (1)即得由表示的關(guān)系式。將它代入第二個方程，又可得由表示的關(guān)系式如此繼續(xù)代入，直到第個方程，于是有如下形式的關(guān)系式 (k=2,3, ) (2)其中和待定?，F(xiàn)將形式如(2)的關(guān)系式代入Ax=d的第k(k=2,3, )個方程，則有 整理可得 (k=2,3, ) (3)與關(guān)系式(2)比較得 (k=2,3, ) (4)注意到方程組中的記號，令，。由(4)中取k=1,可得，代入(1)得，可見(2)式對k=1也成立；又由(4)中取k=n,則可得，而由于方程組Ax=d的第n個方程可以寫成，其中，從而上述的代入可直至第n個方程，也就是說(2)和(3)式對也成立，于是有。綜上所述，可得解三對角方程組的新算法如下：例題2.8 證明下列兩個命題(其中均為算子范數(shù))：(1) 設(shè)B且，則 IB非奇異； 。(2)設(shè)非奇異，奇異，則 證明 (1)這個命題通常被作為矩陣范數(shù)和譜半徑理論中的一個通用定理，它與本章2.6節(jié)提供的定理2.61和定理2.62組成最基本的3個定理?，F(xiàn)用反證法證明命題(1)。若IB奇異，則齊次方程組(IB)x=0 有非零解，且，于是有和。即有。