非线性方程的数值解法
《计算方法》
期末论文
论文题目非线性方程的数值解法
学院
专业
班级
姓名
学号
指导教师
日期
目录
摘要
第1 章绪论
1.1 问题的提出和研究目的和意义
1.2 国内外相关研究综述
1.3 论文的结构与研究方法
第2 章非线性方程的数值解法
2.1 二分法
2.2 迭代法
2.3 迭代法的局部收敛性及收敛的阶
2.4 牛顿迭代法
2.5 牛顿法的改进
2.6 插值
摘要
数值计算方法，是一种研究解决数学问题的数值近似解方法，它的计算对象是那些。
在理论上有解而又无法用手工计算的数学问题。在科学研究和工程技术中都要用到各种计算方法。例如 在地质勘探、汽车制造、桥梁设计、天气预报和汉字设计中都有计算方法的踪影。本文讨论了非线
性方程的数值解法：非线性方程的二分法、迭代法原理、牛顿迭代法，迭代法的收敛性条件及适合非线性方程的插值法等等。
第1 章绪论
可以证明插值多项式L (x) n 存在并唯一。拉格朗日插值多项式的算法 step1.输入 插值节点控制数n 插值点序列 i i x , y
i=0,1,…,n 要计算的函数点x。step2. FOR i =0,1,…,n i 制拉格朗日基函数序列问题的提出和研究目的和意义非线性方程的问题在工程实践中有很多用途 研究其数值解法是当前一个研究方向。目前已有相当一部分算法在广泛使用于工程实践中。非线性方程组和无约束最优化的数值解法 一直是数值优化领域中热门的研究课题。本文对传统的方法进行改进和提出新的算法 该算法不仅有重要的论价值，而且有很高的实用价值。例如在天体力学中，有如下Kepler 开普勒方程 x-t- sin x=0,0< <1,其中t 表示时间 x 表示弧度，行星运动的轨道x 是t 的函数。也就是说，对每个时刻i t 上述方程有唯一解i x ，运动轨道位置。
国内外相关研究综述随着科学技术的高速发展和计算机的广泛应用 求解形如F(x)=0 的非线性方程组问题越来越多的被提出来了 其中F 是的连续可微函数。例如非线性有限元问题、非线性断裂问题、弹塑性问题、电路问题、电子系统计算以及经济与非线性规划问题等都可转化为非线性方程组的求解问题。只要包含有未知函数及其导函数的非线性项的微分方程，无论是用差分方法或有限元方法，离散化
后得到的方程组都是非线性方程组。与线性方程组相比,非线性方程组的求解问题无论在理论上还是在解法上都不如线性方程组成熟和有效.例如,非线性方程组是否有解,有多少解,理论上都没有很好的解法,而对于非线性方程组,除了形式极为特殊的小型方程组以外,直接解法几乎是不可能的.因而,我们主要考虑迭代解法.一般都是采用线性化的方法去构造各种形式的迭代系列.通常都要讨论以下几个基本问题:第一个问题是,迭代点列的适定性问题,即要求迭代点列是有意义的.例如对于牛顿法,Jacobi 矩阵必须是非奇异的.第二个问题,也是最基本的问题,生成的迭代点列的收敛性以及极限点是否为方程组的解.最后一个问题是,迭代点列的收敛速度问题.
早在七十年代以前,许多学者在理论上和数值解法上都对非线性方程组做了大量的研究.Ortega Rheinboldt 系统的介绍了n 阶非线性方程组的基本理论成果,并对牛顿法,延拓法等几种主要迭代法作了详尽的分析.另外,也有一些学者把非线性方程组的求解问题转化为极小化问题, 得到一类称为极小化方法的迭代法, 如下降法, 共轭方向法,Gauss-Newton 法等,李,莫&祁详细介绍了一些适合在计算机上求解的有效算法,如Broyden 算法,以及近十几年来发展的新方法,如区间迭代法,单调迭代法和单纯形法等.
论文的结构与研究方法
1.欲解决的主要问题是：综合当前各类非线性方程的数值解法，通过比较分析，二分法，迭代法，牛顿——雷扶生方法，迭代法的收敛阶和加速收敛方法，解非线性方程的插值方法，这以上五种的算法应
用对某个具体实际问题选择相应的数值解法。
2.比较各类数值算法 分析其优缺点 并应用到具体的实际问题中。
3．利用计算机MATLAB 语言对非线性方程的数值解法进行程序设计。
研究的基本思路是结合目标所提出的问题针对各种方法来具体分析比较
(1) 二分法起始区间[a,b]必须满足f(a)与f(b)符号相反的条件。二分法的第一部是选择中点c=(a+b)/2，然后分析可能存在的三种情况如果f(a)和f(c)符号相反，则在区间[a,c]内存在零点。如果f(c)和f(b)符号相反 则在区间[c,b]内存在零点。如果f(c)=0，则c是零点。（2）迭代法迭代是指重复执行一个计算过程，直到找到答案。首先需要有一个用于逐项计算的规划或函数g(x)，并且有一个起始po。然后通过迭代规则k 1 p =g( k p )，可得到序列值{ k p }。
(3)牛顿——雷扶生法如果f(x)f ‘(x)和f "(x)在根p 附近连续则可将它作为f(x)的特性,用于开发产生收敛到根p 的序列{ k p }的算法。而且这种算法产生序列{ k p }的速度比二分法快。牛顿——雷扶生法依赖于f’(x)和f " (x)的连续性,是这类方法中已知的最有用和最好的方法之一。
(4)迭代法的收敛阶和收敛方法、割线法只计算f(x)不计算f ’(x) 而且在单根上的收敛阶R 1.618033989。割线法比牛顿法收敛速度慢一些 牛顿法的收敛阶为2。当p 是一个M 阶根时 需要更好的求根
技术以获得比线性收敛更快的速度。最终结果显示 通过对牛顿法进行改进 可使其在重根的情况下的收敛阶为2。加速收敛方法有Aitken 加速法和Steffensen 加速法。Steffensen 算法是促使迭代加速收敛的有效算法,但该算法每算一步,需两次迭代 ,其效率不够高。
(5) 解非线性方程的插值方法 Lagrange 插值公式需要进行提高插值多项式次数的插值计算是不方便的。这些方法它们各有优缺点 二分法的优点是对函数f(x)的性态要求不高,只需连续即可,且计算程序简单,能保证收敛。其缺点是收敛速度较慢 且只能求实函数的实零点 单重或奇数重零点。该方法一般用于确定方程根或函数实零点的粗略位置,为快速收敛的算法提供初值。Newton 法的主要优点是收敛速度快,缺点是其收敛性是局部收敛,要求初始值0 x 选在精确解* x 附近才能保证收敛。割线法迭代一次仅需计算函数值f( k x ) 可保留作为下次迭代用,且避免了计算导数。
第2 章非线性方程的数值解法
满足非线性方程f(x)=0 的解x ,称为方程的根或零点。一般用迭代法求非线性方程的根。通常,非线性方程的根不是唯一的,而任何一种方法一次只能算出一个根。因此,在求解非线性方程时,要给定初始条件或求解范围。根可为实数或复数,也称为实根或复根。
二分法
二分法是求方程近似解的一种简单直观的方法。设函数f(x)在[a,b]上连续,且f(a)f(b)<0,则f(x)在[a,b]上至少有一零点 这是微积分
中的介值定理[1],也是使用二分法的前提条件。计算中通过对分区间缩小区间范围的步骤搜索零点的位置。
二分法是对逐步搜索法的一种改进。对于有根区间[ a, b ], 如果取x0= (a+ b)?2,则0 x 将其分为两半; 然后通过检查f ( 0 x ) 与f (a)是否同号来判断根的位置(见图1)。
如此反复二分, 即可得出一系列的有根区间; 其中,每个区间都是前一个区间的一半。当K→∞时, 该区间的大小趋近于零, 其值便为所求方程f (x) = 0 的根。由此可见, 二分法算法简单, 在允许的误差范围内通过有限次的计算,总能求得方程在该有根区间的根。
二分法求根算法
计算f(x)=0 的一般计算步骤如下
step1 输入求根区间[a,b]和误差控制量ε 定义函数f(x)。
IF f(a) f(b)〈0 〉THEN 做step2
ELSE 退出选用其他求根方法
step 2 WHILE |a-b|>ε
计算中点x=(a+b)/2 以及f(x)的值;分情况处理
| f(x)|〈ε 停止计算x =x,转向step4
f(a) f(x)<0 修正区间[a,x]->[a,b]
f(x) f(b)<0: 修正区间[x,b]->[a,b]
ENDWHILE
step 3: x =(a+b)/2。
Step 4:输出近似根x 。
二分法的算法简单 然而 若f(x)在[a,b]上有几个零点时 只能算出其中一个零点 另一方面 即使f(x)在[a,b]上有零点?.也未必有f(a) f(b)<0。这就限制了二分法的使用范围。二分法只能计算方程f(x)=0 的实根。
迭代法
迭代法的局部收敛性及收敛的阶
一种迭代过程，只有具备了收敛性，才能表明其迭代的有效性，同时还需要考察其迭代过程的收敛速度[3]，即其在接近收敛的过程中迭代误差的下降速度。迭代计算过程不收敛，可能是因为迭代格式本身构造不成功，那么算法必须重新构造，也可能是初值选择不当 这时往往可通过调整初值解决
牛顿迭代法
设r是f(x) = 0的根，选取x0作为r初始近似值，过点
（x0,f(x0)）做曲线y = f(x)的切线L，L的方程为y =
f(x0)+f'(x0)(x-x0)，求出L与x轴交点的横坐标 x1 =
x0-f(x0)/f'(x0)，称x1为r的一次近似值。过点（x1,f(x1)）做曲线y = f(x)的切线，并求该切线与x轴交点的横坐标 x2 = x1-f(x1)/f'(x1)，称x2为r的二次近似值。重复以上过程，得r的近似值序列，其中x(n+1)=x(n)－f(x(n))/f'(x(n))，称为r 的n+1次近似值，上式称为牛顿迭代公式。
解非线性方程f(x)=0的牛顿法是把非线性方程线性化的一种近似方法。把f(x)在x0点附近展开成泰勒级数 f(x) =
f(x0)+(x－x0)f'(x0)+(x－x0)^2*f''(x0)/2! +… 取其线性部分，作为非线性方程f(x) = 0的近似方程，即泰勒展开的前两项，则有f(x0)+f'(x0)(x－x0)=0 设f'(x0)≠0则其解为x1=x0－f(x0)/f'(x0) 这样，得到牛顿法的一个迭代序列：x(n+1)=x(n)－f(x(n))/f'(x(n))。
军人在进攻时常采用交替掩护进攻的方式，若在数轴上的点表示A，B两人的位置，规定在前面的数大于后面的数，则是A>B，B>A交替出现。但现在假设军中有一个胆小鬼，同时大家又都很照顾他，每次冲锋都是让他跟在后面，每当前面的人占据一个新的位置，就把位置交给他，然后其他人再往前占领新的位置。也
就是A始终在B的前面，A向前迈进，B跟上，A把自己的位置交给B（即执行B = A操作），然后A 再前进占领新的位置，B再跟上……直到占领所有的阵地，前进结束。像这种两个数一前一后逐步向某个位置逼近的方法称之为迭代法。
迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。
利用迭代算法解决问题，需要做好以下三个方面的工作：
一、确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。
二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。
三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实
现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。
最经典的迭代算法是欧几里德算法，用于计算两个整数a,b 的最大公约数。其计算原理依赖于下面的定理：
定理：gcd(a, b) = gcd(b, a mod b)
证明：a可以表示成a = kb + r，则r = a mod b 。假设d 是a,b的一个公约数，则有 a%d==0, b%d==0，而r = a - kb，因此r%d==0 ，因此d是(b, a mod b)的公约数
同理，假设d 是(b, a mod b)的公约数，则 b%d==0 ,
r%d==0 ，但是a = kb +r ，因此d也是(a,b)的公约数。
因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证。
欧几里德算法就是根据这个原理来做的，欧几里德算法又叫辗转相除法，它是一个反复迭代执行，直到余数等于0停止的步骤，这实际上是一个循环结构。其算法用C语言描述为：int Gcd_2(int a, int b)// 欧几里德算法求a, b的最大公约数
{
if (a<=0 || b<=0) //预防错误
return 0;
int temp;
while (b > 0) //b总是表示较小的那个数，若不是则交换a，b的值
{
temp = a % b; //迭代关系式
a = b; //是那个胆小鬼，始终跟在b的后面
b = temp; //向前冲锋占领新的位置
}
return a;
}
从上面的程序我们可以看到a，b是迭代变量，迭代关系是temp = a % b; 根据迭代关系我们可以由旧值推出新值，然后循环执a = b; b = temp;直到迭代过程结束（余数为0）。在这里a好比那个胆小鬼，总是从b手中接过位置，而b则是那个努力向前冲的先锋。
还有一个很典型的例子是斐波那契(Fibonacci)数列。斐波那契数列为：0、1、1、2、3、5、8、13、21、…，即 fib(1)=0; fib(2)=1; fib(n)=fib(n-1)+fib(n-2) (当n>2时)。
在n>2时，fib(n)总可以由fib(n-1)和fib(n-2)得到，由旧值递推出新值，这是一个典型的迭代关系，所以我们可以考虑迭代算法。
int Fib(int n) //斐波那契(Fibonacci)数列
{
if (n < 1)//预防错误
return 0;
if (n == 1 || n == 2)//特殊值，无需迭代
return 1;
int f1 = 1, f2 = 1, fn;//迭代变量
int i;
for(i=3; i<=n; ++i)//用i的值来限制迭代的次数{
fn = f1 + f2; //迭代关系式
f1 = f2; //f1和f2迭代前进，其中f2在f1的前面f2 = fn;
}
return fn;
}
参考文献：
1.百度百科
2.豆丁网