一维抛物线偏微分方程数值解法(附图及matlab程序)

一维抛物线偏微分方程数值解法（4）

上一篇参看一维抛物线偏微分方程数值解法（3）（附图及matlab程序）

解一维抛物线型方程(理论书籍可以参看孙志忠：偏微分方程数值解法）

Ut-Uxx=0, 00)

U(x,0)=e^x, 0<=x<=1,

U(0,t)=e^t,U(1,t)=e^(1+t), 0

精确解为：U(x,t)=e^(x+t);

用紧差分格式：

此种方法精度为o(h1^2+h2^4),无条件差分稳定；

一：用追赶法解线性方程组（还可以用迭代法解）

Matlab程序为：

function [u p e x t]=JCHGS(h1,h2,m,n)

%紧差分格式解一维抛物线型偏微分方程

%此程序用的是追赶法解线性方程组

%h1为空间步长，h2为时间步长

%m,n分别为空间，时间网格数

%p为精确解，u为数值解,e为误差

x=(0:m)*h1+0; x0=(0:m)*h1;%定义x0,t0是为了f(x,t)~=0的情况%

t=(0:n)*h2+0; t0=(0:n)*h2+1/2*h2;

syms f;

for(i=1:n+1)

for(j=1:m+1)

f(i,j)=0; %f(i,j)=f(x0(j),t0(i))==0%

end

end

for(i=1:n+1)

u(i,1)=exp(t(i));

u(i,m+1)=exp(1+t(i));

end

for(i=1:m+1)

u(1,i)=exp(x(i));

end

r=h2/(h1*h1);

for(i=1:n) %外循环，先固定每一时间层，每一时间层上解一线性方程组%

a(1)=0;b(1)=5/6+r;c(1)=1/12-r/2;d(1)=(r/2-1/12)*u(i+1,1)+... (1/12+r/2)*u(i,1)+(5/6-r)*u(i,2)+(1/12+r/2)*u(i,3)+...

h2/12*(f(i,1)+10*f(i,2)+f(i,3));

for(k=2:m-2)

a(k)=1/12-r/2;b(k)=5/6+r;c(k)=1/12-r/2;d(k)=h2/12*(f(i,k)+...

10*f(i,k+1)+f(i,k+2))+(1/12+r/2)*(u(i,k)+u(i,k+2))+(5/6-r)...

*u(i,k+1);

%输入部分系数矩阵，为0的矩阵元素不输入%一定要注意输入元素的正确性end

a(m-1)=1/12-r/2;b(m-1)=5/6+r;d(m-1)=(1/12+r/2)*(u(i,m-1)+u(i,m+1) )+...

(5/6-r)*u(i,m)+(r/2-1/12)*u(i+1,m+1)+ ...

h2/12*(f(i,m-1)+10*f(i,m)+f(i,m+1));

for(k=1:m-2) %开始解线性方程组消元过程

a(k+1)=-a(k+1)/b(k);

b(k+1)=b(k+1)+a(k+1)*c(k);

d(k+1)=d(k+1)+a(k+1)*d(k);

end

u(i+1,m)=d(m-1)/b(m-1); %回代过程%

for(k=m-2:-1:1)

u(i+1,k+1)=(d(k)-c(k)*u(i+1,k+2))/b(k);

end

end

for(i=1:n+1)

for(j=1:m+1)

p(i,j)=exp(x(j)+t(i)); %p为精确解

e(i,j)=abs(u(i,j)-p(i,j));%e为误差

end

end

[u p e x t]=JCHGS(0.1,0.005,10,200); surf(x,t,e)

>> title('误差');运行约43秒；

[u p e x t]=JCHGS(0.1,0.01,10,100);surf(x,t,e) 20多秒；

[u p e x t]=JCHGS(0.2,0.04,5,25);surf(x,t,e) 3秒；

此方法精度很高；

二：g-s迭代法求解线性方程组

Matlab程序

function [u e p x t k]=JCFGS1(h1,h2,m,n,kmax,ep) % 解抛物线型一维方程格式（Ut-aUxx=f(x,t),a>0)

%用g-s(高斯-赛德尔)迭代法解

%kmax为最大迭代次数

%m,n为x,t方向的网格数，例如（2-0）/0.01=200;

%e为误差，p为精确解

syms temp;

u=zeros(n+1,m+1);

x=0+(0:m)*h1;

t=0+(0:n)*h2;

for(i=1:n+1)

u(i,1)=exp(t(i));

u(i,m+1)=exp(1+t(i));

end

for(i=1:m+1)

