数值分析_总结

数值分析

引论

基本概念

• 误差：近似值和实际值（精确值）的差别。
• 误差限：误差的限度。是误差绝对值的“上界”。
• 相对误差：误差除以实际值乘以 100%。相对误差较小时，可除以近似值。
• 相对误差限：相对误差的限度。相对误差限小则近似程度好。
• 有效数字：一个数中，可供判断精度的数字。若近似值 x*的绝对误差限是某一位上的半个单位，且该位直到 x*的第一位非零数字一共有 n 位，则称它有 n 位有效数字，或精确到该位（比如精确到 0.1，0.0001）。
• 经过四舍五入得到的近似数：有效数字可以通过四舍五入判定原则直观地数出来的数。

有效数字位数的三种判定方法

• 通过定义（绝对误差）判定：计算出近似值的绝对误差，再取一个最小的某一位上的半个单位的绝对误差限，即可得到精度。

【例】绝对误差=0.008<0.05，说明绝对误差限可取 0.05=0.5/10，精确到 0.1。

• 通过四舍五入原则判定：若近似值是由精确值四舍五入得到的，可采用这种判定方法。

【例】3.1415926，3.14 由小数点后第 3 位四舍五入得到，则 3.14 精确到小数点后第二位，从这一位到前面第一个不等于 0 的数都是 3.14 的有效数字。

• 通过相对误差限判定有效数字的位数：近似值边界判定+绝对误差判定=>有效数字位数。

有效数字与相对误差限的关系

（公式是记不住的，推导=绝对误差判断方法+近似值边界判定。）

• 利用有效数字估算绝对误差限，结合$a_1$确定近似值的下界，相除，以近似值估计相对误差。

近似值$x^{＊}=±0.a_1a_2…a_n×10^m$，其有 n 位有效数字，$a_1≠0$，则其相对误差限为$\frac{1}{2a_1}×10^{-n+1}$。

• 结合$a_1$确定近似值的上界，相乘，得到绝对误差限，借此判断有效数字位数。

近似值$x^{＊}=±0.a_1a_2…a_n×10^m$，$a_1≠0$，其相对误差限为$\frac{1}{2a_1+1}×10^{-n+1}$，则其有 n 位有效数字。

误差限的估计公式

已知 x,y 的绝对或相对误差限，求 f(x,y)的绝对或相对误差限。

（仅写出绝对误差限公式，相对误差的公式直接由此推导就好了，记不住的）

• 加减运算：x 和 y 的加减结果的绝对误差限=x 的误差限+y 的误差限。

$|(x^{＊}±y^{＊})-(x±y)|≤|x^{＊}-x|+|y^{＊}-y|$

• ☆☆☆乘除运算：绝对误差限较小时的估计方式（为简化结果）——

$η(x^{＊}y^{＊})≈|x^{＊}|η(y^{＊})+|y^{＊}|η(x^{＊})$

$\eta (\frac{x^{＊}}{y^{＊}})≈\frac{|x^{＊}|η(y^{＊})+|y^{＊}|η(x^{＊})}{|y^{＊}|^2},y≠0,y^{＊}≠0$

近似计算中的原则

保留位数原则

加减运算：小数位

• 计算时：把近似数中小数位数较多的数四舍五入，使其比小数位数最少的数多一位。
• 计算结果：保留的小数位数与原近似数中小数位数最少者相同。

乘除运算：有效数字

• 计算时：因子保留的位数应比有效数字位数最少者的位数多一位。
• 计算结果：有效数位数与原近似值中有效数字位数最少者至多少一位。

乘方与开方运算：有效数字

• 计算结果：有效数字位数与原近似值的有效数字位数相同。

对数运算：有效数字

• 计算结果：有效数字位数与其真数（被对数运算的数）的有效数字位数相同。

中间计算过程

• 应比上述保留位数原则所提及的位数多取一位，在进行最后一次计算时这一位要舍入。

原始数据选取

• 加减运算：小数位应比计算结果要求的多一位。
• 上述其他运算：有效数字位数应比计算结果要求的多一位。

其他原则

• 避免两个相近的数相减：有效数字损失。
• 避免除数绝对值远远小于被除数绝对值的除法：舍入误差增大。
• 要防止“大数”吃掉“小数”：数量级相差过大时小数在计算过程中被舍入（比如计算机内计算时加减法要对阶）。
• 要尽可能减少运算次数：减小累积误差。

重点应用

求误差限

