首页查找驱动Windows 日常使用数据挖掘与人工智能搜索引擎与SEO技术备忘录站长随笔

梯度法和牛顿法,利用导函数查找函数的极值与方程根

2020-04-22 常用计算公式 浏览次数:3999
 
原理:都是利用导函数(某点的斜率,切线,变化率)无限接近极值。

有两个地方要注意:

1 无限接近:最终得到的值不是绝对正确值,而是一个接近正确值的数值。
2 极值:极大(小)值不等于最大(小)值,最终的结算结果可能是某个区间的极值,距离正确值可能会有很大误差,要解决这个,可以采用不同区域的初始值进行计算。

另外,关于导函数要注意的是:

1 不是每一个方程式都有导函数。
2 某点的斜率为零,并不等于某点就是极值,某点是极值的条件:左右两边的导数值一定是一个大于零一个小于零。

话题一:查找某方程的近似根。

牛顿法:利用某点切线(斜率)在变量轴上的交点,多次迭代求出逼近真实的极值。



从上图可以看出,用某个点的切线与变量轴的相交点做为下一个计算点,随着循环次数增加,当前点与上一个点之间的距离会不断的减小,以至于无限趋向于零,如果把距离看作计算精度,一旦精度值小于我们设定的精度值,那么就可以停止求值。牛顿法合适求方程根,用来求极值有时候不方便

话题二:求某方程的极值。

核心:利用导数直的正负来作为判断标准,对输入值应该是加大或减少。

某一点处于单调上升区间,那么它的导数值就是正值。
某一点处于单调下降区间,那么它的导数值就是负值。
某一点处于极值点,那么它的导数值为零。

利用导数的正负值来对此点进行微调(减小或加大),经过多次迭代,就可以接近极值。

什么时候停止迭代?

1 达到设定的迭代次数。
2 导数值为零。
3 某一次的导数值与上一次的正负符号相反,说明越过了极值点,所以取上一次的导数值作为解。

如果微调系数过大,是有可能一下子越过极值点的,当然了越过极值点也不怕,也会慢慢的往极值点回归的,只不过需要增加点循环次数,所以微调系数不宜过大;但是微调系数太小,也会消耗很多算力,毕竟循环次数多了。

对可导的方程查找极值步骤:

1 输入任意一个初始点作为当前点
2 判断当前点的导数的正负
3 根据导数正负,对当前点微调。在这里,导数值的本身并不很重要,更重要的是它充当了一个加减符号指示值,告诉人们要对当前值进行增加还是减小



上图是方程y=x*x + 1的曲线图。

如果X取值是小于零,那么这些点就处于单调递减区间,斜率的变化是递减,箭头朝下,导数值是负数。

如果X取值是大于零,那么这些点就处于单调递增区间,斜率的变化是递增,箭头朝上,导数值是正数。


int fun1()
{
printf("原始函数: y=X * X + 1,其导函数为:f'(y)=2x,输入初始值:");

int InputValue=0;
cin>>InputValue;

// 设置初始点
double x=InputValue;
// 每次增减值
double Step=0.001;

double lastx=x;
int k=0;
while (true)
{
// 求导数值
double d=2*x;

// 如果导数值小于零,需要将x值加大;如果导数值大于零,需要将x值减小
x=x-d*Step;

// 如果导数值为零那么说明到达了极点位置
// if (d==0) break; 其实这句话在计算机里面不能成立,因为双精度型不会绝对等于零,只有无限接近于零

// 只能采用另一种方法,本次的x值和上一次的x值之差,小于一定值的时候,就可以停止了
double t=0;

if (lastx < x){
t=x - lastx;
}
else{
t=lastx - x;
}

t=t / x;
// 达到指定的精度,就停止
if (t < 0) t=0-t;
if (t <= 0.0001) break;

lastx=x;

k++;
}

double y=x * x + 1;
printf("\r\n初始值:%d,极点在: [%.3lf, %.3lf],循环了%d次\r\n",InputValue,x,y,k);

InputValue=0;
cin>>InputValue;

return 0;
}







