循环迭代法

2024-12-30

循环迭代法（精选4篇）

循环迭代法篇1

0 引言

Excel中,如果公式引用自己所在的单元格,不论是直接的还是间接的,都称为循环引用[1];而迭代法[2]是数值计算中求解各种数值问题的最常用方法之一。长期以来,人们主要使用计算机高级语言(如C语言或FORTRAN语言等),通过编程方法实现迭代计算。但这样做的缺点是既不简便,也不直观。因为不论是在实际应用中,还是在教学过程中,若要运行用某种计算机高级语言编写的程序,不仅需要相应的高级语言软件环境,而且用户也需具备较强的编程能力和调试程序能力,但这并非对所有的工程技术人员都能做到。通过使用Excel的循环引用实现迭代计算,不仅不需要编写程序,也不需要专门的数学软件,而且还可以简化迭代计算过程的中间操作,自动、快速、直接地得到迭代计算结果。

需要说明,当用户在Excel的工作薄中输入循环引用公式(如在单元格A1中输入:=A1+1)时,默认情况下Excel并不自动执行循环引用,而是给出一个提示信息框,让用户在几种处理之间作出选择。这是因为Excel中循环引用的实质就是迭代计算,而所计算的迭代公式就是用户输入的循环引用公式。因此要使Excel能够正常执行循环引用,并控制由循环引用自动完成的迭代计算次数与精度。在输入循环引用公式之前,需要用户在Excel“选项”对话框的“重新计算”选项卡中,必须选中“迭代计算”复选框,并根据实际问题的需要,设置“迭代计算”栏中的“最多迭代次数”(默认值为100)和“最大误差”(默认值为0.001)。如果用户不改变这两项的默认值,在选中“迭代计算”复选框的前提下, Excel将对工作薄中用户输入的循环引用公式自动进行迭代计算,并在100次迭代后或在两次相邻迭代得到的数值变化小于0.001时,停止迭代计算。因此一般说来,设置“最多迭代次数”越高,同时设置“最大误差”越小,迭代计算结果就越精确,但相应的Excel用于计算的时间也就越多。对于本文中的计算实例,我们是将“最大误差”设置为0.0000001,而“最多迭代次数”保持默认值不变。

1使用循环引用自动完成求解线性方程组的迭代计算

对于求解n阶线性方程组的迭代法[2]:

x(k+1)=Bx(k)+f k=0,1,2,… (1)

其中B称为迭代矩阵,只要迭代法收敛,利用Excel的循环引用可以自动、快速、直接地得到线性方程组的近似解。

例如,求解线性方程组:

$(\begin{matrix} 10 & - 1 & - 2 \\ - 1 & 10 & - 2 \\ - 1 & - 1 & 5 \end{matrix}) (\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \end{matrix}) = (\begin{matrix} 7.2 \\ 8.3 \\ 4.2 \end{matrix})$

的雅可比(Jacobi)迭代公式为:

$(\begin{matrix} x_{1}^{(k + 1)} \\ x_{2}^{(k + 1)} \\ x_{3}^{(k + 1)} \end{matrix}) = (\begin{matrix} 0 & 0.1 & 0.2 \\ 0.1 & 0 & 0.2 \\ 0.2 & 0.2 & 0 \end{matrix}) (\begin{matrix} x_{1}^{(k)} \\ x_{2}^{(k)} \\ x_{3}^{(k)} \end{matrix}) + (\begin{matrix} 0.72 \\ 0.83 \\ 0.84 \end{matrix})$

我们在Excel中利用循环引用实现该迭代计算的操作如下:

1)在工作表Sheet1的单元格区域A1:C3中输入迭代矩阵的各元素,并在单元格区域D1:D3中分别输入0.72,0.83,0.84;

2)选择单元格区域A5:A7,输入公式:

=MMULT(A1:C3,A5:A7)+D1:D3,如图1所示。

(说明:公式中的MMULT为Excel提供的计算两个矩阵乘积的函数,并注意到在下一步操作完成后单元格区域A5:A7中的计算公式引用了自己所在的单元格,此即为循环引用)3)按Ctrl+Shift+Enter键形成数组公式:{=MMULT(A1:C3,A5:A7)+D1:D3},完成操作。此时,单元格区域A5:A7中的值1.099999989, 1.199999989, 1.299999987即为利用循环引用自动完成的雅可比迭代的计算结果。与原方程组的精确解1.1,1.2,1.3相比较,显然已具有较高的计算精度,并且满足我们设置的“最大误差”为 0.0000001的精度要求。

2使用循环引用自动完成求解方程根的迭代计算

对于单变量非线性方程求根的迭代法[2]

xk+1=f(xk) k=0,1,2,… (2)

其中f(x)称为迭代函数,方程F(x)=0与x=f(x)等价。如果对选取的初始近似x0,迭代法收敛,则利用Excel的循环引用,同样可以自动、快速、直接地得到方程的近似根。

例如,求方程F(x)=x4-2x-4=0根的牛顿法迭代公式为:

$x_{k + 1} = x_{k} - \frac{x_{k}^{4} - 2 x_{k} - 4}{4 x_{k}^{3} - 2} k = 0, 1, 2, \dots (3)$

由于当选取初始近似x0=0时迭代公式(3)收敛,利用Excel的循环引用完成该迭代计算的操作如下:

在Excel的工作表Sheet2的单元格A1中输入公式:

=A1-(A1^4-2*A1-4)/(4*A1^3-2)

