polynom verschieben

OP #5129391
Lesenswert?

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

Also zB:


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

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.
1
(                                                                        a_6) *x^6
2
(                                                             +6*a_6*c  +a_5) *x^5
3
(                                                 +15*a_6*c^2 +5*a_5*c  +a_4) *x^4
4
(                                   +20*a_6*c^3   +10*a_5*c^2 +4*a_4*c  +a_3) *x^3
5
(                     +15*a_6*c^4   +10*a_5*c^3   + 6*a_4*c^2 +3*a_3*c  +a_2) *x^2
6
(         +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
7
( +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?
Gast #5129431
Lesenswert?

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.
OP #5129584
Lesenswert?

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 :)
1
void PolynomialParamsSet::shift(double i_off)
2
{
3
  constexpr int MAX_ORDER = 20;
4
  auto oldC = coefficients;
5
  std::array<int, MAX_ORDER> binCoeff;
6
  std::array<double, MAX_ORDER> offsetPower;
7
  binCoeff[0] = 1;
8
  offsetPower[0] = 1.;
9
  for (int i = 1; i < coefficients.length(); ++i) {
10
    offsetPower[i] = offsetPower[i - 1] * i_off;
11
    binCoeff[i] = 1;
12
    coefficients[0] += offsetPower[i] * oldC[i];
13
  }
14

15
  for (int i = 1; i < coefficients.length(); ++i) {
16
    int lastCoeff = binCoeff[i - 1];
17
    binCoeff[i - 1] = 0;
18
    coefficients[i] = 0;
19
    for (int j = i; j < coefficients.length(); ++j) {
20
      int curF = lastCoeff + binCoeff[j - 1];
21
      coefficients[i] += curF * offsetPower[j - i] * oldC[j];
22

23
      lastCoeff = binCoeff[j];
24
      binCoeff[j] = curF;
25
    }
26
  }
27
}
Persönliche Seite #5129873
Lesenswert?

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.
Persönliche Seite #5136537
Lesenswert?

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:

Um 1 nach rechts:

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.
Beitrag #5136557 wurde von einem Moderator gelöscht.

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

oder

Mit Google-Account einloggen

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren