数值分析笔记期末复习.doc

第一章引论
1、数值分析研究对象：
数值分析是计算数学的一个主要部分，计算数学是数学科学的一个分支，它研究用计算机求解各种数学问题的数值计算方法及其理论与软件实现。
2、数值分析特点：
①面向计算机，要根据计算机特点设计切实可行的有效算法②有可靠的理论分析，能任意逼近并达到精度要求，对近似计算要保证收敛性和数值稳定性③要有好的计算复杂性，时间复杂性好是指节省时间，空间复杂性好是指节省存贮量，这也是建立算法要研究的问题。④要有数值试验，即任何一个算法除了从理论上要满足上述三点外，还要通过数值试验证明是行之有效的。
3、数值分析实质：
是以数学问题为研究对象，不像纯数学那样只研究数学本身的理论，而是把理论与计算紧密结合，着重研究数学问题的数值方法及理论。
4、用计算机解决科学计算问题通常经历以下过程
实际问题--数学模型（应用数学）--数值计算方法--程序设计--上机计算结果（计算数学）
5、误差来源及分类
1.模型误差——从实际问题中抽象出数学模型
2.观测误差——通过测量得到模型中参数的值 （通常根据测量工具的精度，可以知道
这类误差的上限值。）
3.截断误差——当数学模型得不到精确解时，要用数值计算方法求它的近似解，由此产
生的误差称为（截断误差）或（方法误差）
4.舍入误差——由于计算机字长有限，原始数据的输入及浮点数运算过程中都有可能产
生误差，这样产生的误差称为舍入误差
6、五个关于误差的概念
1.绝对误差
2.绝对误差限
3.相对误差
4.相对误差限
（1）定义：
设某一量的准确值为x，近似值为x*，则x*与x之差叫做近似值x*的绝对误差(简称误差)，记为
（2）性质：
(1)绝对误差e(x*) 可正可负 (2) |e(x*) |的大小标志着x*的精确度 (3) 绝对误差e(x*) 未知
（3）判断：
绝对误差是误差的绝对值？（错）

（1）定义：
若指定一个适当小的正数，使则称为近似值 x* 的绝对误差限。(有时用表示近似值x*的精度或准确值的所在范围。
)
（2）性质：
(1)在实际问题中，绝对误差一般是有量纲的，绝对误差限也是有量纲的。
(2)绝对误差限是正的，有无穷多个【则比大的任意正数均是绝对误差
限】

（1）定义：
绝对误差与准确值之比称为x*的相对
误差。
（2）性质：
(1)相对误差是个无量纲量。值小者精度高。
(2)由于准确值x未知，故实际问题中，当 || 较小时，常取

（1）定义：
若指定一个适当小的正数 ，使则称为近似值 x*的相对误差限。
（2）性质：
当|较小时，可用下式计算

5.有效数字
（1）定义：若近似值x*的绝对误差限是某一位的半个单位，该位到x*的第一位非零数字一共有n位，则称近似值x*有n位有效数字，或说x*精确到该位。注意：近似值后面的零不能随便省去！
（2）例题：取x1*= 3作为π的近似值，则：一个有效数字
取 x2* =3.14 作为π的近似值，则：三个有效数字
取 x3* =3.1416作为π的近似值，则：五个有效数字
它们的误差都不超过末位数字的半个单位。
（3）性质：(1)有效数字越多，则绝对误差越小
(2)有效数字越多，则相对误差越小
有效数字的位数可刻画近似数的精确度！
6、一元函数的误差估计
问题：设y=f(x)，x的近似值为x*，则y的近似值 y*的误差如何计算？

故相应的误差限计算如下

7、二元函数的误差估计
问题：设y=f(x1, x2)， x1, x2的近似值为x1*, x2* ，则y的误差如何计算？

故绝对误差限为

8、多元函数的误差估计

9、加减乘除运算的误差估计

加法
减法
乘法
除法
绝对误差

绝对误差限

相对误差

相对误差限

10、算法的数值稳定性概念及运算
（1）定义：初始数据的误差或计算中的舍入误差在计算过程中的传播，因算法不同而异。一个算法，如果计算结果受误差的影响小，就称该算法具有较好的数值稳定性
11、设计算法的五个原则
(一) 要避免相近两数相减

