数值分析课件第四章线性方程组的迭代解法优秀课件

数值分析课件第四章线性方程组的迭代解法向量和矩阵的范数Jacobi迭代法Gauss－Seidel迭代法迭代法的收敛性松弛迭代法（基于G-S的加速收敛方法）误差分析第四章线性方程组的迭代解法引言特点：该方法具有对计算机的存贮单元需求少，程序设计简单、原始系数矩阵在计算过程中不变等优点，是求解大型稀疏矩阵方程组的重要方法．4.1向量和矩阵的范数向量的范数矩阵的范数矩阵基础知识回顾向量的范数证明（2）:所以证明（1）:所以所以证明（3）:矩阵的范数矩阵特征值

设A是n阶方阵，如果存在常数λ和n维非零列向量x使下式成立基础知识回顾则̀λ称为矩阵A的特征值，x称为A对应于特征值λ的特征向量，上式还可写为。关于这个n维其次线性方程组有非零解的充分必要条件是2.矩阵求逆

（初等行变换法）2.矩阵求逆

（伴随矩阵法）其中A*为A的代数余子式每一项代数余子式的符号为-1^(i+j)迭代法的基本思想：例：求解方程组其精确解是x*=(3,2,1)T。现将原方程组改写为简写为x=B0x+f，其中任取初始值，如取x(0)=(0,0,0)T，代入x=B0x+f右边，若等式成立则求得方程组的解，否则，得新值x(1)=(x1(1),x2(1),x3(1))T=(2.5,3,3)T，再将x(1)代入，反复计算，得一向量序列{x(k)}和一般的计算公式（迭代公式）：简写为x(k+1)=B0x(k)+f

k=0,1,2,……x(10)=(3.000032,1.999838,0.999813)T迭代到第10次时有||ε(10)||

∞=||x(10)–x*||=0.000187定义：（1）对于给定方程组x=Bx+f，用迭代公式x(k+1)=Bx(k)+f

(k=0,1,2,……)逐步代入求近似解的方法称迭代法；（2）若k∞时limx(k)存在（记为x*），称此迭代法收敛，显然x*就是方程组的解，否则称迭代法发散；（3）B称为迭代矩阵。问题：

如何建立迭代格式？

收敛速度？

向量序列的收敛条件？

误差估计？若A非奇异，且对角元不为零，将原方程组改写为4.2Jacobi迭代法4.3Gauss－Seidel迭代法4.4迭代法的收敛性设求解线性方程组的迭代格式为将上面两式相减,得而方程组的精确解为x*，则则取范数当即且越小，的速度就越快。定理：设x*为方程组Ax=b的解，若||B||<1,则 对迭代格式x(k+1)=Bx(k)+f

，有（1）（2）证由||B||<1,有所以||x(k+1)–x*||≤||B||||x(k)–x*||x(k+1)–x*=(Bx(k)+f)–(Bx*+f)=B(x(k)–x*

)||x(k)–x*||=||(x(k)–x(k+1))+(x(k+1)–x*)||≤||x(k)–x(k+1)||+||x(k+1)–x*||≤||x(k)–x(k+1)||+||B||||x*–

x(k)||

=

||x(k+1)–x(k)||+||B||||x(k)–x*||所以x(k+1)–x(k)=(Bx(k)–f)–(Bx(k-1)–f)=B(x(k)–x(k-1)

)||x(k+1)–x(k)||≤||B||||x(k)–x(k-1)||故可得误差估计式:注：

（1）式说明，只要||B||不是很接近1，当x(k+1)

和x(k)

很接近时，x(k)

也越接近x*，故可用||

x(k+1)

-x(k)

||中止迭代。（2）式说明，||B||越小，x(k)

收敛越快，可作误差估计式。定理：迭代格式收敛的充要条件为迭代矩阵的谱半径(B)<1。证:对任何n阶矩阵B，都存在非奇异矩阵P，使

B=P–1JP其中，J为B的Jordan标准型。其中,Ji

为Jordan块其中λi

