非线方程组的数值解法

第六章非线性方程组的迭代解法 6.4 非线性方程组的数值解法非线性方程组的数值解法6.4.3非线性方程组的非线性方程组的Newton法法6.4.2 非线性方程组的非线性方程组的Newton法法6.4.1 非线性方程组的不动点迭代法非线性方程组的不动点迭代法第六章非线性方程组的迭代解法 第六章非线性方程组的迭代解法 1.2学习目标：学习目标：第六章非线性方程组的迭代解法 TnxfxfxfxF)(),(),()(21 设含有设含有n个未知数的个未知数的n个方程的非线性方程组为个方程的非线性方程组为 (6,4,1)其中其中 为为n维列向量，维列向量，0)(xFTnxxxx),(21 6.4.1 非线性方程组的不动点迭代法非线性方程组的不动点迭代法),2,1)(nixfi 中至少有一个是中至少有一个是x的非线性函数，的非线性函数，并假设自变量和函数值都是实数。多元非线性方程组并假设自变量和函数值都是实数。多元非线性方程组(6.4.1)与一元非线性方程与一元非线性方程f(x)=0具有相同的形式，可以具有相同的形式，可以与一元非线性方程并行地讨论它的迭代解法。例如不动与一元非线性方程并行地讨论它的迭代解法。例如不动点迭代法和点迭代法和Newton型迭代法。但是，这里某些定理的型迭代法。但是，这里某些定理的证明较为复杂，我们将略去其证明。证明较为复杂，我们将略去其证明。第六章非线性方程组的迭代解法 Tnxxxxx)(,),(),()(21(6.4.2)并构造不动点迭代法并构造不动点迭代法,1,0),()()1(kxxkk(6.4.3)把方程组把方程组(6.4.1)改写成下面便于迭代的等价形式：改写成下面便于迭代的等价形式：的解。的解。是方程组是方程组从而从而的不动点，的不动点，是迭代函数是迭代函数即即满足满足连续函数连续函数.则则的的是自变量是自变量是连续的是连续的,即即且且收敛，收敛，若由此生成的序列若由此生成的序列对于给定的初始点对于给定的初始点)1.4.6()(),(,)(,),(),()(,*2121)0(xxxxxxxxxxxxxxnnf ff f f f KK kx*)(limxxkk 第六章非线性方程组的迭代解法 例例6.11 设有非线性方程组设有非线性方程组081008102122122121xxxxxxx(6.4.4)把它写成等价形式把它写成等价形式)8(101),()8(101),(1211212222212111xxxxxxxxxxx并由此构造不动点迭代法并由此构造不动点迭代法 8)(101),(8)()(101),()(122)(1)(2)(12)1(22)(22)(1)(2)(11)1(1kkkkkkkkkkkxxxxxxxxxxx,1,0k(6.4.5)第六章非线性方程组的迭代解法)(1kx)(2kx取初始点取初始点 。计算结果列于表。计算结果列于表69，可见迭代收敛到，可见迭代收敛到方程的解方程的解Tx)0,0()0(Tx)1,1(*表表 6-9k012 18 1900.80.9280.9999999720.99999998900.80.9310.9999999720.999999989 函数也称映射，若函数函数也称映射，若函数 的定义域为的定义域为 ，则可，则可用映射符号用映射符号 简便地表示为简便地表示为 。为了讨论不动。为了讨论不动点迭代法（点迭代法（6.4.3）的收敛性，先定义向量值函数的映内性）的收敛性，先定义向量值函数的映内性和压缩性。和压缩性。)(xnRDnnRRD:第六章非线性方程组的迭代解法 定义定义6.3 设有函数设有函数 若若 则称则称 在在D D上是映内的，记做上是映内的，记做 ，又若存在常数，又若存在常数 ，使得，使得nnRRD:DxDx,)()(xDD)()1,0(LDyxyxLyx,)()(则称则称 在在D上是压缩的，上是压缩的，L称为压缩系数称为压缩系数)(x 压缩性与所用的向量范数有关，函数压缩性与所用的向量范数有关，函数 对某种范数是压对某种范数是压缩的，对另一种范数可能不是压缩的。缩的，对另一种范数可能不是压缩的。)(x定理定理6.7（Brouwer不动点定理不动点定理）若）若 在有界凸集在有界凸集 上连上连续并且映内，则续并且映内，则 在内在内 存在不动点。存在不动点。DD 00D定理定理6.8（压缩映射定理压缩映射定理）设函数）设函数 在闭集在闭集 上是映内的，并且对某一种范数是压缩的，压缩系数上是映内的，并且对某一种范数是压缩的，压缩系数为为L，则，则（1）在在 上存在唯一的不动点上存在唯一的不动点 。（2）对任何初值）对任何初值 迭代法（迭代法（6.4.3）生成的序列）生成的序列 且收敛到且收敛到 ，并且有误差估计式，并且有误差估计式nnRRD:DD 0)(x0D*x0)0(Dx0)(Dxk*x第六章非线性方程组的迭代解法)1()(*)(1kkkxxLLxx例例6.12 对于例对于例6.11，设，设 试证：对任何初始点试证：对任何初始点 ，由迭代法（，由迭代法（6.4.5）生成的序列的都）生成的序列的都收敛到方程（收敛到方程（6,4.4）在）在 中的唯一解中的唯一解 5.1,5.1:),(21210 xxxxDT0)0(Dx0DTx)1,1(*0D证：首先容易算出，对于任何证：首先容易算出，对于任何 ，都有，都有 因此，迭代函数因此，迭代函数 在在 上是映内的。进而，对于任何上是映内的。进而，对于任何都有都有021),(DxxxT25.1),(8.0211xx2875.1),(3125.0212xx021),(DxxxT021),(DyyyT)()(101)()(2222111111yxyxyxyxyx122113.0)(103yxyxyx第六章非线性方程组的迭代解法 2222211122101)()(yyxxyxyx22122122122111101yyxyxyxxyx)()(1(101222211122yxyxyyxx)5.425.3(1012211yxyx145.0yx 从而从而)()()()()()(22211yxyxyxyx 75.0 可见，函数可见，函数 在上在上 是压缩的。因此，由定理是压缩的。因此，由定理6.8得知得知结论成立。结论成立。0D 以上讨论了迭代法在以上讨论了迭代法在 的收敛性，下面讨论局部收敛的收敛性，下面讨论局部收敛性。性。0D第六章非线性方程组的迭代解法 定义定义6.4 设设 为为 的不动点，若存在的不动点，若存在 的一个领域的一个领域 ，对一切，对一切 ，由（由（6.4.3）式产生的序列）式产生的序列 且且 ，则称，则称 具有局部收敛性。具有局部收敛性。*x*xDS Sx)0(Sxk)(*)(limxxkk)(kx则则 称为称为p阶收敛阶收敛。定义定义6.5 设设 收敛于收敛于 ，存在常数，存在常数 及常数及常数c0,使使 )(kx*x2pcxxxxkkk*)(*)1(lim)(kx定理定理6.9 设设 ，为为 的不动点，若存在开的不动点，若存在开球球 ，常数，常数 ，使，使则由则由(6.4.3)产生的序列产生的序列 局部收敛至局部收敛至 nnRRD:0*Dx DxxxxSS*:),()1,0(LSxxxLxx,)()(*)(kx*x证：任给证：任给 ，一般的，设，一般的，设 ，即，即 ，则，则Sx)0(Sxk)(*xx)()(*)(*)1(xxxxkkLxxLk*)(第六章非线性方程组的迭代解法 得知得知 ，从而有，从而有 。于是，由定义。于是，由定义6.4知知迭代法（迭代法（6.4.3）在点）在点 处局部收敛。定理得证。处局部收敛。定理得证。与单个方程的情形类似，有时可以用关于导数的条件代替与单个方程的情形类似，有时可以用关于导数的条件代替压缩条件来判别收敛性压缩条件来判别收敛性 0lim*)(xxkk*)(limxxkk*x定理定理6.10 设设 ，在在D内有一不动点内有一不动点 ，且，且 在在 处处可导，且谱半径可导，且谱半径 ，则迭代法（，则迭代法（6.4.3）在点）在点 处处局部收敛，其中，函数局部收敛，其中，函数 的导数为的导数为Jacobi矩阵（见矩阵（见*式）式）利用谱半径与范数的关系利用谱半径与范数的关系 ，我们可用，我们可用 代替定理代替定理6.10中的条件中的条件nnRRD:*x*x1)(*x*x)(xAA)(1*x1)(*x第六章非线性方程组的迭代解法 nnnnnnTnTTxxxxxxxxxxxxxxxxxxxxxx21222121211121)()()()()()()()(（*）例如，对于例例如，对于例6.11有有对于例对于例6.12所取的区域所取的区域 的不动点的不动点 在它的内部。容易验在它的内部。容易验 证，在证，在 上有上有 ，因此，迭代法（，因此，迭代法（6.4.5）在点）在点 处处局部收敛。局部收敛。2122212212101)(xxxxxx,0D*x0D 75.0*x*x第六章非线性方程组的迭代解法 对于非线性方程组，也可以构造类似于一元方程的对于非线性方程组，也可以构造类似于一元方程的Newton迭代迭代法。设法。设 是方程组（是方程组（6.4.1）的解，）的解，是方程组的一个近似解。是方程组的一个近似解。用点用点 处的一阶处的一阶Taylaor展开式近似每一个分量函数值展开式近似每一个分量函数值 ，有有*x)(kx)(kx0)(*xfi njkjjjkikiinixxxxfxfxf1)(*)()(*,2,1),()()()(其中其中 为为 的的Jacobi矩阵矩阵 在的在的 值，而值，而写成向量形式有写成向量形式有)()()()(*)()(*kjkkxxxFxFxF )()(kxF)(xF)(xF)(kx6.4.2 非线性方程组的非线性方程组的Newton法法第六章非线性方程组的迭代解法 nnnnnnTnTTxxfxxfxxfxxfxxfxxfxxfxxfxxfxfxfxfxF21222121211121)()()()()()()()(若矩阵若矩阵 非奇异，则可以用使（非奇异，则可以用使（6.4.6）右端为零的向量作）右端为零的向量作为为 新的一个近似值，记为新的一个近似值，记为 ，于是得到，于是得到Newton迭代法迭代法)()(kxF*x)1(kx,2,0),()(1)()1(kxFxFxxkk（6.4.7)0(x)()(1kkxx其中其中 是给定的初值向量。如果写成一般不动点迭代是给定的初值向量。如果写成一般不动点迭代 的形式，则的形式，则Newton迭代函数为迭代函数为)()()(1xFxFxx(6.4.8)第六章非线性方程组的迭代解法 在在Newton法实际计算过程中，第法实际计算过程中，第k步是先解线性方程组步是先解线性方程组解出解出 后，再令后，再令 ，其中包括了计算向量，其中包括了计算向量 和矩阵和矩阵)()()()()(kkkxFxxF(6.4.9)(kxkkkxxx)1()()(kxF)()(kxF例例6.13 用用Newton法解例法解例6.11的方程组（的方程组（6.4.4）解解 对该方程组有对该方程组有取初始向量取初始向量 ，解方程组，解方程组 ，即，即810810)(2122122121xxxxxxxxF10212102)(212221xxxxxxFTx)0,0()0()()()0()0()0(xFxxF88101010)0(x第六章非线性方程组的迭代解法 求出求出 后，后，。同理计算。同理计算 结果结果列于表列于表610。可见，。可见，Newton法的收敛速度比例法的收敛速度比例6.11中的迭代中的迭代法（法（6.4.5）要快的多。）要快的多。)0(xTxxx)88.0,8.0()0()0()1(,)2(x表表 6-10kx2kx1k01 2 3 400.800.9917872210.9999752291.0000000000.880.9917117370.9999685241.00000000关于关于Newton法的收敛性，有下面的局部收敛性定理法的收敛性，有下面的局部收敛性定理第六章非线性方程组的迭代解法 定理定理6.11 设设 ，满足满足 。若有。若有 的开邻的开邻域域 ，在其上连续，在其上连续，可逆，则可逆，则nnRRDF:*x0)(*xF*xDS 0)(xF)(*xF(2)Newton迭代序列迭代序列 在在S上收敛于上收敛于 ，且是超线性收敛，且是超线性收敛。)(kx*x(1)(1)存在以存在以 为中心，为中心，为半径的闭球为半径的闭球 ,使使 （6.4.8）式中的）式中的 对所有对所有 都有意义，并且都有意义，并且 。*x00*),(SxSS)(xSxSx)(0（3）若还有常数若还有常数 ，使，使 则则Newton迭代序列迭代序列 至少二阶收敛于至少二阶收敛于 。SxxxxFxF,)()(*)(kx*x 虽然虽然Newton法具有二阶局部收敛性，但它要求法具有二阶局部收敛性，但它要求 非奇非奇异。如果矩阵异。如果矩阵 奇异或病态，那么奇异或病态，那么 也可能奇异或病也可能奇异或病态，从而可能导致数值计算失败或产生数值步稳定。这时可采态，从而可能导致数值计算失败或产生数值步稳定。这时可采用用“阻尼阻尼Newton法法”，即把（，即把（6.4.9）改成）改成)(*xF)(*xF)()(kxF第六章非线性方程组的迭代解法 其中的参数其中的参数 称为阻尼因子，称为阻尼因子，称为阻尼项，解出称为阻尼项，解出 后，后，令令 。加进阻尼项的目的，是使线性方程的系数矩。加进阻尼项的目的，是使线性方程的系数矩阵非奇异并良态。当阵非奇异并良态。当 选的很合适时，阻尼选的很合适时，阻尼Newton法时线性法时线性收敛的。收敛的。kIk)(kx)()()1(kkkxxxk例例614 用用Newton法和阻尼法和阻尼Newton法求解方程法求解方程 ，其，其中中0)(xF2102310)(2122122121xxxxxxxxF解：易知该方程有一个解是解：易知该方程有一个解是 。由于。由于 Tx)1,4(*,1,0),()()()()(kxFxIxFkkkk第六章非线性方程组的迭代解法 2222)(*xF，），（法有按）（TxNewton438461538.1538461538.31Tkx)5.2,5.2(.10)0(5若取是奇异的，取阻尼因子。，Tx)000000025.1,000000025.4()25(,)438461083.1,538463160.3()1(TxNewton法计算有在按阻尼。Tx)000000286.1,000000286.4(,)29(定性问题，没有出现奇异或数值稳法仍非奇异，奇异，只要可见，即使矩阵NewtonxFxFk)()()(*法并小，。因为次例题的维数太收敛，但收敛是线形的Newton第六章非线性方程组的迭代解法 作用，反而使迭代法不仅没有显示出它的从而阻尼 Newton法是线形收敛的。，阻尼次数更多。但可以看出Newton初值关重要。程时，初始值的选取至用迭代法求解非线形方敛到不同的解。同的初值可能收，而当方程有解时，不不仅影响迭代是否收敛。1)5.0()2(1)(2221221xxxxxF15.6例其中法求解用,0)(xFNewton21221)201xxx与圆（物线该方程组的实数解是抛解,)0000.1,0625.1(,)0,0()1()0(KTTxx那么有如果取初时向量。和TTx)391176313.1,546342883.1()139227667.0,067346086.1(*2201)5.0(xx的交点。这两个实根是第六章非线性方程组的迭代解法。计算结果收敛到*)5(,)391176313.1,546342883.1(,xxT。计算结果收敛到*)5(,)139221092.0,067343609.1(xxT,)583333333.1,645833333.1(,)2,2()1()0(TTxx则有若取初值)10.4.6(,1,0),()(1)()1(。kxFAxxkkkk迭代公式是法的代替我们用较简单的矩阵),()(kkxFNewtonA是困难的。所以，比较复杂时，求导数值的分量函数特别是当)()(xfxFi是不方便的，是每步都要计算法有较好的收敛性，但)()(kxFNewton当取在所代的收敛性，初始值应一般说来，为了保证迭。这是个相当困难的问题学的角度讲，预估一个近似解。从数有的则可以用某些方法经验取初值，。有的实际问题可以凭求解的足够小的邻域内6.4.3非线性方程组的非线性方程组的Newton法法第六章非线性方程组的迭代解法)11.4.6()()()()()1()()1(1kkkkkxFxFxxA11()kkAfx下 一 步 是 要 确 定。若 是 单 个 方 程，割 线 中可 用 差 商于是取具有性质是向量，代替。方程组的情形，)()1(11)/()()(kkkkkkxxxxxfxf方法。时，称为秩方法。为秩221m法，）称为拟的迭代法（为增量矩阵，由此得到称NewtonAk10.4.6时，称。当或方程。通常取）称为拟（12111.4.6mmmNewton)12.4.6(1)(,1。mArankAAAkkkk已知和。在多元情形下，当法中的代替的矩阵)1()()1(1)(kkkkxxxFNewtonA一个可行的途径是令，需要附加其他条件。因此，为了确定矩阵1kA个未知量）。个方程中含有）不能确定矩阵时，由方程（nnnAk211(11.4.6第六章非线性方程组的迭代解法。（），即（kkTkkysvuAk)11.4.6方程满足拟，使得矩阵和选择NewtonAAAvukkkkk1。)()(,)()1()()1(kkkkkkxFxFyxxs的方法。增量矩阵的情形为例，说明确定下面一秩kA1为列向量。记nTkkTkkkRvuvuAAk,1其中总可以表示为的矩阵秩为，则由此可解出若0kTksv有代入和述kkkAuv。把上时总有即迭代尚未终止），这0(22)()1(kkTkkkssvxx因为只要的一个自然取法是令唯一确定。向量由即,kkkkksvvvu，)(1kkkkTksAysvuk第六章非线性方程组的迭代解法。TkkkkkkssAysA)(122）（。13.4.6,1,0,)(1),()(,),(221)()1(1)(1)()1(kssAysAAxFxFyxxsxFAxxTkkkkkkkkkkkkkkkkk的迭代法于是得到求解方程0)(xF做矩阵运算即可证明。引理的结论只要直接降为运算量可将解方程组的直接法)()(23nOnO）中的矩阵求逆，从而避免方法（利用下面的引理，可以13.4.6)(1)0(0)0(xFAxBtoyden可取为给定，方法，其中的初始值秩称之为或单位矩阵。第六章非线性方程组的迭代解法）（。（14.4.61)11111uAvAuvAAuvATTT非奇异的则非奇异，若矩阵引理TTnnuvARvuRA,并且有充分必要条件是,01AuvT。kTkkkkkkTkkTkkkkBssyByBsBvuAB)(1)(11）有那么利用（如果14.4.6,0kkTkyBs有）中，令在（,13.4.61kkAB。kkTkkkTkkkTkkkkTkyBsssvyBvsuAv222211)(111),(1)(122221kkkkkkkkkkksyBssAyBsuA第六章非线性方程组的迭代解法）可改写成于是，方法（13.4.6）（。15.4.6,1,0,)(1),()(,),(1)()1()()1()()()1(KkBsyBsyBsBBxFxFyxxsxFBxxkTkkkkkkTkkkkkkkkkkkkk1)0(0)0()(1xFBxBroyden取为（给定，方法，其中的初始值秩称之为逆形收敛的。定的条件下，它是超线方法。可以证明，在一Newton解非线形方程组的拟方法是一种能有效地求或单位矩阵。逆Broyden16.6例。中的方程组）解例方法（用逆15.615.4.6Broyden。124212)(211xxxxF解有对所给)(xF第六章非线性方程组的迭代解法。1002162.05224991.02721932.03557441.01B,)12109375.1,12890625.2()()()0()1(0TxFxFy及有取TTxFx)25.3,1()(,)0,0()0()0(,)12890625.2,12890625.1()()1(TxF,)1,0625.1()()1()0()1(0)0(0)0()1(xxxsxFBxxT,0125.025.0)(,1410)(1)0(0)0(xFBxF法求解，如果用位有效数字的近似解。这是具有次后有步的计算，如此迭代接着再进行第NewtonxkT12,)93911763127.1,25463428833.1(111)11(多得多。次，但每步计算量却要少迭代方法果，比逆便可得到同样精度的结迭代到4)7(Broydenx