《离散数学》实验报告
（2015 / 2016 学年第一学期）
题目：图的随机生成及欧拉（回）路的确定
专业信息安全
学生姓名
班级学号
指导教师
指导单位计算机学院计算机科学与技术系
日期2015年12月29日
图的随机生成及欧拉（回）路的确定
一、实验内容和要求
内容：编程随机生成n个结点的无向图并能进行（半）欧拉图的判定，若是则给出欧拉（回）路。
要求：对给定n个结点，随机生成邻接矩阵以确定某无向简单图并进行欧拉图和半欧拉图的判定，若符合则给出至少一条欧拉回路或欧拉路。
二、实验目的
对给定n个结点，随机生成邻接矩阵以确定某无向简单图并进行欧拉图和半欧拉图的判定，若符合则给出至少一条欧拉回路或欧拉路。
三、实验任务
1、输入结点个数据生成随机图
2、进行（半）欧拉图的判定
3、若是则给出欧拉（回）路。
四、实验内容
#include
#include
#include
using namespace std;
class Euler
{
public:
Euler(int num);
~Euler();
void DFS(int begin); //公有的深度优先搜索函数void inputEdge(); //输入边
void PrintAM(); //打印邻接矩阵
void PrintRM(); //打印可达性矩阵
void Warshall(); //Warshall算法求可达性矩阵bool IsConnected(); / /判断图是否连通
int IsEorSE(); //判断图是欧拉图还是半欧拉图
bool isEuler;
private:
void DFS(int u,int v,bool **visited); / /私有的深度优先搜索函数
int n;
int **a; //定义动态二维数组
int **p; //定义可达性矩阵
int *b; //存储每个结点的度数};
Euler::Euler(int num) //构造函数
{
isEuler=false;
n=num;
int i,j;
a=new int*[n];
for(i=0;i { a[i]=new int[n]; for(j=0;j a[i][j]=0; } p=new int*[n]; for(i=0;i { p[i]=new int[n]; for(j=0;j p[i][j]=0; } b=new int[n]; for(i=0;i b[i]=0; } Euler::~Euler()//析构函数 { int i; for(i=0;i delete []a; for(i=0;i delete []p; delete []b; } void Euler::inputEdge() { srand((unsigned)time(NULL)); for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { a[i][j] = 0+rand()%2; //随机生成无向图 a[j][i]=a[i][j]; } } for(int ii=0;ii { for(int jj=0;jj { if(a[ii][jj]==1) { p[ii][jj]=1; p[jj][ii]=1; } } } } void Euler::PrintAM() { cout<<"随机生成的图为："< for(int i=0;i { for(int j=0;j cout< cout< } } void Euler::Warshall() { for(int i=0;i for(int j=0;j if(p[j][i]==1) { for(int k=0;k { if(p[j][k]+p[i][k]>0) p[j][k]=1; } } } void Euler::PrintRM() { cout<<"可达性矩阵："< for(int i=0;i { for(int j=0;j cout< cout< } } bool Euler::IsConnected() { int i,j; bool flag=true; / /flag标记是否连通for(i=0;i { for(j=0;j if(p[i][j]==0) //如果可达性矩阵中有一个元素为0， { //就跳出循环，表示该图不连通flag=false; break; } if(!flag) break; } if(!flag) cout<<"该图不是连通的"; else { for(i=0;i for(j=i;j { if(a[i][j]==1&&i!=j) //由边计算结点的度数 { b[i]++;b[j]++; } } } return flag; } int Euler::IsEorSE() { int i,count=0,begin=-1; cout<<"每个结点的度数："< for(i=0;i cout< for(i=0;i if(b[i]%2!=0) { count++; begin=i;//初始化开始结点，存在奇数结点，则将其中一个作为开始点} if(begin==-1)//不存在奇数结点则将0作为起始点 begin=0; if(count==2) { cout<<"该图是半欧拉图"< else if(count==0) { cout<<"该图是欧拉图"< } return begin; } void Euler::DFS(int begin) { int i,j; bool **visited=new bool*[n];//二维数组记录每条边是否被访问过 for(i=0;i { visited[i]=new bool[n]; for(j=0;j if(a[i][j]==1) visited[i][j]=false; else visited[i][j]=true; } for(j=0;j if(!visited[begin][j]) { DFS(begin,j,visited); cout< } for(i=0;i delete []visited; } void Euler::DFS(int u,int v,bool **visited) { if(!visited[u][v])//判断边 { visited[u][v]=true;visited[v][u]=true;//标记被访问 for(int i=0;i DFS(v,i,visited); cout< } int main() { int n,m,begin; bool flag; cout<<"输入结点个数:"; cin>>n; Euler euler(n); euler.inputEdge(); euler.PrintAM(); euler.Warshall(); euler.PrintRM(); flag=euler.IsConnected(); if(flag) { begin=euler.IsEorSE(); if(euler.isEuler) { cout<<"具体路径为："; euler.DFS(begin); } } cout< return 0; } 五、测试数据及其结果分析 六、调试过程中的问题 可达性矩阵无法正确计算，调试后发现是算法中未正确定义循环变量 七、程序设计总结 1.掌握了与离散数学理论相关的编程实现思想和方法，掌握了欧拉图和半欧拉图的判定。 2.利用邻接矩阵表示存在的边，通过Warshall算法求出无向图的可达性矩阵，如果是连通的话，那么可达性矩阵中每一个元素都应该为1，否则存在元素为0。 3.多次利用动态二维数组，并养成了在程序结束时释放动态二维数组内存的习惯。 4.明白了欧拉回路属于欧拉路的一种特殊情况，之前一直没有搞清这两者之间的关系。 在判断是欧拉图还是半欧拉图时，首先判断是不是连通图，然后判断是否只存在零个或者两个奇数度结点，有两个则是半欧拉图，零个则是欧拉图。 5.输出欧拉路时，利用递归深度搜索逆序输出结点，确保找到一条完整的路径，避免存在回路没有被遍历到。 评分细则 评分项优秀良好中等差遵守机房规章制度 上机时的表现 学习态度 算法思想准备情况 程序设计能力 解决问题能力 课题功能实现情况 算法设计合理性 算法效能评价 报告书写认真程度 内容详实程度 文字表达熟练程度 回答问题准确度 简 短 评 语 教师签名： 年月日 评 分 等 级 备 注 评分等级有五种：优秀、良好、中等、及格、不及格 CENTRAL SOUTH UNIVERSITY 数值分析实验报告 Euler 方法与改进的Euler 方法的应用 一、问题背景 在工程和科学技术的实际问题中，常需求解微分方程，但常微分方程中往往 只有少数较简单和典型的常微分方程（例如线性常系数常微分方程等）可求出其 解析解,对于变系数常微分方程的解析求解就比较困难，而一般的非线性常微分方 程的求解困难就更不用说了。大多数情况下，常微分方程只能用近似方法求解。 这种近似解法可分为两大类：一类是近似解析法，如级数解法、逐次逼近法等;另 一类是数值解法，它给出方程在一些离散点上的近似值。 二、数学模型 在具体求解微分方程时，需具备某种定解条件，微分方程和定解条件合在一 起组成定解问题。定解条件有两种：一种是给出积分曲线在初始点的状态，称为 初始条件，相应的定解问题称为初值问题。另一类是给出积分曲线首尾两端的状 态，称为边界条件，相应的定解问题称为边值问题。在本文中主要讨论的是给定 初值条件的简单Euler 方法和改进的Euler 方法来求解常微分方程。 三、算法及流程 Euler 方法是最简单的一种显式单步法。对于方程 ()y x f dx dy ,= 考虑用差商代替导数进行计算，取离散化点列 nh x x n +=0，L n ,2,1,0= 则得到方程的近似式 ()()()()n n n n x y x f h x y x y ,1≈-+ 即 ()n n n n y x hf y y ,1+=+ 得到简单Euler 方法。具体计算时由0x 出发，根据初值，逐步递推二得到系列离 散数值。 简单Euler 方法计算量小，然而精度却不高，因而我们可以构造梯形公式 ()()[]η=++ =+++0111,,2 y y t f y t f h y y n n n n n n 其中()N a b h -=。这是一个二阶方法，比Euler 方法精度高。但是上述公式右边 有1+n y ，因而是隐式差分方程，可以用迭代方法计算1+n y 。初值可以由Euler 公式 P77 31.利用改进欧拉方法计算下列初值问题，并画出近似解的草图：dy + =t = t y y ≤ ≤ ,2 ;5.0 0,3 )0( )1(= ,1 ? dt 代码： %改进欧拉法 function Euler(t0,y0,inv,h) n=round(inv(2)-inv(1))/h; t(1)=t0; y(1)=y0; for i=1:n y1(i+1)=y(i)+h*fun(t(i),y(i)); t(i+1)=t(i)+h; y(i+1)=y(i)+1/2*h*(fun(t(i),y(i))+ fun(t(i+1),y1(i+1))) end plot(t,y,'*r') function y=fun(t,y); y=y+1; 调用：Euler(0,3,[0,2],0.5) 得到解析解：hold on; y=dsolve('Dy=y+1','(y(0)=3)','t'); ezplot(y,[0,2]) 图像： dy y =t - t y ;2.0 t = ≤ )0( 0,5.0 ,4 )2(2= ≤ ? ,2 dt 代码： function Euler1(t0,y0,inv,h) n=round(inv(2)-inv(1))/h; t(1)=t0; y(1)=y0; for i=1:n y1(i+1)=y(i)+h*fun(t(i),y(i)); t(i+1)=t(i)+h; y(i+1)=y(i)+1/2*h*(fun(t(i),y(i))+ fun(t(i+1),y1(i+1))) end plot(t,y,'*r') function y=fun(t,y); y=y^2-4*t; 调用： Euler1(0,0.5,[0,2],0.2) 图像： 求欧拉回路的Fleury算法 一、实验内容： 判断图G是否存在欧拉回路，若存在，输出其中一条欧拉回路。否则，显示无回路。 二、实验环境：vc++ 三、实验过程与结果 1.问题简介：通过图（无向图或有向图）中所有边一次且仅一次行遍所有 顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图 2.算法思想（框图）： （1）任取v0∈V(G)，令P0=v0. （2）设Pi=v0e1v1e2…e i v i已经行遍，按下面方法来从E(G)-{e1,e2,…,e i}中选取e i+1： （a）e i+1与v i相关联； （b）除非无别的边可供行遍，否则e i+1不应该为 G i=G-{e1,e2,…,e i}中的桥。 （3）当（2）不能再进行时，算法停止。 可以证明，当算法停止时所得简单回路Pm=v0e1v1e2…e m v m(v m=v0)为G中一条欧拉回路。 3.数据输入： 边数5，点数6 相关联的点1 2 1 3 2 5 4 2 3 2 4 5 4.运行结果： 存在欧拉回路 1，3，2，4，5，2，1 5.分析总结： Fleury算法是求欧拉图的十分有效的算法，在执行过程中需要用到类似于图的深度优先遍历，因为该算法就是需要将已找到的路径不断的扩展下去，直到将所有边扩展进路径。 四、完整源程序 #include 毕业论文 题目：常微分方程的Euler解法 及其程序设计 学院：数学与信息科学学院 专业：数学与应用数学 毕业年限： 2011年6月 学生： 学号： 指导教师： 常微分方程的Euler解法及其程序设计 摘要本文总结了常微分方程的Euler解法，对各种格式给出了误差估计，设计了这些格式的计算程序． 关键词常微分方程；Euler解法；误差分析；程序设计 Euler Method of Ordinary Differential Equation and Its Programming Abstract Euler method of ordinary differential equation is summarized，the error of each format is analyzed and its programming is designed in this paper. Keywords Ordinary differential equation; Euler method; Error analysis; Programming 科学技术中常常需要求解常微分方程的定解问题，这类问题最简单的形式，即为微分方程 (,)dy f x y dx = （1） 的初值问题 00(,),(). dy f x y dx y x y ?=???=? （2） 定理 （存在与唯一性定理）如果方程（1）的右端函数(,)f x y 在闭矩形域 000000:,R x a x x a y b y y b -≤≤+-≤≤+ 上满足如下条件： （1）在R 上连续； （2）在R 上关于变量y 满足利普希茨（Lipschitz ）条件，即存在常数L ，使 对于R 上任何一对点(,)x y 和(,)x y 有不等式： (,)(,)f x y f x y L y y -≤-, 则初值问题（2）在区间00000x h x x h -≤≤+上存在唯一解 00(),()y y x y x y ==, 其中0(,)min(,),max (,)x y R b h a M f x y M ∈==． 根据存在与唯一性定理，只要(,)f x y 关于y 满足Lipschitz 条件 (,)(,)f x y f x y L y y -≤-， 即可保证其解()y y x =存在并唯一． 然而解析方法只能用来求解少数较简单和典型的常微分方程，例如线性常系数微分方程等，对于变系数常微分方程的解析求解就比较困难，而一般的非线性常微分方程就更不用说，因此，在大多数情况下，实际问题中归结出来的微分方程主要靠数值解法求解． 一、实验内容： 判断图G是否存在欧拉回路，若存在，输出其中一条欧拉回路。否则，显示无回路。 二、实验过程与结果 1.问题简介：通过图（无向图或有向图）中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。 具有欧拉回路的图称为欧拉图 2.算法思想（框图）： （1）任取v0∈V(G)，令P0=v0. （2）设Pi=v0e1v1e2…eivi已经行遍，按下面方法来从E(G)-{e1,e2,…,ei}中选取ei+1： （a）ei+1与vi相关联； （b）除非无别的边可供行遍，否则ei+1不应该为Gi=G-{e1,e2,…,ei}中的桥。 （3）当（2）不能再进行时，算法停止。 可以证明，当算法停止时所得简单回路Pm=v0e1v1e2…emvm(vm=v0)为G中一条欧拉回路。 3.数据输入： 边数5，点数6 相关联的点1 2 1 3 2 5 4 2 3 2 4 5 4.运行结果： 存在欧拉回路1，3，2，4，5，2，1 5.分析总结： Fleury算法是求欧拉图的十分有效的算法，在执行过程中需要用到类似于图的深度优先遍历，因为该算法就是需要将已找到的路径不断的扩展下去，直到将所有边扩展进路径。 三、完整源程序 #include <> #include <> #include <> struct stack { int top , node[81]; } T,F,A; //顶点的堆栈 int M[81][81]; //图的邻接矩阵int n; int degree[81]; bool brigde(int i,int j) { int flag[81],t,s; for(s=1;s<=n;s++) flag[s]=0; if(degree[i]==1) return false; else { M[i][j]=0;M[j][i]=0; =1; [1]=i; flag[i]=1; t=i; while>0) { for(s=1;s<=n;s++) { if(degree[s]>0){ if(M[t][s]==1) if(flag[s]==0) { ++; []=s; flag[s]=1; t=s; break; } } } if(s>n){ ; t=[]; } } for(s=1;s<=n;s++) { if(degree[s]>0) if(flag[s]==0) { M[i][j]=M[i][j]=1; return true; break; } } if(s>n) return false; } } void Fleury(int x) //Fleury算法{ int i,b=0; if<=n+1){ ++;[]=x; for(i=1;i<=n;i++) if(M[x][i]==1) if(brigde(x,i)==false) { b=1; break; } if(b==1) { M[x][i]=M[i][x]=0; degree[x]--; degree[i]--; Fleury(i); } } 生物信息技术0801 徐聪U200812594 #include . 欧拉路径（欧拉回路）相关定义： 若图G中存在这样一条路径，使得它恰通过G中每条边一次,则称该路径为欧拉路径。若该路径是一个圈，则称为欧拉回路。 具有欧拉回路的图称为欧拉图（简称E图）。具有欧拉路径但不具有欧拉回路的图称为半欧拉图。 判断图是否为欧拉图： 无向图为欧拉图，当且仅当为连通图且所有顶点的度为偶数。 无向图为半欧拉图，当且仅当为连通图且除了两个顶点的度为奇数之外，其它所有顶点的度为偶数。 有向图为欧拉图，当且仅当其基图（忽略有向图所有边的方向，得到的无向图称为该有向图的基图）连通，且所有顶点的入度等于出度。 有向图为半欧拉图，当且仅当其基图连通，且有且仅有一个顶点的入度比出度大1、有且仅有一个顶点的入度比出度小1，其它所有顶点的入度等于出度。 欧拉回路（路径）的算法： 有向图： 第一步，判断是否存在欧拉路径（欧拉回路），如果不存在，算法结束。 第二步，如果存在欧拉路径，从入度比出度小1的点开始BFS；如果存在欧拉回路，从任意一点开始。 第三步，设DFS到点u，遍历u的出边e(u,v)。 第四步，如果e未被标记，转到第五步，否则转到第三步。 第五步，标记e(u,v)，DFS点v。 第六步，边e(u,v)入栈。 第七步，完成DFS后，从栈顶顺序输出边构成一个欧拉路径（欧拉回路）。 无向图： 第一步，判断是否存在欧拉路径（欧拉回路），如果不存在，算法结束。 第二步，如果存在欧拉路径，从度为奇数的点开始BFS；如果存在欧拉回路，从任意一点开始。 第三步，设DFS到点u，遍历u的出边e(u,v)。 第四步，如果e未被标记，转到第五步，否则转到第三步。 第五步，标记e(u,v)及它的反向边，DFS点v。 第六步，边e(u,v)入栈。 第七步，完成DFS后，从栈顶顺序输出边构成一个欧拉路径（欧拉回路）。 '. 欧拉回路的求解 左图是一个井田图，由于2、3、5、8、9、12、14、15几个点都是奇数连线，故不存在欧拉回路。而右图增加几条连线后，该图就存在欧拉回路。 a)假设点1和点2 之间的连线消失， b)建立数学模型把右图的拓扑关系（并考虑a中连线消失的因素）表达出来 c)理解fleury算法，并计算一条欧拉迹，使得该欧拉迹从点1出发，经过b中的每一条边， 最终达到点2 d)使用plot命令把该欧拉迹显示出来。这个动画过程可以用一个for循环语句实现，如下。 其中pos是个2x16的矩阵，2行分别代表x/y轴坐标，每一列表示每个点的坐标，共16个点；另外，T是个2xN的矩阵，每一列表示一条边从T(1，i) 点到T(2，i)点。fleury 算法的目的就是要产生这样一个T 矩阵。 for i … draw_arrow(pos(:,T(1,i))',pos(:,T(2,i))',0.5) pause; end 以下是这段动画的其中几个截图 clear all hold off A=zeros(16); for i=1:16 %A(i,i)=1/2; if i+1<=16 && mod(i,4)~=0 A(i,i+1)=1; end if i+4<=16 A(i,i+4)=1; end end A(2,5)=1; A(3,8)=1; A(9,14)=1; A(12,15)=1; A=A+A'; [T3 c3]=fleury3(A); pos3(1:2,1)=0; for i=1:16 if i==1, pos3(1:2,i)=0; else if mod(i-1,4)~=0 pos3(1,i)=pos3(1,i-1)+1; pos3(2,i)=pos3(2,i-1); else pos3(1,i)=pos3(1,i-4); pos3(2,i)=pos3(2,i-4)-1; end end end figure (1), title('3rd Question') for i=1:16 for j=i:16 if A(i,j)==1, plot([pos3(1,i),pos3(1,j)],[pos3(2,i),pos3(2,j)]); hold on, end end end for i=2:size(T3,2) draw_arrow(pos3(:,T3(1,i))',pos3(:,T3(2,i))',0.5) 欧拉（Euler）通路/回路 1、基本概念： （1）定义 欧拉通路(欧拉迹)—通过图中每条边一次且仅一次，并且过每一顶点的通路。 欧拉回路(欧拉闭迹)—通过图中每条边一次且仅一次，并且过每一顶点的回路。 欧拉图—存在欧拉回路的图。欧拉图就是从一顶出发每条边恰通过一次又能回到出发顶点的那种图，即不重复的行遍所有的边再回到出发点。 通路和回路－称v i e1e2…e n v j为一条从v i到v j且长度为n的通路，其中长度是指通路中边的条数．称起点和终点相同的通路为一条回路。 简单图－不含平行边和自回路的图。 混合图－既有有向边，也有无向边的图 平凡图－仅有一个结点的图 完全图－有n个结点的且每对结点都有边相连的无向简单图，称为无向完全图；有n个结点的且每对结点之间都有两条方向相反的边相连的有向简单图为有向完全图。 （2）欧拉图的特征： 无向图 a）G有欧拉通路的充分必要条件为：G 连通，G中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。 b）G有欧拉回路(G为欧拉图)：G连通，G中均为偶度顶点。 有向图 a）D有欧拉通路：D连通，除两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。 b）D有欧拉回路(D为欧拉图)：D连通，D中所有顶点的入度等于出度。一个有向图是欧拉图，当且仅当该图所有顶点度数都是0。 2、弗罗莱（Fleury）算法思想－解决欧拉回路 Fleury算法： 任取v0∈V(G)，令P0=v0； 设Pi=v0e1v1e2…ei vi已经行遍，按下面方法从中选取ei+1： （a）ei+1与vi相关联； （b）除非无别的边可供行遍，否则ei+1不应该为Gi=G-{e1,e2, …, ei}中的桥（所谓桥是一条删除后使连通图不再连通的边）； （c）当（b）不能再进行时，算法停止。 可以证明,当算法停止时所得的简单回路Wm=v0e1v1e2….emvm(vm=v0)为G中的一条欧拉回路，复杂度为O(e*e)。 3、欧拉算法C语言描述 如下为算法的图示动态过程： 西华数学与计算机学院上机实践报告 课程名称：计算方法A 年级：2010级 上机实践成绩： 指导教师：严常龙 姓名：李国强 上机实践名称：解常微分方程初值问题 学号：362011********* 上机实践日期：2013.12.25 上机实践编号：8 上机实践时间：14:00 一、目的 1．通过本实验加深对欧拉法、改进欧拉法、线性多步法的构造过程的理解； 2．能对上述四种方法提出正确的算法描述编程实现，观察计算结果的改善情况。 二、内容与设计思想 自选常微分方程的初值问题，分别用欧拉法、改进欧拉法求解。 分别用以上两种方法求解常微分方程初值问题： 2 '()1,([0.0,1.4],0.1)(0)0.0 y x y h y ?=+=?=?求解区间取步长 三、使用环境 操作系统：Win 8 软件平台：Visual C++ 6.0 四、核心代码及调试过程 #include int i; float y[n+1]; y[0]=m;//赋初值 printf("改进欧拉法\n"); for(i=0;i Euler 法解常微分方程 Euler 法解常微分方程算法： Step 1 分别取积分上限、积分下限、步长 Step 2计算h n n +=判断b n ≤是否成立，成立转到Step 3，否则继续进行Step 4 Step 3 计算),(1n n n n y x hf y y +=+ Step 4 ),(1n n n n y x hf y y +=+ Euler 法解常微分方程算程序： function euler2(fun,y0,A,h) %fun--y' %y0---初值 %A----x 取值范围 %a----x 左区间端点值 %b----x 右区间端点值 %h----给定步长 x=min(A); b=max(A); y=y0; while x 0.4613 指导教师： 年 月 日 改进Euelr 法解常微分方程 改进Euler 法解常微分方程算法： Step 1 分别取积分上限、积分下限、步长 Step 2 取一个以h 为步长，a ，b 分别为左右端点的矩阵 Step 3 （1）做显性Euler 预测),( 1n n i i y x hf y y +=+ （2）将1+i y 带入,(),([2h 11++++=i i i i i x f y x f y y Step 4计算h n n +=判断b n ≤是否成立，成立返回Step 5 )],(),([2h 111+++++=i i i i i i y x f y x f y y 改进Euler 法解常微分方程算程序： function gaijineuler2(fun,y0,A,h) %fun--y' %y0---初值 %A----x 取值范围 %a----x 左区间端点值 %b----x 右区间端点值 %h----给定步长 a=min(A); b=max(A); x=a:h:b; y(1)=y0; for i=1:length(x)-1 w1=feval(fun,x(i),y(i)); y(i+1)=y(i)+h*w1; w2=feval(fun,x(i+1),y(i+1)); y(i+1)=y(i)+h*(w1+w2)/2; end x=x' 7. 取h =0.2，用改进欧拉方法求解下列初值问题。 '(0)5 y y ì?í?=?020x ＃) 第七题: #include "fstream.h" #include "math.h" int main() { double x0,x1,y0,yp,yc,h; ifstream infile("in.dat"); ofstream outfile("out.dat"); infile>>x0>>x1>>h>>y0;//依次输入x 的初值x0，x 的终值x1，步长h ，y （0）的值y0 outfile< 0 5 0.2 7.03239 0.4 9.89185 0.6 13.9148 0.8 19.5739 1 27.5337 1. 2 38.7287 1.4 54.4735 1.6 76.6169 1.8 107.759 2 151.558 2.2 213.156 2.4 299.787 2.6 421.626 2.8 592.981 3 833.977 3.2 1172.91 3. 4 1649.6 3.6 2320.01 3.8 3262.89 4 4588.97 4.2 6453.97 4.4 9076.93 4.6 12765.9 4.8 17954.1 5 25250.8 5.2 35513 5.4 49945.8 5. 6 70244.3 5.8 98792.3 常微分方程欧拉算法 Company Document number：WUUT-WUUY-WBBGB-BWYTT-1982GT 常微分方程欧拉算法 摘要：本文主要论述了常微分方程的欧拉算法的算法原理，误差分析，实例，程序，以及算法比较等内容。 关键词：常微分方程 显式欧拉法 隐式欧拉法 引言：微分方程初值问题模型是常见的一类数学模型。对于一些简单而典型的微分方程模型，譬如线性方程、某些特殊的一阶非线性方程等是可以设法求出其解析解的，并有理论上的结果可资利用。但在数学建模中碰到的常微分方程初值问题模型，通常很难，甚至根本无法求出其解析解，而只能求其近似解。因此，研究其数值方法，以便快速求得数值鳃有其重大意义。 一、欧拉算法原理 对于微分方程初值问题 的解在xy 平面上是一条曲线，称为该微分方程的积分曲线。积分曲线上一点(),x y 的切线斜率等于函数f 在点(),x y 的值，从初始点()000,P x y 出发，向该点的切线方向推进到下一个点()111,P x y ，然后依次做下去，得到后面的未知点。一般地，若知道(),n n n P x y 依上述方法推进到点()111,n n n P x y +++，则两点的坐标关系为： 即 这种方法就是欧拉（Euler ）方法（也叫显式欧拉法或向前欧拉法）。当初值0y 已知，则n y 可以逐步算出 对微分方程()=x y dy f dx ，从n x 到1n x +积分，那么有 现在用左矩形公式()(),n n hf x y x 代替()()1 ,n n x x f t y t dt +?，n y 代替()n y x ，1n y +代替() 1n y x +就得到了欧拉方法。如果用右矩形公式()()11,n n hf x y x ++去代替右端积分，则得到另外一 个公式，该方法就称为隐式欧拉法（或后退欧拉法），其公式为 欧拉公式与隐式欧拉公式的区别在于欧拉公式是关于1n y +的一个直接计算公式，然而隐式欧拉公式右端含有1n y +，所以它实际上是关于1n y +的一个函数方程。 二、实例 例 取h=，用Euler 方法解 《常微分方程》课内实验任务书 学生姓名:张学阳1009300132 及学号： 学院:理学院 班级:数学101 课程名称：常微分方程 题目:Euler方法及其改进方法 指导教师 李鹏松教授 姓名及职称： 朱秀丽讲师 方向实验师 2012年10月17日 《常微分方程》课内实验 实验一 Euler 方法及其改进方法 一、实验目的 1．通过用Matlab 编程运用Euler 方法及其改进方法求解常微分方程初值问题，更进一步掌握常微分方程及其数值解法课程的理论内容，加深对数值解法的理解。 2．熟悉Matlab 编程环境。 二、实验学时和类型 本次实验为2学时、设计性实验。 三、实验内容 1.实验题目 运用Euler 方法及其改进方法求解常微分方程初值问题，具体问题在课内实验习题中学生任意抽取。 2.实验原理 Euler 方法：???+==+) ,()(100n n n n y x hf y y x y y Euler 改进方法：[]?? ? ??++==+++),(),(2)(11100n n n n n n y x f y x f h y y x y y 3.设计思想 在能够获得精确解的题目抽取题目，分别应用Euler 方法、Euler 改进方法求解数值结果，将所得结果列表或者画图，参照精确结果，对Euler 方法、Euler 改进方法的计算误差进行分析。 4.参考程序源代码 %fun 为目标函数字符串 %x0为自变量初始值。 %y0为fun(x0); %bou=[a,b]自变量区间 %h 为步长 fun='1/x^2-y^2'; bou=[1,6]; a=bou(1); b=bou(2); x0=1; y0=0; h=0.1; n=ceil((b-a)/h); xx=linspace(a,b,n+1)'; yy=zeros(1,n+1)'; lengthx=length(xx); xx(1)=x0;yy(1)=y0; for i=2:n+1 x=xx(i-1);y=yy(i-1); k=eval(fun); yy(i)=yy(i-1)+h*k; end Ys=dsolve('Dy=1/x^2-y^2','y(1)=0','x'); for i=1:lengthx x=xx(i); exacty(i)=eval(Ys); end YY=exacty'; yend=[xx,yy,YY] p=plot(xx,yend(:,2),'k-o','LineWidth',1,... 'MarkerEdgeColor','k',... 'MarkerFaceColor','g',... 'MarkerSize',4); hold on; pp=plot(xx,yend(:,3),'r-.+','LineWidth',0.8,... 'MarkerEdgeColor','r',... 'MarkerFaceColor','m',... 'MarkerSize',6); legend([p,pp],'Eula','jiequejie'); %fun为目标函数字符串 %x0为自变量初始值。 %y0为fun(x0); %bou=[a,b]自变量区间 %h为步长 fun='1/x^2-y^2'; bou=[1,6]; a=bou(1); b=bou(2); x0=1; y0=0; 第8章 常微分方程数值解法 本章主要内容： 1．欧拉法、改进欧拉法. 2．龙格-库塔法。 3．单步法的收敛性与稳定性。 重点、难点 一、微分方程的数值解法 在工程技术或自然科学中，我们会遇到的许多微分方程的问题，而我们只能对其中具有较简单形式的微分方程才能够求出它们的精确解。对于大量的微分方程问题我们需要考虑求它们的满足一定精度要求的近似解的方法，称为微分方程的数值解法。本章我们主要 讨论常微分方程初值问题?????==00 )() ,(y x y y x f dx dy 的数值解法。 数值解法的基本思想是：在常微分方程初值问题解的存在区间[a,b]内，取n+1个节点a=x 0＜x 1＜…＜x N =b （其中差h n = x n –x n-1称为步长，一般取h 为常数，即等步长），在这些节点上把常微分方程的初值问题离散化为差分方程的相应问题，再求出这些点的上的差分方程值作为相应的微分方程的近似值（满足精度要求）。 二、欧拉法与改进欧拉法 欧拉法与改进欧拉法是用数值积分方法对微分方程进行离散化的一种方法。 将常微分方程),(y x f y ='变为() *+=?++1 1))(,()()(n x n x n n dt t y t f x y x y 1．欧拉法（欧拉折线法） 欧拉法是求解常微分方程初值问题的一种最简单的数值解法。 欧拉法的基本思想：用左矩阵公式计算（＊）式右端积分，则得欧拉法的计算公式为：N a b h N n y x hf y y n n n n -= -=+=+)1,...,1,0(),(1 欧拉法局部截断误差 11121 )(2 ++++≤≤''=n n n n n x x y h R ξξ或简记为O （h 2）。 Euler法解常微分方程 Euler法解常微分方程算法： Step 1 分别取积分上限、积分下限、步长 Step 2计算判断是否成立，成立转到Step 3，否则继续进行Step 4 Step 3 计算 Step 4 Euler法解常微分方程算程序： function euler2(fun,y0,A,h) %fun--y' %y0---初值 %A----x取值范围 %a----x左区间端点值 %b----x右区间端点值 %h----给定步长 x=min(A); b=max(A); y=y0; while x Step 3 （1）做显性Euler预测 （2）将带入 Step 4计算判断是否成立，成立返回Step 3，否则继续进行Step 5 Step 5 改进Euler法解常微分方程算程序： function gaijineuler2(fun,y0,A,h) %fun--y' %y0---初值 %A----x取值范围 %a----x左区间端点值 %b----x右区间端点值 %h----给定步长 a=min(A); b=max(A); x=a:h:b; y(1)=y0; for i=1:length(x)-1 w1=feval(fun,x(i),y(i)); y(i+1)=y(i)+h*w1; w2=feval(fun,x(i+1),y(i+1)); y(i+1)=y(i)+h*(w1+w2)/2; end x=x' y=y' 例：用改进Euler法计算下列初值问题（取步长h=0.25） 输入：fun=inline('-x*y^2') gaijineuler2(fun,2,[0 5],0.25) 得到： x = 0.2500 0.5000 0.7500 1.0000 1.2500 1.5000 1.7500 2.0000 2.2500 2.5000 2.7500 用改进的欧拉方法和四阶龙格-库塔方法解初值问题 一、题目： 取步长2.0=h ，分别用改进的欧拉方法和四阶龙格—库塔方法解初值问题 ? ??=≤≤+=.1)0(;10,'y x y x y 并比较结果。 二、基本思想： 1.改进的欧拉方法 改进的欧拉方法用梯形公式计算()()()()+1+1-=,.n n x n n x y x y x f x y x dx ?中的积分，并以 n y 和+1n y 分别表示()n y x 和()+1n y x 的近似值，就得到 ()()()+1+1+1=+,+,.2 n n n n n n h y y f x y f x y （梯形公式） 梯形公式也是一个一步法公式。由于公式右端也含有未知的+1n y ，故被称作是隐式的。隐式格式实际上是关于+1n y 的一个函数方程。为了避免解方程，可以采用欧拉方法计算初始值，再由梯形公式计算。这样建立起来的计算格式称为改进的欧拉格式： ()()()()+1+1+1=+,,=+,+,.2 p n n n n n n n n n y y hf x y h y y f x y f x y ????? 梯形公式也可以采用迭代法求解。如果仍然采用欧拉方法计算迭代初值，那么计算格式就是 []()[]()[]()() 0+1+1+1+1+1=+,,=+,+,.2n n n n k k n n n n n n y y hf x y h y y f x y f x y ????? 由于已假定(),f x y 满足里普希兹条件，所以有 [][][]()[]() [][]+1-1-1+1+1+1,+1+1+1+1+1-=-,-.22 k k k k k k n n n n n n n n h hL y y f x y f x y y y ≤ 从而，迭代的收敛条件是0<<1.2hL 2.四阶龙格-库塔方法 龙格—库塔方法不是用求导数的办法，而是用计算不同点上()y x f ,的函数值，然后对这些函数值作线性拟合，构造近似公式。组合的原则是使得近似公式与泰勒展开式有尽可能多的项吻合，以达到较高的精度。 改进的欧拉格式 《离散数学》实验报告 （2015 / 2016 学年第一学期） 题目：图的随机生成及欧拉（回）路的确定 专业信息安全 学生姓名 班级学号 指导教师 指导单位计算机学院计算机科学与技术系 日期2015年12月29日 图的随机生成及欧拉（回）路的确定 一、实验内容和要求 内容：编程随机生成n个结点的无向图并能进行（半）欧拉图的判定，若是则给出欧拉（回）路。 要求：对给定n个结点，随机生成邻接矩阵以确定某无向简单图并进行欧拉图和半欧拉图的判定，若符合则给出至少一条欧拉回路或欧拉路。 二、实验目的 对给定n个结点，随机生成邻接矩阵以确定某无向简单图并进行欧拉图和半欧拉图的判定，若符合则给出至少一条欧拉回路或欧拉路。 三、实验任务 1、输入结点个数据生成随机图 2、进行（半）欧拉图的判定 3、若是则给出欧拉（回）路。 四、实验内容 #include 常微分方程欧拉算法 Prepared on 22 November 2020 常微分方程欧拉算法 摘要：本文主要论述了常微分方程的欧拉算法的算法原理，误差分析，实例，程序，以及算法比较等内容。 关键词：常微分方程 显式欧拉法 隐式欧拉法 引言：微分方程初值问题模型是常见的一类数学模型。对于一些简单而典型的微分方程模型，譬如线性方程、某些特殊的一阶非线性方程等是可以设法求出其解析解的，并有理论上的结果可资利用。但在数学建模中碰到的常微分方程初值问题模型，通常很难，甚至根本无法求出其解析解，而只能求其近似解。因此，研究其数值方法，以便快速求得数值鳃有其重大意义。 一、欧拉算法原理 对于微分方程初值问题 的解在xy 平面上是一条曲线，称为该微分方程的积分曲线。积分曲线上一点(),x y 的切线斜率等于函数f 在点(),x y 的值，从初始点()000,P x y 出发，向该点的切线方向推进到下一个点()111,P x y ，然后依次做下去，得到后面的未知点。一般地，若知道(),n n n P x y 依上述方法推进到点()111,n n n P x y +++，则两点的坐标关系为： 即 这种方法就是欧拉（Euler ）方法（也叫显式欧拉法或向前欧拉法）。当初值0y 已知，则n y 可以逐步算出 对微分方程()=x y dy f dx ，从n x 到1n x +积分，那么有 现在用左矩形公式()(),n n hf x y x 代替()()1 ,n n x x f t y t dt +?，n y 代替()n y x ，1n y +代替() 1n y x +就得到了欧拉方法。如果用右矩形公式()()11,n n hf x y x ++去代替右端积分，则得到另外一 个公式，该方法就称为隐式欧拉法（或后退欧拉法），其公式为 欧拉公式与隐式欧拉公式的区别在于欧拉公式是关于1n y +的一个直接计算公式，然而隐式欧拉公式右端含有1n y +，所以它实际上是关于1n y +的一个函数方程。 二、实例 例 取h=，用Euler 方法解Euler方法与改进的Euler方法的应用
常微分方程作业欧拉法与改进欧拉法
求欧拉回路的Fleury算法
常微分方程的Euler解法
求欧拉回路的Fleury算法
欧拉及改进的欧拉法求解常微分方程
欧拉路径(欧拉回路)算法
欧拉回路的求解matlab
求欧拉回路,Fleury算法的C语言实现[1]
实验8欧拉法_改进欧拉法_线性多步法
MATLAB Euler法解常微分方程
数值计算上机第七题关于改进欧拉方法
常微分方程欧拉算法
Euler方法及其改进方法
第8章 常微分方程数值解法 本章主要内容： 1.欧拉法、改进欧拉法 2
MATLABEuler法解常微分方程
用改进的欧拉方法和四阶龙格-库塔方法解初值问题
图的随机生成及欧拉(回)路的确定
常微分方程欧拉算法
相关主题
文本预览