是矩阵B的特征值，由B=P–1JPBk=(P–1JP)(P–1JP)···(P–1JP)=P–1JkP迭代法x(k+1)=Bx(k)+f

收敛<=>谱半径(B)<1注：(B)≤||B||，且当B为对称阵时，即AT=A，(B)=||B||2。例3.判别下列方程组用Jacobi法和Gauss-Seidel法求解是否收敛:解:(1)求Jacobi法的迭代矩阵所以即Jacobi迭代法收敛。(2)求Gauss-Seidel法的迭代矩阵：显然BJ的几种常用算子范数||BJ||>1，故用其特征值判断。所以Gauss-Seidel迭代法发散。注：本例说明Gauss-Seidel迭代法发散时而Jacobi迭代法却收敛，因此，不能说Gauss-Seidel迭代法比Jacobi迭代法更好。可得故定义设A=(aij

)n×n

Rn×n

，若

(i=1,2,…,n)，则称A为对角占优矩阵，若不等式严格成立，则称A为严格对角占优矩阵。迭代法收敛的其他结论：定理若Ax=b中A为严格对角占优矩阵，则Jacobi迭代和Gauss－Seidel迭代均收敛。证明：因为系数矩阵A严格对角占优，所以故Jacobi迭代法收敛(1)对于Jacobi迭代法，其迭代矩阵为且：(B)≤||B||即从而因此(2)对于G－S迭代法，其迭代矩阵为BG的特征值λ满足分析：要证G－S迭代法收敛，即证其迭代矩阵的谱半径(B)<1，只要证明其特征值λ

<1即可.由于可得<以下用反证法>矛盾由前述定理知，G－S迭代法收敛。定理若A为对称正定阵，则Gauss－Seidel迭代收敛。4.5松弛迭代法当ω＝1时，SOR法化为G－S迭代法G－S法为SOR法的特例,SOR法为G-S法的加速。例1.用G－S法和SOR法求下列方程组的解:要求精度1e-6解:(1)G-S迭代法

x1 x2 x3

1110.75000000.37500001.50000000.56250000.53125001.54166670.65104170.59635421.61458330.70182290.65820311.6727431……….0.99999330.99999231.99999260.99999430.99999351.99999370.99999520.99999441.9999946

k=71x=0.9999950.9999941.999995满足精度的解迭代次数为71次(2)SOR迭代法

x1 x2 x31110.63750000.01218751.31990630.20042700.37175721.31228050.65503350.53401191.69228480.70584680.77334011.7771932………..0.99999900.99999761.99999910.99999840.99999931.99999890.99999980.99999941.99999980.99999960.99999981.9999997k=24x=1.0000001.0000002.000000满足精度的解迭代次数为24次选取适当的ω，SOR法的收敛速度比G-S法要快得多。4.6误差分析结论：（1）的常数项b的第二个分量只有1/1000的微小变化，方程组的解变化却很大。例记方程组（1）为Ax＝b，其精确解为：x1*=2，x2*=0现考察方程组（2）可将其表示为：A(x+x)=b+b其中 b=(0,0.0001)T设x为(1)的解，显然(2)的解为：x+x=(1,1)T

设Ax＝b的扰动方程组为(A+A)(x+x)=b+b，其中A叫A的扰动矩阵，x和b叫x和b的扰动向量。定义若矩阵A或常数项b的微小变化引起方程组Ax＝b的解的巨大变化，则称此方程组为病态方程组，A为病态矩阵（相对方程组而言）；否则称方程组为良态方程组，A为良态矩阵。研究方程组中A或b的微小误差对解的影响的分析称“扰动分析”。(1)A=0，则A

(x+x)=b+b，减去Ax=b，得设Ax=b的扰动方程组为(A+A)(x+x)=b+b，下面进行扰动分析：(2)b=0，则(A+A)(x+x)=b，同理可得Ax=b，故x=A-1

b，即||x||||A-1||

||

b

||，又由Ax=b，有||b||||A

||

||

x

||

，所以定义设A非奇异，称数cond(A)=||A