按Enter键即完成操作。此时单元格A1中的值-1.143901112即为原方程根的近似值。

需要说明的是:众所周知,对于求解线性方程组的迭代法(1),当ρ(B)<1(即B的谱半经小于1)时[2],对任意的初始向量x(0),迭代序列{x(k)}均收敛于线性方程组的唯一解;与求解线性方程组的迭代法不同,求方程根的迭代法收敛与否,以及迭代序列{xk}收敛于方程的哪个根,均依赖于初始近似x0的选取。但Excel中的循环引用只是把被循环引用单元格的初始值(相当于将x0)作为0处理,因此,Excel中的循环引用只能直接处理初始近似为0的迭代计算。

对于方程求根的迭代法,当需要取非零的 $\bar{x}$ 作为初始近似时,我们给出的解决办法是:通过平移原点,可以把以非零的 $\bar{x}$ 作为初始近似时收敛的迭代法(2)转化为以x0=0为初始近似时也收敛的迭代法:

$x_{k + 1} = f (x_{k} + \bar{x}) - \bar{x} k = 0, 1, 2, \dots (4)$

(注意:此处利用了方程x=f(x)的变形: $x + \bar{x} = f (x + \bar{x})$ ),这样就可以利用Excel的循环引用,求得以x0=0为初始近似时公式(4)的迭代计算结果x*,从而x*+ $\bar{x}$ 即为原方程F(x)=0根的近似值。

例如,若要以 $\bar{x}$ =1为初始近似,用牛顿法求上述方程F(x)=x4-2x-4=0的根,可以将迭代公式(3)修改为:

$x_{k + 1} = x_{k} - \frac{(x_{k} + 1)^{4} - 2 (x_{k} + 1) - 4}{4 (x_{k} + 1)^{3} - 2} k = 0, 1, 2, \dots (5)$

利用循环引用我们只需进行如下操作:

在Excel的工作表Sheet2中:

1)在单元格B2中输入公式:=A2+1;

2)在单元格A2中输入公式:

=A2-(B2^4-2*B2-4)/(4*B2^3-2)

按Enter键完成操作。此时单元格A2中的值0.642934884加1,也就是B2中的值1.642934884就是原方程另一个根的近似值。

3使用循环引用自动完成求解非线性方程组的迭代计算

对于求解n个变量x=(x1,x2,…,xn)非线性方程组

F(x)=0 (6)

其中F(x)=(f1(x),f2(x),…,fn(x))T的简单迭代法[3]:

x(k+1)=Ψ(x(k)) k=0,1,2,… (7)

如果对选取的初始向量x(0)=(x $_{1}^{(0)}$ ,x $_{2}^{(0)}$ ,…,x $_{n}^{(0)}$ ),迭代法(7)收敛,则利用Excel的循环引用,同样可以自动、快速、直接地得到非线性方程组(6)的近似解。

需要注意的是,与单变量非线性方程求根的迭代法一样,若需要选取非零的 $\bar{x} = (\bar{x}_{1}, \bar{x}_{2}, \dots, \bar{x}_{n})$ 作为初始近似时,仍然需要通过平移原点,把以非零的 $\bar{x}$ 为初始近似时收敛的迭代法(7)转化为以x(0)=(0,0,…,0)为初始近似时也收敛的迭代法:

$x^{(k + 1)} = Ψ (x^{(k)} + \bar{x}) - \bar{x} k = 0, 1, 2, \dots (8)$

于是使用Excel的循环引用,求得以x(0)=(0,0,…,0)为初始近似时公式(8)的迭代计算结果x*,从而 $x^{*} + \bar{x}$ 即为非线性方程组(6)的近似解。

例如,求解(两个变量的)非线性方程组

${\begin{cases} f_{1} (x_{1}, x_{2}) = x_{1} x_{2} - x_{2}^{2} + x_{1}^{2} x_{2} - 5 = 0 \\ f_{2} (x_{1}, x_{2}) = x_{1}^{2} + x_{2}^{2} - 6 x_{2} + 1 = 0 \end{cases} (9)$

的牛顿法迭代公式为:

$\begin{array}{l} (\begin{matrix} x_{1}^{(k + 1)} \\ x_{2}^{(k + 1)} \end{matrix}) = (\begin{matrix} x_{1}^{(k)} \\ x_{2}^{(k)} \end{matrix}) - \\ (\begin{matrix} \frac{\partial f_{1} (x_{1}^{(k)}, x_{2}^{(k)})}{\partial x_{1}} & \frac{\partial f_{1} (x_{1}^{(k)}, x_{2}^{(k)})}{\partial x_{2}} \\ \frac{\partial f_{2} (x_{1}^{(k)}, x_{2}^{(k)})}{\partial x_{1}} & \frac{\partial f_{2} (x_{1}^{(k)}, x_{2}^{(k)})}{\partial x_{2}} \end{matrix})^{- 1} (\begin{matrix} f_{1} (x_{1}^{(k)}, x_{2}^{(k)}) \\ f_{2} (x_{1}^{(k)}, x_{2}^{(k)}) \end{matrix}) \end{array}$

也可简记为

x(k+1)=x(k)-F′(x(k))-1F(x(k)) (10)

注意对于非线性方程组(9),其中的四个偏导数分别为:

$\frac{\partial f_{1} (x_{1}, x_{2})}{\partial x_{1}} = x_{2} + 2 x_{1} x_{2}$

$\frac{\partial f_{1} (x_{1}, x_{2})}{\partial x_{2}} = x_{1} - 2 x_{2} + x_{1}^{2}$

$\frac{\partial f_{2} (x_{1}, x_{2})}{\partial x_{1}} = 2 x_{1} \frac{\partial f_{2} (x_{1}, x_{2})}{\partial x_{2}} = 2 x_{2} - 6$

而且当取初始近似x(0)为 $\bar{x} = (1.5, 1)$ 时,迭代公式(10)收敛,于是将其转化为当取初始近似x(0)为(0,0,…,0)时也收敛的迭代法:

$x^{(k + 1)} = x^{(k)} - F^{'} (x^{(k)} + \bar{x})^{- 1} F (x^{(k)} + \bar{x})$

k=0,1,2,… (11)

因此利用Excel的循环引用只需进行如下操作(注意:为观察牛顿迭代法(11)对选取不同初始近似值时的收敛情况,我们用两个单元格A3,A4存放初始近似 $\bar{x} = (1.5, 1)$ 的值):

在Excel的工作表Sheet3中:

1)在单元格A3,A4中分别输入1.5,1;

2)在单元格B1,B2中分别输入公式:=A1+A3, =A2+A4;

