数值算法学习笔记

非线性方程求根

这一部分很大情况下以来与函数本身的单调性，
需要掌握一定的数学基础对函数概念要有清晰的认识。
可能也要有点求导和积分的知识。
~~还好我会~~ 我会个毛线
:)

UVa-10341 Solve It!

传送门:UVa-10341
题目大意:
试解一个方程，使得

$pe^{-x}+qsin(x)+rcos(x)+stan(x)+tx^2+u =0 \space \space , x \in [0,1].\\\\ 0\leq p,r \leq 20;\\\\ -20\leq q,s,t \leq 0;$

光凭这个方程我们毫无办法，因为对整个函数求导可以得到.

应用分部求导法则就可以了算是简单的求导

得到

$f'(x) = -pe^{-x}+qcos(x)-rsin(x)+2stan(x)sec^2(x)+2tx \\\\$

眼花缭乱毫无办法,凭借导函数我们看不出任何增减性的变化。

注意到x的边界为0,1。

那么有以下函数在该区间是单减的（严格递减）

$e^{-x};cos(x);$

有以下的函数在该区间单增（严格递增）

$sin(x);tan(x);tx^2;$

再看一眼题目看到了sin(x),tan(x),tx^2前面的系数都是非正的！那么相当于整个函数为在[0,1]上的减函数。

于是根据介值定理，在某一区间上（这里是[0,1]），这个单调递减的函数若满足f(0) >= 0 >= f(1).

则在[0,1]上一定有且仅有一个解.

于是二分就行了。

#include<bits/stdc++.h>
#include<cmath>
using namespace std;

const double eps = 1e-7;
double p,q,r,s,t,u;
double e = pow(double(1.0+1.0/10000),10000);
double calc(double x){return (p*exp(-x)+q*sin(x)+r*cos(x)+s*tan(x)+t*x*x+u);}
\\e^x 可以写成exp(-x)!
int main(int argc, char *argv[])
{
	while(scanf("%lf%lf%lf%lf%lf%lf",&p,&q,&r,&s,&t,&u) == 6)
	{
		double lim0 = calc(0),lim1 = calc(1);
		if (lim1 > 1e-9 || lim0 < -1e-9)
		{
			puts("No solution");
			continue;
		}
		double l = 0.0,r = 1.0,mid;
		while(r-l > eps)
		{
			mid = (l+r)/2;
			if (calc(mid) > 0.0)
			l = mid;
			else 
			r = mid;
		}
		printf("%.4lf\n",l);
	}
	return 0;
}

LA-5009 Error Curves

传送门:LA-5009

题目大意:给出n个抛物线（开口向上）或者直线，定义一个总函数f(x) = max{Si(x)}.

求这个总函数在[0,1000]上的最小值。

错误思路:
把每个函数在[0,1000]上的最小值求出来最后一遍取最小。
这样虽说看上去毫无问题，但是这个思路对于定义就是不正确的
f(x)的定义是max(si(x))而不是min,也就是说,我们在处理函数时不能以偏概全,必须在某一区间上硬性规定要取的是函数的最大值,换言之,我们的答案不能保证取到这个答案时f(x)能取到这个最小值。

//wrong answer.
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
const double eps = 1e-7;
int T,n;
struct Node{
	int a,b,c;
	double ans;
}f[maxn]; 
void calc(Node q)
{
	int x = q.a,y = q.b,z = q.c;
	if (x == 0)
	{
		if (y <= 0) 
		{
			q.ans = (double)(z);
			return ;
		}
		else 
		{
			q.ans = (double)(1000*y+z);
			return ;
		}
	}
	else
	{
		double u = (-y)/(2*x);
		if (u > eps  &&  1000 - u > eps)
			{
				q.ans = u*u*double(x)+u*double(y)+u*double(z);
				return ; 
			}
		if (u < -eps)
			{
				q.ans = double(z);
				return ;
			}
		if (u - 1000 > eps)
			{
				q.ans = 1000*1000*double(x)+double(y)*1000+double(z);
				return ;		
			}		
	}
}
int main(int argc ,char *argv[])
{
	scanf("%d",&T);
	while(T--)
	{
		double ass = 1e8;
		scanf("%d",&n);
		for (int i = 1; i <= n; i++)
			scanf("%d%d%d",&f[i].a,&f[i].b,&f[i].c),
		calc(f[i]),
		ass = min(ass,f[i].ans),
		printf("%.4lf\n",ass);
	} 
	return 0;
}

正解:
可以证明，对于两条抛物线或者直线，要么是单增单减，要么是开口向上的凹形图像。
再用一次数学归纳法,证明从n条线推导到n+1条曲线即可。
因为答案呈单峰，三分求解即可。
交了两次,第一次eps =1e-7莫名wa掉,第二次eps=1e-9就AC了
你敢信
Markdown

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
const double eps = 1e-9;

int a[maxn],b[maxn],c[maxn],T,n;

inline void read(int &x)
{
	x=0;char ch=getchar();int f=1;
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}

double calc(double x)
{
	double ans = a[1]*x*x+b[1]*x+c[1];
	for (int i = 2; i <= n; i++)
		ans = max(ans,a[i]*x*x+b[i]*x+c[i]);
	return ans;
}

int main(int argc, char *argv[])
{
	read(T);
	while(T--)
	{
		read(n);
		for (int i = 1; i <= n; i++)
			read(a[i]),read(b[i]),read(c[i]);
		double l = 0.0,r = 1000.0;
		while(r - l > eps)
		{
			double m1,m2;
			m1 = l+(r-l)/3;
			m2 = r-(r-l)/3;
			if (calc(m2)-calc(m1) > eps)
			r = m2;
			else
			l = m1;
		}
		//printf("%.4lf %.4lf\n",l,r);
		printf("%.4lf\n",calc(l));
	}
	return 0;
}

积分导数技巧

虽然积分和导数算是我高数里比较擅长的东西。
但是还是要理一下的吧。

导数的定义

在可导函数上某一点的瞬时变化率.

$\lim_{\Delta x\rightarrow0} \frac{f(x_0+\Delta x)-f(x_0)}{\Delta x}$

基本初等函数导数即求导法则.

$f(x)=t,f'(x)=0\\\\ f(x)=x^n,f'(x)=nx^{n-1}\\\\ f(x)=sin(x),f'(x)=cos(x)\\\\ f(x)=cos(x),f'(x)=-sin(x)\\\\ f(x)=e^x,f'(x)=e^x\\\\ f(x)=lnx,f'(x)=\frac{1}{x}\\\\ f(x) = tan(x),f'(x)=\frac{1}{cos^2(x)}$ $乘法则:如果一个函数f(x)=g(x)h(x),那么\\\\ f'(x) = g'(x)h(x)+g(x)h'(x)$ $商法则：如果一个函数f(x)=\frac{g(x)}{h(x)},那么\\\\ f'(x)=\frac{g'(x)h(x)-g(x)h'(x)}{h^2(x)}$ $链导法则：如果一个函数f(x)=g(h(x)),那么\\\\ f'(x)=g'(h(x))·h'(x)$

~~Mathjax打得我好累~~