下载文档原格式
共轭梯度法原理共轭梯度法是线性代数中一种求解稀疏矩阵下的大规模线性方程组的方法。
它的优点是它具有迭代次数小的特点，同时也能得到比较准确的解。
共轭梯度法基于梯度下降法，但是避免了梯度下降法的缺点。
梯度下降法每一次迭代都需计算整个向量的梯度，这在高纬度数据中非常复杂，同时使用步长较大时又容易产生来回震荡的现象。
共轭梯度法的优点是在每一次迭代都会寻找一个与上次方向不同的方向，这点可以消除梯度下降法的缺陷。
令A为若干个线性矩阵的乘积，如果我们要解矩阵方程Ax=b，其中b是已知向量，求解的x向量是未知向量。
首先，我们可以用梯度下降法求出一个初值向量x0，称之为迭代初始值。
然后，我们可以利用高斯打乘法和高斯消元得到向量P，并设向量R0=Ax0-b，然后再设P逆矩阵为Pt。
共轭梯度法迭代的主要步骤如下：1. 根据目标函数和梯度函数确定初值x0；2. 初始化残差向量r0=b-Ax0，并设置迭代数k=0；3. 设置搜索方向向量p0=r0；4. 使用一维搜索方法（如Armijo步长准则）寻找最优步长αk；5. 将搜索方向向量移动到新的位置：xk+1=xk+αkp，计算新的残差rk+1=rk+αkAp；6. 如果rk+1=0或者迭代次数已达到设定值，则停止迭代；否则：7. 确定下一个搜索方向pk+1，并重复步骤4-6直到满足收敛条件。
共轭梯度法迭代的优点是每一步都在原解空间的一个线性子空间中求解，因此不需要保存全部解向量，从而大大减少了计算量和存储空间，特别适用于高纬度的线性方程组的求解。
在参数优化、图像处理和物理模拟等领域中广泛应用。
在参数优化中，共轭梯度法可以加速大规模函数的梯度计算，从而加快参数搜索的速度；在图像处理中，共轭梯度法常用于求解稀疏线性系统，例如图像压缩、图像去噪和图像恢复等；在物理模拟中，共轭梯度法可以用于求解偏微分方程组、流体力学问题和计算机视觉等领域。
实验1 共轭梯度法求解线性方程组1.算法原理2.程序框图3.程序使用说明。
本程序使用MATLAB来求解线性方程组Ax b源程序文件“gongetidu1.m”为共轭梯度法源程序，x为方程组的解，k为迭代次数，A为方程组的系数矩阵，b为方程组的右端项，ep为精度。
定义A, b，ep后，在命令窗口输入[x,k] = gongetidu1(A,b,ep)，回车后即可算出方程组的解和迭代次数。
源程序文件“gongetidu2.m”为共轭梯度算例3.2中构造A，b矩阵的程序。
定义阶数n的数值后，在命令窗口输入[A,b] = gongetidu2(n)即可算出A, b矩阵。
4.算例计算结果此算例为课本113页计算实习3.2.首先，设定MATLAB的数值格式为“long”。
当n=100时，在命令窗口中输入“[A,b]=gongetidu2(100)”，回车后可得到A 和b的矩阵；假设精度ep = 10-3，然后在命令窗口输入“[x,k] = gongetidu1(A,b,10^-3)”即可算出方程组的解x和迭代次数k。
x=( 0.999999999999988,0.999999999999995,1.000000000000009，···0.9999 99999999997,0.999999999999998 )T（x向量一共有100个元素）k=49.同理，可以算出n=200,400的结果。
n=200时，同样假设精度ep = 10-3，结果为：x=( 0.999999999999974,1.000000000000023,0.999999999999935,···1.000000 000000029, 0.999999999999987)T （x向量一共有200个元素）k=99.n=400时，同样假设精度ep = 10-3，结果为：x=( 1.000000000000017,0.999999999999846,1.000000000000039,···0.99999999 9999881,1.000000000000062)T （x向量一共有400个元素）k=199。
利用共轭梯度法求解线性方程组翟莹1012205052在自然科学和工程技术中很多问题的解决常常归结为解线性方程组，而这些方程组的系数矩阵大致可分为两种:低阶稠密矩阵和大型稀疏矩阵。
而求解方程组的方法通常为直接法和迭代法。
直接法用于较低阶方程组的求解，效率较高；迭代法更适用于高阶方程组的求解，常用的经典迭代法有高斯-赛德尔迭代法和雅各比迭代法，但收敛效率较低；共轭梯度法（CG）以较高的收敛速度而经常被采用。
从理论上讲，一个n阶方程组最多迭代n 步就可求出精确解。
1 直接法直接法就是经过有限步算术运算，无需迭代可直接求得方程组精确解的方法。
但实际计算中由于舍入误差的存在和影响，这种方法也只能得到线性方程组的近似解，该方法是求解低阶稠密矩阵方程组的有效方法。
如Cramer法则，Gauss消元法及其变形（LU分解法、Cholesky 分解法、QR分解法）等。
Matlab中，用矩阵除法“/”或“\”直接求解线性方程组（见附录一），它是一个内部包含着许许多多的自适应算法，对超定方程用最小二乘法求解；对欠定方程因为它的解不唯一，Matlab给出所有解中范数最小的一个特解；对于三对角阵方程组，采用追赶法求解。
2 迭代法迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法。
该方法具有对计算机的存贮单元需求少，程序设计简单、原始系数矩阵在计算过程中不变等优点，是求解大型稀疏矩阵方程组的重要方法。
迭代法不是用有限步运算求精确解，而是通过迭代产生近似解逼近精确解。
如Jacobi迭代、Gauss-Seidel迭代、SOR迭代法等。
在科学研究和大型工程设计中提出的求解问题，经离散后，常常归结为求解形如Ax = b 的大型线性方程组，此时系数矩阵A和b是通过测量或其它方法得到的，但是在多数情况下方程可能是病态的，即A的条件数非常大。
此时，我们仍然用Matlab中的常规算法，得到的解则可能不是真解。
通常情况下，对系数矩阵A和方程的右端b作微小的扰动，再用上述方法求解，扰动后方程组的解与原方程组的解相差甚远。
共轭梯度法1. 算法原理求解一个系数矩阵为正定矩阵的线性方程组可通过求泛函)(x f 的极小值点来获得，进而可以利用共轭梯度法来求解。
共轭梯度法中关键的两点是，确定迭代格式)()()1(k k k k d x x α+=+中的搜索方向)(k d 和最佳步长k α。
实际上搜索方向)(k d是关于矩阵A 的共轭向量，在迭代中逐步构造之；步长k α的确定原则是给定迭代点)(k x 和搜索方向)(k d 后，要求选取非负数k α，使得)()()(k k k d x f α+达到最小，即选择0≥k α，满足)(min )()()(0)()(k k k k k d x f d x f kααα+=+≤。
设迭代点)(k x和搜索方向)(k d已经给定，k α可以通过一元函数)()()()(k k d xf g αα+=的极小化)()(min )()(0k k d xf g ααα+=≤来求得，所以最佳步长)()()()(k k k k k Addd r TT=α。
在给定初始向量)0(x 后，由于负梯度方向是函数下降最快的方向，故第1次迭代取搜索方向)0()0()0()0()(Ax b x f r d-=-∇==。
令)0(0)0()1(d x x α+=，其中)0()0()0()0(0Addd r TT=α。
第2次迭代时，从)1(x 出发的搜索方向不再取()1r，而是选取)0(0)1()1(d r d β+=，使得)1(d与()0d 是关于矩阵A 的共轭向量，即要求)1(d 满足()()()0,01=Ad d ，由此可求得参数)0()0()0()1(0-Ad d Ad r TT=β，然后从()1x 出发，沿方向)1(d进行搜索得)1(1)1()2(d x xα+=，其中1α已由上面k α的计算式获得。
一般地，设已经求出)()()1(k k k k d x x α+=+，计算)1()1(++-=k k Ax b r。