对于多元函数求极值的方法:

步骤:

1 对每一个变量求一阶导函数
2 将所有一阶导函数组成方程组,算出所有解
3 对所有变量求二阶导函数;把所有变量组合成一起,看成一个变量名,求其一阶导函数
4 将方程组的所有解逐个代入二阶导函数,按照以下规则判断

如果 f'(xx)f'(yy) > f'(xy),此点是极值点,如果 f'(xx) > 0 此点是极小值;如果 f'(xx) < 0 此点是极大值
如果 f'(xx)f'(yy) < f'(xy),此点不是极值点
如果 f'(xx)f'(yy) = f'(xy),此点可能是极值点,也可能不是极值点

修正:f'(xy)与f'(yx)的区别在于:前者是先对 x 求偏导,然后将所得的偏导函数再对 y 求偏导;后者是先对 y 求偏导再对 x 求偏导。当 f'(xy) 与 f'(yx) 都连续时,求导的结果与先后次序无关(当二阶偏导数连续时,二阶混合偏导数与求导次序无关,所以f'(xy)必定等于f'(yx))。下图有关这段文字是错误的“把XY看出一个整体变量”。




话题三:梯度下降(上升),通俗的说,就是给你一堆训练数据集,然后自己设置个大概函数,最后让计算机帮你进行微调参数值,企图找到一个函数,用训练数据里的参数代入之后,计算出来的值尽量跟原数据差别不大。

其实跟话题二非常的相似,都是利用导数值作为一个方向标参考,以便决定变量是增加还是减小。

梯度,其实就是一堆偏导数的集合,有多少个变量,就有多少个偏导数。

关于梯度的计算,就是求偏导数,每一次循环,都将当前的变量值代入偏导数,计算出新的变量值,然后根据偏导数的正负,对每一个变量值进行微调。

停止迭代条件:
1 精度达到指定值
2 循环次数到达一定值,但实际上我更趋向于用时间来限制。


const DC=4;

// 生成数据集
void CreateDataList(double* X, double* Y, double* Z)
{
// 随机生成据
int MaxNumber=20;
// srand(time(0));
srand(9);
int N=0;
while (N < DC){
X[N]=rand()%MaxNumber+1;
Y[N]=rand()%MaxNumber+1;
// 原函数: Z=2X*X + 9Y*Y;
Z[N]=2*X[N]*X[N] + 9*Y[N] + X[N]*Y[N];
printf("训练数据集: [%.0lf, %.0lf, %.0lf]\r\n",X[N],Y[N],Z[N]);
N++;
}

}

