計(jì)算方法課件第三章線性代數(shù)方程組的數(shù)值解法-

1、第三章 線性代數(shù)方程組的數(shù) 值解法 3.1 引言3.2 解線性方程組的消去法3.3 解線性方程組的矩陣分解法3.4 解線性方程組的迭代法第三章 線性代數(shù)方程組的數(shù)3.1 引言3.1 引言 給定一個(gè)線性方程組求解向量 x。 3.1 引言 給定一個(gè)線性方程組求解向量 x。 第一類是直接法。即按求精確解的方法運(yùn)算求解。第二類是迭代法。其思想是首先把線性方程組(3-1)等價(jià)變換為如下形式的方程組：數(shù)值解法主要有兩大類：然后構(gòu)造迭代格式這稱為一階定常迭代格式，M 稱為迭代矩陣。 第一類是直接法。即按求精確解的方法運(yùn)算求解。數(shù)值解法主要有兩 3.2 解線性方程組的消去法 3.2.1 高斯消去法與高斯若當(dāng)消

2、去法 例1 第一步：先將方程（1）中未知數(shù) 的系數(shù)2除（1）的兩邊，得到下列方程組： 3.2 解線性方程組的消去法 3.2.1 高斯消 再將第二個(gè)方程減去第一個(gè)方程的4倍，第三個(gè)方程減去第一個(gè)方程的2倍。 第二步：將方程 中第二個(gè)方程的兩邊除以 的系數(shù)4 再將第二個(gè)方程減去第一個(gè)方程的4倍，第三個(gè)方程 將第三個(gè)方程減去第二個(gè)方程： 第三步：為了一致期見，將第三個(gè)方程中的 系數(shù)變?yōu)?，除以 將第三個(gè)方程減去第二個(gè)方程： 第三步：為了一致期見， 我們來分析一下上述過程：整個(gè)過程分兩大步。一是用逐次消去未知數(shù)的方法，把原來的方程組化為與其等價(jià)的三角形方程組。用矩陣的觀點(diǎn)來看，就是用初等變換的方法將方

3、程組的系數(shù)矩陣進(jìn)行初等變換，即 我們來分析一下上述過程：整個(gè)過程分兩大步。 這樣就將系數(shù)陣化為單位三角陣，這個(gè)過程稱為“消元過程”。二是解三角形方程組，稱為“回代過程”，整個(gè)過程稱為“有回代過程的順序消元法”。 下面我們來討論一般的解n階方程組的高斯消去法，且就矩陣的形式來介紹這種新的過程： 這樣就將系數(shù)陣化為單位三角陣，這個(gè)過程稱為計(jì)算方法課件第三章線性代數(shù)方程組的數(shù)值解法-計(jì)算方法課件第三章線性代數(shù)方程組的數(shù)值解法-計(jì)算方法課件第三章線性代數(shù)方程組的數(shù)值解法- 一般地，第k步：即將矩陣變?yōu)槿缦?一般地，第k步：即將矩陣變?yōu)槿缦掠?jì)算方法課件第三章線性代數(shù)方程組的數(shù)值解法-計(jì)算方法課件第三章線

4、性代數(shù)方程組的數(shù)值解法- 第n步：得到： 經(jīng)過上述n步過程后，原系數(shù)矩陣A變?yōu)橐粋€(gè)單位上三角矩陣，即原方程組化為一個(gè)和它完全等價(jià)的三角形方程組，即 第n步：得到： 經(jīng)過上述n步過程后，原系數(shù)矩陣A變?yōu)橐桓咚瓜シǎ?（1）消元過程： 對(duì)k=1,2, , n 依次計(jì)算 (2) 回代過程： 高斯消去法： (2) 回代過程： 例3.1 試用高斯消去法求解線性方程組 消元過程為 解 例3.1 試用高斯消去法求解線性方程組 消元過程為 解即把原方程組等價(jià)約化為 據(jù)之回代解得即把原方程組等價(jià)約化為 據(jù)之回代解得為了避免回代的計(jì)算，我們可在消元過程中直接把系數(shù)矩陣A約化為單位矩陣I，從而得到解，即 相應(yīng)地，

