数值分析复习.ppt
ReviewChap 1 数值计算中的误差数值计算中的误差 误差误差 误差限误差限 有效数字有效数字 用微分计算函数值误差用微分计算函数值误差 计算方法的数值稳定性计算方法的数值稳定性误差误差 误差限误差限 有效数字有效数字1)定义 1.1：称 为 的绝对误差(简称误差)。设 是准确值，是 的近似值2)定义 1.2：若 ，则称 是 x 的误差限。称单位量上的误差 为 x 的相对误差。3)定义 1.3：定义 1.4：若 ,则称 是 x 的相对误差限。4)定义 1.5：如果近似值 x 的误差限是它的某一位的半个单位，就称它准确到这一位。若该位到 x 左边第一位非零数字共有n 位，则称它有n 位有效数字。5)例1.5 题1.1 用微分计算函数值误差用微分计算函数值误差相对误差误差例1.9 已知 的近似值 x，一元函数值 的近似值为1)2)已知自变量误差和求二元函数值u=f(x,y)的误差 和例1.10,例1.11 3)和、差、积、商的误差例1.10,例1.11,题1.5 计算方法的数值稳定性计算方法的数值稳定性1)求根公式的数值稳定性2)递推法的数值稳定性数值计算中应注意的几个原则数值计算中应注意的几个原则避免相近数相减;避免小除数,大乘数;避免大数吃小数;采用数值稳定的算法;减少运算次数.题1.9,题1.10 题1.7 Chap 2 插值法与最小二乘法插值法与最小二乘法 多项式插值多项式插值 LagrangeLagrange插值公式插值公式 插值余项插值余项 NewtonNewton插值公式插值公式 HermiteHermite插值插值 分段插值分段插值 三次样条函数三次样条函数n 次多项式插值问题：次多项式插值问题：求作一个次数不超过 n 的多项式 ，使之满足插值条件f(x)的满足插值条件(2.1)的n次插值多项式插值区间插值节点已知 上的函数 在点上的函数值被插值函数Lagrange插值公式插值公式 插值余项插值余项求作一个1次已知函数 在点 上的函数值 ，多项式 ，使得1)线性插值2)抛物插值已知函数 在点 上的函数值 ，求作 一个2次多项式 ，使得3)n 次Lagrange插值满足n 次Lagrange插值基函数 的性质:是 n 次式;题2.1 题2.2 4)Lagrange插值余项 定理2.2：设 的 n+1阶导数 在 上存在，则其中 与 有关。例2.4,题2.5 Newton插值公式插值公式1)差商、差商的计算例2.5 2)Newton插值公式误差例2.7,例2.8题2.6,题2.7 差商与微商的关系Hermite插值插值3次Hermite插值3次Hermite插值基函数(插值基函数的性质)插值余项例2.9,题2.8,题2.10 混合型Hermite插值分段插值分段插值1)分段线性插值2)分段3次Hermite插值(如何确定其解析式,光滑性,误差估计?)题2.11,题2.12 3次样条函数次样条函数1)什么是3次样条函数,3次样条插值2)比较3次多项式插值(不含导数条件),分段3次Hermite插值,3次样条插值Chap 3 数值积分与数值微分数值积分与数值微分 机械求积公式机械求积公式 插值型求积公式插值型求积公式 复合求积公式复合求积公式 GaussGauss求积公式求积公式 数值微分数值微分机械求积公式机械求积公式求积节点求积系数例3.1,题3.1,题3.2 代数精度:若一个机械求积公式对准确成立,但对不准确成立,就说它具有m次代数精度.利用代数精度定义构造求积公式题3.11插值型求积公式插值型求积公式1)求积系数2)求积系数具有 n+1个求积节点的插值型求积公式至少具 有 n 次代数精度.3)中矩形公式、梯形公式、Simpson公式是插值型求积公式 (各自的代数精度).4)Newton-Cotes公式:一类节点等距分布的插值型求积公式.(n为奇数时,代数精度为n;n为偶数时,代数精度为n+1)梯形公式余项记Simpson公式余项复合求积公式复合求积公式 (复合求积的思想)1)复合梯形公式复合梯形求积公式的余项为2)复合Simpson公式复合Simpson求积公式的余项为题3.5,题3.6Gauss求积公式求积公式1)什么是Gauss求积公式?2)Gauss点的性质?定理定理3.4：是Gauss点的充分必要条件是以 为零点 的多项式 与所有次数不超过 n-1的多项式正交，即例3.7,例3.8,例3.9,例3.10,题3.9,题3.10,题3.11数值微分数值微分 在点 a 处以 h 为步长的向前差商 在点 a 处以 h 为步长的向后差商 在点 a 处以 2h 为步长的中心差商 例3.111)中心差商公式2)Richardson外推例3.12Chap 4 方程求根方程求根 不动点迭代法不动点迭代法 NewtonNewton迭代法迭代法 简化简化NewtonNewton迭代法迭代法 弦截法弦截法 NewtonNewton下山法下山法不动点迭代法不动点迭代法1)求 的根等价于求 的不动点 2)不动点迭代格式 3)迭代收敛条件 定理 4.1：设 是闭区间 上的压缩函数，则 在 中有唯一不动点 ，且对任意 ,迭 代公式(4.5)都收敛.(全局收敛)推论：设 ，且 1)总有 ;2)存在 ，使则定理4.1结论成立.(全局收敛)定理 4.3：设 在其不动点 附近有连续一阶导数，且 则存在 的某个领域 ，使得 ,迭代(4.5)均收敛.(局部收敛)迭代不收敛的条件 题4.44)迭代收敛速度记 ,若 ，且存在正常数 ，使 定义 4.3：,则称(4.5)为 p 阶收敛的.若 ，则称(4.5)是线性收敛的；若 ,则称(4.5)是平方收敛的.定理 4.4：若 在 的根 邻近有连续的 1阶导数，且 ,则当 时迭代公式(4.5)为线性收敛.若 在 邻近有连续的 2 阶导数，则当 时迭代公式(4.5)为平方收敛.例4.4,例4.5,例4.6,题4.2,题4.3,题4.5Newton迭代迭代求 近似根的Newton迭代公式:1)迭代控制条件2)收敛性单根，则当 时(4.11)平方收敛.定理 4.5：设 在 邻近二次连续可微，是 的3)Newton迭代与开方法例4.7,题4.8例4.8,题4.7简化简化Newton迭代法迭代法 弦截法弦截法 Newton下山法下山法1)简化Newton迭代法2)弦截法3)Newton下山法例4.9例4.10例4.11Chap 5 线性代数方程组数值解法线性代数方程组数值解法 迭代法迭代法 迭代法的收敛性迭代法的收敛性 GaussGauss消去法消去法 矩阵的矩阵的LULU分解及应用分解及应用 方程组的条件数与误差分析方程组的条件数与误差分析迭代法迭代法考虑线性方程组Jacobi迭代Gauss-Seidel迭代考虑线性方程组 A x=b,将 A 进行分解 A=D+L+U,Jacobi迭代的矩阵表示:Gauss-Seidel迭代的矩阵表示:或SOR迭代的矩阵表示:定理：定理：SOR方法收敛的必要条件是 .证明：假设SOR方法收敛，则有设 的特征值为 ，则而A=-L-UD迭代法的收敛性迭代法的收敛性迭代收敛基本定理：迭代收敛基本定理：对任意 和任意的初始向量 ,迭代公式(5.18)收敛的充要条件是 .例5.6,题5.3定理5.3：设G 是(5.18)的迭代矩阵，且它的某一种范数满足 ,则对任意的初值 ，迭代公式(5.18)均收敛.例5.5定理5.4：设 A 严格对角占优，则其 Jacobi 迭代公式和Gauss-Seidel 迭代公式均收敛.例5.7 题5.2 定理：定理：设 对称正定,且 ,则解 的SOR方法收敛.证明：SOR迭代法的迭代矩阵为设 是G的一个特征值，相应的特征向量为 x,则记 ,则 p 0.(因为 A 正定,D 亦正定)又记 ,则有 .且于是而故当 时 ,SOR方法收敛.特别的,当 时,SOR方法就是GS方法,从而当A是对称正定矩阵时,GS方法收敛.Gauss消去法消去法1)顺序Gauss消去法2)列主元Gauss消去法例5.8 题5.7例5.10 题5.7矩阵的矩阵的LU分解及应用分解及应用 A=L U,其中L是单位下三角阵,U是上三角阵1)计算矩阵行列式2)解方程组3)求矩阵的逆例5.11 题5.9方程组的条件数与误差分析方程组的条件数与误差分析 定义5.7:称数 为矩阵 A 的关于解方程 1 组 的条件数.例5.13 题5.10 设 x 是方程组 的精确解,y 是其近似解.称为y 的剩余向量,则成立不等式(定理5.7)当方程组良态时,可以用 来估计近似解 y 的误差.Chap 7 常微分方程初值问题数值解法常微分方程初值问题数值解法 EulerEuler法法 改进改进EulerEuler法法 Runge-KuttaRunge-Kutta法法 收敛性与稳定性收敛性与稳定性(7.1)(7.2)数值求解一阶常微分方程的初值问题:Euler公式:(步进式,单步方法,显式格式)记 ,则Euler公式的局部截断误差:总体截断误差:(Euler法是1阶方法)Euler法的三种分析解释:差商逼近微商,数值积分,Taylor 级数法隐式Euler公式:(单步法,隐式格式,1阶方法)两步隐式Euler公式:(两步方法,显式格式,2阶方法)梯形公式:改进Euler公式:或(2阶方法)经典4阶R-K公式:(4阶方法)例7.1 例7.3 例7.4 题7.1 题7.2如何讨论数值方法的阶?!收敛性与稳定性收敛性与稳定性 定理7.1：设 关于 y 满足 Lipschitz条件，是 1 中任意固定的点(T 0 是常数).则对Euler法的总 1体截断误差有 1)收敛性题7.52)稳定性对模型方程 ,下列方法的稳定性区域为显式Euler公式隐式Euler公式或改进Euler公式梯形公式经典4阶R-K法题7.6The road to wisdom?Well,its plain and simple to express:Errand errand err againbut lessand lessand lessPIET HEIN,Grooks(1966)
