西安交通大學計算方法B完整版

緒論1.1數(shù)值計算現(xiàn)代科學的發(fā)展，已導致科學與技術的研究從定性前進到定量，尤其是現(xiàn)代數(shù)字計算機的出現(xiàn)及迅速發(fā)展，為復雜數(shù)學問題的定量研究與解決，提供了強有力的基礎。通常我們面對的理論與技術問題，絕大多數(shù)都可以從其物理模型中抽象出數(shù)學模型，因此，求解這些數(shù)學模型已成為我們面臨的重要任務。本課程的任務：尋求解決各種數(shù)學問題的數(shù)值方法——如何將高等數(shù)學的問題回歸到初等數(shù)學（算術）的方法求解——了解計算的基礎方法，基本結構（否則只須知道數(shù)值軟件）——并研究其性質。立足點：面向數(shù)學——解決數(shù)學問題面向計算機——利用計算機作為工具充分發(fā)揮計算機的功能，設計算法，解決數(shù)學問題例如：迭代法、并行算法問題的類型1、離散問題：例如，求解線性方程組——從離散數(shù)據(jù)：矩陣A和向量b，求解離散數(shù)據(jù)x；2、連續(xù)問題的離散化處理：例如，數(shù)值積分、數(shù)值微分、微分方程數(shù)值解；3、離散問題的連續(xù)化處理：例如，數(shù)據(jù)近似，統(tǒng)計分析計算；1.2數(shù)值方法的分析在本章中我們不具體討論算法，首先討論算法分析的基礎——誤差。一般來講，誤差主要有兩類、三種（對科學計算）：1）公式誤差——“截斷誤差”，數(shù)學計算，算法形成——主觀（人為）：數(shù)學問題-數(shù)值方法的轉換，用離散公式近似連續(xù)的數(shù)學函數(shù)進行計算時，一般都會發(fā)生誤差，通常稱之為“截斷誤差”；——以后討論2）舍入誤差及輸出入誤差——計算機，算法執(zhí)行——客觀（機器）：由于計算機的存儲器、運算器的字長有限，在運算和存儲中必然會發(fā)生最末若干位數(shù)字的舍入，形成舍入誤差；在人機數(shù)據(jù)交換過程中，十進制數(shù)和二進制數(shù)的轉換也會導致誤差發(fā)生，這就是輸入誤差。這兩種誤差主要是由于計算機的字長有限，采用浮點數(shù)系所致。首先介紹浮點數(shù)系一、計算機上的運算——浮點運算面向計算機設計的算法，則先要討論在計算機上數(shù)的表示。科學記數(shù)法——浮點數(shù)：約定尾數(shù)中小數(shù)點之前的數(shù)全為零，小數(shù)點后第一個數(shù)不能為零。目前，一般計算機都采用浮點數(shù)系，一個存儲單元分成首數(shù)和尾數(shù)：××┅┅┅┅×××┅┅┅┅┅┅┅┅××首數(shù)尾數(shù)(位)其中首數(shù)存放數(shù)的指數(shù)（或“階”）部分，尾數(shù)存放有效數(shù)字。對于進制，尾數(shù)字長為t位的浮點數(shù)系中的（浮點）數(shù)，可以用以下形式表示：此處，指數(shù)（稱為階）限制在范圍內。以下記實數(shù)系中的實數(shù)為，它在浮點數(shù)系中對應的浮點數(shù)記為——進制，尾數(shù)位數(shù)，階的范圍。幾乎所有近代計算機都采用“二進制”（即）：位、字節(jié)和字分別是指位數(shù)不同的二進制數(shù)。例如十進制轉換二進制100000001200000010400000100800001000900001001100000101027位是一個二進制數(shù)（即0或1）；字節(jié)是8個二進制數(shù)字；上表的最后一列是字節(jié)。單精度浮點數(shù)（singleprecision）按32位存儲，雙精度浮點數(shù)（doubleprecision）按64位存儲。精度用于指明每個浮點數(shù)保留多少位以及尾數(shù)和階數(shù)各分配多少位。單精度浮點數(shù)的尾數(shù)為23位、階數(shù)為8位；雙精度浮點數(shù)的尾數(shù)為53位（包含符號位）、階數(shù)為11位（包含符號位）。雙精度浮點數(shù)的等價二進制數(shù)如下所示：浮點數(shù)的特點：實數(shù)轉換到浮點數(shù)——浮點化，〈缺點：〉總會產(chǎn)生誤差（除極個別的情況：）按四舍五入，絕對誤差：（舉例），〈優(yōu)點：〉浮點化產(chǎn)生的相對誤差有界（與數(shù)字本身的數(shù)量級無關）注：設實數(shù)，則按進制可表達為：按四舍五入的原則，當它進入浮點數(shù)系時，若，則若，則對第一種情況：對第二種情況：就是說總有：另一方面，由浮點數(shù)要求的，有，將此兩者相除，便得每一個浮點數(shù)系的數(shù)字有限：浮點數(shù)系中的運算非自封閉,（因為數(shù)字有限等）例：在中，，運算和,的結果顯然已不在此浮點數(shù)系內，而或也不在此浮點數(shù)系內，需結果才在此浮點數(shù)系內。浮點運算應注意：避免產(chǎn)生大結果的運算，尤其是避免小數(shù)作為除數(shù)參加運算；避免“大”“小”數(shù)相加減；避免相近數(shù)相減，防止大量有效數(shù)字損失；4）盡可能簡化運算步驟，減少運算次數(shù)。原因：記，由，可得：（“?！北硎救我庖环N四則運算）此處是由機器字長（實質上是尾數(shù)字長的大小）確定的常數(shù)（它反映了實際運算的精度）。顯然，若要求運算的舍入誤差小，應使運算結果（如：）較小。尤其是小分母運算：，小大誤差。其次，當浮點數(shù)系中兩個數(shù)量級相差較大的數(shù)相加（或減），注意到由于浮點數(shù)系中數(shù)字字長的有限性，可能導致“大數(shù)吃小數(shù)”。例如，中，則似乎沒有參加運算。第三，同樣，由于浮點數(shù)系中數(shù)字字長的有限性，當兩個相近數(shù)相減時：例如，在中，，兩數(shù)相減：，計算結果僅剩2位有效數(shù)字，而原來參加運算的數(shù)字有8位有效數(shù)字，這將嚴重影響最終計算結果的精度。二、算法分析作為一個可用的算法，必須考慮其效率和可靠性，定義：計算機完成一個乘法和一個加法，稱為一個浮點運算（記為flop）；注：由于計算機在運算時，加（減）法所耗時間遠少于乘（除）法，所以通常只須計算乘法的次數(shù)，因此也有“一個算法需要多少個‘乘法’”這一提法。1、計算效率——可計算性（計算復雜性——空間、時間）例：解線性方程組的Grammar方法：，其中是方程組系數(shù)矩陣對應的行列式，而則是以右端向量替代的第列所得矩陣對應的行列式。由線性代數(shù)知識可知，若，則，其中是由{}變換到{}所需的置換次數(shù)?？梢娒坑嬎阋粋€行列式，需要個浮點運算；因此，按Grammar方法解方程組約需個浮點運算。當時 ，用一個運算速度為的計算機進行求解，約需年（日前報道我國計算機已達到秒，這仍需近10年）。而n=20的方程組應該說是一個小型的方程組。因此Grammar方法是一個不能接受的算法，它缺乏可計算性。第二章將介紹的Gauss消去法和迭代法就有較高的效率，具有很好的可計算性。2、計算可靠性作為算法，除了考慮其效率外，必須重視可靠性，它包括兩方面：問題的性態(tài)和方法的穩(wěn)定性問題的性態(tài)所計算的問題當原始數(shù)據(jù)發(fā)生小擾動時，問題的解一般也發(fā)生擾動。問題的性態(tài)——問題的解對原始數(shù)據(jù)發(fā)生變化的敏感性。原始數(shù)據(jù)小擾動問題解例：線性方程組：的解是：若將方程組的系數(shù)改寫成具有2位有效數(shù)字的小數(shù)：的解則變成：；這是一個典型的病態(tài)方程組。一般：由原始數(shù)據(jù)計算結果，擾動后的數(shù)據(jù)計算結果，若對問題存在常數(shù)m，滿足關系式：或則稱（相對誤差之比的上界）m為該問題的條件數(shù)，記作；由微積分中值定理知識容易計算出，當時，。稍后我們在第二章將對線性方程組的性態(tài)作進一步的分析。算法的數(shù)值穩(wěn)定性：例：計算；解：由微積分知識，可得計算公式，①，②，我們將準確值與計算結果列表如下：方法準確值.6321.3679.2642.2073.1709.1455.1268.1124.1010①.6321.3679.2642.2074.1704.1480.1120.2160-.7280②.6320.3680.2643.2073.1709.1455.1268.1124.1010由上表可見，方法①中，原始步的誤差，隨著計算步數(shù)的增加被嚴重地放大，特別是竟變成負數(shù)（注意：被積函數(shù)是非負函數(shù)），而方法②則相反；這是因為方法①中，若前步有誤差：，則，說明的誤差，經(jīng)一步計算后被擴大了倍，隨著的增大，誤差將被大大地擴大；而通過同樣的分析可知：方法②中的誤差則被縮小倍。算法的數(shù)值穩(wěn)定性：算法對初始誤差導致的最終誤差的可控性，如果最終誤差被有效地控制，則稱算法是穩(wěn)定的，否則就是不穩(wěn)定的。第二章線性方程組求解線性方程組：其中2.1消去法2.1.1消去法設計方法原則：面向計算機（事先未知元素，編制程序），例：基本思想：降維——N維問題轉化為N-1維問題——逐次降維，依次進行消去過程——對方程組（2.1）由上而下逐步消去對角元以下的，使之轉化為如下等價形式，達到目標：從而，可進入回代過程，再由下而上，逐步解得：這兒的——主元對問題（2.1）設，目標：將第2～n方程的的系數(shù)轉化為0；方法：“第個方程”-“第1個方程”（，得到現(xiàn)在只須關心由第2～n方程形成的n-1維方程組，以后可仿此進行。消去：第步：設，以第行為基準，消去以下各行中列以下的，令施行：第行—第行新的第行，元素變化：（），，經(jīng)過步消去（注意：以下無元可消），得到式。〈注意：每計算1個僅需1個浮點運算〉回代：第一步，第二步，第步運算量：消元：n元方程組：第1步消元：對第行，共n-1行；每1行：計算，1個乘除法（或“浮點運算”），計算新的共個乘除法（或“浮點運算”），第1次元共個乘除法，因此，消元的運算量；回代：第1步，求需要1個乘除法（或“浮點運算”），即：第2步求用2個乘除法（或“浮點運算”），一般，第步求用個浮點運算，因此，回代的運算量；消去法的總運算量：。例2-1：解線性方程組解：利用增廣矩陣（因為線性方程組的解僅與系數(shù)與右端常數(shù)項相關）例：；解；解：；解；解；解；2.1.3（列）主元消去法算法中，若第步：或則按照原來的簡單消去法算法可能無法執(zhí)行，也可能出現(xiàn)大誤差：例：在浮點數(shù)系中計算；方程組準確解：解：按消去法解：誤差大，原因：若有誤差則，則演變?yōu)?；這說明前步各元素的誤差均被放大倍?？朔椒?，將按絕對值最大的元素交換到主元位置，使，使前步的誤差不再被放大。消元過程中，第步消元以第行為基準，消去其后的個方程的（系數(shù)矩陣第列以下的元素），消去法要求主元。為避免出現(xiàn)作為主元，并使前步的誤差不被放大，應使，為此應使：，通常采用按列選主元的列主元消去法：若，便將第行與第行交換，使與交換位置，使新的第行執(zhí)行在原始消去法中的角色，保證將作為除數(shù)的主元，從而，重復前述的消去過程。列主元消去法的效果：算法穩(wěn)定，即計算誤差能被有效控制；當矩陣的行列式時，算法總可以執(zhí)行完成；注：若矩陣是對稱正定或嚴格對角占優(yōu)，則不選主元，消去法也是穩(wěn)定的；矩陣嚴格對角占優(yōu)的定義：對角元的絕對值大于該行其他元的絕對值之和，即；問題：為什么系數(shù)矩陣嚴格對角占優(yōu)，則不選主元的消去法也是穩(wěn)定的？為保證消去法是穩(wěn)定的，算法應如何進行？注意：第一步消元，由于占優(yōu)：，它的效果與主元消去法的一樣，誤差不會被放大。但因此算法也應適當改變，應先對第一行計算此值，然后從第2列起逐列從上到下計算。且第一步消元后生成的右下方階矩陣仍是嚴格對角占優(yōu)，以第二列為例：又即新的第二行的對角元絕對占優(yōu)，其他也可同樣證明。例2-2：列主元消去法求解例2-1同樣得到原方程組的解；2.2矩陣分解2.2.1Gauss消去法的矩陣意義——矩陣的三角分解若將消去法解方程過程中產(chǎn)生的作為一個單位下三角矩陣——其對角元為1，對角線上的元素均為0——的對應元素；將消去法消元過程最后得到的上三角矩陣——對角線以下元素均為0——記作或（僅考慮方程的系數(shù)矩陣部分）；如例2.1，再將與或相乘：或顯然相乘得到的正是原始所求解的方程的增廣矩陣，而相乘得到的正是原始所求解的方程的系數(shù)矩陣。反過來，一個矩陣也可以通過求解的過程獲得這樣的“分解”，其中為單位下三角矩陣，為上三角矩陣。這樣將一個矩陣分解成一個下三角矩陣和一個上三角矩陣的乘積形式，稱為矩陣的三角（Doolittle）分解。消去法的矩陣意義：以例2-1說明與以下矩陣乘法是一樣的：可見，一般的第一步消元是：若記第步消元后形成的矩陣為，《特別：》則第步消元是將以下初等矩陣左乘矩陣形成因此，Gauss消去過程從矩陣運算的角度來看，是其中為上三角矩陣，為向量：2.2.2矩陣分解注意到初等矩陣具有性質：及因此，我們有根據(jù)矩陣乘積的性質，有這就是基本的矩陣三角分解——Doolittle分解——將矩陣分解為單位下三角矩陣與上三角矩陣的乘積。從矩陣乘法與行列式的關系可知，若矩陣A三角分解得到A=LU，則有：detA=detL*detU，由于下三角矩陣或上三角矩陣的行列式是全部對角元的乘積，因此可利用三角分解求矩陣對應的行列式的值。例如：上述例2.1方程組系數(shù)矩陣對應的行列式的值是-1，下例2.3對稱正定矩陣對應的行列式的值為144。當系數(shù)矩陣為的方程組可以順利求解（不必選主元）時，解的過程顯然是唯一的，因此它的Doolittle分解必然也是唯一的，從而可以通過待定系數(shù)的方法獲得該矩陣的Doolittle分解（通常稱為“直接分解”或“緊湊格式”）。2.2.3其他三角分解除了上述的單位下三角矩陣與上三角矩陣的乘積形式以外，還有其他類型的分解，例如下三角矩陣和單位上三角矩陣的乘積，單位下三角矩陣與對角矩陣、單位上三角矩陣的乘積。對于對稱矩陣，可以分解成矩陣分解的形式，特別是對稱正定矩陣，可以分解成形式（稱為Cholesky分解），其中為下三角矩陣《由Doolittle分解的唯一性可知這些形式的分解也是唯一的》。這些不同的分解都可以通過矩陣乘積的方法取得。下面例2.3以對稱正定矩陣為例，說明通過矩陣乘積的方法取得矩陣分解的不同形式。當然，當矩陣的Doolittle分解存在唯一時，這些不同的分解分別時唯一的，因此可以通過待定系數(shù)的方法取得，也即通過直接分解的方法取得這些分解。例2-3：由此可知：進一步可以考察矩陣左上方各階順序主子式與三角分解所得矩陣的左上方的各階順序主子式的關系：若記矩陣A的各階順序主子矩陣為，同樣的記號也適用于矩陣，則有，從而矩陣的各階順序主子式的值等于的相應的順序主子式的值：，（因為）。以例2-3矩陣分解為例，容易得到：由此，也很容易看到，一個對稱矩陣通過消去過程得到的分解（其中為單位下三角，為上三角矩陣），當?shù)膶窃繛檎龜?shù)時，該對稱矩陣必為對稱正定矩陣。由消去的過程可知各次主元是（矩陣的對角元），可知當矩陣的各階順序主子式均非零時，（原始的）消去法可以順利完成，這是因為當各階順序主子式均非零時，均非零，即消去法可以順利完成。進一步，當矩陣非奇時，列主元消去法必可順利完成：因為當矩陣非奇時，的第一列必不全為零，故通過選主元，可進行第一步消元，即算法可執(zhí)行，得到，且其下方全為零，因為所以的代數(shù)余子式也非零，（），即矩陣非奇，因此下一步列主元消去可進行，由此，可完成全部消元過程。2.定理2.5若分解),則(下)帶寬,(上)帶寬.證明:對二和三階矩陣顯然.(確定),對矩陣的階作歸納證明:設對階矩陣結論成立.令,可驗證(介紹分塊運算):由歸納假設,,因此最后的矩陣乘法：前者是初等矩陣左乘〈實際上是Gauss變換矩陣相乘〉，后者按分塊運算容易得到。特殊情況,——三對角矩陣：，由前述的方法，很容易將它分解成兩個特殊的下、上三角矩陣的乘積：，其中〈因為未講矩陣的直接分解，此處可由確定分解形式、待定系數(shù)方式取得〉：從而，在解方程組，其中時，可以將該方程組轉化為求解兩個簡單方程組：通常被稱為“追趕法”：。這只是Gauss消去法的一個具體應用，在計算機上的應用可以節(jié)約存儲空間，減少運算量。若手工計算，實際只需應用Gauss消去法即可。例2.3線性方程組解的可靠性——向量與矩陣范數(shù)，誤差的代數(shù)表征3.1向量與矩陣范數(shù)向量范數(shù)由二維或三維向量的長度概念推廣而來——工具。1、向量范數(shù)向量，與之相應的一個非負實數(shù)，記作，如果它滿足條件：非負性，正齊性，三角不等式；常用的范數(shù)1-范數(shù)，2-范數(shù)，-范數(shù)，注：一般若不指某特定的范數(shù)，則范數(shù)符號不作下標，記為；2、矩陣范數(shù)矩陣，與之相應的一個非負實數(shù)，記作，如果它滿足條件：非負性，正齊性，三角不等式，，因為矩陣與向量相乘仍是向量，因此：特別要求一種矩陣范數(shù)與一種向量范數(shù)：5）——矩陣與范數(shù)的相容性；與前述三種向量范數(shù)分別相容的常用的三種矩陣范數(shù)：1-范數(shù)，（最大列和）2-范數(shù)，-范數(shù)，（最大行和）；注：作為矩陣的特例——向量，這些范數(shù)定義無矛盾。例：第2章Ex-14（79頁）-范數(shù)，-范數(shù)，-矩陣范數(shù)，其中-非奇矩陣3、范數(shù)的等價性：4、矩陣譜半徑：；有(對任何一種范數(shù)),2.3.2殘向量與誤差誤差的代數(shù)表征（矩陣的條件數(shù)）：若記方程組(2.1)的準確解，近似解；則有近似解的誤差：，近似解的殘向量：。小小？例：比較：方程組與，從前者到后者僅是右端產(chǎn)生誤差，而對應的解則由變?yōu)?，即也產(chǎn)生誤差；它們之間有關系：；注意以上公式：由，以及得到。此處，從本質上反映了方程組右端的相對誤差導致解的相對誤差的數(shù)值關系，反映了方程組原始數(shù)據(jù)發(fā)生擾動時，方程組解發(fā)生變化的大小。比較前已提到的“問題的性態(tài)”，數(shù)反映了方程組的性態(tài)。因此稱此數(shù)為方程組或矩陣的“條件數(shù)”，記作；由于總有（實際上，除了外，幾乎總有），而從推導可知，（此處“~”表示“相當于”），因此一般總有；上例中：對于更一般的矩陣和右端向量均發(fā)生擾動和的情況，有證明：存在，且反證：若奇異，即，則有非解又矛盾，所以非奇，存在，由（至少對常用的三種范數(shù)）：由此得.若:2.4線性方程組的迭代解法迭代法：將方程組（2.1）轉化為等價的形式從而，將向量代入(2.4)的右邊，可計算得到一個新的值：如此反復地進行，便得到向量序列；問題I）如何將方程組（2.1）的形式轉化為(2.3)？II）給定初始向量，迭代產(chǎn)生的向量序列是否收斂？III）向量序列的收斂性與初始向量的選取是否相關？IV）如果收斂，如何估計誤差？2.4.1Jacobi迭代與Gauss-Seidel迭代首先我們回答問題I）:由方程組（2.1）：，使等式左端僅保留向量，其他一概放到右端，即：將方程組的第個方程（設，）改成：，便可將原方程組改寫成如下等價形式：Jacobi迭代：將代入上式右端，便可（按順序逐行）進行計算得到，這便是迭代：Gauss-Seidel迭代：按通常的串行計算方式，迭代（2.5）中先計算第一式得到,此數(shù)完全可以參與第二式的右端的計算,依次類推，便得到：這就是迭代。迭代法的矩陣表示將方程組（2.1）的系數(shù)矩陣A分裂成三部分：，其中原始方程組形成，即左側僅有若，分別對第方程除以，并記左側上標為k+1，右側上標為k，則有Jacobi迭代：若由“最新信息優(yōu)先”，即將已生成的立即用于計算，便是Gauss-Seidel迭代：矩陣分裂：Jacobi迭代：Gauss-Seidel迭代：顯然，不同的迭代方法是對矩陣A做不同的分裂得到的：Jacobi迭代：Gauss-Seidel迭代：逐次超松弛（SOR:SuccesiveOver-relaxation）：由，改G-S迭代：

