線性方程組AX=B的數(shù)值解法(j).ppt

2020 2 13 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 第3章線性方程組AX B的數(shù)值解法 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 引言 在自然科學(xué)和工程技術(shù)中很多問題的解決常常歸結(jié)為解線性代數(shù)方程組 例如電學(xué)中的網(wǎng)絡(luò)問題 船體數(shù)學(xué)放樣中建立三次樣條函數(shù)問題 用最小二乘法求實驗數(shù)據(jù)的曲線擬合問題 解非線性方程組問題 用差分法或者有限元法解常微分方程 偏微分方程邊值問題等都導(dǎo)致求解線性方程組 而且后面幾種情況常常歸結(jié)為求解大型線性方程組 線性代數(shù)方面的計算方法就是研究求解線性方程組的一些數(shù)值解法與研究計算矩陣的特征值及特征向量的數(shù)值方法 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 線性方程組求解問題 考慮線性方程組Ax b其中A是一個 n n 的非奇異矩陣 x是要求解的n維未知向量 b是n維常向量 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 線性方程組的解的存在性和唯一性 定理3 4設(shè)A是N N方陣 下列命題等價 給定任意N 1矩陣B 線性方程組AX B有唯一解矩陣A是非奇異的 即A 1存在 方程組AX 0有唯一解X 0det A 0 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 線性方程組的解 最常見的求線性方程組Ax b的解的方法是在方程組兩側(cè)同乘以矩陣A的逆Gram法則 Ax b 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 線性方程組的解 續(xù)1 求逆運(yùn)算和行列式計算由于運(yùn)算量大 實際求解過程中基本不使用 僅作為理論上的定性討論克萊姆法則在理論上有著重大意義 但在實際應(yīng)用中存在很大的困難 在線性代數(shù)中 為解決這一困難給出了高斯消元法還有三角分解法和迭代求解法 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 解法分類 關(guān)于線性方程組的數(shù)值解法一般有兩類直接法 若在計算過程中沒有舍入誤差 經(jīng)過有限步算術(shù)運(yùn)算 可求得方程組的精確解的方法迭代法 用某種極限過程去逐步逼近線性方程組精確解的方法迭代法具有占存儲單元少 程序設(shè)計簡單 原始系數(shù)矩陣在迭代過程中不變等優(yōu)點(diǎn) 但存在收斂性及收斂速度等問題 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 3上三角線性方程組 定義3 2N N矩陣A aij 中的元素滿足對所有i j 有aij 0 則稱矩陣A為上三角矩陣 如果A中的元素滿足對所有i j 有aij 0 則稱矩陣A為下三角矩陣 定理3 5 回代 設(shè)AX B是上三角線性方程組 如果akk 0 其中k 1 2 N 則該方程組存在唯一解 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 3上三角線性方程組 續(xù)1 定理3 6如果N N矩陣A aij 是上三角矩陣或下三角矩陣 則 條件akk 0很重要 因為回代算法中包含對akk的除法 如果條件不滿足 則可能無解或有無窮解 聯(lián)系定理3 4 可知要條件akk 0成立才能保證方程組存在唯一解 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 3上三角線性方程組 續(xù)2 求解上三角線性方程組的回代算法 最后 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 上三角線性方程組的求解 基本算法 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 上三角線性方程組的求解 續(xù)1 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 4高斯消去法和選主元 求解有N個方程和N個未知數(shù)的一般方程組AX B的一般做法 構(gòu)造一個等價的上三角方程組UX Y 并利用回代法求解如果兩個N N線性方程組的解相同 則稱二者等價對一個給定方程組進(jìn)行初等變換 不會改變它的解 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 4高斯消去法和選主元 續(xù)1 考慮一個簡單的例子 求解第二個方程 得 第二個方程減去第一個方程除以3再乘以4得到的新方程 得到新的方程組 回代到第一個方程 得 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 4高斯消去法和選主元 續(xù)2 考慮包含n個未知數(shù)的方程組 or 作如下行變換之后方程組的解向量x不變對調(diào)方程組的兩行用非零常數(shù)乘以方程組的某一行將方程組的某一行乘以一個非零常數(shù) 再加到另一行上 通過對增廣矩陣 A B 進(jìn)行如上的行變換求解 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 4高斯消去法和選主元 續(xù)3 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 4高斯消去法和選主元 續(xù)4 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 4高斯消去法和選主元 續(xù)5 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 4高斯消去法和選主元 續(xù)6 利用3 3節(jié)的回代法求解上述上三角方程組 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 4高斯消去法和選主元 續(xù)7 消去過程 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 4高斯消去法和選主元 續(xù)8 回代過程 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 4高斯消去法和選主元 續(xù)9 上述消去過程中 如果akk 0 則不能使用第k行消除第k列的元素 而需要將第k行與對角線下的某行進(jìn)行交換 以得到一個非零主元 如果不能找到非零主元 則線性方程組的系數(shù)矩陣是奇異的 因此線性方程組不存在唯一解選主元以避免 如果此主元非零 則不換行 如果此主元為零 則尋找第p行下滿足的第1行 將此行與第p行互換 使新主元非零 平凡選主元策略 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 4高斯消去法和選主元 續(xù)10 選主元以減少誤差 把元素中的最大絕對值移到主對角線上 例3 17和3 18 偏序選主元策略 akp max app app 1 aN 1p aNp 按比例偏序選主元 平衡 策略 sr max arp arp 1 arN 其中r p p 1 N 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 4高斯消去法和選主元 續(xù)11 病態(tài)問題 矩陣A中元素的微小變化引起解的很大變化 cond A 207 012 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 圖形解釋 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 4高斯消去法和選主元 續(xù)12 一個線性方程組稱為是病態(tài)的 如果其系數(shù)矩陣接近奇異且它的行列式接近0 矩陣條件數(shù)cond A A A 1 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 5三角分解法 A LU 下三角矩陣L的主對角線為1 上三角矩陣U的對角線元素非零 定義3 4如果非奇異矩陣A可表示為下三角矩陣L和上三角矩陣U的乘積 A LU 則A存在一個三角分解 A非奇異蘊(yùn)含著對所有的k有ukk 0 k 1 2 3 4 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 矩陣的LU分解 是否所有的非奇異矩陣A都能作LU分解呢 一個例子 N階方陣A有唯一LU分解的充要條件是A的各階順序主子式均不為零 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 5三角分解法 續(xù)1 利用前代 回代算法求解形如Lx b或Ux b的線性方程組是容易的 如果對一個給定的矩陣A 能夠找到一個下三角矩陣L和一個上三角矩陣U 使A LU 則求解線性方程組Ax b的問題可以分解成兩個簡單的問題 Ly bUx y 易見 Ax LU x L Ux Ly b 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 5三角分解法 續(xù)2 假設(shè)已有矩陣A 對A作LU分解 檢驗分解結(jié)果 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 5三角分解法 續(xù)3 構(gòu)造一系列乘數(shù)矩陣M1 M2 M3 M4 MN 1使得 MN 1 M4M3M2M1 A是上三角矩陣 把它重新記成U 對4 4矩陣A M1可取 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 5三角分解法 續(xù)4 M2可取 M3可取 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 5三角分解法 續(xù)5 則U M3M2M1 A是上三角形矩陣每個M矩陣都是下三角形矩陣如M2的逆為 注意到每個M矩陣的逆只是它自身下三角部分元素取相反數(shù)A M3M2M1 1U M1 1 M2 1 M3 1U定義L M1 1 M2 1 M3 1 則L就是一個對角元素全為1的下三角矩陣 因為所有的M矩陣的逆都是對角元素全為1的下三角矩陣 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 5三角分解法 續(xù)6 計算復(fù)雜性 高斯消去法與三角分解法的三角化過程是一樣的 都需要 次乘法和除法 次減法 求解LUX B又需要N2次乘法和除法 以及 N2 N 次減法 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 5三角分解法 續(xù)7 每一個M矩陣中都需要計算1 A i i 當(dāng)?shù)趇個對角元素為0或者很接近0時就沒法計算M 這時A的直接LU分解就沒法繼續(xù)進(jìn)行可以將第i行與它下面的某一行互換 該行的第i列元素非零帶選主元過程的LU分解 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 5三角分解法 續(xù)8 之前我們構(gòu)造了一系列的M矩陣使得是上三角矩陣現(xiàn)在我們構(gòu)造一系列的M矩陣和P矩陣使得是上三角矩陣 MN 1 M4M3M2M1 A MN 1PN 1 M4P4M3P3M2P2M1P1 A 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 6求解線性方程組的迭代法 考慮線性方程組 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 6求解線性方程組的迭代法 續(xù)1 高斯消去法 受限于舍入誤差和病態(tài)性迭代法 另一種求解線性方程組的方法給出初始估計值 通過迭代得到更好的解的近似值迭代法對求解大型線性方程組非常有效Jacobi 雅可比 和Gauss Seidel 高斯 賽德爾 方法 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 6求解線性方程組的迭代法 續(xù)2 將方程組改寫成每個方程的左邊只有一個未知數(shù)的形式 給出初始估計值和迭代規(guī)則 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 Jacobi迭代法 初始估計值 迭代一步后的結(jié)果 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 Jacobi迭代法 續(xù)1 k步迭代后的結(jié)果 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 Jacobi迭代法 續(xù)2 例 Jacobi迭代公式 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 Jacobi迭代法 續(xù)3 初始迭代值 20步迭代后 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 Jacobi迭代法 續(xù)4 迭代會不會收斂到方程組的解 迭代到何時會終止 終止的判斷條件是什么 兩個必須考慮的問題 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 6求解線性方程組的迭代法 續(xù)3 定義3 6設(shè)有N N維矩陣A 如果 其中k 1 2 N 則稱A具有嚴(yán)格對角優(yōu)勢 嚴(yán)格對角占優(yōu) 定理3 15 雅可比迭代 設(shè)矩陣A具有嚴(yán)格對角優(yōu)勢 則AX B有唯一解X P 利用雅可比迭代可產(chǎn)生一個向量序列 Pk 而且對于任意初始向量P0 向量序列都將收斂到P 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 6求解線性方程組的迭代法 續(xù)4 向量之間的距離可以用來判斷 Pk 是否收斂到P 因為兩個向量P x1 x2 xN 和Q y1 y2 yN 之間的歐幾里德距離 計算復(fù)雜 而1 范數(shù)具有度量的數(shù)學(xué)結(jié)構(gòu) 也適合作為一個一般化的 距離公式 而且根據(jù)線性代數(shù)的理論可知 如果兩個向量的 1范數(shù)接近 則它們的歐幾里德范數(shù) 2也接近 所以定義兩個N維向量的距離為 1范數(shù) 用來確定N維空間中的收斂性 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 6求解線性方程組的迭代法 續(xù)5 1 范數(shù) 滿足一般向量范數(shù)的性質(zhì) 定理3 16設(shè)X和Y是N維向量 c是一個標(biāo)量 則函數(shù) X 有如下性質(zhì) 正定性 X 0 X 0當(dāng)且僅當(dāng)X 0齊次性 cX c X 三角不等式 X Y X Y 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 Gauss Seidel迭代法 初始估計值 迭代一步后的結(jié)果 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 每一次迭代新產(chǎn)生的被認(rèn)為是比更好的xj的近似值 所以在計算xj 1時用來替換是合理的 Gauss Seidel迭代法 續(xù)1 k步迭代后的結(jié)果 矩陣A具有嚴(yán)格對角優(yōu)勢時 高斯 賽德爾迭代收斂 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 Gauss Seidel迭代法 續(xù)2 1步G S迭代之后 迭代初始值 例 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 Gauss Seidel迭代法 續(xù)3 2步迭代之后 9步迭代之后 1步迭代之后 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 3 6求解線性方程組的迭代法 續(xù)6 雅可比迭代 高斯 賽德爾迭代 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲 2020 2 13 J 迭代和G S迭代的比較 一般來說 用J 迭代 G S迭代都收斂的問題 用G S迭代收斂更快J 迭代保留上一步所有點(diǎn)的值 花費(fèi)存儲空間 適合并行運(yùn)算 節(jié)省計算時間G 迭代每計算出一個新點(diǎn)都用于下一步的計算中 不須保留上一步所有點(diǎn)的值 節(jié)省存儲空間 但只能串行計算