數值分析教案

數值分析教案緒論§1。數值分析的對象與特點隨著計算機的發(fā)展，人們對計算方法的需要就顯的越來越重要，同一個問題選擇的計算方法不同所得結果就完全不一樣。當然人力，物力，財力等的消耗也不盡相同?！稊抵捣治觥氛n程的主要內容就是研究如何較好的處理數學模型問題。它是數學的一個重要分支，其內容不像純數學那樣只研究理論，而是著重研究求解的數值方法及相關的理論。這些理論包括方法的收斂性，穩(wěn)定性及誤差分析。數值分析課程的特點：既有純數學高度抽象性與嚴密科學性的特點，又有應用的廣泛性與實際實驗的高度技術性的特點，是一門與使用計算機密切結合的實用性很強的數學課程?！?。誤差的來源及誤差分析的重要性我們先來考察一下用計算機解決實際問題的主要過程：實際問題→數學模型→數值計算方法→程序設計→→上機求結果在以上的過程中可以產生下列誤差：模型誤差：由實際問題轉化為數學模型時產生的誤差。觀測誤差：由觀測產生的誤差。截斷誤差（方法誤差）：近似解與精確解之間的誤差。EMBEDEquation.3今求，則有由于不可能得到精確值，若取，則此時的截斷誤差為另外，由于計算機在計算過程中并非是精確運算，它也是只對有限位數進行運算，對于超過位數的數字便自動施行四舍五入，這樣在計算過程中又產生一定的誤差，這種誤差稱為舍入誤差。本課程主要研究截斷誤差和舍入誤差。以下舉例說明誤差分析的重要性。例求 解：容易求得，而是個無理數，不可能取到精確值，今取，得到一個遞推公式：EMBEDEquation.3計算結果見下表：00.18232155↓00.18232155↑10.08839221610.08839221620.05803891820.05803891930.04313874230.04313873440.0343020840.0343063350.0284895850.0284683560.0242187560.0243249170.02176339↓70.02123260↑80.01618305↓80.01883699↑90.0301958890.0169261710-0.05097941100.01536914110.017324710110.01407133812-0.003290219120.01297664113-0.093374172130.01203986714-0.39544229140.0112229233152.0438787↓150.010520499↑16-10.156890160098975041750.843276170.00933600718-254.16082180.008875522191270.8567190.008253968220-6354.2338↓200.0087301587↑注：上表前兩列是由公式計算所得值，后兩列是由以下的公式計算所得值。我們分析一下的特性：ⅰⅱ；ⅲ；ⅳ由此可知公式計算的值是不可應用的。那么怎樣計算才能使結果可靠呢？由公式的遞推公式及可知，，所以，取，顯然誤差是比較大的。建立以下遞推公式：由式重新計算到的值（上表的后兩列）?？梢姳M管的初值取的比較粗糙，但計算到及時還是比較精確的。以下我們來分析EMBEDEquation.3兩式的區(qū)別。由于計算機只能對有限位數進行計算，當取用式計算時，因為帶有的誤差會一直傳下去。具體傳播過程為，設為理論值；為實際計算值，則有==（2-1）盡管誤差很小，但是卻是很大的。而用式時，有=（2-2）盡管誤差很大，但是卻是很小的。由以上兩式知，一個是誤差在積累，一個誤差在縮小。我們稱舍入誤差積累的遞推公式（比如）為不穩(wěn)定的，而稱舍入誤差縮?。ㄖ辽俨辉觯┑倪f推公式（比如）為穩(wěn)定的計算公式?！?。誤差的基本概念3-1誤差與誤差限定義1設為精確值，為的一個近似值，稱為近似值的絕對誤差。（簡稱誤差）。由于精確值是不知道的，所以誤差是不可計算的。通常只能估計，常用來估計，我們稱為誤差限。3-2相對誤差與相對誤差限定義2稱為的相對誤差。（與同上）由于是不知道的，所以通常取EMBEDEquation.3作為的相對誤差。這時產生的誤差可忽略不計。同樣，我們把其絕對值的上界稱為相對誤差限。記作。3-3有效數字我們知道，當精確值有很多位數時，常按四舍五入的原則取其前幾位數字作為其近似值。例：若取,或取，則它們分別具有誤差為及。誤差限分別為及。由此我們給出以下定義，定義3。若近似值的誤差限是某一位的半個單位，該位到的左邊第一位非零數字共有位，則稱有位有效數字。由此知，以上的3.14和3.1416作為的近似值分別具有3位和5位有效數字。有位有效數字的近似數可以寫成標準形式：（3-1）其中，是0—9中的數（），。且例如，用作為的近似值，可以寫成=.且EMBEDEquation.3,∴作為的近似值,它有6位有效數字。例：以下數字都是經過四舍五入得到的數字，問它們各有幾位有效數字？，，有效數字與相對誤差限的關系有以下定理，定理1。由（3-1）表示的近似數，若有位有效數字，則其相對誤差限為（3-2）反之，若的相對誤差限（3-3）則至少有位有效數字。定理說明，有效位數越多，相對誤差限越小。例：為使的近似數的相對誤差限小于0.1﹪，問查開方表時，要取幾位有效數字？解：設查開方表時取位有效數字，那么由（3-2）式并注意到，所以取，因此要使的近似數的相對誤差限小于0.1﹪，只需取滿足EMBEDEquation.3﹪解得n=3。即取。3-4數值運算的誤差估計數值運算的誤差估計一般是很復雜的。通常我們利用Taylor展開的方法來估計誤差，假設要計算的值，已知是的近似值。此時A的近似值為，那么作為A的近似值時的誤差限EMBEDEquation.3（3-4）而的相對誤差限為EMBEDEquation.3（3-5）例：要計算，取。求解：EMBEDEquation.3§4數值運算中誤差分析的若干原則一個工程技術問題的解決往往要經過若干次運算，若每一步都要分析誤差的話那當然是最好的，但這是不可能的。為鑒別計算結果的可靠性，我們提出若干原則。要使用穩(wěn)定的計算公式。要避免兩相近數相減。出現這種情況時，最好對公式進行處理，（1）時，變換（2）時，變換（3）充分大時，變換防止大數“吃掉”小數在計算機運算過程中，若兩個數的數量級相差很大，那么數量級小的數往往被忽略。這就是所說的大數“吃掉”小數。如：要計算53480+，，。就需要先計算之和，然后再加上53480。注意簡化計算步驟，減少運算次數。絕對值較小的數不宜做分母。第二章 方程求根在許多實際問題中，常常會遇到方程f(x)=0求解的問題。當f(x)為一次多項式時，f(x)=0稱為線性方程，否則稱為非線性方程。對于非線性方程，由于f(x)的多樣性，求其根尚無一般的解析方法可以使用，因此研究非線性方程的數值解法是十分必要的。本章主要介紹求非線性方程根的一些常用方法。它們是增值尋根法、二分法、迭代法、牛頓法及割線法。這些方法均是知道根的初始近似值后，進一步把根精確化，直到達到所要求的精度為止。也即求非線性方程根的數值方法。第一節(jié)

