加速迭代格式的构造

加速迭代格式的构造任中贵，潘状元(哈尔滨理工大学应用科学学院，黑龙江哈尔滨150080)摘要构造了一类非精确加速迭代格式，证明了其收敛性，并且给出误差估计.实例表明，其收敛速度更快.关键词奇异问题；加速迭代；收敛性.中图分类号：0241.5 文献标识码：A 文章编号：THEACCELERATIONMETHODFORNEWTON’SMETHODATSINGULARPOINTSRENZhong-gui,PANZhuang-yuan(AppliedScienceCollege,HarbinUniv.Sci.Tech.,Harbin150080,China)Abstract::Theaccelerationmethodisdiscussed，theconvergenceisprovedandtheerrorestimationisgiven.Theexampleshowsthatitsconvergentrateisgood.Keywords:singularpoint；accelerationmethod；convergence.x=x-E-1F(x)'n=0,1,Ev+F(x1)veveRn，<,>表示普通的内积。它以一个近似雅可比矩阵为初值，每次迭代都对这个矩阵进行更新。初始雅可比近似％可取点x0处的精确雅可比矩阵，当然，为了避免导数计算，也可取为单位矩阵。算法如下：Broyden法算法x=初始值0E0=初始雅可比近似fork=0,1,2,---解Es=-f(x)求sxk+1=。+sk｛更新近似雅可比矩阵｝yk=f(xk+1)-f(xk)｛更新近似雅可比矩阵｝E=E+[(y—Es)sT]/(sTs)k+1 k k kkk kkend摘要：对于求解非线性方程组F(x)=0的Broyden秩1方法的计算格式提出一种修正算法，尝试利用矩阵的奇异值分解求解迭代方程组，并且配合使用加速技巧，从而大大提高了算法的安全性和收敛速度.数值算例表明了新算法的有效性.关键词：Broyden方法；加速技巧；奇异值分解Matlab符号对象在求解多维非线性方程组中的应用研究本课题主要研究求解非线性奇异问题的加速迭代格式构造问题。自著名的Newton--Kantorovich定理问世以来，以Newton法为代表的一类迭代法求解非线性方程的研究有了很大的发展并已取得了一系列丰硕成果，已成为非线性问题近似求解的最重要方法之一。但是作为一个专业科技工作者来说，不仅要善于从现有算法中选择相适应的方法，更重要的是如何根据实际问题的需要，改进和构造新的方法，拟补现有算法的不足。设F为Banach空间E到自身的C4映射，假定x*eE为方程F(x)=0的解。若FXx*)不可逆，我们称F(x)=0为奇异问题。一方面奇异非线性方程有许多实际背景。如反应扩散系统、捕食和猎物生物模型、分歧点、优化问题中鞍点计算等。所以研究此类问题具有重要实际意义。另一方面，许多数值方法都是针对非奇异问题讨论其收敛性、收敛速度、迭代格式的形态等，对于奇异问题讨论其解点附近的性态，对非线性问题的研究在理论上也是一种完善。1966年，L.B.Rall首次提出：一元实函数情况下，Newton法在奇异点处能达到平方收敛.1970年，Cavanagh假设F在x*处的某一个去心邻域非奇异，将Rall的结果推广到了一般空间E。然而，要保证奇异情况下的收敛条件十分严格，实际应用价值很低。1978年，GW.Reddien放宽了这个条件，提供了Newton法的可行性，Griewank和Osborne又进一步给出了几何解释。1983年,Decker和Suresh首先修改了Newton法，得到了相应的收敛性及超线性收敛率。为得到更好的收敛效果，Decker和Kelley也改善了Newton法，加速了零空间的收敛速度，使它达到和非奇异情况一样的平方收敛。为了得到更一般性的结果，1980年，Decker和Kelley将Reddien的结果推广到了零空间为有限维的情况。之后他们与Kelle^人进一步研究了在有限维零空间情况下的Newton方法的收敛性及误差估计，并且Decker、Keller及潘状元等人又修改了Newton方法，使它们无论在零空间还是值域空间都能达到平方收敛。显然，Newton法在求解非线性方程的过程中起到了非常重要的作用，但是人们仍然要研究如何构造一种新的迭代格式，以减少计算量获得较高收敛阶。1983年，Decker和Kelley研究了零空间为一维时的chord法，得出相应的收敛性及收敛速度为次线性收敛，1990年，杨忠华结合外推技巧构造了新的迭代格式，在计算量基本相同的情况下，收敛速率却比chord法快得多，但它仍是次线性收敛。潘状元又做了改进，加快了收敛速率，并将零空间为一维推广到有限维。在此基础上，我将根据各种迭代格式(如King-Werner方法、拟Newton方法、Moser方法等)，构造出求解奇异问题的新的迭代格式。三、课题主要研究内容主要有以下几方面研究内容：根据DeckerCT和SureshR给出的迭代格式：y=x一F'(x)-1F(x)n n n n气=F'(y.)-1F(y.)x1=y-(2-c|B卜)5构造求解奇异问题的新的迭代格式。由于这里c与a的最佳选取还不清楚，故可考虑x.+1=yn-(2-殂|Bn||))5皿的迭代格式。考虑中(t)应满足的条件。在非奇异情况下(F(x*)=0,有的Fr(x*)-1存在)，以Newton法为代表，已经形成了比较完善的理论体系。它的基本思想是将非线性方程逐步线性化来解。只要F(x)在点x*的邻域S(x*,5)内连续G一可微，那么Newton法是超线性收敛。如果F(x)在点x*处二阶F一可微，且F〃(x*)hh尹0,VxeRn,h尹0，那么Newton法达到2阶收敛，但是当空间维数n很大时，每步计算量太大，而且微商的逆也不易求。拟Newton法是针对这一缺点提出的算法，其核心是用通过计算函数值代替导数。在此基础上，针对奇异问题，修正拟Newton法，使新的方法在基本保持原有计算量的基础上，获得超线性收敛。King—Werner迭代是效率较高的方法,它每步的计算量与Newton迭代格式相同，组合代价也只比Newton迭代高一倍，而且具有收敛阶1+，。针对奇异问题，修正King-Werner方法。使新的迭代格式在基本保持原有计算量的基础上，获得高阶收敛。Moser法在求解非奇异问题时，不用求逆，故使得计算量较小。针对奇异问题，修正Moser方法，使新的迭代格式在基本保持原有计算量的基础上，获得高阶收敛。

