非线性方程组数值解法的割线法

如题所述

若对方程组 (1)线性化时使用插值方法确定线性方程组

(6)
中的Ak和bk,则可得到一类称为割线法的迭代序列。假定已知第k步近似尣k,为确定Ak和bk,可在尣附近取n个辅助点у忋(j=1,2,…,n),使n个向量
  
线性无关,由插值条件可知

由此可求得

由(6)解得

以此作为方程 (1)的新近似,记作

,于是得到

(7)
(7)称为解非线性方程组的割线法。辅助点у忋 取得不同就得到不同的割线法程序,例如取
    
为常数(j=1,2,…,n),就得到与(5)相同的程序,由于它只依赖于尣点的信息,故也称一点割线法,若取

它依赖于点尣及

, 称为两点割线法。其他多点割线法由于稳定性差,使用较少。
非线性方程组数值解法 - 布朗方法 布朗采用对每个分量方程 ƒi(尣)=0逐个进行线性化并逐个消元的步骤,即在每迭代步中用三角分解求线性方程组的解,得到了一个效率比牛顿法提高近一倍的迭代法,即

式中

(8)中当i=n时求得xn记作

,再逐次回代,求出
  
(i=n-1,n-2,…,1)就完成了一个迭代步。布朗迭代程序的敛速仍保持p=2,而每一迭代步的工作量

,故效率

对这方法还可与牛顿法一样进行改进,得到一些效率更高的算法。这类方法是70年代以来数值软件包中常用的求解非线性方程组的算法。
非线性方程组数值解法 - 拟牛顿法 为减少牛顿法的计算量,避免计算雅可比矩阵及其逆,60年代中期出现了一类称为拟牛顿法的新算法,它有不同的形式,常用的一类是秩1的拟牛顿法,其中不求逆的程序为

式中

,

,

,称为逆拟牛顿公式。计算时先给出尣及 B0,由(9)逐步迭代到满足精度要求为止。每步只算 n个分量函数值及O(n)的计算量,比牛顿法一步计算量少得多。理论上已证明,当尣及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)
这里尣是任意初值,显然H(尣,0)=0,H(尣,1)=ƒ(尣)。为了求得(10)在t=1的解尣=尣(1),可取分点0=t0<t1<…<tN=1在每个分点ti(i=1,2,…,N)上,求方程组 H(尣,ti)=0 (i=1,2,…,N) (12)
的解尣,如果取尣为初值,只要

足够小,牛顿迭代就收敛,但这样做工作量较大。已经证明,如果方程组(12)只用一步牛顿法,当t=tN=1时,再用牛顿迭代,结果仍具有2阶收敛速度。以(11)为例,得到连续法的程序为:

若H(尣,t)的偏导数Ht(尣,t)及

在D×【0,1】嶅R

上连续。且

非奇异,则由(10)对t求导可得到等价的微分方程初值问题:

(13)
于是求方程(10)的解就等价于求常微初值问题(13)的解,求(13)的解可用数值方法由t=0计算到t=tN=b得到数值解

。已经证明只要N足够大,以尣为初值再进行牛顿迭代可收敛到方程(1)的解x,这种算法称为参数微分法。
20世纪60年代中期以后,发展了两种求解非线性方程组(1)的新方法。一种称为区间迭代法或称区间牛顿法,它用区间变量代替点变量进行区间迭代,每迭代一步都可判断在所给区间解的存在惟一性或者是无解。这是区间迭代法的主要优点,其缺点是计算量大。另一种方法称为不动点算法或称单纯形法,它对求解域进行单纯形剖分,对剖分的顶点给一种恰当标号,并用一种有规则的搜索方法找到全标号单纯形,从而得到方程(1)的近似解。这种方法优点是,不要求ƒ(尣)的导数存在,也不用求逆,且具有大范围收敛性,缺点是计算量大。

温馨提示:答案为网友推荐,仅供参考
相似回答