polynom verschieben

[Vlad T. (vlad_tepesch)]

Hi ich habe ein Polynom beliebig vieler cooeffizienten (theoretisch, 
praktisch sind es zB6)

Also zB:

$$p(x):= a_6(x)^6+a_5(x)^5+a_4(x)^4+a_3(x)^3 + a_2(x)^2 +a_1(x) + a_0$$

dieses möchte ich jetzt in x-Richtung verschieben, so dass gilt:

$$p_{new}(x):= p(x+c)$$

da gibts doch bestimmt nen schlauen Algorithmus, wie ich das c in die 
Kooefizienten reinrechne.

wenn man das ganze für das Beispiel 6 mal ausmultiplizieren lässt, 
ergibt sich ein ganz schöner Wust an Termen.

(                                                                        a_6) *x^6
(                                                             +6*a_6*c  +a_5) *x^5
(                                                 +15*a_6*c^2 +5*a_5*c  +a_4) *x^4
(                                   +20*a_6*c^3   +10*a_5*c^2 +4*a_4*c  +a_3) *x^3
(                     +15*a_6*c^4   +10*a_5*c^3   + 6*a_4*c^2 +3*a_3*c  +a_2) *x^2
(         +6*a_6*c^5  + 5*a_5*c^4   + 4*a_4*c^3   + 3*a_3*c^2 +2*a_2*c  +a_1) *x
( +a_6*c^6+  a_5*c^5  +   a_4*c^4   +   a_3*c^3   +   a_2*c^2 +1*a_1*c  +a_0)

Hier raus eine Vorschrift abzuleiten oder eine clevere Implementierung 
abzuleiten fällt mir nur gerade schwer.

Kennt da jemand was?

[mh (Gast)]

Für den Zahlenfaktor in den einzelnen Termen 
https://de.wikipedia.org/wiki/Pascalsches_Dreieck bzw. 
https://de.wikipedia.org/wiki/Binomialkoeffizient

[mh (Gast)]

Ok vllt. sollte ich etwas mehr dazu schreiben. Die Spalten deiner 
"Matrix" sind Diagonalen im Pascalschen Dreieck und wenn du deine Matrix 
im Kopf drehst hast  du das Dreieck. Wenn du von unten rechts anfängst 
sind die Diagonalen von unten links nach oben rechts die Ebenen im 
Pascalschen Dreieck.

[Cyblord -. (Gast)]

Auswertung mittels Horner-Schema:

https://de.wikipedia.org/wiki/Horner-Schema

[Vlad T. (vlad_tepesch)]

Abradolf L. schrieb:
> https://de.wikipedia.org/wiki/Horner-Schema

inwiefern hilft mir das?

mh schrieb:
> Für den Zahlenfaktor in den einzelnen Termen
> https://de.wikipedia.org/wiki/Pascalsches_Dreieck bzw.
> https://de.wikipedia.org/wiki/Binomialkoeffizient

ja, das hab ich auch gefunden, nachdem mir die Zahlen bekannt vor kamen 
:)


weiß nicht obs noch cleverer geht, so richtig zufrieden bin ich noch 
nicht :)

void PolynomialParamsSet::shift(double i_off)
{
  constexpr int MAX_ORDER = 20;
  auto oldC = coefficients;
  std::array<int, MAX_ORDER> binCoeff;
  std::array<double, MAX_ORDER> offsetPower;
  binCoeff[0] = 1;
  offsetPower[0] = 1.;
  for (int i = 1; i < coefficients.length(); ++i) {
    offsetPower[i] = offsetPower[i - 1] * i_off;
    binCoeff[i] = 1;
    coefficients[0] += offsetPower[i] * oldC[i];
  }

  for (int i = 1; i < coefficients.length(); ++i) {
    int lastCoeff = binCoeff[i - 1];
    binCoeff[i - 1] = 0;
    coefficients[i] = 0;
    for (int j = i; j < coefficients.length(); ++j) {
      int curF = lastCoeff + binCoeff[j - 1];
      coefficients[i] += curF * offsetPower[j - i] * oldC[j];

      lastCoeff = binCoeff[j];
      binCoeff[j] = curF;
    }
  }
}

[Johann L. (gjlayde)]

Vlad T. schrieb:
> weiß nicht obs noch cleverer geht

Du könntest den Offset zusammen mit dem Polynom speichern und erst bei 
der Auswertung anwenden, d.h. anstatt ein neues Polynom q(x) = p(x-off) 
zu berechnen, speicherst du off im Polynom-Objekt.

Vorteile:
- Einfachere Auswertung.
- Weniger Rundungsfehler, wenn mehrfach verschoben wird.

Nachteile:
- Die Darstellung des Polynoms ist nicht mehr eindeutig.
- Zur Polynomarithmetik müssen alle beteiligten Polynome gleichen
  Offset haben.

[Johann L. (gjlayde)]

...und das o.g. Horner-Schema sieht auch ganz gut aus, aben mit formaler 
Auswertung der neuen Koeffizienten anstatt Wertberechnung:

Schreib das Polynom in Horner-Darstellung und hangel dich rekursiv vom 
höchsten Koeffizienten runter bis a0.

[Duennwandiger Troll (Gast)]

Faktorisieren. Dh die Nullstellen bestimmen.

[Edi M. (Gast)]

Duennwandiger Troll schrieb:
> Faktorisieren. Dh die Nullstellen bestimmen.

Geht das etwas genauer? Was macht man mit den Nullstellen?
In die Normalform verschieben?

Wie berechnet man die Nullstellen allgemein, wenn die Koeffizienten 
nicht vorher bekannt sind?

[Johann L. (gjlayde)]

Edi M. schrieb:
> Duennwandiger Troll schrieb:
>> Faktorisieren. Dh die Nullstellen bestimmen.
>
> Geht das etwas genauer? Was macht man mit den Nullstellen?
> In die Normalform verschieben?

Für praktische Anwendung ist Faktorisierung die inpraktikabelste und 
aufwändigste Methode, zusätzlich mit Rundingsfehlern behaftet.

Nehmen wir mal p(x) = x^2 + 2 und wollen das mittels Faktorisierung um 1 
nach rechts verschieben.  Das Polynom zerfällt über Q(sqrt(-2)) als:

$$p(x) = \left(x-\sqrt{-2}\right)\left(x+\sqrt{-2}\right)$$

Um 1 nach rechts:

$$p(x-1) = \left(x-\sqrt{-2}-1\right)\left(x+\sqrt{-2}-1\right)$$

Und dann ausmultiplizieren um wieder ein Polynom über Z zu erhalten.

> Wie berechnet man die Nullstellen allgemein, wenn die Koeffizienten
> nicht vorher bekannt sind?

Das ist eine Wissenschaft für sich.  Vergiss den Vorschlag.