研_第2章 线性方程组的直接解法

-1-第二章线性方程组的直接解法§3灵敏度分析§2正交三角分解法§1三角分解法-2-快速、高效地求解线性方程组是数值线性代数研究中的核心问题，也是目前科学计算中的重要研究课题之一。各种各样的科学和工程问题，往往最终都要归结为求解一个线性方程组。线性方程组的数值解法有：直接法和迭代法。直接法：在假定没有舍入误差的情况下，经过有限次运算可以求得方程组的精确解；迭代法：从一个初始向量出发，按照一定的迭代格式，构造出一个趋向于真解的无穷序列。-3-解xxxxxxxxx12312312374511202求解Step1:消元2117(,)451111210AAb21170333002632532rrStep2:回代517222211703330213120.5rrrr一高斯消去法一个例子x36/(2)3x2(333)/32()/x17131221§2.1三角分解法-4-nnnnnnnnnnnnnaxaxaxaaxaxaxaaxaxaxa11112211,121122222,11122,1求解方程：1计算机上所用的公式下面研究它的计算规律：-5-Step1：0011112iilaain()()/(,...,)令2in,...,iirlr11a(0)110假设，kknnkknnkkkkkkknknkkkkkaaaaaaaaaaaaAaaaaaaaaaa(0)(0)(0)(0)(0)(0)111211,111,1(0)(0)(0)(0)(0)(0)212222,122,1(0)(0)(0)(0)(0)(0)(0)12,1,1(0)(0)(0)1,11,21,.......................................记kknknnnnknknnnnaaaaaaaa(0)(0)(0)1,11,1,1(0)(0)(0)(0)(0)(0)12,1,1...........................kknnkknnkkkkkknknkkkkkknkaaaaaaaaaaaaaaaaaaaaa(0)(0)(0)(0)(0)(0)111211,(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(111,12222,122,12,1)(1)(1)1,11,21,1,11,.......................................00...0nnnknknnnnaaaaa(1)(1)(1)(1,12,1,11)(1)(1)....................0....1)消元A(0)-6-1k假设第步消元后kknnkknnkkkkkkkkkknknkkkkkkkaaaaaaaaaaaAaaaaaaa(0)(0)(0)(0)(0)(0)111211,111,1(1)(1)(1)(1)(1)2222,122,1(1)(1)(1)(1)(1),1,1(1)(1)1,1,1..............................00000...............kknknkkkknknknnnnaaaaa(1)(1)1,1,1(1)(1)(1)(1),1,1.........00.....................Stepk：1ikn,...,iikkrlrkkka(1)0若，kkikikkklaa(1)(1)/计算ikn(1,...,)kkkijijikkjaala()(1)(1)以及iknjkn(1...;1,...,1),,kA(1)()kAkknnkknnkkkkkkkkknknkknkkknkkaaaaaaaaaaaaaaaaaa(0)(0)(0)(0)(0)(0)111211,111,1(1)(1)(1)(1)(1)2222,122,1(1)(1)(1)(1),1,11,11,1,1()()(.................................000000...............nknnnnkkkaaa,1)()()(),1..........................00...0.-7-Stepn-1：kknnkknnnkkkkkkkkknknkkkkknknaaaaaaaaaaaAaaaaaaa(0)(0)(0)(0)(0)(0)111211,111,1(1)(1)(1)(1)(1)2222,122,1(1)(1)(1)(1)(1),1,1()()1,11,1,....................................00.0...0.0....0knnnnnnaa()1(1)(1),1...........................0.00..0A消元结束，化为上三角矩阵：1210kkkna,,...,，ikn1,...,ikikikkkalaajkn1,...,1ijikkjijaaaa在实际编程中，为了节省内存，不引入新变量，消元过程记为：-8-消元束后，增广矩阵化为如下“形式”：kknnkknnkkkkkkkkknknkkkkkkkkkkaaaaaaaalllaaaaaalaalla(0)(0)(0)(0)(0)(0)111211,111,1(1)(1)(1)(1)(1)2222,122,1(1)(1)(1)(1),1,1()1,21121,11.2111,..........................................nnnknkknknnnnnknnllllaaa()(),1,1(1)(1),1211,..............................nnnnnnnnkkkkknkjjkkjkxaaxaaxakn(1)1,1(1)(1)(1),11/()/(1,,1)1(0)(0)(0)(0)(0)111211,11(1)(1)(1)(1)2222,12(1)(1)(1),1()21121,11.21,()1,1,211........................................................kknkknkkkkkkkknkkkkknkkkkkkkklllaaaaaaaaaaaxxlaaalxxl1)1(,12................nnnknknnnnallxll2）回代-9-一个模拟计算机求解的例子12341234123412345242232533210xxxxxxxxxxxxxxxx求解解A/11/21/3123/11/211–23–711115–14–313–2–1–2–5206–54–191111511–23–7–5/24–411115–2–120611–23–73–2A11115121422325331211011111–2–1203–5/24–111–2323–2-10-(1)0,(1,2,1)kkkakn4消去法成立的条件：5计算量：3233nnn次乘法动态变化!-11-1Axb容易求解的方程组111121222231323333123000000,nnnnnnnaxbaaxbaaaxbaaaaxb则11bx),,2(11nkxabxkjjkjkk)1,,1(/)(1nkaxabxnkjkkjkjkknnnnabx/111213111222322233333000,000nnnnnnnaaaaxbaaaxbaaxbaxb则.A为下三角结构.A为上三角结构二三角分解法-12-,:AxbA对如果可进行如下分解111212122212nnnnnnaaaaaaAaaa2112111nnlll11121222nnnnuuuuuuLU则AxbLUxbLybUxy从而易得11yb11(2,,)kkkkjjjyblykn/nnnnxyu1()/(1,,1)nkkkjjkkjkxyuxukn2基本思想-13-3Gauss变换矩阵及性质.定义1,,111()11jjjnjLlll1200,,(,,,,,,)Tjjjjjnjllll记，称GaussGauss.为矩阵或变换.性质11.()()jjLLll-14-1,2,1,111()()1iiijiijjninjlLlLlllll2.ij当时，213132121123,1111()()()1...1nnnnnnlllLlLlLlllll-15-2P其中4Gauss消去法的矩阵形式12341234123412345242232533210xxxxxxxxxxxxxxxx求解解AA111151214223253312110211/()1rr312()/1rr413/()1rr1–23–711115–14–313–2–1–2–51PA1P其中000321()/1rr412()/1rr21()PPA11()1()1/11/2100206–54–191111501–23–7001/12/11()1()1(3/11)-16-A211/()1rr312()/1rr413/()1rr1–23–711115–14–313–2–1–2–51PA11()1()11/12/13/(1)1P其中000321()/1rr422()/1rr21()PPA211(1/)1()/1121P其中00206–54–191111501–23–700435()/2rr0004–4[|]Uy321()PPPA3111()5/12P其中综上亦即：即：1321()APPPULU111123LPPP其中111123()PPPU321()[|][|],PPPAbUyU其中为上三角矩阵.1111501–23–7002061/12/11/13/121111/15/2-17-所以，消元过程1[|][|]LAbUy11LAULby