增值尋根法與二分法2.1.1增值尋根法設非線性方程f(x)=0的根為，增值尋根法的基本思想是，從初始值開始，按規(guī)定的一個初始步長h來增值。令=+h(n=0,1,2，…)，同時計算f()。在增值的計算過程中可能遇到三種情形：(1)f()=0，此時即為方程的根。(2)f()和f()同符號。這說明區(qū)間［,］內無根。(3)f()和f()異號，即有f()·f()＜0此時當f(x)在區(qū)間［,］上連續(xù)時，方程f(x)=0在［,］一定有根。也即我們用增值尋根法找到了方程根的存在區(qū)間，或均可以視為根的近似值。下一步就是設法在該區(qū)間內尋找根更精確的近似值，為此再用增值尋根法把作為新的初始近似值，同時把步長縮小，例如選新步長，這樣會得到區(qū)間長度更小的有根區(qū)間，從而也得到使f(x)更接近于零的，作為更精確的近似值，若精度不夠，可重復使用增值尋根法，直到有根區(qū)間的長度｜-｜＜(為所要求的精度)為止。此時f()或f()就可近似認為是零。或就是滿足精度的方程的近似根（如圖2-1）.2—1例1用增值尋根法求方程f(x)=-10=0的有根區(qū)間。解取=-4，h=1，則計算結果如下表2-1： 表2-1x-4-3-2-1012f(x)-10-1-2-7-10-514所以f(x)=0的有根區(qū)間為(1，2).再取=1，h=0.1，計算結果如表2-2： 表2-2x11.11.21.21.4f(x)-5-3.829-2.512-1.0430.584

所以f(x)=0更進一步的有根區(qū)間為(1.3，1.4)2.1.2二分法設f(x)在區(qū)間［a,b］上連續(xù)，且f(a)·f(b)＜0，則由連續(xù)函數性質知，方程f(x)=0在(a,b)內至少有一實根，為以下討論方便，設(a,b)內僅有唯一實根。二分法的基本思想：就是逐步對分區(qū)間［a,b］，通過判斷兩端點函數值乘積的符號，進一步縮小有根區(qū)間，將有根區(qū)間的長度縮小到充分小，從而求出滿足精度的根的近似值，如圖。2-2具體做法如下：用區(qū)間［a,b］的中點平分區(qū)間，并計算f()，同時記(,)=(a,b)，如果恰好有f()=0，則我們已經找到方程的根=。如若不然，f()≠0，如果f()·f()＜0，則記(,)=(,),如果f()·f()＜0，則記(,)=(,)，在后兩種情形區(qū)間(,)為新的有根區(qū)間。它包含在舊的有根區(qū)間(,)內，其區(qū)間長度是原區(qū)間的一半。對區(qū)間(，)施行同樣的辦法。即平分區(qū)間，求中點判斷函數值乘積的符號，得到新的有根區(qū)間(,)，它包含在區(qū)間(,)內，其區(qū)間長度是(,)的，(,)的。如此重復n次，如果還沒有找到方程的精確根，此時我們得到方程的有根區(qū)間序列：(,)，(,)，…,()，…它滿足(,)(,)…()…f()f()<0-=,n=1,2,…n-1當n充分大時，()的長度縮小到充分小，此時它的中點與夾在與之間，它們的距離也充分小，且序列｛｝滿足：上式表明=(2)即序列｛｝以等比數列的收斂速度收斂于。同時也表明序列｛｝是的一個近似值序列。因此對任意給定的精度<0，總存在n，使此時,我們可以取作為的近似值，即可滿足精度。例2：用二分法求方程f(x)==0在［1，2］內的一個實根，且要求滿足精度解：用二分法計算結果如表2-3：nf()11.02.01.52.37521.01.51.25-1.7968731.251.51.3750.1621141.251.3751.3125-0.8483951.31251.3751.34375-0.3509861.343751.3751.359375-0.0964171.3593751.3751.36718750.0323681.3593751.36718751.36328125-0.0321591.363281251.36718751.3652343750.000072101.363281251.3652343751.364257813-0.01605111.3642578131.3652343751.364746094-0.00799

迭代11次，近似根=1.364746094即為所求，其誤差這種方法的優(yōu)點是簡單，對f(x)只要求連續(xù)。它的收斂速度與比值為的等比級數相同，它的局限性是只能用于求實根，不能用于求復根及偶數重根。迭代法的基本思想由函數方程f(x)=0，構造一個等價方程：x=(1)從某個近似根出發(fā)，令，n=0,1,2，…(2)可得到序列｛｝，若｛｝收斂，即lim=只要連續(xù)，有也即從而可知是方程(1)的根，也就是f(x)=0的根。此時｛｝就是方程(1)的一個近似解序列，n越大，的近似程度就越好。若｛｝發(fā)散，則迭代法失敗。例1用迭代法求方程f(x)=-10=0在［1,2］內的一個近似根，取初始近似值.表2-4n(1)(2)(3)(4)01.51.51.51.51-0.8750.81651.286953771.3483997326.7322.99691.402540801.367376373-469.7(-8.651.345458381.3649570141.03

1.375170251.365264755

1.360094191.365225596

1.367846971.3652230587

1.363887001.365229948

1.365916731.365230029

1.364878221.3652300110

1.36541006

15

1.36522368

20

1.36523024

23

1.36522998

25

1.36523001

解原方程的等價方程可以有以下不同形式：(1)(2)(3)(4)對應的迭代公式有：(1)(2)(3)(4)取，列表計算如表2-2。與上節(jié)二分法比較，(3)、(4)都得到較好的結果，而用二分法達到同樣的精度，需要迭代27次，同時也看出迭代函數構造不同，收斂速度也不盡相同，迭代函數構造不當(如(1)，(2))，序列｛｝就不收斂。二、迭代法的幾何意義以上可以看到迭代法可能收斂，也可能不收斂。一般來說從f(x)=0，構造不止一種，有的收斂，有的不收斂，這取決于的性態(tài)。方程x=的根，在幾何上就是直線y=x與曲線y=交點的橫坐標,如圖2-3所示。（a）（b）（c）（d）圖2-3中(1)、(2)收斂，(3)、(4)發(fā)散。三、迭代法收斂的條件定義1如果在根的某個鄰域B=∈B，迭代過程，n=0,1,2，…收斂，則稱迭代過程在附近局部收斂。定理1設=()，在的某個鄰域B內連續(xù)，并且｜｜≤q<1，則對任何∈B，由迭代公式決定的迭代序列｛｝收斂于。且｜-｜≤(3)｜-｜≤(4)證：由拉格朗日中值定理，存在B，使由已知｜｜≤q,從而得｜-｜≤q｜｜≤…≤｜-｜所以這樣我們就證明了｛｝收斂于。再由拉格朗日中值定理，存在，使==()所以｜｜≤q｜｜≤…≤q｜｜(5)又由于｜｜=｜()+()+…+()｜≤｜｜+｜｜+…+｜｜所以｜｜≤(q+q+…+q+1)｜｜=｜｜令p→+∞,有｜-｜≤｜｜也即｜-｜≤｜｜這樣(4)式得證。再由(5)得｜-｜≤｜｜這樣(3)式也得證。這個定理是一個很實用的收斂定理。一方面它可以判定我們所構造的迭代函數是否收斂。另一方面(3)式還可以估計迭代次數。但結果偏保守，次數也偏大，實際中很少用。通常由(4)式，當｜｜<(為給定精度)時，認為｜-｜<就是滿足精度的一個近似解了。定理2〖HTSS〗對于方程x=,如果滿足(1)對任意x∈［a,b］，有∈［a,b］(2)對任意x∈［a,b］，有｜(x)｜≤q<1則對任意x∈［a,b］，迭代x=(x)所決定的序列｛x｝收斂于x=(x)的根x，且(3)、(4)式也都成立。證明與定理1相仿，故略去。以上兩定理中的條件要嚴格驗證都較困難，實用時常用以下不嚴格的標準。有根區(qū)間［a,b］較小，對某一x∈［a,b］,｜(x)｜明顯小于1，由(x)連續(xù)性知在的x某領域內｜(x)｜也小于1，則迭代收斂。例2考察例1中四種迭代法在根附近的收斂情況，取根的近似值為x=。解(1)17.75>1不收斂(2)5.128>1不收斂〖ZK〗〗(3)0.656<1收斂(4)0.122<1收斂)上例說明值越小，收斂速度就越快。四、迭代法的收斂速度用迭代法求方程的近似根，我們不僅要構造適當的要求它收斂，而且還需要知道它的收斂速度。關于收斂速度，有如下定義：定義2設序列｛x｝收斂于，令=-x，若存在某實數p≥1及正常數C，使(6)則稱序列｛x｝階收斂。如果序列｛x｝是由=(x)產生的，且p階收斂，則稱這種迭代過程是p階收斂的。當p=1，且C<1時，稱為線性收斂；當p=2時，稱為平方收斂(或二次收斂)；當1<p<2時，稱為超線性收斂。同前面一樣，設,=(x),=()則有-=(-x)(在在與x之間)所以=因而=||(n→∞)若0<<1,則迭代過程為線性收斂。若=0，由泰勒展開得(x)=()+設()≠0,則-=(x)-()=從而〖→>0(n→∞)此時迭代過程為二階收斂。定理3設在x=的根鄰近有連續(xù)的p階導數，當｜｜<1，且()≠0時，迭代過程=(x)為線性收斂；而當()=0，()≠0時為二階收斂。一般來說，若()=()=…=()=0，而()≠0，則稱=(x)在附近為p階收斂。第三節(jié)迭代收斂的加速從f(x)=0構造出的迭代格式x=(x)可能收斂也可能不收斂，在收斂的情形，收斂速度也取決于｜(x)｜的大小，當｜(x)｜接近于1時，收斂可能很慢。后兩種情形都影響迭代法的應用。能否從x=(x)出發(fā)構造出新的迭代形式，使收斂速度加快呢?松馳法對x=(x)引入一個任意常數作為參數,并假設≠-1，在方程兩邊加上x,得(1+)x=x+(x)于是x=(x)(1)顯然方程(1)與方程x=(x)等價，若令(x)=(x)，(1)可寫成x=(x)(2)為了使得用x=(x)作迭代比用x=(x)作迭代收斂的更快，我們希望|(x)｜比｜(x)｜更小，又由于(x)=(3)若(x)連續(xù)，則當x在根x*附近時，(x)也在(x*)附近，為此選取=-(x*)。這樣可以使得|(x)｜較小。但在求解過程中x*未知，故用x來代替，只要-()≠-1，記，于是代入(1)有松弛法迭代公式：x(n=0,1,2,…)(4)稱為松弛因子。松弛法的加速效果是明顯的，甚至不收斂的迭代函數經加速后一般也能獲得收斂。二、埃特金方法用松弛法計算時，要先算(x)，在使用時有時不太方便，假若在求得x以后，先求出和再利用和構造格式-由此得到埃特金（Altken）公式：==()-(n=0,1,2，…)(5)它的加速效果也十分明顯。例1分別用松弛法、埃特金法求方程-10=0在初值附近的一個根，取迭代格式解用松弛法計算，取因此松弛法的迭代公式為n=0,1,2，…列表計算如下：表2-3n01230.8908036860.8871231410.887130869

