武汉大学数学与统计学院：《数值分析》第二章 求解线性方程组的数值解法（2.3）共轭斜量法

2.3共轭斜量法 Conjugate Gradient Methods) 属于一种迭代法,但如果不考虑计算过程的舍入误 差,CG算法只用有限步就收敛于方程组的精确解

2.3 共轭斜量法 （Conjugate Gradient Methods) 属于一种迭代法，但如果不考虑计算过程的舍入误 差，CG算法只用有限步就收敛于方程组的精确解

Outline >Background > Steepest Descent > Conjugate Gradient

Outline ØBackground ØSteepest Descent ØConjugate Gradient

1 Background The min(max) problem min f(X X But we learned in calculus how to solve that kind of question

1 Background • The min(max) problem: • But we learned in calculus how to solve that kind of question! min f (x) x

real world” problem Connectivity shapes (isenburg,gumhold, gotsman) mesh=c=(v, e), geometry, What do we get only from C without geometry

“real world” problem • Connectivity shapes (isenburg,gumhold,gotsman) • What do we get only from C without geometry? mesh {C  (V, E), geometry}

Motivation-"real world problem first we introduce error functionals and then try to minimize them E(x∈R3)=2(x-x)|-) (i,j)∈E E,(x∈R3)=∑L(x)2 (x)=∑x i(i,j)∈E

Motivation- “real world” problem • First we introduce error functionals and then try to minimize them:   2 3 ( , ) ( ) 1 n s i j i j E E x x x        ( , ) 1 ( ) i j i i i j E L x x x d     3 2 1 ( ) ( ) n n r i i E x L x     

Motivation-"real world problem Then we minimize E(C, h)=argmin(1-h)E, (x)+E, (x) x∈R >High dimension non-linear problem Conjugate gradient method is maybe the most popular optimization technique based on what we'll see here

Motivation- “real world” problem ØThen we minimize: ØHigh dimension non-linear problem. ØConjugate gradient method is maybe the most popular optimization technique based on what we’ll see here.   3 ( , ) arg min 1 ( ) ( ) n s r x E C   E x E x          

Directional derivatives first. the one dimension derivative .1 -0.05 d -.1 40.15 dx

Directional Derivatives: first, the one dimension derivative: 

Directional derivatives Along the axes of(, y) y of(x, y) oX

x f x y   ( , ) y f x y   ( , ) Directional Derivatives : Along the Axes…

Directional derivatives In general direction v∈R21 of(x, y OV

v f x y   ( , ) 2 v R v 1 Directional Derivatives : In general direction…

Directional Derivatives 42024 of(, y) of(x, y) ay ax

Directional Derivatives x f x y   ( , ) y f x y   ( , )