c语言计算机编程三种方法求解非线性方程.doc

本本 科科 专专 业业 学学 年年 论论 文文 题题 目 目 非线性方程求解比较非线性方程求解比较 姓姓 名名 何 娟 专专 业业 计算机科学技术系 班班 级级 08 级本科 2 班 指指 导导 老老 师师 刘 晓 娜 完成日期 完成日期 2010 年年 11 月月 21 日日 计算机学年专业论文 非线性方程求解 1 题题 目 目 非线性方程求解比较非线性方程求解比较 摘摘 要要 本文给出了三种求解非线性方程的方法 分别是二分法 牛顿迭代法 割 弦法 二分法巧妙地利用插值得到的点以及有根区间中点这两点处的函数值 缩小隔根区间 以期望得到更快的收敛速度 牛顿迭代法是非线性方程根的一 种常见的数值方法 对于非线性方程的单重零点来说 牛顿迭代法一般具有局部 二阶收敛性 但是当所求的根 X 是 F X 的 M 重根时 M 是大于等于 2 的整数 此 时牛顿迭代法只有一阶收敛性 弦截法是将牛顿迭代公式中用差商 F F k x 1 k x 代替导数 本文给出了算法改进的具体步骤及算法流程图 k x 1 k x k F x 相关的数值结果也说明了方法的有效性 关关 键键 词词 二分法 牛顿迭代法 割弦法 非线性方程 计算机学年专业论文 非线性方程求解 2 目目 录录 第一章 绪 论 1 第二章 求解非线性方程的三种常见算法 2 2 1 二分法二分法 2 2 2 牛顿迭代法牛顿迭代法 3 2 3 割弦法割弦法 5 第三章 求解非线性方程的三种算法比较 6 3 1 二分法求解方法二分法求解方法 6 3 2 牛顿迭代法求解牛顿迭代法求解 8 3 3 割弦法求解割弦法求解 9 参参 考考 文文 献献 12 计算机学年专业论文 非线性方程求解 3 第一章第一章 绪绪 论论 在科技飞速发展的今天 计算机已经成为我们生活中不可缺少的一部分了 在我们生活与生产中扮演越来越重要的角色 而科学计算已经成为科学计算的 重要方法之一 其应用范围已渗透到所有科学领域 作为科学与工程计算的数 学工具 计算方法已成为高等院校数学与应用数学 信息与计算科学 应用物 理学等必修课 在永恒变化发展的自然界与人类社会中 在研究其内部规律的 各个科学领域中 更深刻 更精确地描述其内部规律的数学工具之一 就是非 线性方程 非线性代数是研究大规模离散数据的运算处理与内在性状的数学科 学 科学技术离不开数据处理与数据分析 因此非线性代数具有广泛的应用 无论在物理学 力学 化学 控制论等科学领域中 非线性方程屡见不鲜 就 是在生命科学领域中 也是用非线性方程来描述生命过程中的能量 信息 物 质等传递过程的 因此 对非线性方程的求解自然就是一个非常重要了 然而 求解非线性方程有很多种方法 每种方法都有自己的优缺点 目前已有的数学软件可以帮助我们实现上机计算 基本上已经将数值分析 的主要内容设计成简单的函数 只要调用这些函数进行运算便可得到数值结果 非线性代数中许多数值计算与计算机结合 才能得到更很好 更快 更精准的 结果 为了将计算机与线性代数方程组更好的结合在一起 本文做了比较全面 的的解说 本文比较全面的介绍了现代计算机科学与工程计算中常见的数值计 算方法 对这些数值计算方法的基本理论与实际计算机实践应用进行了详细的 分析 同时还简要的分析了这些数值算法的计算效果 稳定性 收敛效果 适 用范围以及优劣性与特点 本文着重于化抽象为具体 引用一个具体的非线性 方程用发散性的思维对其进行彻底的分析 主要有 引入一个非线性方程 分别运用三种思想进行分析 得到三种解法的根 本思想 把数学方法与数学思想提出来 并进行简洁易懂的理论证明 既突出了 线性代数的理论和基本思想 又可以帮助读者对该数学方法的理解 给出各种算法的循环思想以及流程图 展现出一个清新的框架在读者面 前 基于 c 语言的基础上 写出可执行的代码 对各种算法得到的结果进行比较分析 计算机学年专业论文 非线性方程求解 4 第二章第二章 求解非线性方程的三种常见算法求解非线性方程的三种常见算法 2 1 二分法二分法 单变量函数方程 f x 0 其中 f x 在闭区间 a b 上连续 单调 且 f a f b 0 则有函数的介值定理可 知 方程 f x 0 在 a b 区间内有且只有一个解 二分法是通过函数在 x 区间端点的符号来确定所在区域 将有根区间缩小到充分小 从而可以求出 x 满足给定精度的根的近似值 x 下面研究二分法的几何意义 设 1 b 区间 中点 及 若 0 则 1 a 1 b 11 b a 1 x 2 11 ba 1 xf 1 xf x 若 f f 0 令 则根 中 这样就得到长度缩 1 a 1 x 2 a 1 a 2 b 1 x x 2 a 2 b 小一半的有根区间 若 f f 0 令 则根 2 a 2 b 1 b 1 x 2 a 1 x 2 b 1 b x 2 a 中 这样就得到长度缩小一半的有根区间 即 f f 0 此时 2 b 2 a 2 b 2 a 2 b 2 b 对有根区间 重复上述步骤 即分半求中点 判断中电处符号 2 a 2 11 ab 2 a 2 b 则可得长度有缩小一半的有根区间 2 a 2 b 如图所示 重复上述过程 第 n 步就得到根的近似序列及包含的区间套 如 x n x x 下 1 2211 nn bababa 计算机学年专业论文 非线性方程求解 5 2 0 nnnn baxbfaf 3 n a n b 112 1 nn ba 1 2 n ab 4 且 n 1 2 3 2 nn n ba x x n x 1 2 n ab 显然 lim 且以等比数列的收敛速度收敛于 因此用二分法求 n x n x x f x 0 的实根可以达到任意指定精度 x 2 2 牛顿迭代法牛顿迭代法 设方程 f x 0 在其根的某个领域 U 内有一阶连续导数 且 f x x x 0 求 f x 0 的根 首先要将 f x 0 转化为等价形式 并使 x 满 x xx 足不动点迭代的一般理论 于是我们令 x x h x f x 可由 0 来确定 h x 的结构 根据 1 x x 1 h f h f x1 1 h f 0 可得 x x x x x h 1 f 由于 f x 0 且 f x 连续 因此当 h x 1 f x 时 h x1 x x 0 即令 x x f x f x 从而有迭代格式 k 0 1 2 1 k x k k k xf xf x 由于 都在 U 领域里 从而当 B 比较小时 可用 f 可近似代替 1 x 2 x 3 x 0 x f 此方法称为牛顿迭代法 k x 1 k x k x 0 xf xf k 下面研究牛顿法的几何意义 设 r 是方程 f x 0 的根 选取作为的 r 初始近似值 经过 f 做曲线 0 x 0 x 0 x y f x 的切线的方程 y f f x 求出 L 与 x 的交点的横坐标 0 x 0 x 0 x 1 x f f 称为 r 的一次近似值经过点 f 做切线 y f x 的切线 0 x 0 x 0 x 1 x 1 x 1 x 并求出该切线与 x 轴的交点横坐标 f f 称为 r 的二次近似值 2 x 1 x 1 x 1 x 2 x 重复以上操作可以得到 r 的近似值序列 下述三个定理分别讨论了牛顿法的收 敛性质 计算机学年专业论文 非线性方程求解 6 定理定理 1 对于方程 f x 0 设 f x 在 a b 上有二阶连续导数且满足下述 条件 1 f a f b 0 0 x 0 x 0 x f 则由牛顿法产生的迭代序列收敛于 f x 0 的根 且 n x x 2 2 1 lim xf xf xx xx k k k 定理定理 2 对于方程 f x 0 设 f x 在 a b 上有二阶连续导数且满足下述 条件 1 f a f b 0 2 对任意的 x a b f x 0 0 x f 3 b a x x x f 0 当 时 由牛顿迭代法 k 0 1 2 式产 0 x x x 1 k x k k k xf xf x 生的序列是以不低于二阶的收敛速度收敛到 n x x 2 3 割弦法割弦法 设 为方程 f x 0 的两个近似根 用差商得 f f k x 1 k x k x 1 k x k x 1 k x 代替牛顿迭代公式中的导数 f 于是得到如下的迭代公式 k x 下面研究割弦法的几何意义 1 k x k x 1 1 kk kk k xx xfxf xf 经过点 f 及点 f 两点作割线 其点斜式方程为 k x k x 1 k x 1 k x 计算机学年专业论文 非线性方程求解 7 Y f 其零点为 X k x 1 1 k kk kk xx xx xfxf k x 把 X 用表示即得到迭代格式 它又称为双点弦割 1 1 kk kk k xx xfxf xf 1 k x 法 需要两个初值 此割线与 X 轴交点的横坐标就是新的近似值 所以弦截法又称为割线 1 k x 法 如图所示 下面三个定理为弦割法收敛定理 定理定理 1 设 f x 在其零点的邻域 U 0 x x x x 内有二阶连续导数 则当U 时 由割弦法式产生的0 x f 0 x x 序列收敛于 且收敛的阶为 1 618 n x x 定理定理 2 设在区间 a b 上连续 且满足下述三点 x f 1 f a f b 0 内有二阶连续导 x x x x 数 f x 0 则当 U 时 由弦割 0 x x 1 k x k x 1 1 kk kk k xx xfxf xf 计算机学年专业论文 非线性方程求解 8 式产生的序列收敛于 且收敛的阶为 1 618 n x x 第三章第三章 求解非线性方程的三种算法比较求解非线性方程的三种算法比较 本章主要通过具体实例比较了第二章中三种算法的优缺点 并得到相应 结论 求解非线性方程 x x x 4 x x 10 0 在 1 2 上 x0 1 5 附近的解精确到 0 000 000 001 3 1 二分法求解方法二分法求解方法 二分法是求方程近似根的方法中行之有效的最简单的方法 它的递推过程简单 便于计算机上实现 实现二分法的基本步骤如下 1 输入有根区间的端点 a b 及预先给定的精度 exp 2 计算 x a b 2 3 若 f a f x 0 则 b x 否则 a x 4 若 b a exp 则输出方程满足精度要求的根 x 则计算结束 否则转 2 二分法算法流程图 二分法算法流程图 c 语言代码 include stdio h include math h float function float x float f f float x x x 4 x x 10 return f void main float f f f 1 x 2 x 0 x 1 x 2 x 0 x 10 x2 10 1 x 计算机学年专业论文 非线性方程求解 9 f function 1 x 1 x f function 2 x 2 x do 2 计算中点 0 x 1 x 2 x f function 计算中点处的函数值 0 x 0 x if f f 1e 6 0 x printf The root is f 0 x 运行结果 n有根区间 a b f 的符号 n x n x 1 1 0 2 0 1 5 2 1 0 1 5 1 25 3 1 25 1 5 1 375 4 1 25 1 375 1 3125 5 1 3125 1 375 1 343 75 6 1 3475 1 375 1 359 375 7 1 359375 1 375 1 367 185 计算机学年专业论文 非线性方程求解 10 The root is 1 365230 3 2 牛顿迭代法求解牛顿迭代法求解 步骤 1 给出初始近似根 及精度 exp 0 x 2 计算 f f 1 x 0 x 0 x 0 x 3 若 1e 6 0 x printf The root is f 0 x 运行结果 The root is 1 365231 3 3 割弦法求解割弦法求解 步骤 1 选择迭代初值 及精度 esp 0 x 1 x 2 计算 f f f 2 x 1 x 1 x 1 x 0 x 1 x 0 x 3 若 0 转向 4 否则 转向 2 2 x 1 x 0 x 1 x 1 x 2 x 4 输出满足精度的根 结束 2 x 算法流程图 计算机学年专业论文 非线性方程求解 12 c 语言代码 include include define eps 0 00001 容许误差 define N 100 最大迭代次数 N float f float x 定义函数 f x float y y x x x 4 x x 10 return y void main float x1 0 x 2 x int i printf input 0 x 1 x scanf f f 0 x 1 x for i 1 i N i f f f 弦截法迭代公式 2 x 1 x 1 x 1 x 0 x 1 x 0 x if fabs eps fabs f eps 满足精度要求输出近似根并退出 2 x 1 x 2 x printf nRoot of equation is 8 6f n 2 x return 准备下一次迭代的初值 0 x 1 x 1 x 2 x 计算机学年专业论文 非线性方程求解 13 printf nAfter d repeat no solved n N 输出无解信息 运行结果 Kf k x k x 01 0 5 0 12 014 0 21 263 157 895 1 602274 384 31 338 827 839 0 430 364 744 41 366 616 395 0 022 909 427 51 365 211 903 2 990 671 pow 10 4 61 365 200 01 2 0416 pow 10 7 71 365 230 0130 0 81 365 230 0130 0 Root of equation is 1 365230 小结 二分法的优点是计算简单 方法可靠 误差容易估计 只要求连续 且 总是收敛的 因此对函数的性质要求较低 它的缺点是不能求偶数重根 也不 能求复根 且收敛较慢 故一般不单独将其用于求根 只用其为根求得一个较 好的近似值 牛顿迭代法是多项式求根的一种效率很高的算法 收敛速度快 对单根 算法简单是迭代法中较好者 但是它有两个缺点 第一每次只能求出一个 根 求其它根时若采用降次处理又会产生精度降低的问题 第二有时会遇