第七章前半部分改完优秀课件.ppt

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