1 非线性方程求根的基本方法
在现实中的许多问题中，如流体力学，弹性力学，电路和电力系统计算，非线性规划等众多领域，常常会遇到求解非线性方程的问题。 设有非线性方程：
f(x)?0 (1.1) 其中函数f(x)可以是超越函数，则其对应方程为超越方程如e5x?sinx。函数f(x)也可以是多项式函数，即
f(x)?anxn?an?1xn?1?????a1x?a 0其中an?0，则称方程（1.1）为n次代数方程。当n?1,2时，求根公式大家都是熟悉的，当n?3,4时。也可以在数学手册上查到根的公式和求法。然而当n?5时，就无法用加减乘除和根式等运算的一般公式来准确写出根的表达式，所以需要数值方法来解决这个问题。
对于代数方程有单根和重根的概念，这可推广到一半方程（1.1）.如果存在常数s使得f(x?)?0,则称s是方程（1.1）的根，又称x?是函数f(x)的零点。若f(x)能分解为
??xm)? f(x)?(x( x)其中?(x?)?0，则称x?是方程（1.1）的m重根和f(x)的m重零点。当m?1时，x?为方程（1.1）的单根和f(x)的单零点。
1.1 非线性方程求根
只有很少类型的非线性方程能解出根的解析表达式，对于大多数非线性方程，通常只能得到一定精度的近似解。一般情况下，多用迭代方法解决此类问题。
首先，要判断根是否存在：判断（1.1）是否有根，如果有，存在几个根？例如对多项式方程，n次方程就有n个根。
其次，确定跟的隔离：把有根区间分成较小的子区间，每个自取件或者有一个根或者没有根，这样可以将有根子区间内的任一点都可以看成该根的一个近似值；
最后，使根精确化：对根的某个初始值设法逐步细化，使之达到一定的精度要
1
求。
1.2 迭代法的基本思想
迭代法是一种逐步逼近的方法，其基本思想是利用迭代格式反复校正根的近似值，使之逐步精确化，直到满足精度要求为止。迭代的基本步骤有两步：首先提供根的估计值，称为迭代初值，然后利用迭代格式将初值逐步转换为满足精度要求的根。
设给定方程f(x)?0，将方程转换为与其等价的形式：
x??(x) （1.2） 这里的方程式隐式的，因此无法直接求出它的解。但是如果直接给出根的某个猜测值x0，将它带入式（1.2）的右端，即可求得x1??(x0)。然后，又可取x1作为猜测值，进一步得到x2??(x1)。如此反复计算。计算公式
,?0,1???,2 xk?1??(xk)k , （1.3）
称为迭代格式。此时得到的一个序列{xk}，称为迭代序列。如果确定的序列{xk}有极限x??limxk，则称迭代公式（1.3）收敛。这时极限值x?显然就是方程（1.2）的
k?0根。
上述迭代法的基本思想就是将隐式方程（1.2）归结为一组显式的计算公式（1.3），就是说，迭代的实质上是一个逐步逼近逐步显式化的过程。利用迭代法求解非线性方程（1.1）需要考虑以下几个问题：
（1）初始的近视根如何选取？
（2）迭代函数如何构造？迭代序列是否收敛？ （3）收敛速度如何？怎样进行误差分析？
1.3 二分法
如果在区间[a,b]上方程（1.1）至少有一个根，那就称[a,b]是方程f(x)?0的一个有根区间，例如，如果知道f(a)f(b)?0,由于f的连续性，可知[a,b]是一个有根区间，可以用一些x点上的函数值f(x)的符号来搜索有根区间。如果在[a,b]上方程有且只有一个根，那就把方程的根隔离出来了，这时候若能把有根区间不断缩小，
2
便可逐步得出根的近似值。
求根方法中最简单最直观的方法是二分法，定义如下
定义1.1 对于[a,b]上连续不断且f(a)f(b)?0的函数y?f(x)，通过不断的把函数 f(x)的零点所在的区间一分为二，是区间的两个端点逐步逼近零点，进而得到零点近似值的方法。
二分法的优点是计算过程简单，收敛性可保证，对函数性质要求低，只要求连续就可以了；它的缺点是计算出来的值收敛速度慢，不能求偶数重根，也不能求复根和虚根。特别是函数值f(ak),f(bk)(k?0,1,2,???)每次均以计算出来，但是没有利用上，只利用了它们的符号，显然是一种浪费。在此基础上人们改进了二分法，充分利用函数f(ak),f(bk)(k?0,1,2,???)的值求根称为试位法，收敛速度速度比二分法快乐许多。
1.4 不动点迭代法
在1.2中我们了解到迭代法的基本思想，我们可以通过不同的途径将方程（1.1）转变为等价方程（1.2）的形式。例如，令?(x)?x?f(x)或者?(x)?x?Af(x)，其中A为常数。函数?(x)与f(x)的定义域可能不相同，但要求它们在所要求的f(x)?0的解x?邻近都有定义。
定义1.2 为了了解方程（1.1）类似线性代数方程组迭代法的构造，把方程（1.1）变换为等价的方程（1.2）。其中?为迭代函数，利用方程（1.2）可以构造迭代公式（1.3），如果limxk?x?，则x?满足方程（1.2）。称x?是迭代函数，x?是函数?的
k?0一个不动点，它也就是方程（1.2）的一个根方法（1.3）被称为不动点迭代法。
用迭代法(1.3）求解f(x)?0，需要讨以下问题： （1）如何选取合适的迭代函数?(x)；
（2）迭代函数?(x)满足什么条件，迭代序列收敛到x?，收敛速度是多少； （3）怎样加速序列{xk}的收敛速度。
3
1.5 迭代法的收敛性
方程f(x)?0的转化形式不同（即迭代函数?(x)不同），随之建立的迭代格式迭代后得到的序列的收敛性也不同。这意味着，并非任意的等价变换后所建立的迭代格式都是收敛的。那么应该如何变换才能使所建立的迭代格式收敛呢？下面我们就来讨论下迭代格式的收敛性。
考虑在区间[a,b]上的迭代函数?(x)的收敛性。 定理1.1 设函数?(x)在区间[a,b]上连续，且满足： 1 映内性： ?x?[a,b]，?(x)?[a,b]；
2 压缩性：存在常数0?L?1，使得?(x1)??(x2)?Lx1?x2，其中L称为压缩系数（Lipschitz 系数）， 则
（1）函数?(x)在区间[a,b]存在唯一的不动点x?；
（2）对任意的初值x0?[a,b]，迭代格式（1.3）所产生的迭代序列一定收敛到x?； （3）误差的估计如下；
L x??x?xkk?x?k1， （1.4）
1?LLkx1?x0. （1.5） x?xk?1?L? 由定理1.1可以看出
xn?1?x?xn?x??L，即
xn?1?x??Lxn?x?.
因此参数L决定迭代速度，并且L的值越接近于0，迭代的收敛速度就越快。由定理1.1 可知，如果L已知，根据给定的精度便可以估计出迭代的次数。在实际操作中，L是难以确定的，运用起来很不方便，但是从（1.4）中可以看出：只要两次相邻的迭代值之差的绝对值充分小，就可以保证迭代值xk充分接近于x?。当L未知时，如果已知精度?，则迭代的终止准则为 xk?1?xk??.
4
在实际操作中，总是采用如下定理来判断迭代格式的收敛性。
定理1.2 将方程f(x)?0f(x)?0改写为x??(x)，如果?(x)在区间[a,b]上连续，且满足：
1 映内性：?x?[a,b]，?(x)?[a,b]；
2 ?x?[a,b]，??(x)存在，且??(x)?L?1，其中L为Lipschitz常数，与x1,x2无关，则迭代xn?1??(xn)收敛，且收敛到f(x)?0的解x?。
迭代法求根的一个显著的优点就是逻辑结构简单，并且只要保证相邻两次迭代值得偏差充分小，就可以保证迭代的收敛性，可以用xk?1?xk控制计算的精度。一般而言，使用迭代法求解的过程如下：
首先，选取初值x0和误差限?，构造方程f(x)?0的等价变换形式x??(x)； 其次，依据构造好的迭代格式x1??(x0)计算?(x0)；
最后，判断x1?x0??，如果成立则停止计算，x1即为方程的根；反之，令x1?x0重复低二第三步。
在上述算法中x0和x1分别代表每次迭代的初值和终值，?为误差限。如果收敛速度过慢则放弃，可以用最大迭代次数N来控制。
在定理1.1和定理1.2中我们讨论了迭代函数?(x)对任意的x0?[a,b]的收敛性，这可以说是在区间[a,b]上的全局收敛性。然而在使用是需要讨论迭代函数在整个区间上的映内性和压缩性，使用不便。另外，我们平时更想要知道的是迭代序列在迭代函数不动点附近的收敛性，即设法找到一个在不动点附近的初始根。这时如果迭代序列收敛则收敛的速度很快；如果迭代序列不收敛，则任何初始根都不会使迭代序列收敛。因此我们更需要讨论在不动点x?附近的收敛性，称之为局部收敛性。 定义1.3 设?在区间I上有不动点x?，若存在x?的一个邻域S?I，对任意的
x0?S，不动点迭代法（1.3）产生的序列{xk}?S，且{xk}收敛到x?，则称迭代法
（1.3）局部收敛。
定理1.3 设x?为?的不动点，??(x)在x?的某个邻域S上存在且连续，满足
5