数值计算方法及算法

数值计算方法及算法第1页，课件共98页，创作于2023年2月第0章绪论第2页，课件共98页，创作于2023年2月

数学建模数值计算实际问题数学问题近似解什么是数值计算方法？什么是“好的”数值计算方法？误差小─误差分析耗时少─复杂度分析抗干扰─稳定性分析第3页，课件共98页，创作于2023年2月误差的类型 绝对误差＝真实值－近似值 相对误差＝绝对误差／真实值误差的来源 原始误差、截断误差、舍入误差输入计算输出真实值近似值第4页，课件共98页，创作于2023年2月一些例子： 计算地球的体积 计算 计算如何减小计算误差？

选择好的算法、提高计算精度范数的定义 满足非负性,齐次性,三角不等式的实函数第5页，课件共98页，创作于2023年2月常用的向量范数常用的矩阵范数矩阵的谱半径例：计算矩阵 的范数和谱半径。例：范数在误差估计中的应用第6页，课件共98页，创作于2023年2月第1章插值第7页，课件共98页，创作于2023年2月函数逼近 用未知函数f(x)的值构造近似函数φ(x)。要求误差小、形式简单、容易计算。常用的函数逼近方法插值：φ(xi)=yi,i=0,1,…,n.拟合：||φ(x)-f(x)||尽可能小通常取

φ(x)=a0φ0(x)+…+anφn(x)，其中{φi(x)}为一组基函数。第8页，课件共98页，创作于2023年2月多项式插值 给定平面上n+1个插值点(xi,yi),构造n次多项式φ(x),满足φ(xi)=yi,i=0,1,…,n.第9页，课件共98页，创作于2023年2月单项式插值第10页，课件共98页，创作于2023年2月Lagrange

插值第11页，课件共98页，创作于2023年2月Newton

插值第12页，课件共98页，创作于2023年2月差商表012…n…0…1…2……......nk阶差商第13页，课件共98页，创作于2023年2月差商的性质以x0,…,xn为节点的n次插值多项式φ(x)的首项系数等于f[x0,…,xn]。 证明：分别以x0,…,xn-1和x1,…,xn为节点构造n-1次插值多项式φ1(x)和φ2(x)，则有

对n用归纳法。f[x0,…,xn]与x0,…,xn的顺序无关。第14页，课件共98页，创作于2023年2月误差估计：证明：设 ，则

有n+2个零点。 根据中值定理，存在于是 。第15页，课件共98页，创作于2023年2月Hermite插值 给定平面上n+1个插值点(xi,yi,mi),构造2n+1次多项式φ(x),满足φ(xi)=yi,φ’(xi)=mi,i=0,1,…,n.第16页，课件共98页，创作于2023年2月单项式

基函数Lagrange

基函数第17页，课件共98页，创作于2023年2月误差估计：证明：设 ，则

有2n+3个零点。根据中值定理，存在

于是 。第18页，课件共98页，创作于2023年2月Runge现象：并非插值点取得越多越好。解决办法：分段插值第19页，课件共98页，创作于2023年2月三次样条插值 给定平面上n+1个插值点(xi,yi),构造分段三次多项式φ(x),满足φ(xi)=yi,φ’(x)可微，φ”(x)连续。第20页，课件共98页，创作于2023年2月第2章数值微分和数值积分第21页，课件共98页，创作于2023年2月数值微分差商法 向前差商 向后差商 中心差商第22页，课件共98页，创作于2023年2月插值法

在x附近取点(xi,f(xi))构造插值多项式φ。样条法

在x附近取点(xi,f(xi))构造样条函数φ。

f’(x)≈φ’(x)第23页，课件共98页，创作于2023年2月例：用中心差商公式计算f’(xi)。例：用向后差商公式计算f’’(0.2),

f’’(0.4)。x0.00.10.20.30.4f(x)1.71.51.62.01.9f’(x)f”(x)x0.00.10.20.30.4f(x)0.8187310.9048371.0000001.1051711.221403f’(x)第24页，课件共98页，创作于2023年2月例：设xi=x0+i*h,i=1,...,n。计算φ’(xk)。解：第25页，课件共98页，创作于2023年2月误差估计 前后差商

中心差商

插值微分第26页，课件共98页，创作于2023年2月数值积分插值法第27页，课件共98页，创作于2023年2月若积分公式对任意m次多项式都取等号，则称积分公式具有至少m阶的代数精度。插值型积分公式的代数精度≥n。当积分节点x0,...,xn给定时，

代数精度≥n的积分公式唯一。第28页，课件共98页，创作于2023年2月例：设xi=a+i*h,i=0,...,n,h=(b-a)/n。

计算Newton-Cotes积分解：第29页，课件共98页，创作于2023年2月特别，当n=1,2时，积分公式分别称为梯形公式Simpson公式na1a2a3a4a51½½21/64/61/631/83/83/81/847/9032/9012/9032/907/90第30页，课件共98页，创作于2023年2月误差估计特别，梯形公式和Simpson公式的误差为 代数精度＝1

