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

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

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

（初等行变换法）第十六页，共七十五页，编辑于2023年，星期日2.矩阵求逆

（伴随矩阵法）其中A*为A的代数余子式每一项代数余子式的符号为-1^(i+j)第十七页，共七十五页，编辑于2023年，星期日迭代法的基本思想：例：求解方程组其精确解是x*=(3,2,1)T。现将原方程组改写为简写为x=B0x+f，其中第十八页，共七十五页，编辑于2023年，星期日任取初始值，如取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第十九页，共七十五页，编辑于2023年，星期日定义：（1）对于给定方程组x=Bx+f，用迭代公式x(k+1)=Bx(k)+f

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

如何建立迭代格式？

收敛速度？

向量序列的收敛条件？

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

，有（1）（2）第四十六页，共七十五页，编辑于2023年，星期日证由||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*||第四十七页，共七十五页，编辑于2023年，星期日所以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)||故可得误差估计式:第四十八页，共七十五页，编辑于2023年，星期日注：

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

和x(k)

很接近时，x(k)

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

x(k+1)

-x(k)

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

收敛越快，可作误差估计式。第四十九页，共七十五页，编辑于2023年，星期日定理：迭代格式收敛的充要条件为迭代矩阵的谱半径(B)<1。证:对任何n阶矩阵B，都存在非奇异矩阵P，使

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

为Jordan块第五十页，共七十五页，编辑于2023年，星期日其中λ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。第五十一页，共七十五页，编辑于2023年，星期日例3.判别下列方程组用Jacobi法和Gauss-Seidel法求解是否收敛:解:(1)求Jacobi法的迭代矩阵第五十二页，共七十五页，编辑于2023年，星期日所以即Jacobi迭代法收敛。(2)求Gauss-Seidel法的迭代矩阵：显然BJ的几种常用算子范数||BJ||>1，故用其特征值判断。第五十三页，共七十五页，编辑于2023年，星期日所以Gauss-Seidel迭代法发散。注：本例说明Gauss-Seidel迭代法发散时而Jacobi迭代法却收敛，因此，不能说Gauss-Seidel迭代法比Jacobi迭代法更好。可得故第五十四页，共七十五页，编辑于2023年，星期日定义设A=(aij

)n×n

Rn×n

，若

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

<1即可.第五十七页，共七十五页，编辑于2023年，星期日由于可得<以下用反证法>第五十八页，共七十五页，编辑于2023年，星期日矛盾由前述定理知，G－S迭代法收敛。定理若A为对称正定阵，则Gauss－Seidel迭代收敛。第五十九页，共七十五页，编辑于2023年，星期日4.5松弛迭代法第六十页，共七十五页，编辑于2023年，星期日第六十一页，共七十五页，编辑于2023年，星期日第六十二页，共七十五页，编辑于2023年，星期日第六十三页，共七十五页，编辑于2023年，星期日当ω＝1时，SOR法化为G－S迭代法G－S法为SOR法的特例,SOR法为G-S法的加速。例1.用G－S法和SOR法求下列方程组的解:要求精度1e-6第六十四页，共七十五页，编辑于2023年，星期日解:(1)G-S迭代法第六十五页，共七十五页，编辑于2023年，星期日

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次第六十六页，共七十五页，编辑于2023年，星期日(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法要快得多。第六十七页，共七十五页，编辑于2023年，星期日第六十八页，共七十五页，编辑于2023年，星期日第六十九页，共七十五页，编辑于2023年，星期日第七十页，共七十五页，编辑于2023年，星期日第七十一页，共七十五页，编辑于2023年，星期日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

第七十二页，共七十五页，编辑于2023年，星期日设Ax＝b的扰动方程组为(A+A)(x+x)=b+b，其中A叫A的扰动矩阵，x和b叫x和b的扰动向量。定义若矩阵A或常数项b的微小变化引起方程组Ax＝b的解的巨大变化，则称此方程组为病态方程组，A为病态矩阵（相对方程组而言）；否则称方程组为