一个代数不等式

mathe · 发表于 2014-7-2 13:30:41

由于22楼的分析对于一般k也成立，我们也总是只需要分析最大和最小的r

mathe · 发表于 2014-7-2 13:44:00

其中最大小的r贡献的乘积对于充分大的t同$k^(-{t(t+1)}/2)$正比，所以说明对充分大的t以后，必然是拆封成较小若干段乘积绝对值更大，也就是太大的t不用考虑。而其中最大的r接近-1，可以看出t趋向无穷时乘积将收敛。所以如果对所有的t，部分乘积绝对值都小于1，拆分就没有好处了，不然，对于充分大的t,我们总可以拆分一部分出来使得乘积变大。而这个k的分界数值计算大概在6.314473,也就是k小于这个数时，无论n多大，都只需要分析有限个t。但是如果k大于这个界以后可能就需要分析所有的t

mathe · 发表于 2014-7-3 06:03:39

如同17#设一般情况$T=\prod_{i=1}^n(kx_{i-1}-x_i)$
偏导数为$\frac{\partial T}{\partial x_i}=T(\frac{k}{kx_i-x_{i+1}}-\frac{1}{kx_{i-1}-x_i})$
于是T取极值时对于所有的i,差值$\frac{k}{kx_i-x_{i+1}}-\frac{1}{kx_{i-1}-x_i}$相等，设这个差值为$(k-1)K$其中K为参数
同样设$Y_i=\frac{1}{kx_{i-1}-x_i}$,于是$k(Y_{i+1}-K)=Y_i-K$.于是同样得出全局极值点只能所有$x_i$相等。
而对于边界情况中长度为t的不含0的部分，同样设
$Y_1-K=k(Y_2-K)=...=k^t(Y_{t+1}-K)=S$,得出
$Y_i=k^{-(i-1)}S+K,kx_{i-1}-x_i=\frac{1}{k^{-(i-1)}S+K}$
所以
$\frac{x_{i-1}}{k^{i-2}}-frac{x_i}{k^{i-1}}=\frac{1}{S+k^{i-1}K}$
累加得出参数$S/K$满足方程$0=\sum_{i=0}^t\frac{1}{x+k^i}$
而根据上面等式我们还可以得出$t+1=\sum_{i=0}^t\frac{x+k^i}{x+k^i}=\sum_{i=0}^t\frac{k^i}{x+k^i}$
也即是$t+1=K^{t+1}\sum_{i=0}^t\frac{1}{k^{-i}S+K}=K^{t+1}\sum_{i=0}^t(kx_i-x_{i+1})=K^{t+1}(k-1)\sum_{i=1}^tx_i$
所以也就是说如果我们取n个数的和为$n/{k-1}$,那么这时$K=1,S=x$,而其中长为t的一段最大连续非零数和为${t+1}/{k-1}$
而这时，这一段数对目标函数贡献的乘积为$\prod_{i=0}^t(kx_i-x_{i+1})=\prod_{i=0}^t\frac{1}{k^{-i}S+K}=\prod_{i=0}^t\frac{k^i}{x+k^i}$
而全局极值点在$\sum_{i=1}^tx_i=n/{k-1}$时目标函数$T=1$

mathe · 发表于 2014-7-3 06:11:53

方程$0=\sum_{i=0}^t\frac{1}{x+k^i}$最大根（绝对值最小）在$(-k,-1)$,而且随着t趋向无穷，这个根收敛到一个这个区间中一个数（但不在边界）
而对应目标函数乘积$\prod_{i=0}^t\frac{k^i}{x+k^i}=\Pi_{i=0}^t\frac{1}{1+k^{-i}x}$在t趋向无穷时绝对收敛
而方程最小根在$(-k^t,-k^{t-1})$上，同样可以设这个根为$-k^t*\lambda_t$,同样可以知道在t趋向无穷时$\lambda_t$趋向$(-1,-1/k)$中间一个数$\lambda$，而对应目标函数乘积为
$\prod_{i=0}^t\frac{1}{1-k^{t-i}\lambda_t}=\prod_{i=0}^t\frac{1}{1-k^i\lambda_t}$，所以t趋向无穷时收敛到$\prod_{i=0}^{+infty}\frac{1}{1-k^i\lambda}=0$

mathe · 发表于 2014-7-3 21:09:44

根据上面分析，在k比较大时，最值应该会比较简单，最大是全部相等时取到，最小在只有一个0时取到，比如k=7.
而k比较小时，好像不会在全局极值点取到最大值（唯一例外可能在中间一小段对于比较小的n有可能会取到全局极大值）