5、計(jì)算公式可表述為： 從而得到解這一無回代的消去法稱為高斯-若當(dāng)（Jordan）消去法 為了避免回代的計(jì)算，我們可在消元過程中直接把系數(shù)矩陣A約化為二、高斯-若當(dāng)（Jordan）消去法 解二、高斯-若當(dāng)（Jordan）消去法 解計(jì)算方法課件第三章線性代數(shù)方程組的數(shù)值解法-例 2 試用高斯-若當(dāng)消去法求解例3.1的線性方程組。 因?yàn)?解例 2 試用高斯-若當(dāng)消去法求解例3.1的線性方程組。 因一般公式： 高斯約當(dāng)消去法是一個(gè)具有消去過程而無回代過程的算法。 以上兩種消去法都是沿系數(shù)矩陣的主對(duì)角線元素進(jìn)行的，即第k次消元是用經(jīng)過前k-1次消元之后的系數(shù)陣位于（k,k)位置的元素作除數(shù)，這時(shí)的(k,k

6、)位置上的元素可能為0或非常小，這就可能引起過程中斷或溢出停機(jī)。因此：一般公式： 高斯約當(dāng)消去法是一個(gè)具有消去過程而無回代計(jì)算方法課件第三章線性代數(shù)方程組的數(shù)值解法- 3.2.2 消去法的可行性和計(jì)算工作量 定理 3.1 如果的各階順序主子式均不為零，即有即消去法可行。推論 若系數(shù)矩陣嚴(yán)格對(duì)角占優(yōu)，即有 3.2.2 消去法的可行性和計(jì)算工作量 定理 3.1 定理 3.2 求解 n 階線性方程組 (3-1) 的高斯消去法的乘除工作量約為 ，加減工作量約為 ；而高斯-若當(dāng)消去法的乘除工作量約為 ，加減工作量約為 。由式（3-4）知，高斯消去法在消元過程中第k步的工作量為所以，消元過程的總工作量為證

7、定理 3.2 求解 n 階線性方程組 (3-1) 的高斯消回代過程中的乘除和加減工作量均為總工作量為 類似可得，高斯-若當(dāng)消去法的工作量為 回代過程中的乘除和加減工作量均為總工作量為 類似可得，高斯-例 3.3 試用高斯-若當(dāng)消去法求解如下矩陣方程因?yàn)?解例 3.3 試用高斯-若當(dāng)消去法求解如下矩陣方程因?yàn)?解 $2 選主元素的消去法 主元素的選取通常采用兩種方法，一種是全主元消去法,另一種是列主元消去法。 下面以例介紹選主元的算法思想例 3.4 試用選主元消去法解線性方程組 $2 選主元素的消去法 主元素的選取通常采用兩種方法，（1）用全主元高斯消去法 回代解出： 還原得： 解（1）用全主元

8、高斯消去法 回代解出： 還原得： 解 （2）用全主元高斯-若當(dāng)消去法 故得解為 （3）用列主元高斯消去法 回代解得 （2）用全主元高斯-若當(dāng)消去法 故得解為 （3） 3.3 解線性方程組的矩陣分解法 一、 非對(duì)稱矩陣的三角分解法 對(duì)于給定的線性方程組 矩陣分解法的基本思想是： （1） 分解可逆下三角矩陣可逆上三角矩陣 3.3 解線性方程組的矩陣分解法 一、 非對(duì)稱矩陣的計(jì)算方法課件第三章線性代數(shù)方程組的數(shù)值解法-顯見S是一個(gè)可逆的下三角陣解兩個(gè)三角形方程組。顯見S是一個(gè)可逆的下三角陣解兩個(gè)三角形方程組。Crout分解（以四階為例） Crout分解（以四階為例） 計(jì)算方法課件第三章線性代數(shù)方程組

9、的數(shù)值解法-計(jì)算方法課件第三章線性代數(shù)方程組的數(shù)值解法-2.利用三角分解法解方程組 2.利用三角分解法解方程組 計(jì)算方法課件第三章線性代數(shù)方程組的數(shù)值解法-計(jì)算方法課件第三章線性代數(shù)方程組的數(shù)值解法- 例1. 試用克洛特分解法解線性方程組 例1. 試用克洛特分解法解線性方程組 計(jì)算方法課件第三章線性代數(shù)方程組的數(shù)值解法- 例2 試用克洛特分解法解線性方程組 解 例2 試用克洛特分解法解線性方程組 解計(jì)算方法課件第三章線性代數(shù)方程組的數(shù)值解法- 3.3.2 解三對(duì)角型線性方程組的追趕法 1.用LU分解矩陣A 3.3.2 解三對(duì)角型線性方程組的追趕法 1.用LU計(jì)算方法課件第三章線性代數(shù)方程組的數(shù)

10、值解法-計(jì)算方法課件第三章線性代數(shù)方程組的數(shù)值解法- 3.3.3 對(duì)稱正定矩陣的三角分解 定義 3.1 若n 階方矩陣 A 具有性質(zhì) 且對(duì)任何n 維向量 成立 ，則稱 A 為對(duì)稱正定矩陣。 定理3.4 若A 為對(duì)稱正定矩陣，則 (1) A的k階順序主子式 (2)有且僅有一個(gè)單位下三角矩陣L和對(duì)角矩陣D 使得 （3-16）這稱為矩陣的喬里斯基（Cholesky）分解。 (3)有且僅有一個(gè)下三角矩陣 ，使 （3-17）這稱為分解矩陣的平方根法。 3.3.3 對(duì)稱正定矩陣的三角分解 定義 3.1 若 （1）首先由A 對(duì)稱正定知 且對(duì)任何k維非零向量 故 為 k 階對(duì)稱正定矩陣，所以 由惟一性得 證