u(1,i)=exp(x(i));

end

for(i=1:n+1)

for(j=1:m+1)

f(i,j)=0;

end

end

a=zeros(n,m-1);

r=h2/(h1*h1); %此处r=a*h2/(h1*h1）；a=1

for(k=1:kmax)

for(i=1:n)

for(j=2:m)

temp=((1/12+r/2)*(u(i,j-1)+u(i,j+1))+(5/6-r)*u(i,j)+...

h2/12*(f(i,j-1)+10*f(i,j)+f(i,j+1))+(r/2-1/12)*(u(i+1,...

j-1)+u(i+1,j+1)))/(5/6+r);

a(i+1,j)=(temp-u(i+1,j))*(temp-u(i+1,j));

u(i+1,j)=temp;%此处注意是u(i+1,j),,而不是u(i+1,j+1)% end

end

a(i+1,j)=sqrt(a(i+1,j));

if(k>kmax)

break;

end

if(max(max(a))

break;

end

end

for(i=1:n+1)

for(j=1:m+1)

p(i,j)=exp(x(j)+t(i));

e(i,j)=abs(u(i,j)-p(i,j));

end

end

[u e p x t k]=JCFGS1(0.1,0.005,10,200,100000,1e-12);k=67;运行速度1秒左右；surf(x,t,e)

[u e p x t k]=JCFGS1(0.01,0.001,100,1000,1000000,1e-12);k=5780;surf(x,t,e)

斐波那契法 一维搜索方法

短后的区间不大于区间[0,10]的5% 。 解：由题意=δ5%，由斐波那契数列δ1 ≥n F ，则n=7， 00=a ，100=b 1t =0b )(0076a b F F --=2180 , 21 130)(00760'1=-+=a b F F a t , 将1t 和'1t 代入函数，比较大小有)()('11t f t f < 则有001==a a ，21801'2==t t ，21130'11==t b ，21 50)(116512=--=a b F F b t ， 将2t 和'2t 代入函数，比较大小有)()('22t f t f < , 则有012==a a ，21502'3==t t ，2180'22==t b ，21 30)(225423=--=a b F F b t ， 将3t 和'3t 代入函数，比较大小有)()('33t f t f >， 则有213033==t a ，2150'34==t t ，218023==b b ，21 60)(33433'4=-+=a b F F a t ， 将4t 和'4t 代入函数，比较大小有)()('44t f t f >， 则有215044==t a ,2160'45==t t ,218034==b b ,21 70)(44324'5=-+=a b F F a t ， 将5t 和'5t 代入函数，比较大小有)()('55t f t f >， 则有216055= =t a ，2170'56==t t ，218045==b b ， 则令105 351)21602180()01.05.0(2160))((55215'6=-?++=-++=a b F F a t ε， 将6t 和'6t 代入函数，比较大小有)()('66t f t f <， 则216056==a a ，105351'66==t b ，区间为：?? ????105351,2160 所以选择6t 为极小点，=)(6t f 89.6)2170( -=f 。

算法设计与分析复习题目及答案 (3)

分治法 1、二分搜索算法是利用（分治策略）实现的算法。 9. 实现循环赛日程表利用的算法是（分治策略） 27、Strassen矩阵乘法是利用（分治策略）实现的算法。 34．实现合并排序利用的算法是（分治策略）。 实现大整数的乘法是利用的算法（分治策略）。 17．实现棋盘覆盖算法利用的算法是（分治法）。 29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。 不可以使用分治法求解的是（0/1背包问题）。 动态规划 下列不是动态规划算法基本步骤的是（构造最优解） 下列是动态规划算法基本要素的是（子问题重叠性质）。 下列算法中通常以自底向上的方式求解最优解的是（动态规划法） 备忘录方法是那种算法的变形。（动态规划法） 最长公共子序列算法利用的算法是（动态规划法）。 矩阵连乘问题的算法可由（动态规划算法B）设计实现。 实现最大子段和利用的算法是（动态规划法）。 贪心算法 能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题， 不能解决的问题：N皇后问题，0/1背包问题 是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。 回溯法 回溯法解旅行售货员问题时的解空间树是（排列树）。 剪枝函数是回溯法中为避免无效搜索采取的策略 回溯法的效率不依赖于下列哪些因素（确定解空间的时间）

分支限界法 最大效益优先是（分支界限法）的一搜索方式。 分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。 分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆） 优先队列式分支限界法选取扩展结点的原则是（结点的优先级） 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法). 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法)之外都是最常见的方式. （1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 （最优子结构性质）是贪心算法与动态规划算法的共同点。 贪心算法与动态规划算法的主要区别是（贪心选择性质）。 回溯算法和分支限界法的问题的解空间树不会是( 无序树). 14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 21、下面关于NP问题说法正确的是（B ） A NP问题都是不可能解决的问题 B P类问题包含在NP类问题中 C NP完全问题是P类问题的子集 D NP类问题包含在P类问题中 40、背包问题的贪心算法所需的计算时间为（ B ）

