LU分解教學(xué)講解課件

LU分解法的與特殊方程組的解法LU分解法的與特殊方程組的解法LU分解法的與特殊方程組的解法LU分解法的與特殊方程組的解法假定我們能把矩陣A寫成下列兩個(gè)矩陣相乘的形式：A=LU其中L為下三角矩陣，U為上三角矩陣。這樣我們可以把線性方程組Ax=b寫成

Ax=（LU)x=L(Ux)=bLy=b令Ux=y,則原線性方程組Ax=bUx=y于是可首先求解向量y使Ly=b然后求解Ux=y,從而求解線性方程組Ax=b的目的.

LU分解法的基本思想假定我們能把矩陣A寫成下列兩個(gè)矩陣相乘的形式：A=LU假定我們能把矩陣A寫成下列兩個(gè)矩陣相乘的形式：A=LU內(nèi)容:LU分解.關(guān)鍵詞:1.LU分解:將系數(shù)矩陣A轉(zhuǎn)變成等價(jià)兩個(gè)矩陣L和U的乘積,其中L和U分別是下三角和上三角矩陣,而且要求U的對角元素都是1.2.緊湊格式:由于可以把L和U兩個(gè)矩陣壓縮到一個(gè)數(shù)組中,而且還可以存儲(chǔ)在原來的系數(shù)矩陣A的數(shù)組中.這種LU分解常被稱為緊湊格式.內(nèi)容:LU分解.內(nèi)容:LU分解.內(nèi)容:LU分解.由LU=A及對L和U的要求可以得到分解的計(jì)算公式．根據(jù)下式(Doolittle分解)：1

l211

l31l321

………ln1ln2…

lnn-11

u11u12u13…u1nu22u23…u2n

…un-1nu(n-1)n

unn=…………aannLUn1an3…a11a12a13…a1na21a22

a23…a2na31a32

a33…

a3n

an2A………由LU=A及對L和U的要求可以得到分解的計(jì)算公式．根據(jù)下式(由LU=A及對L和U的要求可以得到分解的計(jì)算公式．根據(jù)下式(第j個(gè)分量第i個(gè)分量第j個(gè)分量第i個(gè)分量第j個(gè)分量第i個(gè)分量第j個(gè)分量第i個(gè)分量根據(jù)矩陣乘法及相等的定義,有

得公式u1j=a1jj=1,2,…,nli1=ai1/u11i=2,3,…,n根據(jù)矩陣乘法及相等的定義,有得公式u1j=a1j根據(jù)矩陣乘法及相等的定義,有得公式u1j=a1jLU分解教學(xué)講解課件LU分解教學(xué)講解課件在計(jì)算機(jī)程序中常常用這種方法解線性代數(shù)方程組。它的優(yōu)點(diǎn)是存儲(chǔ)量很省。L和U中的三角零元素都不必存儲(chǔ)，就是U的對角元素也因?yàn)槎际?沒有必要再記錄在程序中，這樣只用一個(gè)n階方陣就可以把L和U貯存起來。即：下三角（包括對角元）存儲(chǔ)L各元素而上三角存儲(chǔ)U的元素。再考察公式S會(huì)發(fā)現(xiàn)A中任一元素aij只在計(jì)算lij（j<=i）和uij（j>i)中用到一次以后就不再出現(xiàn)了，因而完全可以利用原始數(shù)組A的單元，一個(gè)個(gè)逐次貯存L或U中的相應(yīng)元素，即：

a11

a12a13…a1nu11u12u13…u1na21a22a23…a2nl21u22u23…u2na31a32a33…a3nl31l32u33…u3n

