计算方法实验指导书(无例程)

第一章 绪论一、主要要求通过实验，认真理解和体会数值计算的稳定性、精确性与步长的关系。

二、主要结果回顾：1、算法：电子计算机实质上只会做加、减、乘、除等算术运算和一些逻辑运算，由这些基本运算及运算顺序规定构成的解题步骤，称为算法．它可以用框图、算法语言、数学语言或自然语言来描述。

用计算机算法语言描述的算法称为计算机程序。

（如c —语言程序，c++语言程序，Matlab 语言程序等）。

2、最有效的算法：应该运算量少，应用范围广，需用存储单元少，逻辑结构简单，便于编写计算机程序，而且计算结果可靠。

3、算法的稳定性：一个算法如果输入数据有误差，而在计算过程中舍入误差不增长，则称此算法是数值稳定的，否则称此算法为不稳定的。

换句话说：若误差传播是可控制的,则称此算法是数值稳定的,否则称此算法为不稳定的。

4、控制误差传播的几个原则： 1）防止相近的两数相减； 2）防止大数吃小数；3）防止接近零的数做除数；4）要控制舍入误差的累积和传播；5）简化计算步骤,减小运算次数,避免误差积累。

三、数值计算实验（以下实验都需利用Matlab 软件来完成） 实验1.1（体会数值计算精度与步长关系的实验）实验目的：数值计算中误差是不可避免的，要求通过本实验初步认识数值分析中两个重要概念：截断误差和舍入误差，并认真体会误差对计算结果的影响。

