Lab 3 - 实现稀疏矩阵以及 Gauss-Seidel 迭代法

本次实验内容为课程作业，计算成绩。你需要将 C++ 源代码、可执行程序（注明运行环境）和实验文档 上传至学在浙大，并将压缩包命名为lab3-学号-姓名.rar/zip。

本次作业提交截止时间：2024 年 3 月 31 日 23:59:59，逾期将要扣分。

编程语言

请使用 C++ 语言作为编程语言。

稀疏矩阵

本实验要求自行实现一种稀疏矩阵。推荐的稀疏矩阵存储方式包括：

1. Compressed Row Storage (CRS)
2. Compressed Sparse Column (CSC)
3. 其他形式的稀疏矩阵存储方式

同学们请基于 sparse.h 实现 Sparse 类，并在实验报告中明确指出自己实现的稀疏矩阵方式。要求保证实现的 Sparse 类至少具备以下的几种最基本的 public 成员函数：

1. at(row, col): 根据row和column的系数来查询矩阵里面的元素的数值，即查询矩阵 A 的元素 A[row][col]
2. insert(val, row, col): 将 val 替换/插入到 (row, col) 这个位置去
3. initializeFromVector(rows, cols, vals): 根据向量来初始化一个稀疏矩阵。其中 rows, cols, vals 皆为等长度的向量。rows 里面存的是行系数，cols 里面存的是列系数，vals 里面存的是数值。例如，vals[i] 对应的就是 A[rows[i]][cols[i]] 的值
4. 其余的基本功能可以参考Matlab里面的 sparse 函数，或者 Eigen Library 里面的 Sparse Matrix 的介绍。

为了便于同学们的实现，对矩阵做出以下约定：

• 矩阵的非零元素的数量少于 int
• 矩阵元素的精度在 1e-10 以内，即如果一个矩阵元素的绝对值小于 1e-10，则可以认为它就是 0

备注：关于 CRS 与 CSC 的实现实现方式可以参考下面的网站：

• http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csr_matrix.html
• http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csc_matrix.html
• http://en.wikipedia.org/wiki/Sparse_matrix
• http://eigen.tuxfamily.org/dox/group__TutorialSparse.html

此外，有兴趣的同学也可以尝试将自己的实现与 Eigen Library 的 Sparse Matrix 进行比较，看是自己的实现比较高效还是 Eigen Library 的实现比较高效。

稀疏矩阵的 Gauss-Seidel 迭代法

本实验要求在自己实现的稀疏矩阵的表达的基础上，实现 Gauss-Seidel 方法，用于求解大规模的稀疏线性方程组。

关于 Gauss-Seidel 方法的介绍已经在课件中进行了详细的介绍。请同学们参照课件，基于 hw3_solve.h 所定义的接口 Gauss_Seidel(A, b, error) 进行代码的编写，其中有

• A: 线性方程组 Ax=b 的系数矩阵
• b: 参照线性方程组 Ax=b
• error: 当前后两次迭代的解向量之差的无穷范数小于等于 error 时，认为已经收敛并停止迭代

$$\Vert x_{k+1}-x_k{\Vert }_{\infty }⩽\text{error}$$

此外还有一些额外的辅助资料提供参考：

• http://mathworld.wolfram.com/Gauss-SeidelMethod.html
• http://en.wikipedia.org/wiki/Gauss%E2%80%93Seidel_method

作为验证实现的正确性，这里给出一个小的Test Case:
$A=\begin{pmatrix} 10 & -1 & 2 & 0 \\ -1 & 11 & -1 & 3 \\ 2 & -1 & 10 & -1\\ 0 & 3 & -1 & 8 \end{pmatrix}$
$b=(6,25,-11,15)^T$
求解得到的结果应该为：

x = [1, 2, -1, 1];

Bonus: 实现共轭梯度法

有余力的同学可以参考相关资料实现共轭梯度法求解线性方程组。

维基百科上有比较详细的共轭梯度法的介绍：Conjugate gradient method

希望完成该 bonus 的同学请基于 hw3_solve.h 所定义的接口 Conjugate_Gradient(A, b, error, kmax) 进行代码的编写，其中有

• A: 线性方程组 Ax=b 的系数矩阵
• b: 参照线性方程组 Ax=b
• error: 当残差 r=b-Ax 的 2 范数的平方小于等于 error 时，认为已经收敛而停止迭代
• kmax: 迭代的最大次数

$$\Vert r{\Vert }_2^2=\Vert b-Ax{\Vert }_2^2⩽\text{error}$$

自主测试

可以利用 main.cpp 进行一个最基本的测试，验证自己的稀疏矩阵的实现是否成功、G-S 迭代（和共轭梯度法，可选）的求解是否正确。这个样例程序只是进行了最基本的测试，批改时会进行更复杂的测试，也欢迎大家提交自己补充的测试代码。

可以使用 makefile 编译，给出一个参考的 makefile 文件。

在这里重新列出所有提供的模板代码：

• 稀疏矩阵类接口：sparse.h
• 样例测试程序：main.cpp
• G-S 迭代和共轭梯度法函数接口：hw3_solve.h
• makefile