非线性方程的解法.doc

20世纪60年代中期以后，发展了两种求解非线性方程组(1)的新方法。一种称为区间迭代法或称区间牛顿法，它用区间变量代替点变量进行区间迭代，每迭代一步都可判断在所给区间解的存在惟一性或者是无解。这是区间迭代法的主要优点，其缺点是计算量大。另一种方法称为不动点算法或称单纯形法，它对求解域进行单纯形剖分，对剖分的顶点给一种恰当标号，并用一种有规则的搜索方法找到全标号单纯形,从而得到方程(1)的近似解。这种方法优点是，不要求f()的导数存在,也不用求逆，且具有大范围收敛性，缺点是计算量大编辑摘要 目录 1 正文 2 牛顿法及其变形 3 割线法 4 布朗方法 5 拟牛顿法 1 正文 2 牛顿法及其变形 3 割线法 4 布朗方法 5 拟牛顿法 6 最优化方法 7 连续法 8 参考书目 非线性方程组数值解法 - 正文n个变量n个方程(n 1)的方程组表示为 (1)式中i(x1,x2,xn)是定义在n维欧氏空间Rn 的开域D上的实函数。若i中至少有一个非线性函数，则称(1)为非线性方程组。在Rn 中记 则(1)简写为(尣)=0。若存在尣*D，使(尣*)0，则称尣*为非线性方程组的解。方程组(1)可能有一个解或多个解，也可能有无穷多解或无解。对非线性方程组解的存在性的研究远不如线性方程组那样成熟，现有的解法也不象线性方程组那样有效。除极特殊的方程外，一般不能用直接方法求得精确解，目前主要采用迭代法求近似解。根据不同思想构造收敛于解尣*的迭代序列尣k(k=0，1，)，即可得到求解非线性方程组的各种迭代法，其中最著名的是牛顿法。 非线性方程组数值解法 - 牛顿法及其变形 牛顿法基本思想是将非线性问题逐步线性化而形成如下迭代程序： (2)式中 是(尣k)的雅可比矩阵,尣0是方程(1)的解尣*的初始近似。 这个程序至少具有2阶收敛速度。由尣k算到尣k+的步骤为:由尣k算出(尣k)及;用直接法求线性方程组的解尣k；求。 由此看到迭代一次需计算n个分量函数值和 n2个分量偏导数值，并求解一次n阶线性方程组。 为了评价非线性方程组不同迭代法的优劣，通常用效率作为衡量标准,其中P为迭代法的收敛阶,W为每迭代步计算函数值i及偏导数值的总个数（每迭代步中求一次逆的工作量相同,均不算在W 内）。效率e越大表示此迭代法花费代价越小,根据效率定义，牛顿法(2)的效率为。 牛顿法有很多变形,如当奇异或严重病态时，可引进阻尼因子k，得到阻尼牛顿法，即 式中I是单位矩阵。牛顿法是局部收敛方法,因而对初始近似尣0限制较严，为放宽对尣0的要求,扩大收敛范围,通常可引进松弛因子k，得到牛顿下降法： (3)式中k的选择应使成立。 为减少解线性方程组次数，提高效率，可使用修正牛顿程序 (4)这种算法也称为萨马斯基技巧，它的收敛阶为 p =m+1，由尣k 计算 的工作量为W =n2+mn，于是该法的效率。当n=10,m7时,当n100,m37时,，由此看到修正牛顿法(4)比牛顿法效率高，且m 越大效果越明显。 在计算机上往往采用不计算偏导数的离散牛顿法，即 (5)式中 ，其中ej为基向量,若取，则(5)仍具有2阶收敛速度。其效率与牛顿法相同。 若在牛顿法(2)中解线性方程组不用直接法,而采用迭代法则得到一类解非线性方程组的双重迭代法。按解线性方程组采用的方法不同就得到不同名称的迭代法，如牛顿赛德尔迭代法，牛顿SOR迭代法，牛顿ADI迭代法，等等。这些方法都具有超线性收敛速度，工作量也比牛顿法大，除了对某些特殊稀疏方程组外，通常用得校少。若将解线性方程组迭代法的思想直接用于非线性方程组(1)，然后把(1)化为一维方程求解，可得到另一类双重迭代法，由于采用的迭代法与解一维非线性方程的方法不同，则得到不同的双重迭代法。如果利用SOR迭代法后再用牛顿法解一维方程则得SOR牛顿迭代法，在牛顿法中只计算一步而不进行迭代，则得一步的SOR牛顿迭代，其计算公式可表示为 式中记号嬠ii表示；为迭代参数，当=1时就是赛德尔-牛顿迭代法,这类方法对解维数高的稀疏的非线性方程组是有效的。 非线性方程组数值解法 - 割线法若对方程组 (1)线性化时使用插值方法确定线性方程组 (6)中的Ak和bk,则可得到一类称为割线法的迭代序列。假定已知第k步近似尣k，为确定Ak和bk,可在尣k附近取n个辅助点忋(j=1,2,n),使n个向量线性无关，由插值条件可知 由此可求得 由(6)解得以此作为方程 (1)的新近似，记作，于是得到 (7)(7)称为解非线性方程组的割线法。辅助点忋 取得不同就得到不同的割线法程序，例如取为常数(j=1,2,n)，就得到与(5)相同的程序，由于它只依赖于尣k点的信息，故也称一点割线法,若取它依赖于点尣k及, 称为两点割线法。其他多点割线法由于稳定性差，使用较少。 非线性方程组数值解法 - 布朗方法布朗采用对每个分量方程 i(尣)=0逐个进行线性化并逐个消元的步骤，即在每迭代步中用三角分解求线性方程组的解，得到了一个效率比牛顿法提高近一倍的迭代法，即 式中 (8)中当i=n时求得xn记作,再逐次回代,求出(i=n-1,n-2,1)就完成了一个迭代步。布朗迭代程序的敛速仍保持p2，而每一迭代步的工作量，故效率对这方法还可与牛顿法一样进行改进，得到一些效率更高的算法。这类方法是70年代以来数值软件包中常用的求解非线性方程组的算法。 非线性方程组数值解法 - 拟牛顿法为减少牛顿法的计算量，避免计算雅可比矩阵及其逆，60年代中期出现了一类称为拟牛顿法的新算法,它有不同的形式，常用的一类是秩1的拟牛顿法，其中不求逆的程序为 式中,，称为逆拟牛顿公式。计算时先给出尣0及 B0，由(9)逐步迭代到满足精度要求为止。每步只算 n个分量函数值及O(n2)的计算量,比牛顿法一步计算量少得多。理论上已证明，当尣0及B0选得合适时,它具有超线性收敛速度,但实践表明效率并不高于牛顿法，理论上尚无严格证明。 非线性方程组数值解法 - 最优化方法求方程组 (1)的问题等价于求目标函数为的极小问题,因此可用无约束最优化方法求问题(1)的解（见无约束优化方法）。 非线性方程组数值解法 - 连续法又称嵌入法，它可以从任意初值出发求得方程组(1)的一个足够好的近似解,是一种求出好的迭代初值的方法。连续法的基本思想是引入参数 t【0,b】，构造算子H(尣,t)，使它满足条件：H(尣,0)=0(尣),H(尣,b)=(尣)，其中0(尣)=0的解尣0是已知，方程： (10)在t【0,b】上有解尣=尣(t)，则尣(b)=尣*就是方程(1)的解。当b有限时，通常取b=1，例如可构造。 (11)这里尣0是任意初值,显然H(尣0,0)=0,H(尣,1)=(尣)。为了求得(10)在t=1的解尣*=尣(1),可取分点0=t0t11)的方程组表示为 198-1 (1)式中(,)是定义在维欧氏空间 的开域上的实函数。若中至少有一个非线性函数，则称(1)为非线性方程组。在R 中记 198-2 f198-3198-03 则(1)简写为f()=0。若存在xinkg2kg2，使f(xin)0，则称xin为非线性方程组的解。方程组(1)可能有一个解或多个解，也可能有无穷多解或无解。对非线性方程组解的存在性的研究远不如线性方程组那样成熟，现有的解法也不象线性方程组那样有效。除极特殊的方程外，一般不能用直接方法求得精确解，目前主要采用迭代法求近似解。根据不同思想构造收敛于解xin的迭代序列(=0，1，)，即可得到求解非线性方程组的各种迭代法，其中最著名的是牛顿法。牛顿法及其变形牛顿法基本思想是将非线性问题逐步线性化而形成如下迭代程序：198-5 (2)式中198-6是f()的雅可比矩阵,是方程(1)的解xin的初始近似。这个程序至少具有2阶收敛速度。由算到(的步骤为:由算出f()及198-7;用直接法求线性方程组198-8的解；求198-9。由此看到迭代一次需计算个分量函数值和 个分量偏导数值，并求解一次阶线性方程组。为了评价非线性方程组不同迭代法的优劣，通常用效率198-10作为衡量标准,其中为迭代法的收敛阶,为每迭代步计算函数值及偏导数值198-11的总个数（每迭代步中求一次逆的工作量相同,均不算在 内）效率越大表示此迭代法花费代价越小,根据效率定义，牛顿法(2)的效率为199-1。牛顿法有很多变形,如当199-2奇异或严重病态时，可引进阻尼因子，得到阻尼牛顿法，即199-3式中是单位矩阵。牛顿法是局部收敛方法,因而对初始近似限制较严，为放宽对的要求,扩大收敛范围,通常可引进松弛因子，得到牛顿下降法： 199-4 (3)式中的选择应使199-5成立。为减少解线性方程组次数，提高效率，可使用修正牛顿程序 199-6 (4)这种算法也称为萨马斯基技巧，它的收敛阶为 p =+1，由 计算 199-44的工作量为 =+，于是该法的效率199-7。当=10,7时,199-8当100,37时,199-10，由此看到修正牛顿法(4)比牛顿法效率高，且 越大效果越明显。在计算机上往往采用不计算偏导数的离散牛顿法，即199-11(5)式中199-12，其中e为基向量,199-14,若取199-15，则(5)仍具有2阶收敛速度。其效率与牛顿法相同。若在牛顿法(2)中解线性方程组不用直接法,而采用迭代法则得到一类解非线性方程组的双重迭代法。按解线性方程组采用的方法不同就得到不同名称的迭代法，如牛顿赛德尔迭代法，牛顿SOR迭代法，牛顿ADI迭代法，等等。这些方法都具有超线性收敛速度，工作量也比牛顿法大，除了对某些特殊稀疏方程组外，通常用得校少。若将解线性方程组迭代法的思想直接用于非线性方程组(1)，然后把(1)化为一维方程求解，可得到另一类双重迭代法，由于采用的迭代法与解一维非线性方程的方法不同，则得到不同的双重迭代法。如果利用SOR迭代法后再用牛顿法解一维方程则得SOR牛顿迭代法，在牛顿法中只计算一步而不进行迭代，则得一步的SOR牛顿迭代，其计算公式可表示为 199-17式中记号表示199-18；为迭代参数，当=1时就是赛德尔-牛顿迭代法,这类方法对解维数高的稀疏的非线性方程组是有效的。割线法若对方程组 (1)线性化时使用插值方法确定线性方程组 199-19(6)中的和,则可得到一类称为割线法的迭代序列假定已知第步近似，为确定和,可在附近取个辅助点(=1,2,),使个向量199-20199-21线性无关，由插值条件可知199-22由此可求得 199-23由(6)解得199-26以此作为方程 (1)的新近似，记作199-44，于是得到199-27(7)(7)称为解非线性方程组的割线法。辅助点 取得不同就得到不同的割线法程序，例如取199-28199-29199-40为常数(=1,2,)，就得到与(5)相同的程序，由于它只依赖于点的信息，故也称一点割线法,若取199-31它依赖于点及199-44, 称为两点割线法。其他多点割线法由于稳定性差，使用较少。布朗方法布朗采用对每个分量方程 ()=0逐个进行线性化并逐个消元的步骤，即在每迭代步中用三角分解求线性方程组的解，得到了一个效率比牛顿法提高近一倍的迭代法，即199-32式中 199-33(8)中当=时求得记作199-36,再逐次回代,求出199-37199-41(=-1,-2,1)就完成了一个迭代步。布朗迭代程序的敛速仍保持p2，而每一迭代步的工作量199-38，故效率199-39对这方法还可与牛顿法一样进行改进，得到一些效率更高的算法。这类方法是70年代以来数值软件包中常用的求解非线性方程组的算法。拟牛顿法为减少牛顿法的计算量，避免计算雅可比矩阵及其逆，60年代中期出现了一类称为拟牛顿法的新算法,它有不同的形式，常用的一类是秩1的拟牛顿法，其中不求逆的程序为 200-1式中200-3,200-4,200-5，称为逆拟牛顿公式。计算时先给出及 ，由(9)逐步迭代到满足精度要求为止。每步只算 个分量函数值及()的计算量,比牛顿法一步计算量少得多。理论上已证明，当及选得合适时,它具有超线性收敛速度,但实践表明效率并不高于牛顿法，理论上尚无严格证明。最优化方法求方程组 (1)的问题等价于求目标函数为200-6的极小问题,因此可用无约束最优化方法求问题(1)的解（见无约束优化方法）。连续法又称嵌入法，它可以从任意初值出发求得方程组(1)的一个足够好的近似解,是一种求出好的迭代初值的方法。连续法的基本思想是引入参数 kg2kg20,，构造算子H(,)，使它满足条件：H(,0)=f(),H(,)=f()，其中f()=0的解是已知，方程： 200-7(10)在kg2kg20,上有解=()，则()=xin就是方程(1)的解。当有限时，通常取=1，例如可构造。 200-8 (11)这里是任意初值,显然H(,0)=0,H(,1)=f()为了求得(10)在=1的解xin=(1),可取分点0=1=1在每个分点(=1,2,)上，求方程组 H(,)=0(=1,2,)(12)的解，如果取为初值，只要200-12足够小，牛顿迭代就收敛，但这样做工作量较大。已经证明，如果方程组(12)只用一步牛顿法，当=1时，再