數(shù)值計算方法(第3章)1課件

第3章線性方程組的數(shù)值解法1引言在自然科學和工程技術中很多問題的解決常常歸結為解線性代數(shù)方程組。

線性代數(shù)方面的計算方法就是研究求解線性方程組的一些數(shù)值解法與研究計算矩陣的特征值及特征向量的數(shù)值方法。2引言關于線性方程組的數(shù)值解法一般有兩類。直接法：經(jīng)過有限步算術運算，可求得方程組的精確解的方法（若在計算過程中沒有舍入誤差）高斯消去法和矩陣分解法迭代法：用某種極限過程去逐步逼近線性方程組精確解的方法直接法適合中小規(guī)模迭代法適于大型線性方程，存在收斂性及收斂速度等問題3什么是n元線性方程組簡記AX=bN個未知量N個方程4矩陣形式AX=b5克萊姆法則在理論上有著重大意義，但在實際應用中存在很大的困難，在線性代數(shù)中，為解決這一困難給出了高斯消元法。63.1高斯消元法3.1.1高斯順序消元法3.1.2高斯主元消元法73.1高斯消元法用消元法解方程組回憶手工解法8消元過程9上述過程如何用程序寫出？10消去過程GaussElimination(A[1..n，1..n],b[1..n])//輸入：系數(shù)矩陣A及常數(shù)項b//輸出：方程組的增廣矩陣等價的上三角矩陣fori=1tondo A[i][n+1]=b[i]fori=1ton-1doifA[i][i]=0then停機else forj=i+1tondofork=iton+1doA[j][k]=A[j][k]–A[i][k]*A[j][i]/A[i][i]11高斯消去法的計算量—消元過程

fori=1tondoA[i][n+1]=b[i]fori=1ton-1doifA[i][i]=0then停機elseforj=i+1tondofork=iton+1doA[j][k]=A[j][k]–A[i][k]*A[j][i]/A[i][i]若把內(nèi)層循環(huán)看成1個單位的工作量三層循環(huán)的總工作量是多少？12思考回代過程如何編寫？將解xi存放在bi中，即第n+1列記載解的值。13高斯消去法的計算量—回代過程同樣依據(jù)循環(huán)次數(shù)考慮14上標表示即將做第1次消元15第一次消元16設第k-1次消元得A(k)x=b(k)其中17高斯順序消去法則第k次消元:18最后19高斯順序消去法也就是對于方程組AX=b系數(shù)矩陣做：20高斯順序消去法

21高斯順序消去法

22高斯順序消去法條件

從最內(nèi)層循環(huán)看出順序消去法的條件是A[j][k]=A[j][k]–A[i][k]*A[j][i]/A[i][i]233.1.2高斯主元素消去法Gauss列主元消元法：從列的角度控制循環(huán)當k=1時，考察第一列找出絕對值最大的元素最大元素在第二行交換第二行和第k=1行的位置在此基礎上按前面的高斯順序消去法消掉第一個變量24當k=2時，考察第二列找出絕對值最大的元素(除第1行)最大元素在第三行交換第三行和第k=2行的位置在此基礎上按前面的高斯順序消去法消掉第二個變量2526betterGaussElimination(A[1..n，1..n],b[1..n])//輸入：系數(shù)矩陣A及常數(shù)項b//輸出：方程組的增廣矩陣等價的上三角矩陣fori=1tondoA[i][n+1]=b[i]fori=1ton-1dopivotrow=iforj=i+1tondoif|A[j,i]|>|A[pivotrow,i]|pivotrow=jifA[pivotrow,i]=0then停機elsefork=iton+1doswap(A[i,k],A[pivotrow,k]) forj=i+1tondofork=iton+1doA[j][k]=A[j][k]–A[i][k]*A[j][i]/A[i][i]27練習282.全主元消去法當k=1時，在第k=1列到第n=4列，第k=1行到第n=4行范圍內(nèi)找出絕對值最大的元素最大元素在第4行，第4列交換第k=1行和第4行的位置，再交換第k=1列和第4列的位置用數(shù)組記錄列的交換z(1)=4z(4)=129在此基礎上按前面的高斯順序消去法進行第一次消元30當k=2時，在第k=2列到第n=4列，第k=2行到第n=4行范圍內(nèi)找出絕對值最大的元素最大元素在第3行，第3列交換第k=2行和第3行的位置，再交換第k=2列和第3列的位置用數(shù)組記錄列的交換z(2)=3z(3)=231在此基礎上按前面的高斯順序消去法進行第二次消元32當k=3時，在第3列到第4列，第3行到第4行范圍內(nèi)找出絕對值最大的元素最大元素在第3行，第3列交換第3行和第3行的位置，再交換第3列和第3列的位置3334練習353.高斯-約當消去法與一般消去法相比，高斯—約當消去法是一種無回代過程的算法36例子第k=1步，從當前第k=1列選擇列主元,(注意從第k行開始)主元在第1行，不存在交換對于第k行：用主元除第k=1行的所有元素對于第i行(i<>k)：用-aik乘以第k行加到元素所在行i37第k=2步，從當前第k=2列選擇列主元,(注意從第k行開始)主元在第3行，交換第3行和第k行對于第k行：用主元除第k=2行的所有元素對于第i行(i<>k)：用-aik乘以第k行加到元素所在行i38第k=3步，從當前第k=3列選擇列主元,(注意從第k行開始)主元在第3行，無需交換對于第k行：用主元除第k=3行的所有元素對于第i行(i<>k)：用-aik乘以第k行加到元素所在行i則原方程的解是x=（3，-2，1）39Guass-Jordan消去法形式上比Guass消去法簡單,求解無回代過程,但從工作量角度看前者大約需要O(),而后者需要量O(),比有回代的Guass消去法多O()工作量.40寫在最后成功的基礎在于好的學習習慣Thefoundationofsuccessliesingoodhabits41