《信号与系统》-2006_2

第二章 方程(组)的迭代解法,2,2017/12/25,1 引言,f(x) = 0代数多项式:f(x)=a0xn+a1xn-1+an-1x+ an (a00)超越函数：如三角函数,指数函数的复合函数等方程的根满足方程 f(x)=0的x值通常叫做方程的根或解，也叫函数f (x)的零点。单根和重根如果f(x)=(x-)mg(x)且g()0，则称为f(x)=0的m重根。m=1称为单根，m1称为重根。,3,2017/12/25,1 引言,1535年意大利数学家坦特格里亚(TorTaglia)发现了三次方程的解法,卡当(HCardano) 得到了这种解法，于1545年在其名著大法中公布了三次方程的公式解，称为卡当算法卡当的学生弗瑞里(Ferrari)又提出了四次方程的解法1824年阿贝尔发表了“五次方程代数解法不可能存在”的论文，但并未受到重视1828年17岁的法国数学家伽罗华写出了划时代的论文“关于五次方程的代数解法问题”，指出即使在公式中容许用n次方根，并用类似算法求五次或更高次代数方程的根是不可能的。决斗前，他把关于五次代数求解的研究成果写成长信，留了下来十四年后，法国数学家刘维尔(JLiouville)整理并发表了伽罗华的遗作38年后，法国数学家若当(CJordan)在专著论置换与代数方程中阐发了伽罗华的思想，一门现代数学的分支群论诞生了。,4,2017/12/25,1 引言,1.2 本章重点介绍求方程实根的迭代解法适用于求解代数方程和超越方程仅限于求方程的实根该方法基本思想：,5,2017/12/25,2 迭代解法,6,2017/12/25,2.1 根的初值确定方法,圈定根所界的范围，称为圈定根或根的隔离代数方程:根的个数与其最高次数相同,有成熟的圈定根的方法 超越方程:可能有一个,几个根或者无解,无固定的圈定根的方法求方程根的问题，就几何上讲,是求曲线y=f (x)与x轴交点的横坐标。,7,2017/12/25,2.1 根的初值确定方法,定理2.1设f (x)为区间a,b上的单值连续函数，如果f (a)f (b)0，取a =r；否则取b=r.3) 若b - a ，转向1)；否则结束,a,b,(a+b)/2,14,2017/12/25,2.1.3 对分法,其几何意义如图:,15,2017/12/25,2.1.3 对分法,误差分析,第 n 步产生的 xk 有误差,计算简单; 对f (x) 要求不高(只要连续即可) .,无法求复根及偶重根 收敛慢,16,2017/12/25,2.2 迭代法求解过程,2.2.1 建立迭代公式。,例如：f(x) = x3+2x2-4 = 0 可以分解为x = x+f(x) = x3+2x2+x-4;x = 2(1/(2+x)1/2x = x-(x3+2x2-4)/(3x2-4x),迭代函数,17,2017/12/25,2.2 迭代法求解过程,2.2.2 进行迭代计算。x1= (x0)x2= (x1)xn+1= (xn) （n=0,1,2,）称为迭代公式x0 , x1 , x2 ,称为迭代序列序列的计算过程称为迭代过程,如果序列x0 , x1 , x2 , 收敛于,即,18,2017/12/25,2.3 迭代解法的几何意义,把求根问题转化为求y(x)=x, y(x)=(x) 的交点，交点的横坐标即为方程的根。,x2,x1,x0,A0 x0,(x0),A0,A1,A1,A,19,2017/12/25,2.2 迭代法求解过程,例2.3用迭代法求方程 f(x)=x3- x -1=0 在x0=1.5附近的根 解：将方程改写为 x=(1+x)1/3按上式建立迭代公式 xn+1=(1+xn)1/3取x0=1.5逐次迭代得x0=1.5,x1=1.35721, x2=1.33086, x3=1.32588, x4=1.32494, x5=1.32476, x6=1.32473, x7=1.32472, x8=1.32472 x=1.32472,20,2017/12/25,2.2 迭代法求解过程,例2.3用迭代法求方程 f(x)=x3- x -1=0 在x0=1.5附近的根将方程改写为 x=x3-1，建立迭代公式 xn+1=xn3-1， x0=1.5, x1=2.375, x2=12.39,迭代法失效。迭代序列有极限存在的迭代过程称为收敛的迭代过程；否则就是发散的。,21,2017/12/25,2.3 迭代解法的几何意义,22,2017/12/25,2.4 迭代法的收敛性,影响迭代法收敛性的要素迭代函数在根近旁的性态初值的选取范围迭代法收敛的类型大范围收敛: 从任何可取初值出发都能保证收敛局部收敛: 为了保证收敛性必须选取初值充分接近于所要求的根。局部收敛方法比大范围收敛方法收敛得快合理的求根算法先用一种大范围收敛方法求得接近于根的近似值(如对分法),再以其作为新的初值使用局部收敛法(如迭代法),23,2017/12/25,2.4 迭代法的收敛性,定理2.2 设 (x)在包含根的区间a,b上可微，且满足条件,则对任何,迭代过程xn+1= (xn)（n=0,1,2,）,一定收敛。,证明：设 (x)在包含根的区间内具有连续的一阶导数。,24,2017/12/25,2.4 迭代法的收敛性,设 (x)在包含根的区间内具有连续的一阶导数。,.,必有,若有,25,2017/12/25,2.4 迭代法的收敛性,定理2.2 设 (x)在包含根的区间a,b上可微，且满足条件,则对任何,迭代过程xn+1= (xn)（n=0,1,2,）,一定收敛。,注意：该定理的条件是充分条件q值等于新旧迭代值之误差比,即对旧误差的缩小率.q愈小,新近似值逼近就愈快在实际应用时,因(x)连续且a,b较小, (x)的值变化不大,可用| (x0)|1超线性收敛r=2平方收敛,新近似值的误差与旧近似值误差的r次方成正比,29,2017/12/25,2.4 迭代法的收敛性,定理2.4 设迭代函数(x)在临近有r阶连续导数，且满足 (x)= (x)= (r-1)(x)=0， 及(r)(x)0，则该迭代序列是r阶收敛的。证明： xn+1= (xn),= (+(xn- ),该定理提供了测定收敛阶的方法!,30,2017/12/25,2.5 迭代序列的误差估计,1.迭代终止条件|xn+1-|, xn+1即为所求得的近似值2.引申迭代终止条件(上界公式)上界公式 亦称为迭代终止的判断条件,31,2017/12/25,2.5 迭代序列的误差估计,32,2017/12/25,2.5 迭代序列的误差估计,按相对误差限来控制,33,2017/12/25,2.5 迭代序列的误差估计,假收敛的情况,34,2017/12/25,2.5 迭代序列的误差估计,证明：由（1）中公式知,35,2017/12/25,2.5 迭代序列的误差估计,预估迭代次数,两边取对数可得:,36,2017/12/25,2.5 迭代序列的误差估计,则当|f(xn)|m 时，就有|xn+1-| 成立,37,2017/12/25,2.5 迭代序列的误差估计,实际中常用|f(xn)| 作为迭代终止的判据这种判据合理吗？当|f(xn)|1时, |f(xn)| 与|f(xn)| m效果相同当|f(xn)|,38,2017/12/25,2.5 迭代序列的误差估计,当|f(xn)|1时,39,2017/12/25,2.5 迭代序列的误差估计,例2.4对下列方程 x-sinx=0.25,用迭代法、取三位小数计算其近似根，并估计其误差,解：方程化为x= sinx+0.25由作图法可粗略知0.9,1.5,因为(x)=sinx+0.25, (x)=cosx,当0.9x1.5时有 |(x)|cos0.90.62=q1,所以迭代过程收敛。取x0=1.2、xn+1=sinxn+0.25计算得x4如下：,40,2017/12/25,2.5 迭代序列的误差估计,x1=sin1.2+0.250=0.932+0.250=1.182x2=sin1.182+0.250=0.925+0.250=1.175x3=sin1.175+0.250=0.923+0.250=1.173x4=sin1.173+0.250=0.922+0.250=1.172x5=sin1.172+0.250= =1.172则有| x4- x3 |=0.001,按照上界公式(1)得 | x4- |0.62/(1-0.62)*0.001=0.0016计算x4的舍入误差小于2*(0.5*10-3)=0.001得近似根x4的总误差为=0.0016+0.001 0.5*10-2所以 =1.17,41,2017/12/25,注 意：,f(x)=0、x= (x) 参数模型= () 参数模型精确解xn+1= (xn) 计算模型方法误差可应用上界公式进行估计迭代控制中的精度要求要适当，否则可能造成迭代过程出现死循环的情况,42,2017/12/25,迭代法小结,迭代法的计算步骤归纳如下：(1)选取初值x0，确定方程f(x)=0的等价形式x=(x)(2)按公式xn+1=(xn)计算xn+1的值(3)判别.如果| xn+1-xn|则停止计算，否则继续迭代说明:(1)必须满足|(x)|q1;(2)一个方程f(x)=0变形为x=(x)有许多形式, q越小,收敛的越快。,43,2017/12/25,3 迭代公式的改进,44,2017/12/25,3 迭代公式的改进,方法(1) 提高初值的精度以减少迭代的次数。(2) 减小q的值。(3) 提高收敛的阶数r,45,2017/12/25,3.1 改变方程式法一,3.1.1 方法描述,x=(x),x- x =(x) - x,(1-)x=(x)- x,思路:,重新构造等效方程,46,2017/12/25,3.1.1 方法描述,例2.5 解x=e-x之根解：因 0.5,0.6，所以有,粗取=-0.6，建立如下迭代公式,仍取x0=0.5，逐次计算得 x1=0.56658 x2=0.56713 x3=0.56714,47,2017/12/25,3.1.2 埃特肯法,取以下平均变化率作为 = 1 :,将x0和 = 1代入,f(x)=0,x=(x),xn+1=(xn),x0,y1=(x0),z1= (y1),48,2017/12/25,3.1.2 埃特肯法,继续求取三个相邻迭代值,得到x1 , y2=(x1) , z2=(y2)，建立,以x1和2代入公式计算出,49,2017/12/25,3.1.2 埃特肯法,其一般公式可归纳为,其中,这个方法叫埃特肯加速收敛法,第一次校正值,第二次校正值,改正值,50,2017/12/25,3.1.2 埃特肯法,埃特肯法的几何意义,y1,x0,A (x0, y1),B (y1, z1),x1,可见埃特肯法就是用直线AB代替曲线AB求取交点的迭代方法,C,51,2017/12/25,3.1.2 埃特肯法,例 2.6 用埃特肯法解 x = e-x解：取x0=0.5,按照埃特肯法公式得x0= 0.5y1= e-0.5 = 0.60653, z1= e-0.60653 = 0.54524,y2= e-0.56762 = 0.56687,z2= e-0.56687 = 0.56730,y3= e-0.56714 = 0.56714,z3= e-0.56714 = 0.56714,52,2017/12/25,3.3 牛顿迭代法,3.3.1 方法描述,y=f(xn)+ f(xn)(x- xn)是y=f(xn)在点(xn , f(xn)的切线方程.与x轴交点为(xn+1, 0),代入切线方程xn+1=xn-f(xn)/ f (xn),f(x)=0,x= x- f(x), f(x)=0,(x),选择值，使|(x)|1|(x)|=|1- f(x) |,53,2017/12/25,3.3.1 方法描述,牛顿迭代法计算步骤：(1)选取初值x0(2)对于n=0,1,2,3计算f(xn)和f (xn)，以及,(3)判断如果| xn+1-xn | |f(x1)|单调下降的目的。 称|f(xn+1)| 1,61,2017/12/25,(3) 牛顿下山法,它是一次切线法中新、旧迭代值yn+1 、xn按 与(1- )的线性组合公式。,62,2017/12/25,(3) 牛顿下山法,例2.12 用牛顿下山法求 f(x) = x3-x-1=0 的根解：方程在0,1.5内有根，取x0=0.6，y1=17.9 用下山法调, y1=17.9, x0=0.6, f(x0)= 1.384,f(9.25) f(x0),f(2.7625) f(x0),f(1.1406)0,xn,xn+1,定理2.7 当f(x)在区间a,b上有直至二阶的连续导数，且满足有f(a) f(b)1的处理方法,x=(x)，分解后|(x)|K1, xa,b。将方程右端(x)中的x反解得到它的反函数x=(x).因为(x)=1/(x)，所以推得 (x)=1/(x)1/K1按照xn+1=(xn)进行迭代必收敛。,73,2017/12/25,4 联立方程组的 迭代解法,74,2017/12/25,4 联立方程组的迭代解法,对于联立方程组,75,2017/12/25,4 联立方程组的迭代解法,设x(0)=(x1(0), x2(0), xn(0)为根x*的零次近似,当n时， xi(k)有极限xi*存在，则xi* 为所求根。,76,2017/12/25,4 联立方程组的迭代解法,设R为含根x* =(x1*, x2*, xn* )的闭域，记,有以下收敛的充分条件及相应的误差估计公式：,77,2017/12/25,4 联立方程组的迭代解法,充分条件1,1,2,n,maxi1因为v 1，可能不收敛。,82,2017/12/25,4 联立方程组的迭代解法,方程组重新改写为,83,2017/12/25,4 联立方程组的迭代解法,计算结果为x*=3.487,y*=2.262。,则 v1=a11+a210.834v2=a12+a220.248 v=max(v1, v2) 0.8341符合充分条件2，按照下式一定收敛。,84,2017/12/25,5 联立方程组的 延拓解法,85,2017/12/25,5.1同伦方程组及其建立方法,建立同伦方程组H(X,t)=0，这里X=(x1, x2,xn)，t为引入的参数。同伦方程组是满足以下条件的联立方程组：（1）H(X(0),t)=0，X(0)=(x1(0), x2(0), ,xn(0)是任意取定的一组初值 即当t=0时,H(X,0)是具有已知解X(0)的联立方程组（2） H(X,1)= F(X)=0，即当t=1时,H(X,1)=0与原联立方程组F(X)相同。,86,2017/12/25,5.1同伦方程组及其建立方法,同伦方程组的构造方法,87,2017/12/25,5.2 求解方法,思想 ：（2） H(X,1)= F(X)=0从已知解X(0)逐步引渡到F(X)=0的未知解具体方法将t划分为 0t0 t1tN-1 tN=1，代入同伦方程组得 Hi=H(X, ti)=0 (i=1,2,N)取X(0)作为H1=0的初值，用某种迭代法求解出H1=0的解X(1)。再以X(1)作为H2=0的初值，求解出H2=0的解X(2)继续下去，直到求出HN=0的