数值计算课程设计报告(非线性方程求根)

精品文档 1欢迎下载1欢迎下载 数 值 计 算 方 法 课 程 设 计 报 告 课程设计名称 数值计算方法 课程设计题目 非线性方程求根 年 级 专 业 组员姓名学号 指 导 教 师 精品文档 2欢迎下载2欢迎下载 完 成 时 间 非线性方程求根 一 一 问题提出问题提出 随着科学技术 生产力经济的发展 在科学与工程计算中存在着大量方程求根问题 例如贷款购房问题 工厂的最佳订货问题等都需要求解一类非线性方程的根 首先根据 实际问题列出数学模型 确定变量 给出各个条件及相关函数 然后对建立的模型进行 具体分析和研究 选择合适的求解方法 编写函数的程序 用计算机求出方程的解 通 过所求解分析具体情况 求解非线性方程的问题有以下几种基本方法 二分法简单易行 但收敛较慢 仅有 线性收敛速度 而且该方法不能用于求偶数重根或复根 但可以用来确定迭代法的初始 值 牛顿法是方程求根中常用的一种迭代方法 它除了具有简单迭代法的优点外 还具 有二阶收敛速度 在单根邻近处 的特点 但牛顿法对初始值选取比较苛刻 必须充分 靠近方程的根 否则牛顿法可能不收敛 弦截法是牛顿法的一种修改 虽然比牛顿法收 敛慢 但因它不需计算函数的导数 故有时宁可用弦截法而不用牛顿法 弦截法也要求 初始值必须选取得充分靠近方程的根 否则也可能不收敛 二 二 背景分析背景分析 代数方程的求根问题是一个古老的数学问题 理论上 n 次代数方程在复数域内一 精品文档 3欢迎下载3欢迎下载 定有 n 个根 考虑重数 早在 16 世纪就找到了三次 四次方程的求根公式 但直到 19 世纪才证明大于等于 5 次的一般代数方程式不能用代数公式求解 而对于超越方程就复 杂的多 如果有解 其解可能是一个或几个 也可能是无穷多个 一般也不存在根的解 析表达式 因此需要研究数值方法求得满足一定精度要求的根的近似解 牛顿迭代法是 牛顿在 17 世纪提出的一种求解方程 多数方程不存在求根公式 从而求精确根非常困 难 甚至不可能 从而寻找方程的近似根就显得特别重要 而在各种科学和工程计算中往往要用到非线性方程组的求解 而牛顿法又是最基础 的迭代法 在各种计算力学 控制工程等领域中发挥了不可代替的作用 而在数值计算 中 非线性方程组的求解同样具有重要意义 随着计算机技术的成熟和高速发展 对于 非线性方程求根问题出现了大量的数学软件 如 MATLAB SAS SPSSD 等 计算机已经成 为工程师应用数学解决工程问题的主要运算工具 同时 工程专业的学生对数学教育的 需求重点正在从手工演绎和运算能力的培养转变到结合计算机软件进行建模 求解和论 证能力的培养 我们采用 Matlab 数学软件平台 通过实例比较了二分法 牛顿迭代法 弦截法三种基本方法的优缺点 三 三 基本算法思想与实现基本算法思想与实现 1 1 二分法 二分法 单变量函数方程 f x 0 其中 f x 在闭区间 a b 上连续 单调 且 f a f b 0 则有函数的介值定理可知 方程 f x 0 在 a b 区间内有且只有一个解 二分法是通过函数在区间端点的 x 符号来确定所在区域 将有根区间缩小到充分小 从而可以求出满足给定精度的根 x 的近似值 x 下面研究二分法的几何意义 设 1 b 区间 中点 及 若 0 则 x 若 f 1 a 1 b 11 b a 1 x 2 11 ba 1 xf 1 xf 1 x f 0 令 则根 中 这样就得到长度缩小一半的 1 a 1 x 2 a 1 a 2 b 1 x x 2 a 2 b 精品文档 4欢迎下载4欢迎下载 有根区间 若 f f 0 令 则根 中 2 a 2 b 1 b 1 x 2 a 1 x 2 b 1 b x 2 a 2 b 这样就得到长度缩小一半的有根区间 即 f f 0 此时 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 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以等比数列的收敛速度收敛于 因此用二分法求 f x 0 的实根 x 可以达到任意指定精度 x 精品文档 5欢迎下载5欢迎下载 2 2 牛顿迭代法 牛顿迭代法 设方程 f x 0 在其根的某个领域 U 内有一阶连续导数 且 f 0 x x x 求 f x 0 的根 首先要将 f x 0 转化为等价形式 xx 并使 x 满足不动 x 点迭代的一般理论 于是我们令 x x h x f x 可由 0 来确定 h x 的结构 根据 x 1 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 时 x x h x1 0 即令 x x f x f x 从而有迭代格式 k 0 1 2 1 k x k k k xf xf x 精品文档 6欢迎下载6欢迎下载 由于 都在 U 领域里 从而当 B 比较小时 可用 f 可近似代替 f 1 x 2 x 3 x 0 x 此方法称为牛顿迭代法 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 的交点的横坐标 f 0 x 0 x 0 x 1 x 0 x f 称为 r 的一次近似值经过点 f 做切线 y f 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 的近似值序列 下述三个定理分别讨论了牛顿法的收敛性质 定理定理 1 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 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 0 当 时 由牛顿迭代法 0 x x x 1 k x k 0 1 2 式产生的序列是以不低于二阶的收敛速度收敛到 k k k xf xf x n x x 3 3 弦截法 弦截法 精品文档 8欢迎下载8欢迎下载 设 为方程 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 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 n x 敛于 且收敛的阶为 1 618 x 精品文档 9欢迎下载9欢迎下载 定理定理 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 式产生的序列收敛于 且收敛的阶为 1 618 n x x 精品文档 10欢迎下载10欢迎下载 四 四 具体应用实例分析具体应用实例分析 求解在附近的根 033 23 xxxxf5 1 1 1 二分法 二分法 建立 erfen M 文件 function k x wuca yx erfen a b abtol a 1 a b 1 b ya fun a 1 yb fun b 1 程序中调用的fun m为函数 if ya yb 0 disp 注意 ya yb 0 请重新调整区间端点a和b retur n end max1 1 ceil log b a log abtol log 2 ceil 是向方向取整 for k 1 max1 1 a ya fun a b yb fun b x a b 2 yx fun x wuca abs b a 2 k k 1 k a b x wuca ya yb yx If yx 0 a x 精品文档 11欢迎下载11欢迎下载 b x else if yb yx 0 b x yb yx else a x ya yx end if b a x 10 0 1 10 y fun x plot x y 精品文档 12欢迎下载12欢迎下载 由图 我们选取区间 6 6 输入程序 k x wuca yx erfen 6 6 0 001 运行结果 k 13 x 1 7322 wuca 7 3242e 004 yx 0 0012 2 2 牛顿迭代法 牛顿迭代法 精品文档 13欢迎下载13欢迎下载 建立 newtonqx M 文件 function k xk yk piancha xdpiancha newtonqx x0 tol ftol gxmax x 1 x0 for i 1 gxmax x i 1 x i fnq x i dfnq x i eps piancha abs x i 1 x i xdpiancha piancha abs x i 1 eps i i 1 xk x i yk fnq x i i 1 xkykpianchaxdpiancha if abs yk ftol xk x i i 1 xkykpianchaxdpiancha return end 精品文档 14欢迎下载14欢迎下载 i 1 xk yk piancha xdpiancha 建立 FNQ 原函数文件 function y fnq x y x 3 x 2 3 x 3 建立 DFNQ 导函数文件 function y dfnq x y 3 x 2 2 x 3 输入程序 k xk yk piancha xdpiancha newtonqx 1 5 0 001 0 001 20 输出结果 k 3 xk 1 7321 yk 1 0617e 005 piancha 0 0013 xdpiancha 7 5560e 004 3 3 弦截法 弦截法 建立 gexian 文件 function k piancha xdpiancha xk yk gexian x01 x02 tol ftol gxmax x 1 x01 x 2 x02 fori 2 gxmax 精品文档 15欢迎下载15欢迎下载 u i fnq x i x i x i 1 v i fnq x i fnq x i 1 x i 1 x i u i v i piancha abs x i 1 x i xdpiancha piancha abs x i 1 eps i i 1 xk x i yk fnq x i i 2 pianchaxdpianchaxkyk if abs yk ftol xk x i yk fnq x i return 精品文档 16欢迎下载16欢迎下载 end 建立 FNQ 函数文件 function y fnq x y x 3 x 2 3 x 3 输入程序 取 1 5 附近的初始值 1 4 1 6 两个 k piancha xdpiancha xk yk gexian 1 4 1 6 0 001 0 001 20 输出结果 k 4 piancha 5 1561e 004 xdpiancha 2 9769e 004 xk 1 7321 yk 3 6710e 005 五 设计总结五 设计总结 根据二分法求解非线性方程根的原理 将所求方程根所在的区间平分为两个小区间 在判断根属于哪个小区间 把有根的小区间再平分为二 再判断根所在的更小的区间 对分 重复这一过程 最后求出所要的近似值 当所分的小区间的间距越小的时候 得 出的方程根结果就越精确 其原因就是所分的小区间间距越小 则就越接近方程等于 0 的根 所以最后的结果的精度越高 得到的误差越小 而对于简单迭代法 只有在满足 一定条件的情况下 才能求解出 在区间上有唯一根 使迭代序列 收敛于 根据牛顿 迭代法的原理 求解出非线性方程根的结果可以看出 牛顿迭代法具有平方收敛的速度 所以在迭代过程中只要迭代几次就会得到比较精确的解 并不像简单迭代法 需要迭代 多次才能解出较为精确的结果 但是用牛顿迭代法求解时选定的初值要接近方程的解 精品文档 17欢迎下载17欢迎下载 否则可能得不到收敛的结果 同时 牛顿迭代法计算量也会相对较大些 单点弦截法 用选定的两个初值点所对应的函数值连接作弦 用此弦与 轴的交点横坐标作为方程根的 近似值 按此方法进行迭代计算 直到满足精度要求为止 六 参考文献六 参考文献 1 奚梅成 数值分析方法 M 合肥 中国科技技术大学出版社 2007 2 薛毅 数值分析与实验 M 北京 北京理工大学出版社 2005 3 汪卉琴 刘目楼 数值分析 M 北京 冶金工业出版社 2004 4 丁丽娟 程杞元 数值计算方法 M 北京 北京理工大学出版社 2005 5 薛定宇 陈阳泉 高等应用数学问题的 MATLAB 求解 北京 清华大学出版社 2008 七 心得体会七 心得体会 1 韩建 这次数值分析课程设计我们受益匪浅 在刚开始拿到题目时 我们提出 很多问题 4 个人各有自己的想法 产生了分歧 但经过这一周的时间和体验下来 我 们学到的不仅是课本知识 还有团队和合作精神 现在想来 也许学校安排的课程设计 有着它更深层的意义 它不仅仅让我们综合那些理论知识来运用到设计和创新 还让我 们知道了一个团队凝聚在一起是所能发挥出的巨大潜能 在这次课程设计中 我们运用到了以前所学的专业课知识 牛顿迭代法 matlab 汇 编语言等 虽然过去都将这些知识用于解题中 未有独立应用过它们 但在学习的过程 中带着问题去学我发现效率很高 设计过程 好比我们的成长历程 常有一些不如意 难免会遇到各种各样的问题 这也激发了我今后努力学习的兴趣 通过这次设计 我懂 得了学习的重要性 了解到理论知识与实践结合的重要意义 学会了坚持 耐心和努力 这将为自己今后的学习和工作打下基础 2 高育坤 此次实验过程中学到了许多东西 对于 MATLAB 的运用也比以前熟练 了一些 在编程过程中也考虑了一些题目以外的因素 虽然还有不足之处 不过我相信 只要不断努力一定会有所进步 通过几次实验我也明白了一个道理 对于编程不要一看 到就害怕 一步步的去做 一点点的去实现算法 编程最难的是算法 题目给出了算法 我们需要的就是将数学公式转化为编程语言 3 李婧 通过此次课程设计我们可以知道计算机在现代生活中的应用已经如此普 精品文档 18欢迎下载18欢迎下载 及 尤其是在数学计算当中 Matlab 软件更是发挥了不可替代的作用 Matlab 以其强大 的功能 方便了当今数值计算 数学教程 及工程计算等众多领域 我们在以 Matlab 软 件为平台的基础上 给出了非线性方程的一般解法 非线性方程的求解有二分法 牛顿 迭代法等 二分法的优点是算法简单 且总是收敛的 但由于二分法的收敛速度太慢 故一般不单独将其用于求根 只用其为根求得一个较好的近似 本文主要介绍了牛顿 迭代法及其在现实生活中的应用 牛顿迭代法为平方收敛 故其收敛速度较快 但对初 值的选取需要谨慎 如果初值选取错误 则可能导致方程迭代发散 最终不能求解出正 确解 在计算一些对精度要求特别苛刻时 最好给出较高的精度输入及输出 防止因为 精度问题导致误差过大 最终影响结果 4 王冬妮 二分法的优点是计算简单 方法可靠 误差容易估计 只要求连续 且总是收敛的 因此对函数的性质要求较低 它的缺点是不能求偶数重根 也不能求复 根 且收敛较慢 故一般不单独将其用于求根 只用其为根求得一个较好的近似值 牛顿迭代法是多项式求根的一种效率很高的算法 收敛速度快 对单根 算法简单 是迭代法中较好者 但是它有两个缺点 第一每次只能求出一个 根 求其它根时若 采用降次处理又会产生精度降低的问题 第二有时会遇到由于初始点选择不当而使算法 失效 牛顿法和割弦法都是先将 f x 线性化 然后求根 但线性化的方式不同 从分析的 角度说 牛顿法是在根 x 邻近点处的切线函数作为 f x 的近似 而割弦法是在 x 邻近 用 f x 的一次插值函数作为 f x 的近似函数 它们本质的区别在于 牛顿迭代法在计算 时 只用到前一步的值 弦截法需要用两个猜测值 因此使用这种方法必须先给出 两个初始值 根据以上三种方法的优缺点 我们在使用非线性方程求根时 应根据实际方程选出 一种或者多种方法进行综合求解 以便快速 便捷的求出最佳精确值 八 附录八 附录 1 二分法的程序 function c err yc bisect f1 a b delta f1 是所要求解的函数 a 和 b 分别为有根区间的左右限 精品文档 19欢迎下载19欢迎下载 delta 是允许的误差界 c 为所求近似解 yc 为函数 f 在 c 上的值 err 是 c 的误差估计 ya feval f1 a yb feval f b if yb 0 c b return end if ya yb 0 disp a b 不是有根区间 return end max1 1 round log b a log delta log 2 for k 1 max1 c a b 2 yc feval f c if yc 0 a c b c return elseif yb yc 0 b c 精品文档 20欢迎下载20欢迎下载 yb yc else a c ya yc end if b a delta return end end k c a b 2 er