中国矿业大学：《数值分析》课程教学课件（讲稿，研究生）第二章 线性方程组的直接解法

第二章线性方程组的直接解法S1 三角分解法82 正交三角分解法S3灵敏度分析1

-1- 第二章 线性方程组的直接解法 §3 灵敏度分析 §2 正交三角分解法 §1 三角分解法

快速、高效地求解线性方程组是数值线性代数研究中的核心问题，也是目前科学计算中的重要研究课题之一。四各种各样的科学和工程问题，往往最终都要归结为求解一个线性方程组图线性方程组的数值解法有：直接法和选代法。直接法：在假定没有舍入误差的情况下，经过有限次运算可以求得方程组的精确解：选代法：从一个初始向量出发，按照一定的送代格式，构造出一个趋向于真解的无穷序列。2

-2-  快速、高效地求解线性方程组是数值线性代数研究中的 核心问题，也是目前科学计算中的重要研究课题之一。  各种各样的科学和工程问题，往往最终都要归结为求 解一个线性方程组。  线性方程组的数值解法有：直接法和迭代法。 直接法：在假定没有舍入误差的情况下，经过有限次 运算可以求得方程组的精确解； 迭代法：从一个初始向量出发，按照一定的迭代格 式，构造出一个趋向于真解的无穷序列

S 2.1 三角分解法高斯消去法一2x;+x, =7+X2求解4x,+5x,-x, =11口一个例子-2x, +x,=0Xi解Stepl：消元2711217712115r3+T5A=(A,b)=4-1112-2ri3x203-3-303-3-3r3-0.5r0-2112000-2112-2-6xs = -6 /(-2) = 3x, =(-3+3×3)/3= 2Step2:回代1x, =(7-1×3-1×2)/2=1-3-

-3- 解 x x x x x x x x x               1 2 3 1 2 3 1 2 3 7 4 5 11 2 0 2 求解 Step1:消元 2 1 1 7 ( , ) 4 5 1 11 1 2 1 0 A A b               2 1 1 7 0 3 3 3 0 0 2 6               3 2 5 3 2 r r   Step2:回代      5 1 7 2 2 2 2 1 1 7 0 3 3 3 0               2 1 3 1 2 0.5 r r r r    一 高斯消去法  一个例子 x3     6/( 2) 3 x2      ( 3 3 3)/ 3 2 x       ( ) / 1 7 1 3 1 2 2 1 §2.1 三角分解法

1计算机上所用的公式a, +ai2X2 +...+ainXn = ai,n+1a21x, +a2X2 +..+a2nX, =a2,n+1求解方程：anx, +an2x +...+amx, =an,n+1下面研究它的计算规律：-4-

-4- n n n n n n n n nn n n n a x a x a x a a x a x a x a a x a x a x a                       11 1 12 2 1 1, 1 21 1 22 2 2 2, 1 1 1 2 2 , 1 求解方程： 1计算机上所用的公式 下面研究它的计算规律：

1消元aoalt+aaoao..*aaca.(0)aacaca2,n+1....***...aaaa0l(0)(0)ac4(0)记ak,k+1ak,n+1......0(0)a.ao.kα(0).(0)(0)ak+1,+1ak+1,nak+1,1ak+1,n+1.......................allaaaoa(0(0)an,n+1nnStepl：假设0,令=/a(i = 2, .., n).(0)a(0)aai(0)ai,k+11ai,n+1aii...1adalaada.0......ln'i11A(0).11aaualkadal0i = 2,., n1al.alalia.0...k+1,k11......***.*1aal.(1)alal)010-5-a......n2n,k+1n,n+1nn

- 5 - Step 1 ： 0 0 1 1 11 2 i i l a a i n   ( ) ( ) 令 / ( , ., ) i n  2, ., i i r l r  1 1 a  (0) 11 假 设 0 ， k k n n k k n n k k kk k k kn k n k k k k k a a a a a a a a a a a a A a a a a a a a a a a           (0) (0) (0) (0) (0) (0) 11 12 1 1, 1 1 1, 1 (0) (0) (0) (0) (0) (0) 21 22 2 2, 1 2 2, 1 (0) (0) (0) (0) (0) (0) (0) 1 2 , 1 , 1 (0) (0) (0) 1,1 1,2 1, . . . . . . . . . . . . . 记 k k n k n n n nk n k nn n n a a a a a a a a              (0) (0) (0) 1, 1 1, 1, 1 (0) (0) (0) (0) (0) (0) 1 2 , 1 , 1 . . . . . . . . . k k n n k k n n k kk k k kn k n k k k k k k n k a a a a a a a a a a a a a a a a a a a a a             (0) (0) (0) (0) (0) (0) 11 12 1 1, (1) (1) (1) (1) (1) (1) (1) (1) (1) (1) (1) ( 1 1 1, 1 22 2 2, 1 2 2, 1 2 , 1) (1) (1) 1 , 1 1,2 1, 1, 1 1, . . . . . . . . . . . . . 00 . 0 n n nk n k nn n n a a a a a          (1) (1) (1) ( 1, 1 2 , 1 , 1 1) (1) (1) . . . . . 0 . . . 1) 消 元 A (0)