3)在单元格C1,D1,E1,C2,D2,E2中分别输入以下公式:

=B2+2*B1*B2, =2*B1,=B1-2*B2+B1^2,

=2*B2-6,=B1*B2-B2^2+B1^2*B2-5,

=B1^2+B2^2-6*B2+1

于是单元格区域B1:E2中的值见图2所示。

(其中单元格区域B1:B2中的值为初始近似 $x^{(0)} + \bar{x}$ 的值;单元格区域C1:D2中为四个偏导数在 $x^{(0)} + \bar{x}$ 值的计算公式;单元格区域E1:E2中为函数向量在 $x^{(0)} + \bar{x}$ 值的计算公式)

4)选择单元格区域A1:A2,输入公式:

=A1:A2-MMULT(MINVERSE(C1:D2),E1:E2)

(说明:公式中的MINVERSE为Excel提供的求逆矩阵的函数)

5)按Ctrl+Shift+Enter键形成数组公式即完成操作。

此时,单元格区域A1:A2中的值(0.499999998, -2.48168E-09)与 $\bar{x} = (1.5, 1)$ 相加,也就是单元格区域B1:B2中的值(1.999999998, 0.999999996)即为非线性方程组(9)的近似解,与相应的精确解(2,1)相比,显然已具有较高的计算精度,并且满足我们设置的“最大误差”为 0.0000001的精度要求。

此外,若还要计算选取其它初始近似值时,利用Excel的自动计算功能,牛顿法(11)的收敛情况,这将变得更加简单。例如,若要计算取初始近似值为 $\bar{x} = (1, 5)$ 时,我们只需将单元格区域A3:A4中存放的 $\bar{x}$ 修改为(1,5)即可,此时单元格区域B1:B2中的值(2.000000001, 4.999999999) 即为非线性方程组(9)的另一个根(2, 5)的近似解。如图3所示。

4 结论

开发Excel的强大计算功能用于求解数值计算问题[4],既不需要设计程序,也不需要专门的数学软件,而且计算精度控制方便、操作简单,同时注意到Excel软件在各类计算机上随处可见,这不仅为课堂教学,而且也为解决工程计算问题提供了极大的便利。

参考文献

[1]张威,陈海波.中文Microsoft Office XP完全手册[M].北京:北京希望电子出版社,2001.

[2]李庆杨,王能超,易大义.数值分析[M].北京:清华大学出版社,2001.

[3]冯果忱.非线性方程组迭代解法[M].上海:上海科学技术出版社,1989.

[4]彭海静.基于Excel求高次方程的解[J].计算机应用与软件,2006,23(2).

循环迭代法篇2

将压缩感知应用与无线传感网络相结合, 可以有效减少感知节点的数目;并可以大大节约有限的节点资源, 其基本思想即通过无线传感器网络中多个节点的协作感知, 相对于单个节点分布式传输, 可大幅度提高数据感知精度与准确性。但这种协作感知无线传感网络在总资源开销方面与感知节点检测方面, 在实际中实现难度较大或难以适用具体的应用[3]。文献[4]提出了一种降低节点资源开销的数传节点感知方法 (记为OMP算法) , 即保证感知可靠性要求, 通过降低感知节点数目以降低资源开销;但并没有给出具体的协作方法, 也没有给出理论计算最优值;文献[5]提出了一种利用检测概率的协作感知方法 (记为DAOMP算法) , 但该方法需假设所有节点具有相同的检测与先验条件, 很难应用到实际场合;文献[6]提出了一种自适应迭代协作感知方法 (记为DOMP算法) , 有效提高感知精度, 但该方法需要知道每个感知节点检测概率, 同时也没有解决整个传感器网络资源开销问题;并且动态适应性较差。

为了对上述研究进行研究, 在研究大规模稀疏型传感网络数据属性的前提下, 从随节点数目急剧增大而导致网络堵塞的问题与节约资源的角度出发, 提出了一种基于协作感知的大规模稀疏网络数传节点优化方法。该方法利用大规模稀疏网络数传节点在空间上的相关性, 构建大规模联合稀疏模型, 自适应选择最优节点作为感知节点;并采用循环迭代控制算法对稀疏网络节点数据进行压缩, 以最大程度用有限节点获得最大信息量, 最后再利用信号稀疏性重构节点数据。

