第一节 直接法与三角形方程组的求解

第二章解线性方程组的直接法§1直接法与三角形方程组的求解第二章解线性方程组的直接法求解bxA§1直接法与三角形方程组的求解高斯消元法：思路首先将A化为上三角阵，再回代求解。=消元记(1)(1)(1)11121(1)(1)(1)(1)21222(1)(1)(1)12,nnnnnnnnaaaaaaAAaaa)1()1(1)1(...nbbbb第一次：设，计算因子(1)110a)...,,2(/)1(11)1(11niaamii将增广矩阵第i行mi1第1行，得到(2)(1)(1)(2)(1)(1)1111,,,2,3,,.ijijijiiiaamabbmbijn其中(1)(1)(1)11121(2)(2)(2)222(2)(2)20,0nnnnnnnaaaaaAaa(1)1(2)(2)2(2)nbbbb11111111211122222222()()1,1,1,,,knkknkkkkkkkknkkkkkkknkkkknknnnnnaaaabaaabAbaabaabaab第k步：设，计算因子()0kkka()()/(1,...,)kkikikkkmaaikn将增广矩阵第i行mik第k行，得到(1)()()(1)()(),,,1,,.kkkkkkijijikkjiiikkaamabbmbijkn如果k-1步消元已经完成111111112111222222222(),.knknnnkkkkkknknnnnnnnaaaabaaabAbaabab如果计算过程中均有()0,1,2,,1.kkkakn共进行？步，有n1回代)()(/nnnnnnabx)1...,,1()(1)()(niaxabxiiinijjiijiii相对的三角形方程组)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11..................nnnnnnnnbbbxxxaaaaaa上述过程意味着，只有()0,1,2,,1,kkkakn消元过程才能进行到底，也即可用消元法解线性方程组。定理若A消元过程满足则可用高斯消元法将方程组化为三角形方程组，且求出唯一解。()0,1,2,,1,kkkakn123123123231,220,325.xxxxxxxxx21311,212213121313111220022213257190222rrrr求解线性方程组3173213121313113110022222271951000022233rr1232,1,2.xxx解得线性方程组的解为11112211001,10,,.21012LAbAbAb上述过程的矩阵表示为21311,212213121313111220022213257190222rrrr223(2)(2)(3)2100,010,,.7013LAbAbAb3173213121313113110022222271951000022233rr三角分解的计算一个四阶矩阵分解的图示消元记(1)(1)(1)11121(1)(1)(1)(1)21222(1)(1)(1)12nnnnnnaaaaaaAAaaa第一次：设，(1)110a)...,,2(/)1(11)1(11niaamii(1)(1)(1)11121(2)(2)(2)222(2)(2)20,0nnnnnaaaaaAaa(1)(1)(1)(1)(1)(1)1112111121(1)(1)(1)(2)(2)2121222222(1)(1)(1)(2)(2)1122100-100010nnnnnnnnnnnnaaaaaamaaaaamaaaaa第二次：设，(2)220a(2)(2)2222/(3,...,)iimaain(1)(1)(1)(1)1112131(2)(2)(2)22232(2)(2)(3)(3)32333(2)(3)(3)223000nnnnnnaaaaaaaAaaaaaa(1)(1)(1)(1)1112131(2)(2)(2)22232(3)(3)(3)333(3)(3)30,0000nnnnnnaaaaaaaAaaaa(1)(1)(1)(1)(1)(1)(1)(1)11121311112131(2)(2)(2)(2)(2)(2)2223222232(2)(3)(3)(3)(3)3232333333(2)(3)(3)22231010001000010nnnnnnnnnnaaaaaaaaaaaaaamaaaaamaaa(3)(3)3,00nnnaa三角分解法高斯消元法的矩阵形式Step1:)0(/111111aaamii记L1=1...11121nmm，则][)1()1(1bAL)1(1)1(1)1(11...baan)2(A)2(bStepn1:)()2(2)1(1)()2(2)2(22)1(1)1(12)1(11121..................nnnnnnnnnbbbaaaaaabALLL其中Lk=1...11,,1knkkmm1kL1...11,,1knkkmm111211...nLLL111jim,记为L单位下三角阵/*unitarylower-triangularmatrix*/记U=)()2(2)2(22)1(1)1(12)1(11............nnnnnaaaaaaLUAA的LU分解/*LUfactorization*/Heyhasn’tGEgivenmeenoughheadache?WhydoIhavetoknowitsmatrixform??!WhenyouhavetosolvethesystemfordifferentwithafixedA.bCouldyoubemorespecific,please?FactorizeAfirst,thenforeveryyouonlyhavetosolvetwosimpletriangularsystemsand.bbyLyxU综合有定理若A消元过程满足则存在唯一的单位下三角矩阵L和上三角矩阵U使得A=LU。()0,1,2,,1,kkkakn顺序主元(),1,2,,1kkkakn不为零的充要条件？111111knkkkknnnknnaaaaaaaaa1111111111111knkkkkknnnnknnaaamaammakkkALU1122kkkkkkAaaa顺序主元(),1,2,,1kkkakn不为零的充要条件？定理主元均不为零的充分必要条件是A的i阶顺序主子阵都是非奇异的。()0,1,2,,1kkkakn(1,2,,1)iAin综合有(1,2,,1)iAin如果矩阵A的i阶顺序主子阵均为非奇异的，则存在唯一的单位下三角矩阵L和上三角矩阵U使得A=LU。定理注：L为一般下三角阵而U为单位上三角阵的分解称为Crout分解。实际上只要考虑A*的LU分解，即，则即是A的Crout分解。ULA~~**~*~LUA0)(nnnaWhatif?Nouniquesolutionexists.0)(iiiaWhatif?Thenwemustfindthesmallestintegerkiwith,andinterchangethek-throwwiththei-throw.0)(ikiaWhatifwecan’tfindsuchk?Nouniquesolutionexists.只要线性方程组系数矩阵A是非奇异的，则可以通过逐次消元及行的交换，将方程组化为三角形方程组，且可求出唯一解。定理用矩阵的LU分解解方程组Ax=b,.LybUxy11121222.nnnnnnuuuuuUu其中11212212nnnnlllLlll解下三角方程组Ly=b111111,2,3,,.iijjijiiibyllybyinl1,1,2,2,1.nnnnnijjijiiiiyxuuxyxinnu解上三角方程组Ux=y