aaltaoa-ao-aa(1)a...ad0a2.k+1...........(k-1),(k-1)at!假设第k-1步消元后A(k-1)=00ak,n+1kk(k-1)(k-1)altl.(k-1)00ak+1,kak+1,k+1ak+1,n+1......a(k-1)α(k-1)a(k-1)a(k-1)00n,k+1nknnn,n+1= α(k-1) / α(k-1)Stepk：若ak-10，计算lk(i= k +1, ..., n)kkα(k-1)a(t-1)以及a(k)10(i= k+1.., n; j=k+1...,n+l)5iikkjaaaaloa a.+Oadadaad0......ik'k1(k-1)g(k-1).(k-1).(k-1)00kkak,n+1ak,k+1aknAA(k)A(k-1)...(k)(k)(k)000i=k+l,.,nak+1,k+1ak+1,n+1ak+1,n.........o..(k)(k)(k)000an,k+1annan,n+1-6-

-6- 假设第k 1步消元后 k k n n k k n n k k k k k kk k k kn k n k k k k k k k a a a a a a a a a a a A a a a a a a a                   (0) (0) (0) (0) (0) (0) 11 12 1 1, 1 1 1, 1 (1) (1) (1) (1) (1) 22 2 2, 1 2 2, 1 ( 1) ( 1) ( 1) ( 1) ( 1) , 1 , 1 ( 1) ( 1) 1, 1, 1 . . . . . . . . . . 0 0 0 0 0 . . . . . . . . . k k n k n k k k k nk n k nn n n a a a a a                 ( 1) ( 1) 1, 1, 1 ( 1) ( 1) ( 1) ( 1) , 1 , 1 . . . 0 0 . . . . . . . . Step k： i k n   1, ., i ik k r l r  k kk a   ( 1) 若 0， k k ik ik kk l a a    ( 1) ( 1) 计算 / ( 1, ., ) i k n   k k k ij ij ik kj a a l a     以及 ( ) ( 1) ( 1) ( 1 . ; 1,., 1) i k n j k n      , , k A ( 1)  ( ) k A k k n n k k n n k k k k kk k k kn k n k k n k k k n k k a a a a a a a a a a a a a a a a a a                (0) (0) (0) (0) (0) (0) 11 12 1 1, 1 1 1, 1 (1) (1) (1) (1) (1) 22 2 2, 1 2 2, 1 ( 1) ( 1) ( 1) ( 1) , 1 , 1 1, 1 1, 1, 1 ( ) ( ) ( . . . . . . . . . . . 0 0 0 0 0 0 . . . . . n k nn n n k k k a a a         , 1 ) ( ) ( ) ( ) , 1 . . . . . . . . . 0 0 . 0 . 

