数值计算方法复习.ppt

Review 复习,1 Preliminaries,The Program for Solving Engineering Problem,Engineering Problem,Academic Model,Practical Model,Resolvable Model,Computer Program,Results,Numerical Method,Analysis Method,Computer Language,Theory for Engineering,The Concept of Numerical analysis,Numerical analysis is the study of algorithms for the problems of continuous mathematics-Lloyd N.Trefethen“计算数学”就是研究在计算机上解决数学问题的理论和数值方法。,数值计算方法是一门根据计算机特点，研究通过计算机求工程问题满足精度要求的近似解的学科。,The Way of Numerical Methods,Dispersing(离散化)只计算定义域上有限个变量的值，而不是所有函数变量的值,Approach(逼近)用简单函数y(x)近似替代函数f(x),但误差E(x)=f(x)-y(x)要满足精 度要求。,Deduce by degrees(递推)递推是将一个复杂的计算过程转化为简单过程的多次重复的数学方法。,The Absolute Error&.Relative Error,The Absolute Error:Ep=|p-p|绝对误差The Relative Error:Rp=|p-p|/|p|相对误差,Significant Digits（有效数字）,|p-p|/|p|10-d/2The number p is said to approximate p to d significant digits if d is the largest positive integer,1、选用数值稳定性好的算法2、相近两数避免相减3、绝对值相对太小的数不宜作除数4、警惕大数吃小数5、简化计算方法，尽量减少过程误差,Loss of Significance(精度损失）,2 The Solution of Nonlinear Equations f(x)=0,The methods,(1)Find the area for the root,(2)Approach,2.1 Iteration for Solving x=g(x)迭代法,迭代函数,迭代序列,迭代收敛,Theorem 2.1,convergence,divergence,Theorem 2.2,Theorem 2.3,P:Attractive fixed Point,P:Repelling fixed Point,2.2 Bracketing Methods for Locating a Root,所谓二分法，是使用对分区间的方法，保留有根区间，舍去无根区间，并且如此不断地对分下去，以逐步逼近方程根的方程求解方法,y=f(x),x,y,0,x*,b,a,f(a),f(b),x1=(a+b)/2,f(a+b)/2)=f(x1),xk,The Bisection Method of Bolzano,Theorem 2.4 Bisection Theorem,Convergence of the False Position Method,y=f(x),x,y,0,x*,b,a,f(a),f(b),xk,2.3Newton-Raphson and Secant Methods(牛顿迭代法和弦割法),是否可以将它转换成线性方程进行求解？如何转化？,The Geometric Construction for Newton-Raphson,Corollary 2.2(Newtons Iteration for finding Square Roots)(求平方根的牛顿迭代法）,牛顿迭代法的收敛性判断,定理3证明,=？,The Convergence of Newton-Raphson Iteration,The Division-by-Zero Error,0,Definition 2.4(Order of a Root),Speed of Convergence,Definition 2.5(Order of Convergence),Theorem 2.6(Convergence Rate for Newton Raphson Iteration),The Secant Methods,Example 2.16(Secant Method at a Simple Root),Accelerated Convergence,Comparison of the Speed of Convergence,3 The Solution of Linear Systems AX=B,主要内容,高斯消去法三角分解法追赶法平方根法,雅可比迭代法高斯赛德尔迭代法向量与矩阵范数谱半径定义迭代法收敛判断,=,=,=,平方根法的解法,=,步骤,雅可比迭代法,高斯赛德尔迭代法,4 向量与矩阵范数,常用向量范数,矩阵范数,常见矩阵范数,举例,谱半径定义,迭代法收敛判断,收敛条件 雅可比迭代法 高斯赛德尔迭代法 超松弛迭代法,收敛,收敛,收敛,收敛,A阵为对角占优矩阵,收敛,收敛,A阵为对称正定矩阵,收敛,当 时收敛,A阵为正定矩阵的充分必要条件是A阵的顺序主子式大于零。,基于MATLAB的线性方程组,矩阵除法,矩阵除法举例,a=-0.002 2 2 1 0.78125 0 3.996 5.5625 4b=0.4 1.3816 7.4178X=ab,x=1.9273-0.6985 0.9004,矩阵除法举例,a=-0.002 2 2 1 0.78125 0 3.996 5.5625 4b=0.4 1.3816 7.4178X=ab,x=1.9273-0.6985 0.9004,平方根法,a=4 2-2;2 2-3;-2-3 14L=chol(a),L=2 1-1 0 1-2 0 0 3,MATLAB实现：,Jacobi.mfunction y=jacobi(a,b,x0)D=diag(diag(a);U=-triu(a,1);L=-tril(a,-1);B=D(L+U);f=Db;y=B*x0+f;n=1;while norm(y-x0)=1.0e-6x0=y;y=B*x0+f;n=n+1;endyn,a=10-1 0;-1 10-2;0-2 10;b=9;7;6;jacobi(a,b,0;0;0),y=0.9958 0.9579 0.7916n=11ans=0.9958 0.9579 0.7916,MATLAB实现：,Jacobi.mfunction y=jacobi(a,b,x0)D=diag(diag(a);U=-triu(a,1);L=-tril(a,-1);B=D(L+U);f=Db;y=B*x0+f;n=1;while norm(y-x0)=1.0e-6x0=y;y=B*x0+f;n=n+1;endyn,a=10-1 0;-1 10-2;0-2 10;b=9;7;6;jacobi(a,b,0;0;0),y=0.9958 0.9579 0.7916n=11ans=0.9958 0.9579 0.7916,seidel.mfunction y=seidel(a,b,x0)D=diag(diag(a);U=-triu(a,1);L=-tril(a,-1);G=(D-L)U;f=(D-L)b;y=G*x0+f;n=1;while norm(y-x0)=1.0e-6x0=y;y=G*x0+f;n=n+1;endyn,a=10-1 0;-1 10-2;0-2 10;b=9;7;6;seidel(a,b,0;0;0),y=0.9958 0.9579 0.7916n=7ans=0.9958 0.9579 0.7916,4 Interpolation and Polynomial Approximation,插值法 Interpolation,插值概念与基础理论 Introduction 插值多项式的求法,插值概念与基础理论,概念 在工程实践和科学实验中，常常需要从一组实验观测数据揭示自变量x与因变量y之间的关系，一般可以用一个近似的函数关系式yf(x)来表示,如何确定插值多项式？,插值余项,对t求导，k(x)看成常数,4.3 Lagrange Approximation,当 n=1 时,称线性插值,当 n=2 时,抛物线插值,MATALAB实现Lagrange插值,%lagrange insertfunction y=lagrange(x0,y0,x)n=length(x0);m=length(x);for i=1:m z=x(i)s=0.0 for k=1:n p=1.0;for j=1:n if j=k p=p*(z-x0(j)/(x0(k)-x0(j);end end s=p*y0(k)+s;end y(i)=s;end,x=0.4:0.1:0.8;y=-0.916291-0.693147-0.510826-0.356675-0.223144;lagrange(x,y,0.54),ans=-0.6161,22 差商与牛顿基本括值多项式,前面构造的拉格朗日插值多项式，其形式具有对称性，既便于记忆，又便于应用与编制程序但是，由于公式中的 都依赖于全部插值节点，在增加或减少节点时，必须全部重新计算为克服这个缺点，插值多项式可以如何构造？,这种形式的插值多项式称为n次牛顿插值多项式,Newton Polynomials,利用MATALAB进行插值计算,一维插值,分段线性插值,分段抛物插值,分段低次插值,分段低次插值,Runge现象产生,x=-5:1:5;y=1./(1+x.2);x0=-5:0.1:5;y0=lagrange(x,y,x0);y1=1./(1+x0.2);plot(x,y)plot(x0,y0,-r),分段线性插值,分段抛物插值,3.1 分段线性插值与分段抛物插值,MATALAB实现Lagrange插值,%lagrange insertfunction y=lagrange(x0,y0,x)n=length(x0);m=length(x);for i=1:m z=x(i)s=0.0 for k=1:n p=1.0;for j=1:n if j=k p=p*(z-x0(j)/(x0(k)-x0(j);end end s=p*y0(k)+s;end y(i)=s;end,x=0.4:0.1:0.8;y=-0.916291-0.693147-0.510826-0.356675-0.223144;lagrange(x,y,0.54),ans=-0.6161,利用MATALAB进行插值计算,一维插值,利用MATLAB软件进行插值,高维插值,气旋变化情况可视化,5 Curve Fitting,曲线拟合的基本概念,5.1 Least-squares Line 最小二乘拟合曲线,实验数据带有误差实验数据很多,最小二乘法问题提法:,在曲线拟合时，如果所选择的拟合函数在所有数据点处的偏差的平方和最小，则称这种拟合方法为最小二乘法。,Theorem 定理 5.1(Least-squares Line),The Power Fit y=AxM,y=AxM,5.2 Curve Fitting,Data Linearization Method for y=CeAx,Nonlinear Least-squares Method for y=CeAx,Interpolation by Spline Function,分段低次插值,Runge现象产生,x=-5:1:5;y=1./(1+x.2);x0=-5:0.1:5;y0=lagrange(x,y,x0);y1=1./(1+x0.2);plot(x,y)plot(x0,y0,-r),分段线性插值,分段抛物插值,3.1 分段线性插值与分段抛物插值,三次样条插值,三次样条插值函数求法,边界条件：,三次样条插值函数简化计算方法,由,确定两个积分常数,6 Numerical Differentiation,6.1 导数的近似值,6.1.2 中心差分公式,6.1.4 Richardson 外推法,6.2 数值差分,6.2.1更多的中心差分公式,6.2.2 误差分析,利用插值多项式构造微分公式,6.2.3 拉格朗日多项式微分,6.2.3 牛顿多项式微分,6.2.4 利用三次样条插值函数构造微分公式,Related Example,Example 6.2(P315);Exercises 4(P325);Algrorithms and Programs 2(P328);,Example 6.5(P332);Exercises 3,8(P339,340);Algrorithms and Programs 1(P341);,7 Numerical Integration,构造数值积分公式的基本方法与有关概念,7.1 Introduction to Quadrature,数值积分余项,E(Pi)=Rif,数值积分公式的精度,例题,The trapezoidal rule n=1,Simpsons rule(n=2),Simpsons 3/8 rule n=3,Booles rule,n=4,牛顿科茨公式余项,梯形公式余项：,辛普森公式余项：,科茨公式余项：,代数精度？,当积分区间比较大时，精度？,7.2 Composite Trapezoidal and Simpsons Rule,Composite Trapezoidal Rule,Composite Simpson Rule,Composite Bools Rule,复合牛顿科茨公式余项,复合梯形公式余项,复合辛普森公式余项,复合布尔公式余项,例题,7.3 Recursive Rules and Romberg Integration,Recursive Trapezoidal Rule,Romberg Integration,数值积分在MATLAB中的应用,quad 采用递推自适应Simpson法计算积分;精度较高，较常用quadl采用递推自适应Lobatto法计算积分;精度高，最常用trapz 采用梯形法计算积分;速度快，精度差cumtrapz 采用梯形法计算一个区间上的积分曲线;速度快，精度差Fnint 利用样条函数求不定积分；与spline、ppval配合使用；主要对付“表格”函数的积分,【例 题】,（1）符号解析法syms x;IS=int(exp(-x*x),x,0,1)vpa(IS)IS=1/2*erf(1)*pi(1/2)ans=.74682413281242702539946743613185,（2）MATLAB指令quad和quadl求积,fun=inline(exp(-x.*x),x);Isim=quad(fun,0,1),IL=quadl(fun,0,1)Isim=0.7468IL=0.7468,（3）10参数Gauss法,Ig=gauss10(fun,0,1)Ig=0.7463,xx=0:0.1:1.5;ff=exp(-xx.2);pp=spline(xx,ff);int_pp=fnint(pp);Ssp=ppval(int_pp,0,1)*-1;1 Ssp=0.7468,（3）样条函数积分法,（4）SIMULINK 积分法,9 Solution of Differential Equations,简单的一阶常微分方程初值问题,欧拉方法,欧拉公式的截断误差与精度分析,后退（隐式）欧拉法,改进欧拉法(休恩方法）,9.4 Taylor Series Method,龙格-库塔方法,这就是欧拉公式,经典龙格-库塔法,通过MATLAB解常微分方程,Runge-Kutta 法:ODE解函数:ode23、ode45、ode113、ode15s、ode23s 参数选择函数：odeset、odeget 输出函数：odeplot、odephas2、odephas3、odeprint,例 y=-2y+2x2+x其中（0X0.5),y(0)=1,fun.mfunction f=fun(x,y)f=-2*y+2*x2+2*x;x,y=ode23(fun,0,0.5,1);x,y=ode23(fun,0:0.1:1.0,1),符号解法,dsolve(Df=f+sin(t),f(pi/2)=0)ans=-1/2*cos(t)-1/2*sin(t)+1/2*exp(t)/(cosh(1/2*pi)+sinh(1/2*pi)dsolve(D2y=-a2*y,y(0)=1,Dy(pi/a)=0)ans=cos(a*t),This Class Is Over,Thanks for Your Attention!,