《前半部分改完》PPT课件

第七章非线性方程求根,1二分法（对分法）2迭代法的算法和理论3迭代加速收敛的方法4Newton迭代法5弦割法和抛物线法,一.研究数值解法的必要性1一般方程的根无法用解析表达式给出；2三次、四次方程的求根公式较繁。需要给出求根的近似值的方法。二.方程的根方程f(x)=0的解称为方程f(x)=0的根或称为f(x)的零点。若f(x)g(x)，其中m为正整数，g(x)满足，显然为f(x)的零点。这时，称为f(x)的m重零点，或称为f(x)=0的m重根。,定理若f(x)具有m阶连续导数,则是f(x)的m重零点之充要条件为：证明必要性设是f(x)的m重零点，则由,当时当k=m时,充分性设使得由Taylor公式得其中01，令则有且根据定义，为f(x)的m重零点,三.根的搜索求方程根的近似值之前，一般需要首先确定隔（有）根区间a,b（在a,b上方程仅有一个根）。方法：通过函数f(x)的增减性、凹凸性、变号特征等，并结合做草图来确定隔（有）根区间a,b。,1二分法（对分法）基本思想：通过区间逐次分半，将有根区间逐步缩小。设f(x)在a,b上连续，f(a)f(b)0，且在a,b内f(x)=0至少有一个实根。记a,b为,计算a1,b1中点的函数值若0，则若，则令若，则令新的有根区间,的长度,再计算,中点的函数值若0，则若，则令若，则令新的有根区间,的长度如此对分下去，则得到一系列有根区间且,由得k=1,2,3当对分过程无限继续下去，则有根区间必收缩为一点，即具体做法(1)给定每步检查是否成立，若成立，取，否则继续对分。(2)令，先确定对分次数k，再计算(3)误差估计为,优点对函数性质要求不高（只要函数连续）；计算简单，且可达到任意精度。缺点计算量大；不能求复根与偶重根。,2迭代法的算法和理论一不动点迭代法对给定的方程f(x)=0，将其变为等价的方程构造k=1,2称为迭代序列，(x)称为迭代函数。称为迭代格(公)式或迭代过程。当(x)连续时，若则有即故序列的极限为方程x=(x)(或f(x)=0)的根,若满足，称为(x)的不动点。即映射关系将映射到本身。因求f(x)的零点等价求的不动点。也称k=1,2为不动点迭代法（简单迭代法或逐次逼近法）。迭代序列的收敛性及收敛速度依赖于迭代函数的选取。,二不动点迭代法的一般理论定理（不动点定理）已知x=(x)，若且对，有;存在常数0L1,使对，有则(x)在a,b上有唯一的不动点；对任意k=0,1,2产生的序列必定收敛到(x)的不动点；有误差估,证明作辅助函数(x)=(x)-x由于(x)在a,b上连续，则(x)Ca,b，且(a)=(a)-a0(b)=(b)-b0故由连续函数的介值定理，至少存在使()=0。即从而(x)在a,b上存在不动点。又设(x)有两个不动点。注意且由微分中值定理得即故即(x)在a,b上有唯一的不动点。,注意且由微分中值定理其中介于与之间得k=1,2因01）在不动点的邻域里连续，则迭代格式为p阶收敛的充要条件是且有证明充分性当p1，若则由得即迭代格式为线性收敛。,对p1，由，知迭代格式满足在邻域具有局部收敛的条件，故迭代式收敛。由介于之间得故即为p阶收敛。,必要性设迭代格式为p阶收敛，则有即由于在邻域的连续性，知下面根据证明：（反证法）设有正整数，使将在展开，得即,显然当由得故这与迭代格式为p阶收敛盾。当由得故但迭代格式为p阶收敛，应有即与迭代格式为p阶收敛产生矛盾。所以,3迭代加速收敛的方法对于线性收敛的迭代格式，其收敛速度较慢（特别是），可以进行迭代加速。一.用两个迭代值进行组合由,得取和则迭代公式为或当有,Remark对因收敛，在领域内，故改造后的迭代有及若即这时，当L较大，加速收敛的效果明显。但当有可能这时迭代不能加速收敛。,对于线性迭代，有通常取，即则故当至少为二阶收敛。实际中，常取的近似值作为c。得加速迭代公式即缺点：需估计的近似值。,二用三个迭代值的进行组合设方程为的某个预测值为校正两次由于在与之间在与之间在邻域中，消去导数信息，即即因此可以得解下述Aitken方法。,Aitken加速收敛迭代格式给出校正再校正改进或记上式可写为：称为Steffensen迭代格式。特点：不需计算导数值；三个迭代值进行组合。,对于Steffensen迭代，有：定理设函数有不动点，且在邻域内具有二阶连续导数，若且则与有相同的不动点；Steffensen迭代为二阶收敛，且极限为证明设Steffensen迭代式为则,验证与有相同的不动点若则即反之，若注意则,即注意的连续性，知故与的根相同。即与有共同的不动点。,用定义证明Steffensen迭代为二阶收敛由有二阶连续导数，且为的不动点，可得关系式：故,由得（假设）即Steffensen迭代为二阶收敛,Remarks二阶收敛的证明也可以证明。上述定理的证明实际上用了迭代收敛的假设。严格的说，应该首先证明收敛性（如：在证明的基础上，证明）再证明二阶收敛。当线性收敛。当发散。但Steffensen迭代不仅能加速收敛，而且也能将发散的迭代改进为收敛的迭代