(二) 要防止大数“吃掉”小数，注意保护重要数据

求和时从小到大相加，可使和的误差减小。若干数相加，采用绝对值较小者先加的算法，结果的相对误差限较小

(三) 注意简化计算步骤，减少运算次数，避免误差积累（秦九韶）

(四) 要避免绝对值小的数作除数

(五) 设法控制误差的传播
许多算法具有递推性。递推法运算过程较规律，但多次递推必然导致误差的积累。

第二章 逼近问题
1，函数逼近
1、插值问题： 求一条曲线严格通过数据点
2、曲线拟合问题： 求一条曲线在一定意义下靠近数据点
2，插值问题
1、定义：
求一个简单函数φ(x)作为f(x)的近似表达式，以满足
我们称这样的问题为插值问题； 并称φ(x)为 f (x)的插值函数； f (x)为被插函数， x0 , x1, x2, …, xn是插值节(基)点；是插值原则.
3，插值多项式
1、定义：
求一个次数不超过n的多项式使满足插值原则(条件)称Pn(x)为 f (x)的n次插值多项式
2、定理：
在n+1个互异节点处满足插值原则且次数不超过n的多项式Pn(x)存在并且唯一。
注：若不将多项式次数限制为 n ，则插值多项式不唯一。
也是一个插值多项式，其中可以是任意多项式。

4,插值问题
拉格朗日差值
牛顿插值

二次插值基函数

一阶差商

k阶差商

零阶差商

1.差商与节点的排列次序无关，称为差商的对称性
2.高阶差商可由低阶差商反复作一阶差商得到，计算具有递推性
3.若f(x)在[a, b]上存在n阶导数，则

为了使得|ωn+1(x)|尽可能小一些，插值基点的选取原则是：使x尽可能位于区间Ix的中部，这里Ix是包含x以及所用基点的最小闭区间。

1.计算量省，便于程序设计
2.具有承袭性的插值公式，便于理论分析

埃尔米特差值
插值条件中除函数值插值条件外，还有导数值插值条件，即已知：2n+2个条件
求:一个次数不超过2n+1的多项式H2n+1(x)

解法1：基函数法
解法2：承袭法
分段低次插值
原因：当插值基点无限加密时，Pn(x)也只能在很小范围内收敛，这一现象称为龙格(Runge)现象，它表明通过增加基点来提高逼近程度是不宜的。
定义：设在[a,b]上给出插值条件：求一个折线插值函数Ih(x)满足
xi
x0
x1
…
xn
f(xi)
f0
f1
…
fn

1°Ih(x)是[a,b]上的连续函数
2°Ih(xk)=fk，k = 0,1,…,n
3°Ih(x)在每个小区间[xk,xk+1]上是线性函数
则称Ih(x)为分段线性插值函数
数学表达：
性质：
1°分段线性插值多项式是分段函数；
2°可以预见，但n充分大时，Ih(x)能很好逼近f(x)。
3°Ih(x)有一个缺点：在插值点处有尖点，即一阶导数不连续，不够光滑。
解决办法：三次埃尔米特插值

三次样条插值
两种构造方法

5，最小二乘法
1、 定义：已知：一组实验数据（xi，yi）(i=0,1,…,m)，且观测数据有误差
求：自变量x与因变量y之间的函数关系y=F(x) ，不要求y=F(x)经过所有点，而只要求在给定点上误差按某种标准最小。
2、 度量标准：
(1)使残差的最大绝对值为最小
(2)使残差的绝对值之和为最小
(3)使残差的平方和为最小
3、最小二乘法——多项式拟合
已知：一组数据（xi，yi）(i = 0,1,…,m)
求：在次数不超过n的多项式中找一个函数，使误差平方和最小，即
这里：
解： 故： 解得：
4、最小二乘法—非多项式拟合—参数线性
①已知：一组数据（xi，yi）(i = 0,1,…,m)
求：在函数类中找一个函数 ，使误差平方和最小，即
这里：
②已知：一组数据（xi，yi），且每个点对应权因子wi >0, (i=1,2,…,m).
求：在函数类中找一个函数 ，使误差平方和最小，即
这里：