an1an2an3…annln1ln2ln3…unn………...…………......(1)(3)(5)(2n-1)(2)(4)(6)(2n)在計(jì)算機(jī)程序中常常用這種方法解線性代數(shù)方程組。………...…在計(jì)算機(jī)程序中常常用這種方法解線性代數(shù)方程組?！?..…采用LU分解有如下特點(diǎn)：（1）LU分解與右端向量無關(guān)。先分解，后回代。一般說來，分解的運(yùn)算次數(shù)正比于n回代求解正比與n。求遇到多次回代時(shí)，分解的工作不必重新做。這樣節(jié)省計(jì)算時(shí)間。（2）分解按步進(jìn)行，前邊分解得到的信息為后邊所用。（3）[A]陣的存儲(chǔ)空間可利用，節(jié)省存儲(chǔ)。32采用LU分解有如下特點(diǎn)：32采用LU分解有如下特點(diǎn)：32采用LU分解有如下特點(diǎn)：32特殊方程組的解法1.追趕法2.LDLT分解法特殊方程組的解法1.追趕法特殊方程組的解法1.追趕法特殊方程組的解法1.追1.追趕法追趕法與稀疏線性方程組

追趕法仍然保持LU分解特性,它是一種特殊的LU分解。充分利用了系數(shù)矩陣的特點(diǎn)，而且使之分解更簡單,得到對三對角線性方程組的快速解法。因三對角矩陣的非零元素呈“帶狀”，我們也因此將它叫做帶狀矩陣。1.追趕法追趕法與稀疏線性方程組1.追趕法追趕法與稀疏線性方程組1.追趕法追趕法與稀疏線性方三對角線性方程組：三對角線性方程組：三對角線性方程組：三對角線性方程組：設(shè)有方程組Ax=d，其中A為三對角矩陣。假設(shè)系數(shù)矩陣A滿足條件：對A作Crout分解形式為：設(shè)有方程組Ax=d，其中A為三對角矩陣。設(shè)有方程組Ax=d，其中A為三對角矩陣。設(shè)有方程組Ax=d，第i個(gè)分量第j個(gè)分量第i個(gè)分量第j個(gè)分量第i個(gè)分量第j個(gè)分量第i個(gè)分量第j個(gè)分量追趕法計(jì)算公式追趕法計(jì)算公式追趕法計(jì)算公式追趕法計(jì)算公式LU分解教學(xué)講解課件LU分解教學(xué)講解課件定理

如果上帶寬為q，下帶寬為p的n階帶狀矩陣A有Doolittle分解。A=LU，則L是下帶寬為p的單位下三角矩陣，U是上帶寬為q的上三角矩陣。

定理如果上帶寬為q，下帶寬為p的n階帶狀矩陣A有Dooli定理如果上帶寬為q，下帶寬為p的n階帶狀矩陣A有DooliLU分解教學(xué)講解課件LU分解教學(xué)講解課件下面舉實(shí)例用追趕法來解三對角方程組。下面舉實(shí)例用追趕法來解三對角方程組。下面舉實(shí)例用追趕法來解三對角方程組。下面舉實(shí)例用追趕法來解三LU分解教學(xué)講解課件LU分解教學(xué)講解課件實(shí)際問題中，當(dāng)求解方程組的系數(shù)矩陣是對稱矩陣時(shí)，則用下面介紹的LDLT分解法可以簡化程序設(shè)計(jì)并減少計(jì)算量.

從定理可知,當(dāng)矩陣A的各階順序主子式不為零時(shí),A有唯一的Doolittle分解A=LU.此時(shí),當(dāng)然有,所以矩陣U的對角線元素uii

0,(i=1,2,,n),將矩陣U的每行依此提出uii2.LDLT分解法實(shí)際問題中，當(dāng)求解方程組的系數(shù)矩陣是對稱矩陣時(shí)，則用下面介紹實(shí)際問題中，當(dāng)求解方程組的系數(shù)矩陣是對稱矩陣時(shí)，則用下面介紹由A=AT，得由分解的唯一性有，即，于是可得下面的結(jié)論。

由A=AT，得由A=AT，得由A=AT，得定理3：若對稱矩陣A各階順序主子式不為零時(shí),

則

A可以唯一分解為A=LDLT

