大连理工大学《矩阵与数值分析》学习指导与课后参考答案第三章、逐次逼近法

第三章逐次逼近法1.1内容提要1、一元迭代法xn+1=φ(xn)收敛条件为：1）映内性x∈[a,b]，φ(x)∈[a,b]2）压缩性∣φ(x)-φ(y)∣≤L∣x-y∣其中L＜1，此时φ为压缩算子，在不断的迭代中，就可以得到最终的不动点集。由微分中值定理，如果∣φ’∣≤L＜1，显然它一定满足压缩性条件。2、多元迭代法xn+1=φ(xn)收敛条件为：1）映内性xn∈Ω，φ(xn)∈Ω2）压缩性ρ（▽φ）＜1，其中▽φ为xn处的梯度矩阵，此时φ为压缩算子，在不断的迭代中，就可以得到最终的不动点集。3、当φ(x)=Bx+f时，收敛条件为，ρ（B）＜1，此时xn+1=Bxn+f，在不断的迭代中，就可以得到线性方程组的解。4、线性方程组的迭代解法，先作矩阵变换Jacobi迭代公式的矩阵形式Gauss-Seidel迭代公式的矩阵形式超松弛迭代法公式的矩阵形式三种迭代方法当时都收敛。5、线性方程组的迭代解法，如果A严格对角占优，则Jacob法和Gauss-Seidel法都收敛。6、线性方程组的迭代解法，如果A不可约对角占优，则Gauss-Seidel法收敛。7、Newton迭代法，单根为二阶收敛8、Newton法迭代时，遇到重根，迭代变成线性收敛，如果知道重数m，仍为二阶收敛9、弦割法的收敛阶为1.618，分半法的收敛速度为（b-a）/2n-110、Aitken加速公式1.2典型例题分析1、证明如果A严格对角占优，则Jacob法和Gauss-Seidel法都收敛。证明：首先证Jacob法收敛，因为A严格对角占优，则，于是，从而，这又有，因此Jacob迭代法收敛。再证G-S法收敛，因为，由定理1.6，非奇异，而，所以，从而严格对角占优矩阵一定可逆。在G-S法中，，从而，求矩阵特征值时，只能是，因为A严格对角占优，，如果，两边乘，这说明矩阵仍然严格对角占优，前面已证明，该行列式不能为0，这是一个矛盾。因此，只能是，而这恰好说明Gauss-Seidel迭代法收敛。2、证明：如果A的对角元非零，超松弛迭代法收敛的必要条件是证明：令，如果超松弛迭代法收敛，应该有而，从而必须满足。3、分析方程2x-3x+4x-5x+6x-7x+8x-9x+10x=10是否有实根，确定根所在的区间，写出求根的Newton迭代公式,并确定迭代的初始点。解：因此该方程在[1,2]有且仅有一个实根，Newton迭代公式为/（），x0=1.5即可4、由求的Newton迭代公式证明：对一切是递减序列。证明：首先，如果中的xk>0，于是。又因为k=1开始5、若f(x)在零点ξ的某个邻域中有二阶连续导数，并且f’(ξ)≠0，试证：由Newton迭代法产生的xk(k=0,1,2,…)有证明：由Taylor公式，6、证明：A∈Cn*n,对任意范数有，证明：首先存在某种范数所以，取得到，对不等式同时取极限即得到再根据范数的等价性对不等式同时取极限即得到对任意范数有结果7、确定常数p,q,r，使如下迭代法收敛到，该方法至少几阶？解：根据定理3.6，一个迭代格式，在根附近它的p-1阶导数为零，就至少有p阶收敛速度1.3习题解答判断正误、选择和填空：1）、对于迭代过程，xn+1=φ(xn)，若迭代函数在x*的邻域有连续的二阶导数，且，则迭代过程为超线性收敛。（不正确），xn+1=φ(xn)的迭代收敛条件有两条，1）映内性xn∈[a,b]，φ(xn)∈[a,b]2）压缩性。更不能保证有超线性收敛，例如：用Newton迭代法求任何非线性方程均局部平方收敛。（不正确）若线性方程组Ax=b的系数矩阵A为严格对角占优，则Jacobi迭代法和G-S迭代法都收敛。（正确）解非线性方程f(x)=0的弦解法迭代具有（局部超线性敛速1.618）。局部平方收敛；（B）局部超线性收敛；（C）线性收敛任给初始向量x(0)及右端向量f，迭代法x(k+1)=Bx(k)+f收敛于方程组Ax=b的精确解x*的充要条件是（）。设φ(x)=x-β(x2-7)，要使迭代法xk+1=φ(xk)局部收敛到x*=，则β取值范围是（）。用迭代法xk+1=xk-λ(xk)f(xk)求f(x)=x3-x2-x-1=0的根，若要使其至少具有局部平方收敛，则（）。用二分法求x3-2x-5=0在[2，3]内的根，并要求，需要迭代（18）步。求f(x)=5x-ex=0在[0，1的根，迭代函数的简单迭代公式收敛阶为（线性）；Newton迭代公式的函数（）；其收敛阶为（二阶）。给定方程组，a为实数，当a满足（），且0<w<2时SOR法收敛。解：超松弛迭代格式现A对称，再加上正定就一定收敛，2、用列主元消去法解方程组Ax=b，其中A=，b=对所求的结果x，使用三次迭代改善后，解的精度能否有明显提高？4、设有线性方程组=，其精确解x*=(1,1,1)T，现用Gauss列主元消去法，得到的近似解x（1）=(1.2001,0.99991,0.92538)T，试用迭代改善法改善其精度。5、设方程组为=,证明：（1）用Jacobi迭代和Gauss-Seidel迭代法收敛的充要条件为（2）Jacobi迭代和Gauss-Seidel迭代法同时收敛或者发散证明：（1）先作矩阵变换Jacobi迭代公式的矩阵形式其中而，由迭代收敛的充要条件，于是Gauss-Seidel迭代公式的矩阵形式其中而，由迭代收敛的充要条件于是（2）显然，，两者都收敛，反之都发散。6、设A=，b=，t为实参数（1）求用Jacobi迭代法解Ax=b的迭代矩阵（2）t在什么范围内时Jacobi迭代法收敛解：（1）Jacobi迭代公式的矩阵形式，其中（2）由，迭代收敛的充要条件，于是，7、设A=，b=，t为实参数用Gauss-Seidel迭代法解Ax=b时，t在什么范围内收敛解：Gauss-Seidel迭代公式的矩阵形式，其中由迭代收敛的充要条件，于是，8、（1）设A=，b=，试证：Jacobi迭代求解发散，而Gauss-Seidel迭代法收敛，并求解。（2）设A=，b=，试证：Jacobi迭代求解收敛，而Gauss-Seidel迭代法发散，并求解。证明：先作矩阵变换（1）Jacobi迭代公式的矩阵形式其中由迭代收敛的充要条件，于是Jacobi迭代求解发散。Gauss-Seidel迭代公式的矩阵形式其中由迭代收敛的充要条件于是Gauss-Seidel迭代法收敛。（2）与（1）解法类似，Jacobi迭代公式中由迭代收敛的充要条件，于是Jacobi迭代求解收敛。而在Gauss-Seidel迭代公式中，由迭代收敛的充要条件应有，而现在，于是Gauss-Seidel迭代法发散。9、设方程组为=证明：（1）用Jacobi迭代和Gauss-Seidel迭代法是否收敛？（2）交换两个方程次序，再用Jacobi迭代和Gauss-Seidel迭代是否收敛？证明：（1）先作矩阵变换Jacobi迭代公式的矩阵形式其中不满足迭代收敛的充要条件，于是Jacobi迭代求解发散。Gauss-Seidel迭代公式的矩阵形式其中不满足迭代收敛的充要条件，于是Gauss-Seidel迭代将发散。（2）交换方程次序后，系数矩阵变为，它严格对角占优，因此Jacobi迭代和Gauss-Seidel迭代都收敛。10、求方程附近的一个根，将方程改写为四种等价形式（1）、（2）、（3）、（4）、试分析据此构造的迭代格式的收敛性，选择收敛最快的格式求根，使之误差不超过，对收敛最慢的格式用Aitken加速，结果如何？解：利用迭代格式xn+1=φ(xn)求解方程时，算子φ只要满足两条：1）映内性xn∈[a,b]，φ(xn)∈[a,b]2）压缩性∣φ’∣≤L＜1，那么迭代收敛。逐个判断上述4种格式的映内性和压缩性比较麻烦，我们先判断方程根的区间。现在，利用4种迭代格式，是企图求出[1，2]中的这个实根。最简便的方法是直接利用计算机迭代，结果如下：迭代格式（1）（2）（3）（4）计算次数126发散发散根1.46571.4659可见，迭代格式（1）、（2）收敛，其中（2）最快；而迭代格式（3）、（4）发散。Aitken加速公式，利用它对迭代格式（1）加速后，8次迭代（计算16次φ值），得根1.4662，对迭代格式（3）、（4）加速后仍不收敛。12、用Newton迭代公式求下列方程的根，要达到（1）、（2）（3）解：（1）先判断方程根的区间。利用（2）先判断方程根的区间。利用（3）先判断方程根的区间。利用14、，15、用弦截法求下列方程的根，要达到（1）、（2）（3）解：（1）先判断方程根的区间。利用（2）先判断方程根的区间。（3）先判断方程根的区间。16、Heonardo于1225年研究了方程请你构造一种简单迭代格式验证该著名结果。解：可见，其结果是正确的，如果对它的末位四舍五入，取将更精确。17、应用Newton法求的头5个非零正实根解：从0开始，以步长h=0.01搜索，出现函数值变号区间，立即以中点为初值，用Newton法加速迭代，找出负根舍弃，正根保留，然后继续搜索。求出5个正根为4.73004344778508，7.8532046238611，10.9956078380018，17.278759657399518、用二分法求要达到19、用幂法计算下列矩阵的主特征值及对应的特征向量；用QR法计算下列矩阵特征值，当主特征值有3位小数稳定时停止。A1=，A2=1）特征值=(0.5858，2.0000，3.4142)，主特征值=3.4142主特征值对应的特征向量（-0.5000，0.7071，-0.5000）T2）特征值=(2.0000，6.0000，3.0000)，主特征值=6.0000主特征值对应的特征向量（0.7974，0.5696，-0.1994）T20、用反幂法计算矩阵的模最小特征值及对应的特征向量；用QR法计算矩阵特征值，当特征值有3位小数稳定时停止。A=特征值=(-7.0709，0.8133，18.2576)，模最小特征值=0.8133，其对应的特征向量为（-0.1341，-0.7318，0.6682）T21、矩阵A=有特征值的近似值4.3，试用原点位移的反幂法求出特征值和对应特征向量解：已知特征值的一个近似值之后，就可能成为矩阵的模最小特征值，这样用反幂法，求出它的最小特征值为0.2745，对应特征向量（-0.6907，0.7149，0.1087）T，于是，可见特征向量仍不变。22、试用SOR法（ω=0.9）解线性方程组=（1）、证明此时SOR法收敛（2）、求满足的解解：（1）SOR格式代入ω=0.9求出其3个特征值=0.0428，0.0300±0.1499i)，可见谱半径小于1，因此迭代收敛（2）x=(-3.0909,1.2372,0.9802)T23、方程组Ax=b，其中A为对称正定矩阵，迭代公式x(k+1)=x(k)+ω(b-Ax(k))证明：当时，迭代收敛（其中0<α≦λ(A)≦β，λ(A)为A的任意特征值）证明：由x(k+1)=x(k)+ω(b-Ax(k))=（I-ωA）x(k)+ωb，如果迭代收敛，应该有ρ(I-ωA)<1但是（I-ωA）的特征值为1-ωλ(A)，所以∣1-ωλ(A)∣＜1，-1＜1-ωλ(A)＜10＜ωλ(A)＜2，又由于0<α≦λ(A)≦β，为保证0＜ωmax(λ(A))＜2，应该有0＜ωβ＜2，所以时可确保迭代收敛。24、（略）25、用G-S法求解方程组：=,，（）26、电路分析，常需要解方程组RI=v，分别用（1）Jacobi迭代（2）Gauss-Seidel迭代（3）SOR迭代（4）C