第5章讲 常用数值计算算法及其程序设计.ppt

5.5.1 牛顿迭代法 (1) 用方程f(x)=0根的初始近似值x0带入牛顿迭代公式求得x1，用x1带入牛顿迭代公式求得x2 如此重复可得到根的近似值序列x0,x1,x2,…xn 。 (2) 每求出一个新的近似值xn+1后均判断|f(xn+1)|? 或|xn+1-xn|是否成立，若成立则xn+1是所要求解的方程f(x)=0在x0附近、满足允许误差?的一个近似实根。 算法描述 5.5.1 牛顿迭代法 采用牛顿迭代法求方程-3x3+4x2-5x+6=0在1.0附近的一个近似实根，允许求得的近似根在小数点后第6位存在误差。 #include stdio.h #include math.h int main(void) { double x,x1,eps=1e-6,f,f1; x=1.0; do{ x1=x; f=6-x1*(5-x1*(4-3*x1)); f1=-5+x1*(8-9*x1); x=x1-f/f1; f=6-x*(5-x*(4-3*x)); }while(fabs(f)=eps fabs(x-x1)=eps); printf(“x=%f”,x); } 程序实现 5.5.1 牛顿迭代法 #include stdio.h #include math.h int main(void) { double x,s1, s2=1; do{ scanf(“%lf”,x); if(x=0) 例 用牛顿迭代公式求当| sn+1- sn |≤10-6时x 的平方根，x从键盘上输入 5.5.1 牛顿迭代法 printf(“x≤0\n”)； }while(x=0); do{ s1=s2; s2=0.5*(s1+x/s1); }while(fabs(s2-s1)=1e-6); printf ( “\n sqrt(%lf )=%lf\n”,x,s2); } 5.5.2 二分法和弦截法 5.5.2 二分法和弦截法 ⑴ 找到x轴上的两个端点a和b使得方程f(x)=0在[a,b]中只有一个根；判断a和b是否为方程的近似根，若是立即结束计算； ⑵ 若a、b均不是近似根则计算[a,b]的中心点c=(a+b)/2，判断c是否为方程的近似根，若是则立即结束计算； ⑶ 若c不是近似根且a?b则将[a,b] 区间调整到[a,c]或[c,b]（即将[a,b] 的长度缩小一半）并确保方程在调整后的[a,b] 中仍有一个实根 ；重复第⑵(3)步直到找到根为止。 二分法算法描述 5.5.2 二分法和弦截法 计算方程-3x3+4x2-5x+6=0的一个近似实根，允许所求得的近似根在小数点后第6位上有误差。 #include stdio.h #include math.h double f(double x) { return 6-x*(5-x*(4-3*x)); } int main(void) { double a,b,c,x,eps=1e-6; do{ printf(“No one root ”); scanf(“%lf%lf”,a,b); }while(f(a)*f(b)0); 二分法程序实现 * * 第5章 常用数值计算算法及其程序设计 主要内容 5.1 素数判断 5.2 求最大公约数 5.3 穷举法求满足条件的一组解 5.4 级数近似计算 5.5 一元非线性方程求根 *5.6 定积分近似计算 5.1 素数判断 素数 如果一个大于1的正整数n只能被1和n自身整除，则称n为素数（prime）。 例如：2是素数，8不是素数 5.1 素数判断 5.1.1 最简单素数判断算法 5.1.2 改进后的素数判断算法 5.1.1 最简单素数判断算法 算法描述 若n2且n不能被2～n-1范围内的任一个整数整除，n就是素数；否则n不是素数；若发现n不是素数，立即停止后续判断。 程序实现 for (t=1,i=2;tin; i++) if(n%i==0)t=0; if(t)printf(“%d is prime”,n); 5.1.2 改进后的素数判断算法 算法描述 如果n2且n不能被2～sqrt(n)之间的所有整数整除，n就是素数。 程序实现 r=sqrt(n); for(t=1,i=2; ti=r; i++) if(n%i==0) t=0;