线性方程组的解法教案课件

线性方程组的解法线性方程组的解法1线性方程组的解法在计算数学中占有极其重要的地位。线性方程组的解法大致分为迭代法与直接法两大类雅可比(Jacobi)迭代法举例说明雅可比迭代法的基本思路例4.1特点:系数矩阵主对角元均不为零第1页/共39页线性方程组的解法在计算数学中占有极其重要的地位。雅可比(Ja2取迭代初值x1(0)=0，x2(0)=0，x3(0)=0将方程改写成如下等价形式据此建立迭代公式第2页/共39页取迭代初值x1(0)=0，x2(0)=0，x3(0)3x(0)000x(1)

0.77780.80000.8667x(2)0.96300.96440.9778x(3)0.99290.99350.9952x(4)········0.99870.99880.9991x1*＝1.0000，x2*＝1.0000，x3*＝1.0000准确解可以看出，迭代每前进一步，结果就逼近准确解一步

迭代过程收敛第3页/共39页x(0)x(1)x(2)x(3)4矩阵形式:以上这种迭代方法称雅可比(Jacobi)迭代法。基本思想：将方程组的求解问题转化为重复计算一组彼此独立的线性表达式。第4页/共39页矩阵形式:以上这种迭代方法称雅可比(Jacobi)迭代法。5(i=1,2,···,n;k=0,1,2,···)(i=1,2,···,n)设有方程组将第i个方程的第i个变量xi分离出来，据此建立分量形式的雅可比迭代公式如果第5页/共39页(i=1,2,···,n;k=0,1,2,···)6用矩阵形式来表示雅可比迭代公式设有方程组:AX=b其中A＝(aij)n为非奇异矩阵，X=(x1,x2,···,xn)T,b=(b1,b2,···,bn)T，唯一解为X*=(x1*,x2*,···,xn*)T将A分解为：A＝U+D+L其中第6页/共39页用矩阵形式来表示雅可比迭代公式设有方程组:AX7于是(U+D+L)X=b得X＝－D－(U+L)X+D－b据此得矩阵形式的雅可比迭代公式

X(k+1)＝－D－(U+L)X(k)+D－b记B＝－D－(U+L)，f＝D－b有B：迭代矩阵(k=0,1,2,······)X(k+1)=BX(k)+f任取X(0),迭代计算产生向量序列:若则迭代过程收敛。x*是方程组Ax=b

的解X(1),X(2),······,X(k),······第7页/共39页于是(U+D+L)X=b(k=0,1,28第8页/共39页第8页/共39页9迭代法适用于解大型稀疏方程组(万阶以上的方程组,系数矩阵中零元素占很大比例,而非零元按某种模式分布)背景:电路分析、边值问题的数值解和数学物理方程问题:(1)如何构造迭代格式？

(2)迭代格式是否收敛？

(3)收敛速度如何？

(4)如何进行误差估计？第9页/共39页迭代法适用于解大型稀疏方程组(万阶以上的方程组,系数矩阵中零10高斯塞德尔Gauss-Seidel迭代法Gauss-Seidel迭代法是通过对Jacobi迭代法稍加改进得到的。Jacobi迭代法的每一步迭代新值

x(k+1)=[x1(k+1),x2(k+1),

···,xn(k+1)]T

都是用前一步的旧值

x(k)=[x1(k),x2(k),

···,xn(k)]T的全部分量计算出来的。那么在计算第i个分量xi(k+1)时，已经计算出

x1(k+1),x2(k+1),···,xi-1(k+1)(i-1)个分量，这些分量新值没用在计算xi(k+1)上。将这些第10页/共39页高斯塞德尔Gauss-Seidel迭代法Gauss-Seid11(i=1,2,…,n)(i=1,2,···,n;k=0,1,2,···)将这些分量利用起来，有可能得到一个收敛更快的迭代公式。具体作法：将分量形式的雅可比迭代公式右端前(i-1)个分量的上标为k换成k+1，即分量形式的高斯-塞德尔迭代公式。第11页/共39页(i=1,2,…,n)(i=1,2,···,n;k12用矩阵形式来表示高斯-塞德尔迭代公式DX(k+1)＝b-LX(k+1)-UX(k)即(D+L)X(k+1)＝-UX(k)+b如果(D+L)－存在，则

X(k+1)＝－(D+L)－UX(k)+

(D+L)－b记B＝(D+L)－，f＝(D+L)－b则(k=0,1,2,···)X(k+1)=BX(k)+f矩阵形式的高斯-塞德尔迭代公式。B：迭代矩阵第12页/共39页用矩阵形式来表示高斯-塞德尔迭代公式DX(k+1)＝b-LX13例第13页/共39页例第13页/共39页14例第14页/共39页例第14页/共39页15第15页/共39页第15页/共39页16Jacobi迭代算法A=[9-1-1;-110-1;-1-115];b=[7;8;13];x=[0;0;0];er=1;k=0;whileer>0.00005er=0;k=k+1;fori=1:3s=0;t=x(i);x(i)=0;forj=1:3s=s+A(i,j)*x(j);endx(i)=t;y(i)=(b(i)-s)/A(i,i);er=max(abs(x(i)-y(i)),er);endx=y;x'end0.77780.80000.86670.96300.96440.97190.99290.99350.99520.99870.99880.99910.99980.99980.99981.00001.00001.00001.00001.00001.0000第16页/共39页Jacobi迭代算法A=[9-1-1;-110-1;17Gauss-Seidel迭代算法A=[9-1-1;-110-1;-1-115];b=[7;8;13];x=[0;0;0];er=1;k=0;whileer>0.00005er=0;k=k+1;fori=1:3s=0;t=x(i);x(i)=0;forj=1:3s=s+A(i,j)*x(j);endx(i)=(b(i)-s)/A(i,i);er=max(abs(x(i)-t),er);endx'end0.77780.87780.97700.98390.99610.99870.99940.99980.99991.00001.00001.00001.00001.00001.0000第17页/共39页Gauss-Seidel迭代算法A=[9-1-1;-118从计算结果可以明显看出，Gauss-Seidel迭代法比Jacobi迭代法效果好。一般而言，Gauss-Seidel迭代法收敛速度比Jacobi迭代法快，但这两种迭代法的收敛范围并不完全重合，而只是部分相交，有的时候Jacobi迭代法可能比Gauss-Seidel迭代法收敛速度更快。甚至可以举出Jacobi迭代法收敛而Gauss-Seidel迭代法发散的例子。第18页/共39页从计算结果可以明显看出，Gauss-Seidel迭代法比Ja19Gauss-Seidel迭代法和Jacobi迭代法的异同：Jacobi迭代法：公式简单，每次只需做矩阵和向量的一次乘法；特别适合于并行计算；不足之处：需存放X(k)和X(k+1)两个存储空间。Gauss-Seidel迭代法：只需一个向量存储空间，一旦计算出了xj(k+1)立即存入xj(k)的位置，可节约一套存储单元；有时起到加速收敛的作用。是一种典型的串行算法，每次迭代中必须依次计算解的各个分量。第19页/共39页Gauss-Seidel迭代法和Jacobi迭代法的异同：第20超松驰(SOR)迭代法超松驰迭代法是迭代方法的一种加速方法，其计算公式简单，但需要选择合适的松驰因子，以保证迭代过程有较快的收敛速度。设有方程组

AX=b其中A＝(aij)n为非奇异矩阵，X=(x1,x2,···,xn)T,b=(b1,b2,···,bn)T，记X(k)为第k步迭代近似值，则

r(k)=b－AX(k）表示近似解X(k)的残余误差，引进如下形式的加速迭代公式第20页/共39页超松驰(SOR)迭代法超松驰迭代法是迭代方法的一种加速方法，21X(k+1)＝X(k)+w(b－AX)w称作松驰因子。其分量形式为选择适当的松驰因子，可期望获得较快的收敛速度。如果在计算分量xi(k+1)时，考虑利用已经计算出来的分量x1(k+1),x2(k+1),···,xi-1(k+1)，又可得到一个新的迭代公式特别当aii≠0时，将上面迭代公式应用于方程组(i=1,2,···,n)第21页/共39页X(k+1)＝22由此得下列超松驰(SOR)迭代公式(i=1,2,···,n;k=0,1,2,3,··········)当w>1时，称超松驰法；当w<1时，称低松驰法；当w＝1时，就是Gauss-Seidel迭代公式。所以超松驰(SOR)迭代法可以看成是Gauss-Seidel迭代法的加速，而Gauss-Seidel迭代法是超松驰方法的特例。第22页/共39页由此得下列超松驰(SOR)迭代公式(i=1,2,···,n23定理4.8

若A是对称正定矩阵,则当0<w<2时SOR迭代法解方程组Ax=b是收敛的定理4.9

若A是严格对角占优矩阵,则当0<w<1时SOR迭代法解方程组Ax=b

是收敛的第23页/共39页定理4.8若A是对称正定矩阵,则当0<w<2时SOR迭代24例4.3用SOR方法解方程组(w=1.4)w=input('input:w:=');A=[2-10;-12-1;0-12];b=[1;0;1.8];x=[1;1;1];er=1;k=0;whileer>0.0005er=0;k=k+1;fori=1:3s=0;t=x(i);x(i)=0;forj=1:3s=s+A(i,j)*x(j);endx(i)=(1-w)*t+w*(b(i)-s)/A(i,i);er=max(abs(x(i)-t),er);endendkk=10x=1.19991.39991.5999ω=1.2,只需k=6第24页/共39页例4.3用SOR方法解方程组(w=1.4)w=input25

块迭代法简介设A∈Rn×n,x∈Rn,b∈Rn将方程组Ax=b中系数矩阵A分块其中,Aii∈Rni×ni,Aij∈Rni×nj

,xi∈Rni,bi∈Rni第25页/共39页块迭代法简介其中,26将A分解,A=DB–LB–UB

Jacobi块迭代

DBx(k+1)=(LB+UB)x(k)+bi=1,2,···,r(2)Gauss-Seidel块迭代

DBx(k+1)=LBx(k+1)+UBx(k)+bi=1,2,···,r第26页/共39页将A分解,A=DB–LB–UBJacobi块27迭代法的收敛性Convergenceofiterativemethod迭代矩阵谱半径Spectralradius对角占优矩阵diagonallydominantmatrix

第27页/共39页迭代法的收敛性第27页/共39页28原始方程:Ax=b迭代格式:x(k+1)=Bx(k)+f定理4.1(迭代法基本定理)迭代法x(k+1)=Bx(k)+f收敛的充要条件是

ρ(B)<1迭代法有着算法简单，程序设计容易以及可节省计算机存贮单元等优点。但是迭代法也存在着收敛性和收敛速度等方面的问题。因此弄清楚迭代法在什么样的条件下收敛是至关重要的。第28页/共39页原始方程:Ax=b迭代格式:x(k+1)=29证对任何n阶矩阵B都存在非奇矩阵P使

B=P–1JP其中,J

为B的Jordan标准型其中,Ji

为Jordan块其中,λi

是矩阵B的特征值,由B=P–1JP第29页/共39页证对任何n阶矩阵B都存在非奇矩阵P使其中,Ji30Bk=(P–1JP)(P–1JP)···(P–1JP)=P–1JkP迭代法x(k+1)=Bx(k)+f收敛<=>(i=1,2,···,r)(i=1,2,···,r)谱半径(B)<1第30页/共39页Bk=(P–1JP)(P–1JP)··31例线性方程组Ax=b,分别取系数矩阵为试分析Jacobi迭代法和Seidel迭代法的敛散性(1)第31页/共39页例线性方程组Ax=b,分别取系数矩阵为试分析32(2)A2=[2,-1,1;1,1,1;1,1,-2]第32页/共39页(2)A2=[2,-1,1;1,1,1;33两种迭代法之间没有直接联系对矩阵A1,求A1x=b

的Jacobi迭代法收敛,而Gauss-Seidel迭代法发散;对矩阵A2,求A2x=b

的Jacobi迭代法发散,而Gauss-Seidel迭代法收敛.第33页/共39页两种迭代法之间没有直接联系第33页/共39页34证由(k)=B(k-1),得

||(k)||≤||B||||(k-1)||

(k=1,2,3,······)所以定理4.2(迭代收敛的充分条件)设有迭代公式x(k+1)=Bx(k)+f，如果||B||<1,则对任意初始向量x(0)和任意f，迭代公式收敛。||(k)||≤||B||k||(0)||

||B||<1第34页/共39页证由(k)=B(k-1),得所以定理4.2(迭35定义4.1A=(aij)n×n,如果则称A为严格对角占优阵.例4.19>|-1|+|-1|10>|-1|+|-1|15>|-1|+|-1||a11|>|a12|+|a13||a22|>|a21|+|a23||a33|>|a31|+|a32|第35页/共39页定义4.1A=(aij)n×n,如果例4.19>36定理4.3

若Ax=b的系数矩阵A是严格对角占优矩阵,则Jacobi迭代和Seidel迭代均收敛证由于矩阵A严格对角占优由A矩阵构造Jacobi迭代矩阵BJ=D-1(D–A)

第i行绝对值求和所以第36页/共39页定理4.3若Ax=b的系数矩阵A是严格对角占优矩阵,则Ja37例4.2试对下列方程组建立收敛的迭代公式解通过观察可发现这个方程组的系数矩阵不是对角占优的。但经行交换后可得下列等价形式此等价形式的系数矩阵是严格对角占优阵，据此建立的雅可比迭代公式和高斯－塞德尔迭代公式收敛。第37页/共39页例4.2试对下列方程组建立收敛的迭代公式解通过观察可发现38收敛速度：称R(B)=-ln(B)为迭代法的渐进收敛速度简称收敛速度。第38页/共39页收敛速度：称R(B)=-ln(B)为迭代法的渐进收敛速度39线性方程组的解法线性方程组的解法40线性方程组的解法在计算数学中占有极其重要的地位。线性方程组的解法大致分为迭代法与直接法两大类雅可比(Jacobi)迭代法举例说明雅可比迭代法的基本思路例4.1特点:系数矩阵主对角元均不为零第1页/共39页线性方程组的解法在计算数学中占有极其重要的地位。雅可比(Ja41取迭代初值x1(0)=0，x2(0)=0，x3(0)=0将方程改写成如下等价形式据此建立迭代公式第2页/共39页取迭代初值x1(0)=0，x2(0)=0，x3(0)42x(0)000x(1)

0.77780.80000.8667x(2)0.96300.96440.9778x(3)0.99290.99350.9952x(4)········0.99870.99880.9991x1*＝1.0000，x2*＝1.0000，x3*＝1.0000准确解可以看出，迭代每前进一步，结果就逼近准确解一步

迭代过程收敛第3页/共39页x(0)x(1)x(2)x(3)43矩阵形式:以上这种迭代方法称雅可比(Jacobi)迭代法。基本思想：将方程组的求解问题转化为重复计算一组彼此独立的线性表达式。第4页/共39页矩阵形式:以上这种迭代方法称雅可比(Jacobi)迭代法。44(i=1,2,···,n;k=0,1,2,···)(i=1,2,···,n)设有方程组将第i个方程的第i个变量xi分离出来，据此建立分量形式的雅可比迭代公式如果第5页/共39页(i=1,2,···,n;k=0,1,2,···)45用矩阵形式来表示雅可比迭代公式设有方程组:AX=b其中A＝(aij)n为非奇异矩阵，X=(x1,x2,···,xn)T,b=(b1,b2,···,bn)T，唯一解为X*=(x1*,x2*,···,xn*)T将A分解为：A＝U+D+L其中第6页/共39页用矩阵形式来表示雅可比迭代公式设有方程组:AX46于是(U+D+L)X=b得X＝－D－(U+L)X+D－b据此得矩阵形式的雅可比迭代公式

X(k+1)＝－D－(U+L)X(k)+D－b记B＝－D－(U+L)，f＝D－b有B：迭代矩阵(k=0,1,2,······)X(k+1)=BX(k)+f任取X(0),迭代计算产生向量序列:若则迭代过程收敛。x*是方程组Ax=b

的解X(1),X(2),······,X(k),······第7页/共39页于是(U+D+L)X=b(k=0,1,247第8页/共39页第8页/共39页48迭代法适用于解大型稀疏方程组(万阶以上的方程组,系数矩阵中零元素占很大比例,而非零元按某种模式分布)背景:电路分析、边值问题的数值解和数学物理方程问题:(1)如何构造迭代格式？

(2)迭代格式是否收敛？

(3)收敛速度如何？

(4)如何进行误差估计？第9页/共39页迭代法适用于解大型稀疏方程组(万阶以上的方程组,系数矩阵中零49高斯塞德尔Gauss-Seidel迭代法Gauss-Seidel迭代法是通过对Jacobi迭代法稍加改进得到的。Jacobi迭代法的每一步迭代新值

x(k+1)=[x1(k+1),x2(k+1),

···,xn(k+1)]T

都是用前一步的旧值

x(k)=[x1(k),x2(k),

···,xn(k)]T的全部分量计算出来的。那么在计算第i个分量xi(k+1)时，已经计算出

x1(k+1),x2(k+1),···,xi-1(k+1)(i-1)个分量，这些分量新值没用在计算xi(k+1)上。将这些第10页/共39页高斯塞德尔Gauss-Seidel迭代法Gauss-Seid50(i=1,2,…,n)(i=1,2,···,n;k=0,1,2,···)将这些分量利用起来，有可能得到一个收敛更快的迭代公式。具体作法：将分量形式的雅可比迭代公式右端前(i-1)个分量的上标为k换成k+1，即分量形式的高斯-塞德尔迭代公式。第11页/共39页(i=1,2,…,n)(i=1,2,···,n;k51用矩阵形式来表示高斯-塞德尔迭代公式DX(k+1)＝b-LX(k+1)-UX(k)即(D+L)X(k+1)＝-UX(k)+b如果(D+L)－存在，则

X(k+1)＝－(D+L)－UX(k)+

(D+L)－b记B＝(D+L)－，f＝(D+L)－b则(k=0,1,2,···)X(k+1)=BX(k)+f矩阵形式的高斯-塞德尔迭代公式。B：迭代矩阵第12页/共39页用矩阵形式来表示高斯-塞德尔迭代公式DX(k+1)＝b-LX52例第13页/共39页例第13页/共39页53例第14页/共39页例第14页/共39页54第15页/共39页第15页/共39页55Jacobi迭代算法A=[9-1-1;-110-1;-1-115];b=[7;8;13];x=[0;0;0];er=1;k=0;whileer>0.00005er=0;k=k+1;fori=1:3s=0;t=x(i);x(i)=0;forj=1:3s=s+A(i,j)*x(j);endx(i)=t;y(i)=(b(i)-s)/A(i,i);er=max(abs(x(i)-y(i)),er);endx=y;x'end0.77780.80000.86670.96300.96440.97190.99290.99350.99520.99870.99880.99910.99980.99980.99981.00001.00001.00001.00001.00001.0000第16页/共39页Jacobi迭代算法A=[9-1-1;-110-1;56Gauss-Seidel迭代算法A=[9-1-1;-110-1;-1-115];b=[7;8;13];x=[0;0;0];er=1;k=0;whileer>0.00005er=0;k=k+1;fori=1:3s=0;t=x(i);x(i)=0;forj=1:3s=s+A(i,j)*x(j);endx(i)=(b(i)-s)/A(i,i);er=max(abs(x(i)-t),er);endx'end0.77780.87780.97700.98390.99610.99870.99940.99980.99991.00001.00001.00001.00001.00001.0000第17页/共39页Gauss-Seidel迭代算法A=[9-1-1;-157从计算结果可以明显看出，Gauss-Seidel迭代法比Jacobi迭代法效果好。一般而言，Gauss-Seidel迭代法收敛速度比Jacobi迭代法快，但这两种迭代法的收敛范围并不完全重合，而只是部分相交，有的时候Jacobi迭代法可能比Gauss-Seidel迭代法收敛速度更快。甚至可以举出Jacobi迭代法收敛而Gauss-Seidel迭代法发散的例子。第18页/共39页从计算结果可以明显看出，Gauss-Seidel迭代法比Ja58Gauss-Seidel迭代法和Jacobi迭代法的异同：Jacobi迭代法：公式简单，每次只需做矩阵和向量的一次乘法；特别适合于并行计算；不足之处：需存放X(k)和X(k+1)两个存储空间。Gauss-Seidel迭代法：只需一个向量存储空间，一旦计算出了xj(k+1)立即存入xj(k)的位置，可节约一套存储单元；有时起到加速收敛的作用。是一种典型的串行算法，每次迭代中必须依次计算解的各个分量。第19页/共39页Gauss-Seidel迭代法和Jacobi迭代法的异同：第59超松驰(SOR)迭代法超松驰迭代法是迭代方法的一种加速方法，其计算公式简单，但需要选择合适的松驰因子，以保证迭代过程有较快的收敛速度。设有方程组

AX=b其中A＝(aij)n为非奇异矩阵，X=(x1,x2,···,xn)T,b=(b1,b2,···,bn)T，记X(k)为第k步迭代近似值，则

r(k)=b－AX(k）表示近似解X(k)的残余误差，引进如下形式的加速迭代公式第20页/共39页超松驰(SOR)迭代法超松驰迭代法是迭代方法的一种加速方法，60X(k+1)＝X(k)+w(b－AX)w称作松驰因子。其分量形式为选择适当的松驰因子，可期望获得较快的收敛速度。如果在计算分量xi(k+1)时，考虑利用已经计算出来的分量x1(k+1),x2(k+1),···,xi-1(k+1)，又可得到一个新的迭代公式特别当aii≠0时，将上面迭代公式应用于方程组(i=1,2,···,n)第21页/共39页X(k+1)＝61由此得下列超松驰(SOR)迭代公式(i=1,2,···,n;k=0,1,2,3,··········)当w>1时，称超松驰法；当w<1时，称低松驰法；当w＝1时，就是Gauss-Seidel迭代公式。所以超松驰(SOR)迭代法可以看成是Gauss-Seidel迭代法的加速，而Gauss-Seidel迭代法是超松驰方法的特例。第22页/共39页由此得下列超松驰(SOR)迭代公式(i=1,2,···,n62定理4.8

若A是对称正定矩阵,则当0<w<2时SOR迭代法解方程组Ax=b是收敛的定理4.9

若A是严格对角占优矩阵,则当0<w<1时SOR迭代法解方程组Ax=b

是收敛的第23页/共39页定理4.8若A是对称正定矩阵,则当0<w<2时SOR迭代63例4.3用SOR方法解方程组(w=1.4)w=input('input:w:=');A=[2-10;-12-1;0-12];b=[1;0;1.8];x=[1;1;1];er=1;k=0;whileer>0.0005er=0;k=k+1;fori=1:3s=0;t=x(i);x(i)=0;forj=1:3s=s+A(i,j)*x(j);endx(i)=(1-w)*t+w*(b(i)-s)/A(i,i);er=max(abs(x(i)-t),er);endendkk=10x=1.19991.39991.5999ω=1.2,只需k=6第24页/共39页例4.3用SOR方法解方程组(w=1.4)w=input64

块迭代法简介设A∈Rn×n,x∈Rn,b∈Rn将方程组Ax=b中系数矩阵A分块其中,Aii∈Rni×ni,Aij∈Rni×nj

,xi∈Rni,bi∈Rni第25页/共39页块迭代法简介其中,65将A分解,A=DB–LB–UB

Jacobi块迭代

DBx(k+1)=(LB+UB)x(k)+bi=1,2,···,r(2)Gauss-Seidel块迭代

DBx(k+1)=LBx(k+1)+UBx(k)+bi=1,2,···,r第26页/共39页将A分解,A=DB–LB–UBJacobi块66迭代法的收敛性Convergenceofiterativemethod迭代矩阵谱半径Spectralradius对角占优矩阵diagonallydominantmatrix

第27页/共39页迭代法的收敛性第27页/共39页67原始方程:Ax=b迭代格式:x(k+1)=Bx(k)+f定理4.1(迭代法基本定理)迭代法x(k+1)=Bx(k)+f收敛的充要条件是

ρ(B)<1迭代法有着算法简单，程序设计容易以及可节省计算机存贮单元等优点。但是迭代法也存在着收敛性和收敛速度等方面的问题。因此弄清楚迭代法在什么样的条件下收敛是至关重要的。第28页/共39页原始方程:Ax=b迭代格式:x(k+1)=68证对任何n阶矩阵B都存在非奇矩阵P使

B=P–1