Aller au boulot

Conjugate Descent

Definition

Let $Q\in {\mathbb{R}}^{n\times n}$ be a symmetric matrix. $v_i,v_j\in {\mathbb{R}}^n,v_i\ne v_j\ne 0$ are Q-orthogonal w.r.t. $Q$ if

$$v_i^{T}Q{v}_j=0.$$

Proposition

Let $Q$ be positive definite. If $v_1,v_2,\dots ,v_k$ are Q-orthogonal, then they are linear independent.

Proof

If $v_k={\alpha }_1{v}_1+\cdots +{\alpha }_{k-1}{v}_{k-1}$, then $$v_k^{T}Q{v}_k=v_k^{T}Q({\alpha }_1{v}_1+\cdots +{\alpha }_{k-1}{v}_{k-1})={\alpha }_1{v}_k^{T}Q{v}_1+\cdots +{\alpha }_{k-1}{v}_k^{T}Q{v}_{k-1}=0$$ controversy with postive definite.

Proposition

Let $v_1,v_2,\dots ,v_n\in {\mathbb{R}}^n$ vectors Q-orthogonal, $x_0\in {\mathbb{R}}^n$ be arbitrary starting point.

Assume

$${\alpha }_k=-\frac{g_k^T{v}_k}{v_k^{T}Q{v}_k}$$

$$x_{k+1}=x_k+{\alpha }_k{v}_k$$

$$g_k=Q{x}_k-b$$

then $x_n$ is the solution of $Qx=b$.

$$\underset{x\in {\mathbb{R}}^n}{\min }\frac{1}{2}{x}^{T}Qx-b^{T}x$$

Matrix $Q\in {\mathbb{R}}^{n\times n}$ is positive definite.

$$Qx=b,x\in {\mathbb{R}}^n$$

Let $v_1,v_2,\dots ,v_n\in {\mathbb{R}}^n$ vectors Q-orthogonal, which is linear independent, then $\forall x^{\ast }\in {\mathbb{R}}^n$ there exist ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n\in \mathbb{R}$,

$$x^{\ast }=\sum _{i=1}^n{\alpha }_i{v}_i={\alpha }_1{v}_1+{\alpha }_2{v}_2+\cdots +{\alpha }_n{v}_n$$

$$v_i^{T}Q{x}^{\ast }=v_i^{T}Q({\alpha }_1{v}_1+{\alpha }_2{v}_2+\cdots +{\alpha }_n{v}_n)={\alpha }_i{v}_i^{T}Q{v}_i$$

$${\alpha }_i=\frac{v_i^{T}Q{x}^{\ast }}{v_i^{T}Q{v}_i}=\frac{v_i^{T}b}{v_i^{T}Q{v}_i}$$

$$x^{\ast }=\sum _{i=1}^n{\alpha }_i{v}_i=\sum _{i=1}^n\frac{v_i^{T}b}{v_i^{T}Q{v}_i}{v}_i$$

Proposition

Let $x_0\in {\mathbb{R}}^n$ arbitrary,

$$\begin{array}{rl}{v}_0& =b-Q{x}_0\\ {\alpha }_k& =-\frac{g_k^T{v}_k}{v_k^{T}Q{v}_k}\\ x_{k+1}& =x_k+{\alpha }_k{v}_k\\ g_k& =Q{x}_k-b\\ v_{k+1}& =-g_{k+1}+{\beta }_k{v}_k\\ {\beta }_k& =\frac{g_{k+1}^{T}Q{v}_k}{v_k^{T}Q{v}_k}\end{array}$$