任意子空间方法 最小残向量 运算步骤 给定M,b并且一组搜索方向{而…而 1)通过将Ms正交化生成p for j=0 to k-1 P=w 如)(M 2)解x计算r的最小值 ()=( ()(M)=(Mp)( SMA-HPC C2003 MIT
给定M，b并且一组搜索方向 1）通过将 正交化生成 for j＝0 to k－1 2）解 计算r 的最小值 { } 0 1 , , w wk− ⋅⋅⋅ G G Mw sj ′ j p s G ′ 任意子空间方法 SMA-HPC ©2003 MIT 最小残向量 运算步骤 ( ) ( ) ( )( ) 1 0 T k j i j j T i i i i Mw Mp p w p Mp Mp − = = −∑ ( ) ( ) ( )( ) ( ) ( ) ( )( ) 0 1 1 0 0 T T i k k i i k T T i i i i ii ii r Mp r Mp x p p Mp Mp Mp Mp − − = = = = ∑ ∑ k x
任意子空间方法 最小残向量 图示计算步骤 1)正交化M,s 2)解计算r的最小值 MpI 自000 SMA-HPC C2003 MIT
1）正交化 2）解计算r 的最小值 任意子空间方法 SMA-HPC ©2003 MIT 最小残向量 图示计算步骤 Mw sj ′
任意子空间方法 最小化算法 ro=b-Axo for j=0 to k-1 for i=0 to j-1 n←n()()2正交搜索方向 P P 标准化向量 柳p)(M )(4)n更新结果 =r+()()4更新残向量 SMA-HPC C2003 MIT
for j＝0 to k－1 for i＝0 to j-1 正交搜索方向 标准化向量 更新结果 更新残向量 0 0 r b Ax = − 任意子空间方法 SMA-HPC ©2003 MIT 最小化算法 j j p w= ( ) ( ) T j j j ii p ← − p Mp Mp p ( )( ) 1 j j T j j p p Mp Mp ← ( ) ( ) 1 T j jj j j x x r Mp p + = + ( ) ( ) 1 T j jj j j r r r Mp Mp + = +
任意子空间方法 子空间的选择 标准 选择而,而的标准 对所有在空间n…,中的 任意3,b-Mb->aM的值都很小 当k<N时b≈在向量空间{ 种选择,单位向量,x∈{2…向量空间 如果k=N进行QR分解 如果k<N情况会很糟糕 SMA-HPC C2003 MIT
选择 的标准 对所有在空间 中的 任意 ， 的值都很小 当 时 在向量空间 一种选择，单位向量， 向量空间 如果k＝N进行QR分解 如果k<N情况会很糟糕 0 1 {,, } w wk− ⋅⋅⋅ G G i α′s 1 0 k k i i i b Mx b Mw α − = = − −∑ G 任意子空间方法 SMA-HPC ©2003 MIT 子空间的选择 标准 k N ≺≺ 1 A b− ≈ { 1, } k k x ee ∈ ⋅⋅⋅ G G 0 1 , , w wk− ⋅⋅⋅ G G 0 1 {,, } w wk− ⋅⋅⋅ G G
任意子空间方法 子空间的选择 传统方法 求()=xM-xb的最小值,其中假设M=M(对称 矩阵)并且xM>0 Vf(x)=Mx-b=x=Mb推导出x最小化f 取向量空间间可=/()f(x 这便是f的最快下降方向,但f并不是残余值。 这种方法不能用于非对成矩阵,和不满足xMx>0 的情况 SMA-HPC C2003 MIT
求 的最小值，其中假设 （对称 矩阵）并且 推导出 x最小化f. 取向量空间 这便是 f的最快下降方向，但 f并不是残余值。 这种方法不能用于非对成矩阵，和不满足 的情况 ( ) 1 2 T T f x x Mx x b = − 任意子空间方法 SMA-HPC ©2003 MIT 子空间的选择 传统方法 T M = M 0 T x Mx > ( ) 1 x f x Mx b x M b− ∇ = −⇒ = { } { ( ) ( ) } 0 1 0 1 ,, ,, k w w fx fx kx x − − ⋅⋅⋅ = ∇ ⋅⋅⋅ ∇ G G 0 T x Mx >