superlineare

Superlineare (superlinear, in English) describes growth or convergence that is faster than linear. The term is used across mathematics, numerical analysis and computer science to indicate that the rate of increase or reduction outpaces simple proportional growth, though it does not necessarily imply quadratic or higher-order behavior.

In numerical analysis and optimization, superlinear convergence refers to an iterative method whose error decreases faster than a linear rate as iterations proceed. Formally, if e_k is the error at step k, a superlinear method satisfies e_{k+1} = o(e_k). A classical example is Newton’s method for well-behaved functions, which often exhibits quadratic convergence: the error roughly squares from one iteration to the next. More generally, convergence with order p>1 is considered superlinear, while linear convergence corresponds to p=1.

In algorithmic analysis and complexity theory, superlinear growth describes costs that increase faster than linearly with input size. A time or resource function T(n) is superlinear if T(n)/n → ∞ as n grows, which includes common bounds such as O(n log n) or O(n^1.5). Such behavior contrasts with linear time O(n) or sublinear time O(n^c) with c<1.

In parallel computing, superlinear speedup occurs when adding processors yields speedups greater than the number of processors due to effects like cache locality. The term requires context, as “superlinear” may refer to growth rates in time, convergence, or performance, all indicating rates that exceed simple linear behavior.