• 已知经过四舍五入得到的近似数（或误差限），求它们的四则运算结果的误差限：利用有效数字数量可以反过来估算一个绝对误差限。再结合近似值的上下界可进一步估算相对误差限。

算术运算

• 保留位数原则的利用。
• 利用近似原则分析运算优劣。

仅在选择、判断常见的内容

计算方法的研究方法

• “离散化”方法：将连续变量问题转化为离散变量问题。
• “递推”方法：将复杂问题转化为简单问题的重复。
• “近似替代”方法：将不能用有限计算解决的问题转化为较简单的有限计算问题。

误差的来源（需要具备判断误差种类的能力）

• 模型误差：问题理想化。
• 观测误差：原始数据观测误差。
• ☆截断误差：计算是有限次带来的误差。
• ☆舍入误差：参与计算的数长度有限带来的误差。

为什么要引入误差限的概念？

• 答：因为精确值一般未知，误差只能在一定范围内研究，而这个范围就叫做误差限。由于研究范围是不惟一的，误差限也具有不惟一性。

---

---

---

插值方法

两个插值惟一性

均可用反证法证明。

• 插值多项式的存在惟一性：n+1 个数据对应的次数不高于 n 的代数多项式存在且惟一。
• Hermite 插值多项式的惟一性：满足给定条件的 Hermite 插值多项式惟一。

Lagrange 插值公式

• 插值基函数$l_n(x)$：次数为 n 的、以$x_{1} ～ x_{n}$为零点、在$x_0$处为 1 的函数。
• Lagrange 公式：函数值乘以基函数。
• Lagrange 余项：反复求导用 Rolle 定理得到。

$f(x)-p_n(x)=\frac{f^{n+1}(ξ)}{(n+1)!}\prod_{i=0}^{n}(x-x_i)$

Newton 插值公式

• 插值基函数$\varphi_n(x)$：$(x-x_0)$到$(x-x_{n-1})$的乘积。
• Newton 公式：差商乘以基函数。
• ☆Newton 余项：

$f(x)-N_n(x)=f[x,x_0,···,x_{n}]\varphi _n(x)$

• k 阶差商：

$f[x_0,x_1,···,x_k]=\frac{f[x_0,···,x_{k-1}]-f[x_1,···,x_{k}]}{x_0-x_k}$

• ☆k 阶差商表示形式二：该表示形式承袭性弱。

  用数学归纳法可证。（证明方式由差商的定义形式可知）