1 稀疏分布节点关联模型的设计

无线传感器网络数据节点数量及规模越来越大, 而数据节点增多导致资源与功耗急剧提高, 将压缩感知技术应用于无线传感器网络中可以减少感知节点数目, 降低资源开销。大规模稀疏型无线传感网络数据节点通信模型如图1所示, 假设该大规模稀疏型无线传感网络模型中, 总共包含N个数据传感器节点, 其中, 工作数据传感器节点数目为K, 观测几点的数目为M。

假设无线传感器网络信道为多径衰弱模型, 且包络服从瑞利分布, 则第n个传感器节点接收到第m个传感器节点数据信号的数学函数表达式为:

式 (1) 中, dism, n表示第m个观测传感器节点到第n个传感器节点的传输距离;α表示衰减因子, |rm, n|表示信号包络幅度模值。

那么包含N个传感器节点与M个传感器观测点的无线传感器网络传输函数表示为:

式 (2) 中, cm, n表示第m个传感器观测节点检测到第n个传感器节点的信号。

定义稀疏信号向量矩阵EN×1, 向量矩阵EN×1中的值为1或0, 其中, 1表示该数据节点传感器处于工作状态, 0表示该数据节点传感器处于非工作状态。假设信号中的噪声为高斯噪声, 服从均值为0, 方差为α2, 则观测传感器节点的信号数学表达式为:

式 (3) 中, CM×NEN×1表示为M个观测点传感的信号函数;εM×1表示高斯白噪声。选用该稀疏模型作为后文研究协作感知节点优化方法的基础。

2 基于稀疏分布的循环迭代控制策略

2.1 问题描述

压缩感知 (compressed sensing, CS) 技术采用低于原始信号频率进行欠采样, 有效降低数据存储量。基于压缩感知的无线传感器网络只要有一部分少量的传感器节点处于工作状态, 而另一部分传感器节点处于非工作状态, 就需要精确感知处于工作状态的数据传感器节点。但在实际应用中仍然面临着很多问题:一类是处于工作状态的数据传感器节点会随传输路径的增加而逐渐衰减;另一类是在实际传输场合下, 常常存在形形色色的噪声干扰;三是观测节点传感器就常常受到多径信号的干扰从而影响接收[7]。

压缩感知理论框架如图2所示, 第一步首先建立稀疏信号模型, 分析原始信号构建稀疏信号;第二步对构建的可压原始信号进行稀疏变换;第三步再对稀疏变换后的信号采用观测矩阵处理;第四步最后再利用稀疏信号最优化理论进行逆变换重构原始信号。

假设长度为N的可压缩信号, 经稀疏变换, 得到观测矩阵数学表达式为:

式 (4) 中, ΦM×N表示可压矩阵;ΨN×N表示稀疏基矩阵;SN×1为可压信号向量。

利用式 (4) 进行重构原始信号可以等价为欠定方程求解问题, 转化为求解最小范数解问题[8], 即

将压缩感知技术应用到无线传感器数据节点网络优化中, 利用大规模稀疏网络数传节点在空间上的相关性, 构建大规模联合稀疏模型, 自适应选择最优节点作为感知节点, 并采用循环迭代控制算法对稀疏网络节点数据进行压缩, 以较少节点资源获得最大的数据信息。

2.2 循环迭代控制算法

基于压缩感知的无线传感器网络数据节点, 使用较少的传感器观测节点来检测无线传感器网络中产生的稀疏事件, 需满足如式 (6) 数学不等式关系[9]。

式 (6) 中, c为常量。由式 (6) 可知, 当处于工作状态节点K值减小时, 其值也随之减小, 也一定程度上降低了数据观测传感节点的数量, 故可以以较少的数据传感节点资源获取最大的稀疏信号数据信息。稀疏矩阵求解可进一步转化为求解1范数问题:

令, 则式 (7) 进一步转化为:

根据欧拉拉格朗日定量求解目标函数表示为[10]:

同时式 (9) 两边求导可得:

根据稀疏梯度解目标函数最优解即可转化为:

式 (11) 中, wi (l+1) =1/ (|eil|+α) 为自适应参数可调因子。

可将上述目标函数求解问题转化为循环迭代求最优解问题, 在此基础上提出一种基于稀疏分布的循环迭代控制算法, 其具体步骤如下:

(1) 首先, 令i=0, l=0;初始化可调迭代参数w (l+1) i;

(2) 每次迭代根据公式 (10) 更新可调参数:

(3) 根据公式计算相邻空间节点的稀疏节点相对误差:

式中, WN×N=diag[ (|ei|+α) -1]N×N。

(4) 当迭代次数大于等于最大迭代次数时, 就停止迭代, 返回主程序, 传送检测结果;当迭代次数小于等于最大迭代次数时, 就跳转步骤 (2) 继续循环迭代。

循环迭代控制算法能够精确的恢复原始的信号, 并且具有良好的抗噪性能。

2.3 算法实现

基于协作感知的大规模稀疏网络数传节点优化方法。该方法利用大规模稀疏网络数传节点在空间上的相关性, 构建大规模联合稀疏模型, 自适应选择最优节点作为感知节点, 并采用循环迭代控制算法对稀疏网络节点数据进行压缩, 以最大程度用有限节点获得最大信息量, 最后再利用信号稀疏性重构节点数据。

