数值方法第二章 非线性方程的近似解法

非线性微分方程的近似解法
非线性微分方程的近似解法有多种，比如准则近似法、加权法、谱正
则近似法、最小二乘法、Adomian分解法、拉格朗日-奥尔德尼法、局部
拟合法等等。

准则近似法是基于一组谐振函数和它们的线性组合构造近似解的方法。

加权法又称多项式拟合法，是一种优化方法，基于给定的一组观测数据，建立一个最优的函数拟合模型，以此解决数值求解的问题。

谱正则近似法是把离散的谱系数和给定的函数值满足最小二乘法引入
一组约束条件，可以由此求得一个接近给定函数的正弦级数的近似解。

最小二乘法是一种误差平方和函数的极小化最优化方法，可以用来求
解非线性方程组。

Adomian分解法是一种将非线性方程化为线性方程组来求解的方法。

拉格朗日-奥尔德尼法是一种最优化方法，常用于求解连续可微分的
非线性优化问题。

局部拟合法是一种在计算上求解非线性方程的方法，要求该方程的解
函数在有限个指定点上满足拟合条件。

第二章 方程求根在许多实际问题中，常常会遇到方程f(x)=0求解的问题。

当f(x)为一次多项式时，f(x)=0称为线性方程，否则称为非线性方程。

对于非线性方程，由于f(x)的多样性，求其根尚无一般的解析方法可以使用，因此研究非线性方程的数值解法是十分必要的。

法、迭代法、牛顿法及割线法。

这些方法均是知道根的初始近似值后，进一步把根精确化，直到达到所要求的 精度为止。

也即求非线性方程根的数值方法。

第一节 第一节 增值寻根法与二分法2.1.1 增值寻根法设非线性方程f(x)=0的根为*x ，增值寻根法的基本思想是，从初始值0x 开始，按规定 的一个初始步长h 来增值。

令 1n x +=n x +h(n=0,1,2，…)，同时计算f(1n x +)。

在增值的计算过程中可能遇到三种情形：(1) f(1n x +)=0，此时1n x +即为方 程的根*x 。

(2) f(n x )和f(1n x +)同符号。

这说明区间［n x , 1n x +］内无根。

(3) f(n x )和f(1n x +)异号，f(n x )·f(1n x +)＜0此时当f(x)在区间［n x , 1n x +］上连续时，方程f(x)=0在［n x , 1n x +］ 一定有根。

也即我们用增值寻根法找到了方程根的存在区间，n x 或1n x +均可以视为根的近似值。

下一步就是设法在该区间内寻找根 *x 更精确的近似值，为此再用增值寻根法 把n x 作为新的初始近似值，同时把步长缩小，例如选新步长1100h h =，这 样会得到区间长度更小的有根区间，从而也得到使f(x)n x ，作为*x 更 精确的近似值，若精度不够，可重复使用增值寻根法，直到有根区间的长度｜1n x +-n x ｜＜ε(ε为所要求的精度)为止。

此时f(n x )或f(1n x +)就可近似认为是零。

n x 或1n x +就是满足精度的方程的近似根（如图2-1）.2—1例1 用增值寻根法求方程f(x)=324x x +-10=0的有根区间。

数值分析非线性方程的数值解法数值分析是一种应用数学方法来分析和解决数学问题的领域。

非线性方程是数值分析中一类重要的问题，其解法包括了迭代法、牛顿法、割线法等。

本文将详细介绍这些数值解法及其原理和应用。

一、迭代法迭代法是解非线性方程的一种常用数值方法。

该方法的基本思想是通过不断迭代逼近方程的根，直到达到所需精度或满足停止准则为止。

迭代法的求根过程如下：1.选择适当的初始值x0。

2. 利用迭代公式xn+1 = g(xn)，计算下一个近似根。

3.重复步骤2，直到满足停止准则为止。

常用的迭代法有简单迭代法、弦截法和牛顿法。

简单迭代法的迭代公式为xn+1 = f(xn)，其中f(x)为原方程的一个改写形式。

该方法的收敛性要求函数f(x)在解附近有收敛性且导数在一个区间内收敛。

弦截法的迭代公式为xn+1 = xn - f(xn) * (xn-xn-1) / (f(xn)-f(xn-1))。

该方法通过连接两个点上的函数值的割线来逼近方程的根。

牛顿法的迭代公式为xn+1 = xn - f(xn) / f'(xn)，其中f'(x)为f(x)的导数。

该方法通过用切线来逼近方程的根。

二、牛顿法牛顿法是解非线性方程的一种常用迭代法。

该方法通过使用方程的导数来逼近方程的根。

迭代过程如下：1.选择适当的初始值x0。

2. 利用迭代公式xn+1 = xn - f(xn) / f'(xn)，计算下一个近似根。

3.重复步骤2，直到满足停止准则为止。

牛顿法的收敛速度较快，但要求方程的导数存在且不为0。

三、割线法割线法是解非线性方程的另一种常用迭代法。

该方法通过连接两个点上的函数值的割线来逼近方程的根。

迭代过程如下：1.选择适当的初始值x0和x12. 计算下一个近似根xn+1 = xn - f(xn) * (xn-xn-1) / (f(xn)-f(xn-1))。

3.重复步骤2，直到满足停止准则为止。

割线法的收敛速度介于简单迭代法和牛顿法之间。

