共轭方向法教学讲义.docVIP

&3.6 共轭方向法引言本节之后的方法大多属于共轭方向法。3.6.1 共轭方向的概念若两个向量，满足如下关系： (3-6-1)其中，a为的对称正定阵，则称x和y是关于a共轭的，x和y称之为共轭方向。注意：若，则称x与y正交。实际上，共轭是正交的推广。例1： 有两个二维向量，判断与是否关于a共轭，是否正交？解：，因此，与关于a共轭。，因此，与正交。3.6.2 共轭向量的概念如果有m个n维向量，满足 (3-6-2)则称这m个向量是a的共轭向量。如果维单位阵，则称这m个为正交向量。3.6.3 共轭向量的几何意义设目标函数为 (3-6-3)其中，a为阶的对称正定阵。的梯度为： (3-6-4)设从某点出发，沿方向进行搜索得到的极小点，则有 (3-6-5)设从某点出发，仍沿方向进行搜索得到的极小点，则有 (3-6-6)式(3-6-6)减(3-6-5)，可得： (3-6-7)这说明与是关于a共轭的。3.6.4 共轭方向法的原理考虑m个n维向量，满足，则这m个向量一定是线性无关的。用反证法。假设线性相关，则一定存在一组不全为0的一组数，满足 (3-6-8)则有 (3-6-8)其中，。因此有：，但这与原假设不符。因此，一定可以得出线性无关的结论。注意：在n维空间中的任意向量，均可以用n个线性无关的n维向量表示，也可以说，n维是由n个线性无关的n维向量张成的（此处还差一步：正交化）。那么，设目标函数的极小点为，初始点为，为关于的n个共轭向量，则有： (3-6-9)将式(3-6-9)写成差分格式： (3-6-10)式中，表示经过次迭代后，。该式表明，为目标函数沿方向的一个极小点，则有： (3-6-11)即 (3-6-12)即可推导出： (3-6-13)式(3-6-13)表明，如果能够构造出一系列共轭向量，则可以求出，那么经过k步迭代，可以求得。对于二次函数，。例2 求解解： 首先，构造二次型： 即，。 取，取第0个搜索方向为：，则根据式(3-6-13)，有：由于与关于a共轭，则有上式与无穷多解，我们任取，则3.6.5 构造共轭方向的一般方法在n维空间中，已知有n个单位向量：第i个分量为则n个共轭方向可以这样确定： (3-6-14)其中，为待定系数。由于，和关于a共轭，因此，即 (3-6-15)可得 (3-6-16)继续，可以构造 (3-6-17)考虑，即 (3-6-18)由于，式(3-6-19)化简为： (3-6-19)即可推出： (3-6-20)同时考虑，即 (3-6-21)同理，由于，式(3-6-21)化简为： (3-6-22)因此有 (3-6-23)特别注意：由于不仅与关于a共轭，同时也与关于a共轭，所以的表达式和在时的表达式(3-6-16)是不同的。由此可以类推，可得： (3-6-24)例题，见matlab程序3.6.6 共轭梯度法共轭梯度法是一种构造共轭方向的方法。任取一个初始点，经过n次迭代，得到n个点，利用这n个点的梯度方向可以构造一组共轭方向。具体做法为：设有一个n维函数，用梯度法经过次迭代，即可以得到这个迭代点，这些点所对应的函数的梯度为。即可以构造一组共轭方向： (3-6-25)可以证明，按照式(3-6-25)构造的n个方向是关于a共轭的。然后，即可按下式计算： (3-6-26)如果是二次函数，那么经过n次迭代后必然可以收敛到极小点。如果按这样的算法计算，则一定需要求得函数的海赛矩阵a，在实用性上存在困难，并且加大了计算负担，因此我们需要想法避免在计算过程中出现a。现在我们对以上公式作一些适当的简化。设有一个二次函数，在进行极小化过程中，迭代公式为： (3-6-27)设为迭代点的梯度，并且令： (3-6-28)这是前后两相邻迭代点的梯度之差。则有： (3-6-29)对n个共轭方向，有：故 (3-6-30)可见在迭代过程中，前后两次迭代点的梯度之差与其他任一共轭方向是正交的。即 (3-6-31)设，则：(3-6-32)又因为式(3-6-31)，故有 (3-6-33)在此式中，是迭代点处的梯度，而是沿方向搜索新得之点。在梯度法中我们已经证明了点处的梯度方向与求得点时的搜索方向是正交的，所以有： (3-6-34)则有： (3-6-35)这就是说，某迭代点的梯度方向与此点以前各点的搜索方向均是正交的。我们再回到构造n个共轭方向的问题上来。已知式(3-6-25)：那么，对于第r次迭代（其中），则有 (3-6-36)所以 (3-6-37)此处。将上式等号两边同时左乘，得到 (3-6-38)又因为，而，所以在上面和式中每一项均为零，即 (3-6-39)所以 (3-6-40)根据式(3-6-28)，已知：，所以 (3-6-41)将式(3-6-41)等号两边同时左乘，得： (3-6-42)考虑当时，有 所以 (3-6-43)根据式(3-6-25)， ，且所以当时，均有：，仅当，。所以有： (3-6-44)再对此式作进一步的简化： (3-6-45)代入上面(3-6-25)式，可得： (3-6-46)将式(3-6-46)两边分别左乘得： (3-6-47)因为和是a共轭方向所以 由前已知所以式(3-6-47)右边各项中除两项不等于零外，其余均等于零，于是有： (3-6-48)由此即可得到求的公式如下： (3-6-49)此式中不含海塞矩阵a，因而免去了许多繁琐的计算，而且不用担心a的正定及非奇异问题，对初始点的选择无任何限值了。从以上分析，我们得出了共轭梯度法的计算步骤及迭代公式如下：1) 任选初始点，则： (3-6-50)2) 计算： (3-6-51)其中，。则可构造n个共轭方向。3) 对于每个迭代点及每个共轭方向，求，使。4）按收敛判断准则判断是否为极小点，若是，则可以停机，