西京学院数学软件实验任务书
【实验课题】
线性方程组的最速下降法与共轭梯度法
【实验目的】
学习和掌握线性方程组的最速下降法与共轭梯度法的求解方法。
【实验内容】
1、问题重述
对于线性方程组AX=b，即：
⎧a11x1+a12x2+ +a1nxn=b1⎪ax+ax+ +ax=b⎪2112222nn2
（1） ⎨
⎪
⎪⎩an1x1+an2x2+ +annxn=bn
其中，A=(aij)n⨯n为对称正定矩阵，b=(bi)n⨯1，如何熟练
地运用最速下降法与共轭梯度法的求解线性方程组。 2、方法理论
在求解线性方程组之前，首先用内积将问题转化为函数问题。 2.1 最速下降法
最速下降法是一种运用梯度与极值的性质，综合数值计算方法寻找局部极值。
基本思想：任一点的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法。
具体步骤：
1、搜索方向：dk=-∇f(xk)，即最速下降方向。
2、搜索步长：λk取最优步长，即满足：
f(xk+λkdk)=minf(xk+λdk)
λ
Step 1 给定初始点x0∈Rn，允许误差ε≥0，令k=1。 Step 2 计算搜索方向dk=-∇f(xk)。
Step 3 若 dk ≤ε，则xk为所求的极值点，否则，求解最优步长λk，使得f(xk+λkdk)=minf(xk+λdk)。
λ
Step 4 令xk+1=xk+λkdk，k=k+1
最速下降方向是反映了目标函数的局部性质，它只是局部目标函数值下降最快的方向。
2.2 共轭梯度法
对于 min
f(x)=
1T
xAx+bTx 2
其中，x0∈Rn，A是对称正定矩阵。
基本思想：将共轭性与最速下降法相结合利用已知迭代点
的梯度方向构造一组共轭方向，并沿此方向搜索，求出函数的极小值。
具体步骤：
Step 1 取初始点x(
0)
，取第一次搜索方向为
)0
d(0=-∇f(x)(。
Step 2 设已求得x(k+1)，若∇f(x(k+
1)
)≠，令0
k+1)
g(x)=∇f((x，则下一个搜索方向)
d(k+1)=-gk+1+βkd(k) （1）
由于d(k+1)与d(k)关于A共轭，所以给（1）两边同时乘以d(k)A，即：
T
d(k)Ad(k+1)=-d(k)Agk+1+βkd(k)Ad(k)=0
d(k)TAgk+1
解得：βk=(k)T （2） (k)
dAd
Step 3 搜索步长的确定，已知迭代点x(k)，和搜索方向
λ
TTT
d(k)，确定步长λk，即：min
f(x(k)+λd(k))
记
φ(λ)=f(x(k)+λd(k))，
令
φ'(λ)=∇f(x(k)+λd(k))Td(k)=0
既有：[A(x(k)+λd(k))+b]Td(k)=0
令 gk=∇f(x(k))=Ax(k)+b 既有：[gk+λAd(k)]Td(k)=0
Tgkd(k)
解得：λk=-(k)T(k)
dAd
共轭梯度法是对最速下降法的一种改进，减少了迭代次数
从而提高了程序运行效率。
程序：
%%%%%%%%%%%%%%%%%%%最速下降法%%%%%%%%%%%%%%%%%% function [x,k]=fast(A,b)
esp=input('ÇëÊäÈëÔÊÐíÎó²îesp='); N=input('ÇëÊäÈë×î´óµü´ú´ÎÊýN='); x0=input('ÇëÊäÈë³õʼֵx0='); k=0; tol=1;
while tol>=esp r=b-A*x0;
q=dot(r,r)/dot(A*r,r); x=x0+q*r; k=k+1;
tol=norm(x-x0); x0=x if k>=N
disp('µü´ú´ÎÊýÌ«¶à£¬¿ÉÄܲ»ÊÕÁ²£¡'); return; end end x k
%%%%%%%%%%%%%%%%%%%共轭梯度法%%%%%%%%%%%%%%%%%%% function [k,x]=C_G(A,b)
esp=input('请输入最大误差='); x0=input('请输入初值x0='); k = 0 ;
r0 = b-A*x0; %Çó³ödangqianÌÝ¶È while norm(r0)>esp r0 = b -A*x0; k = k + 1 ; if k==1
p0 = r0 ; else
lamda=(r0'*r0)/(p0'*A*p0);
r1 = r0 - lamda*A*p0 ;
p0=r0+(r0'*r0)/(r1'*r1)*p0; x1 = x0 + lamda*p0; x0=x1; r0=r1; end end x=r0; k; end
西京学院数学软件实验任务书
【实验课题】
线性方程组的最速下降法与共轭梯度法
【实验目的】
学习和掌握线性方程组的最速下降法与共轭梯度法的求解方法。
【实验内容】
1、问题重述
对于线性方程组AX=b，即：
⎧a11x1+a12x2+ +a1nxn=b1⎪ax+ax+ +ax=b⎪2112222nn2
（1） ⎨
⎪
⎪⎩an1x1+an2x2+ +annxn=bn
其中，A=(aij)n⨯n为对称正定矩阵，b=(bi)n⨯1，如何熟练
地运用最速下降法与共轭梯度法的求解线性方程组。 2、方法理论
在求解线性方程组之前，首先用内积将问题转化为函数问题。 2.1 最速下降法
最速下降法是一种运用梯度与极值的性质，综合数值计算方法寻找局部极值。
基本思想：任一点的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法。
具体步骤：
1、搜索方向：dk=-∇f(xk)，即最速下降方向。
2、搜索步长：λk取最优步长，即满足：
f(xk+λkdk)=minf(xk+λdk)
λ
Step 1 给定初始点x0∈Rn，允许误差ε≥0，令k=1。 Step 2 计算搜索方向dk=-∇f(xk)。
Step 3 若 dk ≤ε，则xk为所求的极值点，否则，求解最优步长λk，使得f(xk+λkdk)=minf(xk+λdk)。
λ
Step 4 令xk+1=xk+λkdk，k=k+1
最速下降方向是反映了目标函数的局部性质，它只是局部目标函数值下降最快的方向。
2.2 共轭梯度法
对于 min
f(x)=
1T
xAx+bTx 2
其中，x0∈Rn，A是对称正定矩阵。
基本思想：将共轭性与最速下降法相结合利用已知迭代点
的梯度方向构造一组共轭方向，并沿此方向搜索，求出函数的极小值。
具体步骤：
Step 1 取初始点x(
0)
，取第一次搜索方向为
)0
d(0=-∇f(x)(。
Step 2 设已求得x(k+1)，若∇f(x(k+
1)
)≠，令0
k+1)
g(x)=∇f((x，则下一个搜索方向)
d(k+1)=-gk+1+βkd(k) （1）
由于d(k+1)与d(k)关于A共轭，所以给（1）两边同时乘以d(k)A，即：
T
d(k)Ad(k+1)=-d(k)Agk+1+βkd(k)Ad(k)=0
d(k)TAgk+1
解得：βk=(k)T （2） (k)
dAd
Step 3 搜索步长的确定，已知迭代点x(k)，和搜索方向
λ
TTT
d(k)，确定步长λk，即：min
f(x(k)+λd(k))
记
φ(λ)=f(x(k)+λd(k))，
令
φ'(λ)=∇f(x(k)+λd(k))Td(k)=0
既有：[A(x(k)+λd(k))+b]Td(k)=0
令 gk=∇f(x(k))=Ax(k)+b 既有：[gk+λAd(k)]Td(k)=0
Tgkd(k)
解得：λk=-(k)T(k)
dAd
共轭梯度法是对最速下降法的一种改进，减少了迭代次数
从而提高了程序运行效率。
程序：
%%%%%%%%%%%%%%%%%%%最速下降法%%%%%%%%%%%%%%%%%% function [x,k]=fast(A,b)
esp=input('ÇëÊäÈëÔÊÐíÎó²îesp='); N=input('ÇëÊäÈë×î´óµü´ú´ÎÊýN='); x0=input('ÇëÊäÈë³õʼֵx0='); k=0; tol=1;
while tol>=esp r=b-A*x0;
q=dot(r,r)/dot(A*r,r); x=x0+q*r; k=k+1;
tol=norm(x-x0); x0=x if k>=N
disp('µü´ú´ÎÊýÌ«¶à£¬¿ÉÄܲ»ÊÕÁ²£¡'); return; end end x k
%%%%%%%%%%%%%%%%%%%共轭梯度法%%%%%%%%%%%%%%%%%%% function [k,x]=C_G(A,b)
esp=input('请输入最大误差='); x0=input('请输入初值x0='); k = 0 ;
r0 = b-A*x0; %Çó³ödangqianÌÝ¶È while norm(r0)>esp r0 = b -A*x0; k = k + 1 ; if k==1
p0 = r0 ; else
lamda=(r0'*r0)/(p0'*A*p0);
r1 = r0 - lamda*A*p0 ;
p0=r0+(r0'*r0)/(r1'*r1)*p0; x1 = x0 + lamda*p0; x0=x1; r0=r1; end end x=r0; k; end