在科学计算中常需要求解非线性方程。
即求函数的零点．非线性方程求解没有通用的解析方法，常采用数值求解算法．数值解法的基本思想是从给定的一个或几个初始近似值出发，按某种规律产生一个收敛的迭代序列，使它逐步逼近于方程(2.1)的某个解．本章介绍非线性方程实根的数值求解算法：二分法、简单迭代法、newton迭代法及其变形，并讨论它们的收敛性、收敛速度等．
一、实根的隔离。
定义2.1 设非线性方程(2.1)中的是连续函数．如果有使，则称为方程(2.
1)的根，或称为函数的零点；如果有，且在邻域内连续，，为正整数，则称为方程(2.1)的重根．当时，称为方程的单根．
非线性方程根的数值求解过程包含以下两步。
1) 用某种方法确定有根区间．称仅存在一个实根的有根区间为非线性方程的隔根区间，在有根区间或隔根区间上任意值为根的初始近似值；
2) 选用某种数值方法逐步提高根的精度，使之满足给定的精度要求．
对于第(1)步有时可以从问题的物理背景或其它信息判断出根的所在位置，特别是对于连续函数，也可以从两个端点函数值符号确定出有根区间．
当函数连续时，区间搜索法是一种有效的确定较小有根区间的实用方法，其具体做法如下。
设是方程(2.1)的一个较大有根区间，选择合适的步长，，．由左向右逐个计算，如果有，则区间就是方程的一个较小的有根区间．
一般情况下，只要步长足够小，就能把方程的更小的有根区间分离出来；如果有根区间足够小，例如区间长度小于给定的精度要求，则区间内任意一点可视为方程(2.1)的根的一个近似．
例2.1 确定出方程的一个有根区间．
解由知为上的单调递增函数，进而在内最多只有一个实根．经计算知，，所以在区间内有惟一实根．
如果希望将有根区间再缩小，可以取步长，在点，，计算出函数值的符号，最后可知区间内有一个实根．
二、二分法
二分法是求非线性方程实根近似值的最简单的方法．其基本思想是将有根区间分半，通过判别函数值的符号，逐步缩小有根区间，直到充分逼近方程的根，从而得到满足一定精度要求的根的近似值．
设在区间上连续，，且方程(2.1)在区间内有惟一实根．记，，中点将区间分为两个小区间和，计算函数值，根据如下3种情况确定新的有根区间：
1) 如果，则是所要求的根；
2) 如果，取新的有根区间；
3) 如果，取新的有根区间．
新有根区间的长度为原有根区间长度的一半．对有根区间施以同样的过程，即用中点将区间再分为两半，选取新的有根区间，并记为。
其长度为的一半(如图2.1所示)．
图2.1 二分法示意图。
重复上述过程，建立如下嵌套的区间序列。
其中每个区间的长度都是前一个区间长度的一半，因此的长度为。
由和，得。当时，显然，有．总结得到如下收敛定理：
定理2.1 设在隔根区间上连续，且，则由二分法产生的序列收敛于方程(2.1)在上的根，并且有误差估计。
设预先给定根的绝对误差限为，要求，只要成立，这样求得对分次数。
取为大于的最小整数．此时是方程(2.1)的满足精度要求的根近似值．
注：由于舍入误差和截断误差存在，利用浮点运算不可能精确计算函数值，二分法中的判断几乎不可能满足，取而代之为判断条件，其中为根近似值的函数值允许误差限．
总结以上内容，给出如下算法。
算法2.1 (二分法)
输入端点、根的绝对误差限、根近似值的函数值允许误差限；
输出近似解或失败信息；
step 1 用公式(2.3)计算最大迭代次数；
step 2 对循环执行step 3～5；
step 3 ，计算；
step 4 若，则输出，end；
step 5 若，则，否则．
例2.2 用二分法求在上的根的近似值，要求．
解由于在区间上，，，故在上有惟一实根．确定循环次数为，利用二分法计算结果见表2.1．
表2.1 二分法计算结果。
二分法具有如下特点。
1) 优点：计算简单，对函数的光滑性要求不高，只要它连续，且在两端的函数值异号，算法收敛就可以保证；
2) 缺点：只能求单实根和奇数重实根，收敛较慢，与为公比的等比级数相同．
当函数连续时，方程(2.1)的实重根可转换为的实单根．
一般在求方程根近似值时不单独使用二分法，而常用它为其它数值方法提供初值．
简单迭代法是求解非线性方程根的近似值的一类重要数值方法．本节将介绍简单迭代法的基本思想、收敛条件、收敛速度以及相应的加速算法．
一、简单迭代法的基本思想。
简单迭代法采用逐步逼近的过程建立非线性方程根的近似值．首先给出方程根的初始近似值，然后用所构造出的迭代公式反复校正上一步的近似值，直到满足预先给出的精度要求为止．
在给定的有根区间上，将方程(2.1)等价变形为。
在上选取作为初始近似值，用如下迭代公式。
建立序列．如果有，并且迭代函数在的邻域内连续，对式(2.5)两边取极限，得。
因而是(2.4)的根，从而也是(2.1)的根．称为迭代函数，所得序列为迭代序列．将这种求方程根近似值的方法称为简单迭代法，简称迭代法．
例2.3 试用方程的不同形式的变形建立迭代公式，并试求其在附近根的近似值．
解利用方程的变形建立如下4种迭代公式。
取初值，迭代计算，结果见表2.2．
表2.2 迭代法计算结果。
例2.3表明非线性方程的不同等价形式对应不同的迭代过程，从某一初值出发，有的迭代收敛快，有的收敛慢，甚至不收敛．那么迭代函数满足什么条件时才能保证迭代序列收敛？ 迭代序列的误差如何估计？
怎样才能建立收敛速度快的迭代公式？
定理2.2 若函数在区间上具有一阶连续导数，且满足条件。
对任意，有；
存在常数：，使得对任意有成立．
则。1) 方程在上有惟一实根。
2) 对任意，迭代公式(2.5)收敛，且。
3) 迭代公式(2.5)有误差估计式。
证明 (1)构造函数，由条件知，，因此在上至少存在一个实根，又由条件知当时，，所以在内存在惟一实根，即在内存在惟一实根，记为．
2) 由及条件知， ，并且有，，二者作差，并由微分中值定理得。
其中，介于与之间．结合条件，得。
反复递推，有。
因，故．3) 由式(2.10)得。从而。
又由于。
其中介于和之间．综合式(2.11)及式(2.12)得误差估计。
由式(2.12)反复递推，得。
并代入式(2.6)得误差估计。
4) 由式(2.9)得。
两端取极限，并注意到的连续性和(因为介于与之间)，得。
误差估计(2.6)称为后验误差估计，也称为误差渐进估计，误差估计(2.7)称为先验误差估计．定理2.
2条件成立时，对任意，迭代序列均收敛，故称定理2.2为全局收敛性定理．下面讨论邻近的收敛性，即局部收敛性．
定理2.3 设存在方程根的闭邻域以及小于的正数，使得连续且．则对任意，迭代收敛．
证明由在内连续，且有，则对任意，有。
由定理2.2知迭代过程对任意初值均收敛．
二、迭代法的收敛阶。
为刻画迭代法收敛速度的快慢，引进收敛序列的收敛阶概念．
数值分析第二章
第二章插值法。1 当时，求的二次插值多项式。解 则二次拉格朗日插值多项式为。2 给出的数值表。用线性插值及二次插值计算的近似值。解 由 知，若采用线性插值法计算即，则。若采用二次插值法计算时，3 给全的函数表，步长若函数表具有5位有效数字，研究用线性插值求近似值时的总误差界。解 求解近似值时，误差可...
数值分析第二章
列选主元lu分解法 function l,u,pv luex a luex lu factorization with partial pivoting synopsis l,u,pv luex a input a coefficient matrix output l lower triangul...
数值分析第二章作业
1.当，时，且。求的二次牛顿插值多项式 证明 2.当时，且求的牛顿插值多项式，并给出其差商型余项表达式。3.已知函数满足，求其三次牛顿插值多项式，并证明存在使得。4.已知，求的四次牛顿插值多项式，并给出其导数 假设函数的五阶导数存在 型余项表达式。5.设，为互异实数，是以其为节点的lagrange插...