非线性微分方程的近似解法一、泰勒级数方法泰勒级数方法可以将非线性微分方程转化为线性微分方程，从而获得其近似解。

该方法基于泰勒公式展开，将未知函数用其导数的级数表达式来逼近。

通过截取级数的前几项，可以得到方程的近似解。

这种方法的主要局限性在于，泰勒级数的收敛范围很小，因此只能用于小范围的近似计算。

二、微扰解法微扰解法是一种将非线性微分方程转化为近似线性微分方程的方法。

该方法假设非线性微分方程的解可以写成一个级数形式，其中级数中的项按照幂次递减。

然后，通过求解线性微分方程的级数项，可以得到原方程的近似解。

这种方法非常适用于具有小参数的问题。

三、极限环法极限环法是一种通过运用线性微分方程的解来解决非线性微分方程的方法。

该方法假设非线性微分方程的解为两个相近解的线性组合。

然后，通过运用极限环理论，可以将原方程转化为一系列线性微分方程的组合，进而求得方程的近似解。

四、变分法变分法是一种通过设定未知函数的一些形式，将非线性微分方程转化为一个变分问题的方法。

通过求解该变分问题，可以得到非线性微分方程的近似解。

变分法的核心思想是将问题转化为求一个泛函的驻定问题，通过变分法的原理求解该泛函，进而得到近似解。

五、数值解法数值解法是一种通过数值计算的方法，来近似求解非线性微分方程。

这种方法将微分方程离散化，将其转化为一个差分方程，通过计算机进行迭代运算，最终得到方程的近似解。

数值解法的优点在于适用范围广，对各种类型的非线性微分方程都适用，但精度较低。

总结起来，非线性微分方程的近似解法有泰勒级数方法、微扰解法、极限环法、变分法和数值解法等。

在实际应用中，我们可以根据具体情况选择合适的方法来解决非线性微分方程问题。

实用文档《数值计算方法》复习资料第一章数值计算方法与误差分析第二章非线性方程的数值解法第三章线性方程组的数值解法第四章插值与曲线拟合第五章数值积分与数值微分第六章常微分方程的数值解法自测题课程的性质与任务数值计算方法是一门应用性很强的基础课，在学习高等数学，线性代数和算法语言的基础上，通过本课程的学习及上机实习、使学生正确理解有关的基本概念和理论，掌握常用的基本数值方法，培养应用计算机从事科学与工程计算的能力，为以后的学习及应用打下良好基础。

第一章数值计算方法与误差分析一考核知识点误差的来源类型；绝对误差和绝对误差限，相对误差和相对误差限，有效数字；绝对误差的传播。

二复习要求1.知道产生误差的主要来源。

2.了解绝对误差和绝对误差限、相对误差和相对误差限和有效数字等概念以及它们之间的关系。

3.知道四则运算中的误差传播公式。

实用文档三例题例 1 设x*= =3.1415926⋯近似值 x=3.14 ＝ 0.314× 101,即 m=1，它的绝对误差是－ 0.001 592 6 ，⋯有即 n=3，故 x=3.14 有 3 位有效数字 .x=3.14准确到小数点后第 2 位 .又近似值 x=3.1416，它的绝对误差是0.0000074 ⋯，有即 m=1,n＝ 5， x=3.1416 有 5 位有效数字 .而近似值x=3.1415，它的绝对误差是0.0000926 ⋯，有即 m=1,n＝ 4， x=3.1415 有 4 位有效数字 .这就是说某数有s 位数，若末位数字是四舍五入得到的，那么该数有s 位有效数字；例 2指出下列各数具有几位有效数字，及其绝对误差限和相对误差限：2.000 4－0.002 009 0009 000.00解因为 x1=2.000 4＝ 0.200 04× 101, 它的绝对误差限 0.000 05=0.5 × 10 1―5，即m=1,n=5, 故 x=2.000 4 有 5 位有效数字 . a1=2，相对误差限x2=－ 0.002 00，绝对误差限0.000 005，因为 m=－2，n=3 ，x2=－ 0.002 00 有 3 位有效数字 . a1=2 ，相对误差限r ==0.002 5实用文档x3=9 000 ，绝对误差限为0.5× 100，因为 m=4, n=4, x3=9 000 有 4 位有效数字， a=9 ，相对误差限r＝＝ 0.000 056x4=9 000.00 ，绝对误差限0.005，因为 m=4， n=6， x4=9 000.00 有 6 位有效数字，相对误差限为r＝＝ 0.000 000 56由 x3与 x4可以看到小数点之后的0，不是可有可无的，它是有实际意义的.例 3 ln2=0.69314718⋯，精确到10－3的近似值是多少？解精确到 10－3＝ 0.001，意旨两个近似值x1,x2满足，由于近似值都是四舍五入得到的，要求满足，近似值的绝对误差限应是＝0.0005,故至少要保留小数点后三位才可以。