该方法以有限的节点资源满足估计精确度的要求, 并有效减少了感知的节点数目, 从而降低系统的资源消耗。

3 仿真结果与性能分析

采用Matlab7.0软件对提出的基于协作感知的稀疏数传节点优化方法进行仿真验证。系统仿真参数设置如下:假设各感知节点是独立的, 且在空间存在一定的弱相关性, 无线传输信号为高斯白噪声, 且包络服从瑞利分布, 无线传感器网络中包括256有效节点, 其中, 处于工作状态的传感器节点有64个, 处于非工作状态的传感器节点有192个, 无线通信信道传输存在衰减, 主要对包括OMP算法, AOMP算法, DAOMP算法以及本文提出的算法进行仿真验证。

图3为各种算法信号重构对比曲线, 从仿真结果可以容易得出, 利用稀疏自适应匹配追踪算法和改进的稀疏自适应匹配追踪算法分别对的原始信号处理, 在其它条件相同的情况下, 本文所提出的重构信号与原始信号较为相近, 其恢复的信号基本就是原始信号的再现。

图4为各种算法节点数量与重构错误率对比曲线。在成功检测概率相同的情况下, 改进的循环迭代控制算法比传统OMP算法使用更少的观测传感器节点数目。同时, 随着观测传感器节点数目的增多, 循环迭代控制算法的检测曲线渐渐趋于平稳, 表明该检测算法具有较好的稳健性, 且收敛速度较快。

图5为两种算法稀疏检测概率对比曲线。比较这两种恢复算法的恢复结果, 可以得出如下结论:本文算法的恢复效果要比原算法好。该方法以有限的节点资源满足估计精确度的要求, 并有效减少了感知的节点数目, 从而降低系统的资源消耗, 有效提升了无线传感网络自适应感知稀疏信号的概率。

4 结束语

本文在研究大规模稀疏型传感网络数据随节点数目急剧增大而导致网络堵塞的问题基础上, 将协作感知与自适应相结合, 提出了一种基于稀疏分布的空间节点资源循环迭代控制算法。该方法以有限的节点资源满足估计精确度的要求, 并有效减少了感知的节点数目, 从而降低系统的资源消耗。

摘要：为解决大规模稀疏型传感网络数据随节点数目急剧增大时导致网络堵塞的问题, 提出了基于稀疏分布的空间节点资源循环迭代控制算法。该方法利用大规模稀疏网络节点在空间上的弱相关性, 构建了一个表达联合稀疏关系的模型。通过通信特征做到自适应选择最优节点作为感知节点, 针对稀松节点数量有限、无法传递海量信息的问题, 采用循环迭代控制对稀疏网络节点数据进行压缩, 以最大程度用有限节点获得最大信息量;再利用信号稀疏性特征重构节点数据。仿真结果表明, 该方法以有限的节点资源满足估计精确度的要求, 并有效减少了感知的节点数目, 降低系统的资源消耗。

关键词：无线传感网络,压缩感知,稀疏分布,循环迭代

参考文献

线性l1问题的一个迭代法篇3

在科技工程的许多领域中需要求解像超定线性方程组和曲线拟合之类的问题, 这时需要求解线性l1问题。设

$\begin{array}{l} A = (a_{1}, a_{2}, \dots, a_{n}) = \\ (\begin{matrix} a_{11} & a_{12} & \dots & a_{1 m} \\ a_{21} & a_{22} & \dots & a_{2 m} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n m} \end{matrix}) \in R^{n \times m} ‚ b = (\begin{matrix} b_{1} \\ b_{2} \\ ⋮ \\ b_{m} \end{matrix}) ‚ \end{array}$

线性l1问题可以表述为

$\min_{x \in R^{n}} f (x) = ∥ A^{Τ} x - b_{1} ∥ =$ $\sum_{i = 1}^{m}$ |aTix-bi| (1)

问题 (1) 是一个不可微优化问题, 目前问题 (1) 已有了一些解法, 都是直接解法, 就是运用适当的手法将其转化为一个线性规划问题来求解, 进而得到其精确解。这些方法缺点是所转化的等价问题规模都比原来大, 当问题 (1) 的规模较大时, 解法比较复杂, 占用计算机的资源较多。利用极大熵技术将问题 (1) 转化为无约束可微优化问题, 再利用最优化的解法来得到问题 (1) 的满足一定精度的数值解。与直接法相比, 此方法简单易于操作, 占用计算机的资源较少。

为叙述方便, 使用以下记号:

E (x) ={i|aTix-bi=0, i=1, 2, …, m},

σi (x) =sgn (aTix-bi) , i∉E (x) 。

ri (x) =aTix-bi, i=1, 2, …, m,

r (x) = (r1 (x) , r2 (x) , …, rm (x) ) 。

于是,

f (x) =‖ATx-b‖1= $\sum_{i = 1}^{m}$ |aTix-bi|= $\sum_{i = 1}^{m}$ |ri (x) |

= $\sum_{i = 1}^{m}$ max{ri (x) , -ri (x) }。

所以f (x) 的极大熵函数为

$F (x, p) = \frac{1}{p}$ $\sum_{i = 1}^{m}$ ln (epri (x) +e-pri (x) ) 。

其中, p>0为一个可调参数, 由于p→+∞时, F (x, p) 一致收敛于f (x) , 所以可以用p>0充分大时 $\min_{x} F (x, p)$ 的最优解来作为问题 (1) 的近似解。

