学号：
课程设计
题目Dijkstra算法的MATLAB实现
学院信息工程学院
专业通信工程
班级
姓名
指导教师
2012 年 1 月9 日
课程设计任务书
学生姓名：专业班级：通信 0901班
指导教师：工作单位：信息工程学院
题目: Dijkstra算法的MATLAB实现
初始条件：
（1）MATLAB应用软件的基本知识以及基本操作技能
（2）高等数学、线性代数等基础数学中的运算知识
（3）数据结构里面关于Dijkstra算法的基本原理和思想
要求完成的主要任务:
必做题：采用MATLAB选用适当的函数或矩阵进行如下计算
（1）极限的计算、微分的计算、积分的计算、级数的计算、求解代数方程、求解常微分方程；
（2）矩阵的最大值、最小值、均值、方差、转置、逆、行列式、特征值的计算、矩阵的相乘、右除、左除、幂运算；
（3）多项式加减乘除运算、多项式求导、求根和求值运算、多项式的部分分式展开、多项式的拟合、插值运算。
选做题：Dijkstra算法的MATLAB实现
时间安排：
第一周，安排任务地点：鉴主17楼实验室
第1-17，周仿真设计地点：鉴主13楼计算机实验室
第18周，完成答辩，提交报告地点：鉴主17楼实验室
指导教师签名：年月日
系主任（或责任教师）签名：年月
目录
摘要................................................................................................................................. I Abstract ......................................................................................................................... II 1 MATLAB的基本运算 .. (1)
1.1 基础微积分计算 (1)
1.1.1 极限的基本运算 (1)
1.1.2 微分的计算 (1)
1.1.3 积分的计算 (2)
1.1.4 级数的运算 (3)
1.1.5 求解代数微分方程 (3)
1.1.6 求解常微分方程 (4)
1.2 矩阵的基本运算 (5)
1.2.1 矩阵的最大最小值 (5)
1.2.2 矩阵的均值方差 (6)
1.2.3 矩阵的转置和逆 (7)
1.2.4 矩阵的行列式 (7)
1.2.5 矩阵特征值的计算 (8)
1.2.6 矩阵的相乘 (8)
1.2.7 矩阵的右除和左除 (9)
1.2.8 矩阵的幂运算 (9)
1.3 多项式的基本运算 (10)
1.3.1 多项式的四则运算 (10)
1.3.2 多项式的求导、求根、求值运算 (11)
1.3.3 多项式的部分分式展开 (12)
1.3.4 多项式的拟合 (13)
1.3.5 多项式的插值运算 (14)
2关于Dijkstra的问题描述 (15)
2.1问题的提出 (15)
2.2 Dijkstra算法的算法思想 (15)
2.3 Dijkstra算法的算法原理 (15)
3 Dijkstra算法的设计分析 (17)
3.1 Dijkstra算法部分的设计分析 (17)
3.2 程序主体的设计分析 (17)
4程序源代码与算法思想 (19)
4.1 文件isIn.m的源代码 (19)
4.2 文件default_dat.m的源代码 (19)
4.3 文件input_dat.m的源代码 (19)
4.4 文件menu.m的源代码 (20)
4.5 文件dijkstra.m的源代码 (22)
5 测试报告 (27)
6 心得体会 (30)
7 参考文献 (31)
摘要
MATLAB的功能十分强大，在本篇中，主要分别介绍了MATLAB在高等数学中微机分的一些基本运算，线性代数中矩阵的一些基本计算以及多项式中的计算，采用具体举例，然后根据具体的例子建模，然后编写m文件，然后实际调试运行来得出结果的方式来整理报告。在报告中为了计算的方便，在矩阵那一方面，我采用事先定义的方式，便于以后计算直接提取。在多项式那一大块我也是采用这种方式。还有文中有些运算需要通过画出图形来显示运算的效果，我也适当的画了图形来显示。
此外，本篇还对Dijkstra算法用MATLAB来实现，分析了Dijkstra算法的基本思想，设计思想，以及怎么样用MATLAB来进行实现。并且对实现的结果进行了分析。
关键字：基本运算、MATLAB 、 Dijkstra算法
Abstract
The function of MATLAB is very strong.The main difference I have introduced in advanced mathematics MATLAB computer points in some of the basic operations, linear algebra .Some basic calculations in the matrix and the calculation of the polynomial, using concrete examples, and then the specific .Examples of modeling, then write m file, and then to the commissioning way to organize the findings reported .In order to calculate the convenience of the report, in the matrix that one, I used the pre-defined way, to facilitate .After the calculation of direct extraction. Polynomial which is large in this way I am. There are some text.Operations need to draw a graph to show the effect of computing, I also painted the appropriate graphics to display.
In addition,the main essay I have introduced used MATLAB to enforce the Dijkstra arithmetic,analysis the basic thoughts,design thoughts of the Dijkstra arithmetic and how to use MATLAB to enforce it.Besides,the essay analysis the result of it.
Keywords: basic calculations，MATLAB, Dijkstra arithmetic
1 MATLAB的基本运算
1.1 基础微积分计算
微积分的计算在工程应用上有着广泛的应用，可以说微积分的计算是数学的基础，而MATLAB关于这一点有着很好的应用，MATLAB功能强大，对于微积分也有专门的函数来进行运算，关于基础的微机分计算主要有求函数的极限，微分运算，积分运算，级数的计算，代数的求解，以及常微分方程的求解，下面对这些分别进行介绍。
1.1.1 极限的基本运算
MATLAB中极限函数limit格式如下：
limit(F,x,a) ；limit(F,a)；limit(F)；limit(F,x,a,'right')；
limit(F,x,a,'left')
其中F表示的是函数式，x表示求极限的变量，a表示的是变量取的值，left或right表示是取左极限还是右极限。
例求
)
3
(
lim2x
x
x
x
-
+
∞
→
分析：这是一个典型的求极限的题目，题目中涉及了一个变量，先要对其进行定义，然后直接利用函数limit编程计算。
示例程序和运行结果如下：
1.1.2 微分的计算
MATLAB中微分函数diff格式如下：
Y = diff(X)；Y = diff(X,n)；Y = diff(X,n,dim)
其中X 表示待微分的变量，n 表示n 次微分，第三式表示沿着定维dim 的n 阶微分。
例 求sin ln y x x x =的导数
分析：微分运算能直观的显示函数值的变化快慢，在平时计算中常常反映变量的变化对函数值的影响
程序和运行结果如下：
1.1.3 积分的计算
MATLAB 中积分常用函数为int ，格式为：int(f,x,a,b)
其中f 表示待积分的函数，x 表示积分变量，而a ，b 则分别表示积分起始终止点。
例 求下列变上限积分?+2
1x x
dx x
分析：积分运算大量运用于求面积体积等，此处选用的是一个变上限积分，属于有些典型的积分例子，但任然是根据函数格式就可以写出程序。
程序和运行结果如下：
1.1.4 级数的运算
MATLAB中级数常用函数为symsum，格式如下：
r = symsum(s)；r = symsum(s,v)；r = symsum(s,a,b)；r = symsum(s,v,a,b) 函数表达的意义是表达式s关于变量v从a到b求和。
例求级数∑
=+
9
1
1 1
n n
的值
分析：对于级数我们最先接触的就是常数项无穷级数, 直接用symsum 函数上下限从1到9 即可。
程序和运行结果如下：
1.1.5 求解代数微分方程
代数方程分为很多种，有简单有复杂，方法也有很多。可用MATLAB符号工具箱中的solve( )函数， MATLAB中求解代数方程常用函数solve格式如下：[x,…]=solve(eqn1,eqn2,…,eqnn，’x,…’)
其中eqn表示的是式子，x等表示的是变量。
例：求解方程组5x-2=18
分析：为了计算的简单，这里选用了基础的一元一次方程，直接用语句描述即可。
程序以及运行结果如下：
1.1.6 求解常微分方程
常微分方程是指未知的一元函数以及它的某些阶的导数连同自变量都由一已知方程联系在一起的方程。
dsolve的基本格式是：
s=dsolve(‘方程1’, ‘方程2’,…,’初始条件1’，’初始条件2’…,’自变量’)
例：求解微分方程y''=2+y’，y(0)=0,y'(0)=0的解析解
分析：求解此微分方程的解析解直接采用dsolve即可。
程序和运行结果如下：
1.2 矩阵的基本运算
矩阵在日常工程应用中也用的十分广泛，矩阵计算是线性代数中的核心内容，其对于整个数学系统的计算方面的意义是十分巨大的，集中它的基本运算包括最大值、最小值、均值、方差、转置、逆、行列式、特征值的计算、矩阵的相乘、右除、左除、幂运算等等，下面将具体介绍。
矩阵的运算都是要以矩阵为基础的，本报告中决定选用一组矩阵来完成几乎全部可以完成的计算，那么首先就得生成矩阵了。
1.2.1 矩阵的最大最小值
MATLAB中max函数可以表示求每一列的最大值，求最小值的函数为min，那么经过分析可以知道，先求出每一列的最大值然后求出这些最大值里面的最大值，最小值也类似，下面以A矩阵为例。
程序及运行结果如下：
MATLAB中求解矩阵均值的函数是mean，它的具体用法如下：
mean(A,1)表示对列取平均，mean(A,2）表示对行取平均，mean(A）则默认为mean(A,1)。若要求矩阵的均值可以进行两次求平均值，这样就可以得到矩阵的平均值，或者，直接mean(A(:))，更加简便。
MATLAB中求解矩阵方差的函数是var，它的常用格式是V = var(X)，如果X 是一个矩阵，var(X)返回一个包含矩阵X每一列方差的行向量。与求均值不同的是，矩阵的方差不可以通过两次求方差获得，而是用var(X(:))来求得，下面的例子可以看出，通过两次求得的结果并不正确。
还是以矩阵A为例，实验程序以及运行结果如下：
矩阵的转置是矩阵运算之中很重要的一个，如果A是一个实数矩阵，那么它被转置时，第1行变成第1列，第2行变成第2列，依此类推，一个m×n矩阵变为一个n×m矩阵。MATLAB中求转置的函数是conj，Y=conj(X) 实际中求矩阵的逆要求矩阵是方阵，MATLAB中求逆的函数是inv，格式为Y = inv(X)。
实验程序和运行结果如下：
1.2.4 矩阵的行列式
实际中求矩阵的行列式均要求矩阵是方阵，求矩阵行列式的函数是det，格式为Y = det(X)，实验程序及运行结果如下：
1.2.5 矩阵特征值的计算
求矩阵的特征值和特征向量用eig函数。
[V,D] =eig(A)产生一个矩阵A的特征值在对角线上的对角矩阵D和矩阵V，它的列是相应的特征向量，满足AV=VD，下面以矩阵A为例来演示。
1.2.6 矩阵的相乘
MATLAB中求矩阵的乘积直接用符号*即可，下面以A、B矩阵为例来分别演示AB与BA区别。实验程序和运行结果如下：
观察运行结果可以发现，两个结果不一样，说明矩阵的相乘不满足交换律。
1.2.7 矩阵的右除和左除
在MATLAB中，有两个矩阵除法的符号，左除“ \”和右除“/”。MATLAB执行它们时是不同的，且在MATLAB中求解一个系统用左除比用逆和乘法所需的运算次数要少。程序以及运行结果如下：
1.2.8 矩阵的幂运算
对于二维方阵，A的p次乘方可以用A^p实现。如果p是一个正整数，那么这个幂可以由许多矩阵乘法运算定义。对于 p= 0，得到与A维数相同的同一个矩阵；当 p< 0时，如果A- 1存在，可定义A ^p，它是与inv(A)^(-p)相同。
程序以及运行结果如下：
1.3 多项式的基本运算
多项式的运算，主要包括多项式加减乘除、多项式求导、求根和求值运算、多项式的部分分式展开、多项式的拟合、插值运算。
1.3.1 多项式的四则运算
多项式的四则运算就是包括加减乘除，其中加减运算可以直接用+、-来运算，它们的运算规则中注意要满足向量的长度相同，而乘除就得用函数了，其中乘法的计算函数是conv，它本来是卷积的意思，同时它也符合多项式函数的运算规则，除法运算是相乘的逆运算，但会有余子式。程序和运行结果如下：
1.3.2 多项式的求导、求根、求值运算
多项式求导数的函数是polyder，调用格式是e=polyder（c），其中c表示的是待求导的函数式，然后求根运算的函数是roots或poly，其中roots是根据函数求多项式的根，它的调用格式是h=roots（c），c代表待求根的函数式，而poly函数是根据根求函数，格式是i=poly（h），表示根据h求函数i，然后求值运算的函数是polyval，将多项式的自变量赋予值z，则调用格式是j=polyval（f，z），表示当变量是1时，函数f的结果。
程序和运行结果如下：
1.3.3 多项式的部分分式展开
函数residue可以将多项式之比用部分分式展开，也可以将一个部分分式表示为多项式之比。其调用格式如下：
[r,p,k]=residue(a,b)返回多项式之比a/b的部分分式展开，参照下面公式。[a,b]=residue(r,p,k)返回部分分式的多项式向量。
程序及运行结果如下：
1.3.4 多项式的拟合
多项式拟合用polyfit(x,y,n)来实现，n 是拟合多项式的阶次。调用函数polyfit 常用格式为p = polyfit(x,y,n)，x 为变量，y 为函数，n 为阶数。为了能形象说明问题，采用绘图来演示。
实验程序以及运行结果如下：
01234567
-1-0.5
0.5
1
1.501234567
-1-0.5
0.5
1
1.5
由上面两个图对比可知，高次拟合比低次拟合效果好，更加贴近实际情况。
1.3.5 多项式的插值运算
插值函数通常是分段的，，插值数据通过给定的数据点x，y。插值函数一般地可表示为yi=interpi（x,y,xi,’method’）其中i代表几维插值可取1、2,xi为插值范围内的任意点集的x坐标,yi是插值后对应数据点集的坐
标,method为插值函数的类型选项，有linear为线性，也是缺省项，cubic和cubic spline为三次样条等三样。
程序以及运行结果如下：
2关于Dijkstra的问题描述
2.1问题的提出
给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
2.2 Dijkstra算法的算法思想
按路径长度递增次序产生最短路径算法：
把V分成两组：
（1）S：已求出最短路径的顶点的集合
（2）V-S=T：尚未确定最短路径的顶点集合
将T中顶点按最短路径递增的次序加入到S中，
保证：
（1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度。
（2）每个顶点对应一个距离值
S中顶点：从V0到此顶点的最短路径长度
T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度。
依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和。
2.3 Dijkstra算法的算法原理
首先，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。如D[3]=2表示从始点v到终点3的路
两个指定顶点之间的最短路径 问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。 以各城镇为图G 的顶点，两城镇间的直通铁路为图G 相应两顶点间的边，得图G 。对G 的每一边e ，赋以一个实数)(e w —直通铁路的长度，称为e 的权，得到赋权图G 。G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点00,v u 间的具最小权的轨。这条轨叫做00,v u 间的最短路，它的权叫做00,v u 间的距离，亦记作),(00v u d 。 求最短路已有成熟的算法：迪克斯特拉（Dijkstra ）算法，其基本思想是按距0u 从近到远为顺序，依次求得0u 到G 的各顶点的最短路和距离，直至0v （或直至G 的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。 (i) 令0)(0=u l ，对0u v ≠，令∞=)(v l ，}{00u S =，0=i 。 (ii) 对每个i S v ∈（i i S V S \=），用 )}()(),({min uv w u l v l i S u +∈ 代替)(v l 。计算)}({min v l i S v ∈，把达到这个最小值的一个顶点记为1+i u ，令}{11++=i i i u S S 。 (iii). 若1||-=V i ，停止；若1||- function [c0,c,path0,path]=dijkstra(s,t,C,flag) % Use the Dijkstra's algorithm to find the shortest path from % s to t and can also find the shortest path between s and all % the other points. % Reference: Graph Theory with Applications by J. A. Bondy and % U. S. R. Murty. % Input -- s is the starting point and also is the point s. % -- t is the given terminal point and is the point t. % -- C \in R^{n \times n}is the cost matrix, where % C(i,j)>=0 is the cost from point i to point j. % If there is no direct connection between point i and % j, C(i,j)=inf. % -- flag: if flag=1, the function just reports the % shortest path between s and t; if flag~=1, the % function reports the shortest path between s and t, % and the shortest paths between s and other points. % Output -- c0 is the minimal cost from s to t. % -- path0 denotes the shortest path form s to t. % -- c \in R{1\times n} in which the element i is the % minimal cost from s to point i. % -- path \in R^{n \times n} in which the row i denotes % the shortest path from s to point i. % Copyright by MingHua Xu(徐明华), Changhzou University, 27 Jan. 2014. s=floor(s); t=floor(t); n=size(C,1); if s<1 || t < 1 || s > n || t > n error(' The starting point and the terminal point exceeds the valid range'); end if t==s disp('The starting point and the terminal point are the same points'); end label=ones(1,n)*inf; label(s)=0; S=[s]; Sbar=[1:s-1,s+1:n]; c0=0; path=zeros(n,n); path(:,1)=s; c=ones(1,n)*inf; parent=zeros(1,n); i=1; % number of points in point set S. while i 学号： 课程设计 题目Dijkstra算法的MATLAB实现 学院信息工程学院 专业通信工程 班级 姓名 指导教师 2012 年 1 月9 日 课程设计任务书 学生姓名：专业班级：通信 0901班 指导教师：工作单位：信息工程学院 题目: Dijkstra算法的MATLAB实现 初始条件： （1）MATLAB应用软件的基本知识以及基本操作技能 （2）高等数学、线性代数等基础数学中的运算知识 （3）数据结构里面关于Dijkstra算法的基本原理和思想 要求完成的主要任务: 必做题：采用MATLAB选用适当的函数或矩阵进行如下计算 （1）极限的计算、微分的计算、积分的计算、级数的计算、求解代数方程、求解常微分方程； （2）矩阵的最大值、最小值、均值、方差、转置、逆、行列式、特征值的计算、矩阵的相乘、右除、左除、幂运算； （3）多项式加减乘除运算、多项式求导、求根和求值运算、多项式的部分分式展开、多项式的拟合、插值运算。 选做题：Dijkstra算法的MATLAB实现 时间安排： 第一周，安排任务地点：鉴主17楼实验室 第1-17，周仿真设计地点：鉴主13楼计算机实验室 第18周，完成答辩，提交报告地点：鉴主17楼实验室 指导教师签名：年月日 系主任（或责任教师）签名：年月 目录 摘要................................................................................................................................. I Abstract ......................................................................................................................... II 1 MATLAB的基本运算 .. 0 1.1 基础微积分计算 0 1.1.1 极限的基本运算 0 1.1.2 微分的计算 0 1.1.3 积分的计算 (1) 1.1.4 级数的运算 (1) 1.1.5 求解代数微分方程 (1) 1.1.6 求解常微分方程 (2) 1.2 矩阵的基本运算 (2) 1.2.1 矩阵的最大最小值 (2) 1.2.2 矩阵的均值方差 (3) 1.2.3 矩阵的转置和逆 (3) 1.2.4 矩阵的行列式 (3) 1.2.5 矩阵特征值的计算 (3) 1.2.6 矩阵的相乘 (4) 1.2.7 矩阵的右除和左除 (4) 1.2.8 矩阵的幂运算 (4) 1.3 多项式的基本运算 (4) 1.3.1 多项式的四则运算 (4) 1.3.2 多项式的求导、求根、求值运算 (5) 1.3.3 多项式的部分分式展开 (5) 1.3.4 多项式的拟合 (5) 1.3.5 多项式的插值运算 (6) 2关于Dijkstra的问题描述 (6) 2.1问题的提出 (6) 2.2 Dijkstra算法的算法思想 (7) 2.3 Dijkstra算法的算法原理 (7) 3 Dijkstra算法的设计分析 (8) 3.1 Dijkstra算法部分的设计分析 (8) 3.2 程序主体的设计分析 (9) 4程序源代码与算法思想 (10) 4.1 文件isIn.m的源代码 (10) 4.2 文件default_dat.m的源代码 (11) 4.3 文件input_dat.m的源代码 (11) 4.4 文件menu.m的源代码 (11) 4.5 文件dijkstra.m的源代码 (13) 5 测试报告 (16) 6 心得体会 (17) 7 参考文献 (18) Dijkstra算法是寻找最短路径的一种搜索算法，由荷兰科学家提出。 1)算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径, 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v 到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。 2)算法步骤： a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点， 即:U={其余顶点}，若v与U中顶点u有边，则 过程如下： 在网上搜索一些版本的Matlab实现方法，感觉都有些毛病。经过修改，得到比较好的效果。[cpp]view plain copy 1.function [ distance path] = Dijk( W,st,e ) 2.%DIJK Summary of this function goes here 3.% W 权值矩阵 st 搜索的起点 e 搜索的终点 4.n=length(W);%节点数 5. D = W(st,:); 6.visit= ones(1:n); visit(st)=0; 7.parent = zeros(1,n);%记录每个节点的上一个节点 8. 9.path =[]; 10. 11.for i=1:n-1 最短路径—Dijkstra算法 Dijkstra算法 1.定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。 问题描述：在无向图G=(V,E) 中，假设每条边E[i] 的长度为w[i]，找到由顶点V0 到其余各点的最短路径。（单源最短路径） 2.算法描述 1)算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S 中只有一个源点，以后每求得一条最短路径, 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。 2)算法步骤： a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边， 则 第一章插值方法 1.1Lagrange插值 1.2逐步插值 1.3分段三次Hermite插值 1.4分段三次样条插值 第二章数值积分 2.1 Simpson公式 2.2 变步长梯形法 2.3 Romberg加速算法 2.4 三点Gauss公式 第三章常微分方程德差分方法 3.1 改进的Euler方法 3.2 四阶Runge-Kutta方法 3.3 二阶Adams预报校正系统 3.4 改进的四阶Adams预报校正系统 第四章方程求根 4.1 二分法 4.2 开方法 4.3 Newton下山法 4.4 快速弦截法 第五章线性方程组的迭代法 5.1 Jacobi迭代 5.2 Gauss-Seidel迭代 5.3 超松弛迭代 5.4 对称超松弛迭代 第六章线性方程组的直接法 6.1 追赶法 6.2 Cholesky方法 6.3 矩阵分解方法 6.4 Gauss列主元消去法 第一章插值方法 1.1Lagrange插值 计算Lagrange插值多项式在x=x0处的值. MATLAB文件：（文件名：Lagrange_eval.m）function [y0,N]= Lagrange_eval(X,Y,x0) %X,Y是已知插值点坐标 %x0是插值点 %y0是Lagrange插值多项式在x0处的值 %N是Lagrange插值函数的权系数 m=length(X); N=zeros(m,1); y0=0; for i=1:m N(i)=1; for j=1:m if j~=i; N(i)=N(i)*(x0-X(j))/(X(i)-X(j)); end end y0=y0+Y(i)*N(i); end 用法》X=[…];Y=[…]; 》x0= ; 》[y0,N]= Lagrange_eval(X,Y,x0) 1.2逐步插值 计算逐步插值多项式在x=x0处的值. MATLAB文件：（文件名：Neville_eval.m）function y0=Neville_eval(X,Y,x0) %X,Y是已知插值点坐标 %x0是插值点 %y0是Neville逐步插值多项式在x0处的值 m=length(X); P=zeros(m,1); P1=zeros(m,1); P=Y; for i=1:m P1=P; k=1; for j=i+1:m k=k+1; 图论实验三个案例 单源最短路径问题 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到j v 的权ij w =∞。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在 1 i v +，使 1()min{()} i l v l v +=，v S ∈； ⑤ 1{} i S S v +=， 1{} i S S v +=-，1i i =+，转②； 实际上，Dijkstra 算法也是最优化原理的应用：如果12 1n n v v v v -是从1v 到 n v 的最短路径，则 12 1 n v v v -也必然是从1v 到 1 n v -的最优路径。 在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元 素表示顶点i v 到j v 的权ij w ，若i v 到j v 无边，则realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数+308)。 function re=Dijkstra(ma) 第8章 常微分方程初值问题数值解法 8.1 引言 8.2 欧拉方法 8.3 龙格-库塔方法 8.4 单步法的收敛性与稳定性 8.5 线性多步法 8.1 引 言 考虑一阶常微分方程的初值问题 00(,),[,],(). y f x y x a b y x y '=∈=（1.1） （1.2） 如果存在实数 ，使得 121212(,)(,).,R f x y f x y L y y y y -≤-?∈（1.3） 则称 关于 满足李普希茨(Lipschitz ）条件， 称为 的李普希茨常数（简称Lips.常数）. 0>L f y L f (参阅教材386页) 计算方法及MATLAB 实现 所谓数值解法，就是寻求解 在一系列离散节点 )(x y <<<<<+121n n x x x x 上的近似值 . ,,,,,121+n n y y y y 相邻两个节点的间距 称为步长. n n n x x h -=+1 如不特别说明，总是假定 为定数， ),2,1( ==i h h i 这时节点为 . ) ,2,1,0(0 =+=i nh x x n 初值问题(1.1),(1.2)的数值解法的基本特点是采取 “步进式”. 即求解过程顺着节点排列的次序一步一步地向前推进. 00(,),[,], (). y f x y x a b y x y '=∈= 描述这类算法，只要给出用已知信息 ,,,21--n n n y y y 计算 的递推公式. 1+n y 一类是计算 时只用到前一点的值 ，称为单步法. 1+n y n y 另一类是用到 前面 点的值 ， 1+n y k 11,,,+--k n n n y y y 称为 步法. k 其次，要研究公式的局部截断误差和阶，数值解 与 精确解 的误差估计及收敛性，还有递推公式的计算 稳定性等问题. n y )(n x y 首先对方程 离散化，建立求数值解的递推 公式. ),(y x f y =' 用MATLAB实现结构可靠度计算 口徐华…朝泽刚‘u刘勇‘21 。 (【l】中国地质大学(武汉工程学院湖北?武汉430074; 12】河海大学土木工程学院江苏?南京210098 摘要:Matlab提供了各种矩阵的运算和操作,其中包含结构可靠度计算中常用的各种数值计算方法工具箱,本文从基本原理和相关算例分析两方面,阐述利用Matlab,编制了计算结构可靠度Matlab程.序,使得Matlab-语言在可靠度计算中得到应用。 关键词:结构可靠度Matlab软件最优化法 中图分类号:TP39文献标识码:A文章编号:1007-3973(200902-095-Ol 1结构可靠度的计算方法 当川概率描述结构的可靠性时,计算结构可靠度就是计算结构在规定时问内、规定条件F结构能够完成预定功能的概率。 从简单到复杂或精确稃度的不同,先后提出的可靠度计算方法有一次二阶矩方法、二次二阶矩方法、蒙特卡洛方法以及其他方法。一次■阶矩方法又分为。I-心点法和验算点法,其中验算点法足H前可靠度分析最常川的方法。 2最优化方法计算可靠度指标数学模型 由结构111n个任意分布的独立随机变量一,x:…以表示的结构极限状态方程为:Z=g(■.托…t=0,采用R-F将非正念变量当罱正态化,得到等效正态分布的均值o:和标准差虹及可靠度指标B,由可靠度指标B的几何意义知。o;辟 开始时验算点未知,把6看成极限状态曲面上点P(■,爿:---37,的函数,通过优化求解,找到B最小值。求解可靠皮指标aJ以归结为以下约束优化模型: rain睁喜t华,2 s.,.Z=g(工i,x2’,…,工:=0 如极限状态方栉巾某个变最(X。可用其他变量表示,则上述模型jfIJ‘转化为无约束优化模型: 。。B!:手f生丛r+阻:坚:坠:盐尘}二剐 t∞oY?’【叫,J 3用MATLAB实现结构可靠度计算 3.1Matlab简介 Matlab是++种功能强、效率高、便.丁.进行科学和工程计算的交互式软件包,汇集了人量数学、统计、科学和工程所需的函数,MATI.AB具有编程简甲直观、用户界mf友善、开放性强等特点。将MATLAB用于蒙特卡罗法的一个显著优点是它拥有功能强大的随机数发生器指令。 3.2算例 3.2.I例:已知非线形极限状态方程z=g(t r'H=567f r-0.5H2=0’f、r服从正态分布。IIf=0.6,o r=0.0786;la|_ 2.18,o r_0.0654;H服从对数正态分布。u H= 3218,O。 =0.984。f、r、H相互独立,求可靠度指标B及验算点(,,r’,H‘。 解:先将H当量正念化:h=ln H服从正态分布,且 ,‘-““了:等专虿’=,。49?口二-、『五ir面_。。3 作者：夏云木子 1、 >> syms re(x) re(y) re(z) >> input('计算相对误差：'),re(x)=10/1991,re(y)=0.0001/1.991,re(y)=0.0000001/0.0001991 所以可知re(y)最小，即y精度最高 2、 >> format short,A=sqrt(2) >> format short e,B=sqrt(2) >> format short g,C=sqrt(2) >> format long,D=sqrt(2) >> format long e,E=sqrt(2) >> format long g,F=sqrt(2) >> format bank,H=sqrt(2) >> format hex,I=sqrt(2) >> format +,J=sqrt(2) >> format,K=sqrt(2) 3、 >> syms A >> A=[sqrt(3) exp(7);sin(5) log(4)];vpa(pi*A,6) 4、1/6251-1/6252=1/6251*6252 5、（1）1/（1+3x）-(1-x)/(1+x)=x*(3*x-1)/[(1+3*x)*(1+x)] (2) sqrt(x+1/x)-sqrt(x-1/x)=2/x/[sqrt(x-1/x)+sqrt(x+1/x)] (3) log10(x1)-log(x2)=log10(x1/x2) (4) [1-cos(2*x)]/x =x^2/factorial(2)-x^4/factorial(4)+x^6/factorial(6)-… 利用计算机语言编程实现D算法 一：实验目的 本实验课程主要目的是让学生够熟练掌握图论中的D算法。 二：实验方法 选择MATLAB语言编程实现D算法。 三：实验要求 1.输入必要参数，包括：节点个数、节点间路径长度、给定节点； 2.输出给定节点到其它各节点的最短路径、径长； 3.节点间路径长度用矩阵形式表示。 四：实验内容 无向图共有7个节点，如下图所示。 v1 45 7 计算机输入的节点间路径长度为7×7矩阵： 1234567 1 2 3 4 5 6 7 0123 106 2054 304 5407 6408 780?? ∞∞∞?? ∞∞∞∞?? ??∞∞∞??∞∞∞∞?? ??∞∞∞ ??∞∞∞ ????∞∞∞∞ ??v v v v v v v v v v v v v v 若 1 v为指定节点，则1v到其它各节点的最短路径及径长的计算机计算结果为： 提示：不相邻的两个节点间∞可以用相对较大的数代替（如输入100表示∞） 五：实验原理 1. D 算法原理 已知图G=(V,E)，将其节点集分为两组：置定节点集p G 和未置定节点集 p G G -。其中p G 内的所有置定节点，是指定点s v 到这些节点的路径为最短（即已完成最短路径的计算）的节点。而p G G -内的节点是未置定节点，即s v 到未置定节点距离是暂时的，随着算法的下一步将进行不断调整，使其成为最短径。在调整各未置定节点的最短径时，是将p G 中的节点作为转接点。具体地说，就是将p G 中的节点作为转接点，计算（s v ,j v ）的径长（j p v G G ∈-），若该次计算的径长小于上次的值，则更新径长，否则，径长不变。计算后取其中径长最短者，之后将j v 划归到p G 中。当（p G G -）最终成为空集，同时p G G =，即求得s v 到所有其他节点的最短路径。 j w 表示s v 与其他节点的距离。 在p G 中，i w 表示上一次划分到p G 中的节点i v 到s v 得最短路径。在 p G G -中，表示s v 到j v （j p v G G ∈-）仅经过p G 中的节点作为转接点所求得的该次的最短路径的长度。 如果s v 与j v 不直接相连，且无置定节点作为转接点，则令j w =∞。 2. D 算法实现流程 D 算法流程如下图所示。 1、Newdon迭代法求解非线性方程 function [x k t]=NewdonToEquation(f,df,x0,eps) %牛顿迭代法解线性方程 %[x k t]=NewdonToEquation(f,df,x0,eps) %x:近似解 %k:迭代次数 %t:运算时间 %f:原函数，定义为内联函数 ?:函数的倒数，定义为内联函数 %x0:初始值 %eps:误差限 % %应用举例： %f=inline('x^3+4*x^2-10'); ?=inline('3*x^2+8*x'); %x=NewdonToEquation(f,df,1,0.5e-6) %[x k]=NewdonToEquation(f,df,1,0.5e-6) %[x k t]=NewdonToEquation(f,df,1,0.5e-6) %函数的最后一个参数也可以不写。默认情况下，eps=0.5e-6 %[x k t]=NewdonToEquation(f,df,1) if nargin==3 eps="0".5e-6; end tic; k=0; while 1 x="x0-f"(x0)./df(x0); k="k"+1; if abs(x-x0) < eps || k >30 break; end x0=x; end t=toc; if k >= 30 disp('迭代次数太多。'); x="0"; t="0"; end 2、Newdon迭代法求解非线性方程组 function y="NewdonF"(x) %牛顿迭代法解非线性方程组的测试函数 %定义是必须定义为列向量 y(1,1)=x(1).^2-10*x(1)+x(2).^2+8; y(2,1)=x(1).*x(2).^2+x(1)-10*x(2)+8; return; function y="NewdonDF"(x) %牛顿迭代法解非线性方程组的测试函数的导数 y(1,1)=2*x(1)-10; y(1,2)=2*x(2); y(2,1)=x(2).^+1; y(2,2)=2*x(1).*x(2)-10; return; 以上两个函数仅供下面程序的测试 function [x k t]=NewdonToEquations(f,df,x0,eps) %牛顿迭代法解非线性方程组 %[x k t]=NewdonToEquations(f,df,x0,eps) %x:近似解 %k:迭代次数 %t:运算时间 %f:方程组（事先定义） ?:方程组的导数（事先定义） %x0:初始值 %eps:误差限 % %说明：由于虚参f和df的类型都是函数，使用前需要事先在当前目录下采用函数M文件定义% 另外在使用此函数求解非线性方程组时，需要在函数名前加符号“@”，如下所示 % %应用举例： %x0=[0,0];eps=0.5e-6; %x=NewdonToEquations(@NewdonF,@NewdonDF,x0,eps) %[x k]=NewdonToEquations(@NewdonF,@NewdonDF,x0,eps) %[x k t]=NewdonToEquations(@NewdonF,@NewdonDF,x0,eps) %函数的最后一个参数也可以不写。默认情况下，eps=0.5e-6 %[x k t]=NewdonToEquations(@NewdonF,@NewdonDF,x0,eps) 图论实验三个案例 单源最短路径问题 1.1 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到 j v 的权 ij w =∞ 。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在1i v +，使1()min{()}i l v l v +=，v S ∈； ⑤ 1{}i S S v += ，1{}i S S v +=-，1i i =+，转②； 实际上，Dijkstra 算法也是最优化原理的应用：如果121n n v v v v - 是从1v 到n v 的最短路径，则121n v v v - 也必然是从1v 到1n v -的最优路径。 在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元素表示顶点i v 到 j v 的权 ij w ，若i v 到 j v 无边，则 realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数(1.7977e+308)。 function re=Dijkstra(ma) 信息系统分析与设计作业 层次分析法确定绩效评价权重在matlab中的实现 小组成员：孙高茹、王靖、李春梅、郭荣1 程序简要概述 编写程序一步实现评价指标特征值lam、特征向量w以及一致性比率CR的求解。 具体的操作步骤是：首先构造评价指标，用专家评定法对指标两两打分，构建比较矩阵，继而运用编写程序实现层次分析法在MATLAB中的应用。 通过编写MATLAB程序一步实现问题求解，可以简化权重计算方法与步骤，减少工作量，从而提高人力资源管理中绩效考核的科学化电算化。 2 程序在matlab中实现的具体步骤 function [w,lam,CR] = ccfx(A) %A为成对比较矩阵，返回值w为近似特征向量 % lam为近似最大特征值λmax，CR为一致性比率 n=length(A(:,1)); a=sum(A); B=A %用B代替A做计算 for j=1:n %将A的列向量归一化 B(:,j)=B(:,j)./a(j); end s=B(:,1); for j=2:n s=s+B(:,j); end c=sum(s);%计算近似最大特征值λmax w=s./c; d=A*w lam=1/n*sum((d./w)); CI=(lam-n)/(n-1);%一致性指标 RI=[0,0,0.58,0.90,1.12,1.24,1.32,1.41,1.45,1.49,1.51];%RI为随机一致 性指标 CR=CI/RI(n);%求一致性比率 if CR>0.1 disp('没有通过一致性检验'); else disp('通过一致性检验'); end end 3 案例应用 我们拟构建公司员工绩效评价分析权重，完整操作步骤如下： 3.1构建的评价指标体系 我们将影响员工绩效评定的指标因素分为：打卡、业绩、创新、态度与品德。 3.2专家打分，构建两两比较矩阵 A = 1.0000 0.5000 3.0000 4.0000 2.0000 1.0000 5.0000 3.0000 0.3333 0.2000 1.0000 2.0000 0.2500 0.3333 0.5000 1.0000 3.3在MATLAB中运用编写好的程序实现 直接在MATLAB命令窗口中输入 [w,lam,CR]=ccfx(A) 继而直接得出 d = 1.3035 2.0000 0.5145 0.3926 w = 0.3102 0.4691 0.1242 0.0966 lam =4.1687 最短路dijkstra算法Matlab程序调用举例 2014/4/17 徐明华 设赋权图如下图所示 下述Matlab程序 % test dijkstra's algorithm % The test example is take from the following book % Graph Theory with Applications by J. A. Bondy and U. S. R. Murty. % Page 16. clc s=1; t=5; flag=1; W=ones(11,11)*inf; % for i=1:11 W(i,i)=0; end W(1,2)=2; W(2,1)=2; W(2,3)=1; W(3,2)=1; W(3,4)=2; W(4,3)=2; W(4,5)=9; W(5,4)=9; W(5,6)=4; W(6,5)=4; W(6,7)=1; W(7,6)=1; W(7,8)=9; W(8,7)=9; W(8,1)=1; W(1,8)=1; W(1,9)=8; W(9,1)=8; W(9,2)=6; W(2,9)=6; W(9,8)=7; W(8,9)=7; W(9,7)=2; W(7,9)=2; W(9,10)=1;W(10,9)=1; W(9,3)=5; W(3,9)=5; W(10,7)=4; W(7,10)=4; W(10,11)=6; W(11,10)=6; W(10,3)=3; W(3,10)=3; W(11,7)=3; W(7,11)=3; W(11,6)=1; W(6,11)=1; W(11,4)=7; W(4,11)=7; W(11,5)=2; W(5,11)=2; W(11,3)=9; W(3,11)=9; [c0,c,path0,path]=dijkstra(s,t,W,flag); c0 path0 调用matlab函数dijkstra(具体见本文库文档：最短路dijkstra算法Matlab程序), 可得到顶点v1 到顶点v5的最短路径path0及最短路径的长度c0如下： c0 = 13 path0 = 1 2 3 10 9 7 6 11 5 如果将上述程序中的语句 flag=1; 替换为 flag=2; 并将 [c0,c,path0,path]=dijkstra(s,t,C,flag); c0 path0 替换为 [c0,c,path0,path]=dijkstra(s,t,C,flag); c path 运行程序可得到顶点v1到图中其他各顶点的最短路径所成矩阵path和各最短路径的长度所成向量c，其中path的第i行表示v1到第i个顶点的最短路径，c(i) 为v1到第i个顶点的最短路径的长度。具体运算结果如下： c = 0 2 3 5 13 10 9 1 7 6 11 path = 1 0 0 0 0 0 0 0 0 0 0 计算方法作业（作者：夏云木子） 1、help linspace type linspace 2、a1=[5 12 47;13 41 2;9 6 71];a2=[12 9;6 15;7 21];B=a1*a2, C=a1(:,1:2).*a2, D=a1.^2, E=a1(:).^2 3、a1=[5 12 47;13 41 2;9 6 71];a2=[12 9;6 15;7 21];a1(4:5,1:3)=a2.';a1([4 5],:)=a1([5 4],:);b1=a1 c1=b1(4,1),c2=b1(5,3),D=b1(3:4,:)*a2 4、a1=[5 12 47;13 41 2;9 6 71]; E=eye(3,3); S = a1 + 5*a1' - E, S1=a1^3-rot90(a1)^2+6*E 5、a1=[5 12 47;13 41 2;9 6 71];s=5;A=s-a1,B=s*a1,C=s.*a1,D=s./a1,E=a1./s 6、c=[1 2 3 4;5 6 7 8;9 10 11 12;13 14 15 16];A=c^-4,B=(c^3)^-1,C=(3*c+5*c^-1)/5 7、a=[1 i 3;9i 2-i 8;7 4 8+i];A=a.' 8、abc=[-2.57 8.87;-0.57 3.2-5.5i];m1=sign(abc),m2=round(abc),m3=floor(abc) Sign为符号函数，round表示四舍五入取整，floor表示舍去小数部分取整 9、x=[1 4 3 2 0 8 10 5]';y=[8 0 0 4 2 1 9 11]';A=dot(x,y) 10、a=[3.82 5.71 9.62];b=[7.31 6.42 2.48];A=dot(a,b),B=cross(a,b) 11、P=[5 7 8 0 1];Pf=poly(P);Px=poly2str(Pf,'x') 12、P=[3 0 9 60 0 -90];K1=polyval(P,45),K2=polyval(P,-123),K3=polyval(P,579) 13、P1=[13 55 0 -17 9];P2=[63 0 26 -85 0 105];PP=conv(P1,P2);P1P2=poly2str(PP,'x'),[Q,r]=deconv(P2,P1) 从起点sb到终点db通用的Dijkstra标号算法程序 function [mydistance,mypath]=mydijkstra(a,sb,db); % 输入：a—邻接矩阵，a（i，j)是指i到j之间的距离，可以是有向的% sb—起点的标号, db—终点的标号 % 输出：mydistance—最短路的距离, mypath—最短路的路径 n=size(a,1); visited(1:n) = 0; distance(1:n) = inf; distance(sb) = 0; %起点到各顶点距离的初始化visited(sb)=1; u=sb; %u为最新的P标号顶点 parent(1:n) = 0; %前驱顶点的初始化 for i = 1: n-1 id=find(visited==0); %查找未标号的顶点 for v = id if a(u, v) + distance(u) < distance(v) distance(v) = distance(u) + a(u, v); %修改标号值 parent(v) = u; end end temp=distance; temp(visited==1)=inf; %已标号点的距离换成无穷 [t, u] = min(temp); %找标号值最小的顶点 visited(u) = 1; %标记已经标号的顶点 end mypath = []; if parent(db) ~= 0 %如果存在路! t = db; mypath = [db]; while t ~= sb %从终点db开始回溯 p = parent(t); mypath = [p mypath]; t = p; end end mydistance = distance(db); 例题：运筹学教材P205 第七题 D=[0 3 6 1 inf inf inf inf; inf 0 2 inf 4 6 inf inf; inf inf 0 inf inf 5 inf inf; inf inf 4 0 inf 3 6 inf; inf inf inf inf 0 inf inf 7; inf inf inf inf inf 0 7 11; inf inf inf inf inf inf 0 8; inf inf inf inf inf inf inf 0]最短路dijkstra算法Matlab程序
dijkstra算法的matlab实现
dijkstra算法原理及MATLAB代码
Dijkstra算法
王能超 计算方法——算法设计及MATLAB实现课后代码
图论算法及matlab程序的三个案例
0计算方法及MATLAB实现简明讲义课件PPS8-1欧拉龙格法
用MATLAB实现结构可靠度计算.
计算方法及其MATLAB实现第二章作业
利用MATLAB实现Dijkstra算法
matlab用于计算方法的源程序
图论算法及matlab程序的三个案例
层次分析法计算权重在matlab中的实现
最短路dijkstra算法Matlab程序调用举例
计算方法及其MATLAB实现第一章作业
D_i_j_k_s_t_r_a最短路算法MATLAB程序_
相关主题
文本预览