Problem 421086 · medium · Level 04 Non-Linear Data Structures

Stable, Unstable or Ringing For Ever?

poles · stability · unit circle · marginal stability · repeated poles

A drone's flight-control firmware is built from recursive filters and loops, and every candidate is checked before it flies. The check uses the poles: the roots of the denominator list a, read as powers of z with the highest first (see the root-finding problem). Each pole p contributes a term like p ** k to the impulse response:

  • |p| < 1: the term dies away. If every pole is inside the unit circle, the system is stable.
  • |p| > 1: the term grows without limit: unstable (the drone flips over).
  • |p| = 1: the term neither grows nor dies. A pole at 1 holds a constant for ever (an integrator), a pair at exp(+-1j * w) rings as a sine wave for ever (a digital oscillator). With such simple poles on the circle and none outside, the system is marginally stable. But a pole on the circle that is repeated gives a term like k * p ** k, which grows: unstable.

The setup provides roots_of(p), which returns the roots of a coefficient list (highest power first) as a list of complex numbers, computed by Durand-Kerner as in the root-finding problem. Its answers are accurate to about 1e-8 even for repeated roots, so use these tolerances:

  • radius is the largest abs(pole) (0.0 if there are no poles, len(a) == 1);
  • a pole is on the circle if abs(abs(pole) - 1) <= 1e-6, outside if abs(pole) > 1 + 1e-6;
  • two poles on the circle are the same pole if they are less than 1e-3 apart.

Write pole_verdict(a) that returns (verdict, radius), where verdict is "unstable" if a pole is outside or a pole on the circle is repeated, otherwise "marginal" if a pole is on the circle, otherwise "stable". To see each kind of impulse response, paste your run_transfer from the seismometer problem and press Run with plot(run_transfer([1], a, [1] + [0] * 60)).

Examples

Input:  a = [1, -1.2, 0.5]
Output: ("stable", 0.7071067811865476)
Explanation: poles 0.6 +- 0.3j, both at distance sqrt(0.5) from 0.

Input:  a = [1, -1.6180339887498949, 1]
Output: ("marginal", 1.0)
Explanation: poles at exp(+-0.2j * pi): an oscillator producing a sine at a tenth of the sample rate.

Input:  a = [1, -2, 1]
Output: ("unstable", 1.0)
Explanation: a double pole at z = 1: the step response is a ramp that never stops.

Constraints

  • a[0] != 0, len(a) <= 11
  • no pole is within 1e-4 of the circle unless it is exactly on it; distinct poles on the circle are at least 0.05 apart
  • answers are compared with a tolerance of 1e-6; a list is accepted in place of the tuple

Goals

  • Decide stability from the poles: every pole strictly inside the unit circle
  • Recognise marginal stability: simple poles on the circle, which ring or hold for ever
  • Know that a repeated pole on the circle, or any pole outside it, makes the system unstable
Starting Python…