，這里L(fēng)T為L的轉(zhuǎn)置矩陣。當(dāng)A有LDLT分解時(shí)，利用矩陣運(yùn)算法則及相等原理易得計(jì)算ljk及dk的公式為定理3：若對稱矩陣A各階順序主子式不為零時(shí),則

A可以唯一定理3：若對稱矩陣A各階順序主子式不為零時(shí),則

A可以唯一

k=1,2,,n;j=k+1,k+2,,n為減少乘法次數(shù)，引入輔助量ujk=ljkdk,則上面公式可寫成k=1,2,,n;j=k+1,k+2,,n為減少乘法k=1,2,,n;j=k+1,k+2,,n為減少乘法LU分解教學(xué)講解課件LU分解教學(xué)講解課件LU分解教學(xué)講解課件LU分解教學(xué)講解課件LU分解教學(xué)講解課件LU分解教學(xué)講解課件平方根法設(shè)A為正定矩陣，則它的各階順序主子式均為正。由前面的定理知，A必有唯一的LDLT分解式

A=LDLT

在解對稱正定線性方程組時(shí)，系數(shù)矩陣A的LDLT分解中D又可分解為D=D1/2D1/2，這里D1/2也是對角矩陣平方根法平方根法平方根法LU分解法的與特殊方程組的解法LU分解法的與特殊方程組的解法LU分解法的與特殊方程組的解法LU分解法的與特殊方程組的解法假定我們能把矩陣A寫成下列兩個(gè)矩陣相乘的形式：A=LU其中L為下三角矩陣，U為上三角矩陣。這樣我們可以把線性方程組Ax=b寫成

Ax=（LU)x=L(Ux)=bLy=b令Ux=y,則原線性方程組Ax=bUx=y于是可首先求解向量y使Ly=b然后求解Ux=y,從而求解線性方程組Ax=b的目的.

LU分解法的基本思想假定我們能把矩陣A寫成下列兩個(gè)矩陣相乘的形式：A=LU假定我們能把矩陣A寫成下列兩個(gè)矩陣相乘的形式：A=LU內(nèi)容:LU分解.關(guān)鍵詞:1.LU分解:將系數(shù)矩陣A轉(zhuǎn)變成等價(jià)兩個(gè)矩陣L和U的乘積,其中L和U分別是下三角和上三角矩陣,而且要求U的對角元素都是1.2.緊湊格式:由于可以把L和U兩個(gè)矩陣壓縮到一個(gè)數(shù)組中,而且還可以存儲(chǔ)在原來的系數(shù)矩陣A的數(shù)組中.這種LU分解常被稱為緊湊格式.內(nèi)容:LU分解.內(nèi)容:LU分解.內(nèi)容:LU分解.由LU=A及對L和U的要求可以得到分解的計(jì)算公式．根據(jù)下式(Doolittle分解)：1

l211

l31l321

………ln1ln2…

lnn-11

u11u12u13…u1nu22u23…u2n

…un-1nu(n-1)n

unn=…………aannLUn1an3…a11a12a13…a1na21a22

a23…a2na31a32

a33…

a3n

an2A………由LU=A及對L和U的要求可以得到分解的計(jì)算公式．根據(jù)下式(由LU=A及對L和U的要求可以得到分解的計(jì)算公式．根據(jù)下式(第j個(gè)分量第i個(gè)分量第j個(gè)分量第i個(gè)分量第j個(gè)分量第i個(gè)分量第j個(gè)分量第i個(gè)分量根據(jù)矩陣乘法及相等的定義,有

得公式u1j=a1jj=1,2,…,nli1=ai1/u11i=2,3,…,n根據(jù)矩陣乘法及相等的定義,有得公式u1j=a1j根據(jù)矩陣乘法及相等的定義,有得公式u1j=a1jLU分解教學(xué)講解課件LU分解教學(xué)講解課件在計(jì)算機(jī)程序中常常用這種方法解線性代數(shù)方程組。它的優(yōu)點(diǎn)是存儲(chǔ)量很省。L和U中的三角零元素都不必存儲(chǔ)，就是U的對角元素也因?yàn)槎际?沒有必要再記錄在程序中，這樣只用一個(gè)n階方陣就可以把L和U貯存起來。即：下三角（包括對角元）存儲(chǔ)L各元素而上三角存儲(chǔ)U的元素。再考察公式S會(huì)發(fā)現(xiàn)A中任一元素aij只在計(jì)算lij（j<=i）和uij（j>i)中用到一次以后就不再出現(xiàn)了，因而完全可以利用原始數(shù)組A的單元，一個(gè)個(gè)逐次貯存L或U中的相應(yīng)元素，即：