11、（1）首先由A 對(duì)稱正定知 且對(duì)任何k維非零向量 以下推導(dǎo)平方根法和喬里斯基分解法的計(jì)算公式。 由此可建立平方根法的遞推計(jì)算公式如下： 以下推導(dǎo)平方根法和喬里斯基分解法的計(jì)算公式。 由此可建立平方類似地，由 得 從而可建立喬里斯基分解法的遞推計(jì)算公式為 對(duì)于 依次計(jì)算類似地，由 例 3.7 試分別用平方根法和喬里斯基分解法分解矩陣 (1) 解例 3.7 試分別用平方根法和喬里斯基分解法分解矩陣 計(jì)算方法課件第三章線性代數(shù)方程組的數(shù)值解法-把平方根法應(yīng)用于解方程組，則把 Ax=b 化為等價(jià)方程 相應(yīng)的求解公式為 把平方根法應(yīng)用于解方程組，則把 Ax=b 化為等價(jià)方程 相應(yīng)把喬里斯基分解法應(yīng)用于解

12、方程組，則 Ax=b 化為等價(jià)方程 相應(yīng)的求解公式為 把喬里斯基分解法應(yīng)用于解方程組，則 Ax=b 化為等價(jià)方程 例3.8 試用平方根法求解對(duì)稱線性方程組 解由此，可先由上三角形線性方程組 例3.8 試用平方根法求解對(duì)稱線性方程組 解由此，可先由上再由下三角形線性方程組 再由下三角形線性方程組 例3.9 試用喬里斯基分解法解線性方程組 解 例3.9 試用喬里斯基分解法解線性方程組 解計(jì)算方法課件第三章線性代數(shù)方程組的數(shù)值解法- 3.4 解線性方程組的迭代法 3.4.1 雅可比迭代法與高斯-塞德爾迭代法 對(duì) （3-23）以分量表示即 約化便得 雅可比（Jacobi）迭代 從而可建立迭代格式 3.

13、4 解線性方程組的迭代法 3.4.1 雅可比迭代則雅可比迭代格式（3-24）可用矩陣表示為 MJf J則雅可比迭代格式（3-24）可用矩陣表示為 MJf J用矩陣表示為 對(duì)雅可比迭代格式修改得高斯-塞德爾（G-S）迭代 f G-SMG-S用矩陣表示為 對(duì)雅可比迭代格式修改得高斯-塞德爾（G-S）迭例3.10 分別用雅可比迭代法和高斯-塞德爾迭代法求解 線性方程組 解高斯-塞德爾迭代雅可比迭代令 取四位小數(shù)迭代計(jì)算 由雅可比迭代得 由高斯-塞德爾迭代得 相應(yīng)的迭代公式為例3.10 分別用雅可比迭代法和高斯-塞德爾迭代法求解解高 3.4.2 迭代法的收斂性 定義 3.2 設(shè) n 階線性方程組 的精

14、確解為 x* 相應(yīng)的一階定常迭代格式為 如果其迭代解 收斂于精確解 ，即 則稱迭代格式（3-26）收斂 命題 3.2 記 的充分必要條件為 3.4.2 迭代法的收斂性 定義 3.2 設(shè) n 階定理 3.5 若一階定常迭代格式（3-26）的迭代矩陣 滿足條件 則該迭代格式對(duì)任何初始向量 均收斂。 證 定理得證。 相減得 定理 3.5 若一階定常迭代格式（3-26）的迭代矩陣則該則該迭代格式對(duì)任何初始向量 均收斂。 定理 3.6 若一階定常迭代格式（3-26）的迭代矩陣 滿足條件 定理 3.7 若雅可比迭代法的迭代矩陣 滿足條件（3-28）或（3-29），則雅可比迭代法與相應(yīng)的高斯-塞德爾迭代法對(duì)任何初始向量 均收斂。 推論 如果線性代數(shù)方程組 A x = b的系數(shù)矩陣 A 為嚴(yán)格對(duì)角占優(yōu)矩陣，即則相應(yīng)的雅可比迭代法與高斯-塞德爾迭代法對(duì)任何初始向量 均收斂。 則該迭代格式對(duì)任何初始向量 均收斂。 定理 3.8 一階定常迭代格式 對(duì)任何初始向量均收斂的充分必要條件為其迭代矩陣的譜半徑小于1，即 這里 為 M 的特征值 定理