数值计算的优化

返回主页<-

数值计算的优化

总的来说: 别做多余的事情. 此话说起来简单做起来难.

分割

即把复杂的问题适当地减小规模.如 {二分快速方法}

合并

即用适当的方法将分割的问题合并.

尽量把无序的化为有序的,如化为整数指数乘幂的计算 , 乘法两因子尽量接近（对于FFT乘法,），乘法其中一因子尽量小（以便使复杂度降为O(n)）.

例1：

原题: 使得 n²-19n+91 为完全平方数的自然数的个数是 , 即 .

数学解法是:

设 n²-19n+91=m² , n²-19n+90=m²-1 , (n-10)(n-9)=(m+1)(m-1) , (n-10)(n-9)=0

n=9,10

解法让人感到不太服气, 于是用程序来验证某小范围内的数.

最初的思路是这样的:

{$N+}
const MaxN=30000000;

ZERO=1e-8;
var f, q :extended;
i :longint;
begin
for i:=1 to MaxN do begin

f:=i*(i-19)+91; {完全按式子计算}

if abs(f-int(f))<ZERO then writeln(i);

end;

end.

因为 ((n+1)²-19(n+1)+91) - (n²-19n+91) = 2n-18 也就是说, 前一个f(n)加上2n-18就得到 f(n+1), 同样的 f(n+1) 加上 2(n+1)-18 得到 f(n+2). 更进一步, (2(n+1)-18) - (2n-18)= 2. 综合起来就是 f(n+1) = f(n) + t, t=t+2 . 其中 f(0)=91, t0=2*0-18=-18

这样就完全避免了乘法运算. 事实上, 若p(x)是多项式, 要计算连续的 p(x0+ka) (k是整数, a, x0 是常数), 总可以消去乘法运算.

{$N+}
const n=60000000;
var f, q :extended;
    t :longint;
begin
t:=-18;
f:=91;
while i<n do begin
    q:=sqrt(f);
    if f=int(f) then writeln(t shr 1);
    f:=f+t;
    inc(t,2);
end;
end.

关于计算误差:

这里讲的是小数运算时产生误差的问题.

例如计算 1-cos0.1 ,假设用一个有6位数的计算器计算.

若先算得cos0.1=0.995004, 直接计算 1-0.995004=0.00499 只有3位有效数字(原来有6位).

若用幂级数计算cos时忽略首项, 同样的计算量(计算3项)可以获得多三位的有效数字(没有被截断).

若改成 1-cos0.1=2sin(0.05)^2, 同样计算3项幂级数, 也可获得多三位的有效数字(末位有-1的误差)

再看一个例子. 用狭义相对论计算物体的长度变化(与静止长度比较), 设速度是v=30m/s, 光速c=3e8m/s,物体沿速度方向长l₀.

长度变化 Δl=l₀-l₀*√(1-v²/c²).

如果直接计算后一项, √(1-v²/c²)=0.99999999999999499 ,一直要计算到小数点后15位才看出变化.

而 Δl/l₀ = (1-√(1-v²/c²)) = v²/c²/(1+√(1-v²/c²)) { 分子有理化 } =5.0000000000000125e-15 就有17位精度了.

从另一角度看, 有些函数本身的变化速度就很快,以至于即使自变量只有微小变化, 结果也会有较大不同.

为描述这种误差设有 y=f(x), 考虑相对误差 Δy/y, 和自变量的误差 Δx/x, 用微分代替小量.

函数	误差放大量	函数	误差放大量
ax	1	sin(x)	x cot(x)
x^2	2	cos(x)	-x tan(x)
x^n	n	tan(x)	x /sin(x) cos(x)
e^x	x	arcsin(x)	x/√(1-x^2)/arcsin(x)
a^x	x ln(a)	arccos(x)	-x/√(1-x^2)/arccos(x)
ln(x)	1/ln(x)	arctan(x)	x/(1+x^2)/arctan(x)
log(a,x)	1/ln(x)	sinh(x)	x cosh(x)
log(x,a) <*>	-1/ln(x)	cosh(x)	x tanh(x)
		tanh(x)	x/sinh(x)/cosh(x)

<*> 若c=log(a,b) 则 a^c=b. 即a是底数, b是真数, c是对数(指数).

TP7.0 的用户也可参照 TP各语句的运行速度比较来修改程序使之最优.