[理学]第8章常用算法.ppt

本 章 要 点 数值积分: 矩形法 梯形法 辛普生法 解一元方程(近似求解) 迭代法 牛顿迭代法 二分法 弦截法 求函数的最大值以及打印图案与仿真 概要 通过前面的学习我们初步具备了编写简单程序的能力. 我们知道: 程序=数据结构+算法 本章我们继续学习常用算法基础 要求: 切实掌握基本算法的设计方法和技巧,并能在此基础上举一反三,也就是掌握各类算法的原理和基本规律. 8.1 数值积分 求一个函数F(x)在区间[a, b]上的定积分: 其几何意义就是求曲线F(x)与直线X=A,Y=0,X=B所围成的曲边梯形面积. 8.1 数值积分 为了求出近似面积,可将[a, b]区间分成若干个小区间,每个区间的宽度为(b-a)/n , n为区间个数. 首先求出每个小曲边梯形面积的近似值, 然后将n个小曲边梯形面积相加起来就是总面积的近似值. N的取值愈大, 近似程度就愈高. 8.1 数值积分 求近似小曲边梯形面积的方法有如下三种: 用小矩形代替小曲边梯形,求出单个小矩形的面积,然后累加之; 用小梯形代替小曲边梯形; 在小区间范围内,用一个抛物线来代替该区间的F(x),然后求出由该抛物线与x=a+(i-1)h, y=0, x=a+ih 围成的小曲边梯形面积. 8.1 数值积分 8.1.1 矩形法 先求出第一个小矩形的面积:底为: (b-a)/n , 高为: f(a) 或 f(a+h) 第i 个小矩形的面积:Si=h×f(a+(i-1)h) 8.1.1 矩形法程序设计举例 READ(*,*) A, B, N X=A H=(B-A)/N F0=EXP(X) S=0.0 DO 10,I=1,N SI=F0*H S=S+SI X=X+H F0=EXP(X) 10 CONTINUE WRITE(*,100) A,B,N WRITE(*,200) S 100 FORMAT(1X,A=,F10.3,3X,B=,F10.3,3X,N=,I4) 200 FORMAT(1x, S=,F15.8) END 8.1 数值积分 8.1.2 梯形法(用小梯形代替小矩形) 先求出第一个小梯形的面积:上底为: f(a) ,下底为: f(a+h) , 高: h 第i 个小梯形的面积:Si=h×(f(a+ih)+f(a+(i-1) h))/2 READ(*,*) A,B,N X=A H=(B-A)/N S=0.0 DO 10,I=1,N SI=(SIN((I-1)*H)+SIN(I*H))*H/2.0 或者是： si=(sin((i-1)*h+x)+sin((i*h)+x))*h/2  S=S+SI 10 CONTINUE WRITE(*,100) A, B, N WRITE(*,200) S 100 FORMAT(1X,A=,F10.3,3X,B=,F10.3,3X,N=,I4) 200 FORMAT(1X,S=,F15.8) END READ(*,*) A,B,N H=(B-A)/N S=0.0 F1=SIN(A) DO 10,I=1,N F2=SIN(A+I*H) SI=(F1+F2)*H/2.0 S=S+SI F1=F2 10 CONTINUE WRITE(*,100) A, B, N WRITE(*,200) S 100 FORMAT(1X,A=,F10.3,3X,B=,F10.3,3X,N=,I4) 200 FORMAT(1X,S=,F15.8) END 8.1 数值积分 8.1.2 梯形法我们也可以用n个小梯形面积的代数和公式, 就是设f0、f1、f2、f3…fn 分别是x等于x0、 x1、x2、x3…xn时函数F(X)的值。 8.1 数值积分 8.1.2 梯形法 8.1 数值积分 8.1.3 辛普生法(Sinpson) 基本思想： 在一个小区间内用一抛物线f1(x)代替原来的曲线f(x) 抛物线f1(x)的确定：取a, b中点c,其坐标为((b+a)/2, 0) 通过c点可求出F(c).也就是通过f(a)f(b)f(c)三点作出唯一一条抛物线f1(x)。可以证明f1(x)等于： 由上面的公式可以看出: X=a时, f1(a)=f(a); X=b时,f1(b)=f(b); X=c时,f1(c)=f(c).因此在区间[a, b]的定积分（1）可由（2）代替 根据抛物线定积分求值公式(已知抛物线上三点)： 8.1 数值积分 8.1.3 辛普生法(Sinpson) 我们可