西安交通大学计算方法A上机作业.pdf

《西安交通大学计算方法A上机作业.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算方法（A）大作业姓名：班级：专业：学号：共轭梯度法一、算法原理共轭梯度法是把求解线性方程组的问题转化为求解一个与之等价的二次函数极小化的问题，因此从任意给定的初始点出发，沿一组关于矩阵A的共轭方向进行线性搜索，在无舍入无差的假定下，最多迭代n(其中n为矩阵A的阶数）次就可求得二次函数的极小点，也就求得了线性方程组Ax=B的解。下述定理给出了求系数矩阵A是对称正定矩阵的线性方程组Ax=b的解与求二1??次函数?(?)=???−??极小点的等价性。2定理3.4.1设A是n阶对称正定矩阵，则?∗是方程组Ax=b的解的充分必要条∗1??件是?是二次函数?(?)=???−??的极小点，即2??∗=

2、?⟺?(?∗)=????(?)?∈??证明：充分性.设?∗是f(x)的极小点，则由无约束最优化问题最优解的必要条件知??(?∗)=??∗−?即?∗是方程组Ax=b的解。必要性.若?∗是方程组Ax=b的解，即A?∗=b，注意到A是对称正定矩阵，故∀x∈??有11?(?)−?(?∗)=????−???−????∗+???∗221(???∗?∗)−?∗?∗?∗=??−2??+?????+??21(??∗?∗?∗)−(??∗?∗=??−2(??)?+???−?)?21(?−?∗)?∗=?(?−?)2≥0即?∗是f(x)的极小点，进而由A是正定矩阵知，?∗是f(x)的最小点。证毕。共轭梯度法在形式上具

3、有迭代法的特征，在给定初始值情况下，根据迭代公式：?(?+1)=?(?)+??(?)?产生的迭代序列?(1),?(2),?(3)…在无舍入误差假定下，最多经过n次迭代，就可求得f(x)的最小值，也就是方程Ax=b的解。共轭梯度法中关键的两点是，确定迭代格式中的搜索向量?(?)和最佳步长??（?≥0）。实际上，搜索方向d(?)是关于矩阵A的共轭向量，在迭代中逐步构造之。?步长?的确定原则是给定迭代点?(?)和搜索方向d(?)后，要求选取非负实数?，使??得f(?(?)+?d(?))达到最小，即选择?，满足???(?(?)+??(?))=????(?(?)+??(?))?0≤?1下面首先导出最佳

4、步长k的计算公式。假设迭代点?(?)和搜索方向d(?)已经给定，?可以通过一元函数?∅(?)=?(?(?)+??(?))的极小化???∅(?)=?(?(?)+??(?))0≤?来求得，根据多元复合函数的求导法则得:(?)(?)?(?)∅́(?)=??(?+??)?令(?)(?)?(?)(?)(?)?(?)0=∅́(?)=??(?+??)?=[?(?+??)−?]?=(??(?)−?+???(?))??(?)=(−?(?)+???(?))??(?)其中?(?)=?−??(?)。由此解得最佳步长?(?)??(?)??=?(?)???(?)(3.4.4)下面确定搜索方向d(?)。给定初始向量?(

5、0)后，由于负梯度方向是函数下降最快的方向，故第1次迭代取搜索方向?(0)=?(0)=−??(?(0))=?−??(0)。令?(1)=?(0)+??(0)0?(0)??(0)(1)(1)其中?0=?(0)???(0)。第2次迭代时，从?出发的搜索方向不再取?，而是选取?(1)=?(1)+?0?(0)，使得?(1)与?(0)是关于矩阵A的共轭向量，即要求?(1)满足(?(1),??(0))=0，由此可求得参数?:0?(1)???(0)?0=−?(0)???(0)然后从?(1)出发，沿?(1)进行搜索得到?(2)=?(1)+??(1)1其中?1由式（3.4.4）确定。一般地，设已经求出?(?+1

6、)=?(?)+???(?)，计算?(?+1)=?−??(?+1)。令?(?+1)=?(?+1)+???(?)，选取??，使得?(?+1)和?(?)是关于A的共轭向量，即要求?(?+1)满足(?(?+1),??(?))=0。由此可得:?(?+1)???(?)??=−?(?)???(?)从而确定了搜索方向?(?+1)。2综上所述，共轭梯度法的计算公式为?(0)=?(0)=?−??(0),?(?)??(?)??=?(?)???(?),?(?+1)=?(?)+??(?),??(?+1)=?−??(?+1),?(?+1)???(?)??=−?(?)???(?),?(?+1)=?(?+1)+??(?).

7、?利用定理3.4.3，可以将??和??的表达式简化为?(?)??(?)??=?(?)???(?)?(?+1)??(?+1)??=?(?)??(?)定理3.4.3设分别是共轭梯度法中产生的非零残向量和搜索方向，则（1）(?(?),?(?−1))=0（2）(?(?),?(?))=(?(?),?(?))（3）?(0),?(1),…,?(?)(k≤n−1)是正交向量组，?(0),?(1),…,?(?)(k≤n−1)是