代数精度＝3第31页，课件共98页，创作于2023年2月复化数值积分第32页，课件共98页，创作于2023年2月梯形公式Simpson公式第33页，课件共98页，创作于2023年2月Richardson外推法

我们要计算 假设 则 有比和更高的精度。误差估计第34页，课件共98页，创作于2023年2月Romberg积分公式 等分的梯形公式，瑕积分重积分Gauss-Legendre积分第35页，课件共98页，创作于2023年2月定理：假设 满足则插值积分公式具有2n+1阶的代数精度。证明：课本21页性质1.3：若f(x)为m次多项式，则f[x0,...,xn,x]为m-n-1次多项式。第36页，课件共98页，创作于2023年2月求多项式空间在内积

下的标准正交基。解法1：对任意基作Gram-Schmidt正交化。解法2：对任意度量方阵作相合对角化。解法3：求解正交关系的线性方程组。解法4：Legendre多项式第37页，课件共98页，创作于2023年2月第3章曲线拟合的最小二乘法第38页，课件共98页，创作于2023年2月曲线拟合对区间I上的连续函数

f，

构造特定类型的函数φ

使φ≈f。对离散数据序列(xi,yi),i=1,2,…,m，

构造特定类型的函数φ

使φ(xi)≈yi。最小二乘法求φ

使 最小。求φ

使 最小。第39页，课件共98页，创作于2023年2月多项式拟合 其中

是标准正交基， 。

求 使 最小。第40页，课件共98页，创作于2023年2月奇异值分解Moore-Penrose广义逆矛盾方程组的解第41页，课件共98页，创作于2023年2月其他类型的离散数据拟合

第42页，课件共98页，创作于2023年2月第4章非线性方程求根第43页，课件共98页，创作于2023年2月问题求f(x)=0在区间[a,b]内的实根求f(x)=0在x0附近的一个实根求f(x)=0在x0附近的一个复根求多项式f(x)=0的所有复根求非线性方程组的根方法用近似函数φ(x)的根逼近f(x)的根。第44页，课件共98页，创作于2023年2月二分法已知f(a)f(b)<0，设c=(a+b)/2。若f(a)f(c)<0则根在[a,c]内；若f(a)f(c)>0则根在[b,c]内。当|f(c)|<ε或|b-a|<ε时，输出c。迭代步数：O(log2ε)第45页，课件共98页，创作于2023年2月不动点

当|φ’(x)|≤L<1时，|xk+1-α|≤L|xk-α|。当|xn+1-xn|<ε时，输出xn。迭代步数：O(logLε)Lipschitz常数线性收敛第46页，课件共98页，创作于2023年2月Newton法（一阶Taylor展开） 当|f(xk)|<ε或|xk+1-xk|<ε时，输出xk+1。 迭代步数：O(loglogε)二次收敛第47页，课件共98页，创作于2023年2月Newton法（p重根情形）第48页，课件共98页，创作于2023年2月用Newton迭代法求f(z)=z3−2z+2的根。当初值分别位于红、蓝、绿色区域时，迭代收敛到三个根。当初值位于黑色区域时，迭代陷入死循环0→1→0。图片引自JohnHubbard,DierkSchleicher,ScottSutherland,Howtofindallrootsofcomplexpolynomials,Inventionesmathematicae146,1-33(2001).第49页，课件共98页，创作于2023年2月弦截法（线性插值） 当|f(xk)|<ε或|xk+1-xk|<ε时，输出xk+1。 迭代步数：O(loglogε)第50页，课件共98页，创作于2023年2月弦截法的收敛速度第51页，课件共98页，创作于2023年2月Newton法解非线性方程组求 的所有复根

等价于求x1,…,xn使f(t)=(t-x1)…(t-xn)。第52页，课件共98页，创作于2023年2月其他求根方法 Brent （反插值x=φ(y)）

Halley （二阶Taylor展开）

Muller （二次插值）

有理插值……第53页，课件共98页，创作于2023年2月第5章解线性方程组的直接法第54页，课件共98页，创作于2023年2月问题：求解n元线性方程组AX=B。方法？速度？精度？存储？下三角方程组上三角方程组

n(n-1)/2次加减法，n(n+1)/2次乘除法。第55页，课件共98页，创作于2023年2月Gauss消元法解一般方程组

(2n3+3n2-5n)/6次加减法，

(n3+3n2-n)/3次乘除法。第56页，课件共98页，创作于2023年2月追赶法解三对角方程组