一维数组的常用算法源代码

1.数组元素逆置 #include #include int main() { int a[10],t,i,j; //随机生成数组元素,并显示 printf("逆置前:"); for(i=0;i<10;i++) { a[i]= rand()%100; printf("%4d",a[i]); } printf("\n"); //数组元素逆置，即对称位置交换for(i=0,j=9;i

2.静态查找 #include #include int main() { int a[10],t,i,j; //随机生成数组元素,并显示 printf("数组元素:"); for(i=0;i<10;i++) { a[i]= rand()%100; printf("%4d",a[i]); } printf("\n"); //输入查找的数 printf("请输入要查找的数："); scanf("%d", &t); //静态查找:从前往后依次遍历 for(i=0;i<10;i++) if(a[i]==t) break;//找到并退出//输出查找结果 if(i<10)

printf("%d在数组a[%d]中。\n",t,i); else printf("%d不在a数组中。\n",t); } 3.二分查找：前提数组有序 #include #include void sort(int a[], int n) { int i,j, t; for(i=0;ia[j+1]) {t=a[j]; a[j]=a[j+1]; a[j+1]=t;} } int main() { int a[10],t,i,left,right,mid; //随机生成数组元素 printf("数组元素:"); for(i=0;i<10;i++)

常用一维搜索算法

无约束优化：不对定义域或值域做任何限制的情况下，求解目标函数的最小值。 这是因为实际应用中，许多情形被抽象为函数形式后均为凸函数，对于凸函数来说局部最小值点即为全局最小值点，因此只要能求得这类函数的一个最小值点，该点一定为全局最小值。 （直接法：又称数值方法，它只需计算目标函数驻点的函数数值，而不是求其倒数，如坐标轮换法，单纯型法等。 间接法：又称解析法，是应用数学极值理论的解析方法。首先计算出目标函数的一阶或一阶、二阶导数，然后根据梯度及海赛矩阵提供的信息，构造何种算法，从而间接地求出目标函数的最优解，如牛顿法、最速下降法共轭梯度法及变尺度法。） 在优化算法中保证整体收敛的重要方法就是线搜索法与信赖域法,这两种算法既相似又有所不同。根据不同的线搜索准则就延伸出不同的线搜索算法,譬如比较常见和经典的最速下降法,牛顿法,拟牛顿法以及共辄梯度法等。 一维搜索又称线性搜索(Line Search),就是指单变量函数的最优化,它是多变量函数最优化的基础,是求解无约束非线性规划问题的基本方法之一。 一维搜索技术既可独立的用于求解单变量最优化问题,同时又是求解多变量最优化问题常用的手段,虽然求解单变量最优化问题相对比较简单,但其中也贯穿了求解最优化问题的基本思想。由于一维搜索的使用频率较高,因此努力提高求解单变量问题算法的计算效率具有重要的实际意义。 在多变量函数的最优化中,迭代格式X k+1=X k+a k d k其关键就是构造搜索方向d k和步长因子a k 设Φ(a)=f(x k+ad k) 这样从凡出发,沿搜索方向d k,确定步长因子a k,使Φ(a)<Φ(0)的问题就是关于步长因子a的一维搜索问题。其主要结构可作如下概括:首先确定包含问题最优解的搜索区间，然后采用某种分割技术或插值方法缩小这个区间，进行搜索求解。 一维搜索通常分为精确的和不精确的两类。如果求得a k使目标函数沿方向d k达到 极小,即使得f (x k+a k d k)=min f (x k+ ad k) ( a>0) 则称这样的一维搜索为最优一维搜索,或精确一维搜索,a k叫最优步长因子; 如果选取a k使目标函数f得到可接受的下降量,即使得下降量f (x k)一f (x k+a k d k)>0是用 户可接受的,则称这样的一维搜索为近似一维搜索,或不精确一维搜索,或可接受一维 搜索。 由于在实际计算中,一般做不到精确的一维搜索,实际上也没有必要做到这一点,因为精确的

基于matlab的一维搜索