第二章 非线性方程数值解法在科学计算中常需要求解非线性方程()0f x = (2.1)即求函数()f x 的零点．非线性方程求解没有通用的解析方法，常采用数值求解算法．数值解法的基本思想是从给定的一个或几个初始近似值出发，按某种规律产生一个收敛的迭代序列0{}k k x +∞=，使它逐步逼近于方程(2.1)的某个解．本章介绍非线性方程实根的数值求解算法：二分法、简单迭代法、Newton 迭代法及其变形，并讨论它们的收敛性、收敛速度等．§2.1 二分法一、实根的隔离定义 2.1 设非线性方程(2.1)中的()f x 是连续函数．如果有*x 使*()0f x =，则称*x 为方程(2.1)的根，或称为函数()f x 的零点；如果有*()()()m f x x x g x =-，且()g x 在*x 邻域内连续，*()0g x ≠，m 为正整数，则称*x 为方程(2.1)的m 重根．当1m =时，称*x 为方程的单根．非线性方程根的数值求解过程包含以下两步(1) 用某种方法确定有根区间．称仅存在一个实根的有根区间为非线性方程的隔根区间，在有根区间或隔根区间上任意值为根的初始近似值；(2) 选用某种数值方法逐步提高根的精度，使之满足给定的精度要求．对于第(1)步有时可以从问题的物理背景或其它信息判断出根的所在位置，特别是对于连续函数()f x ，也可以从两个端点函数值符号确定出有根区间．当函数()f x 连续时，区间搜索法是一种有效的确定较小有根区间的实用方法，其具体做法如下设[,]a b 是方程(2.1)的一个较大有根区间，选择合适的步长()/h b a n =-，k x a kh =+，(0,1,,)k n =．由左向右逐个计算()k f x ，如果有1()()0k k f x f x +<，则区间1[,]k k x x +就是方程的一个较小的有根区间．一般情况下，只要步长h 足够小，就能把方程的更小的有根区间分离出来；如果有根区间足够小，例如区间长度小于给定的精度要求，则区间内任意一点可视为方程(2.1)的根的一个近似．例2.1 确定出方程32()3430f x x x x =-+-=的一个有根区间．解 由22()3643(1)10f x x x x '=-+=-+>知()f x 为(,)-∞∞上的单调递增函数，进而()f x 在(,)-∞∞内最多只有一个实根．经计算知(0)0f <，(2)0f >，所以()0f x =在区间[0,2]内有惟一实根．如果希望将有根区间再缩小，可以取步长0.5h =，在点0.5x =，1x =， 1.5x =计算出函数值的符号，最后可知区间[1.5,2]内有一个实根． 二、二分法二分法是求非线性方程实根近似值的最简单的方法．其基本思想是将有根区间分半，通过判别函数值的符号，逐步缩小有根区间，直到充分逼近方程的根，从而得到满足一定精度要求的根的近似值．设()f x 在区间[,]a b 上连续，()()0f a f b <，且方程(2.1)在区间(,)a b 内有惟一实根*x ．记1a a =，1b b =，中点111()/2x a b =+将区间11[,]a b 分为两个小区间11[,]a x 和11[,]x b ，计算函数值1()f x ，根据如下3种情况确定新的有根区间：(1) 如果1()0f x =，则1x 是所要求的根；(2) 如果11()()0f a f x <，取新的有根区间2211[,][,]a b a x =； (3) 如果11()()0f x f b <，取新的有根区间2211[,][,]a b x b =．新有根区间22[,]a b 的长度为原有根区间11[,]a b 长度的一半．对有根区间22[,]a b 施以同样的过程，即用中点222()/2x a b =+将区间22[,]a b 再分为两半，选取新的有根区间，并记为33[,]a b ，其长度为22[,]a b 的一半(如图2.1所示)．图2.1 二分法示意图重复上述过程，建立如下嵌套的区间序列1122[,][,][,][,]k k a b a b a b a b =⊃⊃⊃⊃其中每个区间的长度都是前一个区间长度的一半，因此[,]k k a b 的长度为11()2k k k b a b a --=-由*[,]k k x a b ∈和()/2k k k x a b =+，得*11()()22k k k k x x b a b a -≤-=- 当k →∞时，显然，有*k x x →．总结得到如下收敛定理：定理2.1 设()f x 在隔根区间[,]a b 上连续，且()()0f a f b <，则由二分法产生的序列0{}k k x +∞=收敛于方程(2.1)在[,]a b 上的根*x ，并且有误差估计*1()(1,2,)2k kx x b a k -≤-= (2.2) 设预先给定根*x 的绝对误差限为ε，要求*k x x ε-≤，只要1()2k b a ε-≤成立，这样求得对分次数ln()ln ln 2b a k ε--≥． (2.3)取k 为大于(ln()ln )/ln 2b a ε--的最小整数．此时k x 是方程(2.1)的满足精度要求的根近似值．注：由于舍入误差和截断误差存在，利用浮点运算不可能精确计算函数值，二分法中的判断()0k f x =几乎不可能满足，取而代之为判断条件0()k f x ε<，其中0ε为根近似值的函数值允许误差限．总结以上内容，给出如下算法 算法2.1 (二分法)输入 端点,a b 、根的绝对误差限ε、根近似值的函数值允许误差限0ε； 输出 近似解c 或失败信息；Step 1 用公式(2.3)计算最大迭代次数k ； Step 2 对1,,n k =循环执行Step 3～5； Step 3 ()/2c a b =+，计算()f c ；Step 4 若0()f c ε<，则输出c ，end ；Step 5 若()()0f c f b <，则a c =，否则b c =．例 2.2 用二分法求32()4100f x x x =+-=在[1,2]上的根*x 的近似值，要求*31102k x x --<⨯． 解 由于在区间[1,2]上，(1)5f =-，(2)14f =，2()38(38)0f x x x x x '=+=+>，故()0f x =在[1,2]上有惟一实根*x ．确定循环次数为11k =，利用二分法计算结果见表2.1．二分法具有如下特点(1) 优点：计算简单，对函数()f x 的光滑性要求不高，只要它连续，且在两端的函数值异号，算法收敛就可以保证；(2) 缺点：只能求单实根和奇数重实根，收敛较慢，与1/2为公比的等比级数相同． 当函数()f x '连续时，方程(2.1)的实重根可转换为()0()f x f x ='的实单根． 一般在求方程根近似值时不单独使用二分法，而常用它为其它数值方法提供初值．§2.2 简单迭代法简单迭代法是求解非线性方程根的近似值的一类重要数值方法．本节将介绍简单迭代法的基本思想、收敛条件、收敛速度以及相应的加速算法． 一、简单迭代法的基本思想简单迭代法采用逐步逼近的过程建立非线性方程根的近似值．首先给出方程根的初始近似值，然后用所构造出的迭代公式反复校正上一步的近似值，直到满足预先给出的精度要求为止．在给定的有根区间[,]a b 上，将方程(2.1)等价变形为()x x ϕ= (2.4)在[,]a b 上选取0x 作为初始近似值，用如下迭代公式1()k k x x ϕ+= (0,1,2,k =) (2.5)建立序列0{}k k x +∞=．如果有*lim k k x x →∞=，并且迭代函数()x ϕ在*x 的邻域内连续，对式(2.5)两边取极限，得**()x x ϕ=因而*x 是(2.4)的根，从而也是(2.1)的根．称()x ϕ为迭代函数，所得序列0{}k k x +∞=为迭代序列．将这种求方程根近似值的方法称为简单迭代法，简称迭代法．例2.3 试用方程3()10f x x x =--=的不同形式的变形建立迭代公式，并试求其在1.5附近根的近似值．解 利用方程的变形建立如下4种迭代公式(1) 1k x +=，(2) 311k k x x +=-(3) 1k x += (4) 3112k k k x x x ++-=取初值0 1.5x =，迭代计算，结果见表2.2．例 2.3表明非线性方程的不同等价形式对应不同的迭代过程，从某一初值出发，有的迭代收敛快，有的收敛慢，甚至不收敛．那么迭代函数()x ϕ满足什么条件时才能保证迭代序列收敛? 迭代序列0{}k k x +∞=的误差如何估计? 怎样才能建立收敛速度快的迭代公式?定理2.2 若函数()x ϕ在区间[,]a b 上具有一阶连续导数，且满足条件 ① 对任意[,]x a b ∈，有()[,]x a b ϕ∈；② 存在常数L ：01L <<，使得对任意[,]x a b ∈有()x L ϕ'≤成立．则(1) 方程()x x ϕ=在[,]a b 上有惟一实根*x(2) 对任意0[,]x a b ∈，迭代公式(2.5)收敛，且*lim k k x x →∞= (3) 迭代公式(2.5)有误差估计式*11k k k Lx x x x L--≤-- (2.6)*101kk L x x x x L-≤-- (2.7)(4) **1*lim ()k k kx x x x x ϕ+→∞-'=- (2.8) 证明 (1)构造函数()()g x x x ϕ=-，由条件①知()()0g a a a ϕ=-≤，()()0g b b b ϕ=-≥，因此()0g x =在[,]a b 上至少存在一个实根，又由条件②知当[,]x a b ∈时，()1()10g x x L ϕ''=-≥->，所以()0g x =在[,]a b 内存在惟一实根，即()x x ϕ=在[,]a b 内存在惟一实根，记为*x ．(2) 由0[,]x a b ∈及条件①知，[,]k x a b ∈(1,2,)k =，并且有1()k k x x ϕ+=，**()x x ϕ=，二者作差，并由微分中值定理得***1()()()()k k k k x x x x x x ϕϕϕξ+'-=-=- (1,2,)k = (2.9) 其中，k ξ介于k x 与*x 之间．结合条件②，得**1k k x x L x x +-≤- (1,2,)k = (2.10)反复递推，有**2*1*1100k k k k x x L x x L x x L x x ++-≤-≤-≤-≤≤-， (1,2,)k = 因01L <<，故*lim k k x x →∞=． (3) 由式(2.10)得***1111*1k k k k k k k k k k x x x x x x x x x x x x L x x+++++-=-+-≤-+-≤-+-从而*111k k kx x x x L+-≤-- (2.11)又由于111()()()()k k k k k k k x x x x x x ϕϕϕη+--'-=-=-1k k L x x -≤- (1,2,)k =(2.12)其中k η介于k x 和1k x -之间．综合式(2.11)及式(2.12)得误差估计*11k k k Lx x x x L--≤--由式(2.12)反复递推，得111210k k k k k x x L x x L x x -----≤-≤≤-并代入式(2.6)得误差估计*11011kk k k L L x x x x x x L L--≤-≤--- (1,2,)k =(4) 由式(2.9)得*1*()k k k x x x x ϕξ+-'=-两端取极限，并注意到()x ϕ'的连续性和*lim k k x ξ→∞=(因为k ξ介于*x 与k x 之间)，得 **1*lim ()k k kx x x x x ϕ+→∞-'=-． 误差估计(2.6)称为后验误差估计，也称为误差渐进估计，误差估计(2.7)称为先验误差估计．定理 2.2条件成立时，对任意0[,]x a b ∈，迭代序列均收敛，故称定理2.2为全局收敛性定理．下面讨论*x 邻近的收敛性，即局部收敛性．定理 2.3 设存在方程()x x ϕ=根*x 的闭邻域***(,)[,](0)U x x x δδδδ=-+>以及小于1的正数L ，使得()x ϕ'连续且()1x L ϕ'≤<．则对任意*0(,)x U x δ∈，迭代1()k k x x ϕ+=收敛．证明 由()x ϕ'在*(,)U x δ内连续，且有()1x L ϕ'≤<，则对任意*(,)x U x δ∈，有****()()()()x x x x x x L ϕϕϕϕηδδ'-=-=-≤<由定理2.2知迭代过程1()k k x x ϕ+=对任意初值*0(,)x U x δ∈均收敛． 二、迭代法的收敛阶为刻画迭代法收敛速度的快慢，引进收敛序列的收敛阶概念．定义2.2 设迭代序列0{}k k x +∞=收敛到*x ，记*k k e x x =-，如果存在常数0c >和实数1p ≥，使得1limk pk ke c e +→∞= (2.13)则称序列0{}k k x +∞=是p 阶收敛的．当1p =时，称0{}k k x +∞=为线性收敛的，此时要求01c <<；1p >为超线性收敛．p 越大，序列0{}k k x +∞=收敛到*x 越快．c 称为渐进常数，c 越小，收敛越快．所以迭代法的收敛阶是对迭代法收敛速度的一种度量． 显然，由定理 2.2(4)知，当*()0x ϕ'≠时简单迭代法线性收敛，渐进常数*()c x ϕ'=．算法2.2 (简单迭代法)输入 初始值0x 、容许误差ε； 输出 近似解1x 或失败信息；Step 1 对1,,n m =循环执行Step 2～3； Step 2 10()x x ϕ=；Step 3 若10x x ε-<，则输出1x ，end ；否则01x x =，转向Step2．例2.4 求方程()2lg 70f x x x =--=的最大实根的近似值，要求绝对误差不超过31102-⨯．解 (1)确定有根区间．方程等价形式为27lg x x -=作函数27y x =-和lg y x =的图形，如图 2.2所示，知方程的最大实根在区间[3,4]内．(2)建立迭代公式，判别收敛性．将方程等价变形为1(lg 7)2x x =+ 迭代函数1()(lg 7)2x x ϕ=+，迭代公式11(lg 7)2k k x x +=+． 由11()02ln10x x ϕ'=⋅>，[3,4]x ∈，知()x ϕ在区间[3,4]内仅有一根．又(3) 3.74ϕ≈，(4) 3.80ϕ≈，所以，当[3,4]x ∈时，()[3,4]x ϕ∈．图2.2 函数27y x =-和lg y x =的图形因为 3.54max ()(3)0.07x L x ϕϕ≤≤''==≈，所以对于一切[3,4]x ∈有 ()(3)0.071x ϕϕ''≤≈<由定理2.2知，迭代法收敛．(3) 迭代计算．取0 4.0x =，有1=3.801030x ，2=3.789951x ，3=3.789317x ，4=3.789280x 因为343110 2x x --≤⨯，所以方程的最大根*4 3.789280x x ≈=． 三、迭代法的加速对于收敛的迭代序列，理论上迭代次数足够多时，就可以使计算结果满足任意给定的精度要求．但在应用中，有的迭代过程收敛极为缓慢，计算量很大，因此研究迭代格式的加速方法是非常必要的． 1. 线性收敛序列的Aitken 加速法设0{}k k x +∞=是一个线性收敛的序列，极限为*x ．即有小于1的正数c 使得*1*limk k k x x c x x +→∞-=-由于它线性收敛，误差减少的速度较慢，值得采用加速技术．下面介绍Aitken 加速法．对充分大的k ，有*1*,k k x x c x x +-≈- *2*1k k x x c x x ++-≈- 由上面两式得**12**1k k k k x x x x x x x x +++--≈--解得22*2112121()22k k k k k k k k k k k k x x x x x x x x x x x x x +++++++--≈=--+-+利用上式右端的值可定义另一序列0{}k k y +∞=，即得Aitken 加速公式2121()2k k k k k k kx x y x x x x +++-=--+ (2.14)它仍然收敛到*x ，但收敛速度更快．证明请参考文献[19]．2. Steffensen 迭代法Aitken 加速方案是对任意线性收敛序列0{}k k x +∞=构建的，并不限定0{}k k x +∞=如何获得．将Aitken 加速方法用于简单迭代法产生迭代序列时，得到著名的Steffensen 迭代法，具体迭代公式如下21()()(0,1,2,)()2k k k kk s x t s k s x x x t s x ϕϕ+=⎧⎪==⎪⎨-⎪=-⎪-+⎩(2.15)或者直接写成21(())(())2()k k k k k k kx x x x x x x ϕϕϕϕ+-=--+ (0,1,2,)k =可以证明Steffensen 迭代法在一定的条件下与原简单迭代法的迭代序列具有相同的极限，但Steffensen 迭代法收敛速度更快，可以达到二阶收敛．证明请参考文献[19]．例 2.5 对例 2.3用Steffensen 迭代法求方程根的近似值，要求811102k k x x -+-<⨯． 解 (1) 简单迭代法 将原方程化成12(10/(4))x x =+，建立迭代公式121104k k x x +⎛⎫= ⎪+⎝⎭ 易验证该迭代公式在区间[1,2]上满足定理2.2的条件，产生的迭代序列收敛．(2) Steffensen 迭代法 加速公式为12122110410(0,1,2,)4()2k k k k k s x t k s s x x x t s x +⎧⎛⎫⎪= ⎪+⎪⎝⎭⎪⎪⎛⎫⎨==⎪⎪+⎝⎭⎪-⎪=-⎪-+⎩(1) 取初值0 1.5x =，简单迭代法和Steffensen 迭代法计算结果见表2.3． 注意：Steffensen 迭代法每一迭代步的计算量大约是原简单迭代法计算量的两倍．§2.3 Newton 迭代法Newton 迭代法是求解非线性方程根的近似值的一种重要数值方法．其基本思想是将非线性函数()f x 逐步线性化，从而将非线性方程(2.1)近似地转化为一系列线性方程来求解．下面讨论其格式的构造、收敛性、收敛速度以及有关变形． 一、Newton 迭代法的构造设k x 是方程(2.1)的某根的一个近似值，将函数()f x 在点k x 处作Taylor 展开2()()()()()()2!k k k k f f x f x f x x x x x ξ'''=+-+- 取前两项近似代替()f x ，即用线性方程()()()0k k k f x f x x x '+-=近似非线性方程(2.1)．设()0k f x '≠，则用线性方程的根作为非线性方程根的新近似值，即定义1()()k k k k f x x x f x +=-' (2.16) 上式即是著名的Newton 迭代公式．它也是一种简单迭代法，其中迭代函数21()()()f x x x f x ϕ=-' Newton 迭代法具有明显的几何意义(如图2.3所示)．方程()0f x =的根*x 即为曲线()y f x =与x 轴的交点的横坐标．设k x 是*x 的某个近似值，过曲线()y f x =上相应的点(,())k k x f x 作切线，其方程为()()()k k k x f x y f x x '+-=它与x 轴的交点横坐标就是1k x +．只要初值0x 取得充分靠近根*x ，序列0{}k k x ∞=就会很快收敛到*x ．所以Newton 迭代法也称为切线法．图2.3 Newton 迭代法的几何意义二、收敛性定理2.4 设*x 是方程(2.1)的单根，在*x 的邻域上()f x ''连续且*()0f x '≠．则存在0δ>，当***0(,)[,]x U x x x δδδ∈=-+时，Newton 法产生的序列0{}k k x ∞=至少二阶收敛．证明 (1) Newton 法迭代函数的导数为2()()()[()]f x f x x f x ϕ'''='显然，()x ϕ'在*x 邻域上连续．又*()0x ϕ'=，一定存在*x 的某个δ闭邻域*(,)U x δ，当*(,)x U x δ∈时，有()1x L ϕ'≤< 从而Newton 法产生的序列0{}k k x ∞=收敛．(2)将()f x 在k x 处作一阶Taylor 展开***210()()()()()()2!k k k k k f x f x f x x x f x x ξ'''==+-+- (2.17) 其中k ξ介于*x 与k x 之间．又由Newton 迭代公式有10()()()k k k k f x f x x x +'=+- (2.18)式(2.17)与式(2.18)相减22**21()()2()k k k k f x x x x f x ξ+''-=--' 从而**1*2*()lim 0()2()k k kx x f x x x f x +→∞''-=≠'- (2.19) 由迭代法收敛阶的定义知，Newton 迭代法至少具有二阶收敛速度．上述定理给出了Newton 法局部收敛性，它对初值要求较高，初值必须充分靠近方程根时才可能收敛，因此在实际应用Newton 法时，常常需要试着寻找合适的初值．下面的定理则给出Newton 法在有根区间上全局收敛的一个充分条件．定理2.5 设*x 是方程(2.1)在区间[,]a b 上的根且()f x ''在[,]a b 上存在，如果(1) 对于任意[,]x a b ∈有，()0f x '≠()0f x ''≠； (2) 选取初值0[,]x a b ∈，使00()()0f x f x ''>．则Newton 法产生的迭代序列0{}k k x ∞=单调收敛于*x ，并具有二阶收敛速度．(a)(b)(c) (d)23图2.4 定理2.5的几何解释证明 满足定理条件(1)共有4种情形，如图2.4所示．下面仅以图2.4(a )情况进行证明，此时满足对任意[,]x a b ∈有，()0f x '>，()0f x ''>，初值*0x x >．首先用数学归纳法证明0{}k k x ∞=有下界*x ． 当0k =时，*0x x >成立．假设k n =时，不等式*n x x >成立． 将*()f x 在n x 处作一阶Taylor 展开，得***2*()()()()()()0,(,)2!n n n n n n n f f x f x f x x x x x x x ξξ'''=+-+-=∈ 于是**2()()()()2()n n n n n n f x f x x x x f x f x ξ''=---'' 又由Newton 迭代公式，有**21()()2()n n n n f x x x x f x ξ+''=--' (2.20) 式(2.20)右端的第二项大于零，因此*1n x x +>．由数学归纳法知*k x x >，(0,1,2,)k =． 其次证明0{}k k x ∞=单调递减．由()0f x '>，*k x x >，*()0f x =知，()0k f x >，()0k f x '>，于是Newton 迭代公式(2.16)的第二项大于零，从而1k k x x +>故迭代序列0{}k k x ∞=单调减少．序列0{}k k x ∞=单调减少有下界*x ，它必有极限，记为ˆx ，它满足*0ˆx x x ≤<，进而有ˆ[,]xa b ∈．对1()()k k k k f x x x f x +=-'两端取极限，并利用()f x ，()f x '的连续性，得ˆ()f x=0．结合函数()f x 在[,]a b 上的单调性知*ˆx x =． 因此，Newton 法产生的迭代序列0{}k k x ∞=单调收敛于*x ，利用式(2.20)及式(2.19)知该Newton 迭代序列二阶收敛．算法2.3 (Newton 迭代法)输入 初始近似值0x 、 容许误差ε； 输出 近似解1x 或失败信息；Step 1 对1,,n m =循环执行Step 2～3； Step 2 1000()/()x x f x f x '=-；Step 3 若10x x ε-<，则输出1x ，end ；否则01x x =，转向step2．例 2.6 利用非线性方程230x -=的Newton的近似值，使得811102n n x x ---≤⨯，并证明对任意0(0,)x ∈+∞，该迭代法均收敛．24解 (1) 建立计算公式213213(0,1,2,)(2)k k k kk kk x x x x x x +-=-=+=其中00x >．(2) 判断收敛性在区间(0,)+∞内，()20f x x '=>，()20f x ''=>，当选取初值0)x ∈+∞时，存在足够大的M，使得0]x M ∈．由定理 2.5知，该迭代公式产生的迭代序列0{}k k x ∞=当选取初值0x ∈时，100013()2x x x x =+>> 这样，从1x 起，以后的(2)k x k ≥．故该迭代公式对任何初值00x >都收敛． (3) 取初值02x =，迭代计算，结果见表2.4．从表2.4可见，迭代4步后已经满足精度要求，精确解1.73205080756888=．三、Newton 迭代法的变形Newton 迭代格式构造容易，迭代收敛速度快，但对初值的选取比较敏感，要求初值充分接近真解，另外对重根收敛速度较慢（仅有线性收敛速度），而且当函数复杂时，导数计算工作量大．下面从不同的角度对Newton 法进行改进． 1 Newton 下山算法Newton 迭代法的收敛性依赖于初值0x 的选取，如果0x 偏离*x 较远，则Newton 迭代法有可能发散，从而在实际应用中选出较好的初值有一定难度，而Newton 下山法则是一种降低对初值要求的修正Newton 迭代法．方程(2.1)的根*x 也是()f x 的最小值点，若把()f x 看成()f x 在x 处的高度，则*x 是山谷的最低点．若序列0{}k k x ∞=满足单调性条件1()()k k f x f x +< (2.21) 则称0{}k k x ∞=为称为()f x 的下山序列．25在Newton 迭代法中引入下山因子(0,1]λ∈，将Newton 迭代公式(2.16)修正为1()(0,1,2,)()k k k k f x x x k f x λ+=-=' (2.22)适当选取下山因子λ，使得单调性条件(2.21)成立，即称为Newton 下山法．对下山因子的选取是逐步探索进行的．一般地，从1λ=开始反复将因子λ的值减半进行试算，一旦单调性条件(2.21)成立，则称“下山成功”；反之，如果在上述过程中找不到使条件(2.21)成立的下山因子λ，则称“下山失败”，这时可对k x 进行扰动或另选初值0x ，重新计算． 2 针对重根情形的加速算法假设*x 是方程的(2)m ≥重根，并且存在函数()g x ，使得有**()()(),()0m f x x x g x g x =-≠ (2.23)式中()g x 在*x 的某邻域内可导，则Newton 迭代函数***1**()()()()()()()()()()()()()()m m m f x x x g x x x g x x x x x f x m x x g x x x g x mg x x x g x ϕ---=-=-=-'''-+-+-，其导数在*x 处的值***********()()()()()()()()lim lim()1lim 11()()()x x x x x x x x g x x x x x mg x x x g x x x x x x g x m mg x x x g x ϕϕϕ→→→---'-+-'==--=-=-'+-所以*0()1x ϕ'<<，由定理2.2知Newton 迭代法此时只有线性收敛速度．为了加速收敛，可以采用如下两种方法方法一 令()()()f x x f x μ='，则*x 是方程()0x μ=的单根，将Newton 迭代函数修改为2()()()()()[()]()()x f x f x x x x x f x f x f x μψμ'=-=-''''- 因此有重根加速迭代公式12()()(0,1,2,)[()]()()k k k k k k k f x f x x x k f x f x f x +'=-='''- (2.24)它至少二阶收敛．方法二 将Newton 迭代函数改为()()()f x x x mf x ϕ=-' 这时*()0x ϕ'=，由此得到加速迭代公式1()(0,1,2,)()k k k k f x x x mk f x +=-=' (2.25)3 割线法26Newton 法每步需要计算导数值()k f x '．如果函数()f x 比较复杂时，导数的计算量比较大，此时使用Newton 法不方便．为了避免计算导数，可以改用平均变化率11()()k k k k f x f x x x ----替换Newton 迭代公式中的导数()k f x '，即使用如下公式111()()()()k k k k k k k f x x x x x f x f x +--=--- (2.26)上式即是割线法的迭代公式．割线法也具有明显的几何意义，如图2.5所示，依次用割线方程11()()()()k k k k k k f x f x y f x x x x x ---=+--的零点逐步近似曲线方程()0f x =的零点．割线法的收敛速度比Newton 法稍慢一点，可以证明其收敛阶约为1.618，证明请参考文献[4]．此外在每一步计算时需要前两步的信息1,k k x x -，即这种迭代法也是两步法．两步法在计算前需要提供两个初始值0x 与1x ．图2.5 割线法的几何意义例 2.7 已知方程42()440f x x x =-+=有一个二重根*x =Newton 法(2.16)和重根Newton 法(2.24)和(2.25)求其近似值，要求611102n n x x ---≤⨯解32()48,()128f x x x f x x '''=-=-，2()2()()4f x x x f x xμ-=='，2m =． 由Newton 法(2.16)得221232(0,1,2,)44k k k k k kx x x x k x x +-+=-==由Newton 法(2.24) 得272122(2)4(0,1,2,)22k k kk k k k x x x x x k x x +-=-==++由Newton 法(2.25) 得22122(0,1,2,)22k k k k k kx x x x k x x +-+=-==利用上述三种迭代格式，取初值0 1.4x =，分别计算，结果见表2.5．3 10知识结构图习 题1 用二分法求方程2sin 0x e x --=在区间[0,1]内根的近似值，精确到3位有效数字．2 方程340x x +-=在区间[1,2]内有一根，试用二分法求根的近似值，使其具有5位有效数字，至少应二分多少次．基本概念 （单根、重根、收敛阶）283 已知方程3210x x --=在0 1.5x =附近有根，试判断下列迭代格式的收敛性，并用收敛的迭代公式求方程根的近似值，比较迭代次数，要求311102n n x x ---≤⨯ (1) 1211n nx x +=+；(2) 1n x +=；(3) 1n x +=．4 设有方程(1) cos 0x x -=； (2) 230x x e -=确定区间[,]a b 及迭代函数()x ϕ，使1()k k x x ϕ+=对任意初值0[,]x a b ∈均收敛，并求各方程根的近似值，要求411102n n x x ---≤⨯．5 用迭代法求50.20x x --=的正根，要求准确到小数点后5位．6 用Steffensen 迭代法求方程31x x =-在区间[1,1.5]内的根，要求准确到小数点后4位．7 用Newton 法和割线法分别求方程3310x x --=在02x =附近根的近似值，并比较迭代次数(根的准确值为* 1.87938524x =，要求准确到小数点后4位)．8 Halley 法是加速Newton 法收敛的一个途径，Halley 法在()f x 的单根情况下可达到三阶收敛．Halley 迭代函数是12()()()()1()2(())f x f x f x g x x f x f x -''⎛⎫=-- ⎪''⎝⎭其中括号中的项是对Newton 迭代公式的改进．(1) 设函数2()f x x a =-，试给出Halley 迭代公式，取初值02x =求5的近似值，要求准确到小数点后10位．(2) 设函数3()32f x x x =-+，试给出Halley 迭代公式，取初值0 2.4x =计算其根的近似值．要求准确到小数点后10位．9试建立计算x Newton 迭代公式，并取初值01x =求611102n n x x ---≤⨯．10 （数值试验）用二分法和Newton 法求下列方程的惟一正根的近似值)0.50x x x =11 （数值试验）设投射体的运动方程为/15/15()9600(1)480()2400(1)t t y g t et x h t e --⎧==--⎪⎨==-⎪⎩１）求当撞击地面时的时间，精确到小数点后10位． ２）求水平飞行行程，精确到小数点后10位．12 （数值试验）试用Newton 法分别求解方程(1)0m x -=，(3,6,12m =)，观察迭代序列的收敛情形，分析所发生的现象．能否改造Newton 法使得它收敛更快．。

