Successive approximation

From Glossary

Jump to: navigation, search

The iterative scheme by which an approximation is used for the basic design of an algorithm. The sequence generated is of the form LaTeX: \textstyle x^(k+1) = x^k + A(x^k), where LaTeX: A is an algorithm map specified by its approximation to some underlying goal. Typically, this is used to find a fixed point, where LaTeX: A(x)=0 (e.g., seeking LaTeX: f(x)=x, let LaTeX: A(x) = f(x) - x, so the iterations are LaTeX: x^(k+1) = f(x^k), converging to LaTeX: x^* = f(x^*) if f satisfies certain conditions, such as a contraction map).

Personal tools