a11

a12a13…a1nu11u12u13…u1na21a22a23…a2nl21u22u23…u2na31a32a33…a3nl31l32u33…u3n

an1an2an3…annln1ln2ln3…unn………...…………......(1)(3)(5)(2n-1)(2)(4)(6)(2n)在計(jì)算機(jī)程序中常常用這種方法解線性代數(shù)方程組。………...…在計(jì)算機(jī)程序中常常用這種方法解線性代數(shù)方程組。………...…采用LU分解有如下特點(diǎn)：（1）LU分解與右端向量無關(guān)。先分解，后回代。一般說來，分解的運(yùn)算次數(shù)正比于n回代求解正比與n。求遇到多次回代時(shí)，分解的工作不必重新做。這樣節(jié)省計(jì)算時(shí)間。（2）分解按步進(jìn)行，前邊分解得到的信息為后邊所用。（3）[A]陣的存儲(chǔ)空間可利用，節(jié)省存儲(chǔ)。32采用LU分解有如下特點(diǎn)：32采用LU分解有如下特點(diǎn)：32采用LU分解有如下特點(diǎn)：32特殊方程組的解法1.追趕法2.LDLT分解法特殊方程組的解法1.追趕法特殊方程組的解法1.追趕法特殊方程組的解法1.追1.追趕法追趕法與稀疏線性方程組

追趕法仍然保持LU分解特性,它是一種特殊的LU分解。充分利用了系數(shù)矩陣的特點(diǎn)，而且使之分解更簡單,得到對三對角線性方程組的快速解法。因三對角矩陣的非零元素呈“帶狀”，我們也因此將它叫做帶狀矩陣。1.追趕法追趕法與稀疏線性方程組1.追趕法追趕法與稀疏線性方程組1.追趕法追趕法與稀疏線性方三對角線性方程組：三對角線性方程組：三對角線性方程組：三對角線性方程組：設(shè)有方程組Ax=d，其中A為三對角矩陣。假設(shè)系數(shù)矩陣A滿足條件：對A作Crout分解形式為：設(shè)有方程組Ax=d，其中A為三對角矩陣。設(shè)有方程組Ax=d，其中A為三對角矩陣。設(shè)有方程組Ax=d，第i個(gè)分量第j個(gè)分量第i個(gè)分量第j個(gè)分量第i個(gè)分量第j個(gè)分量第i個(gè)分量第j個(gè)分量追趕法計(jì)算公式追趕法計(jì)算公式追趕法計(jì)算公式追趕法計(jì)算公式LU分解教學(xué)講解課件LU分解教學(xué)講解課件定理

如果上帶寬為q，下帶寬為p的n階帶狀矩陣A有Doolittle分解。A=LU，則L是下帶寬為p的單位下三角矩陣，U是上帶寬為q的上三角矩陣。

定理如果上帶寬為q，下帶寬為p的n階帶狀矩陣A有Dooli定理如果上帶寬為q，下帶寬為p的n階帶狀矩陣A有DooliLU分解教學(xué)講解課件LU分解教學(xué)講解課件下面舉實(shí)例用追趕法來解三對角方程組。下面舉實(shí)例用追趕法來解三對角方程組。下面舉實(shí)例用追趕法來解三對角方程組。下面舉實(shí)例用追趕法來解三LU分解教學(xué)講解課件LU分解教學(xué)講解課件實(shí)際問題中，當(dāng)求解方程組的系數(shù)矩