黄金分割法、二次插值法C语言编程

黄⾦分割法及其代码线性搜索之黄⾦分割法及其应⽤摘要最优化理论和⽅法⽇益受到重视，已经渗透到⽣产、管理、商业、军事、决策等各个领域，⽽最优化模型与⽅法⼴泛应⽤于⼯业、农业、交通运输、商业、国防、建筑、通讯和政府机关等领域。

伴随着计算机技术的⾼速发展，最优化理论与⽅法的迅速进步为解决实际最优化问题的软件也在飞速发展。

其中，MATLAB 软件已经成为最优化领域应⽤最⼴的软件之⼀。

有了MATLAB这个强⼤的计算平台，既可以利⽤MATLAB优化⼯具箱（OptimizationToolbox）中的函数，⼜可以通过算法变成实现相应的最优化计算。

在最优化计算中⼀维最优化⽅法是优化设计中最简单、最基本的⽅法。

⼀维搜索，⼜称为线性搜索，⼀维问题是多维问题的基础，在数值⽅法迭代计算过程中，都要进⾏⼀维搜索，也可以把多维问题化为⼀些⼀维问题来处理。

⼀维问题的算法好坏，直接影响到最优化问题的求解速度。

⽽黄⾦分割法是⼀维搜索⽅法中重要的⽅法之⼀，它适⽤于任何单峰函数求最⼩值的问题，甚⾄于对函数可以不要求连续，是⼀种基于区间收缩的极⼩点搜索算法。

关键词：最优化、黄⾦分割法、MATLAB软件、⼀维搜索引⾔数学科学不仅是⾃然科学的基础，也是⼀切重要技术发展的基础。

最优化⽅法更是数学科学⾥⾯的⼀个巨⼤的篇幅，在这个信息化的时代，最优化⽅法⼴泛应⽤于⼯业、农业、国防、建筑、通信与政府机关、管理等各领域；它主要解决最优计划、最优分配、最优决策、最佳设计、最佳管理等最优化问题。

⽽最优解问题是这些所有问题的中⼼，是最优化⽅法的重中之重，在求最优解问题中，有多种⽅法解决，我们在这⾥着重讨论⽆约束⼀维极值问题，即⾮线性规划的⼀维搜索⽅法之黄⾦分割法。

黄⾦分割法也叫0.618法，属于区间收缩法，⾸先找出包含极⼩点的初始搜索区间，然后按黄⾦分割点通过对函数值的⽐较不断缩⼩搜索区间。

当然要保证极⼩点始终在搜索区间内，当区间长度⼩到精度范围之内时，可以粗略地认为区间端点的平均值即为极⼩值的近似值。

