7.6-压缩映射原理及应用

第1页•压缩映射及其不动点的概念第6节压缩映射原理及其应用•压缩映射原理应用举例—求映射的不动点•压缩映射原理第2页注：1）把“方程的求解”问题化归为“求映射的不动点”问题，并用逐次逼近（即迭代）法求不动点（既近似解）的方法是计算数学，分析和代数中常用的一种重要方法。例如，牛顿求代数方程根时采用的切线法。2）映射的不动点：使x=Tx的x称为T:XX的不动点.基本思想：代数方程微分方程积分方程x=Txx0,xn+1=TxnxTx~~第3页定义6.1(压缩映射)设X是距离空间，T：XX是X上的自映射，如果存在01，对x,yX，都有(Tx,Ty)(x,y)，则称T是X上的一个压缩映射。一、压缩映射及压缩映射原理1.压缩映射及其不动点的定义定义4.1(映射的不动点)设X距离空间，T：XX是X上的自映射，如果存在xX，使得x=Tx，则称x是映射T的一个不动点。定理1压缩映射是连续映射事实上，{xn}X,xnxX,T:XX是压缩映射(Txn,Tx)(xn,x)0(n)T是连续映射第4页2.压缩映射原理(Banach不动点原理，波兰，1922)定理4.1(压缩映射原理)设X是完备的距离空间，映射T：XX是压缩映射，则T在X中存在唯一的不动点x,即x=Tx。证存在性设X完备，T:XX是压缩映射，①任取初始点x0X，构造迭代序列{xn}X：xn+1=Txn(n=0,1,2,…)②证明{xn}是基本列,因而是收敛列。T是压缩映射,01,使得(xn+1,xn)=(Txn,Txn-1)(xn,xn-1)2(xn-1,xn-2)…n(x1,x0)=n(Tx0,x0)(n=1,2,…)(xn+k,xn)(xn+k,xn+k-1)+(xn+k-1,xn+k-2)+…+(xn+1,xn)(n+k-1+n+k-2+…+n)(Tx0,x0)(kN)第5页②证明极限点x就是T的不动点。T是压缩映射T是连续映射xn+1=Txn,xnx,T连续x=Tx(n)x是T的不动点唯一性设x,y都是T的不动点x=Tx,y=Ty(x,y)=(Tx,Ty)(x,y)(x,y)=0(01)),(1),(1)1(),(0000xTxxTxxxnknnkn(xn+k,xn)0(n)(01){xn}是基本列{xn}收敛(X完备)xX,使xnx(n)第6页注1)压缩映射原理给出了映射的不动点存在的条件；2)压缩映射原理提供了映射不动点的求法—迭代法:x0X,令xn=Txn-1,则xn=Tnx0(n=1,2,…),x=limxn(n).3)压缩映射原理给出了近似解的误差估计公式：),(1),(lim),(00xTxxxxxnnknkn事实上，由定理证明过程知),(1),(1)1(),(,0000xTxxTxxxknknnkn令k,有极限保号性记即得证第7页推论4.1设X是完备的距离空间，T：XX.如果T在闭球S(x0,r)上是压缩映射，并且(Tx0,x0)(1)r(01)则T在闭球S(x0,r)中存在唯一的不动点。分析只要在闭球内构造一个迭代序列{xn}即可。证取初始点x0S(x0,r)，作迭代xn=Tnx0(n=0,1,2,…)T是S(x0,r)上的压缩映射,且(Tx0,x0)(1)r(01)(x1,x0)=(Tx0,x0)(1-)rr(x2,x0)=(Tx1,x0)(Tx1,Tx0)+(Tx0,x0)(x1,x0)+(1-)r+r(1-)r=r(xn,x0)r(n=1,2,…)(数学归纳法)xnS(x0,r)(n=1,2,…)唯一xS(x0,r)，使得x=Tx.（在S(x0,r)上应用定理4.1)第8页推论4.2设X是完备距离空间，T：XX，如果存在常数(01)及正整数n0，使对任何x,yX，都有则T存在唯一不动点x，即x=Tx.(其中定义：T2x=T(Tx),T3x=T(T2x),…,Tnx=T(Tn-1x),…)),(),(00yxTxTnn证),(),(),1,0[,,,000yxyTxTNnXyxnn0nT是X上的压缩映射xxTXxn0,使唯一TxxTTxTTxTnnn)()(0001x与Tx都是的不动点x=Tx（不动点的唯一性）0nT第9页应用压缩映射原理及其推论解决实际问题的步骤：1)说明X是完备距离空间；2)有实际问题定义映射T:XX，使x=Tx；3)证明所定义映射T是X上的压缩映射；3)有压缩映射原理说明不动点的存在唯一性。3.压缩映射原理应用例4.1设f(x)在R可导,且f’(x)1,则f(x)在R上有唯一的不动点x,且x可由迭代xn+1=Txn(n=1,2,…)(x0R)迭代求得.证R是完备距离空间，函数f(x)是R到R的一个映射，x1,x2R,由拉格朗日中值定理,有(f(x1),f(x2))=f(x1)-f(x2)=f’()x1-x2(x1,x2)f:RR是压缩映射f(x)在R上有唯一的不动点x，对于迭代xn+1=Txn，有nnxxlim第10页例4.2设f(x)在闭区间[x0-h,x0+h]上可导,且f’(x)1,又f(x0)-x0(1-)h,则f(x)在[x0-h,x0+h]上有唯一的不动点x,且x可由迭代xn+1=Txn(n=1,2,…)(x0[x0-h,x0+h])迭代求得.证（结合推论4.1及例4.1即得证。）R是完备距离空间，函数f(x)是R到R的一个映射，x1,x2[x0-h,x0+h],由拉格朗日中值定理,有(f(x1),f(x2))=f(x1)-f(x2)=f’()x1-x2(x1,x2)f:RR是压缩映射又(f(x0),x0)=f(x0)-x0(1-)hf(x)在[x0-h,x0+h]上有唯一的不动点x(推论4.2)，且对于迭代xn+1=Txn，有nnxxlim第11页例4.3设f(x,y)在R2上连续,且关于y满足Lipschitz条件：f(x,y1)-f(x,y2)ky1-y2(k0),则微分方程初值问题：00),,(yyyxfdxdyx有唯一解。证R2完备,且y(x)在R上连续,0,使=k1,令C[x0-,x0+]={y=y(x)x[x0-,x0+],y(x)连续}，则C[x0-,x0+]按如下距离(y1,y2)是完备的距离空间：xxxdttytfyxyyyyxfdxdy00)(,()(),,(00xxdttytfyxyTxxCxyy0)(,())((],,[)(000令)()(max),(21],[2100xyxyyyxxx第12页)1(),(),()()(max)()(max))(,())(,(max))](,())(,([max,max),(],,[)(),(2121021],[21],[21],[21],[21],[210022110000000000000kyyyykxxtytykdttytykdttytftytfdttytftytfTyTyTyTyxxCxyyxyyxxxxxxxxxxxxxxxxxxxxxT是压缩映射唯一y(x)C(x0-,x0+),使,)(,))(,())(()(),(lim)(0000xxnnyxydttytfyxTyxyxyxy第13页例4.3设有线性方程组如果对每个i,),...2,1(,1nibxaxinjjiji则该方程组有唯一解。,11njija证Rn按距离是完备的距离空间.iiniyxyy121max),(TxbAxxnibxaxnibxaxinjjijiinjjiji),...2,1(,),...2,1(,11则T是Rn到Rn的映射,可以证明，T是压缩映射，因而存在唯一不动点x,使得x=Tx=Ax+b,即原方程组有唯一解。事实上，x(k)=(x1(k),x2(k),…,xn(k))Rn,k=1,2.第14页)(maxmaxmax)(max)()(maxmax),(),(1,,...,2,1)2()1()2()1(1111)2()1(11)2()1(111)2()1(1)2()1(1)2()1()2()1(1xxxxaxxaxxabxabxayyyyTxTxanijjnjnjijninjjjijninjjjijninjnjijijijijniiininjijT:RnRn是压缩映射。第15页nxxxx21321yyyynjnbjxnjanjbjxjanjbjxjaTx1122111TxbAxx211max)2,1()2,1(iyiyniyyTxTx由于njibjxijanjibjxijani12111maxnjjxjxijani1211max2111maxjxjxnjijani第16页由于对每个11,njijai故111maxnjijani2,1TxTx2,1211maxxxjxjxnj从而从而T是压缩映射。由压缩映射原理，知T在nR中有唯一的不动点nxxxx......2,1使.11~,,2~2,11~1~~njnjnbjxnjabjxjabnjjxjaxTx0lim~xnTnx即原代数方程有唯一解且可用选代法求得：第17页第18页第19页第20页第21页