求解非线性算子方程的两步组合方法的收敛性
- 格式:pdf
- 大小:437.86 KB
- 文档页数:14
本科专业学年论文题目:非线性方程求解比较姓名:何娟专业:计算机科学技术系班级:08级本科(2)班指导老师:刘晓娜完成日期:2010年11 月21 日题 目:非线性方程求解比较摘 要本文给出了三种求解非线性方程的方法,分别是二分法,牛顿迭代法,割弦法。
二分法巧妙地利用插值得到的点以及有根区间中点这两点处的函数值,缩小隔根区间,以期望得到更快的收敛速度。
牛顿迭代法是非线性方程根的一种常见的数值方法,对于非线性方程的单重零点来说,牛顿迭代法一般具有局部二阶收敛性,但是当所求的根X*是F(X)的M 重根时,M 是大于等于2的整数,此时牛顿迭代法只有一阶收敛性。
弦截法是将牛顿迭代公式中用差商F(k x )-F(1-k x )/ (k x - 1-k x )代替导数'()k F x 。
本文给出了算法改进的具体步骤及算法流程图相关的数值结果也说明了方法的有效性。
关 键 词 : 二分法;牛顿迭代法;割弦法;非线性方程目录第一章绪论- 3 -第二章求解非线性方程的三种常见算法……………………………- 4-2.1 二分法………………………………………………………-4 -2.2 牛顿迭代法……………………………………………………- 5 -2.3 割弦法- 6 -第三章求解非线性方程的三种算法比较- 8 -3.1 二分法求解方法- 8 -3.2 牛顿迭代法求解- 10 -3.3 割弦法求解- 11 -参考文献- 14 -第一章绪论在科技飞速发展的今天,计算机已经成为我们生活中不可缺少的一部分了,在我们生活与生产中扮演越来越重要的角色,而科学计算已经成为科学计算的重要方法之一,其应用范围已渗透到所有科学领域,作为科学与工程计算的数学工具,计算方法已成为高等院校数学与应用数学,信息与计算科学,应用物理学等必修课。
在永恒变化发展的自然界与人类社会中,在研究其内部规律的各个科学领域中,更深刻、更精确地描述其内部规律的数学工具之一,就是非线性方程。
Computer Knowledge and Technology 电脑知识与技术人工智能及识别技术本栏目责任编辑:唐一东第7卷第1期(2011年1月)具有全局收敛性的求解非线性方程组的新方法任晓慧(聊城大学计算机学院,山东聊城252059)摘要:将非线性方程组的求解转化为多维函数优化问题,利用基于自然选择的粒子群算法进行求解,解决了传统方程求解对初值要求高的问题。
仿真结果表明,该算法具有全局收敛性,精度高,速度快等特点。
关键词:自然选择粒子群算法;非线性方程组;初值;全局收敛中图分类号:TP301文献标识码:A 文章编号:1009-3044(2011)01-0197-02A New Method With Global Convergence for Solving System of Nonlinear EquationsREN Xiao-hui(College of Computer Science,Liaocheng University,Liaocheng 252059,China)Abstract :When solving system of nonlinear equations be transformed into the multidimensional function optimization problem,the prob -lem can be solved by particle swarm optimization algorithm based on nature selection.The method solves the problem that system of non -linear equations is very sensitive to initial value .Simulation results show that this algorithm has the advantage of the Global Convergence ,high precision and fast operation speed.Key words:NSPSO;system of nonlinear equations;global convergence非线性方程组的解法长期以来一直是工程应用和数值计算中重要的研究内容。
关于牛顿迭代法的课程设计实验指导非线性方程(或方程组)问题可以描述为求 x 使得f (x ) = 0。
在求解非线性方程的方法中,牛顿迭代法是求非线性方程(非线性方程组)数值解的一种重要的方法。
牛顿是微积分创立者之一,微积分理论本质上是立足于对世界的这种认识:很多物理规律在微观上是线性的。
近几百年来,这种局部线性化方法取得了辉煌成功,大到行星轨道计算,小到机械部件设计。
牛顿迭代法正是将局部线性化的方法用于求解方程。
一、牛顿迭代法及其收敛速度牛顿迭代法又称为牛顿-拉夫逊方法(Newton-Raphson method ),是一种在实数域和复数域上通过迭代计算求出非线性方程的数值解方法。
方法的基本思路是利用一个根的猜测值x 0做初始近似值,使用函数f (x )在x 0处的泰勒级数展式的前两项做为函数f (x )的近似表达式。
由于该表达式是一个线性函数,通过线性表达式替代方程中的求得近似解x 1。
即将方程f (x ) = 0在x 0处局部线性化计算出近似解x 1,重复这一过程,将方程f (x ) = 0在x 1处局部线性化计算出x 2,求得近似解x 2,……。
详细叙述如下:假设方程的解x *在x 0附近(x 0是方程解x *的近似),函数f (x )在点x 0处的局部线化表达式为)()()()(000x f x x x f x f '-+≈由此得一次方程 0)()()(000='-+x f x x x f求解,得 )()(0001x f x f x x '-= 如图1所示,x 1比x 0更接近于x *。
该方法的几何意义是:用曲线上某点(x 0,y 0)的切线代替曲线,以该切线与x 轴的交点(x 1,0)作为曲线与x 轴的交点(x *,0)的近似(所以牛顿迭代法又称为切线法)。
设x n 是方程解x *的近似,迭代格式)()(1n n n n x f x f x x '-=+ ( n = 0,1,2,……) 就是著名的牛顿迭代公式,通过迭代计算实现逐次逼近方程的解。
非线性方程求解算法的收敛性分析在数学和工程领域中,非线性方程求解是一项重要的任务。
与线性方程相比,非线性方程由于其复杂性而具有更高的挑战性。
因此,开发一种有效且收敛性良好的求解算法显得尤为重要。
本文将对非线性方程求解算法的收敛性进行分析,并探讨影响收敛性的因素。
一、非线性方程求解算法综述非线性方程求解算法广泛用于科学计算和工程应用中,例如在数值模拟、优化问题以及信号处理等领域。
常见的求解算法包括二分法、牛顿迭代法、割线法、弦截法等。
尽管这些算法在不同问题上具有一定的适用性,但它们在求解非线性方程时都存在收敛性问题。
二、收敛性的定义和评价在讨论收敛性之前,我们首先需要明确收敛性的定义。
对于一个求解算法而言,收敛性表示算法能够找到非线性方程的根,并且随着迭代次数的增加,逼近于精确解。
评价一个算法的收敛性通常需要考虑三个方面:收敛速度、收敛域和全局收敛性。
1. 收敛速度收敛速度是指求解算法逼近根的速度。
通常情况下,我们希望算法具有快速收敛的性质,以提高求解效率。
常见的判断收敛速度的方法有用残差准则和定义迭代次数等。
2. 收敛域收敛域表示求解算法在何种范围内能够保证收敛性。
对于一些特定的求解算法,收敛域可能受到限制。
因此,在选择求解算法时,需要考虑非线性方程的特性,以确定算法的收敛域是否满足问题要求。
3. 全局收敛性全局收敛性意味着算法以任意的初值作为起点,都能够收敛到方程的根。
虽然一些算法可能在特定的条件下保证收敛性,但在全局范围内可能存在无法收敛的情况。
三、影响收敛性的因素收敛性的质量取决于多个因素。
下面我们将讨论几个主要的影响因素。
1. 初始值的选取初始值的选取在非线性方程求解中起着至关重要的作用。
不同的初始值可能导致算法的收敛性不同。
因此,合理选择初始值对于求解算法的收敛性至关重要。
2. 方程的特征方程的特征也会对求解算法的收敛性产生影响。
例如,方程的非线性程度、奇点的存在等都可能导致算法的收敛性发生变化。
一:非线性方程的基本迭代方法简单迭代法非线性方程的一般形式f(x)=0 其中f(x)是一元非线性函数。
若存在常数s 使f(s)=0,则称s 是方程的根。
把方程转化为其等价的方程)(x x ϕ=,因而有)(s s ϕ=。
选定s 的初始近似值0x ,用迭代公式)(1k k x x ϕ=+,得到}{k x 收敛于s ,就求出了方程的解。
收敛性:)(s s ϕ=,)(x ϕ'在包含s 的某个开区间内连续。
如果|)(x ϕ'|<1则存在δ>0,0x ∈[s-δ,s+δ]时,由该迭代函数产生的迭代法收敛。
收敛速度:(}{k x 收敛于s ,k e 为s 与k x 的差值绝对值,则c e e r k k k =+∞→1lim,c 是常数,则该迭代是r 阶收敛)Newton 法为了使迭代的收敛速度更快,应尽可能使)(x ϕ在s 处有更多阶的导数等于零。
令)(x ϕ=)()(x f x h x +,)(x h 为待定函数,已知)(s ϕ'=0,推出)(x h =)(1x f '-。
这就得出了牛顿法的迭代形式 )()(1k k k k x f x f x x '-=+,(k=0、1、···) 牛顿法是二阶收敛的迭代方法,但是牛顿法的是局部收敛的,因此要求初值要靠近根。
求解中,对于每一个k 都要计算)(k x f ',而导数的计算比较麻烦,否则会产生很大误差。
割线法 在牛顿法基础上,用11)()(----k k k k x x x f x f 来代替)(k x f ',其中1-x 、0x 预先给定。
得到了割线法的迭代形式 )()())((111--+---=k k k k k k k x f x f x x x f x x ,(k=0、1、···) 割线法的收敛速度至少为1.618这样就避免了牛顿法求导数的繁琐程序单点割线法单点割线法就是在割线法的基础上,用))(,(00x f x 代替))(,(11--k k x f x ,得到的迭代形式 )()()(001k k k k k x f x f x f x x x x ---=+,(k=1、2、···) 单点割线法是一阶收敛的方法,它比割线法初值要少取一个点更加容易选取初值二:非线性方程的迭代解法的拓展修正的Chebyshev 法思想:将函数)(x f 在k x 处进行泰勒展开既 +-''+-'+≈!2)()())(()()(2k k k k k x x x f x x x f x f x f ,如果)(x f ≠0,先取线性部分来代替原来函数,既)(x f =)(k x f +))((k k x x x f -'=0,得到k x x -=)()(k k x f x f '-; 再用二次多项式部分代替原函数,既!2)()())(()()(2k k k k k x x x f x x x f x f x f -''+-'+==0,合并这两次的结果得到)()()))((2)()(1(2k k k k k k x f x f x f x f x f x x ''''⋅+-=,令1+=k x x ,得到就得到了新的迭代公式,这就是Chebyshev 方法的思想,该方法的迭代公式具有三阶收敛速度。
一.何为收敛?在这里我引用一个会员的提问来解释这个问题:Q:结构非线性静力分析经常出现收敛这个词,如:收敛容限,收敛准则,收敛的解,位移收敛检验等,请解释,thanks!A: 个人是这样理解的谈到收敛总会和稳定性联系在一起,简单的说,就是在进行求解过程中的一些中间值的误差对于结果的影响的大小,当中间量的误差对于你的数值积分的结果没有产生影响,就说明你的积分方法是稳定的,最终你的数值积分的结果就会收敛于精确解;当中间量的误差导致数值积分结果与精确解有很大的差别时,就说明你的方法稳定性不好,你的数值积分结果不会收敛于精确解。
我想当你对于稳定性和收敛的概念真正理解后,那些名词对于你来说,并不是问题,力学的问题最终都会和数学联系在一起,建议你看看数值积分方面的教程,学好了数学,力学对于你来说就是a piece of cake。
Q:那么说收不收敛,最终都是因为采用的计算方法和计算参数选取的问题了?A:就本人所学的专业来说,很大程度上取决于所采用的算法,我学的是结构工程,举个例子吧 :当在进行结构动力时程分析时,采用的几分方法有线性加速度法,威尔逊-theta法,对于线性加速度法,当时间步长大于周期的0.5倍时,计算结果很可能出现不收敛,而当时间步长小于0.1倍的周期时,才有可能获得稳定的计算结果;而威尔逊-theta法,实质上就是线性加速度法的修正形式,很多实例表明当theta值大于1.37时,这种算法是无条件稳定的。
当然影响计算结果是否收敛的原因有很多,比如初始条件,我所指的仅仅是我所学专业的一个问题的很小的一个方面。
A: 说白了,就是数学。
牵涉到实际的计算问题时,才发现数学实在是太有用了,不过可惜数学实在学得不好。
A: 收敛的问题,就好像你往水里扔一块石头激起的波浪,慢慢会平息下来,这就收敛了。
计算的时候就是这样,数据在每次迭代的时候在精确解的周围震荡,最后无限趋向于精确解。
我想学过级数的人就应该知道,里面就有个无穷级数的和收敛的问题。