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

《線(xiàn)性方程組AX=B的數(shù)值解法(j).ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《線(xiàn)性方程組AX=B的數(shù)值解法(j).ppt（53頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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