最优化理论与算法 基于matlab 的一维搜索——0.618试探法 2 m in ()21def f x x x =-- ， 初始区间11[,][1,1]a b =-,精度0.16L ≤ clc clear %设定初始值 L=0.16; k=1; b=1; a=-1; r=a+0.382*(b-a); u=a+0.618*(b-a); fr=fun(r); fu=fun(u); c=[]; while b-a>L if fr>fu a=r; b=b; r=u; u=a+0.618*(b-a); fr=fun(r); fu=fun(u); else a=a; b=u; u=r; r=a+0.382*(b-a); fr=fun(r); fu=fun(u); end k=k+1; c=[c,[a,b,r,u,fr,fu]]; end k jieguo=reshape(c,6,k)’ s=[a,b] l=b-a jieguo = -1.0000 1.0000 -0.2360 0.2360 -0.6526 -1.1246 -0.2360 1.0000 0.2360 0.5278 -1.1246 -0.9706 -0.2360 0.5278 0.0558 0.2360 -1.0496 -1.1246 0.0558 0.5278 0.2360 0.3475 -1.1246 -1.1060 0.0558 0.3475 0.1672 0.2360 -1.1113 -1.1246 0.1672 0.3475 0.2360 0.2787 -1.1246 -1.1234 0.1672 0.2787 0.2098 0.2360 -1.1218 -1.1246

第5章 一维搜索

