C++线性方程求解

介绍

 

程序SolveLinearEquations解决联立方程。该方案需要一个文本文件，其中包含输入和输出方程解决。这个项目是几年前我写在C＃中http://www.codeproject.com/Articles/673076/Linear-Equation-Solver线性方程组求解。以外，这个程序没有图形用户界面和一个稍微修改公式格式，这个计划是非常类似于C＃程序，该程序使用SparseArray模板类来实现向量和矩阵。矩阵使用DoubleIndex的类，这需要两个整数指数，实行单一的键使用SparseArray类。矩阵SparseArray的存储类型是双精度数。每个向量只是一个实例的的SparseArray类存储一个双精度值一个整数索引一键。代码使用原油的解析器来解析输入文件中的方程。这是原油，因为它需要有些僵硬的输入格式，不支持括号或数学函数。

 

输入文件是一个文本文件，其中包含方程。可以有不超过1024个字符的行上。方程以分号结束。如果没有分号结尾的行，然后在下一行上继续方程。

 

该方程具有以下格式，它允许使用加法和减法符号，以结合的形式： 

 

[number][variable]

每个方程中必须有一个单等号。

 

无论是数字或变量是可选的，可以结合使用加号或减号所需的许多条款。这个数字可以包含小数点和指数。变量可以

只包含字母字符或下划线字符。

 

浮点指数前^字符，而不是通常的ê字符，以避免任何模糊变量名。下面的行显示一个浮点数，等于230万。  

 

X = 2.3^6

公式必须包含一个等号。

 

方程组的一个例子是： 

 

3 X + 4 Y = -5 Z

 

X + Z = 10 Y

 

X + Z = 42.5

 

注意空行分隔方程。

 

该程序产生的解决方案，这些方程：

 

X = 114.75

Y = 4.25

Z = -72.25

 

 设置3个方程的另一个例子可能是：

 

MARYS_AGE=2BOBS_AGE ; BOBS_AGE = 3 CATHYS_AGE

 

CATHYS_AGE = 4;

 

或另外一个例子：

 

HEIGHT = 5 + 10

如果您忘记了公式的格式

 

运行下面的命令行程序，将给上述有关公式输​​入文件中的要求的格式相同的信息。 

 

SolveLinearEquations -h

背景   

 

我在大学的时候，我写了一个电路分析程序在Fortran。我需要一种方法来解联立方程，我无意中发现了下面这本书和算法： 

 

病态线性方程组 “，由JH威尔金森，”数字计算机的数学方法“第2卷，编辑安东尼·罗尔斯顿和赫伯特·S·维尔夫，1967年，约翰·威利父子，第65-93页的“ 解决方案。虐待空调的方程组是一组方程，是很困难或不可能解决使用给定的浮点精度。方程病态当两个或更多的方程定义几乎平行的线，或两个以上的尺寸，几乎平行的平面几乎平行的超平面的情况下。病态方程的一个例子将是：

 

3 10 -12 X + Y = 0.7

 

            X + Y = 0.9，我很幸运，栽倒在这个特定的参考。虽然这本书给出了一个标准的执行 高斯消去部分旋转，教计算机科学线性代数课程，这种算法也确定是否可以找到一个准确的解决方案。这是通过使用两个矩阵的 规范和一个常数，它被设置的基础上的一个浮点数的尾数的比特数。

 

我已经重写了该算法几次。我写这在Fortran，C + +使用简单的数组，再在C + +使用的是稀疏的容器类，终于在C＃中。

 

早在20世纪70年代末，我一个DEC-10计算机上运行这个算法，解决1000 1000在大约30秒的变量方程。今天，与原来的C代码，一个问题，就是在PC上运行，大小在

眨眼。这段代码是比较慢，因为它使用了一个的SparseArray，但它仍然是非常快的。

 

文件列表

 

SolveLinearEquations.cpp – 主程序。

LinearEquationParser.cpp – 解析输入文件包含方程。

LinearEquationParser.h – 分析器头文件。

CharString.cpp – 一个字符串处理类

CharString.h – 字符串类的头文件。

MatrixPackage.cpp – 包含线性方程组的求解器功能。

MatrixPackage.h – 线性方程组求解的头文件。

SparseArray.h – 的SparseArray模板文件。

DoubleIndex.cpp进入一个关键的两个指标 – A类。

DoubleIndex.h – 头文件DoubleIndex

SolveLinearEquations.vcproj – Visual Studio 2008项目文件。 

SolveLinearEquations.sln – Visual Studio 2008的解决方案文件。

关于SolveLinearEquations功能

 

一组线性方程组的矩阵方程表示： 

 

aMatrix xVector = bVector