1.51.3649539161.3652300121.365230013

用埃特金方法計算，迭代格式為n=0,1,2，…列表計算如下：表2-4n01230.8908036860.8871231410.887130869

1.51.3649539161.3652300121.365230013

與上節(jié)例1中(3)與(4)相比收斂速度明顯增加。第四節(jié)

牛頓法解非線性方程f(x)=0的牛頓(Newton)法，就是將非線性方程線性化的一種方法。它是解代數方程和超越方程的有效方法之一。一、牛頓法的基本思想把非線性函數f(x)在處展開成泰勒級數f(x)=f()+(x-)f′()+(x-)+…取其線性部分，作為非線性方程f(x)=0的近似方程，則有f()+(x-)f′()=0設f′()≠0，則其解為x=-(1)再把f(x)在x處展開為泰勒級數，取其線性部分為f(x)=0的近似方程，若f′(x)≠0，則得x=-如此繼續(xù)下去，得到牛頓法的迭代公式：x=-(n=0,1,2,…)(2)例1用牛頓法求方程f(x)=x+4x-10=0在［1,2］內一個實根，取初始近似值x=1.5。解f′(x)=3x+8x所以迭代公式為：x=-n=0,1,2，…列表計算如下：n01231.51.37333331.365262011.36523001

二、牛頓法的幾何意義方程f(x)=0的根就是曲線y=f(x)與x軸交點的橫坐標x*，當初始近似值選取后，過(,f())作切線，其切線方程為：y-f()=f′()(x-)它與x軸交點的橫坐標為x=-一般地，設是x*的第n次近似值，過(,f()作y=f(x)的切線，其切線與x軸交點的橫坐標為：x=-即用切線與x軸交點的橫坐標近似代曲線與x軸交點的橫坐標，如圖2-4。2-4牛頓法正因為有此明顯的幾何意義，所以也叫切線法。三、牛頓法的收斂性及收斂速度定理設f(x)在［a,b］滿足(1)

f(a)·f(b)<0(2)f(x)∈［a,b］，f′(x),f″(x)均存在，且f′(x)與f″(x)的符號均保持不變。(3)f()·f″(x)>0，、x∈［a,b］，則方程f(x)=0在［a,b］上有且只有一個實根，由牛頓法迭代公式計算得到的近似解序列｛｝收斂于方程f(x)=0的根x*。由方程f(x)=0得到的牛頓迭代形式x=x-==1-=由于f(x*)=0，所以當f′(x*)≠0時，(x*)=0，牛頓法至少是二階收斂的，即牛頓法在單根附近至少是二階收斂的，在重根附近是線性收斂的。牛頓法收斂很快，而且可求復根，缺點是對重根收斂較慢，要求函數的一階導數存在。

四、牛頓二階導數法這里將簡單介紹一下牛頓二階導數法。對其幾何意義及收斂性不作詳細的敘述，讀者可仿照牛頓法進行討論，其基本思想是：將f(x)在處展開泰勒級數f(x)=f()+f′()(x-)+f″()(x-)+…取右端前三項近似代替f(x)，于是得f(x)=0的近似方程為f()+f′()(x-)+f″()(x-)=0也即f()+(x-)[f′()+f″()(x-)]=0(3)設其解為.利用(1)，-=-，代入(3)中括號內-,則得f()+(-)[f′()+f″()]=0于是解出，得=-重復以上過程得：=-于是得牛頓二階導數法的迭代公式為：=-n=0,1,2,…(4)上式與牛頓法迭代公式(2)相比，利用此公式求根收斂更快，迭代次數更少。其缺點是要求f(x)的二階導數存在。第五節(jié)割線法用牛頓方法解非線性方程f(x)=0，雖然在單根附近有較高的收斂速度，但需要計算f′(x)。若f(x)比較復雜時，每次計算f′(x)帶來很多不便；如果用不計算導數的迭代方法，往往只有線性收斂的速度。本節(jié)我們介紹割線法，采取在迭代過程中不僅用前一步處的函數值，而且還使用處的函數值來構造迭代函數。這樣做能提高迭代的收斂速度。一割線法的基本思想設非線性方程f(x)=0，其中f(x)為［a,b］上的連續(xù)函數，且f(a)·f(b)<0。設,為f(x)=0的根x*的兩個初始近似值，過(,f())和(,f())作一直線，其方程為：y=f()+(x-)當f()≠f()時，此直線與x軸交點為=-(-)(1)作為f(x)=0根的第二次近似值，可以預期比,更接近于x*。重復上述過程可得,，…，,從而可得割線法的迭代公式：=-(-)(n=1,2,…)(2)很明顯，它也可由牛頓法用差商近似代替微商f′()而得。若把(2)中的換為,則得迭代公式=-(-)(n=1,2,…)(3)顯然，它也可由牛頓法用差商近似代替微商f′()而得。以上兩種迭代方法都稱為割線法(或弦截法)。(2)稱為雙點割線法。也稱為有記憶割線法。(3)稱為單點割線法。它們都需要x*鄰近的兩個初始近似值,才能啟動。例1

用雙點割線法求方程x-3x+1=0在0.5附近的根。精確到小數點后第六位。解：令f(x)=x-3x+1=-(-)(n=1,2,…)即=-(-)(n=1,2,…)取=0.5，=0.2列表計算如下：表2-6n123450.50.20.3563220.3477310.3472950.20.3563220.3477310.3472950.347296

二割線法的幾何意義雙點割線法是用過點(,f())和(,f())兩點的割線與x軸交點的橫坐標x2作為x*的新近似值。重復此過程，用過點(，f())和(,f())兩點的割線法與x軸交點的橫坐標來作為x*的下一新的近似值。如圖2-5。單點迭代法則是用過點(,f())和(,f())兩點的割線與x軸交點的橫坐標來作為x*的近似值，如圖2-6。2-52-6三割線法收斂的速度定理設方程f(x)=0的根為x*。若f(x)在x*附近有連續(xù)的二階導數，f′(x*)≠0，而初值,充分接近x*，則雙點割線法的迭代過程收斂，收斂速度為｜-x*｜≈｜-x*｜這說明它是超線性收斂的(p=1.618>1)。而單點割線法在單根附近是線性收斂的。第三章解線性方程組的直接法3.1引言與矩陣一些基礎知識3.1.1引言線性方程組求解是科學計算中最常遇到的問題，如在應力分析、電路分析、分子結構、測量學中都會遇到解線性方程組問題.在很多廣泛應用的數學問題的數值方法中，如三次樣條、最小二乘法、微分方程邊值問題的差分法與有限元法也都涉及到求解線性方程組.本章討論n個變量n個線性方程的方程組求解，其表達式為通常用向量矩陣表示，則上述方程可寫成(3.1.1)其中并記做，分別表示A為n×n階實矩陣，x,b為n維實向量.根據線性代數知識可知A非奇異，即detA≠0，方程組(3.1.1)有唯一解，并可用Cramer法則將解用公式表示出來，但由于計算量太大，因此不能用于實際求解.本章要討論的直接方法是將方程組(3.1.1)轉化為三角方程組，再通過回代求三角方程組的解.理論上，直接法可在有限步內求得方程的精確解，但由于數值運算有舍入誤差，因此實際在計算機上求得的數值解仍是近似解，仍要對它進行誤差分析.解線性方程組的另一類方法是迭代法，將在下一章討論.下面給出本章和下章需要的一些矩陣基礎知識.3.1.2矩陣特征值與譜半徑定義1.1設，若存在一個數(實數或復數)和非零向量，使(3.1.2)則稱為A的特征值，x為A對應的特征向量，A的全體特征值稱為A的譜，記作，即(3.1.3)稱為A的譜半徑.由式(3.1.2)知，可使齊次方程有非零解，故系數行列式det(I-A)=0，即(3.1.4)稱為特征多項式，方程(3.1.4)稱為特征方程，在復數域中有n個根，故由行列式(3.1.4)展開可知：于是，矩陣的n個特征值是它的特征方程(3.1.4)的n個根，A的跡trA有(3.1.5)(3.1.6)此外，A的特征值和特征向量x還有如下性質：(1)與A有相同的特征值及相同的特征向量x.(2)若A非奇異，則的特征值為，特征向量為x.(3)相似矩陣有相同特征多項式.例3.1求的特征值及譜半徑.解A的特征方程為故A的特征值為.譜半徑為.講解：根據特征值定義（3.1.2）式知它等價于齊次方程有非零解，它的充分必要條件是系數行列式為零即，將行列式展開，由（3.1.4）看到它是的n次多項式，記作稱為特征多項式，將行列式對角元素相乘，即它決定了中及的系數，因為行列式的展開式中其余各項的次數均不超過，故，利用，有n個根（在復數域中，復根成對出現），故，可知，于是有，稱為矩陣A的跡。另外行列式中令，則得，從而得到（3.1.6）3.1.3對稱正定矩陣定義1.2設，如果，即，則稱A為對稱矩陣，若還滿足對于，則稱A為對稱正定矩陣，如果對有，則稱A為半正定矩陣.當A為對稱時，A的特征值皆為實數，且有n個線性無關的特征向量.對稱正定矩陣還有以下重要性質：(1)對稱正定，則〖WTHX〗A非奇異，且也對稱正定；(2)A對稱正定的充要條件是，A的所有特征值；(3)A對稱正定，則A的對角元素；(4)A對稱正定的充要條件是A的所有順序主子式以上性質可直接由定義證明，證明略.講解：對稱正定矩陣性質都可直接由定義證明為了更好理解，下面就性質（1）給出證明先證A非奇異，用反證法，假定A奇異，則，使，故與A正定的假定矛盾，故A非奇異，即存在。由于是，即對稱，再證正定。對，令，于是，由A正定得，故也正定。3.1.4正交矩陣與初等矩陣定義1.3若且，則稱A為正交矩陣.由定義知，且與均為正交陣，且有.定義1.4設.則為單位矩陣，稱為(實)初等矩陣.顯然，例如，則設，則若σ已知，選，使則當時，令(3.1.7)則有(3.1.8)此外，還有(3.1.9)下面給出兩個常用的初等矩陣.例3.2初等排列矩陣.令則矩陣也稱初等置換矩陣，它由單位矩陣I交換i行與j行得到，它有以下性質：(1)，故為正交矩陣.(2).(3)是將A的i,j行互換，是將A的i,j列互換.例3.3初等下三角矩陣.設,則記稱為指標為j的初等下三角矩陣，即(3.1.10)矩陣有以下性質：(1).(2).(3)，為單位下三角矩陣.初等下三角矩陣也稱為Gauss變換矩陣.講解：例3.2中給出的初等排列陣，其作用是實現矩陣A的i,j行互換及列互換，即表示A的i、j兩行互換，而，表示A的i,j兩列互換。例3.3初等下三角陣，由（3.1.10）所表示的矩陣，在下節(jié)Gauss消去法中有應用，其逆矩陣，表示為3.2Gauss消去法3.2.1順序消去法Gauss消去法就是將方程組(3.1.1)通過(n-1)步消元，將(3.1.1)轉化為上三角方程組(3.2.1)再回代求此方程組的解.下面記增廣矩陣，即第1步設，計算l，記為，若用乘第一行加到第i行，可消去,用Gauss變換矩陣表示令其中一般地，假定已完成了(k-1)步消元，即已將轉化為以下形式：第k步，假定，計算(3.2.2)記，，則其中(3.2.3).當k=1,2，…,n-1則可得到，即方程組(3.2.1).直接回代解(3.2.1)得，(3.2.4)并且有，由以上順序消去過程可得如下定理.定理2.1設非奇異，則通過兩行互換總可使，k=1,2，…,n-1.可將方程組(3.1.1)轉化為(3.2.1)并求得方程組(3.1.1)的解為(3.2.4)，且有.如果不做行交換，則使的條件如下.定理2.2非奇異，且各階順序主子式，則，k=1,2，…,n-1.證明用歸納法，當，故.現假設(k-1)成立，即，對i=1，2，…,k-1已推出，故Gauss消去法能進行(k-1)步消元，A已約化為，即故對k=1,2,…,n均成立，證畢.在整個消去法消元過程中，k從1到(n-1)共需乘除法運算次數為加減法次數為回代過程中由公式(3.2.4)可知乘除法次數為，加減法次數為，于是Gauss消去法的乘除法總次數為，加減法次數為例3.4用Gauss消去法解方程組并求detA.解消元得再由(3.2.4)回代，得解講解：Gauss消去法是將方程組AX＝b,通過消元轉化為上三角方程組（3，2，1）求解，消元第一步做完后有用矩陣表示第K－1步完成后得到當，可做K步，得到得到，對應的方程組就是（3.2.1），利用公式（3.2.4）就可求得解。定理2.2給出了進行順序消去法的條件，即A的所有順序生子式，而方程（3.1.1）解存在唯一的條件是3.2.2消去法與矩陣三角分解上述Gauss消去法的消元過程從矩陣變換角度看，就是進行了(n-1)次的Gauss變換，即若令，則，則由，得其中L為單位下三角矩陣，U為上三角矩陣.定理2.3設非奇異，且A的順序主子式(i=1,2,…,n-1)，則存在唯一的單位下三角矩陣L和上三角矩陣U，使A=LU.證明存在性已從上面A的Gauss變換中得到，下面只證唯一性.假定A有兩種不同的分解式，其中，為單位下三角矩陣，為上三角矩陣，因A非奇異，故，，，均非奇異，于是上式用左乘，用右乘，則得因仍為上三角矩陣，則為上三角矩陣，而仍為單位下三角矩陣，故，且.由此可得=，=.證畢.將A分解為單位下三角矩陣L及上三角矩陣U的乘積A=LU，稱為A的Doolittle(杜里特爾)分解.講解：從上面討論的消元過程看到每消元一步就是用相應Gauss變換左乘矩陣A，因而有（上三角陣），即，其中為單位下三角，這就是A的三角分解。它說明只要能進行順序Gauss消元就能將矩陣A分解為LU的乘積。定理2.3給出了LU分解的存在唯一性條件。3.2.3列主元消去法在順序消元過程中，只要(k=1,2,…，n-1)即可進行計算，但如果很小，則將導致舍入誤差增長，使解的誤差很大，見下例.例3.5用Gauss消去法求解方程組解因,，故方程有唯一解，且精確解為.若用Gauss消去法取四位有效數字計算，可得解，與比較，誤差很大，若將兩個方程互換為仍用Gauss消去法求解，則得，它有四位有效數字，即.這例子表明通過行交換可避免舍入誤差增長，這就是列主元消去法的基本思想。其計算步驟是：第1步，在中的第1列選主元，即行為主元.若，將的第行與第1行互換，再按消元公式計算得到.假定上述過程已進行(k-1)步，得到.第k步，在中第k列選主元，，若，則在中將與k行互換(若=k則不動)，再按公式(3.2.2)、(3.2.3)求出.對k=1,2,…，n-1，重復以上過程則得，如果某個k出現主元，則表明detA=0，方程沒有唯一解或嚴重病態(tài)，否則可由(3.2.4)求得解.上述每步行交換后再消元相當于(3.2.5)其中是指標為k的初等下三角矩陣，為初等排列矩陣，=k時，表示不換行，經過(n-1)步換行與消元，A化為上三角矩陣，即它也表明當A非奇異時，存在排列矩陣P(若干初等排列矩陣的乘積)，使PA=LU，其中L為單位下三角矩陣，其元素，U為上三角矩陣.例3.6用列主元消去法解Ax=b，其中解：由回代公式(3.2.4)求得解此例的精確解為，可見結果精度較高.若不選列主元Gauss消去法，求解得，誤差較大.除列主元消去法外，還有一種消去法，是在A的所有元素中選主元，稱為全主元消去法.因計算量較大且應用列主元已能滿足實際要求，故不再討論.目前很多數學軟件庫都有列主元消去法，可直接調用.講解：為了減少計算的舍入誤差，使用消去法通常都要選主元，目前最常用的是列主元消去法，也就是每步消元之前選主元，當第一步選A中第1列的主元，即，然后將行與1行互換，再進行消元，以后每步消元做法類似，先選主元，再消元。3.3直接三角分解法3.3.1Doolittle分解法上節(jié)定理2.3已經證明當非奇異，且(i=1,2,…,n-1)，則A可做LU分解，即A=LU，其中L為單位下三角矩陣，U為上三角矩陣.現在可直接通過矩陣乘法求得L及U的元素，于是解方程(3.1.1)就轉化為求解(3.3.1)若令Ux=y，則解方程(3.1.1)轉化為求兩個三角方程下面直接用矩陣乘法求U及L的元素，由直接得到(3.3.3)若已求得U的(i-1)行及L的(i-1)列，則由矩陣乘法有可得(3.3.4)這就求得U的第i行元素，求L的第i列可由若，可得(3.3.5)計算規(guī)律是先由(3.3.3)求U的第1行和L的第1列元素，再由(3.3.4)求U的第i行(i=2,3,…,n)元素，再由(3.3.5)計算L的第i列元素,求出L及U后再解方程(3.3.2)，其計算公式為(3.3.6)(3.3.7)例3.7用Doolittle分解法求方程的解.解先用公式(3.3.3)～(3.3.5)求出,，，，，，，，于是，再由(3.3.6)求得的解由(3.3.7)求得的解.講解：直接利用矩陣乘法求A＝LU的L及U的元素，一般只要掌握矩陣乘法規(guī)則，對U中元素由上而下逐行計算，L元素由左向右逐列計算，總的次序是先算一行U的元素再算一列L元素，按次序交替進行，完成分解后再解兩個三角方程組（3.3.2），計算公式為（3.3.6）和（3.3.7）。3.3.2Cholesky分解與平方根法當對稱正定時，A的順序主子式，故由定理2.3知，A=LU的分解存在且唯一，其中L為單位下三角矩陣，U為上三角矩陣，且.定理3.1若對稱，且A的順序主子式，則A可唯一分解為，其中L為單位下三角矩陣，D為對角矩陣.證明由定理2.3可知A=LU，而，故這里，，為單位上三角矩陣.因.由A=LU的分解唯一性，得，于是有.證畢.定理3.2若對稱正定，則存在唯一的對角元為正的下三角矩陣L，使A分解為(3.3.8)這種分解稱為Cholesky分解.證明由定理3.1可知,這里為單位下三角矩陣，，.由于A的順序主子式，因A正定，故，可推出.若記，于是有.若，則L為下三角矩陣，且對角元為正，故有，即為(3.3.8).證畢.利用Cholesky分解式(3.3.8)將求方程組(3.1.1)的解轉化為求方程的解.令,則得(3.3.9)根據矩陣乘法，由，求L的元素CONTROLShockwaveFlash.ShockwaveFlash.1\s得當i=j有(3.3.10)當i＞j,得(3.3.11)注意當j=1時有，對j=2，3，…，n由(3.3.10)，(3.3.11)逐列求得L的元素，這就是A的Cholesky分解，然后再解(3.3.9)的兩個三角方程組，得(3.3.12)及(3.3.13)這就是對稱正定方程組的平方根法.其工作量約為Doolittle分解法的一半.另外，由于故有這表明分解過程中矩陣L中元素的數量級不增長，因此平方根法計算是數值穩(wěn)定的.例3.8用平方根法求以下方程組的解.解先驗證系數矩陣A對稱正定，對稱顯然，，，故A對稱正定，可用Cholesky分解(3.3.10)，(3.3.11)計算，求得即，求解.由公式(3.3.12)得,再由的公式(3.3.13)求得Cholesky分解法要用到開方運算，為避免開方運算，可將A分解為(其中L為單位下三角矩陣)，再分別解方程組及或，這種方法稱為改進平方根法，可作為練習自行推導.講解：當A為對稱正定矩陣時，可將A分解為，其中L為下三角陣，這種分解為Cholesky分解，它也是存在唯一的，求L的元素仍可直接用矩陣乘法，由公式（3.3.10）和（3.3.11）逐列求得L的元素，注意，當j＝1時得然后對j＝2，3...n逐列計算.由（3.3.10）可得及，所以這表明，平方根法得到的中間量是有界的，完全可以控制，舍入誤差也同樣可以控制，故計算過程是穩(wěn)定的。使用平方根法要計算開方，為避免開方可用改進平方根法，將A分解為，即其中，由矩陣乘法，比較等式兩邊，按行計算L，T元素，對于i=2,3,…n解方程組以下步驟進行：所以，這就是改進平方根法。3.3三對角方程組的追趕法在許多科學計算問題中，常常所要求解的方程組為三對角方程組，即(3.3.14)其中(3.3.15)并滿足條件(3.3.16)稱A為對角占優(yōu)的三對角矩陣，對這種簡單方程可通過對A的三角分解建立計算量更少的求解公式.現將A分解為下三角矩陣L及單位上三角矩陣U的乘積.即A=LU，其中(3.3.17)直接用矩陣乘法公式可得到于是有(3.3.18)由此可見將A分解為L及U，只需計算及兩組數，然后解，計算公式為(3.3.19)再解Ux=y則得(3.3.20)整個求解過程是先由(3.3.18)及(3.3.19)求,及，這時i=1,…,n是"追"的過程，再由(3.3.20)求出，這時i=n,…,1是往回"趕"，故求解方程組(3.3.14)的整個過程稱為追趕法.它只用(5n-4)次乘除法運算，計算量只是,而通常方程組求解計算量為，另外，追趕法計算,是數值穩(wěn)定的，因為在式(3.3.16)表示的條件下，可證明所以，追趕法是一種計算量少及數值穩(wěn)定的好算法.講解：注意追趕法滿足條件（3.3.16）時，直接由（3.3.18）則可推出它表明及有界，因此即使不選主元，方法也是數值穩(wěn)定的，并且，故方程組（3.3.14）解時存在唯一的。3.4向量和矩陣范數3.4.1內積與向量范數為了研究方程組Ax=b解的誤差和迭代法收斂性，需對向量及矩陣的"大小"引進一種度量，就要定義范數，它是向量"長度"概念的直接推廣，通常用表示n維實向量空間，表示n維復向量空間.定義4.1設(或)，，，實數或復數，稱為向量x與y的數量積也稱內積.非負實數，稱為向量x的歐氏范數或2-范數.定理4.1設設(或)則內積有以下性質：(1)，當且僅當x=0時等號成立；(2),或；(3),或；(4)；(5)(3.4.1)稱為Cauch-Schwarz不等式.(6)，稱為三角不等式.定義4.2向量的某個實值函數N(x)，記作，若滿足下列條件：(1)‖x‖≥0,當且僅當x=0時等號成立(正定性)；(2)(齊次性)；(3)(三角不等式)；則稱是上的一個向量范數.對于，由內積性質可知它滿足定義4.2的三個條件，故它是一種向量范數.此外還有以下幾種常用的向量范數.(稱為∞-范數)(稱為1-范數)容易驗證及均滿足定義4.2的三個條件.更一般的還可定義但只有p=1,2,∞時的三種范數是常用的向量范數.例如給定,則可求出定理4.2設是上任一種向量范數，則N(x)是向量x的分量的連續(xù)函數.定理4.3設與是上任意兩種向量范數，則存在常數，使(3.4.2)不等式稱為向量范數等價性.以上兩定理證明可見［2］，［3］.講解：在向量得內積（x,y）的性質中，定理4.1的（5）為Cauch-Schwarz不等式（3.4.1）是經常使用的，下面給出證明，顯然當x＝0或y＝0時（3.4.1）成立，現設，考察若取則上式為于是兩邊開方則得（3.4.1）利用（3.4.1）直接可證三角不等式，從而可證明向量2一范數，滿足定義中的三個條件。及是三種最常用的范數。實際上可以給出很多不同的向量范數，只要證明它們滿足定義4.2中的三個條件，定理4.3表明任意的兩種向量范數及，它們都是等價的，對于的等價性在習題10中給出，可自己證明。3.4.2矩陣范數矩陣可看成n×n維向量，如果直接將向量的2-范數用于矩陣A，則可定義(3.4.3)稱為矩陣A的Frobenius范數，簡稱F-范數.它顯然滿足向量范數的三條性質，但由于矩陣還有乘法運算，因此矩陣范數的定義中應增加新條件.定義4.3如果的某個非負實函數N(A)，記作‖A‖，滿足條件：(1)‖A‖≥0，當且僅當A=0(零矩陣)時等號成立；(2)；(3)；(4)；則稱N(A)=‖A‖為上的一種矩陣范數.顯然滿足定義中的四個條件［(3)，(4)兩條均可由Cauchy-Schwarz不等式(3.4.1)證明，故是一種矩陣范數.除矩陣自身的運算外，在解方程中矩陣乘向量的運算即Ax，也是必不可少的.因此要求所引進的范數應滿足條件：(3.4.4)上式稱為相容性條件.為使引進的矩陣范數滿足條件(3.4.4)，我們給出以下定義.定義4.4設，當給定向量范數時可定義(3.4.5)稱為矩陣的算子范數或從屬范數.定理4.4設是上的一種向量范數，則由(3.4.5)定義的是一種矩陣范數，且滿足相容性條件(3.4.4).證明因是中有界閉集上的連續(xù)函數，故在D上有最大值，即使，而對，令

故所以從而當時(3.4.4)成立，而x=0時(3.4.4)顯然也成立.下面驗證由(3.4.5)定義的滿足矩陣定義的四個條件.條件(1)，(2)顯然成立.下面只需證(3)，(4).由(3.4.5)及(3.4.4)有故(3)成立，又因故有.證畢.定理4.5設則(A的行范數)(A的列范數)(A的2范數)這里ρ(·)為矩陣的譜半徑.證明這里只給出的證明，其余可見［2］.設，由其中.故對均有.下面證明,使得現設，其中顯然，且.證畢.從定理可以看出，計算及較容易，而計算2時因為要求的特征值，所以較為困難.但當A對稱時，有例3.9已知，求.解.定理4.6對任何為任一種從屬范數則(3.4.6)反之，對任意ε＞0，至少存在一種從屬范數，使(3.4.7)證明只證定理前一半，后半證明可見［3］.設為A的特征值，則，使，由(3.4.4)有及得即證畢.注意，當A對稱時，，表明(3.4.6)可取等號.定理4.7(矩陣范數等價性)對上的任兩種范數及，存在常數，使(3.4.8)證明略.例3.10證明(3.4.9)解因對稱半正定，，利用特征值性質(3.1.5)及和的定義，有另一方面于是,證畢.定理4.8設1則非奇異，且(3.4.10)證明用反證法.假定(I+B)奇異，則齊次方程有非零解，即使故而與‖B‖＜1的假設矛盾，故(I+B)非奇異.又，即，得，取范數，于是得(3.4.10).證畢.講解：矩陣范數可看作向量范數的擴充，它的定義中除了向量范數定義的三條性質，只增加了由矩陣乘法的得到的第4條即但為使矩陣與向量運算AX能相容，要求它們滿足條件（3.4.4）即這就是相容性條件，由此給出了矩陣的算子范數，即從屬范數為等式（3.4.5），它是由相應的向量范數定義的，定理4.4證明了（3.4.5）定義的從屬范數，滿足矩陣范數的定義，并針對三種常用的范數及得到了及，它們的表達式已有定理4.5給出。這就是必須記住的，并且當給定具體的矩陣A以后要能算出和.如例3.9.定理4.6給出了矩陣范數與譜半徑關系，是一個很重要的結果，必須記住，定理4.8給出陣非奇異的條件和它的逆矩陣估計式是一個經常使用的結論。3.5誤差分析與病態(tài)方程組3.5.1矩陣條件數與擾動方程組誤差界在解方程組Ax=b時，由于各種原因，A或b往往有誤差，從而使得解也產生誤差.例3.11方程組的準確解為，當A與b有微小變化時，如變?yōu)榉匠虅t準確解變?yōu)?它表明A,b的微小擾動引起方程解x的很大變化，這就是病態(tài)方程.定義5.1求解線性方程組Ax=b時，若A或b有微小擾動或時，解x的誤差很大，則稱此方程組為病態(tài)方程組，相應的系數矩陣A稱為病態(tài)矩陣.反之，若此時很小，則稱方程組為良態(tài)方程組，矩陣A為良態(tài)矩陣.注意方程組是否病態(tài)與用什么數值方法無關，它是由方程自身性質決定的.在例3.11中因為行列式，因此出現病態(tài).但有時A從表面上看性質很好，也可能是病態(tài)的.例3.12方程組Ax=b表示為它的準確解，A對稱正定且.表面看性質"較好"，但若對右端b作微小變化，如方程改為,則解變?yōu)門.這里b的相對誤差大約只有，但解的相對誤差卻很大，故A也是病態(tài)矩陣.那么如何判斷A是否病態(tài)?先給出如下定義.定義5.2設非奇異，‖·‖為矩陣的任一種從屬范數，則(3.5.1)稱為矩陣A的條件數.從定義看到矩陣條件數依賴于范數的選取，如范數為2-范數，則記為.同理有等等.條件數有以下性質：(1)；(2)；(3)U為正交矩陣，則(4)若與為A的按模最大與最小特征值，則.若A對稱，則下面給出擾動方程組解的誤差分析.先考察b有擾動，則擾動方程為由于Ax=b,故得，于是，再由Ax=b,有，即，故得(3.5.2)下面再研究方程Ax=b，當A有擾動時，其解的誤差分析.此時擾動方程為因Ax=b,故有(3.5.3)因存在，若假定則由定理4.8可知非奇異，并有由(3.5.3)可得即故有(3.5.4)綜合(3.5.2)與(3.5.4)的結果可得到如下定理.定理5.1設是方程組Ax=b的解，是擾動方程組的解.如果，則有誤差估計(3.5.5)此定理包含了(3.5.2)及(3.5.4)兩種特例.當則得(3.5.2)式；當時則得(3.5.4)式.實際使用時，由于誤差‖‖及‖‖很小，并且一般是可以控制的，故定理中的條件是可以成立的.從(3.5.5)看到，當A的條件數Cond(A)很大時，解的相對誤差也很大，故方程組為病態(tài).在例3.11中1，而于是條件數很大，故方程是嚴重病態(tài)的.例3.13Hibert矩陣是一個著名的病態(tài)矩陣，記作