最小二乘法—非多项式拟合—参数非线性
第三章 定积分
1，求解定积分问题方法：（求曲边梯形面积）
旧：（1）牛顿—莱布尼兹公式
【需要寻求原函数的困难】【已知点离散】
新：（2）机械求积公式
【多项式机械求积公式】***【解决原函数的困难】
【中矩形公式】***【解决原函数的困难】
【梯形公式】***【解决原函数的困难】
【插值型求积公式】***【解决离散问题】
2，代数精度
（1）目的：
数值求积方法是近似方法，为了保证精度，我们自然希望公式能对“尽可能多”的函数准确成立，这就提出了所谓代数精度的概念。
（2）定义：
①若某个求积公式对于次数≤m的多项式均能够准确成立，但对于m+1次多项式就不一定准确，则称该求积公式有m次代数精度。
②若某个求积公式对于1, x,…, xm 均能够准确成立，但对于xm+1就不准确成立，则称该求积公式有m次代数精度。
（3）定理：
当n为偶数时，牛顿—柯特斯公式至少有n+1次代数精度。注：在实际应用时，出于对计算复杂性和计算速度的考虑，我们常常使用低阶偶数求积公式，代替高一阶的奇数求积公式。

3，插值求积公式
（1）定理：具有n+1个求积节点的机械求积公式至少有n次代数精度的充分必要条件是，它是插值型的。
试总结证明机械求积公式是插值型求积公式的方法。
（2）求积公式的余项
若求积公式的代数精度为m，则余项形如其中K是不依赖于f(x)的待定参数。
3，牛顿—柯特斯求积公式{梯形，辛普森，柯特斯}
1、 定义
【牛顿—柯特斯】

梯形公式
辛甫生(Simpson)公式
柯特斯(Cotes)公式

一阶【2次代数精度】令f(x)=x2
二阶【3次代数精度】令f(x)=x4
四阶【5次代数精度】

4，复化求积公式
1、 定义：
为了提高精度通常可把积分区间分成若干子区间，再在每个子区间上用低阶求
积公式。这种方法称为复化求积法。
复化求积法就是先用低阶的牛顿—柯特斯公式求得每个子区间[xk, xk+1]上的积分 Ik，然后再求和，用 作为所求积分I的近似值。即
复化梯形公式
复化辛甫生公式
复化柯特斯公式

复化辛甫生公式精度优于复化梯形公式

5，高斯求积公式
1、 定义：
机械求积公式含有2n+2个待定参数：若适当选择这些参数使求积公式具有2n+1次代数精度，则这类公式称为高斯公式。
中矩形公式是
2、 高斯点定义：
高斯公式的求积节点称为高斯点。
3、 求一点的高斯公式
设一点高斯公式为则其代数精度应为
4、 求二点的高斯公式
再设两点高斯公式为代数精度应为
5、 高斯点的性质：
定理：对于插值型求积公式(4.1)，其节点是高斯点的充要条件是以这些点为零点的多项式与任意次数不超过n的多项式P(x)均正交，即【证明看习题】
6、 高斯—勒让得公式
① 特别地，取[a, b]=[-1, 1]，其上高斯公式为：下面求对应的高斯点。
② 对于任意求积区间[a, b]如何求？作变换可以化到区间[-1，1]上，这时

7、 带权的高斯公式
1、定义：求积公式若该公式具有2n+1次代数精度，则称这类公式为带权的高斯公式。上述ρ(x)≥0是权函数。
2、定理：是高斯点的充要条件是是区间[a, b]上关于ρ(x)的正交多项式。
3、特别：若[a, b] = [-1，1]，权函数是所建立的高斯公式为【切比雪夫—高斯公式】【xk是切比雪夫多项式的零点】
第四章 解线性方程组
1、分类
【一般形式】
【矩阵形式】

系数矩阵为低阶稠密矩阵
（阶数大约不超过150）

【直接法】（经过有限步算术运算，可求得方程组的精确解的方法，一般用于解系数矩阵为低阶稠密矩阵）

系数矩阵为大型稀疏矩阵
（阶数高且零元素较多）

【迭代法】（用某种极限过程去逐步逼近精确解的方法，一般用于解系数矩阵为大型稀疏矩阵）

2、范数