mathe · 发表于 2014-7-4 08:55:59

现在我们可以数值计算分析一下对于较小的n极值所采用的模式，类似前面的记号，全局极值点的取值为G=1,而t个连续非零数对应乘积的两个极值为$A_{t+1},B_{t+1}$,数值计算n=3时最小值为A3,最大值在k小于2.61时为B3,大于2.62为G.n=4时最小值为A4,最大值为A2^2和1，分界约5.82。n=5时，最小值为A2B3和A5,分界约2.32，最大值为A2A3和G,分界为6.03。n=6时最小值为A2^3和A6,分界约5.56,最大值为A3^2和G,分界约6.24。n=7时最小值为A2^2A3和A7,分界约5.78，最大值为A2^2B3,A3A4和G，分界在约2.12,6.27(这时开始有三段）

mathe · 发表于 2014-7-4 10:24:24

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
#define MAXC 100
#define MIN_ERR 1E-10
double f(double k, double x, int t){
double s=0.0;
double ki=pow(k,(double)t);
int i;
for(i=t;i>=0;i--){
s+=1./(x+ki);
ki/=k;
}
return s;
}
double df(double k, double x, int t){
double s=0.0;
double ki=pow(k,(double)t);
int i;
for(i=t;i>=0;i--){
s-=1./((x+ki)*(x+ki));
ki/=k;
}
return s;
}
double find_max_root(double k, int t){
double x0;
int c=0;
x0=-(k+1.0)/2.0;
while(c<MAXC){
double err=f(k,x0,t)/df(k,x0,t);
x0-=err;
if(err/x0<MIN_ERR)
break;
}
if(c==MAXC){
fprintf(stderr,"too much error find max root for %f,%d\n",k,t);
}
return x0;
}
double find_min_root(double k, int t){
double x0;
double kp;
int c;
kp=pow(k,(double)t);
x0=-(k+1.0)/2.0*kp/k;
while(c<MAXC){
double err=f(k,x0,t)/df(k,x0,t);
x0-=err;
if(err/x0<MIN_ERR)
break;
}
if(c==MAXC){
fprintf(stderr,"too much error find min root for %f,%d\n",k,t);
}
return x0;
}
double find_root_target(double k, int t, double r){
double p=1.0;
double kp=1.0;
int i;
for(i=0;i<=t;i++){
p/=(1.0+kp*r);
kp/=k;
}
return p;
}
#define TYPE_A 0
#define TYPE_B 1
typedef struct _rtype_t{
double d;
int c;
int t;
}rtype_t;
vector<rtype_t> v;
#define MAXN 40
#define MINK 1.01
#define MAXK 10.0
#define STEPK 0.01
typedef struct _item_t{
short index;
short count;
}item_t;
item_t cur_max[MAXN];
int cur_max_count;
double cur_max_value;
item_t cur_min[MAXN];
int cur_min_count;
double cur_min_value;
item_t cur_stack[MAXN];
int cur_stack_count;
int csum;
double mprod[MAXN];
void dump_items(const item_t items[MAXN], int c, double value){
printf("%.3g\t",value);
if(c==0){
printf("G");
}else{
int i;
for(i=0;i<c;i++){
int index=items[i].index;
if(v[index].t==TYPE_A){
printf("A%d",v[index].c);
}else{
printf("B%d",v[index].c);
}
if(items[i].count>1){
printf("^%d",items[i].count);
}
}
}
}
void find_recursive(double k, int n, int t)
{
int i,j;
int ic=v[t].c;
double d=1.0;
for(i=1;i*ic<=n-csum;i++){//try to use i times v[t].d
d*=v[t].d;
if(cur_stack_count==0){
mprod[cur_stack_count]=d;
}else{
mprod[cur_stack_count]=mprod[cur_stack_count-1]*d;
}
cur_stack[cur_stack_count].index=t;
cur_stack[cur_stack_count].count=i;
csum+=i*ic;
if(csum==n){
if(mprod[cur_stack_count]<cur_min_value){
cur_min_value=mprod[cur_stack_count];
cur_min_count = cur_stack_count+1;
memcpy(&cur_min, &cur_stack, sizeof(cur_min[0])*cur_min_count);
}else if(mprod[cur_stack_count]>cur_max_value){
cur_max_value=mprod[cur_stack_count];
cur_max_count = cur_stack_count+1;
memcpy(&cur_max, &cur_stack, sizeof(cur_max[0])*cur_max_count);
}
}else{
cur_stack_count++;
for(j=t+1;j<v.size();j++){
find_recursive(k,n,j);
}
cur_stack_count--;
}
csum-=i*ic;
}
}
void find_min_max(double k,int n)
{
cur_max_count=cur_min_count=0;
cur_max_value=cur_min_value=1.0;
cur_stack_count=0;csum=0;mprod[0]=1.0;
int i;
for(i=0;i<v.size();++i){
find_recursive(k,n,i);
}
printf("min%d\t",n);
dump_items(cur_min,cur_min_count,cur_min_value);
printf("\tmax%d\t",n);
dump_items(cur_max,cur_max_count,cur_max_value);
printf("\t");
}
void try_add_value(const rtype_t& rt)
{
int size=v.size();
int i,j;
for(i=0;i<size;i++){
for(j=i;j<size;j++){
if(v[i].c+v[j].c!=rt.c)continue;
double t=v[i].d*v[j].d;
if(t*rt.d>0){//must same sign
if(fabs(rt.d)<=fabs(t)){//we could remove it
return;
}
}
}
}
v.push_back(rt);
}
int main()
{
double k;
int n;
for(k=MINK;k<MAXK;k+=STEPK){
v.clear();
double r=find_min_root(k,1);//r1
double A2=find_root_target(k,1,r);
printf("k=%.3g\t",k);
rtype_t rt;
rt.d=A2;rt.c=2;rt.t=TYPE_A;
v.push_back(rt);
for(n=3;n<=MAXN;n++){
r=find_min_root(k,n-1);
double B = find_root_target(k,n-1,r);
r=find_max_root(k,n-1);
double A = find_root_target(k,n-1,r);
if(n&1){
rt.d=B;rt.c=n;rt.t=TYPE_B;
try_add_value(rt);
rt.d=A;rt.t=TYPE_A;
try_add_value(rt);
}else{
if(fabs(A)>=fabs(B)){
rt.d=A;rt.c=n;rt.t=TYPE_A;
}else{
rt.d=B;rt.c=n;rt.t=TYPE_B;
}
try_add_value(rt);
}
find_min_max(k,n);
}
printf("\n");
}
}

复制代码

mathe · 发表于 2014-7-4 13:12:07

现在随便取一个特例$n=10,k=6,S=n/{k-1}=2$的情况已知$\sum_{h=1}^10x_h=2,x_0=x_10,x_h>=0$，求$\prod_{h=1}^10(6x_{h-1}-x_h)$的最值
我们现在可以得到 $A_3^2A_4=-1.216284499029738978312013981<=\prod_{h=1}^10(6x_{h-1}-x_h)<=1.169884986538096750088324307=A_5^2$
略微修改可以写成一个看上去舒服一点的不等式 $-11/9<\prod_{h=1}^10(6x_{h-1}-x_h)<6/5$
计算$A_3,A_4,A_5$得出 $A3=-1.061818494455482830466867062$ 由$0,u_1=0.4159268149800571614955459999,u_2=0.1840731850199428385044540000$三个数构成的一段数取到
$A4=-1.078784259169675957317902515$, 由$0,v_1=0.4184646072638971043360394266,v_2=0.2122115263540643604243481800,v_3=0.1693238663820385352396123968$四个数构成一段数取到
$A5=-1.081612216341003033739793319$, 由$0,w_1=0.4188846033465609284019833903,w_2=0.2168394522384006497782939244,w_3=0.1971725276545286129429425117,w_4=0.1671034167605098088767801764$ 五个数构成的数据段取到
所以10个和为2的数$0,u_1,u_2,0,u_1,u_2,0,v_1,v_2,v_3$可以取到最小值$A_3^2A_4$ 10个和为2的数$0,w_1,w_2,w_3,w_4,0,w_1,w_2,w_3,w_4$可以取到最大之$A_5^2$

mathe · 发表于 2014-7-5 11:12:22

25#方法对于一切k＞=1都成立，而且对于t=4的情况，由于总乘积为正数，同样可以两两合并，也就是Bh在h>=5不用考虑

mathe · 发表于 2014-7-5 11:45:56

数值计算结果表明$B_4$也不用考虑，也就是$B_4$的绝对值必然小于$A_4$的绝对值，但是用这个方法就不行了. 不过可以直接比较两个极值得出$|B_4|<|A_4|$(实际上对于任意$h>3,|B_h|<|A_h|$.）
由此,再加上前面得出对于$h>=5$我们也不需要考虑$B_h$,我们得出只需要考虑$B_3$和$A_h$

账号		自动登录	找回密码
密码			欢迎注册

[转载] 一个代数不等式