1 极大熵函数F (x, p) 的性质

根据文献[1]和文献[2]可得到下列结论。

引理1 当p→+∞时, F (x, p) →f (x) , 且有

$f (x) < F (x, p) \leq f (x) + \frac{m}{p} \ln 2$ 。 ⌷

引理2 函数F (x, p) 关于p严格单调递减。 ⌷

引理3 函数F (x, p) 是关于x的凸函数。

证明对任意k=1, 2, …, n;有

$\frac{\partial F}{\partial x_{k}} =$ $\sum_{i = 1}^{m}$ $\frac{e^{p r_{i} (x)} - e^{- p r_{i} (x)}}{e^{p r_{i} (x)} + e^{- p r_{i} (x)}} a_{i k}$ ,

$\frac{\partial^{2} F}{\partial x_{k}^{2}} =$ $\sum_{i = 1}^{m}$ $\frac{4 p a_{i k}^{2}}{[e^{p r_{i} (x)} + e^{- p r_{i} (x)}]^{2}} > 0$ 。

所以函数F (x, p) 是关于x的凸函数。

2 算法

根据极大熵函数F (x, p) 的性质, 可以得到一个求线性l1问题的一个迭代法。

(1) 选取p1>0, 初始点x (0) , 置k:

=1;

(2) 以x (k-1) 为初始点, 求

$\min_{x} F (x, p_{k}) = \frac{1}{p_{k}}$ $\sum_{i = 1}^{m}$ ln (epkri (x) +e-pkri (x) ) (2)

得最优解x (k) ;

(3) 若|f (x (k) ) -F (x (k) , pk) |<ε, 停止计算, 输出x (k) ;否则增大pk, 取pk+1>pk, 置k:

=k+1, 转 (2) 。 ⌷

对于子问题 (2) , 可以采用解无约束最优化问题的某一个方法来求解。由于F (x, p) 的Hession矩阵一般较为复杂, 因而可使用信赖域法、FR法或BFGS方法等。

3 算法的收敛性

由文献[3]和文献[4]可得到下面的引理。

引理4 (线性l1问题的最优性条件)

x∈Rn为问题 (1) 的最优解的充分必要条件是, 存在常数λi∈[-1, 1], i∈E (x) , 使得

$\sum_{i \notin E (x)}$ σi (x) ai= $\sum_{i \in E (x)}$ λiai。 ⌷

下面讨论算法的收敛性。

定义1 若x满足ᐁxF (x, p) =0, 则称x为问题 (2) 的稳定点。

定理1 若 $\bar{x}^{(k)}$ 为问题 (2) 的稳定点, x*为 $\bar{x}^{(k)}$ 当pk→+∞时的一个极限点, 则x*为线性l1问题 (1) 的最优解。

证明设 ${\bar{x}^{(k_{i})}}$ 为数列 ${\bar{x}^{(k)}}$ 的一个收敛于x*的子列, 即当pk→+∞时, $\bar{x}^{(k_{i})} \to x^{*}$ , 则由F (x, p) 的表达式有

$\nabla_{x} F (x, p) = \frac{1}{p}$ $\sum_{i = 1}^{m}$ $\frac{p e^{p r_{i} (x)} - p e^{- p r_{i} (x)}}{e^{p r_{i} (x)} + e^{- p r_{i} (x)}} a_{i} =$

$\sum_{i = 1}^{m}$ $\frac{e^{p r_{i} (x)} - e^{- p r_{i} (x)}}{e^{p r_{i} (x)} + e^{- p r_{i} (x)}} a_{i} \overset{Δ}{=}$

$\sum_{i = 1}^{m}$ hi (x, p) ai。

这里hi (x, p) = $\sum_{i = 1}^{m}$ $\frac{e^{p r_{i} (x)} - e^{- p r_{i} (x)}}{e^{p r_{i} (x)} + e^{- p r_{i} (x)}}$ , 显然, -1<hi (x, p) <1;i=1, 2, …, m。

由于ri (x) 是线性函数, 所以当pk→+∞时,

若ri (x*) >0, 有 $h_{i} (\bar{x}^{(k_{i})}, p_{k_{i}}) \to 1 (3)$

若ri (x*) <0, 有 $h_{i} (\bar{x}^{(k_{i})}, p_{k_{i}}) \to - 1 (4)$

若ri (x*) =0, 有 $- 1 \leq h_{i} (\bar{x}^{(k_{i})}, p_{k_{i}}) \leq 1 (5)$

因为 $\bar{x}^{(k)}$ 为问题 (2) 的稳定点, 即有 $\nabla_{x} F (\bar{x}^{(k)}, p_{k}) = 0$ , 所以, 当pk→+∞时, 有

$\sum_{i = 1}^{m}$ $h_{i} (\bar{x}^{(k)}, p_{k}) a_{i} = 0$ 。

在ri (x*) ≠0处, 当pk充分大时, $r_{i} (\bar{x}^{(k_{i})})$ 与ri (x*) 同号;在ri (x*) =0处, 取λi为 $h_{i} (\bar{x}^{(k_{i})}, p_{k_{i}})$ 的一个极限点, 则由式 (5) 得