向量范数
矩阵范数
类型
在Rn上的向量x =(x1,…, xn)T∈Rn
在Rn×n上的矩阵A=(aij),
定义
设对任意向量 x∈Rn，按一定的规则有一实数与之对应，记为‖x‖，若‖x‖满足

则称‖x‖为向量的范数
设对任意矩阵 A∈Rn×n，按一定的规则有一实数与之对应，记为‖A‖，若‖A‖满足

则称‖A‖为矩阵的范数

称为∞－范数或最大范数
【绝对值最大的元素】
称为1－范数
称为2－范数
称为p－范数
【所有值绝对值的P次方求和，再开P次方】

称为∞－范数或行范数
【所有元素绝对值之和最大的一行】
称为1－范数或列范数
【所有元素绝对值之和最大的一列】
称为2－范数
【ATA的最大特征值开平方】
称为Frobennius－范数
【所有元素平方和开平方】
性质
定义：
如果Rn中有两个范数 ||x||s 与 ||x||t ，存在常数m, M>0，使对任意n维向量x有则称这两个范数等价.
性质：
对两种等价范数而言，某向量序列在其中一种范数意义下收敛时，则在另一种范数意义下也收敛。
定理：
Rn上的任意两个范数等价。【注：今后研究向量序列的收敛性时，可在任何一种范数意义下研究。】

3、“病态”方程组
1、定义：
当一个方程组，由于系数矩阵 A 或右端常数项 b 的微小变化，引起方程组Ax=b解的巨大变化，则称此方程组为“病态”方程组，矩阵A称为“病态”矩阵，否则称方程组为“良态”方程 组，A为“良态”矩阵.
2、如何划分“病态”的程度：
①条件数：设A为非奇异阵，称cond(A)v=||A-1||v||A||v (v =1, 2, ∞) 为矩阵A的条件数。
② 【b】
③ 【A】
④则系数矩阵A的条件数刻划了方程组的“病态”程度。条件数愈大，方程组的“病态”程度愈大，也就愈难得到方程组的比较准确的解；当矩阵A的条件数相对地小，则方程组是“良态”的。
4、 线性方程组解法

向量序列的收敛性
矩阵序列的收敛性
定义1
设 {x(k)} 为Rn中的向量序列，x∈Rn，如果其中||.||为向量范数，则称序列 {x(n)}收敛于 x，记为
设 {A(k)} 为 n 阶方阵序列，A为n阶
方阵，如果其中||.||为矩阵范数，则称序列 {A(n)}收敛于A，记为
定理1

Rn中的向量序列 {x(k)}收敛于Rn中的向量 x 当且仅当

设 A(k) = (aij) (k=1, 2, …)，A = (aij)均为 n 阶方阵，则矩阵序列{A(n)}收敛于
矩阵A的充要条件为

直接消去法
高斯直接消去法
基本思想：用逐次消去未知数的方法把原来方程组AX=b化为与其等价的三角形方程组，而求解三角形方程组就容易了！
高斯消去法的特点：消元和回代不同步！
使用高斯消去法的条件：使用高斯消去法要求在每步消元时，
定理：约化的主元素 (i=1,2,…,n) 的充要条件是矩阵A的顺序主子式
定理6：如果 n 阶矩阵A的所有顺序主子式均不为零，则可通过高斯消去法（不进行交
换两行的初等变换），将方程组约化为三
角形方程组。
定理6：如果A为 n 阶非奇异矩阵，则可通过高斯消去法（及交换两行的初等变换）将方程组 Ax=b 化为三角形方程组。

推论：如果A的顺序主子式不等于0，则

主元素法
在采用高斯消去法解方程组时，小主元可能产
生麻烦，故应避免采用绝对值小的主元素。
对一般矩阵，最好每一步选取系数矩阵（或
消元后的低阶矩阵）中绝对值最大的元素作
为主元素，以使高斯消去法具有较好的数值
稳定性！
列主元素法：
选主元时仅考虑按列选取，然后换行使之变到主元位置上，再进行消元计算。列主元消去法的特点：
（1）能够得到较高精度要求的 解 ；
（2）计算量大大减少