3n-3次加减法，5n-4次乘除法。第57页，课件共98页，创作于2023年2月线性方程组解的精度矩阵条件数第58页，课件共98页，创作于2023年2月Gauss消元法的实质是LU分解存在性？A的顺序主子式≠0。唯一性？L1U1=L2U2L1-1L2=U1U2-1对角精确度？A-1b的相对误差≈(L,U,b)的相对误差×cond(L)×cond(U)。第59页，课件共98页，创作于2023年2月Dolittle分解Courant分解第60页，课件共98页，创作于2023年2月全/列/行主元分解LDLT分解、Cholesky分解第61页，课件共98页，创作于2023年2月QR分解第62页，课件共98页，创作于2023年2月SVD分解Givens旋转 Householder反射第63页，课件共98页，创作于2023年2月第6章解线性方程组的迭代法第64页，课件共98页，创作于2023年2月Jacobi迭代Gauss-Seidel迭代第65页，课件共98页，创作于2023年2月迭代法解线性方程组AX=B AXk+1–B=C(AXk–B) C称为Conditioner，满足ρ

(C)<1或||C||<1 通常取C=I–AÃ-1，其中Ã≈A，于是Xk+1=Xk–Ã-1(AXk–B)第66页，课件共98页，创作于2023年2月Jacobi迭代：Ã=D定理：A行对角优、或A列对角优

Jacobi迭代收敛。Gauss-Seidel迭代：Ã=D+L定理：A行对角优、或A列对角优、或A正定

Gauss-Seidel迭代收敛。第67页，课件共98页，创作于2023年2月松弛迭代：Ã=w-1D+L定理：松弛迭代收敛0<w<2定理：A正定且0<w<2

松弛迭代收敛Newton迭代求A-1：Xk+1=2Xk–XkAXk第68页，课件共98页，创作于2023年2月第7章计算矩阵的特征值

和特征向量第69页，课件共98页，创作于2023年2月问题1：求复方阵的模最大(最小)特征值。方法：幂法、反幂法问题2：求复方阵的所有特征值。方法：QR迭代问题3：求Hermite方阵的所有特征值。方法：Jacobi方法第70页，课件共98页，创作于2023年2月幂法当A只有一个模最大的特征值λmax，并且x0与λmax的特征向量amax不正交时当A的模最大的特征值都相同时，以上迭代仍然收敛。第71页，课件共98页，创作于2023年2月当A的模最大的特征值各不相同时，可以选取数s使A-sI的模最大的特征值只有一个。当A恰有m个模最大的特征值时，有 R的特征值就是A的模最大的特征值。第72页，课件共98页，创作于2023年2月反幂法当A只有一个模最小的特征值λmin，并且x0与λmin的特征向量amin不正交时计算A-sI的模最小的特征值等价于计算A的最接近s的特征值。第73页，课件共98页，创作于2023年2月QR迭代利用QR分解，酉相似A为上三角。QR迭代的本质是幂法当 时，QR迭代收敛。可对A-sI作QR分解，加速收敛。第74页，课件共98页，创作于2023年2月Jacobi方法通过Givens旋转，逐渐减小非对角元。本质是2阶Hermite方阵的酉相似。Jacobi方法具有2阶收敛速度。第75页，课件共98页，创作于2023年2月复矩阵的奇异值分解A=UΣV一般方法AHA=VHΣ2V或AAH=UΣ2UHQR迭代Jacobi方法

计算2阶方阵的SVD第76页，课件共98页，创作于2023年2月第8章常微分方程数值解第77页，课件共98页，创作于2023年2月问题：求解一阶常微分方程的初值问题：解法：化微分方程为积分方程第78页，课件共98页，创作于2023年2月Euler折线法向前Euler公式向后Euler公式 Picard迭代中心Euler公式梯形公式 改进的 Euler公式第79页，课件共98页，创作于2023年2月Runge-Kutta方法选取{xi,cij}使yr

有最高精度p，即r1,2,3,45,6,78,910,11,...pp=rp=r-1p=r-2p≤r-2第80页，课件共98页，创作于2023年2月Runge-Kutta方法的误差估计设满足Lipschitz条件设满足初值误差截断误差整体误差第81页，课件共98页，创作于2023年2月线性多步法(*)

其中φ(t)为f(t,y(t))的q次插值多项式。当xn,…,xn-q为插值节点时，(*)称为显式Adams公式。当xn+1,…,xn+1-q为插值节点时，(*)称为隐式Adams公式。第82页，课件共98页，创作于2023年2月一阶常微分方程组的初值问题：解法：同一阶常微分方程的初值问题。第83页，课件共98页，创作于2023年2月高阶常微分方程的初值问题解法：令化方程为第84页，课件共98页，创作于2023年2月单步法 (*)收敛性稳定性

将(*)应用于方程y’=y，得yn+1=E(h)yn。

当|E(h)|<1时，称(*)绝对稳定的。

称{复数h:|E(h)|<1}为绝对稳定区域。称{实数h:|E(h)|<1}为绝对稳定区间。第85页，课件共98页，创作于2023年2月复 习第86页，课件共98页，创作于2023年2月第0章绪论误差的定义向量的范数矩阵的范数、条件数、谱半径第87页，课件共98页，创作于2023年2月第1章插值Lagrange插值差商、Newton插值Hermite插值插值公式的截断误差Runge现象样条函数第88页，课件共98页，创作于2023年2月第2章数值微分和数值积分