iteration

Iteration (from Latin iterare , repeat ') generally describes a process of repeating the same or similar actions several times to approach a solution or a specific goal. With this meaning first used in mathematics, the term is now used in various fields with a similar meaning. In computer science, for example, not only the process of repetition, but also the repetition itself is called iteration. In other areas, the meaning is limited to repetition, as in the Latin starting word, for example in linguistics.

Dynamic systems

In mathematics , especially in the theory of dynamic systems , iteration is the repeated application of the same function, i.e. the formation (composition) of

{\ displaystyle f ^ {n}: = \ underbrace {f \ circ f \ circ \ dotsb \ circ f} _ {n {\ text {mal}}}}

for a given function on a set (a space) . ${\ displaystyle f \ colon X \ to X}$ ${\ displaystyle X}$

The theory of dynamic systems deals in particular with the long-term behavior of the orbits of points under such iterations. ${\ displaystyle \ left \ {f ^ {n} (x) \ right \}}$ ${\ displaystyle x \ in X}$

example

Consider the quadratic function ${\ displaystyle f \ colon \ mathbb {R} \ to \ mathbb {R}}$

{\ displaystyle f (x) = x ^ {2}}

.

Then (not to be confused with ) and one can investigate the long-term behavior of different orbits: for converges to the fixed point 0, for applies , for the sequence is constant and also for the sequence remains constant from the first iteration. ${\ displaystyle f ^ {n} (x) = x ^ {2 ^ {n}}}$ ${\ displaystyle (f (x)) ^ {n} = x ^ {2n}}$ ${\ displaystyle \ vert x \ vert <1}$ ${\ displaystyle f ^ {n} (x)}$ ${\ displaystyle x> 1}$ ${\ displaystyle \ lim _ {n \ to \ infty} f ^ {n} (x) = \ infty}$ ${\ displaystyle x = 1}$ ${\ displaystyle x = -1}$

Different spelling

Because of the possibility of confusion mentioned, the spellings are occasionally found in the literature

for potency :	${\ displaystyle f ^ {\; \! 0}}$	${\ displaystyle: = \ mathrm {1}}$	and	${\ displaystyle f ^ {\; \! n + 1}}$	${\ displaystyle: = f \ cdot f ^ {\; \! n}}$	( without superscript parentheses)
for the derivation :	${\ displaystyle f ^ {(0)}}$	${\ displaystyle: = f}$	and	${\ displaystyle f ^ {(n + 1)}}$	${\ displaystyle: = (f ^ {(n)}) '}$	(with raised round bracket),
for the iteration:	${\ displaystyle f ^ {\ langle {0} \ rangle}}$	${\ displaystyle: = \ mathrm {id} _ {X}}$	and	${\ displaystyle f ^ {\ langle {n + 1} \ rangle}}$	${\ displaystyle: = f \ circ f ^ {\ langle {n} \ rangle}}$	(with pointed brackets raised). ${\ displaystyle \ langle \ rangle}$

Then for example

${\ displaystyle \ sin ^ {2} + \ cos ^ {2} = 1}$	two second powers (squares), is
${\ displaystyle \ sin ^ {(2)} = - \ sin}$	the second derivative and
${\ displaystyle \ sin ^ {\ langle {-} 1 \ rangle} = \ arcsin}$	the inverse function (the minus first iteration)

the sine function.

numerical Mathematics

In numerical mathematics , iteration describes a method of gradually approaching the exact solution of a computational problem (successive approximation ). It consists in the repeated use of the same calculation method.

The results of one step are taken as the starting values for the next step. The sequence of results must converge . If the difference to the previous calculation step is smaller than the accepted error, then the result has been determined with sufficient accuracy and the method is ended. One of the best-known examples is the Newton method . Sometimes results from two or more previous steps are used in the next step, for example with the Regula falsi .

The speed of convergence is a measure of how useful the iteration method is.

Application of the method

Iteration is used in cases where the result cannot be calculated in closed form, for example with the Kepler equation , calculating the surface shape of an aspherical lens or the heat distribution on a circuit board.
Systems of linear equations can be solved iteratively under certain conditions.
In the case of application problems, the input data can contain errors, in which case the “exact solution” of the given problem is not necessarily better than its approximation. The iteration method is preferred if it delivers a good approximation faster than the calculation of the exact solution needs.
Some functions on calculators or fractals are calculated iteratively.

Example: Determination of zeros of a continuous function

Approximations at zeros of a continuous function , if one exists at all, are often found iteratively more quickly than by other algebraic methods (e.g. as a closed expression):

One chooses two approximate values for the zero of the function in such a way that is.

{\ displaystyle x_ {1}, \, x_ {2}}

{\ displaystyle f}

{\ displaystyle f (x_ {1}) \ cdot f (x_ {2}) <0}

The equation of the secant given by and is set up. ${\ displaystyle (x_ {1}; f (x_ {1}))}$ ${\ displaystyle (x_ {2}; f (x_ {2}))}$

The intersection of the secant with the x-axis is then a “better” approximation for the searched zero of .

{\ displaystyle x_ {3} = x_ {1} - {\ frac {x_ {2} -x_ {1}} {f (x_ {2}) - f (x_ {1})}} \ cdot f (x_ {1})}

{\ displaystyle f}

The two aforementioned steps are repeated until the zero point has been found with the desired accuracy ( Regula falsi ).

Computer science

In addition to mathematical iterative problem solving, computer science also speaks of iteration, if

data of a data structure is accessed step by step (repeated in the same way), for example by means of a FOREACH loop .
A special pointer to the individual objects is called an iterator if it switches (usually automatically) to the next date / object in the data structure after each access.

an instruction block (the so-called "loop body") - controlled by loop control instructions - is executed repeatedly ; each execution is an iteration of the loop . This type of programming is known as iterative programming .
It is in contrast to recursive programming , in which the statement block is inserted into a procedure and its repetitions are formulated by recursive (self) calls.

linguistics

In linguistic terms, iterative denotes the type of action of a verb that expresses an occurrence consisting of repeatedly repeated similar processes, e.g. B. fluttering , crawling or poking . Such repetitive verbs are also called iteratives .

When forming a word, we speak of iteration if the same or similar word parts are repeated two or more times, for example in great-great-grandmother (see also reduplication or triplication ).

Software engineering

In software technology , an iteration describes a single development cycle, depending on the process model, beginning with planning, analysis or design, ending with implementation, testing or maintenance. Iterations play a special role in Extreme Programming and the Rational Unified Process . In Scrum (agile project management), an iterative process is often used to develop software. One speaks here of feedback loops in all phases of planning, implementation, review and adjustment.

History

In historical studies, iteration denotes the repeated exercise of the same office in the official career of the Roman Republic . After the Mos maiorum , iteration was frowned upon. At the consulate the multiple, in exceptional cases also immediately consecutive, dressing of the office had occurred since the early republic; since the constitutional reform of the dictator Sulla in 82 BC Chr. Repeated clothing of the consulate was only allowed after ten years. Alongside the collegiality and annuity principles, the prohibition of iteration was the most important means of preventing a dangerous wealth of power from public officials.

The iteration came up repeatedly, especially during the crisis of the republic : the best-known examples are Gaius Sempronius Gracchus , who wanted to be elected tribune for three years in a row , and Gaius Marius , who held the consulate for five consecutive years (104 to 100 BC). and exercised a total of seven times, as well as Gaius Iulius Caesar , who ran the consulate in 59, 48, 46, 45 and 44 BC. Clad. In the imperial period from Augustus onwards, the iteration of the consulate was a sign of a prominent socio-political position. Consulates in immediate succession were only held by members of the imperial family.

philosophy

Jacques Derrida introduced iteration to the language of philosophy . "Iteration" here describes the repetition of a term in philosophical and social discourse. According to Derrida, with each iteration of a term, its meaning changes, so that the same meaning is never reproduced as when the term was used before. Rather, each iteration results in a variation in meaning that adds something to the original term and enriches it. There can therefore be no original definition of terms to which one could trace their meaning.

Construction economy

In construction economics , an iterative process is the step-by-step approach of the original construction goals to the feasible implementation.

Construction theory

In design theory , one speaks of iterative approach , sometimes also of iterative search , when the approach to finding a solution is that the solution is gradually improved on the basis of an inspiration from the designer.

management

In management , iteration is a way of dealing with the uncertainties and surprises in complex situations. In the event of changes, the course of projects or the effect of actions cannot always be forecast. Regarding every change management as a "big plan" with immovable goals leads in most cases to surprises for which the planners and implementers are not prepared. That does not mean giving up plans, but rather only being temporarily certain about your own approach. Linear-causal project thinking is replaced by an iterative approach : By probing in advance along purposes, interests and power constellations, ambiguity is gradually reduced, acceptance achieved, effect generated and routine established. The sequence of topics and content only emerges in the course of the change. "An iterative process of initial interpretation and design, implementation and improvisation, learning from change effort, and then sharing that learning systemwide, leading to ongoing re-interpretation and redesign of the change as needed." (Anthony F. Buono / Kenneth W Kerber: Building Organizational Change Capacity).

Web links

Wiktionary: Iteration - explanations of meanings, word origins, synonyms, translations

Individual evidence

^ Helmut Glück (ed.), With the assistance of Friederike Schmöe : Metzler Lexikon Sprach . 4th, updated and revised edition. Verlag JB Metzler, Stuttgart / Weimar 2010, ISBN 3-476-02335-4 . Keywords: iteration , iterative .
^ Jacques Derrida: signature event context. In: Peter Engelmann (Ed.): Randgang der Philosophie , Passagen, Vienna 1988. See also Jacques Derrida: Limited Inc. Passagen, Vienna 2001. Although Derrida popularized the term, Edmund Husserl already used the term (more or less terminological) used: e.g. in the lectures on the phenomenology of inner time consciousness : “The time-constituting continuum is a flow of constant generation of modifications and modifications. Starting from the current now, the respective original impression u, the modifications proceed in the sense of iterations, but steadily forwards; they are not only modifications in relation to u, but also successive modifications of each other in the order in which they run. "( P. 451, online at the University of Freiburg ).
^ Robert Fischer, Peter Schwer: Modules for the house of the future . VDF Hochschulverlag AG at ETH Zurich and Interact Verlag, Hochschule Luzern, Luzern 2009, p. 14, ISBN 978-3-7281-3286-4 (VDF) or ISBN 978-3-906413-72-3 (interact), online at google books .
↑ Markus Bürger, Michael Dambacher, u. a .: Design theory - mechanical engineering . Verlag Europa-Lehrmittel, Haan-Gruiten 2009, p. 11, ISBN 978-3-8085-1400-9 , fs-fachbuch.at (PDF).
↑ Faculty for Interdisciplinary Research and Training (PDF) University of Klagenfurt, accessed on April 25, 2019.

[1] Helmut Glück (ed.), With the assistance of Friederike Schmöe : Metzler Lexikon Sprach . 4th, updated and revised edition. Verlag JB Metzler, Stuttgart / Weimar 2010, ISBN 3-476-02335-4 . Keywords: iteration , iterative .

[2] Jacques Derrida: signature event context. In: Peter Engelmann (Ed.): Randgang der Philosophie , Passagen, Vienna 1988. See also Jacques Derrida: Limited Inc. Passagen, Vienna 2001. Although Derrida popularized the term, Edmund Husserl already used the term (more or less terminological) used: e.g. in the lectures on the phenomenology of inner time consciousness : “The time-constituting continuum is a flow of constant generation of modifications and modifications. Starting from the current now, the respective original impression u, the modifications proceed in the sense of iterations, but steadily forwards; they are not only modifications in relation to u, but also successive modifications of each other in the order in which they run. "( P. 451, online at the University of Freiburg ).

[3] Robert Fischer, Peter Schwer: Modules for the house of the future . VDF Hochschulverlag AG at ETH Zurich and Interact Verlag, Hochschule Luzern, Luzern 2009, p. 14, ISBN 978-3-7281-3286-4 (VDF) or ISBN 978-3-906413-72-3 (interact), online at google books .

[4] Markus Bürger, Michael Dambacher, u. a .: Design theory - mechanical engineering . Verlag Europa-Lehrmittel, Haan-Gruiten 2009, p. 11, ISBN 978-3-8085-1400-9 , fs-fachbuch.at (PDF).

[5] Faculty for Interdisciplinary Research and Training (PDF) University of Klagenfurt, accessed on April 25, 2019.