正文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+m
n,于是该法的效率
。当
n=10,m=7时,
当
n=100,m=37时,
,由此看到修正牛顿法(4)比牛顿法效率高,且m 越大效果越明显。
在计算机上往往采用不计算偏导数的离散牛顿法,即
(5)式中
,其中
ej为
基向量,
,若取
,则(5)仍具有2阶收敛速度。其效率与牛顿法相同。
若在牛顿法(2)中解线性方程组不用直接法,而采用迭代法则得到一类解非线性方程组的双重迭代法。按解线性方程组采用的方法不同就得到不同名称的迭代法,如牛顿-
赛德尔迭代法,牛顿-
sor迭代法,牛顿-ADI迭代法,等等。这些方法都具有
超线性收敛速度,工作量也比牛顿法大,除了对某些特殊稀
疏方程组外,通常用得校少。若将解线性方程组迭代法的思想直接用于非线性方程组(1),然后把(1)化为一维方程求解,可得到另一类双重迭代法,由于采用的迭代法与解一维非线性方程的方法不同,则得到不同的双重迭代法。如果利用SOR迭代法后再用牛顿法解一维方程则得SOR-牛顿迭代法,在牛顿法中只计算一步而不进行迭代,则得一步的SOR-牛顿迭代,其计算公式可表示为
式中记号嬠
iƒi表示
;
ω为迭代参数,当
ω=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)就完成了一个迭代步。布朗迭代程序的敛速仍保持
p=2,而每一迭代步的工作量
,故效率
对这方法还可与牛顿法一样进行改进,得到一些效率更高的算法。这类方法是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=
t0t1<>
tN=1在每个分点
ti(
i=1,2,…,
N)上,求方程组
H(尣,ti)=0 (i=1,2,…,N) (12)
的解尣
i,如果取尣
i-1为初值,只要
足够小,牛顿迭代就收敛,但这样做工作量较大。已经证明,如果方程组(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足够大,以尣
N为初值再进行牛顿迭代可收敛到方程(1)的解
x*,这种算法称为参数微分法。
20世纪60年代中期以后,发展了两种求解非线性方程组(1)的新方法。一种称为区间迭代法或称区间牛顿法,它用区间变量代替点变量进行区间迭代,每迭代一步都可判断在所给区间解的存在惟一性或者是无解。这是区间迭代法的主要优点,其缺点是计算量大。另一种方法称为
不动点算法或称单纯形法,它对求解域进行单纯形剖分,对剖分的顶点给一种恰当标号,并用一种有规则的搜索方法找到全标号单纯形,从而得到方程(1)的近似解。这种方法优点是,不要求
ƒ(尣)的导数存在,也不用求逆,且具有
大范围收敛性,缺点是计算量大。
[1] 参考书目J.M.Ortega and W.G.Rheinboldt,Iterative Solution of Nonlinear Equations in Several variables,Academic Press,New York,1970.
点击加载更多
加载中...
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。