问题提出：设一元函数f :R →R ，则f 在x 0的导数定义为：hx f h x f x f h )()(lim)('0000-+=→实验内容:根据不同的步长可设计两种算法,计算f 在x 0处的导数。

计算一阶导数的算法有两种：h x f h x f x f )()()('000-+≈ （1）hh x f h x f x f 2)()()('000--+≈（2）请给出几个计算高阶导数的近似算法，并完成如下工作：1、对同样的h ，比较(1)式和(2)式的计算结果；2、针对计算高阶导数的算法，比较h 取不同值时(1)式和(2)式的计算结果。

《计算方法与程序设计》实验指导书1．上机实验使用的语言：C 语言或PASCAL 语言任选。

2．上机要求和步骤：（1）认真分析题目的条件和要求，复习相关的理论知识，选择适当的解决方案和算法；（2）编写上机实验程序，作好上机前的准备工作；（3）上机调试程序，并试算各种方案，记录计算的结果（包括必要的中间结果）；（4）分析和解释计算结果； （5）按照要求书写实验报告； （6）要求独立完成上述各项。

3．实验内容：实验一 非线性方程求根从下列3题中任选2题：1为求方程01)(23=--=x x x f 在5.10=x 附近的一个根，可将方程改写成下列下列等价形式，并建立相应的迭代公式（1） 改写成211x x +=迭代公式为2111kk x x +=+； （2） 改写成231x x +=迭代公式为3211k k x x +=+；（3） 改写成112-=x x 迭代公式为111-=+k k x x试分析每一种迭代公式的收敛性。

2 证明：当5.10=x 时，迭代法k k x x +=+4101 和 311021k k x x -=+都收敛于方程0104)(23=-+=x x x f 在区间[1，2]内唯一实根*x ，并分别用上迭代法求满足要求5110-+≤-k k x x 的近似根。

再用牛顿迭代法求此方程根的近似值（精确到5110-+≤-k k x x ），并将迭代次数与上面方程相比较。

3 设0>a ，试写出用牛顿迭代法求a 近似值的计算公式，并且 （1） 讨论该迭代法的收剑性；（2） 求17具有4位有较数字的近似值。

实验二 线代数方程求解 从下列3题中任选2题：1 分别用顺序消去法和列主元消去法解方程组⎪⎩⎪⎨⎧=++-=++-=++000.3643.5072.1000.2000.2623.4712.3000.1000.1000.3000.2001000.0321321321x x x x x x x x x （要求用具有舍入的4位数进行运算），并将所得结果与具有四位有较数字的准确解T x )3675.0,05104.0,4904.0(*--=进行比较。

计 算 方 法实 验 指 导 书彭彬计算机技术实验中心2012年3月· 实验环境： VC++ 6.0· 实验要求：在机房做实验只是对准备好的实验方案进行验证，因此上机前要检查实验准备情况，通过检查后方可上机。

没有认真准备的学生不能上机，本次实验没有分数。

实验中要注意考察和体会数值计算中出现的一些问题和现象：误差的估计,算法的稳定性、收敛性、收敛速度以及迭代初值对收敛的影响等。

· 关于计算精度：如果没有特别说明，在计算的过程中，小数点后保留5位数字，最后四舍五入到小数点后四位数字。

迭代运算的结束条件统一为51102-⨯。

在VC++ 6.0中，可使用setprecision 在流的输出中控制浮点数的显示（缺省显示6位）。

演示如下： # include<iostream.h> # include<math.h> # include<iomanip.h>//输出6位精度，输出左对齐cout<<setprecision(6)<<setiosflags(ios::left); //设置输出宽度为12（不够将补充0） cout<<setw(12)<<coeff[i];· 关于图形绘制本课程个别实验要求画出函数的曲线，所有画图题目均要求用MFC 完成。

利用VC++6.0的MFC 画图，先要建立一个工程，然后在***View 中加入自定义变量、自定义函数等，最后在OnDraw （）方法中调用自定义函数。

也可以把代码直接写入OnDraw （）方法中。

画曲线有两种方法，（一）一句坐标逐个打点（用SetPixel()函数），（二）先把当前光标移动（MoveTo（）函数）到曲线的始点，再用LineTo （）函数画线。

线的样式由画笔决定。

对封闭区域可以填充，填充的样式由画刷决定。

在VC++6.0中,先新建一个MFC AppWizard(exe)类型的工程(建立工程时，“应用程序类型”选择“单文档”；“是否包含数据库”选择“不包含数据库”；其它选择缺省),然后在“ClassView ”中选择XXView 类文件加以操作。

实验一 插值方法一、实验目的和要求（1）理解插值的基本概念，掌握各种插值方法，包括拉格朗日插值、牛顿插值、分段插值。

（2）通过实验进一步理解并掌握各种插值方法。

二、实验器材PC 机、Turbo c 或C++、WINDOWS 系统 三、实验内容任务（一）拉格朗日插值法：用拉格朗日插值多项式求函数近似值。

1、 实验内容设函数y=f(x)在给定的两两互异节点x 0，x 1，…，x n 上的函数值为y 0，y 1，…，y n ，求作一个次数≤n 的多项式P n (x)=a 0+a 1x+…+a n x n使它满足：P n (x i )= y i (i=0,1,2,…,n)。

∑==n k k k n x l y x p 0)()(其中nkj j jk j k x x x x x l ≠=--=0)(为拉格朗日插值公式。

2、 实验步骤#include<stdio.h> #define N 3 void main() {float X[N+1],Y[N+1],x; double L,LI; int i,j;printf("Please input X[i],Y[i]:\n"); for(i=0;i<=N;i++)scanf("%f,%f",&X[i],&Y[i]); printf("Please input x:\n"); scanf("%f",&x); L=0;for(i=0;i<=N;i++) {LI=1;for(j=0;j<=N;j++) {if(j==i) continue;LI=(LI*(x-X[j]))/(X[i]-X[j]); }L=L+LI*Y[i]; }printf("\nN=%d\nL(%f)=%f\n",N,x,L); }3、 实验结果与分析Please input X[i],Y[i]: 0.56160,0.82741 0.56280,0.82659 0.56401,0.82577 0.56521,0.82495 Please input x: 0.5635N=3L(0.563500)=0.826116任务（二）牛顿插值方法：造出差商表，并用牛顿插值多项式求函数近似值。

《算法设计与分析》实验指导书实验一 用贪心方法解背包问题一: 实验目的掌握按贪心方法原理求背包问题最优解的方法二:问题描述背包问题描述如下: 已知背包容量M=120物品种类数n=10各种物品的总效益pi(i=1,2,………10) : 50,60,70,80,90,80,70,60,50,40各种物品的总重量wi(i=1,2………10) : 17,30,25,41,80,70,64,56,47,38求: 各种物品所取重量占其总重量的比例xi(i=1,2,…..10),满足0<=xi<=1,且 且使得 达到最大值. 三. 基本要求(1) 按三种不同的量度标准分别计算所得最大总效益,然后比较哪个最大1. 按效益值由大到小取物品.2. 按重量值由小到大取物品3.按比值pi/wi 的值由大到小取物品四： 选做题 装箱问题问题描述：装箱问题可简述如下：设有编号为0、1、…、n-1的n 种物品，体积分别为v0、v1、…、vn-1。

将这n 种物品装到容量都为V 的若干箱子里。

约定这n 种物品的体积均不超过V ，即对于0≤i ＜n ，有0＜vi ≤V 。

不同的装箱方案所需要的箱子数目可能不同。

装箱问题要求使装尽这n 种物品的箱子数要少。

若考察将n 种物品的集合分划成n 个或小于n 个物品的所有子集，最优解就可以找到。

但所有可能划分的总数太大。

对适当大的n ，找出所有可能的划分要花费的时间是无法承受的。

为此，对装箱问题采用非常简单的近似算法，即贪婪法。

该算法依次将物品放到它第一个能放进去的箱子中，该算法虽不能保证找到最优解，但还是能找到非常好的解。

不失一般性，设n 件物品的体积是按从大到小排好序的，即有v0≥v1≥…≥vn-1。

如不满足上述要求，只要先对这n 件物品按它们的体积从大到小排序，然后按排序结果对物品重新编号即可。

装箱算法简单描述如下： {输入箱子的容积；输入物品种数n ；按体积从大到小顺序，输入各物品的体积；预置已用箱子链为空；预置已用箱子计数器box_count 为0；for (i=0;i<n;i++){ 从已用的第一只箱子开始顺序寻找能放入物品i 的箱子j ；if （已用箱子都不能再放物品i ）{ 另用一个箱子，并将物品i 放入该箱子；box_count++；}else将物品i 放入箱子j ；} }上述算法能求出需要的箱子数box_count ，并能求出各箱子所装物品。

算例1-1：选择函数y=exp(-x2) (-2≤x≤2),在n个节点上（n不要太大，如5~11）用拉格朗日、牛顿插值方法，计算m个插值点的函数值（m要适中，如50~100），通过数值和图形输出，将插值结果与精确值进行比较，进行误差分析。

适当增加n，再作比较，并作初步分析。

%lagrangen.mfunction y=lagrangen(x0,y0,x)n=length(x0);m=length(x);for i=1:mz=x(i);s=0;for k=1:nL=1;for j=1:nif j~=kL=L*(z-x0(j))/(x0(k)-x0(j));endends=s+L*y0(k);endy(i)=s;endy;%shiyan1-1x=-2:1:2y=exp(x.*x)xi=-2:0.01:2yi=lagrangen(x,y,xi)plot(xi,yi,'r',x,y,'*')算例1-2：已知函数在下列各点的值为试用4次牛顿插值多项式P4(x)对数据进行插值，用图给出{(x i,y i),x i=0.2+0.08i,i=0,1…,10},P4(x)。

function y=newton(x0,y0,x)n=length(x0);D=zeros(n,n);D(:,1)=y0';for j=2:nfor i=j:nD(i,j)=(D(i,j-1)-D(i-1,j-1))/(x0(i)-x0(i-j+1));endendy=D(n,n);for i=n-1:-1:1y=y.*(x-x0(i))+D(i,i);end%shiyan1-2x=[0.2 0.4 0.6 0.8 1.0]y=[0.98 0.92 0.81 0.64 0.38]i=0:1:10xi=0.2+0.08*i;yi=newton(x,y,xi)plot(xi,yi,'r',x,y,'*')算例用这9个点作8次多项式插值函数L8(x)的图形。

《计算方法》实验课程指导书徐中宇朱洪秀2011年3月目录第一章插值法......................................................................................................... 错误!未定义书签。

§1拉格朗日插值.................................................................................................. 错误!未定义书签。

§2牛顿插值........................................................................................................ 错误!未定义书签。

第二章线性方程组的解法 ................................................................................... 错误!未定义书签。

§1高斯消去法.................................................................................................. 错误!未定义书签。

§２列主元消去法............................................................................................ 错误!未定义书签。

§3线性方程组的迭代解法.............................................................................. 错误!未定义书签。

计算机算法设计与分析实验指导书本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。

上机实验一般应包括以下几个步骤：（1）、准备好上机所需的程序。

手编程序应书写整齐，并经人工检查无误后才能上机。

（2）、上机输入和调试自己所编的程序。

一人一组，独立上机调试，上机时出现的问题，最好独立解决。

（3）、上机结束后，整理出实验报告。

实验报告应包括：题目、程序清单、运行结果、对运行情况所作的分析。

本书共分阶段8个实验，其具体要求和步骤如下：实验一C/C++环境及递归算法（2学时）一、实验目的与要求1、熟悉C/C++语言的集成开发环境；2、通过本实验加深对递归过程的理解二、实验内容：掌握递归算法的概念和基本思想，分析并掌握排列问题的递归算法和Hanoi塔问题的递归算法。

三、实验题1、设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。

任意输入一串整数或字符，输出结果能够用递归方法实现整数或字符的全排列。

2、设a,b,c是3个塔座。

开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。

各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。

四、实验步骤1．理解算法思想和问题要求；2．编程实现题目要求；3．上机输入和调试自己所编的程序；4．验证分析实验结果；5．整理出实验报告。

实验提示1、#include <iostream.h>inline void swap(int &a,int &b){int temp=a;a=b;b=temp;}void perm(int list[],int k,int m){if(k==m){for(int i=0;i<=m;i++)cout<<list[i];cout<<endl;}elsefor(int i=k;i<=m;i++){swap(list[k],list[i]);perm(list,k+1,m);swap(list[k],list[i]);}}void main(){int list[3]={1,2,3};perm(list,0,2);}2、void hanoi(int n, int a, int b, int c){if (n > 0){hanoi(n-1, a, c, b);move(a,b);hanoi(n-1, c, b, a);}}实验二分治算法（2学时）一、实验目的与要求1、熟悉二分搜索算法和快速排序算法；2、初步掌握分治算法；二、实验题1、设a[0:n-1]是一个已排好序的数组。

《计算方法实验》教学大纲课程名称：计算方法学时：16学分：无独立学分课程性质：专业必修课开课对象：数学与应用数学专业学生一、教学目的与要求本课程主要研究建立各种数学问题的数值计算方法与理论，并提供在计算机上实际可行的、理论可靠的、计算复杂性好的各种常用算法。

结合上机实验实现有关算法是必要的实践环节。

通过实验，使学生了解科学和工程计算中常用算法的实现方法以及算法的有效性和可行性，加深学生对计算方法的理论及算法的理解，培养学生的实际动手能力和解决问题的能力，为今后更好地利用计算机解决实际问题奠定良好基础。

二、主要仪器设备计算机、Matlab软件、Mathematica软件。

三、实验项目设置与内容四、课程考核以20%计入课程总成绩。

五、实验指导书及主要参考书[1]数值分析Numerical Analysis，苏岐芳主编，中国铁道出版社，2007.[2] Richard L. Burden J. Douglas Faires. Numerical Analysis, 数值分析（第七版影印版），北京: 高等教育出版社，2001.[3] Robert J.Schilling Sandra L.Harris. Applied Numerical Methods for Engineers Using MATLAB and C, 应用数值方法使用MA TLAB 和C语言(英文版)，北京：机械工业出版社，2004.[4] David Kincaid Ward Cheney，Numerical Analysis, 数值分析（英文版.第3版），北京：机械工业出版社，2003.[5] 晨曦工作室荀飞，Mathematica 4 实例教程，北京: 中国电力出版社,2000.[6] 周煦编著，计算机数值计算方法及程序设计，北京：机械工业出版社，2004．[7] 王兵团桂文豪编著，数学实验基础，北京：北方交通大学出版社，2003．[8] 李丽王振领，MATLAB工程计算及应用，北京: 人民邮电出版社,2001.执笔人：苏岐芳审定人：赵岳清《数学实验》实验教学大纲课程名称：数学实验实验学时：18学分：0.5课程性质：专业方向限选课考核方式：考查开课对象：数学与应用数学专业一、教学目的与要求结合《数学实验》课程的学习，利用数学软件做实验，学习解决实际问题常用的数学方法，分析并解决经过简化的实际问题，提高学数学，用数学的兴趣、意识和能力，在基本数学知识和数学的应用之间架起一座桥梁，提高综合解决实际问题的能力。