ABS algorithm

From Glossary

Jump to: navigation, search

This is a family of algorithms to solve a linear system of LaTeX: m equations, LaTeX: Ax = b, with LaTeX: n variables such that LaTeX:  n \ge m . Its distinguishing property is that the k-th iterate, LaTeX: x^k, is a solution to the first LaTeX: k equations. While algorithms in this class date back to 1934, the family was recognized and formally developed by J. Abaffy, C.G. Broyden and E. Spedicato, so the algorithm family name bears their initials. The ABS algorithm is given by the following.

Notation: LaTeX: A_{(i,:)} is the i-th row of LaTeX: A.

  1. Initialize: choose LaTeX: x^0 \in \mathbb{R}^n, LaTeX: H^1 \in \mathbb{R}^{n \times n} so that is it nonsingular, set LaTeX: i = 1
  2. Set search direction LaTeX: d^i = H^i z for any LaTeX: z that does not satisfy LaTeX: z^T H^i A_{(i,:)} = 0. Compute residuals: LaTeX: r = Ax^i - b.
  3. Iterate: LaTeX: x^{i+1} = x^i - s d^i, where LaTeX: s is the step size: LaTeX: s = r_i / A_{(i,:)} d^i.
  4. Test for convergance (update residuals, if used in test): Is solution within tolerance? If so, stop; else, continue.
  5. Update: LaTeX: H^{i+1} = H^i - D^i, where LaTeX: D^i is a rank 1 update of the form LaTeX:  H^i A_{(i,:)} (H^i w)^T for LaTeX: w such that LaTeX: w^T H^i A_{(i,:)} = 1.
  6. Increment: let LaTeX: i = i + 1 and go to step 1.

The ABS algorithm extends to nonlinear equations and to linear diophantine equations.


Views
Personal tools