数值分析作业 - 对称正定线性方程组的解法

数值分析

Problem 1

则该矩阵正定. Cholesky 分解:

回代求解:

先求解

再求解

Problem 2

共轭方向法

首先产生两个共轭方向

然后进行迭代

共轭梯度法

Problem 3

仍然基于 CUDA C++ 和 cuBLAS 实现两种算法. 算法实现参见 spd.cu.

对于问题 1 中的方程, 使用梯度下降法以及共轭梯度法进行求解:

Testing small matrix
Gradient descent did not converge in 50 iterations
0.99999221 1.99998272 -1.00000174
Gradient Descent: 23.11ms
Conjugate gradient finally converged in 3 iterations
1.00000000 2.00000000 -1.00000000
Conjugate Gradient: 2.086ms

观察到梯度下降法经过 50 次迭代达到设置的极限时, 仍然有较明显的误差, 而共轭梯度法只需很少的迭代即可收敛到精确解.

为了充分测试算法的性能, 通过下列方法构造大规模的测试数据:

使用区间内均匀随机数填充
确保至少是半正定
使用区间内均匀随机数填充

取 , 运行算法并比较求出的解与精确解的无穷范数

Testing large matrix with n = 1000
Gradient descent did not converge in 1500 iterations
Gradient Descent: 432.497ms
Norm: 0.20379112
Conjugate gradient finally converged in 1000 iterations
Conjugate Gradient: 389.31ms
Norm: 0.05191499

能注意到梯度下降法的迭代速度略快与共轭梯度法, 但是即使梯度下降法消耗了更长时间, 其精度仍不如共轭梯度法.

本文采用署名-相同方式共享 4.0 国际许可协议，转载请注明出处。