Solve求解非数字系数线性方程组的耗时随未知数数目增加而爆增?
mathematica吧
全部回复
仅看楼主
吧务
level 15
xzcyr 楼主
如题。未知数数目增加时,Solve的求解时间有所增加是意料之中的,可是,我过去还真没注意到,当方程组中的系数不是数字时,这个增加速度是非常快的:
f[n_] := Solve[
Thread[Plus @@@ Table[Unique[] t[j], {i, n}, {j, n}] == 0
(*Table[
Unique[],{j,n}]*)], Table[t[j], {j, n}]]
First@AbsoluteTiming[f[#];] & /@ Range[6];
ListLogPlot[%, Joined -> True]
n = 6 时耗时已经超过了100秒……再往上的我不打算试了。非齐次的情形(使用我写在代码注解里的部分作为等式右端即可)是类似的,这里不贴了。
顺便,对于数字系数,这个问题就基本不构成威胁:
f2[n_] :=
Solve[Thread[
Plus @@@ Table[RandomInteger[{5, 10}] t[j], {i, n}, {j, n}] ==
RandomInteger[{5, 10}]], Table[t[j], {j, n}]]
First@AbsoluteTiming[f2[#];] & /@ Range[60];
ListLogPlot[%, Joined -> True]
RandomReal[]的结果是类似的,这里不贴了。
那么问题来了:这种速度的爆跌可否改善?还是说这就是追求符号解的代价?
2013年11月12日 04点11分 1
吧务
level 15
xzcyr 楼主
目前可以找到的一个改善方法是,改用LinearSolve:
g[n_] := First@
AbsoluteTiming@
LinearSolve[Table[a[i, j], {i, n}, {j, n}](*,Table[b[i],{i,5}]*)];
g /@ Range[8]
(*
{0.0010000, 0., 0.0010000, 0.0020000, 0.1190000, 0.1260000,
0.1380000, 0.6870000}
*)
2013年11月12日 07点11分 3
吧务
level 12
增长速度应该是与n*n!成正比,比e^x还快.
2013年11月12日 13点11分 4
嗯,仔细思考之后我也发现这种增长由解的性质决定的,是自然的,我会感到惊讶只是因为教科书上的用行列式“记录”的解让我产生了错觉而已。
2013年11月12日 15点11分
1