计算方法3线性方程组数值解法

12学习要点消去法：包括高斯顺序消去法和列主元高斯消去法；三对角方程组的追赶法；各种向量范数和矩阵范数的概念；解线性方程组的迭代法：Jacobi迭代法；Gauss-Seidel迭代法；迭代法的收敛性判断；33.1问题的提出在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组。例如:建筑工程中的结构力学问题;用最小二乘法求实验数据的曲线拟合问题;用差分法或者有限元法解常微分方程，偏微分方程边值问题等都导致求解线性方程组而且后面几种情况常常归结为求解大型线性方程组。4线性代数方面的计算方法就是研究求解线性方程组的一些数值解法与研究计算矩阵的特征值及特征向量的数值方法。5

式中，aij，bi为已知常数，xi为待求的未知量。记设有线性方程组6

则式（3.1）可写出矩阵形式Ax=b

也可以把式（3.1）写成增广矩阵形式7关于线性方程组的数值解法一般有两类：直接法：经过有限步算术运算，可求得方程组的精确解的方法（若在计算过程中没有舍入误差）迭代法：用某种极限过程去逐步逼近线性方程组精确解的方法，迭代法具有占存储单元少，程序设计简单，原始系数矩阵在迭代过程中不变等优点，但存在收敛性及收敛速度等问题83.2消去法一上三角方程组的解法设9写出矩阵形式为：Ux=y其中U称为上三角矩阵10若uii≠0（i=1,2,……n）,则由下至上依次回代得11二高斯消去法其中aij(1)=aij,ai,n+1(1)=bi1≤i,j≤n1、第1步消元。设a11(1)≠0,将的第一行乘以-li1(li1=ai1(1)/a11(1))，加到i行记原线性方程组为12其中

aij(2)=aij(1)-li1a1j(1)

，2≤i≤n；2≤j≤n+1

得到同解方程组13

从运算过程来看，上面相当于用矩阵左乘即

14若已经进行了k-1步次消元，同解方程组为：15其中，

aij(k+1)=aij(k)-likakj(k)

，k+1≤i≤n；k+1≤j≥n+1第k步消元：16即

第k步消元，也相当于用矩阵左乘17

一直作到n-1步，得到同解方程组记则线性方程组为

：Ux=y18

例1用高斯消去法解线性方程组19解：20因此得到与原方程同解的三角方程组为通过回代，可以得到解为：X3=-3, x2=2, x1=121三列主元高斯消去法

≠0（k=1,2,……n-1）;若很小，也不适用；高斯消去法的问题：列主元消去法：与高斯消去法相似；防止舍入误差的增长；选列主元，进行行交换。22具体过程：设k-1步消元得到：23在进行第k步消元前，选出第k列中位于对角线及其以下元素绝对值中的最大值者，即确定t使得将第t行和第k行互相交换；再按高斯消去法进行第k步消元；若系数矩阵为对称正定或严格对角占优的方程组，不必选主元24

例2用列主元高斯消去法解线性方程组253.3追赶法其系数矩阵为三对角形，元素满足以下条件：|b1|>|c1|>0|bi|≥|ai|+|ci|，且aici≠0i=2，3，……n-1;|bn|≥|an|>0。可以采用追赶法求解26消元过程:追赶273.4向量范数和矩阵范数为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对Rn(n维向量空间)中的向量或Rnxn中矩阵的“大小”引入一种度量——向量和矩阵的范数。28向量范数对空间直角坐标系任意向量其长度为：29它满足如下3个条件

对任意x属于R3，|x|≥0，|x|=0当且仅当x=0;

对任意常数c属于R和任意x属于R3，有|cx|=|c|·|x|;对任意x属于R3，y属于R3，有|x+y|≤|x|+|y|;这三个条件分别称为向量长度的非负性、齐次性和三角不等式，推广此概念即可得到向量范数30定义

设f(x)=||x||是定义在Rn上的实函数，如果它满足如下条件：1对对任意x属于Rn，||x||≥0，||x||=0当且仅当x=0;2对任意实常数c和任意x属于Rn，有||cx||=|c|·||x||;3对任意x属于Rn，y属于Rn，有 ||x+y||≤||x||+||y||;

则称||·||为Rn上的向量范数31

最常用的是三种范数：向量的1-范数：向量的2-范数：向量的∞-范数：示例(-5，-3，4)T的三种范数分别为：32定义设向量x,y属于Rn上，则称||x-y||为x和y之间的距离三种范数之间的关系33矩阵范数定义:

设A属于Rn×n，||·||是Rn上的任一向量范数，称为A的矩阵范数，记作Rn×n表示所有n×n阶矩阵组成的实线性空间。34

最常用的三种矩阵范数：35矩阵范数的五个性质：36定理:设A∈R，||·||为一种矩阵范数，则ρ(A)≤||A||证明：设λ为A的按模最大的特征值，x为相对应的特征向量，则37例5设A=

383.5迭代法迭代法及其收敛性思路：与方程求根的迭代法思想类似，对于线性方程组：39通过变形，找到同解方程组：x=Bx+f建立迭代公式x(k+1)=Bx(k)+f若给定初始向量x(0)，就可以按迭代公式解出向量序列{x(k)}40定义：

设x(0)，x(1)，x(2),……是Rn中的一个向量序列，c属于Rn是一个常向量。如果迭代矩阵则称向量序列收敛于c，并记为如果向量序列{x(k)}收敛于x*，对迭代函数两边取极限，得

x*=Bx*+f41定理(充分条件)：对给定方程组x=Bx+f，如果||B||<1，则（1）此方程组有唯一解x*;（2）对任意向量x(0)属于Rn，迭代格式x(k+1)=Bx(k)+f收敛于x*,且有||x(k+1)–x*||≤||B||||x(k)–x*||

k=0,1,2……（3）（4）42定理3.3

：对给定方程组x=Bx+f，迭代格式x(k+1)=Bx(k)+f对任意的初始值x(0)都收敛的充要条件为ρ(B)<1例

用迭代法解线性方程组43雅可比（Jacobi）迭代法由以下方程组的第i个方程解出xi(i=1,2……n),44得到一个同解的方程组,取初始向量x(0)=(x1(0),x2(0)x……

xn(0))T,利用迭代式反复迭代可以得到一个向量序列{x(k)}，称为雅可比迭代格式，称用此迭代格式求解方程组的方法为雅可比迭代法45可以将矩阵A分解为其中A=LUD46雅可比迭代格式的表达式为

Jacobi

迭代阵迭代矩阵称为雅可比矩阵47例

用雅可比迭代法求解线性方程组，并分析迭代格式的收敛性48高斯-赛德尔（Gauss-Seidel）迭代法在雅可比迭代中，用新值及时取代旧值，即在求xi(k+1)时，用x1(k+1)，x2(k+1)，x3(k+1)，……

xi-1(k+1)进分别代替x1(k)，x2(k)，x3(k)，……

xi-1(k)行进行迭代计算49矩阵表示形式为G就被称为高斯-赛德尔迭代矩阵50例

用高斯-赛德尔迭代法求