完全主元素法：
其中y1,y2,…,yn为未知数x1,x2,…,xn调换后的次序。【第一步：首先在A中选取绝对值最大的元素作为主元素；然后交换到第一行、第一列的位置；再进行第一次消元，】完全主元素消去法的缺点：在选主元素时要花费较多机器时间。时时纪录x顺序的变化情况

高斯约当消去法
高斯——约当消去法定义：
则同时消去对角线上方和下方的元素。
高斯——约当消去法的特点：
(1) 消元和回代同时进行；
(2) 乘除法的次数要比高斯消去法大，所以通常用于同时求解系数矩阵相同的多个方程组或求逆矩阵。

直接三角法
直接三角分解法
定理: (矩阵的LU分解)
设 A 为 n 阶矩阵，如果 A 的顺序主子式
( i = 1,2,…,n-1)， 则 A 可分解为一个
单位下三角矩阵 L 和一个上三角矩阵 U 的乘积，且这种分解是唯一的。注：若A 实现了LU分解，则Ax = b (LU)x=b Ly = b Ux = y

单位下三角阵 上三角阵

解得
解得
平方根法
A=LDLT
A=LLT
平方根法适用于系数矩阵为对称正定阵的方
程组的求解。
定理1 (对称阵的三角分解定理)
设A为n阶对称阵，且A的所有顺序主子式均
不为零，则A可唯一分解为 A=LDLT其中L为单位下三角阵，D为对角阵.

定理2 (对称正定阵的三角分解定理)
设A为n阶对称阵，且A的所有顺序主子式均
大于零，则存在一个非奇异下三角阵 L 使
A=LLT，当限定L的对角元素为正时，这种
分解是唯一的。Cholesky分解

追赶法A=LU
追赶法适用于系数矩阵为三对角阵的方程组
的求解。
利用系数矩阵的特点，可以将A分解为两个三角阵的乘积，A=LU，其中L为下三角矩阵，U为单位上三角矩阵。

迭代法
雅克比迭代法
一般形式

矩阵形式
将方程组记为 Ax = b其中A非奇异且aii ≠0 (I=1, 2, …, n).将A分裂为 A = D－Ｌ－Ｕ 其中

高斯塞德尔

将方程组记为 Ax = b其中A非奇异且aii ≠0 (I=1, 2, …, n).将A分裂为 A = D－Ｌ－Ｕ 其中

超松弛迭
x(k+1) = x(k) + ω △xω <1时，称为低松弛； ω=1时，是G-S法；ω >1时，称为超松弛法，简称SOR法

用分解式 A = D－Ｌ－Ｕ，则可写为

注：
(1) 松弛法是G-S法的一种加速方法；
(2) 具有计算公式简单，程序设计容易；
(3) 但需要选择较好的加速因子。

5、 迭代法敛散性判断方法
预备定义
定义1：称迭代公式中的矩阵 B 为迭代矩阵.
定义2：设A为n阶方阵，λi (i = 1,…,n)为A的特征值，称特征值模的最大值为矩阵A的谱半径，记为
定义2：称为矩阵A的谱.
定义3：Ak = AA…A 的谱为 ( k = 1, 2, …)
定义3：Ak = AA…A 的谱半径为

已知定理
定理1：设A为任意n阶方阵，||.||为任意由向量:范数诱导出的矩阵的范数，则
定理2：设A为n阶方阵，则对任意正数ε，存在一种矩阵范数||.||，使得
定理3：设A为n阶方阵，则的充要条件为
辅助定义
定义：若n阶方阵 A=(aij)满足且至少有一个 i 值，使上式中不等号严格成立，则称A为弱对角占优阵。若对所有 i，不等号均严格成立，则称A为严格对角占优阵。

定义：如果矩阵A不能通过行的互换和相应列的互换成为形式其中A11，A22为方阵，则称A为不可约.
收敛判断条件
设有线性方程组Ax=b，下列结论成立：
1. 若A为严格对角占优阵或不可约弱对角占优阵，则Jacobi迭代法和Gauss-Seidel迭代法均收敛。
2. 若A为严格对角占优阵，0<ω≤1，则松弛法收敛。
3. 若A为对称正定阵，0<ω<2，则松弛法收敛.即：若A是对称正定阵，则松弛法收敛的充要条件为0<ω<2。
推论：若迭代矩阵满足 ||M||<1，则迭代公式产生的向量序列{x(k)}收敛。
定理：对任意初始向量 x(0)和右端项g，由迭代格式x(k+1) = Mx(k) + g产生的向量序列收敛的充要条件为
推论：松弛法收敛的必要条件是 0<ω<2
值得注意的是：改变方程组中方程的顺序，即将系数矩阵作行交换，会改变迭代法的收敛性。