#include <stdio.h>#include <stdlib.h>#include <math.h>#define maxint 32767.0#define minint -32768.0#define accuracy 0.0000001//精确度，值越小计算结果越精确float a,b,c;//系数float dt;//b^2-4acfloat x1=0.0,x2=0.0;//方程的解void read();void setDt();int assertX();void binarySolution();void interation();void newtonInteration();double f(double x);double f1(double x);double absolute(double x);void accurate();int main(void){int end=1;while(end!=0)//继续运算{accurate();printf("按任意键继续（输入0退出）：\n");scanf("%d",&end);}}//读取a,b,cvoid read(){printf("请输入方程ax^2+bx+c=0的系数a,b,c：\n");printf("请输入二次项系数a：");while(0==scanf("%f",&a)||a==0){while('\n' != getchar()){}printf("输入无效！请重新输入二次项系数a：");}printf("请输入一次项系数b：");while(0==scanf("%f",&b)){while('\n' != getchar()){}printf("输入无效！请重新输入一次项系数b：");}printf("请输入常数项c：");while(0==scanf("%f",&c)){while('\n' != getchar()){}printf("输入无效！请重新输入常数项c：");}}//计算dtvoid setDt(){dt=b*b-4*a*c;}//判断是否有解int assertX(){if(dt>=0) return 1;return 0;}//循环计算控制void accurate(){read();setDt();int method=0;printf("请选择求解方法：\n\t1.二分法\n\t2.迭代法\n\t3.牛顿迭代法\n请选择：");while((0==scanf("%d",&method))||(method!=1&&method!=2&&method!=3)){while('\n' != getchar()){}printf("输入无效！请重新选择：");}if(!assertX()){printf("该方程无解！\n");}else{switch(method){case 1:binarySolution();break;case 2:interation();break;case 3:newtonInteration();break;}printf("方程%fx^2+%fx+%f=0的解为：x1=%.10f x2=%.10f\n",a,b,c,x1,x2); }}//二分法void binarySolution(){double min=minint,temp=(-1.0*b)/(2*a),max=maxint,middle=0.0;//求解X1while((max-temp)>=accuracy){middle=(max+temp)/2;if(a>0)//开口向上{if(f(middle)>0)max=middle;elsetemp=middle;}else//开口向下{if(f(middle)>0)temp=middle;elsemax=middle;}}x2=temp;//求解X2temp=(-1.0*b)/(2*a);while((temp-min)>=accuracy){middle=(min+temp)/2;if(a>0)//开口向上{if(f(middle)>0)min=middle;elsetemp=middle;}else//开口向下{if(f(middle)>0)temp=middle;elsemin=middle;}}x1=temp;}//迭代法void interation(){//求解X1，在曲线对称轴处选择初始点double index=(-1.0*b)/(2*a),temp;if(b!=0)//b不等于0时进行迭代{temp=index;index=-1.0*(a*temp*temp+c)/b;while((absolute(index-temp))>accuracy) {temp=index;index=-1.0*(a*temp*temp+c)/b;}x1=index;x2=(-1.0*b)/a-x1;}else//b=0时ax^2+c=0直接求解{x1=sqrt(-1.0*c/a);x2=-x1;}}//牛顿迭代法void newtonInteration(){//求解X1，在曲线对称轴右侧选取初始点double index=(-1.0*b)/(2*a)+10,temp; temp=index;index=temp-f(temp)/f1(temp);while((absolute(index-temp))>accuracy) {temp=index;index=temp-f(temp)/f1(temp);}x1=index;//求解X2，在曲线对称轴左侧选取初始点index=(-1.0*b)/(2*a)-10,temp;temp=index;index=temp-f(temp)/f1(temp);;while((absolute(index-temp))>accuracy) {temp=index;index=temp-f(temp)/f1(temp);}x2=index;}//函数f(x)double f(double x){return a*x*x+b*x+c;}//函数f(x)的一次导函数double f1(double x){return 2.0*a*x+b;}//求解绝对值double absolute(double x) {if(x<=0) return (-1.0*x); return x*1.0;}。

二次插值方法二次插值方法是一种常用的数值计算方法，用于在给定一组离散数据点的情况下，通过插值来估计在其他位置的函数值。

该方法的基本思想是通过构建一个二次多项式，通过已知数据点的特性来逼近未知位置的函数值。

本文将介绍二次插值方法的原理、步骤和应用。

一、原理二次插值方法基于拉格朗日插值公式，其基本假设是函数在已知点附近是近似二次形式的。

二次插值多项式的一般形式为：f(x) = ax^2 + bx + c，其中a、b、c为待求系数。

通过已知数据点的特性，可以构建一个二次多项式，然后用该多项式来近似未知位置的函数值。

二、步骤进行二次插值的步骤如下：1. 获取已知数据点：首先需要获取一组已知的数据点，这些数据点可以是实验测量得到的，也可以是理论计算得到的。

2. 构建二次多项式：根据已知数据点，利用拉格朗日插值公式构建一个二次多项式。

通过将已知数据点带入多项式中，可以得到方程组，从而求解系数a、b、c。

3. 插值计算：得到二次多项式后，就可以利用这个多项式来估计其他位置的函数值。

将待求位置的自变量带入多项式中，即可得到相应的函数值。

