Content deleted Content added
Added navbox |
→Derivation from the conjugate direction method: first expansion |
||
Line 9:
==Derivation from the conjugate direction method==
{{Expand section|date=April 2010}}
The conjugate gradient method can be seen as a special case of the conjugate direction method applied to minimization of the quadratic function
:<math>f(\boldsymbol{x})=(\boldsymbol{b}-\boldsymbol{x})^\mathrm{T}\boldsymbol{A}(\boldsymbol{b}-\boldsymbol{x})\text{.}</math>
===The conjugate direction method===
In the conjugate direction method for minimizing
:<math>f(\boldsymbol{x})=(\boldsymbol{b}-\boldsymbol{x})^\mathrm{T}\boldsymbol{A}(\boldsymbol{b}-\boldsymbol{x})\text{,}</math>
one starts with an initial guess <math>\boldsymbol{x}_0</math> and the corresponding residual <math>\boldsymbol{r}_0=\boldsymbol{b}-\boldsymbol{Ax}_0</math>, and computes the iterate and residual by the formulae
:<math>\begin{align}
\alpha_i&=\frac{\boldsymbol{p}_i^\mathrm{T}\boldsymbol{r}_i}{\boldsymbol{p}_i^\mathrm{T}\boldsymbol{Ap}_i}\text{,}\\
\boldsymbol{x}_{i+1}&=\boldsymbol{x}_i+\alpha_i\boldsymbol{p}_i\text{,}\\
\boldsymbol{r}_{i+1}&=\boldsymbol{r}_i-\alpha_i\boldsymbol{Ap}_i
\end{align}</math>
where <math>\boldsymbol{p}_0,\boldsymbol{p}_1,\boldsymbol{p}_2,\ldots</math> are a series of mutually conjugate directions, i.e.,
:<math>\boldsymbol{p}_i^\mathrm{T}\boldsymbol{Ap}_j=0</math>
for any <math>i\neq j</math>.
The conjugate direction method is imprecise in the sense that no formulae are given for selection of the directions <math>\boldsymbol{p}_0,\boldsymbol{p}_1,\boldsymbol{p}_2,\ldots</math>. Specific choices lead to various methods including the conjugate gradient method and [[Gaussian elimination]].
==Derivation from the Arnoldi/Lanczos iteration==
| |||