第5章 一维搜索 §5.1 最优化算法的简单介绍 1．算法概念 在解非线性规划时，所用的计算方法，最常见的是迭代下降算法． 迭代：从一点) (k x 出发，按照某种规则A 求出后继点) 1(+k x ．用1+k 代替k ，重复以上 过程，产生点列}{) (k x 。 规则A 是在某个空间X 中点到点的映射，即对每一个X x k ∈) (，有点 X x A x k k ∈=+)() () 1(． 更一般地，把A 定义为点到集的映射，即对每个点X x k ∈) (，经A 作用，产生一个点 集X x A k ?)() (.任意选取一个点)() () 1(k k x A x ∈+，作为) (k x 的后继点． 定义1: 算法A 是定义在空间X 上的点到集映射，即对每一个点X x ∈，给定－个子集 X x A ?)(. 例1 考虑线性规划： 1 s.t. min 2 ≥x x 最优解1=x ．设计一个算法A 求出这个最优解． ???????

无约束最优化问题可以定义解集合为 }0)(|{=?=Ωx f x 约束最优化问题可以定义解集合为 }T -K 为|{点x x =Ω 2. 算法收敛问题 设Ω为解集合，X X A →:是一个算法，集合X Y ?.若以任一初点Y x ∈) 1(开始， 算法产生的序列其任一收敛子序列的极限属于Ω，则称算法映射A 在Y 上收敛． 收敛速率: 定义2: 设序列}{) (k γ 收敛于* γ，定义满足 ∞<=--≤+∞ →βγ γ γ γp k k k * ) (*) 1(lim 的非负数p 的上确界为序列}{) (k γ 的收敛级． 若序列的收敛级为p ，就称序列是p 级收敛的． 若1=p 且1<β，则称序列是以收敛比β 线性收敛的． 若1>p 或者1=p 且0=β，则称序列是超线性收敛的． 例2 序列{}10 ,<

三点一维搜索法报告

三点一维搜索法报告 姓名：张攀班级：2009211102 学号：09210048 算法的基本思想： 三点一维算法是从0.618法衍生而来的，0.618算法使用从两点a,b间选择两个点c,d将原来区域分为三个，抛弃不符合所求数值趋势的两个区域，不断逼近所求值，当|b-a|

实例分析： 选择函数：f[x] := Sin[x^4] + Cos[x] 该函数在[0,1]范围内有极小值，令a=0,b=1，p=0.1,e选取1*10^(-9)，运算后结果在x=0.4904089750976563时有最小值0.939949。运算次数为22次， P值选取效率的影响： 在该函数中，[0,1]内函数波动较为平缓，从中间缓慢向两边扩展显然速度较快，因为所求点接近终点，当p增大的时能很快覆盖到所求点效率将变高，如果区域远超过所求点则效率将变低。 P取值以及逼近次数i的关系: P=0.1,i=22 P=0.2,i=26 P=0.25,i=19 P=0.3,i=19 P=0.35,i=21 P=0.4,i=23 P=0.5,i=26 P=0.6,i=30 P=0.7,i=36 P=0.8,i=57 可见最好的取值应为0.25到0.3之间。 总结： 三点一维算法实际通过多次比较，减少了0.618法对点的移动，和对区域的选择，比0.618法稳定。在比较区域大时三点一维算法比起0.618法更加优秀。

黄金分割法 二次插值 牛顿 matlab 程序一维搜索方法比较

一维搜索方法应用比较 一、黄金分割法 （1）黄金分割法的起源 黄金分割在文艺复兴前后，经过阿拉伯人传入欧洲，受到了欧洲人的欢迎，他们称之为"金法"，17世纪欧洲的一位数学家，甚至称它为"各种算法中最可宝贵的算法"。这种算法在印度称之为"三率法"或"三数法则"，也就是我们现在常说的比例方法。 其实有关"黄金分割"，我国也有记载。虽然没有古希腊的早，但它是我国古代数学家独立创造的，后来传入了印度。经考证。欧洲的比例算法是源于我国而经过印度由阿拉伯传入欧洲的，而不是直接从古希腊传入的。 因为它在造型艺术中具有美学价值，在工艺美术和日用品的长宽设计中，采用这一比值能够引起人们的美感，在实际生活中的应用也非常广泛，建筑物中某些线段的比就科学采用了黄金分割，舞台上的报幕员并不是站在舞台的正中央，而是偏在台上一侧，以站在舞台长度的黄金分割点的位置最美观，声音传播的最好。就连植物界也有采用黄金分割的地方，如果从一棵嫩枝的顶端向下看，就会看到叶子是按照黄金分割的规律排列着的。在很多科学实验中，选取方案常用一种0.618法，即优选法，它可以使我们合理地安排较少的试验次数找到合理的西方和合适的工艺条件。正因为它在建筑、文艺、工农业生产和科学实验中有着广泛而重要的应用，所以人们才珍贵地称它为"黄金分割"。我国数学家华罗庚曾致力于推广优选法中的"0.618法"，把黄金分割应用于生活实际及科学应用中。 黄金分割〔Golden Section〕是一种数学上的比例关系。黄金分割具有严格的比例性、艺术性、和谐性，蕴藏着丰富的美学价值。应用时一般取0.618 ，就像圆周率在应用时取3.14一样。 由于公元前6世纪古希腊的毕达哥拉斯学派研究过正五边形和正十边形的作图，因此现代数学家们推断当时毕达哥拉斯学派已经触及甚至掌握了黄金分割。 公元前4世纪，古希腊数学家欧多克索斯第一个系统研究了这一问题，并建立起比例理论。 公元前300年前后欧几里得撰写《几何原本》时吸收了欧多克索斯的研究成果，进一步系统论述了黄金分割，成为最早的有关黄金分割的论著。 中世纪后，黄金分割被披上神秘的外衣，意大利数家帕乔利称中末比为神圣比例，并专门为此著书立说。德国天文学家开普勒称黄金分割为神圣分割。 到19世纪黄金分割这一名称才逐渐通行。黄金分割数有许多有趣的性质，人类对它的实际应用也很广泛。最著名的例子是优选学中的黄金分割法或0.618法，是由美国数学家基弗于1953年首先提出的，70年代在中国推广。

一维搜索算法(二)

项目二 一维搜索算法（二） [实验目的] 编写抛物线插值法的程序。 [实验学时] 2学时 [实验准备] 1、掌握二分法的思想及迭代步骤 2、掌握抛物线插值法的思想及迭代步骤。 [实验内容及步骤] 编程解决以下问题： 1、用二分法求解 )2()(min +=t t t ?， 已知初始单谷区间]5,3[],[-=b a ，要求按精度3.0=ε，001.0=ε分别计算． 2、用抛物线插值法求解 3728)(m in 23+--=x x x x f ， 已知初始单谷区间001.0]20[][==ε，，， b a ．取初始插值点为x=1

[实验教案] 例1 用二分法求f(x)=8x^3-2*x^2-7*x+3 的局部最优解．允许误差ε=0.0001 ，初始点设区间为[0，1]． #include using namespace std; float f(float x) { return (8*x*x*x-2*x*x-7*x+3); } float f1(float x) { return (24*x*x-4*x-7); } void main() { float a=0,b=1,c,delta=0.0001; do { c=(a+b)/2; if(f1(c)>=0) { b=c; } else { a=c; } }while((b-a)/2>delta); cout<<"该问题的最优解为"<<(a+b)/2<<",最优值为"<

[例题2] 用抛物线插值法求解 30min ()32t t t t ?≥=-+， 已知初始单谷区间[0,3]．0.05ε=，取初始插值点为t=1 #include #include using namespace std; double Alpha(double x1,double x2,double x3); double faiPhi(double t); double faiPhi(double t) //求3()32x t t ?=-+ { return (t*t*t-3*t+2); } double Alpha(double x1,double x2,double x3) //求α { double x,y; x=(x2*x2-x3*x3)*faiPhi(x1)+(x3*x3-x1*x1)*faiPhi(x2)+(x1*x1-x2*x2)*faiPhi(x3); y=(x2-x3)*faiPhi(x1)+(x3-x1)*faiPhi(x2)+(x1-x2)*faiPhi(x3); return (0.5*x/y); } void main() { double a=0,b=3,t=2,Epsilon=0.05,t1; do { t1=Alpha(a,t,b); if(fabs(t-t1)t) { if(faiPhi(t1)<=faiPhi(t)) { a=t;t=t1; } else { b=t1; } } else { if(faiPhi(t1)<=faiPhi(t)) { b=t;t=t1; } else { a=t1; } } } }while(1); }

实验1 一维搜索算法的程序设计

实验一 一维搜索算法的程序设计 一、实验目的 1、熟悉一维无约束优化问题的二分法、0.618算法和牛顿法。 2、培养matlab 编程与上机调试能力。 二、实验课时：2个课时 三、实验准备 1、预习一维无约束优化问题的二分法、0.618算法和牛顿法的计算步骤。 2、熟悉matlab 软件的基本操作。 四、实验内容 课堂实验演示 1、根据二分法算法编写程序，求函数 2 ()22f x x x =++ 在区间[2,1]-上的极小值。 二分法如下： （1）给定区间[,]a b (要求满足0)(',0)('>δ； （2）若δ≤-a b ，则停，输出*()/2x a b =+； （3）计算()/2c a b =+； （4）若0)('c f ，令b c =；否则若0)('=c f ，则停输出*()/2x a b =+； function [val,x,iter] = bisection_method(a,b,delta) iter = 0; while abs(b-a)>delta iter = iter+1; [y,dy] = fun((a+b)/2); if abs(dy)<= delta x = (a+b)/2; val = y; return; elseif dy<0 a = (a+b)/2; else b = (a+b)/2;

end end x = (a+b)/2; [val,dval] = fun(x); %%%%%%%%%%%%%%%%%%%%%%% obj function %%%%%%%%%%%%%%%%%%%%%%%%% function [y,dy] = fun(x) y = x^2+2*x+2; dy = 2*x+2; >> delta = 1.0e-6; [val,x,iter] = bisection_method(-2,1,delta) val = 1 x = -1 iter = 21 2、根据0.618算法编写程序，求函数 ()()()630sin tan 1x f x x x e =- 在区间[0,1]上的极大值。 令()()()()630sin tan 1x g x f x x x e =-=--，则原问题转化为求[] ()0,1m in x g x ∈ 0.618算法如下： （1）给定区间[,]a b ，及精度0eps >； （2）计算试探点0.382(),0.618()r a b a u a b a =+-=+-. 令1=k ； （3）若eps a b <-，则停止计算，输出)(,2/)(* **x f f a b x =+=；否则， 若()()f r f u >，转（4）；若)()(u f r f <，转（5）; （4）令a r =，r u =，计算0.618()u a b a =+-，转（6）; （5）令b u =，u r =，计算0.382()r a b a =+-，转（6）; （6）令1+=k k ，回 (3). 运行结果，如下： >> a=0,b=1,eps=10^(-5); [optx,opty,iter]=gold_section_method(a,b,eps) iter = 26 optx = 0.9707

一维搜索算法(一)

项目一 一维搜索算法（一） [实验目的] 编写进退法、对分法、Newton 法的程序。 [实验学时] 2学时 [实验环境] Matlab 或VC++6.0 [实验目的] 1．掌握一维收搜索中搜索区间的进退法的思想及迭代步骤； 2．掌握0.618法的思想及迭代步骤； 3．掌握Fibonaci 法的思想及迭代步骤。 [实验内容及步骤] 编程解决以下问题： 1．用进退法确定一维最优化问题 12)(min 30+-=≥t t t t ? 的搜索区间，要求选取2,1,000===αh t ． 2．用0.618法求解 12)(min 3+-=t t t ?， 已知初始单谷区间]1,0[],[=b a ，要求精度01.0=ε． 3．用Fibonaci 法求解 12)(min 3+-=t t t ?， 已知初始单谷区间]1,0[],[=b a ，要求精度01.0=ε．

[实验教案] 例1 设f(x)=x^2-2*x+4 ，试用进退法确定初始搜索区间。#include using namespace std; float f(float x) { return (x*x-2*x+4); } void main() { int k=0; float a0,h,t,aerfa,a1,a,b; cout<<"初始数据为: "; cout<<"初始点a0="; cin>>a0; cout<<"\t\t始步长h="; cin>>h; cout<<"\t\t加倍系数t="; cin>>t; do { a1=a0+h; if(f(a1)

机械优化设计一维搜索实验报告

《机械优化设计》 实验报告 班级: 机械设计（2）班 姓名：邓传淮 学号：0901102008

1 实验名称：一维搜索黄金分割法求最佳步长 2 实验目的：通过上机编程，理解一维搜索黄金分割法的原理，了解计算机在优化设计中的应用。 3 黄金分割法的基本原理 黄金分割法是用于一元函数f(x)在给定初始区间[a,b]内搜索极小点α*的一种方法。它是优化计算中的经典算法，以算法简单、收敛速度均匀、效果较好而著称，是许多优化算法的基础，但它只适用于一维区间上的凸函数[6]，即只在单峰区间内才能进行一维寻优，其收敛效率较低。其基本原理是：依照“去劣存优”原则、对称原则、以及等比收缩原则来逐步缩小搜索区间[7]。具体步骤是：在区间[a,b]内取点：a1 ，a2 把[a,b]分为三段。如果f(a1)>f(a2)，令a=a1,a1=a2,a2=a+r*(b-a)；如果f(a1)

（2）黄金分割法计算框图

5 程序源代码 （1）进退发确定单峰区间的程序源代码 #include #include #define f(x) pow(x,4)-3*pow(x,3)-5*pow(x,2)-14*x+46 main() { int k; double x,h,x1,x2,x3; double f1,f2,f3,f; double a,b; x1=0; h=1; x2=x1+h; f1=f(x1); f2=f(x2); if (f1>f2) { h=2*h; x3=x2+h; f3=f(x3); } else { h=-h; x1=x2; f1=f2; x3=x2+h; f3=f(x3); } printf("x1=%lf,x2=%lf\0",x1,x2); do { x1=x2; x2=x3; f1=f2; f2=f3; x3=x2+h; f3=f(x3); }while(f30) {

第三章 一维搜索

第三章 常用一维搜索方法 第节维搜索概述 第一节 一维搜索概述一、下降迭代算法的基本思想、下降迭代算法的基本思想 不失一般性，考虑如下的优化问题 min ()x S f x ∈ （3.1） 其中:n f S R R ?→. 下降迭代算法的的基本思想：给定一个初始点1n x R ∈，按 }k 使得当}k 是有限点列时照某种迭代规则产生一个点列{x ，使得当{x 其最后一个点是最优化问题的最优解；当{}k x 是无穷点列时，它有极限点，且其极限点是优化问题的最优解.

设已迭代到点k x 处，则下一次迭代会出现以下两种情况之一： （1） 从k x 出发沿任何方向移动，目标函数不再下降； 出发至少存在个方向使标数有所 （2）从k x 出发至少存在一个方向使目标函数()f x 有所下降.这时，从中选取一个下降方向k d ，即k d 满足 ()0k T k f x d ?<，然后在直线 k k x x d λ=+上适当的确定一个新点 1k k k k x x d λ+=+，使得1()()()k k k k k f x f x d f x λ+=+<，此时就说完成了第1k +次迭代. 基本迭代格式 1k k k k x x d λ+=+ 本代格式 k d ------搜索方向 k λ-----步长因子或搜索步长

最优化问题的求解步骤 最优化问题的求解步骤：（1）选取初始点1x ，令1k =； （2）构造搜索方向k d .依照一定的规则，构造()f x 在点 k x 处的下降方向或可行下降方向作为搜索方向k d ； （3）确定搜索步长k λ.以k x 为起点沿搜索方向k d 选取的 λ适当步长k ，使得目标函数值有某种意义的下降，通常使 ()()k k k k f x d f x λ+<. 1k +令1k k k + （4）求出新的迭代点x .令k x x d λ=+（5）检验终止条件.判定1 k x +是否满足终止条件，若满足 停止迭代输出近似最优解否则令转 停止迭代，输出近似最优解1k x +；否则，令:1k k =+，转（2）.

一维搜索 黄金分割法 二次插值法

一维搜索黄金分割法二次插值法 #include #include #include double f(double); double golden_split(double(*)(),double,double);/*黄金分割法*/ double rcczf(double(*)(),double[],double[],double); /*二次插值法*/ void jtf(double(*)(),double,double *,double *,double *);/*进退法*/ void jtf(double(*objf)(),double a0,double *h0,double *a,double *y) { double h; a[0]=a0; h=*h0; a[1]=a[0]+h,y[1]=objf(a[1]); if(y[1]>y[0]) { h=-h; a[2]=a[0],y[2]=y[0]; a[0]=a[1],y[0]=y[1]; a[1]=a[2],y[1]=y[2]; } a[2]=a[1]+h; y[2]=objf(a[2]); while(y[2]

一维搜索方法

一维搜索方法：（方法比较） “成功—失败”法、二分法、0.618法（黄金分割法）、牛顿法、二次插值法、D.S.C法、Powell法、D.S.C—Powell组合法。 1、“成功—失败”法：主要思想：从一点出发，按一定的步长搜索新点，若成功，加大步长继续搜索，否则，缩短步长小步后退。此方法可以求最优解所在区间，称为“搜索区间”。 2、二分法：主要思想：区间[a,b]的中间值x0，判断f（x）的导数在三个点处的值，舍去一部分区间再求f(x)的极小值。 3、0.618法：等比例收缩原则，每次留下来的区间长度是上次留下来的区间长度的w倍。以及对称原则、去坏留好原则。W=0.618 4、牛顿法：基本思想：在极小值点附近用目标函数的二阶泰勒多项式近似代替目标函数，从而求得目标函数的极小值点的近似值。 5、二次插值法：牛顿法是在x k附近的目标函数用泰勒多项式近似代替，而此法是将f(x)用二次插值多项式p(x)近似代替。把p(x)的极小值点作为f(x)极小值点的代替，从来求得函数的极小值。 6、D.S.C法：主要思想：利用成功—失败法寻找靠近极小值点的三点，进行二次插值。 优点是：收敛速度快，且不要求函数可微。 7、Powell法：基本思想：在搜索方向开始得到三点x0,x1,x2后，作二次插值，求得最小值x， 在四点中去坏留好，在余下的三点中再作二次插值…… 8、D.S.C—Powell组合法： 几种方法比较： D.S.C—Powell组合法是非常好的一种方法，它比任何一个单个方法都好 D.S.C—Powell组合法与0.618法比较：D.S.C—Powell法中函数值的计算要比黄金分割法少得多，一般来讲它优于黄金分割法。 但：D.S.C—Powell法不一定能收敛到最优解。 最速下降法与修正牛顿法： 对于正定二次函数，牛顿法一步可以求得最优解，对于非二次函数，牛顿法并不能保证有限次求得其最优解，但由于目标函数在极小值的附近近似于二次函数，故当初始点靠近极小值时，牛顿法收敛的速度比较快。 牛顿法的缺点是：计算量大。 故：开始几步用最速下降法，后面用牛顿法。 最速下降法、牛顿法、修正牛顿法是无约束优化方法中的基本方法。

第一章 一维搜索方法

第一章一维搜索方法：黄金分割法 1.1 实验原理 一维搜索是解函数极小值的方法之一，其解法思想为沿某一已知方向求目标函数的极小值点。一维搜索的解法很多，这里主要采用黄金分割法（0.618法）。该方法用不变的区间缩短率0.618代替斐波那契法每次不同的缩短率，从而可以看成是斐波那契法的近似，实现起来比较容易，也易于人们所接受。 图1 黄金分割法是用于一元函数f(x)在给定初始区间[a,b]内搜索极小点α*的 一种方法。它是优化计算中的经典算法，以算法简单、收敛速度均匀、效果较好而著称，是许多优化算法的基础，但它只适用于一维区间上的凸函数，即只在单峰区间内才能进行一维寻优，其收敛效率较低。其基本原理是：依照“去劣存优”原则、对称原则、以及等比收缩原则来逐步缩小搜索区间[7]。具体步骤是：在区间[a,b]内取点：a1 ，a2 把[a,b]分为三段。如果f(a1)>f(a2)，令 a=a1,a1=a2,a2=a+r*(b-a)；如果f(a1)

1.3 程序考核题 36 10 ) ( min2+ - =t t t F 1.4 实验内容 编程： clear a=0; 给定a,b,c λ←0.618 y1≧y2 ? a←α1 α1←α2 y1←y2 b←α2 α2←α1 y2←y1 α2←a+λ(b-a) y2←f(α2) α1←b-λ(b-a) y1←f(α1) 开始 b-a≤ε α*←(a+b)/2 结束α1←b-λ(b-a) y1←f(α1) α2←a+λ(b-a) y2←f(α2)