迭代初值及公式对迭代收敛速度影响

本本科科生生 课课程程设设计计 报报告告 实实习习 课课程程数值分析 学学院院名名称称管理科学学院 专专业业名名称称 学学生生姓姓名名 学学生生学学号号 指指导导教教师师 实实验验地地点点 实实验验成成绩绩 二二 一一 六六 年年 六六 月月 填 写 说 明 1 专业名称填写为专业全称 有专业方向的用小括号标明 2 格式要求 格式要求 用 A4 纸双面打印 封面双面打印 或在 A4 大小纸上用蓝黑色水笔书写 打印排版 正文用宋体小四号 1 5 倍行距 页边距采取默认形式 上 下 2 54cm 左右 2 54cm 页眉 1 5cm 页脚 1 75cm 字符间距为默认 值 缩放 100 间距 标准 页码用小五号字底端居中 具体要求 题目题目 二号黑体居中 摘要摘要 摘要 二字用小二号黑体居中 隔行书写摘要的文字部分 小 4 号宋体 关键词关键词 隔行顶格书写 关键词 三字 提炼 3 5 个关键词 用分号隔 开 小 4 号黑体 正文部分采用三级标题 第第 1 1 章章 小二号黑体居中 段前 0 5 行 1 11 1 小三号黑体 段前 段后 0 5 行 1 1 11 1 1 小四号黑体 段前 段后 0 5 行 参考文献参考文献 黑体小二号居中 段前 0 5 行 参考文献用五号宋体 参照 参考文献著录规则 GB T 7714 2005 迭代初值及公式对迭代收敛速度影响 摘 要 迭代收敛速度受到迭代函数和初始迭代值的影响 本实验在于体会在非线性方程求根的迭代法中 迭代函数和初始迭代值的 选取对迭代收敛性的影响 sttefensen 加速的效果 并试图总结一些规律 关键词 sttenfensen 加速 迭代初值 收敛速度 1 目录目录 第 1 章 前 言 1 1 1 内容及要求 1 1 2 研究思路及结构安排 1 第 2 章 相关理论知识 2 2 1 迭代法 2 2 2 迭代收敛 2 第 3 章 算法分析 3 3 1 单一迭代算法步骤及流程图 3 第 4 章 算法实现 4 4 1 程序总体结构 4 4 2 源程序清单 5 4 3 程序运行 11 第 5 章 结果分析 14 参考文献 14 1 第 1 章 前 言 1 1 内容及要求 体会在非线性方程求根的迭代法中 迭代函数和初始迭代值的选取对迭代收敛性的影响 考虑一个简单的代数方程 针对这个方程 可以构造多种迭代法 如下列 32 4100 xx 几种迭代格式 32 1 410 nnnn xxxx 1 3 2 1 1 10 2 nn xx 1 2 1 10 4 n x x 32 1 2 410 38 nn nn nn xx xx xx 要求 1 取定某个初始值 x0 按如上四种迭代格式进行计算 它们的收敛性如何 重复选取不同 的初始值 反复实验 分析四种迭代法的收敛性与初值选取的关系 2 选取第 种迭代格式 Newton 迭代法 取不同的初始值进行迭代 结果如何 并分析 迭代法对不同的初值是否有差异 3 对上述四种迭代格式 编制 Steffensen 迭代程序 选取不同的初始值 输出迭代次数和 方程的根 并与 1 2 中的结果进行比较 1 2 研究思路及结构安排 按照题目要求分别编写公式 1 4 以及他们的 steffensen 加速公式 在每一次的计算中 通过输入不同的迭代初值 然后进行 8 个公式的的计算 最后得到每个 公式在此迭代初值条件下的表现 得到满足精度要求的近似解的迭代次数 并且 程序运行过程中通过文件读写将每一次的每个公式的迭代次数都写入到 data txt 中 对 比一目了然 通过对迭代次数的对比分析可以得到较为清晰的结论 2 第 2 章 相关理论知识 2 1 迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法 设方程为 f x 0 用某种数 学方法导出等价的形式 x g x 然后按以下步骤执行 1 选一个方程的近似根 赋给变量 x0 2 将 x0 的值保存于变量 x1 然后计算 g x1 并将结果存于变量 x0 3 当 x0 与 x1 的差的绝对值还小于指定的精度要求时 重复步骤 2 的计算 若方程有根 并且用上述方法计算出来的近似根序列收敛 则按上述方法求得的 x0 就认为是方程 的根 2 2 迭代收敛 具体使用迭代法求根时应注意以下两种可能发生的情况 1 如果方程无解 算法求出的近似根序列就不会收敛 迭代过程会变成死循环 因此在使用 迭代算法前应先考察方程是否有解 并在程序中对迭代的次数给予限制 2 方程虽然有解 但迭代公式选择不当 或迭代的初始近似根选择不合理 也会导致迭代失 败 3 第 3 章 算法分析 3 1 单一迭代算法步骤及流程图 x2 x0 x1 0 b 0 fabs x1 x2 N 是 b x1 x2 x2 pow x1 3 4 pow x1 2 x1 10 开始结束 4 第 4 章 算法实现 4 1 程序总体结构 开始 int a 0 b 0 double x0 0 x1 0 x2 0 x3 0 x4 0 scanf d a 2 scanf lf 否 printf 计算完毕 n 结束 x2 x0 x1 0 b 0 fabs x1 x2 N 是 b x1 x2 x2 pow x1 3 4 pow x1 2 x1 10 否 其他七个公式 的相似结构 5 4 2 源程序清单 include include define N 0 0001 void main int a 0 b 0 a 为选择项 b 为计数器 double x0 0 x1 0 x2 0 x3 0 x4 0 FILE fp fq fp fopen data txt w fq fopen strenge txt w fprintf fp 序号 初值式一式二式三式四式一 式二 式三 式四 n printf 此程序为验证不同的迭代函数和初值对迭代收敛速度的影响而设计 n printf 以方程 x 3 4x 2 10 0 为例 n printf 请选择 n1 输入初值进行计算2 退出 n scanf d if a 1 scanf d 6 int i 1 while a 2 printf 请输入迭代初值 n scanf lf fprintf fp d i fprintf fp 2f x0 printf 进行计算 n x2 x0 公式一迭代 x1 0 b 0 while fabs x1 x2 N b x1 x2 x2 pow x1 3 4 pow x1 2 x1 10 fprintf fp 2f b printf 经过迭代公式一 d 次迭代得到近似解 6 5f n b x2 x2 x0 公式二迭代 x1 0 b 0 while fabs x1 x2 N b 7 x1 x2 x2 0 5 pow 10 x1 x1 x1 0 5 fprintf fp d b printf 经过迭代公式二 d 次迭代得到近似解 6 3f n b x2 x1 x0 公式三迭代 x1 0 b 0 while fabs x1 x2 N b x1 x2 x2 pow 10 4 x1 0 5 fprintf fp d b printf 经过迭代公式三 d 次迭代得到近似解 6 3f n b x2 x2 x0 公式四迭代 x1 0 b 0 while fabs x1 x2 N b x1 x2 x2 x1 x1 x1 x1 4 x1 x1 10 3 x1 x1 8 x1 8 fprintf fp d b printf 经过迭代公式四 d 次迭代得到近似解 6 3f n b x2 x4 x0 公式一迭代 stffensen 加速 x1 0 b 0 while fabs x1 x4 N b x1 x4 x2 pow x1 3 4 pow x1 2 x1 10 x3 pow x2 3 4 pow x2 2 x2 10 x4 x1 pow x2 x1 2 x3 2 x2 x1 printf 经过迭代公式一 stffensen 加速 d 次迭代得到近似解 6 3f n b x4 fprintf fq d 3f n b x4 fprintf fp d b printf 经过迭代公式一 stffensen 加速 d 次迭代得到近似解 6 3f n b x4 x4 x0 公式二迭代 stffensen 加速 x1 0 b 0 while fabs x1 x4 N 9 b x1 x4 x2 0 5 pow 10 x1 x1 x1 0 5 x3 0 5 pow 10 x2 x2 x2 0 5 x4 x1 pow x2 x1 2 x3 2 x2 x1 fprintf fp d b printf 经过迭代公式二 stffensen 加速 d 次迭代得到近似解 6 3f n b x4 x4 x0 公式三迭代 stffensen 加速 x1 0 b 0 while fabs x1 x4 N b x1 x4 x2 pow 10 4 x1 0 5 x3 pow 10 4 x2 0 5 x4 x1 pow x2 x1 2 x3 2 x2 x1 fprintf fp d b printf 经过迭代公式三 stffensen 加速 d 次迭代得到近似解 6 3f n b x4 x4 x0 公式四迭代 stffensen 加速 x1 0 b 0 10 while fabs x1 x4 N b x1 x4 x2 x1 x1 x1 x1 4 x1 x1 10 3 x1 x1 8 x1 x3 x2 x2 x2 x2 4 x2 x2 10 3 x2 x2 8 x2 x4 x1 pow x2 x1 2 x3 2 x2 x1 fprintf fp d n b printf 经过迭代公式四 stffensen 加速 d 次迭代得到近似解 6 3f n b x4 printf 请选择 n1 再次输入初值进行计算2 退出 n scanf d if a 1 scanf d i fclose fp fclose fq printf 计算完毕 n 11 4 3 程序运行 图二 图三 12 图四 图五 13 图六 不同初值在 8 个公式中的结果 注 参数表示得到近似解时迭代次数 0 和 1 表示公式不收敛 图七 公式一的 steffensen 加速在取初值为 17 时的表现 注 迭代结果从 17 逐渐趋近到 1 538 后突变为 1 780 再突变到 27 819 最后稳定 14 第 5 章 结果分析 对图六进行分析可知 无论迭代初值取何值 公式一都为发散 公式二和公式三在迭代初值 取 1 和 2 时收敛 其他值均发散 公式四始终收敛 只是所需迭代次数随着迭代初值与真实值相 差越大而越大 说明公式一与迭代初值没有关系 公式二和公式三均只能在迭代初值与方程的解 1 365 非 常接近时才能收敛 当相差较大时则发散 公式四则只有迭代次数收到迭代初值的影响 所以 迭代法在不同的迭代初值下存在差异 对四个公式进行 steffensen 加速后 原本不收敛的公式一变得收敛 并且可以迭代得到方程的 近似解 只是迭代次数随迭代初值远离方程的解而发生跳跃式增长 迭代次数从初值为 1 时的 9 次到初值为 20 时的 49847 公式二在对迭代初值的敏感性上没有差异 而在原来的基础上可收敛 时收敛速度得到提升 公式三由原来的只对初值 1 和 2 收敛变为对所有的初值都收敛 并且都只 需要 3 次迭代 可谓收敛性能最好 稳定性最佳 公式四反而在加入加速公式后收敛速度变慢 计算中存在一个奇怪现象 公式一的 steffensen 加速在初值为 17 时 迭代结果从 17 逐渐递减 趋近到 1 538 后突变为 1 780 再突变到 27 819 最后稳定 这应该是一个偶然现象 这里不作特别研 究 综上 迭代初值对迭代的收敛性存在影响 但是这种影响存在不确定性 没有发现可寻的规律 Newton 迭代法对初值存在一定的相关性 第一段中已作说明 通过四种公式与其 steffensen 加速后公式的表现的对比可知 steffensen 对公式的加速作用也存 在不确定性 可能收到良好效果 如 公式三的加速得到一个收敛性能最好 稳定性最佳的公式 也可能收到更坏的效果 如 公式四反而在加入加速公式后收敛速度变慢 可能使得原本不收敛 的公式变得收敛 也可能对公式的收敛性没有影响 参考文献 1 posted on 2006 05 04 22 29 透明 人 1 学生学生 学习学习 心得心得 通过对迭代法的深入研究 我从中体会到了一种方法或者算法不一 定能够在所有情况下都取得良好效果 其功能效果受到多方面的影