我为基本操作构建了一个普通的分数类。唯一的问题是，由于有大量操作（我正在做高斯消除），分子或分母都会溢出。
我有 100 个方程，所以有一个 100 x 100 矩阵。并且最终的结果需要精确到10^-6。我应该怎么办？
问问题
626 次
4 回答
2
正如@Chris A 在他的评论中已经建议的那样，我会使用任意精度整数作为分母和分子。您可以使用的示例实现是GNU MP Bignum。
并确保您尽快简化（“取消”）分数！这使分母和分子保持较小。因此，最大公约数可能是有意义的。
于 2011-06-28T16:57:46.583 回答
0
由于您的 100x100 矩阵是病态的，您可能会出现溢出/未溢出。如果您不使用部分旋转，则应该使用。
更好的选择是使用除高斯消除之外的其他方法。即使有部分旋转，高斯消元仍然会遇到与病态矩阵相关的问题。一种替代方法是使用通过奇异值分解构造伪逆。使用 SVD 将矩阵 A 分解为 UVW* 形式。A 的伪逆是 UV^{-1}W*，其中 V^{-1} 是对角矩阵 V 的伪逆。这很容易计算：只需找到每个对角元素的逆，除了你使用看似矛盾的 1/（小数）= 0。
于 2011-06-28T17:43:29.990 回答
0
众所周知，完整 NxN 矩阵 A 的LU 分解（相当于高斯消元的行缩减阶段）需要 ~2N³/3 次乘法和除法。即使部分旋转，此操作计数也成立。
浮点运算可能会导致每一步的舍入误差。消除步骤的“前向”误差分析不会产生有用的准确度估计，因为在最坏的情况下，舍入误差会以指数方式累积。然而，JH Wilkinson 展示了“后向误差分析可以给出现实的估计，例如对于正定矩阵或对角占优矩阵，其中通过高斯消元计算得到的解是要求解的系统的“适度”扰动的精确解（通常情况下也只有部分旋转）。然后可以根据扰动的大小和矩阵的条件数来估计残差的大小，通常定义为 A 的范数与 A 的逆范数之比。如果 A 是奇异的，这是无限的，如果 A 接近奇异，那么任意大。如果条件数大到足以将扰动大小（通常是浮点运算的机器 epsilon）放大到大于可接受的残差，我们就说矩阵是病态的。否则我们说 A 是良条件的。
当然，一个想法是通过使用整数或有理数的精确算术来避免浮点算术的舍入误差。
但是精确的整数保留算法通常会导致条目的快速增长并因此溢出，即使矩阵在上述意义上是条件良好的。 已经提出了各种最小化条目增长的策略，这可以追溯到 Jordan（其名称通常与高斯相关，在消除版本中计算矩阵逆而不是线性系统的解）。W. Kahan 给出了一个特别简洁的说明。任意精度整数（或有理数）实现将解决这个困难。
然而，这种精确的方法能否与密集矩阵上的浮点运算竞争似乎值得怀疑。如果像高斯消元这样的直接方法没有达到所需的精度，通过计算残差来检查（将矩阵 A 乘以计算的解并从右侧向量中减去它），然后再次求解一个修正项具有相同矩阵 A 但右侧对应于残差的线性系统。如果高斯消元的归约阶段实际上是作为 LU 分解完成的，则只需要反求解阶段来求解迭代校正。
在必须从可用的浮点精度中提取最佳精度的情况下，基于正交矩阵的直接方法很有用（请参阅Householder和Givens变换）。
归根结底，线性系统的解决方案是一个经常重新发明的轮子，很难想象有一个更强大的软件重用案例。请参阅本演示文稿的第三张幻灯片：“如何编写数值线性代数软件——不要！尽可能依赖现有的成熟软件库来执行数值线性代数计算。”
于 2011-06-29T03:56:55.010 回答
0
对需要约 670000 次算术运算的算法使用精确的有理算术注定要失败。你怎么可能有其他想法？如果您需要精确到 的结果10^-6，则工作到 (哦，我不知道) 的准确度10^-20，并使用旋转。
于 2011-06-28T18:54:01.697 回答