消元结束，A化为上三角矩阵Step n-l:aaaalf+aaaada..aad0att!atl!at-l)A(n-a(k)att.at.010ak+1,k+1....a(ni)a(n-1)0nn,n+1k =1,2,..,n-l, a 0i= k+1,..,n在实际编程中为了节省内存a不引入新变量j = k + 1,..., n+1消元过程记为ay-aikak=a-7-

-7- Step n-1： k k n n k k n n n k k k k kk k k kn k n k k k k k n k n a a a a a a a a a a a A a a a a a a a                 (0) (0) (0) (0) (0) (0) 11 12 1 1, 1 1 1, 1 (1) (1) (1) (1) (1) 22 2 2, 1 2 2, 1 ( 1) ( 1) ( 1) ( 1) ( 1) , 1 , 1 ( ) ( ) 1, 1 1, 1, . . . . . . . . . . . . 0 0 . 0 . . 0 0 . . . 0 k n n nn n n a a           ( ) 1 ( 1) ( 1) , 1 . . . . . . . 0 . . . 0 0 . 0 消元结束，A化为上三角矩阵： 1 2 1 0 kk k n a    , ,., ， i k n   1,., ik ik ik kk a l a a   j k n    1,., 1 ij ik kj ij a a a a   在实际编程中， 为了节省内存， 不引入新变量， 消元过程记为：

消元束后，增广矩阵化为如下“形式”：al.aaa0aala...a..adaad..........alt!(k-1)os,(k-1)Iki1akkak,n+1(k)a(k).(k)Ik+iak+1,nak+1,k+1ak+1,n+1'k+1,kk+1.2...*.*e..,(n-1)a(n-1)InVnkIn.k+11ma中电业nnn,n+12）回代aaa0al.axi....adall(1)ad)X2a2,k+1......-/ax, =a(n-)a.............2a(k-1)a(k-1),(k-1)IIh2(k-1)(k-1)(k-)aknXk-1akkak,k+1X=(a)akjakk.n+1allat.j=k+1Ik+1.!1Xk..*k+1.2"k+1,k(k=n-1,.,1)....a(n-1)41In.k+1x....nn-8-

-8- 消元束后，增广矩阵化为如下“形式” ： k k n n k k n n k k k k kk k k kn k n k k k k k k k k k k a a a a a a l a a l l a a a a a a l a l l a a                 (0) (0) (0) (0) (0) (0) 11 12 1 1, 1 1 1, 1 (1) (1) (1) (1) (1) 22 2 2, 1 2 2, 1 ( 1) ( 1) ( 1) ( 1) , 1 , 1 ( ) 1 , 21 1 2 1,1 1.2 1, 1 1 . . . . . . . . . . . . . . . n n nk n k k n k n n n k nn n n l l l l a a a             ( ) ( ) , 1, 1 ( 1) ( 1) 1 2 1 , , 1 . . . . . . . . . . . n n n n n nn n k k k k k n kj j kk j k x a a x a a x a k n                       ( 1) 1 , 1 ( 1) ( 1) ( 1) , 1 1 / ( ) / ( 1, ,1) 1 (0) (0) (0) (0) (0) 11 12 1 1, 1 1 (1) (1) (1) (1) 22 2 2, 1 2 ( 1) ( 1) ( 1) , 1 ( ) 21 1 2 1,1 1.2 1, ( ) 1, 1 , 2 1 1 . . . . . . . . . . . . . . . . . . . . . . . . k k n k k n k k k kk k k kn k k k k k n k k k k k k k k l l l a a a a a a a a a a a x x l a l a a x l x              1 ) 1 ( , 1 2 . . . . . . . . n n nk n k n nn n l l l l a x         2）回代

0口一个模拟计算机求解的例子11511X+X++=521-1-24X+2x2 -x + 4x4 =-2解A=求解23-3-2-5-2x -3x2 +2x - 5x4 =31231103x +x,+2x,+x=10111511151-23111-2271/1A→26-1/11342-311-2/1-19-543-2/13/1-2-12-511111511113-23-22223006-1-1-22334-2-5/24-2-5/2-9-

-9-  一个模拟计算机求解的例子 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 5 2 4 2 2 3 2 5 3 3 2 10 x x x x x x x x x x x x x x x x                          求解 解 A  1 1/ 2 1/ 3 1/ 2 3 1 1/ 2 1/ 1 –2 3 –7 1 1 1 1 5 –1 4 – 3 13 –2 –1 –2 –5 2 0 6 –5 4 –19 1 1 1 1 5 1 1 –2 3 –7 –5/2 4 –4 1 1 1 1 5 –2 –1 2 0 6 1 1 –2 3 –7 3 –2 A     1 1 1 1 5 1 2 1 4 2 2 3 2 5 3 3 1 2 1 10      1 1 1 1 1 –2 –1 2 0 3 –5/2 4 –1 1 1 –2 3 2 3 –2

4消去法成立的条件：(k-1)+0, (k=1,2...,n-1)akk动态变化！2nn5计算量次乘法+n33-10-

-10- ( 1) 0, ( 1,2 , 1) k kk a k n     4消去法成立的条件： 5计算量： 3 2 3 3 n n   n 次乘法 动态变化!