第五章 解非线性方程组
1、定义
求 f (x) = 0 的根：f(x)为非线性函数或高次代数方程，若有数x*使f(x*) = 0成立，则称x*为方程f(x) = 0的根(零点)。若f(x)可分解为当m = 1，称x*是单根；当m > 1，称x*是m重根.
2、求根的两个步骤
(1)确定根的初始近似值(称之为初始近似根) ，一般为一个包含根的区间，称为“有根区间”【逐步扫描法：原理：设f(x)在[a, b]连续，且f(a) f(b)<0。则由连续函数的性质知f(x)=0在(a, b)内至少有一个根。若f(x)在[a, b]上单调，则f(x)=0在(a, b)上有且仅有一个根。】
(2)根的精确化。根据根的初始近似值按某种方法逐步精确化，直至满足预先要求的精度为止。【①二分法②简单迭代法③牛顿迭代法④弦截法】

2、分类
二分法
原理：若 f ÎC[a, b]，且 f (a) · f (b) < 0，则 f 在 (a, b) 上必有一根 x*。
实施：将方程根的区间平分为两个小区间，然后判断根在哪个小区间，舍去无根的区间，而把有根区间再一分为二，再判断根属于哪个更小的区间，如此周而复始，直到求出满足精度要求的近似根。
停止： 或
误差分析：对于给定的精度 e ,可估计二分法所需的步数 k
优点：①简单; ② 对f (x) 要求不高(只要连续即可) .
缺点：①无法求复根及偶重根 ② 收敛慢

简单迭代法
基本思想：
f(x) = 0【同解变形】x = g(x)【构造公式】xk+1 = g(xk)【给初值x0 ；若xk→x*且g(x)连续】x*就是f(x)=0的根
区间收敛：
设方程 x = g(x)有根x*, g(x)可微，若( I ) 当 xÎ[a, b] 时， g(x)Î[a, b]；( II ) $ 0 £ L < 1 使得 | g’(x) | £ L < 1 对 " xÎ[a, b] 成立。
则任取 x0Î[a, b]，由 xk+1 = g(xk) 得到的序列收敛于g(x) 在[a, b]上的唯一不动点。
注1：定理中的L<1非常重要，否则不能保证收敛，且L越小，收敛越快。
注2：为恰当估计 ，可以把有根区间取得适当小。
补充：1.迭代是否收敛除了依赖于迭代函数外，还依赖于有根区间。
2．设方程x=g(x)在区间[a,b]内有根，若总有,则迭代公式对任意[a,b]上的初值均发散。
局部收敛：
定义：设x*是g(x)的不动点，若存在 x* 的某d 邻域 Bd = { x | | x - x* | £ d } ，对 迭代产生的序列且收敛到x*，则称局部收敛.
定理：设x*是g(x)的不动点，若g’(x)在 x* 的某 邻域连续，且有| g’(x*) | < 1，则迭代法局部收敛。
收敛速度：
迭代法的收敛阶定义：设迭代 xk+1 = g(xk) 收敛到g(x) 的不动点 x*。设 ek = xk - x*，若则称该迭代为p 阶收敛，其中 C 称为渐进误差常数。
特别地：
p = 1时：线性收敛， p >1时：超线性收敛， p = 2时：平方收敛
定理：
设 x* 为x = g(x) 的不动点，若 ，p ³ 2；
且，则 xk+1 = g(xk) 在内 p 阶收敛。
牛顿迭代法
原理：将非线性方程线性化——泰勒展开