int main()
{

printf("原始函数: Z=2 * X * X + 9 * Y + X * Y 产生的输入如下:\r\n");

// 生成数据集
double X[DC]={0};
double Y[DC]={0};
double Z[DC]={0};

CreateDataList(X,Y,Z);

printf("拟合函数: Z=a * X * X + b * Y + c\r\n");

/*
创造拟合函数,采用的函数不一定要跟原来的一样,毕竟现实中很难知道原函数是什么,或许也没有原函数,
但是有一点可以确定的是:用不同的函数可以画出同样的坐标曲线图

设用于拟合的函数为:f(X,Y)=a*X*X + b*Y + c

现在就是要让计算机帮找出合适的a,b,c值,有点像大体框架我来搭,继续细节完善让计算机来做


采用最新二乘法作为损失函数: H=(f(X,Y) - Z) * (f(X,Y) - Z) / (2*DC)
实际就是用拟合函数 减 训练集的数据,把这个误差当做做事依据

a 偏导数: H'(a)=(f(X,Y) - Z) * X*X
b 偏导数: H'(b)=(f(X,Y) - Z) * Y
c 偏导数: H'(b)=(f(X,Y) - Z) * 1
*/

double loss=0;

// 每次增减值
double Step=0.001;

// 设置初始点
double a=0;
double b=30;
double c=1;

int K=0;
while (true)
{

// 偏导数的值
double FA=0;
double FB=0;
double FC=0;

int N=0;
while (N < DC){
double ParamX=X[N];
double ParamY=Y[N];


// 将数据集的X,Y数值代入拟合函数
double F=a*ParamX*ParamX + b*ParamY + c;
// 将数据集的X,Y,Z数值代入偏导函数
double Fa=(F-Z[N]) * ParamX*ParamX;
double Fb=(F-Z[N]) * ParamY;
double Fc=(F-Z[N]) * 1;


// 累计偏导数的值
Fa/=1000;
Fb/=1000;
Fc/=1000;
FA+=Fa;
FB+=Fb;
FC+=Fc;

N++;
}

// 本来设想:在某偏导函数某一次的运算后找到极值就停止了,以后的循环里不再计算这个变量偏导函数,
// 但是这样做是错的,因为拟合函数每一次运算都会用到所有变量,而导致每次的导数正负变化都不一样。

// 网上很多教程喜欢用导数值参与运算,我不太喜欢,我更喜欢自己微调,所以把下面三句代码注释掉了
// a=a - (FA * Step / DC);
// b=b - (FB * Step / DC);
// c=c - (FC * Step / DC);

// 其实在实际应用中更加灵活,可以采用类似二分查找法一样,估算值进行跳跃,可大大缩减循环次数
double fu=0;
if (FA < 0){
fu=Step;
}
else{
fu=0-Step;
}
a+=fu;


fu=0;
if (FB < 0){
fu=Step;
}
else{
fu=0-Step;
}
b+=fu;


fu=0;
if (FC < 0){
fu=Step;
}
else{
fu=0-Step;
}
c+=fu;


loss=0;
N=0;
while (N < DC){
double ParamX=X[N];
double ParamY=Y[N];

// 将数据集的X,Y数值代入拟合函数
double F=a*ParamX*ParamX + b*ParamY + c;
// 拟合函数和原值的差
double T=(F-Z[N]);
double error=(T*T) / (2*DC);

loss+=error;

N++;
}

// 达到指定精度,停止循环
if (loss <= 0.01) break;

// 有时候怎么算都达不到指定的精度,所以得设置其他的终止循环条件
// 这里省事,限制循环次数
if (K++ > 10000000) break;
// 也可以设置函数超时,if (time > 超时值) break;
}

printf("\r\n得出拟合函数函数: Z=%.3lf * X * X + %.3lf * Y + %.3lf\r\n",a,b,c);
printf("结果: [a=%.3lf, b=%.3lf, c=%3.lf],循环次数: %d,精度: %.3lf\r\n",a,b,c,K,loss);


int N=0;
while (N < DC){
double ParamX=X[N];
double ParamY=Y[N];

// 将数据集的X,Y数值代入函数
double F=a*ParamX*ParamX + b*ParamY + c;
// 将数据集的X,Y,Z数值代入偏导函数
printf("原值 / 拟合值: %.3lf / %.3lf\r\n",Z[N],F);

N++;
}

int InputValue=0;
cin>>InputValue;


return 0;
}


拟合结果:
留言

有啥想说的就说吧,有啥想问的就问吧
Good good study, day day up!

昵称

Email (填它做啥?国内不兴这玩意,但程序代码里有,我懒得删...)

    ToolBar:

    正在上传图片,请稍等...   

内容  (如果可以的话,最好有相关问题的几张图,特别是出现了错误的时候,当时弹出的错误消息,或者对话框之类的,截图传上来看看吧,这样才好知道具体情况)

查看 HTML 代码(只读模式), 点击返回编辑.

 
最新文章
 
求助
2019 - 2024 mypcrun.com
桂ICP备19002156号-1桂公网安备 45070202000667号
这回把网站设计得那么漂亮,这下子不会被人笑了吧。