將由的改變量，作松弛，取松弛因子，有或計算式，由：矩陣分裂：逐次超松弛（SOR）收斂條件：必要條件：A嚴格對角占優(yōu)：逐次超松弛（SOR）收斂A對稱正定：逐次超松弛（SOR）收斂2.4.3收斂性以下我們回答問題II）和III）：記方程組的解為，若當時向量序列收斂于方程的解，即，有等價關系（注意到范數(shù)的等價性）：由于滿足關系式，將它與一般迭代：，兩者相減，可得，遍取向量范數(shù)，并由矩陣范數(shù)與向量范數(shù)的相容性，可得：從而，由此可見，當時，無論如何取，總有，即：；即定理2.6：迭代取任意初值生成的向量序列當時收斂于方程的解的充分條件是.具體化——考察對原始問題（2.1）進行迭代或迭代時，迭代收斂對矩陣的要求。由式可知，迭代的迭代矩陣為，迭代的迭代矩陣為；由于的第行是：（）；因此，顯而易見當為嚴格對角占優(yōu)時該行各元素的絕對值之和小于1，所以：；結論是：推論2.7：若方程組（2.1）的系數(shù)矩陣嚴格對角占優(yōu),則任取初值的迭代收斂.其他結論：定理2.8：若方程組（2.1）的系數(shù)矩陣嚴格對角占優(yōu),則任取初值的迭代收斂.證：記嚴格對角占優(yōu)，由的有限性，記由及相減即設則所以由，得證完定理2.9：若方程組（2.1）的系數(shù)矩陣對稱正定,則任取初值的迭代收斂；當正定時，迭代收斂，否則就不收斂。最后，有：定理2.10：迭代收斂的充分必要條件是矩陣的譜半徑.例：關于充分性：Jocabi：令則因此，總有，但并不滿足定理的充分條件。例：又，等價于解：；結論：Jacobi迭代收斂，Gauss-Seidel迭代不收斂。例：結論：Jacobi迭代不收斂，Gauss-Seidel迭代收斂。例：正定，不正定，Seidel收斂，Jacobi不收斂。例：例：證明：時Seidel迭代收斂，僅當時Jacobi迭代收斂。證：i.時正定：，綜上，時正定，所以Gauss-Seidel迭代收斂；ii.所以，（當且）僅當時Jacobi迭代收斂?！凑ǎ赫?；綜合正定條件，得結論。但這是在正定的前提下的結論，如果不正定，條件是否仍如此？例：，以表示解的Jacobi、Gauss-Seidel迭代收斂的充分必要條件；I：Jacobi迭代：Jacobi迭代收斂；II：Gauss-Seidel迭代：等價于解：Gauss-Seidel迭代收斂。例用迭代格式求解方程組，試問實數(shù)取何值可使迭代收斂？解：迭代格式為,故迭代矩陣為又，該迭代格式收斂故時，可使迭代收斂。2.4.4迭代終止的判據(jù)定理2.11:迭代,若,則任意取初值生成的向量序列當時收斂于方程的解,且有誤差估計:或；證：利用及令，便得結論。注1：前者稱為“先驗估計”，后者稱為“事后估計”；迭代法通常要求計算獲得的解滿足給定的誤差界：：先驗估計：對要求的誤差界，由估計式可計算得，從而，可將由此所得的作為迭代步數(shù)的最大控制數(shù)，取；事后估計：對要求的誤差界，由估計式可知，在迭代計算過程中，應驗證不等式是否滿足，如果滿足，迭代就可終止，取。在實際計算中，通常將上述兩種終止判據(jù)同時使用。注2：對于系數(shù)矩陣嚴格對角占優(yōu)的迭代，可用定理2.8定義的作為收斂因子（即?。?，當然此時應取-范數(shù)；注3：若已肯定迭代收斂，但收斂因子q難以獲得，可根據(jù)：對適當大的確定q的估計值。HilbertMatrixnn374859610第三章數(shù)據(jù)近似已知函數(shù)關系的數(shù)據(jù)點：，求一個適當?shù)暮瘮?shù)，它是已知函數(shù)族——稱為基函數(shù)——的線性組合，即：尋求系數(shù)，使，與按某種標準相近似；通常按下述標準之一，使之取得極小：若取向量形式：,則上述三數(shù)分別為：；3.1多項式插值一般，若有個數(shù)據(jù)點，上述近似標準要求即：，則稱近似函數(shù)為滿足插值條件(3.2)的插值函數(shù)，而點稱為插值節(jié)點。若滿足插值條件(3.2)的函數(shù)的基函數(shù)取，則是多項式稱滿足插值條件(3.2)的多項式為插值多項式。代數(shù)學基本定理：n次多項式有且僅有n個根（包括重根）插值多項式根據(jù)插值條件(3.2)，可形成有個未知量的個方程：，這個方程組的系數(shù)矩陣稱為Verdermonde矩陣，由其性質可知，當時，該方程組的解存在且唯一。因此有定理3.1：對數(shù)據(jù)點，存在滿足條件(3.3)的唯一的插值多項式；強調：插值多項式唯一——形式可以不同3.1.2Lagrange(形式)插值多項式由兩點直線方程談起，；若有不超過次的多項式：，可形成如下表：……100…00…00001…00…00………………0000…1…00…………0000…00…1……稱為Lagrange基本插值多項式，顯然它有個根：；由于次多項式有且僅有個根，因此注意到，可知：；若記便有不難證明為所求的插值多項式，它被稱為Lagrange（形式）插值多項式。缺點：增加插值節(jié)點后，Lagrange插值多項式發(fā)生大變化。舉例，3.1.3定義：差商一階差商：；二階差商：；n階差商：；考慮逐次增加插值節(jié)點后，插值多項式的變化：記滿足插值條件的（不超過）次插值多項式為，并記，即，注意：是次多項式；由故有；由于次多項式有且僅有個根，因此；確定系數(shù)：同樣的方法可得：由此形成的插值多項式稱作Newton插值多項式，記作：差商-性質1、對稱性：對的任意排列，有證明：前方法的Newton插值多項式的導出過程是：從僅滿足一個插值條件的插值多項式開始，逐步增加插值條件，直到最后的，形成的，它的次項的系數(shù)就是；同樣，若從僅滿足一個插值條件的插值多項式開始，逐步增加插值條件，直到最后的，形成的的最高次（次）項的系數(shù)就必定是。由插值多項式的唯一性可知，這兩個插值多項式是同一的，從而它們的次項的系數(shù)也是同一的，由此便得結論。差商-性質2、設有直到n階導數(shù)，則證明：設為插值節(jié)點，則對應的Newton插值多項式，令，顯然，它有個零點：；由定理可知有n個零點，同理可知有n-1個零點，依此不難推出在中至少有一個零點，記為，即：，而，由此得結論。例：多項式，且與點的選擇無關；例：設3.1.4帶導數(shù)的插值多項式若在點可導，利用差商和導數(shù)的定義，有，類似，可得到；上述結論也可以從差商性質2推出；例如，當時可獲得上述第一個結論，當時可得到后一個結論。說明：由此可知，Newton插值多項式是Taylor展開式的推廣例：求滿足下述插值條件的插值多項式，解：建立差商表：由此可寫出插值多項式；注：利用Newton插值多項式，重節(jié)點差商公式，以及差商性質2，容易看到：Taylor展開式實質上是當時的Newton插值多項式。3.1.5若將以為插值節(jié)點插值多項式，再增加一個插值節(jié)點，得插值多項式，由插值性質，有，據(jù)此，并由所取的任意性，可將改作，便得插值公式的余項公式：利用差商性質2，及符號，又可以有余項的另一種表達形式Runge現(xiàn)象：問題：答1：若有界，有界，則可。例：，顯然，取區(qū)間，插值點等距分布：等分區(qū)間，步長，節(jié)點逐步向外擴充，比較：使最?。菏菂^(qū)間中點，等分區(qū)間等分，則而當或，則所以，，從而若插值點非等距分布，例如可證明：，因此當時，另一方面，即使有界，當無界時，仍可能無界。例：，顯然，當．經(jīng)典的例子：函數(shù)，區(qū)間等分份，節(jié)點；（參考后圖）注意：通常插值公式用到.附表：的函數(shù)插值多項式值0.840.860.880.900.920.950.962.67444.06913.94510.0471-10.3345-39.9524-50.86440.970.9730.9740.9750.9760.978-58.5447-59.5704-59.7279-59.7819-59.7254-58.2381解決方案：分段多項式插值——減小，低階導數(shù)可估計、有界；同時保持小區(qū)間。其他插值方法，例如用其他基函數(shù)插值等；最小二乘近似——逼近點多，近似函數(shù)低階（放棄插值）；其他逼近方法。Runge函數(shù)及插值的圖形3.2分段插值分段三次多項式插值——樣條插值區(qū)間上的節(jié)點：要求：分段三次多項式，在節(jié)點處插值：，在內節(jié)點處連續(xù)：思路：由連續(xù)預設,為一次多項式：故積分2次積分常數(shù)（2個）由插值條件確定積分常數(shù)得（含預設的）利用連續(xù)：確定的個方程+2邊界條件確定加入的表達式，形成區(qū)間中，設2、求表達式：對積分2次：其中：由插值條件得3、求導，要求導數(shù)連續(xù)：有根據(jù)導數(shù)連續(xù)：，則由并記可得共個方程：4、完成需共個，確定之應有個方程，尚缺2個方程；需邊界條件：自然樣條（簡支）：，即給定(剛支）：令,由表達式：形成2個新的分別關于和的方程：無其他導數(shù)條件：由確定（三次）插值多項式由確定（三次）插值多項式的的系數(shù)：，的的系數(shù)是，令：又由原始設定：可知：形成方程：綜上，形成如下形式的元方程組：周期樣條：是周期函數(shù)，此時對方程：及對下標做適當調整：，形成：其中：；注：第1）2）4）三種情況線性方程組均為嚴格對角占優(yōu)矩陣，而3）產(chǎn)生了“不可約對角占優(yōu)矩陣”（我們在此不再對此進一步討論），它與嚴格對角占優(yōu)矩陣有幾乎相同的性質。計算步驟：計算：解方程組，取得，形成對，計算；定理3.5設，則以為節(jié)點的三次樣條滿足，其中。證明：記先在區(qū)間中考慮，記，取，令，則；由定理，存在使。注意：，因此，由可知：又：，所以。由于所以進一步有又由可得所以最后，由的任意性，有證完注意:此處用到隱含是內點標號!若（情況是相同的）：對于邊界條件a）此情況不存在，邊界條件b）此時，與前證明完全一樣；邊界條件d）此時扮演相同的角色，也都是內點，不存在問題；關于邊界條件c）問題較難討論。3.3最小二乘法3.3.1（線性）最小二乘問題的法方程已知數(shù)據(jù)點：，求近似式：，使函數(shù)與按以下標準取得極?。海划敃r，該問題稱為最小二乘問題，問題的解稱為最小二乘解。通過對以為參數(shù)，以為極小化目標函數(shù)的計算，可以證明該最小二乘問題的解就是方程組的解，此方程組稱為最小二乘問題的法方程組，其中；對此也可以從另一個角度作一簡單的解釋。作向量差；由方程組理論可知，當方程組的方程個數(shù)大于未知量個數(shù)時（通常稱為超定方程組），方程組一般無解，因此當時，方程組一般無解。但若將此方程組左乘，則方程組變成通常的階方程組，從而可以求解，這個階方程組就是法方程組。嚴格證明:注意到關于的極小與對應極小是完全一樣的.因此最小二乘問題的解應滿足方程:為解釋方便,將記為,注意到,有交換求和順序，便形成方程組：比較法方程的具體表達式：可知：法方程的解最小二乘問題的解。3.3.2正交化算法通常法方程組是病態(tài)的（），因此求解法方程組最好采用正交化方法，這是一個解線性方程組的穩(wěn)定性非常好的方法。定義：若矩陣滿足條件，即矩陣的逆矩陣是它的轉置矩陣，則稱此矩陣為正交矩陣。注意，從矩陣乘法規(guī)則容易看到，正交矩陣的列是互相正交的，而且它的列的2-范數(shù)長度為1。這也是它被稱為正交矩陣的原因。正交矩陣性質1：正交矩陣的乘積仍是正交矩陣。設是正交矩陣，則；正交矩陣性質2：（正交變換——在二、三維空間中旋轉變換——坐標軸夾角總是直角——不改變向量長度）；引理3.6：對任意非零向量，總存在正交矩陣，使，其中；證明：首先，對任意向量，若，容易驗證矩陣為正交矩陣。其次，令即；注意，向量是由其方向和長度唯一確定的，此向量的方向是，而其長度則為：，因此取。驗證：，而注意到因此，`，這就說明了：，即，對于給定的向量，取適當?shù)南蛄?，形成正交矩陣，使之滿足引理。算法：記矩陣，針對矩陣的第一列，構造m階正交矩陣,使：，從而有然后針對矩陣的第二列的后m-1個元素構造m-1階正交矩陣，使之成為m-1維空間的第一坐標方向向量：，再將擴充為m階正交矩陣，以此左乘，就有照此辦理，經(jīng)過n步如此的正交化過程，就有注意到正交矩陣的乘積仍是正交矩陣的乘積，由此，法方程組可變化為：當?shù)闹葹閚，即的n個列向量線性無關時，全不為0，對角矩陣滿秩，它必有逆矩陣。因此，由，其中，兩邊左乘，得，解此方程組，便可得所求的；同時，根據(jù)正交矩陣的性質，可有。由Lagrange插值多項式，待定函數(shù)方法構造余項：余項：設有直到階連續(xù)導數(shù),記令則由Rolle定理，在包含全體的區(qū)間中，有個零點，有個零點,…有(至少)一個零點,記作,由于為不超過次多項式,因此例：設為互異節(jié)點，是基本插值多項式，則1，0；例：求不超過2次插值多項式，使之滿足條件：解：利用待定系數(shù)法，令則由導數(shù)插值條件，應：，立即解得：，因此所求.例：若，則以-1，0，1，4為插值節(jié)點的三次插值多項式；差商4；例：（習題3-7，第129頁），以點為插值節(jié)點的插值多項式記為，求。解：由余項公式：，令，便有差商表：因此：第四章數(shù)值積分(NumericalIntegrationandDifferentiation)記號：——積分，——求積公式，誤差：，(QuadratureFormula)節(jié)點：，求積系數(shù)：；4.1內插求積,Newton-Cotes公式利用插值多項式：積分;例如,插值多項式取Lagrange形式,便有及此類通過在節(jié)點處滿足插值條件的插值多項式導出的求積公式稱為內插求積公式。其中：求積系數(shù)，誤差顯然，當函數(shù)為不超過次的多項式時，必有.由此可見,若函數(shù)為不超過某次的多項式，便有求積公式的誤差，即.定義：若求積公式對任何不超過m次的多項式成立：，而對次多項式等式不再成立，則稱該求積公式的代數(shù)精度為m(事實上,可對一般的函數(shù)與其相應的近似公式定義代數(shù)精度).代數(shù)精度——何時沒有誤差。本節(jié)討論的公式的節(jié)點為等距分布：——稱為Newton-Cotes公式4.1.1Newton-Cotes公式1）n=1，梯形(Trapezoidal)公式，誤差：利用積分中值定理（參見附錄I，定理I.6：積分中值定理）2）n=2Simpson公式，誤差注：該誤差公式不能簡單地對僅用此三點的插值多項式的余項公式積分獲得。3）n=4Cotes公式4.1.2復化求積公式(CompositeNumericalIntegration)梯形公式、Simpson公式的優(yōu)點：簡單，容易估計誤差；缺點：大區(qū)間誤差大改進：利用積分的可加性，1）復化梯形公式誤差：若連續(xù)，由連續(xù)函數(shù)的介值定理(見例I.2)，及，結論：代數(shù)精度1；計算精度——一般，若有誤差，誤差與步長的關聯(lián)程度；（若，則）2）復化Simpson公式誤差：若連續(xù)，與復化梯形公式誤差的推導一樣，有結論：代數(shù)精度3計算精度；4.1.3變步長積分法——步長的選取通常，對數(shù)值積分有一定的誤差要求：給定誤差界，使；1)復化梯形積分法，由誤差公式設在變化不大，即將以上兩式相除，即得由此，得梯形積分的誤差估計：；從而，由可計算的值估計；由于這是由約等式導出的，因此通常取估計數(shù)值積分是否達到誤差要求。2)Simpson積分公式，由誤差公式設在變化不大，即將以上兩式相除，即得；從而，由；3)變步長比較步長之比為2:1的復化梯形積分公式：，，可得（理解）:由此可見，容易通過計算步長對分以后兩個不同的復化梯形積分公式計算值的差，估計復化梯形積分公式的誤差，由此確定是否達到所要求的精度。4.1.4Romberg積分由梯形積分的誤差估計：，設想將誤差部分“歸還”給梯形積分，應可以得到積分的一個更精確的近似值。通過計算，有：==；注意，梯形積分公式的精度是，而通過適當?shù)慕M合，可得到Simpson公式，它的精度是，精度得到很大的提高；同時代數(shù)精度也得到提高。這種方法并沒有增加函數(shù)計算量，僅增加了極少的代數(shù)運算，就能大大地提高計算精度，這類方法通常被稱為“外推法”。用類似的方法，將Simpson公式適當?shù)亟M合，可得到精度為，代數(shù)精度為5的Cotes公式；再將Cotes公式適當?shù)亟M合，可得到精度，代數(shù)精度更高的Romberg公式：；在計算時，可列出如下的表進行計算：一般,Romberg方法用到為止，盡管理論上還可以繼續(xù)進行：以取得精度更高的公式。但我們可以從兩方面衡量該公式的實際意義。1、將此公式改為：，由于，因此可將此式認作是對的修正，而修正值是；當較大時，與已是積分的比較準確的近似值，因此這部分的修正對的進一步改進影響一般比較小；2、注意到公式的誤差：，公式的誤差：，公式的誤差：，公式的誤差需要用到f的高階導數(shù)，而f的高階導數(shù)的性態(tài)是很難確定的（如同插值多項式余項估計），因此，一般不再繼續(xù)進行此類外推（Romberg）方法，僅用到為止。例積分：例：積分：（效果并不明顯）由此，也可從此體會到，Romberg方法的效果（準確性），與被積函數(shù)的高階導數(shù)的性態(tài)有關。4.1.5待定系數(shù)法例：求確定以下公式的系數(shù)使之具有盡可能高的代數(shù)精度，求其代數(shù)精度，并求其誤差：解：取插值多項式，先求差商表：由此，通過對該插值多項式積分，得；因此求積公式為：；誤差：該插值多項式的余項：；由于在積分區(qū)間中，函數(shù)非正，因此由中值定理顯然，這是積分公式。而且從公式的導出過程可以看到，公式實際上隱含著函數(shù)在積分區(qū)間中點處的導數(shù)值信息，因此作為等距節(jié)點數(shù)值積分公式，它用到了函數(shù)的4個信息，它具有4階精度（），代數(shù)精度達到3.注：對于一般區(qū)間的積分，可用變量代換將積分變換到區(qū)間：，再利用所獲得的結果，便可得到前獲得的積分公式，及其誤差公式。但這樣求積分公式比較麻煩，以下介紹另一種方法——待定系數(shù)法。通常情況下，公式的代數(shù)精度越高，該公式越精確。因此，可以利用代數(shù)精度刻畫的積分與求積公式的等式關系，確定未知的求積公式中的某些待定的參數(shù)，使公式達到盡可能高的代數(shù)精度。前面定義代數(shù)精度：若求積公式對任何不超過m次的多項式成立：，即，而對m+1次多項式則不再成立，則稱該求積公式的代數(shù)精度為m.由前已得的梯形、Simpson等公式的誤差表達式（一般形式為）容易判定其代數(shù)精度分別為1和3.然而如果僅有公式,一般不易判定其代數(shù)精度,因為無法用無窮多的“任何不超過m次的多項式”去驗證是否總有。為此我們可以給出代數(shù)精度的另一種定義：求積公式的代數(shù)精度為，當且僅當對任何不超過m次的單項式成立：，而對則（參見本章習題1）。顯然，這種定義只須次驗證即可完成，從而確定求積公式的代數(shù)精度。另一方面，上述等式關系形成了個方程，從而可以確定求積公式的個系數(shù)。這樣導出公式的方法稱為待定系數(shù)法。此外，若一個求積公式的代數(shù)精度為，由代數(shù)精度的新的定義方式可知，公式誤差的一般形式必為，因此確定求積公式的誤差實際上是確定系數(shù)，若令，注意到的階導數(shù)為常數(shù)：，因此由：容易得到系數(shù)（注意：和在驗證該公式的代數(shù)精度時都已經(jīng)計算過），從而便可得到誤差表達式。例（重復前例）：確定以下公式的系數(shù)使之具有盡可能高的代數(shù)精度，求其代數(shù)精度，及其誤差：；解：取分別代入公式，由代數(shù)精度的等價條件，可以形成4個方程，據(jù)此確定公式的4個系數(shù)：解此方程組，得；再考察等式是否成立:左邊==右邊，所以公式的代數(shù)精度為3.由此得公式：，顯然，待定系數(shù)法比以前用插值多項式積分的方法要簡單得多。公式的誤差：由于令，有，因此，由此得誤差公式：例：確定以下公式的系數(shù)使之具有盡可能高的代數(shù)精度，求其代數(shù)精度，及公式誤差：；解：仿前，有又：令，故代數(shù)精度：3誤差：令，有，因此，由此得誤差公式：.一般：例：確定以下公式的系數(shù)使之具有盡可能高的代數(shù)精度，求其代數(shù)精度，及公式誤差：；解：仿前，有得公式：又：令，故代數(shù)精度：3誤差：令，有，因此，由此得例：確定以下公式的系數(shù)使之具有盡可能高的代數(shù)精度，求其代數(shù)精度，及公式誤差：解：仿前解得：，代數(shù)精度為3，公式誤差：由令，有，因此，由此得誤差公式：例：確定以下公式的系數(shù)使之具有盡可能高的代數(shù)精度，求其代數(shù)精度，及公式誤差（上例中的情況）：解：仿前解得：，公式：將代入，等式成立，而代入，等式不再成立。因此代數(shù)精度為3.公式的誤差：由于令，有，因此，由此得誤差公式：例：確定以下公式的系數(shù)及節(jié)點使公式具有盡可能高的代數(shù)精度，求其代數(shù)精度，及公式誤差：解：仿前解得：；公式：，且代數(shù)精度為3.誤差：由于令，有，因此，由此得誤差公式：例4.8：確定以下公式的系數(shù)，及節(jié)點，使之具有盡可能高的代數(shù)精度，并求其代數(shù)精度：解：仿前：解得，，；公式：，代數(shù)精度3；誤差：由于令，有，因此，由此得誤差公式：注：由此兩例，可知節(jié)點，代數(shù)精度可達——積分；4.1.6樣條函數(shù)的應用由樣條函數(shù)公式：由已知節(jié)點，〈及邊界條件〉，可得：誤差估計：與Simpson公式比較，該區(qū)間中點的函數(shù)值由樣條函數(shù)公式得，按Simpson公式，可得這說明，利用樣條插值函數(shù)所構造的求積公式得到的值與利用Simpson公式導出的積分的近似值相同。因此，這兩者的精度一致，即利用樣條插值函數(shù)所構造的求積公式的精度為.4.3自適應積分法前述復化公式均采用等分區(qū)間，例如復化梯形，誤差,要求,當,則。此數(shù)值當大時，可能很小，即：區(qū)間將要求等分很多份，或：要求計算大量的函數(shù)值（實際計算用，而這總是對區(qū)間作整體考慮的）。例：對應在,若?。褐腥?，要求區(qū)間等分段,計算個函數(shù)值.取，要求區(qū)間等分段部分的積分,若承擔誤差，因此取，要求區(qū)間等分段部分的積分,若承擔誤差，因此取，要求區(qū)間等分4段最后,將區(qū)間分為[0,1],[1,2]和[2,10]三部分；按上述分析，可：等分10000段；等分375段；[1,2]：等分64段；等分4段，總數(shù)為10068段，計算10069個函數(shù)值。5443段依此思想，給定區(qū)間上求積分，誤差界，則若，不滿足，則考慮在前半?yún)^(qū)間（后半?yún)^(qū)間一樣）上：是否滿足。若不滿足，再對分；若滿足，則計算后半?yún)^(qū)間。而每一小段承擔的誤差由其長度在區(qū)間總長中所占的比值確定。4.4Gauss型積分與正交多項式前Newton-Cotes公式的結點是等距分布的；其代數(shù)精度當結點個數(shù)（包括重結點）為則代數(shù)精度為,可否提高?由前“4.5待定系數(shù)法”節(jié)的例（書.163例4.8）可知,若適當選取結點,其代數(shù)精度可達到；問題1：結點（包括重結點）數(shù)為代數(shù)精度可否比可否更高?結論：結點數(shù)為代數(shù)精度最高就是。反證，若取次多項式則，由于非負，且不恒為0，因此積分而求積公式矛盾。因此，任何求積公式的代數(shù)精度最高就是。問題：結點如何選取——正交多項式的根?？疾鞄嗪瘮?shù)的積分4.4.1正交多項式定義:記為關于權函數(shù)的內積.若則稱在區(qū)間上關于權函數(shù)正交.若函數(shù)族在上兩兩正交,即稱為正交函數(shù)族；特別,若,則稱之為標準正交函數(shù)族.例:4.9為上,權為1的正交函數(shù)族;正交多項式——注意：在實數(shù)域內，任何高次多項式總可由低次多項式組合而成；最高次項系數(shù)為1的正交多項式記為；問題2：（積分）區(qū)間上，權函數(shù)為的正交多項式如何構造？定理4.9:令則最高次項系數(shù)為1的正交多項式系可由以下遞推公式生成:其中證明:顯然，如此構造的多項式系的最高次項系數(shù)為1。1：令與正交:立得():;一般,由遞推關系,對取內積，若已有，則表達式;再對取內積:注意；，并將展開由正交性可得：因此有上述遞推公式。最后，證明由此構造的確是最高次項的系數(shù)為1的正交多項式系。即，由，從而當時，推得是正交多項式系。2：是顯然的，（）。在此基礎上直接得到：；因此，是正交系。又在它的基礎上有；3：再證明由于，而；因此（為稍后方便，將改寫為）因此是正交系。4：歸納證明：設已是正交系，即它們相互正交，基于上述假設，構造過程已有以下證明新構造的多項式與它們都正交，即：與前相同，是最高次項的系數(shù)為1的次多項式，因此因此，按公式構造的多項式系為正交多項式系。推論4.10：最高次項系數(shù)為的正交多項式系的遞推公式其中.稍后，我們將取正交多項式的根為求積公式的節(jié)點。問題3：次正交多項式有多少個實根？定理4.11:次正交多項式有個互異實根.證明：1）在中有實根：反證，設，若（或，則由正交性與（或性質，有矛盾，所以至少有一個根。2）單根：若為重根為次多項式，由正交性又矛盾，所以若有根則必為單根。3）在中有且共有個互異實根：反證：若僅有個根：，即其中（或（因為它在此區(qū)間中不再有其他根），且是次多項式。將函數(shù)在上按權函數(shù)積分，由于為次多項式，因此，按正交性：另一方面，被積函數(shù)在上保持符號，因此（或）矛盾。綜上，n次正交多項式在上恰有n個互異實根。4.4.2Gauss型求積公式1）Gauss型積分性質個節(jié)點,代數(shù)精度達到的求積公式稱為Gauss型求積公式,這樣的節(jié)點稱為Gauss點.問題4：這個Gauss點與正交多項式的個根關系如何？定理4.12:求積公式節(jié)點成為Gauss點的充要條件是:是上以為權的正交多項式的個根；證明：設為Gauss點，記，因代數(shù)精度：，故對任何——不超過次多項式——說明：與任何不超過次多項式正交，是第個正交多項式（至多差一個系數(shù)），即是正交多項式的根。設為正交多項式，，則任何次多項式——：次多項式；由正交性，點內插型求積公式的代數(shù)精度至少：i.e．公式代數(shù)精度：——為Gauss點。2)求積系數(shù)及誤差誤差：由于此處考慮一般的Gauss型積分，因此對代數(shù)精度為的求積公式，求誤差公式不是取，而是取，此時有。由于代數(shù)精度為，一般地有，因此可知4.4.3若干典型公式（各公式的Gauss點，對應的求積系數(shù)及誤差，請參見教材）Legendre多項式、積分——權，區(qū)間，或遞推公式：Laguerre多項式、積分——權，區(qū)間，或遞推公式：Chebychev多項式、積分——權，區(qū)間或遞推公式：算法——利用已有積分公式，作變量代換；或構造相應的正交多項式，求其根及積分常數(shù)。例：試求以下求積公式的結點及求積系數(shù)，使公式具有最高代數(shù)精度（：解：具有最高代數(shù)精度的求積公式必是Gauss型求積公式，對積分區(qū)間，先求相應的正交多項式：內積：（可驗證其正交性），結點：，插值多項式：因此，Gauss積分公式（即：中矩形公式）為代數(shù)精度為1.，結點：插值多項式：由求積系數(shù)因此，公式當，其Gauss求積公式：可驗證代數(shù)精度：誤差：本例也可用待定系數(shù)法解，但時，求解較困難。此外也可利用Legendre積分，經(jīng)過積分限的變換獲得：對積分，利用變量代換：顯然，對應于，因此由Legendre多項式，可知結點為：，通過公式或查表可知兩求積系數(shù)均為1，因此時再利用及，可得同樣的結果：4.5數(shù)值微分4.5.1插值公式方法數(shù)值導數(shù)與數(shù)值積分類似，可由插值公式的導數(shù)得到。先引入一個公式：：證：；類似的，有二階導數(shù)公式：同樣，有等等；由此可得高階導數(shù)公式：等等。一階導數(shù)的數(shù)值計算公式：兩點插值，Newton插值多項式：兩邊求導；由此，顯然當時，差商是導數(shù)的良好近似。因此，在上式中代入便得，；類似地，對三點插值公式（等距點）求導，其中，可得分別代入，注意到由此，可得以下公式：，，；二階導數(shù),由可知，當時，差商是導數(shù)的良好近似。又由，因此，在上式中分別代入可得，，；Taylor公式方法(待定系數(shù)法)在求數(shù)值導數(shù)時，總希望誤差小。從誤差項看，（當誤差項中的導數(shù)有界時）總是步長越小越好。但另一方面，數(shù)值導數(shù)總是一個除式，要做一個除法，除數(shù)是（或），它當然是一個小數(shù)；而被除數(shù)也是一個小數(shù)，如上例中求，由于存在，必連續(xù)，當小時，與必為相近數(shù)，此兩相近數(shù)在浮點數(shù)系內相減時必然減損有效數(shù)位，再除以小數(shù)，必然產(chǎn)生大誤差。因此，數(shù)值導數(shù)問題總是病態(tài)問題。而實際算例也證明，步長并非越小越好，太小經(jīng)常反而會產(chǎn)生大誤差。因此為實現(xiàn)計算的誤差盡可能小，應采用誤差項中的冪次高的方法，通常就用“外推法”。在導出該方法時，需要先導出能比較準確地描述誤差項的數(shù)值導數(shù)公式。為此先介紹利用Taylor展開式導出數(shù)值導數(shù)公式的一種方法。我們通過例子介紹這一方法。例：確定如下數(shù)值導數(shù)公式的系數(shù)及其誤差：；解：由Taylor展開式：比較系數(shù)，可知所以；此時，便有寫成通常的形式，便是：；外推法外推法是一種利用一個（或若干個）公式的不同步長的計算結果，進行適當?shù)慕M合，獲得比原公式精度更高的一種方法。例如，以前我們介紹的Romberg積分方法就是一種外推方法。我們仍用一個例子介紹這種方法。仍如上例，若記近似公式：在上面的推導中如果再保留若干項，可得該近似公式的更精細的誤差：，及：；組合之從而有：記計算的公式：，顯然，該公式的精度達到，這說明由原精度為的公式經(jīng)適當組合后精度提高了2階達到精度。若再進一步將適當組合，精度會進一步提高。這一類方法稱為外推法，它可以達到較高的精度。這樣，在數(shù)值計算中，就可以以相對較大的步長，可以得到很高的精確度。第五章非線性方程求解5.1解一元方程的迭代法方程：，準確解；方法形成，迭代法——逐次逼近問題I）如何將方程的形式轉化為？II）給定初值，迭代產(chǎn)生的向量序列是否收斂？III）序列的收斂性與初值的選取是否相關？IV）如果收斂，如何估計誤差？5.1.1簡單迭代法方程簡單迭代，迭代函數(shù)為一元函數(shù)，且與迭代步無關。解：采用兩種方法迭代，等價方程：方法1，，迭代：,取不收斂方法2，，迭代：…..……..…例2.()解：采用兩種方法迭代，等價方程：方法1，迭代，取不同的初值：…..……..…不收斂方法2,迭代,取不同初值:…..……..…超出定義域要求理解：解非線性方程的迭代法的收斂性，不僅與迭代函數(shù)有關，而且與所選的初值有關！Newton迭代法思想：非線性問題局部線性化處理：對局部線性化，設的第次近似已知，僅依賴信息生成線性函數(shù)，在的鄰近局部替代，以的零點為的零點的新近似：在處取插值條件：，構造插值多項式（形式）：；以方程：的零點作為的解的新近似：此迭代，稱為Newton迭代。另一解釋：在處的展開式當在鄰近時，顯然可以略去二次項，記則(這仍是形式插值多項式)，當為的近似，以代替原方程，，這仍是方程，解出便是Newton迭代。從迭代計算式可知，當連續(xù)，由出發(fā)，Newton迭代生成的序列若收斂于，且，則必有，即是的解。解：Newton迭代：，初值；例2、()解：Newton迭代：，初值1：；初值2：；Newton迭代幾何意義：已有近似，則以通過的的切線與軸的交點，作為的新近似；優(yōu)點：收斂快，自修正性（計算誤差干擾小）；缺點：每步需計算，初值要求在解的鄰近；“計算”的解決方案之一，充分利用已得的：簡化Newton法——固定例1、解：簡化Newton迭代，初值；“計算”的解決方案之二：5.1.3割線法目的：對局部線性化，以線性函數(shù)在近似解的鄰近局部替代，迭代依賴信息，即以通過與的割線與軸的交點，作為的新近似：插值：，；！注意：通常取，且由于“數(shù)值導數(shù)總是病態(tài)的”，因此通常用后一式計算。例1、解：割線迭代，初值；5.1.4區(qū)間法——“尋求較好的初值”方案之一，二分法——尋求含的盡可能精確的區(qū)間初始區(qū)間————，區(qū)間中點，計算——確定新區(qū)間，原則：1）區(qū)間長度減半，2）在此區(qū)間內，若則，否則：；一般，由計算，比較數(shù)據(jù)；經(jīng)步，若區(qū)間長度，可??；弦位法——尋求：含的盡可能精確的區(qū)間，或初始區(qū)間————，由，取若則；兩種可能：1）區(qū)間長，2）點，或；5.2收斂性問題5.2.1簡單迭代——不動點討論的收斂性定理5.1：（壓縮映象原理）若1）（適定性）2）（壓縮性）則在中有唯一的不動點，任取，迭代生成的序列收斂于，且有估計證明：①由條件1）可知，由，同理，若；因此當時，必有②解存在：令；又由條件2），連續(xù)，故連續(xù)；由此可知必有，使,即的不動點；③唯一性：若另有，則,矛盾；④收斂：設則由1）可知且有令由此可知，即；⑤誤差估計：由2），若，則,特別：，所以，在此式中令，由及的收斂性，，便得結論。推論5.2：若在可導，，則上述定理的條件2）成立；例：例1中，1）迭代，區(qū)間：當又，因此迭代收斂。2）迭代；取區(qū)間，則，可知，但，因此，，總有，即：迭代不可能收斂。注1：、條件“”是必須的；若改為“”，則不動點的存在性將存疑。例：顯然:且而在中無不動點()注意:由(不妨設),當,即不存在常數(shù)使條件2)成立.問題:如何將條件1)推廣到區(qū)間的情況?若對定理成立,可將,可得:定理在區(qū)間成立；同樣，再將，便可有：定理在上成立。注2：若在不動點及其鄰域中連續(xù)，且，則必有小量，使，總有。注：以上性質僅為“定性”，除非能準確地得到數(shù)，5.2.2收斂改善1、松馳因子法：——改善定理5.1中的,使盡可能?。喝舻皇諗?，改善之，使迭代收斂；若迭代收斂，使迭代加速；考慮:在鄰近,有,令,則在鄰近,注意到這是的導數(shù),并考慮迭代式的不動點是,因此取迭代函數(shù).仍以為不動點,且時,取,迭代必收斂.例:例1,迭代不收斂，若已知，取，：初值迭代收斂，加速:取，迭代；取初值2、Aitkin加速——迭代收斂，但較慢，加速：若迭代收斂，即，由當在的鄰近，有，所以由此，解得通常將右端作為新的迭代值。若記此為迭代為，有，此即為Aitkin加速。5.2.3Newton法的收斂性Newton迭代：，按推論5.2，，若在鄰近有界，及由可知：定理5.3：若在二階導數(shù)連續(xù)，則當充分接近時，Newton迭代收斂。注：由于總存在的鄰域，當時，使。定理5.4：若在二階導數(shù)連續(xù)，且1）2），3）在中不改變符號，則當取時，Newton迭代收斂。證明：由條件可知（連續(xù)，不變號，在區(qū)間嚴格單調，而由1），方程在區(qū)間有解，因此，解唯一。下設。由，而知；由此而因為，，所以，故由得，綜上，，由歸納法便得序列單調增上有界，必有極限，記，又在式中令，可知；由解的唯一性，.5.2.4收斂速度定義：迭代序列收斂于，若有常數(shù)，成立則稱序列（至少）階收斂。特別，若，稱為線性收斂；若，且當，稱為超線性收斂；若，稱為2階收斂或平方收斂；一般的簡單迭代是線性收斂。Newton迭代——二階收斂Taylor展開：Newton迭代：相減，得：，即：，2階收斂。2）割線迭代——超線性收斂兩點插值及其余項：，割線法：，相減，得：，又,因此由于有界，，記，則，即超線性收斂。一般有定理：若迭代以初值生成的序列收斂于，又各級導數(shù)存在連續(xù)，且，而，且在鄰域有界，則該迭代的收斂速度為階。證：由Taylor展開式：得：令，則有。收斂速度的解釋——例：線性：超線性：平方收斂：例：方程在0.3鄰近有解，（1）請問，以0.3為初值，迭代是否收斂到此根，請證明之；（2）對此迭代實施改善，若不收斂，使改善后的迭代收斂；若收斂，使改善后的迭代收斂加速；（3）另設計2個收斂的簡單迭代法，及其選取的初值范圍。（參考數(shù)據(jù)：，）解：（1），取區(qū)間，顯然，此時，，因此所以，迭代不收斂；（2）改善：迭代必收斂。（若取區(qū)間，則而所以若取區(qū)間，則同樣有且，所以迭代必收斂；）（3）①取且收斂（初值，如）；（若?。贜ewton迭代，所以，取收斂；（）5.3*非線性方程組5.3.1簡單迭代法：取適當初值，迭代生成序列，考察的收斂性。的導數(shù)（矩陣）：是的不動點,。定理：閉集，若1）2）在閉集上存在，且連續(xù)，，則在中有唯一不動點，且任取初值，迭代生成序列必收斂于，并有估計式5.3.2Newton法線性化，，略去二階項，得，令此右端為：，解此方程得，便得Newton迭代：實際計算不求逆，而解方程：優(yōu)點：收斂速度快；有自修正性；缺點：對初值要求高；每步要求計算導數(shù)矩陣。解決方法1，簡化Newton法：，從而變成解方程：此時，通常將矩陣的分解保留，在解不同右端“”，時可以節(jié)省大量運算工作量。解決方法2：割線法線性化：尋求線性函數(shù)在解的鄰近成立。對元方程組，設已有個近似點（不妨設）：，應使由此確定矩陣與向量；<不求它們>，再解方程組，得新近似；為此，設向量組：線性相關；特別，設后個向量線性無關；即由它們形成的階矩陣非奇（或可逆）；在此假設下，第一個向量可由后個向量線性線性組合成：將此分別以代入，經(jīng)歸并，得因為。目標是取得方程組的解，因此令，便可知，取便是所求的解。而，則可由解方程組取得?；?，由已有的，考慮新近似，由，按上述組合系數(shù)組合：有由要求獲得的解，要求成立，因此有令，此即，從而新解。第六章常微分方程數(shù)值方法連續(xù)問題的離散處理——尋求微分方程的解在某些離散點上的值——在處的近似值；記號：——所求函數(shù)在處的（準確）函數(shù)值，——計算得到的處的函數(shù)（近似）值，——節(jié)點，——步長；等步長：；以下若不另作說明，一般總記為等步長?！?.1初值問題的數(shù)值方法考察微分方程初值問題：由微分方程理論可知：若函數(shù)關于滿足條件，即存在與無關的常數(shù)，使初值問題的解存在且唯一；6.1.1法及其變形1、法由Taylor展開式：作局部化假設：，并略去項，便有將此式右端作為的近似，便得到公式Euler公式兩者的差（即略去的項）稱為局部截斷誤差，記作：Euler公式也可由其他方法導出，例如由第四章數(shù)值導數(shù)公式，可有：；解出，并由替換，便可得Euler公式。又如，根據(jù)Newton-leibniz公式：將以“0次插值多項式”替換，即以代入積分，得到數(shù)值積分（左矩形）公式，及其誤差：又得到與Taylor展開式相同的表達式，從而又導出Euler公式。幾何意義——折線法若一個公式的局部截斷誤差為，則稱該公式的精度為階，或該公式為階公式。Euler公式是1階公式。注意，以上的截斷誤差是在局部化假設的前提下得到的，即認定。倘若在每一步都按局部化假設，我們有Euler公式的總體截斷誤差：2、后退法若取數(shù)值導數(shù)公式：與前相同的推導過程，可以得到在局部化假設的前提下截去局部截斷誤差便得到后退法公式：注意到此公式中的右端也有，需要求解關于的方程才能得到。因此將這類公式稱為隱式公式，而將可以通過直接計算得到的公式稱為顯式公式。后退公式是一階隱式公式，Euler公式是1階顯式公式6.1.2多步法梯形公式：在式右端的積分中，取梯形積分公式，有由此，并據(jù)微分方程，可得：梯形公式局部截斷誤差：這是一個2階隱式公式。Simpson公式：在式右端的積分中，取Simpson積分公式，有由此，并據(jù)微分方程，可得：Simpson公式局部截斷誤差：；與以前的公式不同，用Simpson公式計算，必須有前2步的函數(shù)值：和。因此這種方法稱為2步方法，而為啟動此算法所需的最初的2個函數(shù)值：稱為表頭。更一般的，若計算必須有至少前2步函數(shù)值，則這種方法稱為多步法。具體地，若計算必須有前k步的函數(shù)值，則這種方法稱為k步方法，而為啟動該方法所需的最初的k個函數(shù)值：稱為該方法的表頭。與此相對，以前的方法計算，只須前1步的函數(shù)值，便稱為單步方法。因此，Simpson公式是2步、4階、隱式方法。Adams方法（線性多步法）在式右端的積分中，若取具有k+1節(jié)點的插值多項式近似替代作為被積函數(shù)，導出初值問題的求解方法稱為Adams方法。（1）顯式Adams方法——Adams-Bashforth公式取處的構造插值多項式取代：其中。由于，有由此（以后為方便計，記），可得顯式的多步法Adams-Bashforth公式及其局部截斷誤差這是步、階的顯式公式。下表是的的數(shù)值（注意：）011123-121223-16532455-5937-947201901-27742616-1274251以下是的公式推導過程：作變量代換：，以為變量，當?shù)淖兓瘏^(qū)間為時，的變化區(qū)間為，且，有（2）隱式Adams方法——Adams-Moulton公式若取處的構造插值多項式取代，與前一樣的方法，可得隱式的多步法Adams-Moulton公式及其局部截斷誤差這是步、階的隱式公式。下表是的的數(shù)值（注意：）：011121121258-1324919-514720251646-264106-19述評：從表可見，對相同的，相同，而，特別是：，，而有若干，因而在存在計算誤差時，由前步導致的誤差顯然隱式公式要比顯式公式小（顯式公式對前步的誤差會被放大，而顯隱式公式則不會），而且局部截斷誤差也是隱式公式要比顯式公式小，結論：隱式公式的穩(wěn)定性一般比顯式公式好。6.1.3待定系數(shù)法利用展開式比較有關項的系數(shù)，可以直接導出公式——待定系數(shù)法。例：求以下數(shù)值公式的系數(shù)使公式具有盡可能高的精度：解：由于，因此由展開式，同時，對所求公式右端各項也作相應的展開，并乘以相應的系數(shù)：由于期望盡可能準確，比較各對應項的系數(shù)，可得方程組：，解之可得：；注意到局部截斷誤差是，因此顯然，這就是的顯式Adams-Bashforth公式。例：求以下數(shù)值公式的系數(shù)使公式具有盡可能高的精度：與上例完全一樣，比較系數(shù)，可得公式：局部截斷誤差：這個公式稱為Milne公式，稍后我們將用到它。綜上所述，從公式的構造過程可見，微分方程初值問題的算法公式基本上源于：Taylor展開式、數(shù)值積分或數(shù)值微分，而插值方法一般也是通過數(shù)值積分或數(shù)值微分完成的。Taylor展開式——待定系數(shù)法直接來自于Taylor展開式，通過比較系數(shù)，形成線性方程組，取得公式與局部截斷誤差；數(shù)值積分——前面的多步法等，基本上都源于此，例如梯形、Simpson方法等，而Adams方法用的是，當用不同的點生成的不同的插值多項式代換時，便得到不同的公式，包括顯式和隱式公式；數(shù)值微分——由導出Euler公式，而由可導出后退Euler公式，若取3點數(shù)值微分公式可導出更多公式：其中第二個公式就是“中點公式”；當然它們也可以由待定系數(shù)法取得：例如第3個公式：用待定系數(shù)法求以下隱式公式的系數(shù)及局部截斷誤差：由Taylor展開式：比較：為使公式具有盡可能高的精度，比較系數(shù)，得方程組：因此，公式是，與之相應，有局部截斷誤差：6.1.4問題的性態(tài)與算法的穩(wěn)定性問題的性態(tài)——問題對原始數(shù)據(jù)的敏感性原始數(shù)據(jù)————問題的應有的結果原始數(shù)據(jù)擾動———問題的結果問題的條件數(shù)——相對誤差之比的上確界：由微積分知識：初值問題：固定步長，初值；計算結果：因此：由于，當；或：又得：因此：良態(tài)病態(tài)例：方程的解病態(tài)（圖示——）例：方程的解良態(tài)（圖示——）例：，當病態(tài)，當良態(tài)。（圖示——）方法的穩(wěn)定性——方法：由初始誤差導致的后期誤差的可控性。中點法：由數(shù)值導數(shù)公式得可導出中點法此為2步2階公式，但穩(wěn)定性差。例：真解：取2種不同的表頭：（即一步法），下表中列出對不同的步長：計算的近似值，按后退法計算獲得，按中點法由初值及表頭獲得，按中點法由初值及表頭獲得，誤差放大則是比值。后退法誤差放大5741119091112110798說明：總體誤差，由前可知——后退法：因此，對于后退法，若，（）可計算得；若，可計算得顯然實際情況良好；而對于中點法，其總體誤差考慮表頭都用準確值（注意在浮點數(shù)系中運算，仍是有誤差的，這可認為是初始誤差），若，（）可計算得，而，可計算得，而實際計算并非如此。2、對于同是中點法：由此表可見，兩個中點法的不同結果是由不同的表頭導致的，實際的不同僅是的不同，而它們之間的誤差（或不同）導致的計算結果的誤差被放大5000倍甚至1萬余倍。說明中點法并不是好的方法，盡管它是一個2階方法，但實際計算不如后退法這樣的1階方法。定義：步方法，若存在常數(shù)其中及是按此方法分別由表頭及計算得到，則稱此方法是穩(wěn)定的。此定義因未限制，故實際可要求，因此本定義又——“漸近穩(wěn)定性”或“0穩(wěn)定性”。實際計算關心——對確定步長，一個算法，每步計算誤差是否被放大？——無法討論一般方程——研究對象：典型方程：其中：。原因：對維常微分方程組：，為階矩陣，它的特征值反映了矩陣的性態(tài)，當時，方程是良態(tài)，若時則是病態(tài)（工程中，通常稱之為“穩(wěn)定性”，時，系統(tǒng)穩(wěn)定，否則，不穩(wěn)定）。定義：對于典型方程，及確定的，一個步方法，若由表頭及計算得到及，存在常數(shù)使則稱此方法對是絕對穩(wěn)定的，全體的集合稱為該方法的絕對穩(wěn)定域。事實上，也可將此定義改寫成對于單步法則為：對典型方程，單步法總有例如：法：，后退法：，梯形法：，；由于單步法因此，當則方法絕對穩(wěn)定：法：，在復平面上是以–1為中心，1為半徑的圓內部；后退法：，即，在復平面上是以1為中心，1為半徑的圓的外部。為稍后介紹方便，對一般的步方法，寫成即：例如法：后退法：中點法：梯形法：法：；定義——算法的特征多項式：其中分別稱為算法（*）