Penalized present value: Difference between revisions
Jump to navigation
Jump to search
en>Xqbot m r2.7.3) (Robot: Modifying es:Valor Actualizado Penalizado to es:Valor actualizado penalizado |
en>EmausBot m Bot: Migrating 1 langlinks, now provided by Wikidata on d:Q9092530 |
||
| Line 1: | Line 1: | ||
The | The '''conjugate residual method''' is an iterative [[numeric method]] used for solving [[systems of linear equations]]. It's a [[Krylov subspace method]] very similar to the much more popular [[conjugate gradient method]], with similar construction and convergence properties. | ||
This method is used to solve linear equations of the form | |||
:<math>\mathbf A \mathbf x = \mathbf b</math> | |||
where '''A''' is an invertible and [[Hermitian matrix]], and '''b''' is nonzero. | |||
The conjugate residual method differs from the closely related [[conjugate gradient method]] primarily in that it involves more numerical operations and requires more storage, but the system matrix may be merely semi-definite. The conjugate residual method then computes the least-square solution of the linear problem. | |||
Given an (arbitrary) initial estimate of the solution <math>\mathbf x_0</math>, the method is outlined below: | |||
:<math> | |||
\begin{align} | |||
& \mathbf{x}_0 := \text{Some initial guess} \\ | |||
& \mathbf{r}_0 := \mathbf{b} - \mathbf{A x}_0 \\ | |||
& \mathbf{p}_0 := \mathbf{r}_0 \\ | |||
& \text{Iterate, with } k \text{ starting at } 0:\\ | |||
& \qquad \alpha_k := \frac{\mathbf{r}_k^\mathrm{T} \mathbf{A r}_k}{(\mathbf{A p}_k)^\mathrm{T} \mathbf{A p}_k} \\ | |||
& \qquad \mathbf{x}_{k+1} := \mathbf{x}_k + \alpha_k \mathbf{p}_k \\ | |||
& \qquad \mathbf{r}_{k+1} := \mathbf{r}_k - \alpha_k \mathbf{A p}_k \\ | |||
& \qquad \beta_k := \frac{\mathbf{r}_{k+1}^\mathrm{T} \mathbf{A r}_{k+1}}{\mathbf{r}_k^\mathrm{T} \mathbf{A r}_k} \\ | |||
& \qquad \mathbf{p}_{k+1} := \mathbf{r}_{k+1} + \beta_k \mathbf{p}_k \\ | |||
& \qquad \mathbf{A p}_{k + 1} := \mathbf{A r}_{k+1} + \beta_k \mathbf{A p}_k \\ | |||
& \qquad k := k + 1 | |||
\end{align} | |||
</math> | |||
the iteration may be stopped once <math>\mathbf x_k</math> has been deemed converged. Note that the only difference between this and the conjugate gradient method is the calculation of <math>\alpha_k</math> and <math>\beta_k</math> (plus the optional incremental calculation of <math>\mathbf{A p}_k</math> at the end). | |||
==Preconditioning== | |||
By making a few substitutions and variable changes, a preconditioned conjugate residual method may be derived in the same way as done for the conjugate gradient method: | |||
:<math> | |||
\begin{align} | |||
& \mathbf x_0 := \text{Some initial guess} \\ | |||
& \mathbf r_0 := \mathbf M^{-1}(\mathbf b - \mathbf{A x}_0) \\ | |||
& \mathbf p_0 := \mathbf r_0 \\ | |||
& \text{Iterate, with } k \text{ starting at } 0: \\ | |||
& \qquad \alpha_k := \frac{\mathbf r_k^\mathrm{T} \mathbf A \mathbf r_k}{(\mathbf{A p}_k)^\mathrm{T} \mathbf M^{-1} \mathbf{A p}_k} \\ | |||
& \qquad \mathbf x_{k+1} := \mathbf x_k + \alpha_k \mathbf{p}_k \\ | |||
& \qquad \mathbf r_{k+1} := \mathbf r_k - \alpha_k \mathbf M^{-1} \mathbf{A p}_k \\ | |||
& \qquad \beta_k := \frac{\mathbf r_{k + 1}^\mathrm{T} \mathbf A \mathbf r_{k + 1}}{\mathbf r_k^\mathrm{T} \mathbf A \mathbf r_k} \\ | |||
& \qquad \mathbf p_{k+1} := \mathbf r_{k+1} + \beta_k \mathbf{p}_k \\ | |||
& \qquad \mathbf{A p}_{k + 1} := \mathbf A \mathbf r_{k+1} + \beta_k \mathbf{A p}_k \\ | |||
& \qquad k := k + 1 \\ | |||
\end{align} | |||
</math> | |||
The [[preconditioner]] <math>\mathbf M^{-1}</math> must be symmetric. Note that the residual vector here is different from the residual vector without preconditioning. | |||
==References== | |||
* [[Yousef Saad]], ''Iterative methods for sparse linear systems'' (2nd ed.), page 194, SIAM. ISBN 978-0-89871-534-7. | |||
* Jonathan Richard Shewchuck, ''An Introduction to the Conjugate Gradient Method Without the Agonizing Pain'' (edition <math>1 \tfrac 1 4</math>), pages 39–40. | |||
[[Category:Numerical linear algebra]] | |||
[[Category:Articles with example pseudocode]] | |||
Latest revision as of 03:23, 1 April 2013
The conjugate residual method is an iterative numeric method used for solving systems of linear equations. It's a Krylov subspace method very similar to the much more popular conjugate gradient method, with similar construction and convergence properties.
This method is used to solve linear equations of the form
where A is an invertible and Hermitian matrix, and b is nonzero.
The conjugate residual method differs from the closely related conjugate gradient method primarily in that it involves more numerical operations and requires more storage, but the system matrix may be merely semi-definite. The conjugate residual method then computes the least-square solution of the linear problem.
Given an (arbitrary) initial estimate of the solution , the method is outlined below:
the iteration may be stopped once has been deemed converged. Note that the only difference between this and the conjugate gradient method is the calculation of and (plus the optional incremental calculation of at the end).
Preconditioning
By making a few substitutions and variable changes, a preconditioned conjugate residual method may be derived in the same way as done for the conjugate gradient method:
The preconditioner must be symmetric. Note that the residual vector here is different from the residual vector without preconditioning.
References
- Yousef Saad, Iterative methods for sparse linear systems (2nd ed.), page 194, SIAM. ISBN 978-0-89871-534-7.
- Jonathan Richard Shewchuck, An Introduction to the Conjugate Gradient Method Without the Agonizing Pain (edition ), pages 39–40.