三、应用二次插值方法在实际应用中具有广泛的用途，下面简要介绍几个常见的应用领域：1. 数据处理：在数据处理领域，二次插值可以用于填充缺失值、平滑曲线、去除噪声等。

通过利用已知数据点的特性，可以对缺失的数据进行估计，从而得到完整的数据集。

2. 图像处理：在图像处理中，二次插值可以用于图像的放大和缩小。

通过在已知像素点之间插入新的像素点，可以实现图像的放大；反之，通过对已知像素点进行插值，可以实现图像的缩小。

3. 数值分析：在数值分析中，二次插值方法可以用于数值积分和数值微分。

通过构建二次多项式，可以对函数进行逼近，从而得到函数的积分值或导数值。

四、总结二次插值方法是一种常用的数值计算方法，通过构建二次多项式来估计未知位置的函数值。

它在数据处理、图像处理和数值分析等领域都有广泛的应用。

1.用进退法确定f(x)=x 2-7x+10的初始搜索区间.设x 0=0,h 0=1. 解：()()000()10,()0+1(1)40f x f f x h f f ==+===，因为000f x f x h >+（）（），搜索成功，步长加倍；计算0000023 031 32f x h h f x h f f ++=+=+⨯==-（）（）（）（）， 因为00003f x h f x h +>+（）（），搜索成功，步长加倍； 计算00000347 071 710f x h h f x h f f ++=+=+⨯==（）（）（）（）， 因为00003 7f x h f x h +<+（）（），搜索失败，停止迭代；得到初始搜索区间为[]][0000, 71[,7]a b x h x h =++=，。

function [a, b]=jtf(varargin) if numel(varargin)<1 h0=input(' h0= ' ); x0=input(' x0= ' ); fx=@(x)x^2-7*x+10; elseinput_num= cell2mat (varargin(1, 1:2)); h0=input_num(1) ; x0=input_num(2) ; fx=varargin{3}; endh=h0;x1=x0;f1=fx(x1);x2=x1+h;f2=fx(x2); if f2>f1h=-h;x3=x1;f3=f1;x1=x2;f1=f2;x2=x3;f2=f3; endh=2*h;x3=x2+h;f3=fx(x3); while f2>=f3x1=x2;f1=f2;x2=x3;f2=f3; h=2*h;x3=x2+h;f3=fx(x3); end if h<0a=x3;b=x1; elsea=x1;b=x3; endresult=[a,b]MATLAB 程序运行结果： h0= 1 x0= 0 result =1 72.用0.618法求函数f(x)=x 2-7x+10的最优解.已知初始搜索区间为[2,8],精度为0.4。

C语言编程技巧整数开方算法整数开方算法是计算一个整数的平方根的算法，即求解方程x^2=a的解x。

在计算机编程中，有多种方法可以实现整数开方算法，包括牛顿迭代法、二分法和位运算法等。

下面将介绍几种常用的整数开方算法及其优化技巧。

1.牛顿迭代法牛顿迭代法是一种不断逼近平方根的方法。

它基于以下的迭代公式：x=(x+a/x)/2具体实现时，我们可以选择一个适当的初始值x0，然后不断迭代，直到找到满足精度要求的解。

例如，我们可以选择初始值x0=a/2、然后迭代若干次，直到解的变化非常小，即可认为找到了平方根。

牛顿迭代法的优点是收敛速度快，但需要使用浮点数运算，适用于计算精度较高的场合。

2.二分法二分法是一种更加简单的算法，它通过不断二分待求解的区间来逼近平方根。

具体实现时，我们从区间[1,a]开始，然后不断二分，找到满足条件的解。

例如，我们可以选择初始区间的中点作为猜测的平方根，然后根据和a的关系来判断解在左半区间还是右半区间，继续二分直到找到解。

二分法的优点是实现简单，并且只需要使用整数运算，适用于计算精度要求不高的场合。

3.位运算法位运算法是一种基于位运算的快速整数开方算法。

它利用二进制表示中1的位置与平方根的关系，通过位运算来求解。

具体实现时，我们可以从最高位开始，逐位计算解的每一位。

假设我们要计算a的平方根，这里只考虑正整数的情况。

首先，我们可以确定解的最高位，它是使得b*b<=a的最大整数b。

然后，我们可以依次计算解的其它位，如果当前位是1，那么解的该位可以取0或1，如果当前位是0，那么解的该位只能取0。

位运算法的优点是计算速度快，但需要对二进制表示进行运算，并且在计算负数的平方根时较复杂。

在实际编程中，我们可以根据具体的需求选择合适的整数开方算法。

如果需要高精度的计算，可以选择牛顿迭代法；如果需要快速计算，可以选择位运算法；如果对精度要求不高，可以选择二分法。

另外，还可以结合不同的算法，根据具体情况进行优化。

已知：F(x)=x4-4x3-6x2-16x+4,求极小值，极小值点，区间，迭代次数？用进退法确定区间，用黄金分割法求极值。

#include <stdio.h>#include <math.h>#define e 0.001#define tt 0.01float f(double x){float y=pow(x,4)-4*pow(x,3)-6*pow(x,2)-16*x+4;return(y);}finding(float *p1,float*p2){float x1=0,x2,x3,t,f1,f2,f3,h=tt;int n=0;x2=x1+h;f1=f(x1);f2=f(x2);if(f2>f1) {h=-h;t=x2;x2=x1;x1=t;}do{ x3=x2+h;h=2*h;f3=f(x3);n=n+1;}while(f3<f2);if(x1>x3) {t=x1;x1=x3;x3=t;}*p1=x1;*p2=x3;return(n);}gold(float *p){float a,b,x1,x2,f1,f2; int n=0;finding(&a,&b);do{x1=a+0.382*(b-a);x2=a+0.618*(b-a);f1=f(x1);f2=f(x2);n=n+1;if(f1>f2) a=x1;else b=x2;}while((b-a)>e);*p=(x1+x2)/2;return(n);}main(){float a,b,x,min;int n1,n2;n1=finding(&a,&b);n2=gold(&x);min=f(x);printf("\n The area is %f to %f.",a,b); printf("\n The nunmber 1 is %d.",n1);printf("\n The min is %f and the result is %f.",x,min);printf("\n The nunmber 2 is %d.",n2)二插法已知：F(x1,x2)=4*x1-x2的平方-12；求极小值，极小值点，迭代次数？用复合形法求极值。

进退法试用进退法确定函数f(x)=3x2+8x+9的初始单峰区间，设定给定的初始值x0=0,初始步长h=0.1。

#include <math.h>#include <stdlib.h>#include <stdio.h>main(){float x0=0,x1,x2;float h=0.1;double f1,f2;printf("请输入初始点，初始步长。

\n");/*scanf("%f%f\n",&x0,&h);*/x1=x0;x2=x1+h;printf("%f,%f\n",x1,x2);f1=3*pow(x1,2)-8*x1+9;f2=3*pow(x2,2)-8*x2+9;printf("%f,%f\n",f1,f2);if(f1>f2) {ss:h=2*h;x2=x2+h;f1=f2;f2=3*pow(x2,2)-8*x2-9;if(f2>f1)printf("区间是%f,%f\n",x1,x2);else {x1=x2-h;if(f1==f2)printf("区间是%f,%f\n",x1,x2);else goto ss;}}else{if(f2==f1)printf("区间是%f,%f\n",x1,x2);else{h=-h/4;kk: x1=x1+h;f2=f1;f1=3*pow(x1,2)-8*x1-9;if(f2<f1)printf("区间是%f,%f\n",x1,x2);else{x2=x1-h;if(f1=f2)printf("区间是%f,%f\n",x1,x2);else{h=2*h;goto kk;}}}}}输出正确结果：（0.7，3.1）黄金分割法试用黄金分割法求一元函数minf(x)=x2+6x+9的最优解。