$\begin{array}{l} \lim_{p_{k_{i}} \to + \infty} \nabla F_{x} (\bar{x}^{(k_{i})}, p_{k_{i}}) = \lim_{p_{k_{i}} \to + \infty} [\sum_{i \notin E (x^{*})} h_{i} (\bar{x}^{(k_{i})}, p_{k_{i}}) a_{i} + \\ \sum_{i \in E (x^{*})} h_{i} (\bar{x}^{(k_{i})}, p_{k_{i}}) a_{i}] = \sum_{i \notin E (x^{*})} σ_{i} (x^{*}) a_{i} + \sum_{i \in E (x^{*})} λ_{i} a_{i} = 0 。 \end{array}$

且-1≤λi≤1, i∈E (x*) 。

由线性l1问题的最优性条件知, x*为线性l1问题 (1) 的最优解。

定理2 若水平集

L={x|f (x) ≤F (x (1) , p1) }

有界, 则算法产生的点列{x (k) }的任一聚点都是问题 (1) 的最优解。

证明由最优化理论可知[5], 当水平集L有界时, 算法1产生的点列存在极限点x*, 它当然是问题 (2) 的稳定点, 所以根据定理1知道x*是问题 (1) 的最优解。

4 算例

例1 已知

$A^{Τ} = (\begin{matrix} 1 & 0 \\ 0 & 1 \\ 3 & 2 \\ 4 & - 1 \end{matrix}) ‚ b = (\begin{matrix} 2 \\ 3 \\ 4 \\ 8 \end{matrix})$

。

求解 $\min_{x \in R^{2}} f (x) =$ $\sum_{i = 1}^{4}$ |aTi-bi|。

取初始点

$x^{(0)} = (\begin{matrix} 1 \\ 1 \end{matrix})$

, 子问题 (2) 使用FR法, 结果如表1。

迭代5次得到近似最优解为x*≈ (1.818 4, -0.725 8) T, 目标函数最优值近似为3.911 6。

参考最优解为 $x^{*} = (\frac{20}{11}, - \frac{8}{11})^{Τ}$ , 目标函数最优值为 $\frac{43}{11}$ 。

例2 已知

$A^{Τ} = (\begin{matrix} 1 & 0 \\ 0 & 1 \\ 1 & 3 \\ 1 & 4 \\ 1 & 5 \end{matrix}) ‚ b = (\begin{matrix} 1 \\ 0 \\ 2 \\ 3 \\ 2 \end{matrix}) 。$

求解 $\min_{x \in R^{2}} f (x) = \sum_{i = 1}^{5} | a_{i}^{Τ} - b_{i} |$ 。

取初始点

$x^{(0)} = (\begin{matrix} 1 \\ 0 \end{matrix})$

, 子问题 (2) 使用FR法, 结果如表2。

迭代6次得到近似最优解为x*≈ (1.004 1, 0.330 7) T, 目标函数最优值近似为1.671 2.

参考最优解为 $x^{*} = (1, \frac{1}{3})^{Τ}$ , 目标函数最优值为 $\frac{5}{3} .$

摘要：运用极大熵技术, 提出一个求解线性l1问题的迭代法, 与传统的直接解法相比, 提出的极大熵方法具有简单易行、占用计算机资源少的优点, 最后的两个算例表明此算法是可行的。

关键词：线性l1问题,迭代法,极大熵,数值解

参考文献

[1]姚健康, 崔焕钰.非线性l1问题的极大熵方法.应用数学与计算数学学报, 2001;15:79—86

[2]姚健康.线性l1问题的最优解集.科学技术与工程, 2007;6:1147—1149

[3]Charalambous C.On conditions for optimality of the nonlinearl1problem.Math Programming, 1979; (17) :123—135

[4]Bartels R H, Conn A R, Sinclair J W.Minimization techniques for piecewise differentable functions:thel1-solution to an overdetermined linear system.SIAMJ Numb Anal, 1978;15:224—241

循环迭代法篇4

关键词：基坑,支护模拟,位移迭代法

1 我国基坑工程的研究方法

随着高层建筑和底下工程的不断出现, 基坑工程开始受到人们越来越多的重视, 于是基坑的开挖和支护问题就不可避免的也随之出现了。在基坑工程的研究中, 主要涉及到三个方面的问题, 即:支护结构、基坑的稳定性问题以及土体的变形问题。研究基坑工程的方法有很多种, 比如模型观测、工程经验等。在进行基坑理论计算的时候, 最常用的方式是极限平衡法、土抗力法以及位移迭代法。其中位移迭代法可以从时间和空间上全面的反映各种元素对支护结构以及基坑周围土体的受力和位移的情况, 所以在应用上的前景比较广阔。位移迭代法中利用有限元模型进行数值分析在基坑中又是最常用的一种方法, 它主要包括弹性地基杆有限元法和连续介质有限元法两种:

1) 弹性地基杆有限元法:这是一种比较简单的方法, 因此在基坑工程中经常可以看到。主要是因为此种方法是建立在线弹性本构关系上, 不用考虑土体的弹塑性以及土压力随位移的变化情况, 所以在实际中, 这种方法有它的明显的缺点, 就是不能真实的反映土以及结构在位移和荷载上的变化情况。

2) 连续价值有限元法:这种方法在桩土间采用的是接触面单元, 考虑桩土的共同作用。在岩土工程中常常用到的接触面单元是Goodman接触面单元[1]和Desai薄层接触面单元[2]。Goodman接触面单元的概念比较清楚, 只要给出接触面法向刚度Kn与切向刚度Ks, 那么, 从应用工程的角度来看, 这种方法是很方便且易行的, 不过在法向刚度的取值上, 它要求的数值比较大, 目的是为了防止嵌入的过量, 但是也就导致了这种人为设置的法向刚度使得法向应力的误差增大。