$f[x_0,x_1,···,x_k]=\sum_{j=0}^{k}\frac{f(x_j)}{\omega '_k(x_j)},\omega '_k(x_j)=\prod^k_{i=0,i≠j}(x-x_i)$

• 表达形式二可推出：
  • 差商的对称性：差商的值与节点的排列顺序无关。
  • 数据点越多的、带 x 数据项的差商的 x 幂次反而越低。

Hermite 插值

• 仅讨论一阶导数值和函数值给定的情况。

• 插值基函数$\varphi _n(x)$和$\Psi _n(x)$：与 Lagrange 基函数构造思路一致。

  区别：根据导数条件构造的基函数与根据函数值构造的基函数符号相异。

• Hermite 公式：函数或导数值乘以基函数。

• Hermite 基函数的多项式系数计算方法：

  • 按照定义构造式子，解线性方程组死算。
  • 根据承袭性。比如已知$x_0,x_2,···,x_n$对应的函数值，并知道某些点的导数值(比如知道$x_0,x_1$的)，则可以构造函数，$p_n(x)$是 Lagrange 或者 Newton 求出来的多项式，分别求解$p_n(x)$和$a_i$。

$H_{n+2}(x)=p_{n}(x)+(a_0x+a_1)(x-x_0)(x-x_1)···(x-x_n)$

• Hermite 余项：在某一结点有多少项就乘以多少次方。

$f(x)-H_n(x)=\frac{f^{n+1}(ξ)}{(n+1)!}\prod_{i=0}^{n_1}(x-x_i)×\prod_{i=0}^{n_2}(x-x_i),n_1+n_2=n$

分段插值法

• 分段插值公式的单个区间的 x 只在区域内。因此可以计算得到误差的最大值、精度可以被划分区间长度限制、收敛性总能得到保证、修改数据点只有局部受影响。而 Lagrange 余项或插值公式并没有对 x 取值进行讨论。
• 分段线性插值：单个区间的误差<$\frac{1}{8}h_i^2$×这一段二阶导的最大值。
• ☆分段三次 Hermite 插值：单个区间的误差<$\frac{1}{384}h_i^4$×这一段四阶导的最大值。

重点应用

构造插值多项式求函数值

• 给数据表，计算 Lagrange、Newton、Hermite 插值多项式。（一般给的数据比较少），Newton 插值多项式在 x 有规律地分布时是最好算的。
• 也可能是求 x 的值，把表反过来用就行。

由一个插值多项式推另一个

• 多半使用了承袭性。可以先看看之前的那个多项式是由哪些点推导而来的。如果单纯增加了导数，就 Hermite 插值多项式的承袭性；如果增加的是点，就用 Newton 差商的承袭性。后者比前者好算。

证明等式成立

• 多半用了差商的性质，结合其他的定义式。

证明一致收敛

• 把误差计算出来，如果在某条件下误差趋向 0，说明一致收敛。（绝对值）

仅在选择、判断中出现的内容

Lagrange 与 Newton 插值余项的比较

• Lagrange 余项要求 f(x)有(n+1)阶导，Newton 余项中含有 f(x)。
• Newton 插值公式可改写成：

$N_n(x)=f(x_0)+f'(ξ_1)\varphi _1(x)+···+\frac{f^{(n)}(ξ_n)}{n!}\varphi _n(x),ξ∈[min(x_i),max(x_i)]$

Runge 现象

• 大范围内使用高次插值，逼近效果往往并不理想。

• Runge 举例：在 x=±5 附近，$p_{10}(x)$偏离 f(x)的程度远大于$p_5(x)$。

$f(x)=\frac{1}{1+x^2},-5≤x≤5$

分段插值法的缺憾

• 即使是分段三次 Hermite 插值，在插值节点处插值曲线也不够光滑，而且这种需要提供的信息很多。

样条插值和曲线拟合

• 样条插值：分段三次 Hermite 插值改进，为解决插值结点处曲线不够光滑。
• 最小二乘法：不要求所构造的逼近函数严格地通过给定的数据点，只是在某一函数类 H 中，以使残差的平方和最小为标准，作近似替代。主要讨论的是多项式拟合。

---

---

---

数值积分

基本概念

机械求积

• 定义：取一个合适的值作为积分区间的平均高度，再乘以积分区间的宽度，得到积分区间的面积。
• 应用：Newton-Cotes 公式、中矩形公式等。
• 基本构造：令$A_i$为求积系数,$x_i$为求积结点，

$∫^b_af(x)dx≈\sum^n_{i=0}A_if(x_i)$

• 求积系数$A_i$的求解方法：
  • 解线性方程组法：根据代数精度的定义，依次使 f(x)=$1,x,x^2,x^3,···,x^m$，建立一系列等式，求出求积系数$A_i$。
  • 插值法：用 Lagrange 插值多项式近似替代被积分函数，积分得到求积系数为$A_i=∫^b_al_i(x)dx$。对于已知的插值节点和常数 a,b，$∫^b_al_i(x)dx$是常数。

代数精度

• 定义：如果求积公式对于一切次数小于等于 m 的多项式是准确的，而对于次数为 m+1 的某一多项式并不准确成立，则称该求积公式具有 m 次代数精度。
• 证明方法：因为积分具有线性性，所以“准确成立”也具有线性性。证明 m 阶代数精度，只需要代入证明对$x^m$和$x^{m+1}$是否准确成立即可。即：

$∫^b_af(x)dx=\sum^n_{i=0}A_if(x_i),f(x)=x^k(k=0,1,···,m)$

• 性质：n+1 个互异结点构造的求积公式的代数精度不低于 n。

插值型的求积公式

• 定义：求积系数为$A_i=∫^b_al_i(x)dx$的求积公式。
• 性质：求积公式至少具有 n 次代数精度的充要条件是它是插值型的。

数值稳定性

• 定义：即计算结果可靠。一个算法，如果在执行它的过程中舍入误差在一定条件下能够得到控制，即舍入误差的增长不影响产生可靠结果，则称它是数值稳定的。
• 证明：计算总的舍入误差，若它是有上界的，则可称它是数值稳定的。

事后误差估计法

• 定义：直接用计算结果来估计误差的方法。

Newton-Cotes 公式

• 定义：等距节点的插值型的机械求积公式。将积分区间分成(n+1)份。
• n=1,2,4 的 Newton-Cotes 公式常用：
  • ☆梯形公式：1/2, 1/2
  • ☆Simpson 公式：1/6, 4/6, 1/6
  • Cotes 公式：7/90, 32/90, 12/90, 32/90, 7/90
  • ☆三阶的 Cotes 系数为：1/8, 3/8, 3/8, 1/8
• 性质：
  • 代数精度：因为是插值型，所以至少为 n；且当 n 为偶数时，它的代数精度至少为 n+1。由 n+1 阶多项式对应的余项做代换之后等于 0 证明。
  • 数值稳定：n=8 或之后不再具有数值稳定性，因为 Cotes 系数出现负数。总舍入误差可以写成与 Cotes 系数与(b-a)相关的。
  • ☆截断误差：（由 Lagrange 插值多项式的余项积分得到）
    • 梯形公式：$R=-\frac{1}{12}(b-a)^3f''(ξ),ξ∈[a,b]$；
    • Simpson 公式：$R=-\frac{1}{90}(\frac{b-a}{2})^5f^{(4)}(ξ),ξ∈[a,b]$；
    • Cotes 公式：$R=-\frac{8}{945}(\frac{b-a}{4})^7f^{(6)}(ξ),ξ∈[a,b]$；
  • n<8 时，有如下性质：(取 f(x)=1 可证)

$\sum^n_{i=0}C_i=\sum^n_{i=0}|C_i|=1$

复化求积法

• 原理：把区间分成 n 个小区间，在每个小区间上采用次数不高的插值多项式去替代被积函数，构造出相应的求积公式，然后把它们加起来作为整个积分区间上的求积公式。步长 h=$\frac{b-a}{n}$。

• 确定重复被加的求积节点应作图。（见章末附图）

• 根据余项确定步长：

  • ☆复化梯形公式：$|R_T|≤\frac{nh^3}{12}max[f''(x)]$
  • 复化 Simpson 公式：$|R_S|≤\frac{nh^5}{90}max[f^{(4)}(x)]$
  • 复化 Cotes 公式：$|R_C|≤\frac{8nh^7}{945}max[f^{(6)}(x)]$
  • 缺陷：求导麻烦、（用导数最大值）估计较保守。

• ☆递推法（二分法）确定步长（以梯形法为例）：

  • 取 n，近似计算$T_n$；
  • 用$T_{n}$近似计算$T_{2n}$，其中$x_i$是二分新增的节点；

$T_{2n}=\frac{1}{2}T_n+(\frac{1}{2})^n[f(x_1)+f(x_2)+···+f(x_n)]$

• 判断$|T_{2n}-T_n|≤ε$是否成立，如果成立则表示$T_{2n}$满足精度要求。该判断误差的方法是一种事后误差估计法。

Romberg 积分法

• 用误差来修正公式，由低精度求积公式的组合得到较高精度求积公式。它算法简单，收敛速度快。误差估计与 Newton-Cotes 公式截断误差同。
• ☆$S_n=\frac{4}{3}T_{2n}-\frac{1}{3}T_n；C_n=\frac{16}{15}S_{2n}-\frac{1}{15}S{n}；R_n=\frac{64}{63}C_{2n}-\frac{1}{63}C_n$。

重点应用

构造求积公式（例题有，课后习题没有）

• 由代数精度构造求积公式；

  1. 设 f(x)=$1,x,x^2,x^3,···,x^m$，代入求积公式构造式。
  2. 解线性方程组，得到$A_i$。

• 由插值节点构造求积公式：

  1. 列出插值基函数；

  2. 计算插值基函数在区间内的积分，得到$A_i$。

求代数精度（详情见上）

计算截断误差，通过误差判断步长等

• 利用 Taylor 公式求截断误差；
• 利用（复化）Newton-Cotes 公式结论求截断误差。

证明是插值型的

• 非常规，证明题：
  • 确定插值结点，列出插值基函数；
  • 分别对插值积分，对比求积系数，看是否相等，若均相等则为插值型。
• 常规并均分：对比 Cotes 系数。

---

---

---

常微分方程数值解法

基本概念

• ☆初值问题：求解$y'(x)=f(x,y),y(x_0)=y_0$方程组，满足 Lipschitz 条件则有唯一解。

$Lipschitz:|f(x,y)-f(x,{ \bar y})|\leq L|y-\bar y|,L\geq 0$

• $y_n$：$y(x_n)$的近似值。$y(x_n)$是 y(x)在$x_n$处的精确值。
• 显式递推公式等式右边没有$y_{n+1}$，隐式的有。
• 局部截断误差：
  • 定义：假定在求$y_{n+1}$的递推公式中等式右边所有的量都是精确的，在此前提下的$y(x_{n+1})-y_{n+1}$。
  • 计算方法：使用局部截断误差的定义和 Taylor 公式展开。
• 精度：局部截断误差为$O(h^{p+1})$，则称此方法精度为 p 阶。
• 收敛性：h→0(同时 n→∞)时趋向于准确解$y(x_n)$。
  • 收敛性定理：假设单步法具有 p 阶精度，且增量函数满足 Lipschitz 条件，且初值是准确的，则其整体截断误差为$O(h^p)$。
• 稳定性：误差的积累得到控制。
  • 扰动：$\delta _n=\tilde y_n-y_n $。
  • 隐式尤拉法无条件稳定。
• 整体截断误差：$|y(x_{n})-y_{n}|$可由局部截断误差反复递推得到。

近似递推公式

构造方法

一阶差商法

• 尤拉法（折线法）：向前差商，显式，单步，一阶；
• 隐式尤拉法：向后差商，隐式，单步，一阶；不能直接计算：
  • 计算时化为显式；
  • 预报-校正法：尤拉预报，隐式校正。
• 二步尤拉法（中心差商法）：中间差商，显式，二步，二阶。

解定积分法

• 原理：$∫^{x_{n+1}}_{x_n}y'dx=y(x_{n+1})-y(x_n)=hf(x_ξ,y_ξ)$。其中解定积分参考第三章。

• 梯形公式：

  • $f(x_ξ,y_ξ)=\frac{f(x_n,y_n)+f(x_{n+1},y_{n+1})}{2}$。单步，隐式，二阶。
  • 是尤拉法和隐式尤拉法的算术平均，计算量大。

• 改进的尤拉法：用预报-校正法改进梯形公式的结果。

  • 嵌套形式：将预报值直接代入梯形公式中。

  • 平均化形式：利用了梯形公式是尤拉法和隐式尤拉法的算术平均。

    这种形式更好观察几何意义。

    $y_p=y_n+hf(x_n,y_n)=y_n+hk_1;$

    $y_c=y_n+hf(x_{n+1},y_p)=y_n+hk_2;$

    $y_{n+1}=\frac{1}{2}(y_p+y_c)$。

龙格-库塔法

• 原理：
  • 本质：构造$y(x_{n+1})=y(x_n)+hy'(ξ)$中$y'(ξ)$的近似替代。
  • 方法：构造导数近似值，利用 Taylor 公式分析局部截断误差，求出导数近似值对应的参数的值。
• 一阶：比如用$y'(x_n)$的近似值替代$y'(ξ)$。
• 二阶：用$x_n$、$x_{n+1}$两点上的导数近似值的平均替代$y'(ξ)$。
  • 改进的尤拉法：$\lambda =\frac 12,\, p=1$；
  • 变型的尤拉法（中点方法）：$\lambda =1,\, p=\frac 12$；
  • ☆构造：$\lambda p=\frac 12$。

$f(n)= \begin{cases} y_{n+1}=y_n+h((1-\lambda )k_1+\lambda k_2) \\k_1=f(x_n,y_n) \\ k_2=f(x_n+ph,y_n+phk_1) \end{cases}$

• 三阶：举例。

$f(n)= \begin{cases} y_{n+1}=y_n+\frac16(k_1+4k_2+k_3) \\k_1=hf(x_n,y_n) \\ k_2=hf(x_n+\frac 12h,y_n+\frac 12k_1) \\k_3=hf(x_n+h,y_n-k_1+2k_2) \end{cases}$

• ☆四阶：

  • Gill 公式。

  • 经典公式（标准 4 阶龙格-库塔公式）：

$f(n)= \begin{cases} y_{n+1}=y_n+\frac16(k_1+2k_2+2k_3+k_4) \\k_1=hf(x_n,y_n) \\ k_2=hf(x_n+\frac 12h,y_n+\frac 12k_1) \\k_3=hf(x_n+\frac 12h,y_n+\frac 12k_2)\\k_4=hf(x_n+h,y_n+k_3) \end{cases}$

• 性质：适用于求解范围大、精确度要求高的较光滑曲线求解。

• 变步长：

  • 计算结果的偏差$△=\frac 1{2^p-1}|y_{n+1}^{(h/2)}-y_{n+1}^{(h)}|$；
  • 在满足精度的要求下，步长尽量取大。

重点应用

解初值问题

• 不是算公式，是计算离散点的值。
• 计算时先把预报的值求出来，而不是直接把公式代入预报的公式。

求解计算公式的精度

• 主要是用泰勒公式，重点步骤(偏导和导数的关系)：

$f'_x(x_n,y_n)+f'_y(x_n,y_n)y'(x_n)=y''(x_n)$

证明收敛性、稳定性

• 收敛性：证明满足 Lipschitz 条件；
• 稳定性：证明扰动可控。
  • 假设一个扰动；
  • 计算这个扰动在递推后得到的下一个扰动值；
  • 令递推之后扰动的传播系数不超过 1，得到稳定性条件；

仅在选择、判断中出现的

• 数值解法：能算出精确解 y(x)在一系列离散节点上的近似解的方法。
• 二步尤拉法的缺陷：①计算局部截断误差时的附加限制条件不一定成立；②h 足够小时，精度越高才能保证局部截断误差越小。

---

---

---

方程求根

基本概念

• m 重根：f(x)=$(x-x^＊)^mg(x),g(x^＊)\neq 0$。
• 隔根区间：区间内只有一个根的区间。
• 有根区间：区间内有根的区间。
• 局部收敛性：如果存在领域△:$|x-x^＊|\leq \delta$，迭代过程对于任意初值$x_0\in △$均收敛，则这种在根的邻近具有收敛性的收敛性称为局部收敛性。若$\varphi (x)$在$x=\varphi (x)$的根$x^＊$邻近有连续的一阶导数，且$|\varphi '(x)\leq k <1|$，k 越小收敛得越快。
• 迭代速度（收敛速度）：迭代误差$\varepsilon _k =x_k -x^＊ (k=0,1,···)$，对某个实数 p 与非零常数 C，有$lim_{k→∞}\frac{\varepsilon _{k+1}}{\varepsilon ^p_k}=C,C\neq 0$，则称{x$_k$}是 p 阶收敛的，p=1 则是线性收敛，p>1 是超线性收敛，p=2 是平方收敛。p 越大，收敛越快。

逐步搜索法

• 预定步长，按一定顺序看每一步上的导数值，直到确定根区间或遍历结束。

二分法

• 逐步搜索法的改进，只能求出一个根。二分看导数值。
• 适用于：一个边界异号的有根区间。
• ☆误差估计：$|x^＊-x_k|\leq \frac {1}{2^{k+1}}(b-a),k=1,2,···$

迭代法（逐步逼近的方法）

• 原理：将$f(x)=0$转换成$x=\varphi(x)$，如果$\varphi(x)$是收敛的，迭代结果是方程的根。

• 收敛性定理：设$\varphi (x)$在[a,b]上具有连续一阶导，且$\varphi (x)\in [a,b]$，存在正数 L<1，使对任意$x\in [a,b]$，有$|\varphi '(x)|\leq L<1$，则唯一解，而且对任意$x_0$序列收敛。

• ☆误差估计：$|x^＊-x_k|\leq \frac {L^k}{1-L}|x_1-x_0|,k=1,2,···$。

• 收敛过程加速的原理：估计迭代结果的误差，并将误差估计加至迭代式中，则可能产生一个更好的求根迭代式。如 Aitken 加速，用了两次迭代改进。

• 牛顿法（又称切线法）：迭代函数根据导数变化。

  • 构造：$x=x-\frac{f(x)}{f'(x)},(f'(x)\neq 0)$.
  • 局部收敛性：若$x^＊$是方程 f(x)=0 的一个单根，并且 f(x)在$x^＊$即附近有连续的二阶导数，则牛顿法具有局部收敛性。
  • ☆收敛速度：若二阶导$f''(x)\neq 0$，则平方收敛；
  • 局限性：初值需要选取与根相近的。要保证$|\varepsilon _1|<|\varepsilon _0|$。

• 牛顿下山法：改进的牛顿法。

  • ☆构造：$x_{n+1}=x_n-\lambda_n\frac{f(x_n)}{f'(x_n)},0<\lambda _n <1,\lambda$是下山因子。
  • ☆下山条件：$|f(x_{k+1})|<|f(x_k)|$，令$\lambda$不断减半直到满足单调性条件。

重点应用

• 二分法求根并分析误差
• 证明迭代法的收敛性和收敛速度
• 对牛顿法进行误差分析