该aMatrix bVector，并给出的xVector是解决。

 

上面给出的方程组的第一个例子中可改写为：

 

 

 

3 X + 4 Y + 5 Z = 0

1 X – 10 Y + 1 Z = 0

1 X + 0 Y + 1 Z = 42.5

 

这些方程的矩阵形式为：

 

| 3 4 5 | | X | | 0 | | 1 10 1 | | Y | = | 0 | | 1 0 1 | | Z | | 42.5 |

 

的aMatrix是在左边的方阵。在右边的bVector。 

 

的xVector，其中包含的变量名，这是个未知数，是在中间。为了解决这些方程，调用SolveLinearEquations功能在MatrixPackage命名空间。此功能在文件MatrixPackage.h和定义实施文件MatrixPackage.cpp。

 

 

Status_T SolveLinearEquations(unsigned int number_of_equations, const SparseMatrix & a_matrix, const SparseVector & b_vector, SparseVector & x_vector);

 

一天的意图，实现更大的一组矩阵运算命名这些文件MatricPackage的意图。所有我需要的时候是一个方程求解，，和一些错误代码，现在是矩阵包。xVector，这将存储解决方案，是最后一个参数。方程的数量是一维的正方形矩阵的大小。

 

该计划还将表示，如果一组方程是’奇异’的工作精度。甲奇异的一组方程没有单一的解决方案，因为两个或更多的方程仅仅是其他公式的倍数，如：

 

X + Y = 7 2X + 2Y = 36

 

即使第二个方程，“2X + 2Y = 14”，所以这是与第一个方程相一致，没有单一的解决方案的两个方程，方程是奇异的加工精度，该方案将报告。 

 

确定如果方程是病态的一个重要参数

 

文件MatrixPackage.cpp包含一个常数，它是一套基于数位双精度浮点数的尾数。 

 

const double f_SMALL_FLOAT = 5.69E-14;

如果线性方程解算器移植到另一个平台上，那么一定要调整这个常数。该代码包含以下注释，关于这个常数。

 

/ / 原来实行浮动的电脑上

 。对于该系统，下面的值

 / / 设置为2.92E-11，只是略大于

 / / 1 /（2 ^ 35），这是2.91E-11。对于我的英特尔系统，尾数

 / / 双精度浮点数是48位，所以

 / / 值设置为略大于1 /（2 ^ 44）。1 /（^ 44）

 / / 计算结果为5.68E-14，所以值5.69E-14是用在这里。

为什么稀疏的容器用于向量和矩阵。

 

在20世纪70年代后期，我实现了这个算法在Fortran的电路分析程序。该阵列是硬编码的大小。因此，要解决1000 1000系统的方程需要两个矩阵，有1000 项，或一百万个条目！多年以后，我重新编码，这在C语言中，再次与硬编码的大小。大多数现实世界的问题，要求矩阵大小远远小于1000 1000，或矩阵是稀疏的。电路分析程序通常需要大约5每个方程中，其中每个词对应的一列“组成的”矩阵。所以，一个1000 1000矩阵这样的问题会只有1000 5星，或5000的非零项。因此，稀疏容器将只有5000双精度值存储，1000 1000，而一个完整的矩阵将需要一百万双精度值，或尽可能多值的200倍！ 

 

对于非常大的问题，节省空间巨大，值得在运行时的性能退化。

 

另外，我意识到，这是很容易实现稀疏的容器和算法，将其转换为使用固定大小的数组，而做相反的是大量的工作。所以，有人可以转换使用了大量的空间，并有可能更快。随着现代处理器的高速缓存中，根据总线的速度和处理器体系结构，使得该算法使用了大量的内存，可以使算法的速度较慢，即使当执行的指令数是由更小。

 

使用代码 

 

创建一个文件，该文件只包含方程早在这篇文章中提到的格式，或使用提供的文件equations.txt的。输入：

 

SolveLinearEquations equations.txt

该计划将输出变量名和值按字母顺序排序的列表。对于文件equations.txt，输出将是： 

 

Linear Equation Solver – Version 2.01

Copyright (C) William Hallahan 2001-2013.

Ann = 2

Joe = 8

Mary = 12

Rita = 18

Tom = 70

 

总结

 

只有的ASCII构建支持Windows。字符串类型类不支持Unicode，但大部分其他的代码将被移植。最困难的代码端口将输入文件的代码，使用ofstream的。虽然这是可能的，但它需要更多的工作，使其跨平台移植。

 

我还没有测试在g+ +编译器中的代码SparseArray.h MatrixPackage.cpp（H）在Linux上使用。我预计，如果代码不编译和在Linux，使其工作所需的改变将是最小的和简单的。

<!--EndFragment-->