优选数值分析第三章解线性方程组的直接方法
- 格式：ppt
- 大小：1.28 MB
- 文档页数：33
下载文档原格式
合集下载
数值分析实验三 线性方程组的直接接法2
数值分析实验三 线性方程的直接解法组号 班级 学号 姓名 分数一：实验目的1、掌握求解线性方程组的不同方法。
二：实验内容及基本知识介绍本实验中利用高斯消去法和矩阵的直接三角分解法求解线性方程组。
用消去法解方程组的基本思想：是用逐次消去未知数的方法把原方程组Ax=b 化为与其等价的三角形方程组，而求解三角形方程组可用回代的方法求解。
即上述过程就是用行的初等变换将原方程组系数矩阵化为简单形式（上三角矩阵），从而将求解原方程组的问题转化为求解简单方程组问题。
或者说对系数矩阵A 施行一些做变换将其约化为上三角矩阵。
直接三角分解法的原理：在高斯消去法的基础上，高斯消去法实质上产生了一个将A 分解为两个三角形矩阵相乘的因式分解，即矩阵的LU 分解——设A 为n 阶矩阵，如果A 的顺序主子式i D ≠0（i=1,2,…n-1）,则A 可分解为一个单位下三角矩阵L 和一个上三角矩阵U的乘积，且这种分解是唯一的。
将高斯消去法改写为紧凑形式，可以直接从矩阵A 的元素得到计算L,U 元素的递推公式，而不需要任何中间步骤，这就是直接三角分解法。
一旦实现了矩阵A 的LU 分解，那求解Ax=b 的问题就等价于求解两个三角形方程组 ① Ly=b,求y;② Ux=y,求x.其中用直接三角分解法解Ax=b 的分解矩阵A 的计算公式：①111111(1,2,...),/(2,3,...),i i i i i n i n u a l a u ====计算U 的第r 行，L 的第r 列元素（r=2,3,…n ）.②11r ri ri rk ki k ua l u -==-∑ (i=r,r+1,…n); ③11)/(r ir ik kr rr ir k a l l u u -==-∑ (i=r+1,…,n;且r ≠n) 三：实验问题及方法、步骤分别用直接三角分解法和高斯消元法解方程组Ax=b,其中 2111339,23353A b --⎛⎫⎛⎫ ⎪ ⎪== ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭。
数值分析第三章 解线性方程组的直接方法 ppt课件
对算每一一次行。计以算后每s注i一意数步m 1：学考j这上a虑n两|严x子a个格i列j |方等。 a程价为...kk 组。省中在时as间iki 最，s大i 只的在ai初k 为始主时元计。
a nk
注：稳定性介于列主元法和全主元法之间。
§2 三角分解法 /* Matrix Factorization */
A(2) b(2)
其中
a(2) ij
b(2) i
a(1) ij
b(1) i
mi
a(1)
1 1j
mi1b1(1)
(i, j 2, ...,n)
Step
k：设
a(k) kk
， 0计算因子
m ik a i(k k )/a k (k )k(i k 1 ,..n ) .,
且计算
a(k1) ij
➢ 高斯消元法的矩阵形式 /* Matrix Form of G.E. */：
Step 1: m i1a i1/a 11(a 1 10 )
1
记 L1 =
m 21 ...
1
m n1
a1(1)1...a1(1n) b1(1)
A b ，则 L 1 [A (1 ) b (1 )]
(2) (2)
1
Step n 1:
Ln1Ln2 ...L1
Ab
a1(11)
a(1) 12
a(2) 22
...
a(1) 1n
...
a(2) 2n
... ...
bb12((12))
...
其中 Lk =
1
a(n) nn
bn(n)
1
m k 1,k ...
m n ,k
1
1
数值分析第三章 解线性方程组的直接方法
§1 Gaussian Elimination – The Method
回代
( n) ( n) xn bn / ann
bi( i ) xi
a
j i 1 (i ) ii
(i ) a ij x j
n
( i n 1, ..., 1)
Then must find the Whatwe if we can’t (n i) smallest integer k i with ( ) 0 定理 若A的所有顺序主子式 a /* determinant of leading What if ? find such k ? ii No No unique unique a 0 What if ? (i ) nn , and interchange a ki 0 exists. solution solution exists. principal submatrices */ k 均不为 ，则高斯消元无需换行即可 the -th row0 with the i-th row.
. a nk
si
注：稳定性介于列主元法和全主元法之间。
§2 三角分解法 /* Matrix Factorization */
高斯消元法的矩阵形式 /* Matrix Form of G.E. */：
Step 1: mi 1 ai 1 / a11
1 m21 1 . . . m n1
1步 共进行 n ？
(1) (1) ) (1) a11 x a12 ... a1(1 b 1 n 1 ( 2) ( 2) ( 2) a22 ... a2 n x2 b2 . . . . . ... . . . . ( n) ( n) ann xn bn
解线性方程组的直接方法
解线性方程组的直接方法一、高斯消元法高斯消元法是解线性方程组最常用的方法之一、它通过一系列的消元操作，将线性方程组转化为阶梯型方程组，从而求解未知数的值。
1.确定线性方程组的阶数和未知数的个数。
设线性方程组中有n个未知数。
2.将线性方程组写成增广矩阵的形式。
增广矩阵是一个n行n+1列的矩阵，其中前n列是线性方程组的系数矩阵，第n+1列是等号右边的常数。
3.通过初等行变换（交换行、数乘行、行加行）将增广矩阵化为阶梯型矩阵。
具体步骤如下：a.首先，找到第一个非零元素所在的列，将它所在的行视为第一行。
b.将第一行的第一个非零元素（主元）变成1，称为主元素。
c.将主元所在列的其他元素（次元素）变为0，使得主元所在列的其他元素只有主元素是非零的。
d.再找到第一个非零元素所在的列，将它所在的行视为第二行，并重复上述步骤，直到将增广矩阵化为阶梯型矩阵。
4.根据阶梯型矩阵求解未知数的值。
具体步骤如下：a.从最后一行开始，依次求解每个未知数。
首先，将最后一行中非零元素所在的列作为含有该未知数的方程，将该未知数的系数设为1b.将含有该未知数的方程中其他未知数的系数设为0，并对其他方程进行相应的变换，使得该未知数所在列的其他元素都为0。
c.重复上述步骤，直到求解出所有未知数的值。
高斯消元法的优点是简单易懂、容易实现，但当线性方程组的系数矩阵接近奇异矩阵时，计算精度可能会降低。
二、矩阵求逆法矩阵求逆法是解线性方程组的另一种直接方法。
它通过对系数矩阵求逆，然后与常数矩阵相乘，得到未知数的值。
1.确定线性方程组的阶数和未知数的个数。
设线性方程组中有n个未知数。
2.将线性方程组写成矩阵方程的形式，即Ax=b，其中A是一个n阶方阵，x和b分别是n维列向量。
3.求系数矩阵A的逆矩阵A^-1a. 首先，计算系数矩阵A的行列式det(A)。
b. 判断det(A)是否为0，如果det(A)=0，则该线性方程组无解或有无穷多解；如果det(A)≠0，则系数矩阵A可逆。
第3章_解线性方程组的直接方法
变换结束后增广矩阵最后一列就是解，不
需回代。这种解法称为约当消去法。
它容易学习掌握，也容易编写计算机程序。 其计算过程可写为：
2020/1/22
18
数值计算方法
对k=1~n(步)做
对j= k+1~n (行)令 akj akj / akk
对I=1~n但i≠k(行)做（“适当倍数”）
对j= k+1~n+1(列)令aij aij aikakj
4
数值计算方法
例如： 要解方程组
x1 2x2 3x3 1 5x1 x2 3x3 4
7x1 8x2 11x3 3
其步骤如下：将第一个方程乘-5，-7，分别加于第二、 第三方程，消去未知量x1，得同解方程组
x1 2x2 3x3 1 9x2 18x3 9
6x2 10x3 10
2020/1/22
5
数值计算方法
将所得方程组的第二方程乘 2 ，加到第三方程，
3
消去未知量x2，得同解方程组
x1 2x2 3x3 1
9x2 18x3 9
2x3 4
这是上三角形方程组。
由第三方程解得x3=-2，将x3代入第二方程可
数值计算方法
不过交换两列相当于改变未知量顺序，所 以需用一数组，专门记录未知量顺序及其变化， 并在最后调整解的顺序，使解中n个数与未知 量正确对应。
假定用数组L表求未知量的顺序，则全主 元法的计算步骤可归纳如下：
2020/1/22
26
数值计算方法
对j=1~n令Lj j（记未知量原始顺序） 对k=1~n-1做（以下为消去过程）
bn
数值计算_第3章 解线性方程组的直接法
第3章解线性方程组的直接法在近代数学数值计算和工程应用中，求解线性方程组是重要的课题。
例如，样条插值中形成的关系式，曲线拟合形成的法方程等，都落实到解一个元线性方程组，尤其是大型方程组的求解，即求线性方程组（3.1）的未知量的数值。
（3.1）其中ai j，bi为常数。
上式可写成矩阵形式Ax = b，即（3.2）其中，为系数矩阵，为解向量，为常数向量。
当detA=D0时，由线性代数中的克莱姆法则，方程组的解存在且惟一，且有为系数矩阵的第列元素以代替的矩阵的行列式的值。
克莱姆法则在建立线性方程组解的理论基础中功不可没，但是在实际计算中，我们难以承受它的计算量。
例如，解一个100阶的线性方程组，乘除法次数约为（101·100！·99），即使以每秒的运算速度，也需要近年的时间。
在石油勘探、天气预报等问题中常常出现成百上千阶的方程组，也就产生了各种形式方程组数值解法的需求。
研究大型方程组的解是目前计算数学中的一个重要方向和课题。
解方程组的方法可归纳为直接解法和迭代解法。
从理论上来说，直接法经过有限次四则运算，假定每一步运算过程中没有舍入误差，那么，最后得到方程组的解就是精确解。
但是，这只是理想化的假定，在计算过程中，完全杜绝舍入误差是不可能的，只能控制和约束由有限位算术运算带来的舍入误差的增长和危害，这样直接法得到的解也不一定是绝对精确的。
迭代法是将方程组的解看作某种极限过程的向量极限的值，像第2章中非线性方程求解一样，计算极限过程是用迭代过程完成的，只不过将迭代式中单变量换成向量而已。
在用迭代算法时，我们不可能将极限过程算到底，只能将迭代进行有限多次，得到满足一定精度要求的方程组的近似解。
在数值计算历史上，直接解法和迭代解法交替生辉。
一种解法的兴旺与计算机的硬件环境和问题规模是密切相关的。
一般说来，对同等规模的线性方程组，直接法对计算机的要求高于迭代法。
对于中等规模的线性方程组，由于直接法的准确性和可靠性高，一般都用直接法求解。
第3章线性方程组的直接解法1PPT课件
(3.5)
u x n1,n1 n1 un1,nxn bn1
unnxn bn
n
u iixi b i (u i,i 1 xi 1 u inxn) b i u ijxj
j i 1
xnbn/unn,
xi bijn i1uijxj/uii8,in1,n2,
返回LU
,2,1. 返回(3.20)
3.2.2 消去法的基本思想
(3.4)
返回式3.19
i1
liixi bi (li1x1li2x2 li,i1xi1)bi lijxj j1
i1
xi bi lijxj /lii, i 1,2, ,n.
j1
7
三、上三角方程组（返回Gauss）
u11x1 u12x2 u13x3 u1nxn b1
uiixi ui,i1xi1 uinxn bi
x3
78 26
3
x2 -28 10x3 -28 10(3)
x 1
16
(x2
2
4x 3 )
2
10
16
2 2
4(3)
1
3.2.3 高斯消元过程（即初等行变换） 记方程组（3.1）为
返回矩阵的三角分解
aa12((1111))xx11
a1(12)x2 a2(12)x2
an(11)x1an(12)x2
2
3.1 引 言
自然科学和工程计算中的很多问题的解决常常 归结为求解线性方程组。如三次样条插值函数问 题、用最小二乘原理确定拟合曲线、求解微分方 程的数值解等，最终都要转化为求解线性方程组。
求解线性方程组可采用：
1、直接法——经有限步算术运算可求得方 程组的精确解的方法（若计算过程无舍入误差）。
解线性方程组的直接解法
解线性方程组的直接解法一、实验目的及要求关于线性方程组的数值解法一般分为两大类：直接法与迭代法。
直接法是在没有舍入误差的情况下，通过有限步运算来求方程组解的方法。
通过本次试验的学习，应该掌握各种直接法，如：高斯列主元消去法，LU分解法和平方根法等算法的基本思想和原理，了解它们各自的优缺点及适用范围。
二、相关理论知识求解线性方程组的直接方法有以下几种：1、利用左除运算符直接求解线性方程组为bx\=即可。
AAx=，则输入b2、列主元的高斯消元法程序流程图：输入系数矩阵A，向量b，输出线性方程组的解x。
根据矩阵的秩判断是否有解，若无解停止；否则，顺序进行；对于1p:1-=n选择第p列中最大元，并且交换行；消元计算；回代求解。
（此部分可以参看课本第150页相关算法）3、利用矩阵的分解求解线性方程组（1）LU分解调用matlab中的函数lu即可，调用格式如下：[L,U]=lu（A）注意：L往往不是一个下三角，但是可以经过行的变换化为单位下三角。
（2）平方根法调用matlab 中的函数chol 即可，调用格式如下：R=chol （A ）输出的是一个上三角矩阵R ，使得R R A T =。
三、研究、解答以下问题问题1、先将矩阵A 进行楚列斯基分解，然后解方程组b Ax =(即利用平方根法求解线性方程组，直接调用函数)：⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--------=19631699723723312312A ，⎪⎪⎪⎪⎪⎭⎫ ⎝⎛-=71636b 解答：程序：A=[12 -3 2 1;-3 23 -7 -3;2 -7 99 -6;1 -3 -6 19];R=chol(A)b=[6 3 -16 7]';y=inv(R')*b %y=R'\bx=inv(R)*y %x=R\y结果：R =3.4641 -0.8660 0.5774 0.28870 4.7170 -1.3780 -0.58300 0 9.8371 -0.70850 0 0 4.2514y =1.73210.9540-1.59451.3940x =0.54630.2023-0.13850.3279问题 2、先将矩阵A 进行LU 分解，然后解方程组b Ax =（直接调用函数）：⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛----=8162517623158765211331056897031354376231A ，⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛-=715513252b解答：程序：A=[1/3 -2 76 3/4 5;3 1/sqrt(3) 0 -7 89;56 0 -1 3 13;21 65 -7 8 15;23 76 51 62 81];b=[2/sqrt(5);-2;3;51;5/sqrt(71)];[L,U]=lu(A)y=inv(L)*bx=inv(U)*y结果：L = 0.0060 -0.0263 1.0000 0 00.0536 0.0076 -0.0044 0.1747 1.00001.0000 0 0 0 00.3750 0.8553 -0.6540 1.0000 00.4107 1.0000 0 0 0U =56.0000 0 -1.0000 3.0000 13.00000 76.0000 51.4107 60.7679 75.66070 0 77.3589 2.3313 6.91370 0 0 -43.5728 -50.06310 0 0 0 96.5050y =3.0000-0.63880.859850.9836-11.0590x =0.13670.90040.0526-1.0384-0.1146问题3、利用列主元的高斯消去法，求解下列方程组：⎪⎪⎩⎪⎪⎨⎧=+--=--+=-+-=+-+01002010100511.030520001.0204321432143214321x x x x x x x x x x x x x x x x解答：程序：function [RA,RB,n,X]=liezhu(A,b)B=[A b];n=length(b);RA=rank(A);RB=rank(B);zhica=RB-RA;if zhica>0disp('Çë×¢Ò⣺RA~=RB£¬ËùÒÔ´Ë·½³Ì×éÎ޽⡣')returnendif RA==RBif RA==ndisp('Çë×¢Ò⣺ÒòΪRA=RB=n,ËùÒÔ´Ë·½³Ì×éÓÐΨһ½â¡£')X=zeros(n,1);C=zeros(1,n+1);for p=1:n-1[Y ,j]=max(abs(B(p:n,p)));C=B(p,:);for k=p+1:nm=B(k,p)/B(p,p);B(k,p:n+1)=B(k,p:n+1)-m*B(p,p:n+1)endendb=B(1:n,n+1);A=B(1:n,1:n);X(n)=b(n)/A(n,n);for q=n-1:-1:1X(q)=(b(q)-sum(A(q,q+1:n)*X(q+1:n)))/A(q,q);endelsedisp('Çë×¢Ò⣺ÒòΪRA=RB¡´n£¬ËùÒÔ´Ë·½³ÌÓÐÎÞÇî¶à½â¡£') endend键入A=[1 20 -1 0.0012 -5 30 -0.15 1 -100 -102 -100 -1 1];b=[0;1;0;0];[RA,RB,n,X]=liezhu(A,b)结果：请注意：因为RA=RB=n,所以此方程组有唯一解。
数值分析第三章线性方程组解法
数值分析第三章线性方程组解法在数值分析中，线性方程组解法是一个重要的主题。
线性方程组是由一组线性方程组成的方程组，其中未知数的次数只为一次。
线性方程组的解法包括直接解法和迭代解法两种方法。
一、直接解法1.1矩阵消元法矩阵消元法是求解线性方程组的一种常用方法。
这种方法将方程组转化为上三角矩阵，然后通过回代求解得到方程组的解。
1.2LU分解法LU分解法是将系数矩阵A分解为一个下三角矩阵L和一个上三角矩阵U的乘积，然后通过解两个三角方程组求解线性方程组。
这种方法可以减少计算量，提高计算效率。
1.3 Cholesky分解法Cholesky分解法是对称正定矩阵进行分解的一种方法。
它将系数矩阵A分解为一个下三角矩阵L和它的转置的乘积，然后通过解两个三角方程组求解线性方程组。
Cholesky分解法适用于对称正定矩阵的求解，具有较高的精度和稳定性。
二、迭代解法2.1 Jacobi迭代法Jacobi迭代法是一种迭代求解线性方程组的方法。
它通过分解系数矩阵A为一个对角矩阵D和一个余项矩阵R，然后通过迭代更新未知数的值，直至达到一定精度要求为止。
Jacobi迭代法简单易懂，容易实现，但收敛速度较慢。
2.2 Gauss-Seidel迭代法Gauss-Seidel迭代法是一种改进的Jacobi迭代法。
它通过使用新计算出的未知数值代替旧的未知数值，达到加快收敛速度的目的。
Gauss-Seidel迭代法是一种逐步逼近法，每次更新的未知数值都会被用于下一次的计算，因此收敛速度较快。
2.3SOR迭代法SOR迭代法是一种相对于Jacobi和Gauss-Seidel迭代法更加快速的方法。
它引入了一个松弛因子，可以根据迭代的结果动态地调整未知数的值。
SOR迭代法在理论上可以收敛到线性方程组的解，而且收敛速度相对较快。
三、总结线性方程组解法是数值分析中的一个重要内容。
直接解法包括矩阵消元法、LU分解法和Cholesky分解法，可以得到线性方程组的精确解。
数值分析第三章解线性方程组的直接方法演示文稿
省去换列的步骤，每次仅选一列中最大的元。
| aik ,k
|
max
kin|aik Nhomakorabea|
0
§1 Gaussian Elimination – Pivoting Strategies
例：
109
1
1 1
1 2
1 109
1 1
2 1
1 0
1 1
2 1
x2 1 , x1 1 ✓
注：列主元法没有全主元法稳定。
➢ 选主元消去法
例：单精度解方程组
109
x1
x2
1
x1 x2 2
/*
精确解为
x1
1 1 109
8个
1.00...0100...和
x2 2
x1
8个
0.99 ...9899...*/
用Gaussian Elimination计算：
m21 a21 / a11 109 8个 a22 1 m21 1 0.0 ...01109 109 109
b (1)
b
b1(1) ...
bn(1)
Step 1：设a1(11) ，0计算因子
mi1
a (1) i1
/
a (1) 11
(i 2, ..., n)
将增广矩阵/* augmented matrix */ 第 i 行 mi1 第1行，
得到
a (1) 11
a (1) 12
...
a (1) 1n
b(1) ]
a(1) 11
...
a(1) 1n
b1(1)
A b (2) (2)
1
Step n 1:
Ln1Ln2 ... L1
数值分析小论文线性方程组的直接解法
数值分析小论文线性方程组的直接解法线性方程组的直接解法是指通过一系列的代数运算直接求解线性方程组的解。
线性方程组是数值分析中非常重要的问题，广泛应用于工程、科学、计算机图形学等领域。
在线性方程组的直接解法中，最常用的方法是高斯消元法，它是一种基于矩阵变换的方法。
高斯消元法将线性方程组表示为增广矩阵，并通过一系列的行变换将增广矩阵转化为行阶梯形矩阵，从而得到方程组的解。
高斯消元法的主要步骤包括消元、回代和得到方程组的解。
消元是高斯消元法的第一步，通过一系列的行变换将增广矩阵的元素转化为上三角形式。
在消元过程中，我们首先找到主元素，即矩阵的对角线元素，然后将其它行的元素通过消元操作转化为0，从而使得矩阵逐步变成上三角形矩阵。
回代是高斯消元法的第二步，通过一系列的回代操作求解线性方程组。
回代操作是从上三角形矩阵的最后一行开始，通过依次求解每个未知数的值，最终得到方程组的解。
高斯消元法的优点是算法简单易于实现，可以在有限的步骤内求解线性方程组，适用于一般的线性方程组问题。
但是高斯消元法也存在一些问题，例如当矩阵的主元素为0时，无法进行消元操作，此时需要通过行交换操作来避免这种情况。
另外，高斯消元法对病态矩阵的求解效果较差，容易引起舍入误差累积，导致解的精度下降。
在实际应用中，为了提高求解线性方程组的效率和精度，人们常常使用一些改进的直接解法，例如列主元高斯消元法和LU分解法。
列主元高斯消元法通过选择最大主元来避免主元为0的情况，进一步提高了求解线性方程组的精度。
LU分解法将矩阵表示为两个矩阵的乘积，从而将线性方程组的求解问题转化为两个三角形矩阵的求解问题，提高了求解效率。
综上所述，线性方程组的直接解法是一种基于矩阵变换的方法，通过一系列的代数运算求解线性方程组的解。
高斯消元法是最常用的直接解法之一，它简单易于实现，适用于一般的线性方程组问题。
在实际应用中，可以通过改进的直接解法来进一步提高求解效率和精度。
数值分析 第三章解线性方程组的直接法
T T A LDU 0 , AT U 0 DT LT , A AT U 0 L A LDLT
由于A是正定矩阵，所以D中的元素都大于零，可以把D也再分解
14
d11 d11 1 1 1 d 22 D2 D2 , D2 D d nn
lii 1,lik 0 k i , ukj 0 k j
11
ai1 由此得算法： u1 j a1 j , j 1, 2,, n; li1 a ,i 1, 2,, n 11
uij aij lik ukj , j i, i 1,, n; lij
还可以进一步用标度化的选主元(相对最大)
6
第三节 矩阵的三角分解
消元法求解方程组是通过行初等变换把系数矩阵化为对角阵,由 线性代数知识可知,左乘一个初等矩阵,就相当于做一次行变换.
1 a 21 a11 a 记 L = 31 1 a11 an1 ห้องสมุดไป่ตู้ 11
第三章 解线性方程组的直接法
第一节 引言
解线性方程组的方法可分为两大类:直接法和迭代法. 直接法的基本原理就是高斯消元法,再根据数值计算的特点 做一些适当的处理而得到的一类算法.直接法的特点是没有 截断误差,只有计算误差(舍入误差). 迭代法是类似于上一章单个方程那样,以某种方式构造一 个向量序列,使得这个向量序列收敛到解向量.因此迭代 法既有截断误差又有舍入误差.
0.01000 0.01200 0 0.100 103 0 0 .
8.010 44.41 1175 105 6517 105 x3 5.546; x2 100.0; x1 104.0 0.1670 0.6781
第三章 解线性方程组的直接法
第三章 解线性方程组的直接法3.1 引言许多科学技术问题要归结为解含有多个未知量x 1, x 2, …, x n 的线性方程组。
例如，用最小二乘法求实验数据的曲线拟合问题，三次样条函数问题，解非线性方程组的问题，用差分法或有限元法解常微分方程、偏微分方程的边值等，最后都归结为求解线性代数方程组。
关于线性方程组的数值解法一般有两类：直接法和迭代法。
1. 直接法直接法就是经过有限步算术运算，可求得线性方程组精确解的方法（假设计算过程中没有舍 入误差）。
但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解。
本章将阐述这类算法中最基本的高斯消去法及其某些变形。
2. 迭代法迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法，迭代法需要的计算机存储 单元少、程序设计简单、原始系数矩阵在计算过程中不变，这些都是迭代法的优点；但是存在收敛性和收敛速度的问题。
迭代法适用于解大型的稀疏矩阵方程组。
为了讨论线性方程组的数值解法，需要复习一些基本的矩阵代数知识。
3.1.1 向量和矩阵 用nm ⨯R表示全部n m ⨯实矩阵的向量空间，nm C⨯表示全部n m ⨯复矩阵的向量空间。
()⎪⎪⎪⎪⎪⎭⎫⎝⎛==⇔∈⨯nn n n n n ij nm a a aa a aa a a a212222111211A R A 此实数排成的矩形表，称为m 行n 列矩阵。
⎪⎪⎪⎪⎪⎭⎫⎝⎛=⇔∈n n x x x 21x R x x 称为n 维列向量矩阵A 也可以写成)(n 21a ,,a ,a A = 其中 a i 为A 的第i 列。
同理⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=T T T n 21b b b A其中T i b 为A 的第i 行。
矩阵的基本运算：（1） 矩阵加法 )( ,n m n m R C ,R B ,R A B A C ⨯⨯⨯∈∈∈+=+=n m ij ij ij b a c . （2） 矩阵与标量的乘法 ij j a ci αα== ,A C （3） 矩阵与矩阵乘法 p nk kjik b acij ⨯⨯⨯=∈∈∈==∑m p n n m R C ,R B ,R A AB C ( ,1（4） 转置矩阵 ji ij T nm a c ==∈⨯ , ,A C RA（5） 单位矩阵 ()n n ⨯∈=R e ,,e ,e I n 21 ，其中 ()Tk e 0,0,1,0,0 = k=1,2,…,n（6） 非奇异矩阵 设nn ⨯∈RA ，nn ⨯∈RB 。
第3章线性方程组的直接解法1
b1(1) (1) （3.6） b2 (1) bn
若 a 第一步消元： 11 0,
１
(1) 利用主元素（即为消元过程中的主对角线元素）a11 (1) a 消去下面的 i1 , i 2,3,, n
取消元因子 消元计算得到
li1 a / a , i 2,3,, n 用第 i 行减去第一行的 l a(1) / a(1) , i 2,3,, n倍 i1 i1 11
i 1
三、上三角方程组（返回Gauss）
u11 x1 u12 x 2 u13 x3 u1n x n b1 u ii xi u i ,i 1 xi 1 u in x n bi u n 1,n 1 x n 1 u n 1,n x n bn 1 u nn x n bn n uii xi bi (ui ,i 1 xi 1 uin xn ) bi uij x j
阶线性方程组消元过程可描述为经过
步消元化成上三角方程组.
A
(1)
,b
(1)
A
k 1
( 2)
,b
( 2)
A
k 2
(k )
,b
(k )
A
k n 1
(n)
, b( n )
三、高斯消去法的算法公式
（上三角形式）.
总结上述消元与回代过程，得到高斯消去法的算法公式如下
或写成矩阵形式：
(3.1)
返回
a11 a12 a a 21 22 a a n1 n 2
或简单地记为:
a1n x1 b1 a 2 n x 2 b2 b a nn x n n Ax b,
第三章 解线性方程组的直接法
相等.
定理 线性方程组 AX = b 可以用简单高斯消元法求解的
充要条件是
系数矩阵
A的
k
阶顺序主子式
∆k
≠
0
(k
=1, 2, , n).
8
如果主对角元素 ak(kk) 的绝对值很小, 由第一章的误差分 析可知计算时将会产生很大的计算误差.
例 用简单高斯消元法求解方程组(用四位浮点数计算)
0.012x1 + 0.01x2 + 0.167 x3 = 0.6781,
a(2) 2n
b1(1) b2( 2 )
→
An
= 0
0
a(3) 33
a(3) 3n
b3( 3 )
.
0
0
0
a(n) nn
bn(n)
对应的同解上三角形方程组为
a(1) 11
x1
+
a(1) 12
x2
a(2) 22
x2
+
+
a(1) 1n
b
0.6781
12.10
981.0
r1 ↔ r3
14
例 用高斯全主元消元法求解方程组(用四位浮点数计算)
0.012x1 + 0.01x2 + 0.167 x3 = 0.6781,
x1
+
0.8334 x2
+
5.91x3
= 12.1,
3200
x1
+
1200 x2
+
【VIP专享】数值分析课件 第三章 线性代数方程组的直接解法19
L1 n1
L
l31
l32 1
ln1 ln2
1 ln,n1
1
l2,1
1
即单位下三角阵
L
l3,1 M
l3,2 M
O M
1
ln,1 ln,2 L ln,n1 1
可以分解为一系列初等下三角阵的乘积
L L11L21 L
L L 1 1 n2 n1
三、 三角分解的计算
➢ Gauss消去法
设给定矩阵
r1T A1
高斯变换
a(1) 11 0
r1T
取 L1 I l1e1T l1 (0, l21,L , ln1)T
其中
li1
a (1) i1
a (1) 11
i 2,3,L , n
记 A(2) L11 A(1)
1
A( 2 )
c1
a(1) 11
L11 I l1e1T
0
a (1) 11
end
b(n) b(n) l(n, n)
➢考虑上三角形方程组
Ux y
u11 u12 ... u1n
x1 y1
U
u22
...
u2n
x
x2
,
y
y2
O
M M
unn
xn yn
xi 的计算公式为：
1
n
xi
uii
yi
uij x j , i
ji 1
n, n 1,L
,1;
算法3.1.2 上三角形方程组的回代法：
for j n : 1: 2
y( j) y( j) u( j, j) y(1: j 1) y(1: j 1) y( j)u(1: j 1, j)
解线性方程组的直接方法
解线性方程组的直接方法一、高斯消元法高斯消元法是解线性方程组的一种常用且直接的方法。
它的基本思想是通过一系列的代数运算，将方程组化为一个三角方程组，然后从最后一行开始，逐步回代求解未知数。
下面以一个二元一次方程组为例，说明高斯消元法的具体步骤：例如，给定方程组：a₁₁x₁+a₁₂x₂=b₁a₂₁x₁+a₂₂x₂=b₂其中，a₁₁,a₁₂,a₂₁,a₂₂,b₁,b₂为已知系数。
1.检查a₁₁的值是否为0，若为0则交换第一行与非零行。
2.将第一行的每个元素除以a₁₁，使a₁₁成为13.将第一行乘以(-a₂₁)并加到第二行上，使第二行的第一个元素变为0。
4.引入一个新的未知数y₂=a₂₁x₁+a₂₂x₂，并代入第二行，化简方程组。
5.使用回代法求解方程组。
高斯消元法的优势在于其直接的解题思路和较高的计算精度，但是其缺点是计算复杂度较高，对于大规模的方程组不太适用。
二、逆矩阵法逆矩阵法是解线性方程组的另一种直接方法，它通过求解方程组的系数矩阵的逆矩阵，并将其与方程组的常数向量相乘，得到方程组的解向量。
下面以一个三元一次方程组为例，说明逆矩阵法的具体步骤：例如，给定方程组：a₁₁x₁+a₁₂x₂+a₁₃x₃=b₁a₂₁x₁+a₂₂x₂+a₂₃x₃=b₂a₃₁x₁+a₃₂x₂+a₃₃x₃=b₃其中，a₁₁,a₁₂,a₁₃,a₂₁,a₂₂,a₂₃,a₃₁,a₃₂,a₃₃,b₁,b₂,b₃为已知系数。
1.计算系数矩阵A的行列式D=，A。
2. 求解系数矩阵A的伴随矩阵Adj(A)。
3. 计算逆矩阵A⁻¹=Adj(A)/D。
4.将常数向量b用列向量表示。
5.计算解向量x=A⁻¹b。
逆矩阵法的优势在于其求解过程相对简单，计算量较小，并且不需要对系数矩阵进行消元操作。
但是逆矩阵法的限制在于当系数矩阵不可逆时无法使用。
三、克莱姆法则克莱姆法则是解线性方程组的另一种直接方法，它通过定义克莱姆行列式和克莱姆向量，利用行列式的性质求解方程组的解向量。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
mik
b(k ) k
(i, j k 1, ..., n)
共进行 n？ 步1
mik
a(k) ik
/ ak(kk )
a1(11)
a(1) 12
a(2) 22
... ...
...
(i k 1, ..., n)
a(1) 1n
a(2) 2n ...
a(n) nn
x1
x2 ... xn
➢ 选主元消去法
例：单精度解方程组
109
x1
x2
1
x1 x2 2
/*
精确解为
x1
1 1 109
8个
1.00...0100...和
x2 2
x1
8个
0.99 ...9899...*/
用Gaussian Elimination计算：
m21 a21 / a11 109 8个 a22 1 m21 1 0.0 ...01109 109 109
b2 2 m21 1 109
109 1
1
0
109
109
小主元 /* Small pivot element */ 可能导致计
算失败。
x2 1, x1 0
全主元消去法 /* Complete Pivoting */
每一步选绝对值最大的元素为主元素，保证 | mik | 。1
Step k:
b(1) ]
a(1) 11
...
a(1) 1n
b1(1)
A b (2) (2)
1
Step n 1:
Ln1Ln2 ... L1
Ab
a1(11)
a(1) 12
a(2) 22
...
a(1) 1n
...
a(2) 2n
... ...
b(1) 1
b(2) 2
...
1
其中
Lk =
a(n) nn
b(n) n
1
mk1,k ...
mn,k
1
1
Lk1
1
mk 1,k ...
mn,k
§2 Matrix Factorization – Matrix Form of G.E.
1
L11
L21
...
L1 n1
1
mi, j
记为 L
1
1
a(1) 11
记U=
A LU a(1) 12
a(2) 22
seHo...nd...lesdFs...ovCfiyyfooWasebu/foUs*rcaealphmgIuvtht12tr(u(...eewaehx1h2nenoleea))vndcsmaornnthteiinirvhfyttzsreisiya’exoeeyctaioryAm,uLGtydfbsAwuoop..aypEbl单yirlohfscktyelemihegwatohnra位esmv?iueostaevmtre??ewr,eoib下foa-!?itnrtfxnhnoiWeroate三ilmegsrayndhnunedh角ylgaaurv阵leartomatrix
b
b1(1) ...
bn(1)
Step 1：设a1(11) ，0计算因子
mi1
a (1) i1
/
a (1) 11
(i 2, ..., n)
将增广矩阵/* augmented matrix */ 第 i 行 mi1 第1行，
得到
a (1) 11
a (1) 12
...
a (1) 1n
A( 2 )
ank
注：稳定性介于列主元法和全主元法之间。
§2 三角分解法 /* Matrix Factorization */
➢ 高斯消元法的矩阵形式 /* Matrix Form of G.E. */：
Step 1: mi1 ai1 / a11 (a11 0)
1
记 L1 =
m21 ...
1
mn1
，则 L1[ A(1)
b1(1) b (2)
其中
a(2) ij
b(2) i
a (1) ij
b(1) i
m
i
a (1)
1 1j
mi1b1(1)
(i, j 2, ...,n)
Step
k：设
a
(k kk
)
， 0计算因子
且计算
a ( k 1) ij
b( k 1) i
a(k) ij
b(k ) i
mik
a(k kj
)
s若ubAm的at所ric有eWWtsshas顺mhesh*ko( ii/oaaa)lN序fku均iltltN-nolutteiiio主hdfft0o不suioanautrs,n子onni为n(uia(iiennniqwnic)e)xtq式u0hdexiuwesg，ikiest0i0ne/stt*?hrt则s.??ed.ktreh高ctehei斯ariwm-ntih消gitnhea元nt无of需le换adi行ng即可
省去换列的步骤，每次仅选一列中最大的元。
| aik ,k
|
max
kin
|
aik
|
0
§1 Gaussian Elimination – Pivoting Strategies
例：
109
1
1 1
1 2
1 109
1 1
2 1
1 0
1 1
2 1
x2 1 , x1 1 ✓
注：列主元法没有全主元法稳定。
优选数值分析第三章解线性方 程组的直接方法
求解
A
x
b
➢ 高斯消元法：
思 首先将A化为上三角阵 /* upper-triangular matrix */， 路 再回代求解 /* backward substitution */。
=
消元
记
A(1) A (ai(j1) )nn ,
b (1)
① 选取 | aik jk源自|maxki, jn
|
aij
|
0;
② If ik k then 交换第 k 行与第 ik 行; If jk k then 交换第 k 列与第 jk 列;
③ 消元
注：列交换改变了 xi 的顺序，须记录交换次序，解完后再 换回来。
列主元消去法 /* Partial Pivoting, or maximal column pivoting */
bb12((12))
...
bn(n)
§1 Gaussian Elimination – The Method
回代
xn
b(n) n
/
a(n) nn
n
b( i ) i
a(i ij
)
x
j
xi
j i 1
a(i) ii
(i n 1, ...,1)
定理
principal
TWhheantwifewmeucsatnf’itnd the
进行到底，得到唯r一ow解. 。
注：消事元实及上行，交只换要d，eAt(将A非i 方)奇程异a.1.组1.，化即.. .. ..为Aa.三.1.i1 角存形在方，程则组可，通求过出逐唯次
一解。
ai1 ... aii
定理（矩阵的 LU分解） 设A为n阶矩阵，如果A的顺序主子式Di 0(i 1, 2, , n 1)， 则A可分解为一个下三角矩阵L和一个上三角矩阵U的乘积， 且这种分解是唯一的.
例：11
109 1
109
2
1 0
109 109
109
109
x2 1 ,
x1
0
标度化列主元消去法 /* Scaled Partial Pivoting */
对算每一一次行。计以算后每s注i一意数步m1：学考ja这上x虑n |两严子a个格ij列|方等。a程价为...kk 组。省中在时as间iik 最，s大i 只的在ai初k 为始主时元计。