黑龙江省高校骨干教师创新(1054G010)定义1.1[3]设h是Hilbert函数空间，其元素是某个抽象集合e上的实值或复值函数，内积用下式表示：7,g=；f(•),g(・)；，f,geH•若对任意固定的qeE，存在一个K(p,q)作为p的函数是H中的元素，而且对任意的feH及qeE有f(q)='•f(P),K(p,q)-P则称k(p,q)是Hilbert函数空间h的再生核，称h是再生核空间.定义1.2囹Hilbert函数空间f(t)(t>0)为具有有限范数『…―〕1—ffIf(z)l2e-tzdxdy|<8兀IC J的所有整函数f(z)在该范数意义下构成的Hilbert函数空间，且cxC上的二元函数e»〃为该空间的再生核.即对空间中的任意一个元f(z)eF(t)及zeC,UeC有f(u)=<f(z),etzu>z这个空间称为Fock空间.引理1.1[5]对Vf,geL2(i),有ff(Twavf)(a,x)(Twwg)(a,x) =~ff(t)g(t)dt=~<f,g>•a2ai a考虑到a的对称性，有ff+xdadxff+xdadx(Twavf)(a,x)(Twavg)(a,x)a2Lf f(t)g(t)dt=—<f,g>•2a i 2a(5)作为式(5)的特例，对于feL(i)，有ff|(Twavfff|(Twavf)(a,x)些a2兀2af(x)2dx(6)上的所有复值函数尸的空间，Twav把L2(i)等距地映射到L2(+x;四a-2dadx)，即上的所有复值函数尸的空间，且研=四ff|F(a,b)2地收敛；当赋予范数|||」||，这是一个Hilbert空间.TwavL2(i)的兀 a2+x像仅构成一个闭子空间，不是整个空间L2(+x ;丛a-2dadx沮常

2Gauss小波变换像空间的再生核定理2.1对于e上的再生核Hilbert空间h和E上任意的非零的复值函数$(p),K$(p,q)=$(p)$(q)K(p,q)，p,qeE•是Hilbert空间hK的再生核，其中HK是由E上所有以如下形式表示的函数f(是Hilbert空间hKSf、P)=f(P)$(P)，feHk-且H具有内积sf$$,/Hk证明1)对于任意固定的qeE,K(p,q)作为p的函数，有K(p,q)eHr2)对于任意的feHk，任意的qeE有s■f(p),K(p,q).■hf(p)$(■f(p),K(p,q).■hf(p)$(p)$(p)$(q)K(p,q)$(p) $(p)Hkf(p),$(q)K(p,q).■■Hk由定义2.1可知k(p,q)为Hilbert函数空间hk的再生核.由于a的对称性，考虑a>0时，将式(4)推广为(Twavf)(A,z)=<f(t),V(t)>=Jf(t)A-2V(t―)dtA，z i AfeL2(i)•并记小波变换式(7)的像空间为H，其中A=a+bi,a>0,z=x+yi小波变换式(7)的像空间h的再生核为1rt-z)1rt-z‘)2VA2VIAJIA，JdtK(A,z；A',z，)=JA-1=A2A'2JV(Ao)v(A'<»)e-，3?-?')do.T—1" 一一如一,)一=A2A，2JAoe-aA2o2AOe-aA，o2e-,o*-z，do(8)其中，A'=a'+b'i,a'>0,z'=x'+y'i，a',b',x',y'ei•把式(8)作进一步计算，可得(z-席1-((z-席1-(2aM2+A'2v J(9)兀(AAr)2K(A,z；A，,z'I= 3T2aM2+A，22其中，arg小:其中，由上面再生核函数K(A,z；A，,z')的具体表达式，可知K(A,z；A，,z')作为(A,z)的函数在△(-)xC上是解析的，并且作为(A，,z，)的函数在△(-)xC上是反解析的•因此L2(R)中的小4 4波变换式(4)的像3wavf)(a,X)可以被解析延拓到空间△(-)xC上，形式为(7wavf)(A,z)，像4(Twavf)(A,z)是具有定理2.2中再生核K(A,z;A',z')的Hilbert函数空间h的元素.更进一步地，因为!A-:vf=];A€△(-),zwCI在L2(i)中是完备的，所以有等距恒等式[VaJ4J||(T”a’f)(A,z)||2=IlfI上)•结合式(6)，进一步可得到恒等式||(Twavf)(A,z)||2=^"jj (Twavf)(a,x)2dadx• (10)兀七 a2参考文献：唐远炎，王铃.小波分析与文本文字识别[M].科学出版社，2002.彭玉华.小波变换与工程应用[M].科学出版社,2000.AronszajnN.,TheoryofReproducingKernels[J],Transa