《数值分析复习---第七章 非线性方程(组)的数值解法》由会员分享，可在线阅读，更多相关《数值分析复习---第七章 非线性方程(组)的数值解法（38页珍藏版）》请在金锄头文库上搜索。
1、数值分析数值分析 Numerical Analysis 郑州大学研究生课程 2009 2010学年第一学期 郑州大学研究生课程 2009 2010学年第一学期 习题课习题课 第七章非线性方程 组 的数值解法第七章非线性方程 组 的数值解法 2 38郑州大学研究生2009 2010学年课程数值分析Numerical Analysis 二分法求根过程二分法求根过程 取有根区间 取有根区间 a b 之中点之中点 将它分为两半将它分为两半 分点分点 这样就可缩小有根区间这样就可缩小有根区间 2 0 ba x y y f x y f x x a x1 x x0 b a x0 x1 b a1 b1 a1
2、b1 a2 b2 a2 b2 一 要点回顾 3 38郑州大学研究生2009 2010学年课程数值分析Numerical Analysis 7 2 二分区间法 对压缩了的有根区间施行同样的手法 即取中点 将区间再分为两半 然 后再确定有根区间 其长度是的 二分之一 对压缩了的有根区间施行同样的手法 即取中点 将区间再分为两半 然 后再确定有根区间 其长度是的 二分之一 11 ba 2 11 1 ba x 11 ba 22 b a 11 ba y y f x y f x x a x1 x x0 b a x0 x1 b a1 b1 a1 b1 a2 b2 a2 b2 4 38郑州大学研究生2009
3、2010学年课程数值分析Numerical Analysis 7 2 二分区间法 如此反复下去 若不出现 即可得出一 系列有根区间序列 上述每个区间都是前一个区间的一半 因此 的长度 如此反复下去 若不出现 即可得出一 系列有根区间序列 上述每个区间都是前一个区间的一半 因此 的长度 0 k xf kk babababa 2211 2 1 2 1 11 ababab k kkkk 当当k 时趋于零 这些区间最终收敛于一点x 时趋于零 这些区间最终收敛于一点x 即为 所求的根 即为 所求的根 5 38郑州大学研究生2009 2010学年课程数值分析Numerical Analysis 7 2 二
4、分区间法 每次二分后 取有根区间的中点 作为根的近似值 得到一个近似根的序列 该序列以根x 每次二分后 取有根区间的中点 作为根的近似值 得到一个近似根的序列 该序列以根x 为极限 只要二分足够多次 即 为极限 只要二分足够多次 即k足够大 便有 这里 为给定精度 由于 则 足够大 便有 这里 为给定精度 由于 则 kk ba 2 1 kkk bax 210k xxxx k xx kk bax 6 38郑州大学研究生2009 2010学年课程数值分析Numerical Analysis 7 2 二分区间法 1 11 22 k kk kk ab ab ab 1 22 k kk k abab xx
5、 7 38郑州大学研究生2009 2010学年课程数值分析Numerical Analysis 7 2 二分区间法 当给定精度 0后 要想成立 只要 取 当给定精度 0后 要想成立 只要 取k满足即可 亦即当满足即可 亦即当 k xx x f 给定误差限 给定误差限 0 5 10 3 使用二分法时 使用二分法时 52 3 xxxf 016 3 01 2 ff 9 38郑州大学研究生2009 2010学年课程数值分析Numerical Analysis 7 2 二分区间法 误差限为只要取误差限为只要取k满足满足 2 1 1 abxx k k 3 1 10 2 1 2 1 ab k 即可 亦即即可
6、 亦即 3 102 k97 9 21 10lg3 g k 所以需二分10次便可达到要求 所以需二分10次便可达到要求 10 38郑州大学研究生2009 2010学年课程数值分析Numerical Analysis 7 3 迭代法及其加速 为求解非线性方程f x 0的根 先将其写成便于迭代 的 为求解非线性方程f x 0的根 先将其写成便于迭代 的等价方程等价方程 其中为x的连续函数其中为x的连续函数 x xx 迭代法的基本思想迭代法的基本思想 如果数使如果数使f x 0 则也有则也有 反之反之 若若 则也有则也有 称为称为迭代函数迭代函数 而 称 而 称x 为的为的不动点不动点 x xx xx
7、 0 xf x x 11 38郑州大学研究生2009 2010学年课程数值分析Numerical Analysis 7 3 迭代法及其加速 任取一个初值任取一个初值 代入式的右端代入式的右端 得 到 得 到 0 x xx 01 xx 再将代入式的右端再将代入式的右端 得到得到 依此类推依此类推 得到一个数列得到一个数列 其一般表示 其一般表示 1 x xx 12 xx 23 xx 2 1 0 1 kxx kk 称为求解非线性方程的称为求解非线性方程的简单迭代法简单迭代法 12 38郑州大学研究生2009 2010学年课程数值分析Numerical Analysis 7 3 迭代法及其加速 如果
8、由迭代格式产生的序列收敛 即 如果由迭代格式产生的序列收敛 即 n x 1kk xx limxx n n 则称则称迭代法收敛迭代法收敛 13 38郑州大学研究生2009 2010学年课程数值分析Numerical Analysis 定理定理7 3 1 设函数在设函数在 a b 上有连续的一阶导 数 上有连续的一阶导 数 且满足 且满足 1 对所有的 对所有的x a b 有 有 a b 2 存在 存在 0 L 1 使所有的使所有的x a b 有 有 L 则方程在则方程在 a b 上的解上的解存在且唯一存在且唯一 对 任意的初值 对 任意的初值 a b 迭代过程 均收敛于 并有误差估计式 迭代过程
9、 均收敛于 并有误差估计式 x x x xx x 0 x 1kk xx x 1 1 kkk xx L L xx 01 1 xx L L xx k k 14 38郑州大学研究生2009 2010学年课程数值分析Numerical Analysis 由连续函数介值定理知由连续函数介值定理知 必有必有 a b 使 所以有解存在 使 所以有解存在 即 假设有两个解和 即 假设有两个解和 a b 则 由微分中值定理有 其中 是介于 则 由微分中值定理有 其中 是介于x 和之间的点 从而有 和之间的点 从而有 a b 进 而有由条件 进 而有由条件 2 有有 1 所 以 所 以 0 即 即 解唯一 证 解
10、唯一 证 构造函数构造函数 由条件 对任意的由条件 对任意的x a b a b 有有 xxx 0 0 bbb aaa x x 0 xxx xx xx xx xx xxxxxx x 0 1 xx x xx x x 15 38郑州大学研究生2009 2010学年课程数值分析Numerical Analysis 按迭代过程按迭代过程 有有 1 kk xx 1 1 kkk xxxxxx 1 1 kkk xxLxxxx 0 2 2 1 xxLxxLxxLxx k kkk 由于L 1 所以有 可见L越小 收敛越快由于L xxf 18 38郑州大学研究生2009 2010学年课程数值分析Numerical
11、Analysis 7 3 迭代法及其加速 即 不满足收敛条件 即 此时迭代公式满足迭代收敛条件 即 不满足收敛条件 即 此时迭代公式满足迭代收敛条件 4 2 5 x x 2 11 4 5 4 2 45 x x x x x 5 24 xx 24 5 xx 2 112 0 24 5 1 24 5 1 5 4 5 4 x x x 19 38郑州大学研究生2009 2010学年课程数值分析Numerical Analysis 7 3 迭代法及其加速 迭代法的局部收敛性迭代法的局部收敛性 定理7 3 2定理7 3 2 设在的根的邻域中有连 续的一阶导数 且则迭代过程 具有局部收敛性 设在的根的邻域中有连
12、 续的一阶导数 且则迭代过程 具有局部收敛性 x xx x 1 x 1kk xx 定义 局部收敛性 定义 局部收敛性 如果存在x如果存在x 的某个邻域 当初 值x 的某个邻域 当初 值x0 0属于此邻域时 迭代过程收敛 则称此迭代过程具有局部收敛性 属于此邻域时 迭代过程收敛 则称此迭代过程具有局部收敛性 1kk xx 20 38郑州大学研究生2009 2010学年课程数值分析Numerical Analysis 7 3 迭代法及其加速 证明证明 由于 存在充分小邻域 由于 存在充分小邻域 使成立 这里L为某个定数 根据微分中值定理 由于 又当 时 故有 由 使成立 这里L为某个定数 根据微分
13、中值定理 由于 又当 时 故有 由定理7 3 1定理7 3 1知对于任意的都收 敛 知对于任意的都收 敛 1 x xx 1 Lx xxxx xx x xxxxLxx 1kk xx 0 x 21 38郑州大学研究生2009 2010学年课程数值分析Numerical Analysis 例例7 3 3 设设 要使迭代过程 局部收敛到 求的取值范围 要使迭代过程 局部收敛到 求的取值范围 解解 由在根邻域具有局部收敛性时 由在根邻域具有局部收敛性时 收敛 条件 收敛 条件 5 2 xxx 1kk xx 5 x 5 2 xxx xx 21 1521 ax 15211 a 0522 a 所以所以 0 5
14、 1 a 5 x 22 38郑州大学研究生2009 2010学年课程数值分析Numerical Analysis 例7 3 4例7 3 4 已知方程在内有根 且在 上满足 利用构造一个迭代函数 使局部收敛于 已知方程在内有根 且在 上满足 利用构造一个迭代函数 使局部收敛于 解解 由可得 由可得 xx ba x ba 13 x x xg 2 1 0 1 kxgx kk x xx xxxx3 3 3 2 1 xgxxx 1 2 1 3 2 1 3 2 1 xxxg bax 故故 迭代公式迭代公式 1 0 使 设迭代过程收敛于的 根 记迭代误差 若存在常数p p 1 和c c 0 使 1kk xx
15、 xx x kk xxe 迭代法的收敛速度迭代法的收敛速度 c e e p k k k 1 lim 则称序列是则称序列是 p 阶收敛阶收敛的 的 c称称渐近误差常数渐近误差常数 特别地 特别地 p 1时称为 1时称为线性收敛线性收敛 p 2时称为 2时称为平方收 敛 平方收 敛 1 1 p 2时称为 2时称为超线性收敛超线性收敛 k x 24 38郑州大学研究生2009 2010学年课程数值分析Numerical Analysis 定理定理7 3 3 设迭代过程设迭代过程 若在所求根 的邻域连续且 则迭代过程在邻域是 若在所求根 的邻域连续且 则迭代过程在邻域是p阶收敛阶收敛的 的 证证 由于
16、即在邻域由于即在邻域 所以 有局部收敛性 所以 有局部收敛性 将在处泰勒展开将在处泰勒展开 1kk xx x p x 0 0 1 xxxx pp x 0 x x 1 x 1kk xx k x x p k p kkk xx p xxxxxxxx 1 2 1 2 根据已知条件得根据已知条件得 p k p k xx p xx 1 由迭代公式由迭代公式 1kk xx 及及 xx 有有 p k p k xx p xx 1 0 lim 1 p x e e p p k k k 25 38郑州大学研究生2009 2010学年课程数值分析Numerical Analysis 7 3 迭代法及其加速 例例7 3 5 已知迭代公式收敛于 证明该迭代公式平方收敛 证 已知迭代公式收敛于 证明该迭代公式平方收敛 证 迭代公式相应的迭代函数为迭代公式相应的迭代函数为 2 1 1 3 2 k kk x xx 3 3 x 2 1 3 2 x xx 43 6 2 3 2 x x x x 根据根据定理定理7 3 3可知 迭代公式平方收敛 可知 迭代公式平方收敛 3 3 x0 3 2 33 6 0 33 xx 26 38郑