2 位移迭代法的有限元模型

2.1 建立模型

下面通过具体实例进行位移迭代法的优先模型分析, 如图1所示:

我们取一断面通过问题分析, 根据对称性, 截取模型的1/2, 将整体模型分成图1中的三部分:即主动土体A、支护结构B以及被动土体C, 其中:

A部分:所承受的荷载为重力, 左侧的边界条件是受水平方向固定约束, 右侧的边界条件是支护桩的反力, 而底部的边界条件受垂直方向固定约束的, 模拟的方式是通过四边形单元来进行模拟, 节点可以是4, 5, 8, 9等节点, 土体通常使用的是弹塑性本构模型。

B部分:在不考虑自重的前提下, 边界条件是两侧的压力, 其中右侧开挖的部分是自由边界, 底部是固定约束。

C部分:所承受的荷载一样也是重力, 左侧的边界条件是支护桩的反力, 右侧的边界条件是水平方向的固定约束, 正好与A部分是相反的, 底部同样是垂直方向的固定约束。通常也是采用的四边形面单元。

2.2 模型计算

用位移迭代法将模型中的三个独立部分分别进行计算, 在三个模型中输入桩体界面上的相互作用力或者位移作为边界的条件, 我们可以假设支护桩的侧壁光滑, 并且以桩体不变形作为初始条件, 那么通过反复的迭代就可以使桩土接触处的位移和水平应力相等, 从而作为求解稳定的条件。

2.3 位移迭代法的实现流程

1) 分别对模型A、B、C建立有限元方程:

公式中:[K]—总刚度矩阵;{δ}—节点位移列阵;{R}—荷载列阵;上表表示不同的模型。

2) 将模型的三个有限元方程按照位移向量重组, 使得桩土共节点处的水平位移集中到一起, 并将坑底以上和以下的位移分开, 并对刚度矩阵和荷载列阵分块, 即得到以下:

公式中:{δ1 AB}、{δ2 AC}分别基坑底面以上和以下支护桩的位移;{R1AB}、{R2AB}分别是基坑底面以上和以下的A对B的作用力;{R2CB}是基坑底面以下C对B的作用力;{δ3 A}、{δ3 C}是除{δ1 AB}、{δ2 AC}以外的节点位移分量的列阵;{R3A}、{R3C}是{δ3 A}、{δ3 C}对应的节点荷载, [Kij A, B, C]是各个模型总刚度矩阵的子块。

3) 前面说了, 如果在只进行一次开挖的情况下, 计算的时候讲初始条件设置为支护桩桩体不变形, 即{δ1AB}0={0}, {δ2 AC}0={0}, 通过方程式 (2) (4) , 可以求得约束结点的水平结点力{R1AB}0、{R2AB}0、{R2CB}0。

4) 将{R1AB}0、{R2AB}0、{R2CB}0作为边界条件再代入 (2) (3) (4) 中, 进而可以求得支护桩个结点的位移{δ1AB}1、{δ2AC}1。

5) 将上述{δ1 AB}1、{δ2 AC}1代入 (2) (4) 公式中, 分别求得约束结点的水平结点力{R1AB}1、{R2AB}1、{R2CB}1。

6) 再将{R1AB}1、{R2AB}1、{R2CB}1代入公式 (3) 中, 求得支护桩各结点的位移{δ1 AB}2、{δ2 AC}2。

7) 对两次求解的结果进行比较, 当其中对应的元素结果值相等时就可以终止计算, 从而获得支护桩与土体的相关参数。在实际中, 可以使用相对误差来判定。

8) 当误差相差太大, 不在允许的范围内时, 那么就要继续重复2——6的步骤, 直到结果满足为止, 迭代结束。

9) 对于多次开挖的基坑工程, 初始条件设置为上一次位移计算的结果, 即{δ1 AB}0={u10}、{δ2AC}0={u20}, 然后重复2—6的步骤。

3 结语

综上所述, 在基坑开挖和支护模拟的研究中, 其他的研究方法要么就是没有考虑支护结构的变形, 要么就是接触面单元的弹性参数不容易确定, 所以有着自身明显的弊端, 而位移迭代法从根本上弥补了这些方法上的不足, 通过建立三个相对独立的模型, 各自进行计算, 当进行两次或者几次移迭代计算, 得出的结果相等时, 迭代完成, 此时得出的力和位移就可以作为基坑支护结构稳定后的受力和变形, 因而位移迭代法比较全面客观的反映了结构与土体相互作用的动态过程, 因此, 在以后的基坑开挖和支护模拟的研究中应用的前景非常广阔。

参考文献

[1]李萍.基坑开挖与支护模拟的位移迭代法[J].岩土力学, 2005, (11) .124-127.

[2]邓小鹏.深基坑开挖与支护有限元数值分析[D].长安大学, 2004.25-27

[3]张云.深基坑工程开挖与支护的ANSYS有限元模拟[D].中国海洋大学, 2008.11-12

[4]聂淼.深基坑开挖过程数值模拟及支护对策[D].贵州大学, 2009.23-24

[5]张峰.深基坑板桩支护模型试验研究[D].武汉科技大学, 2007.25-25

【循环迭代法】推荐阅读：

黄金分割迭代法10-03

迭代程序10-20

迭代函数06-08

迭代方法07-10

迭代增强08-16