Kennisbank

Polynomiale Kromme Best Passend

Achtergrond

Onlangs moesten we voor een klant een best-fit curve berekenen voor een set punten. De software die we implementeerden wordt gebruikt om een metaalbewerkingsmachine aan te sturen en moest een uitvoer produceren die een vloeiende curve was, gebaseerd op een set bemonsterde punten. Omdat ik eerder aan soortgelijke problemen had gewerkt, had ik een ruw idee hoe dit wiskundig zou moeten werken, maar zoals meestal het geval is bij het ontwikkelen van software, was ik er zeker van dat iemand anders dit specifieke probleem al had opgelost.

Vereisten

We hebben een set punten met X- en Y-coördinaten. De software moet een kromme berekenen die het beste past bij de punten. Daarbij moet het ook extra tussenliggende punten introduceren zodat de curve zo vloeiend mogelijk is. Bijvoorbeeld, voor een set van 400 punten berekent de software 5.000 punten die allemaal op de best passende curve liggen.

Onderzoek

Een snelle zoektocht op Google leverde een aantal mogelijke Delphi-oplossingen voor dit probleem op.

De oplossing die het meest veelbelovend leek, was deze oplossing van David Taylor: https://www.satsignal.eu/software/components.html#CurveFit

Dit was een enkele Delphi unit die niet afhankelijk was van andere componenten en gewoon de System.Math unit gebruikte.
De routine was geschreven in Delphi 5, maar het testproject compileerde zonder problemen in de nieuwste versie van Delphi, zoals je zou verwachten van een puur wiskundige Delphi unit.

De code gebruiken

Inputs

De hoofdfunctie accepteert:

  • Een array van floating-point X-waarden.
  • Een array van floating-point Y-waarden.
  • Het aantal termen dat gebruikt moet worden.

Het aantal termen heeft betrekking op de graad van de polynoomformule die zal worden gebruikt.

Een enkele term is gelijk aan een horizontale lijn op een grafiek, bijv.   y = 2

Het gebruik van twee termen staat gelijk aan een rechte lijn op een grafiek, bijv.   y = 3x + 2

Drie termen gebruiken is gelijk aan een kwadratische vergelijking, bijv.   y = 4x² + 3x + 2

Outputs

De berekeningsfunctie vult een array van floating-point waarden die overeenkomen met de coëfficiënten van de vergelijking. Als we bijvoorbeeld drie termen willen gebruiken (een kwadratische vergelijking), kunnen we een matrix van drie drijvendekomma getallen doorgeven. In het bovenstaande kwadratische voorbeeld zouden de coëfficiënten respectievelijk 2, 3 en 4 zijn. De berekening geeft ook een correlatiecoëfficiënt terug, die ons vertelt hoe nauw de curve correleert met de opgegeven invoerpunten. Hoe dichter deze coëfficiënt bij 1 ligt, hoe nauwkeuriger de fit.

Resultaten

Bij het gebruik van de code werden unit tests geschreven op basis van een set testpunten die door onze klant waren aangeleverd. De geleverde punten waren typisch voor de samples die ze in de productie zouden gebruiken. Met deze testpunten werd de nauwkeurigste curve geproduceerd wanneer de functie met zes termen werd aangeroepen. Dit komt overeen met een polynoomfunctie van de vijfde graad.

Bij gebruik van meer dan zes termen ontstonden er af en toe floating-point overflowfouten, waarschijnlijk omdat de berekende coëfficiënten te klein waren om te worden weergegeven in een Double-type in Delphi. Bij gebruik van minder dan zes termen berekende de routine nog steeds de best passende curve, maar de fit was natuurlijk niet zo nauwkeurig. Met minder termen was de correlatiecoëfficiënt lager.

Met zes termen kregen we zes coëfficiënten terug in de array die aan de functie werd geleverd.

Zodra we de coëfficiënten hebben, kunnen we de Y-waarde berekenen voor elke waarde van X. Om de gewenste curve te krijgen, werd een matrix van 5000 gelijkmatig gespreide X-punten berekend, begrensd door de maximale en minimale X-waarden van de steekproef.

function CalculateY(const X: Double; const Coefficients: TArray<Double>): Double;
begin
  var yc := 0.0;
  var xc := 1.0;

  for var i := Low(Coefficients) to High(Coefficients) do
  begin
    yc := yc + Coefficients[i] * xc;
    xc := xc * X;
  end;

  Result := yc;
end;

Hier is een voorbeeld van enkele van de invoerpunten:

In de software wordt de best passende curve berekend en als volgt over de punten gelegd:

Implementatie

De functie gebruikt een algoritme voor het passen van de kleinste kwadratencurve met Gauss-Jordan eliminatie.

Dit is een bekend algoritme voor het vinden van een best passende polynomiale curve voor een verzameling punten.

Conclusie

We hebben gezien dat wiskundige code die oorspronkelijk was geschreven in Turbo Pascal en vroege versies van Delphi zonder wijzigingen kan worden gebruikt in de nieuwste versies van Delphi.

Deze code kan nauwkeurige en vloeiende curven produceren voor de beste fit van een set gegevenspunten.
Hoe hoger het aantal termen en dus de graad van de polynoom, hoe nauwkeuriger de fit.

Geschreven door James Goodger
Directeur, UK

Contact

Laat ons helpen jouw ambities concreet te maken.