第二章非线性方程数值解法本章将讨论非线性方程0)(=x f (2.1)的数值解法，我们最为熟悉的非线性方程是一元二次方程02=++c bx ax也是最简单的非线性方程，其解为：aac b b x 2422,1-±-=但是对于(2.1)式中一般形式的非线性函数)(x f ，很难甚至不可能找到解析形式的解，通常只能用数值的方法求其近似数值解。

2.1 基本概念定义2.1如果*x 满足0)(*=x f ，则称*x 为方程(2.1)的解或根，也称*x 为函数)(x f 的零点或根。

用数值方法求解非线性方程的解，通常需要我们对其解有一个初步的估计，或知道其解的一个限定区间，因此确定包含解的区间将是我们首先需要解决的问题。

定义2.2若连续函数)(x f 在],[b a 内至少有一个根，则称],[b a 为有根区间，若在],[b a 内恰有一个根，则称],[b a 为隔根区间。

定理2.1 如果函数)(x f 在],[b a 上连续且0)()(<b f a f ，则)(x f 在),(b a 内至少有一个根，如果函数)(x f 另外满足在],[b a 上单调连续，则)(x f 在),(b a 内恰有一个根。

寻找隔根区间的通常方法有：图形法, 试探法。

例2.1 求033)(3=+-=x x x f 的有根区间。

解：作出函数)(x f y =的曲线图形图2.1 例2.1曲线示意图观察图中的曲线与X 轴的交点，可判断在区间)2,3(--之间方程有一个根。

例2.2 求033)(23=--+=x x x x f 的有根区间。

解：计算出)(x f 在一些点的值。

从表中可以看出1-=x 是一个根，区间)2,1(是一个有根区间。

如果在[-2,-1]之间把间隔再缩小到0.25我们可以得到下列表格在这个表格里我们又发现一个有根区间)5.1,75.1(--。

从此例中我们可以体会到试探法有可能漏掉某些有根区间，具有一定的局限性。