它是一個對稱正定矩陣，當n≥3時它是病態(tài)矩陣.例如，故.另外還有.等等因此是嚴重的病態(tài)矩陣，且n越大越大.例3.1４在例3.12的方程組中可算出A的特征值，，，，故例中，，，實際相對誤差是而根據(3.5.2)的誤差估計為這與實際相差不大，即相對誤差放大了將近3000倍.故方程為病態(tài)方程組.定理5.2設方程組，若實際求得解為，則(3.5.6)證明記剩余，則，，，又故有.證畢.這是關于方程解的事后誤差估計，它表明如果方程組病態(tài)，即使剩余‖r‖很小，解的相對誤差仍可能很大.講解：矩陣條件數是判斷矩陣是否病態(tài)的依據，要求在n3時能夠計算，一般情況由于計算較困難，只要知道它的性質則可，利用條件數估計解方程組AX＝b的誤差，主要根據定理5.1的誤差估計式（3.5.5）。3.5.2病態(tài)方程組的解法如果A的條件數Cond(A)>>1，則Ax=b為病態(tài)方程，但計算Cond(A)時需要求，計算量很大，相當于解方程組，在實際中?？赏ㄟ^求解過程直觀地判斷方程組的病態(tài)性質，如果解方程時出現下述情況之一，則可能是"病態(tài)"方程組.(1)在列主元消去法中出現小主元；(2)在計算過程中行或列幾乎線性相關或三角分解中對角元出現近似零的元素；(3)矩陣A的元素數量級相差很大且無規(guī)律；(4)剩余很小，而解很大，又達不到精度要求.對病態(tài)方程組求解可采用以下措施：(1)采用高精度運算，減輕病態(tài)影響，例如用雙倍字長運算.(2)用預處理方法改善A的條件數，即選擇非奇矩陣，使與Ax=b等價，而的條件數比A改善，則求的解，即為原方程的解.計算時可選擇P，Q為對角矩陣或三角矩陣.(3)平衡方法，當A中元素的數量級相差很大，可采用行均衡或列均衡的方法改善A的條件數.設非奇異，計算，令，于是求Ax=b等價于求，或.這時的條件數可得到改善，這就是行均衡法.例3.15給定方程組Ax=b為A的條件數，若用行均衡法可取，則平衡后的方程為，用三位有效數字的列主元消去法求解得.【本章小結】1.本章主要討論解方程組AX＝b的Gauss消去法和直解三角分解法，首先要理解消去法原理并能用列主元消去法求解方程組。當矩陣A的順序主子式，則可通過順序消去得到方程組的解，通過n-1步消去相當于用n-1次Gauss變換使方程轉化為,其中,即為上三角陣，于是,其中L為單位下三角陣，為上三角陣，這就是A的LU分解具體計算時也可直接利用矩陣乘法求得L與U的元素。從而將方程AX＝b的求解轉化為解兩個三角方程及，要求在不記公式的前提下對n=3的方程組能直接求出L及U和解x,要注意A能進行LU分解的條件。例3.16非奇異矩陣不一定都有LU分解。解設非奇異，要說明A不一定能做LU分解，只需舉出一個例子不能分解即可，通常應盡量找簡單例子?，F考慮矩陣顯然A為非奇異，若A有LU分解，則于是，而顯然不能同時成立，這矛盾說明A不能做LU分解，所有只假定A非奇異不能保證A能作LU分解，充分條件是A的所有順序主子式2.特殊方程組的三角分解法。當A為對稱正定矩陣，使用Cholesky分解，得，其中L為下三角陣，再用平方根法求得方程組的解x，分解仍用矩陣乘法規(guī)則求得L的元素,然后解兩個三角方程組Ly=b及，計算公式（3.3.12），（3.3.13），為避免開方可用改進的平方根法。當A為三對角矩陣時通常用追趕法求解，它也是一種三角分解，只要A的元素滿足條件（3.3.16），則追趕法（見公式（3.3.18）－（3.3.20））計算是穩(wěn)定的，得到的解是可靠的，且整個計算過程只需（5n-4）次乘除和3(n-1)次加減法運算。3．向量和矩陣的范數是本章另一重點，要熟記向量范數定義的3條性質和矩陣范數的4條性質，并能根據定義檢驗每種具體的范數及是否符合定義要求。對常用的向量范數和矩陣范數及要熟記并能正確算出結果。為使同學更好掌握范數定義，再給出以下兩個例題。例3.17設為非奇異陣，為上的向量范數，定義，證明是上的一種向量范數。證明只要證滿足范數定義3.1中的3個條件。（1）因P非奇異，故對，故時x=0,且當，于是例當且僅當成立。（2）對（3）故是上的一種向量范數。例3.18設，證明（1）是一種矩陣范數（2）不是A的矩陣范數證明（1）要證明是一種矩陣范數只要證明它滿足矩陣范數定義的4個條件。（1），且成立。（2）（3）（4）由此可知是A的一種矩陣范數。（2）由于不滿足條件例如于是顯然不成立，故不是矩陣范數5.矩陣的條件數是衡量矩陣A病態(tài)程度的條件，若，就稱A為病態(tài)矩陣，通常為病態(tài)，P越大，病態(tài)越嚴重，當A為對稱矩陣分別為A的絕對最大與最小特征值，利用矩陣條件數還可估計解方程組的計算誤差，即當A和b有誤差及時解的誤差，由（3.5.5）式可得到的估計。例3.19已知Hilbert矩陣解方程組時，及b有微小誤差（取3位有效數字），估計解的誤差解方程組在及b有微小變化時為簡記為，它的精確度為，而且的精確解為于是而.這表明及b的相對誤差不超過0.3％，而引起解的相對誤差超過50％下面利用定理3.6給出的誤差估計式（3.2.1）可得這個估計結果是比實際誤差大是合理的。第三章解線性方程組的直接法3.1引言與矩陣一些基礎知識3.1.1引言線性方程組求解是科學計算中最常遇到的問題，如在應力分析、電路分析、分子結構、測量學中都會遇到解線性方程組問題.在很多廣泛應用的數學問題的數值方法中，如三次樣條、最小二乘法、微分方程邊值問題的差分法與有限元法也都涉及到求解線性方程組.本章討論n個變量n個線性方程的方程組求解，其表達式為通常用向量矩陣表示，則上述方程可寫成(3.1.1)其中并記做，分別表示A為n×n階實矩陣，x,b為n維實向量.根據線性代數知識可知A非奇異，即detA≠0，方程組(3.1.1)有唯一解，并可用Cramer法則將解用公式表示出來，但由于計算量太大，因此不能用于實際求解.本章要討論的直接方法是將方程組(3.1.1)轉化為三角方程組，再通過回代求三角方程組的解.理論上，直接法可在有限步內求得方程的精確解，但由于數值運算有舍入誤差，因此實際在計算機上求得的數值解仍是近似解，仍要對它進行誤差分析.解線性方程組的另一類方法是迭代法，將在下一章討論.下面給出本章和下章需要的一些矩陣基礎知識.3.1.2矩陣特征值與譜半徑定義1.1設，若存在一個數(實數或復數)和非零向量，使(3.1.2)則稱為A的特征值，x為A對應的特征向量，A的全體特征值稱為A的譜，記作，即(3.1.3)稱為A的譜半徑.由式(3.1.2)知，可使齊次方程有非零解，故系數行列式det(I-A)=0，即(3.1.4)稱為特征多項式，方程(3.1.4)稱為特征方程，在復數域中有n個根，故由行列式(3.1.4)展開可知：于是，矩陣的n個特征值是它的特征方程(3.1.4)的n個根，A的跡trA有(3.1.5)(3.1.6)此外，A的特征值和特征向量x還有如下性質：(1)與A有相同的特征值及相同的特征向量x.(2)若A非奇異，則的特征值為，特征向量為x.(3)相似矩陣有相同特征多項式.例3.1求的特征值及譜半徑.解A的特征方程為故A的特征值為.譜半徑為.講解：根據特征值定義（3.1.2）式知它等價于齊次方程有非零解，它的充分必要條件是系數行列式為零即，將行列式展開，由（3.1.4）看到它是的n次多項式，記作稱為特征多項式，將行列式對角元素相乘，即它決定了中及的系數，因為行列式的展開式中其余各項的次數均不超過，故，利用，有n個根（在復數域中，復根成對出現），故，可知，于是有，稱為矩陣A的跡。另外行列式中令，則得，從而得到（3.1.6）3.1.3對稱正定矩陣定義1.2設，如果，即，則稱A為對稱矩陣，若還滿足對于，則稱A為對稱正定矩陣，如果對有，則稱A為半正定矩陣.當A為對稱時，A的特征值皆為實數，且有n個線性無關的特征向量.對稱正定矩陣還有以下重要性質：(1)對稱正定，則〖WTHX〗A非奇異，且也對稱正定；(2)A對稱正定的充要條件是，A的所有特征值；(3)A對稱正定，則A的對角元素；(4)A對稱正定的充要條件是A的所有順序主子式以上性質可直接由定義證明，證明略.講解：對稱正定矩陣性質都可直接由定義證明為了更好理解，下面就性質（1）給出證明先證A非奇異，用反證法，假定A奇異，則，使，故與A正定的假定矛盾，故A非奇異，即存在。由于是，即對稱，再證正定。對，令，于是，由A正定得，故也正定。3.1.4正交矩陣與初等矩陣定義1.3若且，則稱A為正交矩陣.由定義知，且與均為正交陣，且有.定義1.4設.則為單位矩陣，稱為(實)初等矩陣.顯然，例如，則設，則若σ已知，選，使則當時，令(3.1.7)則有(3.1.8)此外，還有(3.1.9)下面給出兩個常用的初等矩陣.例3.2初等排列矩陣.令則矩陣也稱初等置換矩陣，它由單位矩陣I交換i行與j行得到，它有以下性質：(1)，故為正交矩陣.(2).(3)是將A的i,j行互換，是將A的i,j列互換.例3.3初等下三角矩陣.設,則記稱為指標為j的初等下三角矩陣，即(3.1.10)矩陣有以下性質：(1).(2).(3)，為單位下三角矩陣.初等下三角矩陣也稱為Gauss變換矩陣.講解：例3.2中給出的初等排列陣，其作用是實現矩陣A的i,j行互換及列互換，即表示A的i、j兩行互換，而，表示A的i,j兩列互換。例3.3初等下三角陣，由（3.1.10）所表示的矩陣，在下節(jié)Gauss消去法中有應用，其逆矩陣，表示為3.2Gauss消去法3.2.1順序消去法Gauss消去法就是將方程組(3.1.1)通過(n-1)步消元，將(3.1.1)轉化為上三角方程組(3.2.1)再回代求此方程組的解.下面記增廣矩陣，即第1步設，計算l，記為，若用乘第一行加到第i行，可消去,用Gauss變換矩陣表示令其中一般地，假定已完成了(k-1)步消元，即已將轉化為以下形式：第k步，假定，計算(3.2.2)記，，則其中(3.2.3).當k=1,2，…,n-1則可得到，即方程組(3.2.1).直接回代解(3.2.1)得，(3.2.4)并且有，由以上順序消去過程可得如下定理.定理2.1設非奇異，則通過兩行互換總可使，k=1,2，…,n-1.可將方程組(3.1.1)轉化為(3.2.1)并求得方程組(3.1.1)的解為(3.2.4)，且有.如果不做行交換，則使的條件如下.定理2.2非奇異，且各階順序主子式，則，k=1,2，…,n-1.證明用歸納法，當，故.現假設(k-1)成立，即，對i=1，2，…,k-1已推出，故Gauss消去法能進行(k-1)步消元，A已約化為，即故對k=1,2,…,n均成立，證畢.在整個消去法消元過程中，k從1到(n-1)共需乘除法運算次數為加減法次數為回代過程中由公式(3.2.4)可知乘除法次數為，加減法次數為，于是Gauss消去法的乘除法總次數為，加減法次數為例3.4用Gauss消去法解方程組并求detA.解消元得再由(3.2.4)回代，得解講解：Gauss消去法是將方程組AX＝b,通過消元轉化為上三角方程組（3，2，1）求解，消元第一步做完后有用矩陣表示第K－1步完成后得到當，可做K步，得到得到，對應的方程組就是（3.2.1），利用公式（3.2.4）就可求得解。定理2.2給出了進行順序消去法的條件，即A的所有順序生子式，而方程（3.1.1）解存在唯一的條件是3.2.2消去法與矩陣三角分解上述Gauss消去法的消元