局部收敛性
设 f ÎC2[a, b]，若 x* 为 f (x) 在[a, b]上的根，且 f ’(x*) ¹ 0，则存在 x* 的邻域使得任取初值Newton’s Method产生的序列{ xk } 收敛到x*，且满足有只要就有 p ³ 2。重根是线性收敛的。
注： (1) 牛顿法要求初值充分接近根以保证局部收敛性。
(2)牛顿迭代法的主要优点是收敛较快，是平方收敛的缺点是公式中需要求 f(x) 的导数。若 f(x)比较复杂，则使用牛顿公式就大为不便。
弦截法
针对问题：重根问题
问题1: 若，Newton’s Method 是否仍收敛？
K1: 有局部收敛性，但重数 n 越高，收敛越慢。
问题2: 如何加速重根的收敛？
K2: 将求 f 的重根转化为求另一函数的单根。令则 f 的重根 = m 的单根。
下山法：
原理：若由 xk 得到的 xk+1 不能使 | f | 减小，则在 xk 和 xk+1 之间找一个更好的点，使得 l = 1 时就是Newton’s Method 公式。当 l = 1 代入效果不好时，将 l 减半计算。

弦截法
Newton’s Method 一步要计算 f 和 f ’，相当于2个函数值，比较费时。现用 f 的值近似 f ’，可少算一个函数值。需要 2 个初值 x0 和 x1
切线斜率 » 割线斜率

弦截法与牛顿法相比较
相同之处：都是线性化方法
不同之处：牛顿法在计算xk+1时只用到前一步的值xk，故这种方法称为单点迭代法；而弦截法在求xk+1时要用到前两步的值xk和xk-1，因此这种方法称为多点迭代法。
弦截法的收敛速度
与牛顿法相比，弦截法的收敛速度也是比较快的。可以证明，弦截法具有超线性收敛速度，收敛阶为即
第6章 解常微分方程
1、定义
理论上可以证明：只要函数f(x，y)适当光滑—关于y满足李普希兹(Lipschitz)条件则初值问题的解存在唯一。
2、两种解
一般解(解析解) y=y(xi)在x=xi处的精确值.
对一些典型的微分方程(可分离变量方程，一阶线性方程等等)，有可能找出它们的一般解表达式，然后用初始条件确定表达式中的任意常数，这样解即能确定。故解为y=x2
数值解（近似解）：yi 一般解y=y(x)在x=xi处的近似值.

y1，y2，…，yn
由于在实用上对初值问题，一般是要求得到解在若干点上满足规定精确度的近似值yi，或者是得到一个满足精确度要求的便于计算的近似表达式。故常微分方程的数值解就是求出在若干点上解的近似值。
定义：指在由初始点x0开始的若干离散的x值处，即对x0<x1<x2<…<xn，求出准确值y(x1),y(x2),…，y(xn)的近似值y1，y2，…，yn

2、三种数值解法
用差商代替导数

yn=yn-1+hf(x0+(n-1)h,yn-1)
使用泰勒公式
在微分方程y’=f(x,y)中，y’是x及y(x)的函数.由于精确值y(x+h)在h=0处的泰勒展式为

注：应用泰勒公式求数值解，从形式上看简单，其实具体构造这种公式往往是相当困难的，因为它需要提供导数值，y(j)n当阶数提高时，求导过程可能很复杂，因此泰勒公式通常不直接使用，但可以用它来启发思路。

使用数值积分的方法
对于微分方程 y’=f(x,y)两边求x0到x的定积分

2、 五种数值方法、
在假设 yi = y(xi)，即第 i 步计算是精确的前提下，考虑的截断误差 Ri+1 = y(xi+1) - yi+1 称为局部截断误差
欧拉公式
简单；精度低
向前差商近似导数

欧拉法具有 1 阶精度
隐式的欧拉公式
稳定性最好；
精度低, 计算量大
向后差商近似导数

隐式欧拉公式具有 1 阶精度。
梯形公式
精度提高
计算量大

的确有局部截断误差 即梯形公式具有2 阶精度，比欧拉方法有了进步。但注意到该公式是隐式公式，计算时不得不用到迭代法，其迭代收敛性与欧拉公式相似。

中点欧拉公式
计算量大
多一个初值,
可能影响精度

即中点公式具有 2 阶精度需要2个初值 y0和 y1来启动递推过程，这样的算法称为双步法而前面的三种算法都是单步法
改进的欧拉公式

此法亦称为预测-校正法。可以证明该算法具有 2 阶精度，同时可以看到它是个单步递推格式，比隐式公式的迭代求解过程简单。