Einfache Lagrange Interpolatin < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | keine Aufgabe, nur Frage |
Mir ist gerade aufgefallen, dass die Lagrange Interpolation (im Restklassenring n) zwar relativ einfach ist, jedoch während einer Klausur (und darum geht es mir gerade) relativ wenig bringt.
Wenn ich meine Aufzeichnungen und Bücher richtig verstehe, dann kann ich in einem Restklassenring folgender Weise mein x Interpolieren:
[mm] $\sum\limits_{i=1}^k y_i\cdot \prod\limits_{1\leq m\leq k \vee m\neq j}^k (x-x_m)(x_j-x_m)^{-1} \bmod [/mm] n$
Was bedeutet, dass ich immerwieder das multiplikativ Inverse mod n berechnen müsste, für jeden Faktor jedes einzelnen Polynoms. Das ist natürlich in einer Klausur recht zeitintensiv.
Daher die Frage: Gibt es eine einfachere/schnellere Methode die Lagrange Interpolation mod n durchzuführen? Bzw. (noch besser) eine schnellere Methode (per Hand) das multiplikativ Inverse mod n zu berechnen?
Danke und liebe Grüße!
alex.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:08 Fr 21.03.2014 | | Autor: | felixf |
Moin,
> keine Aufgabe, nur Frage
> Mir ist gerade aufgefallen, dass die Lagrange
> Interpolation (im Restklassenring n) zwar relativ einfach
> ist, jedoch während einer Klausur (und darum geht es mir
> gerade) relativ wenig bringt.
>
> Wenn ich meine Aufzeichnungen und Bücher richtig verstehe,
> dann kann ich in einem Restklassenring folgender Weise mein
> x Interpolieren:
>
> [mm]\sum\limits_{i=1}^k y_i\cdot \prod\limits_{1\leq m\leq k \vee m\neq j}^k (x-x_m)(x_j-x_m)^{-1} \bmod n[/mm]
>
> Was bedeutet, dass ich immerwieder das multiplikativ
> Inverse mod n berechnen müsste, für jeden Faktor jedes
> einzelnen Polynoms. Das ist natürlich in einer Klausur
> recht zeitintensiv.
>
> Daher die Frage: Gibt es eine einfachere/schnellere Methode
> die Lagrange Interpolation mod n durchzuführen? Bzw. (noch
> besser) eine schnellere Methode (per Hand) das
> multiplikativ Inverse mod n zu berechnen?
nun, du kannst das ganze als lineares Gleichungssystem schreiben und dieses mit dem Gauss-Verfahren loesen. Dabei musst du allerdings auch modulo $n$ invertieren, wenn du es ganz klassisch machst, allerdings gibt's auch eine "divisionsfreie" Variante, bei der du bis zum Schluss rechnen kannst und dann nur die Pivotelemente invertieren musst.
Beim von Hand rechnen, gerade bei kleinen/einfachen Beispielen, ist das mit dem Gleichungssystem meist einfacher als per Lagrange. Vom asymptotischen Aufwand ist beides jedoch im Wesentlichen das gleiche (es sei denn man verwendet schnelle Multiplikation oder aehnliches, aber das lohnt sich nur bei sehr grossen Faellen, also nichts was man in einer Klausur machen will).
LG Felix
|
|
|
| |
|
ah, cool. Vielen Dank schonmal!
Nur kurz zum Verständnis: meinst du mit "musst du allerdings auch modulo $ n $ invertieren" das multiplikativ Inverse? Das ist ja praktisch mein eigentliches Problem, denn das ist ja nicht schwer, nur aufwendig.
Hast du die "divisionsfreie" Variante parat?
Liebe Grüße!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:46 Fr 21.03.2014 | | Autor: | felixf |
Moin,
> Nur kurz zum Verständnis: meinst du mit "musst du
> allerdings auch modulo [mm]n[/mm] invertieren" das multiplikativ
> Inverse?
genau.
> Das ist ja praktisch mein eigentliches Problem,
> denn das ist ja nicht schwer, nur aufwendig.
Ja, das ist nicht ganz ohne  Mit dem euklidischen Algorithmus geht das noch ganz gut, aber ist halt auch muehsam.
Bei ganz kleinen Werten von $n$ bietet es sich an, vorm Rechnen eine Tabelle mit allen Inversen aufzustellen. Das geht meist recht effizient, wenn man alle Potenzen von 2 berechnet (und dann von 3, 5, ..., je nachdem ob noch nicht alles abgegrast ist); sobald man eine Potenz hat, die 1 ergibt, hat man das Inverse von 2 und von allen Potenzen von 2 (mit ein wenig Indexabzaehlerei).
In einer Klausur wird entweder $n$ klein sein oder du musst nur sehr selten invertieren. Oder du darfst Taschenrechner/Computer/... verwenden, mit dem das schneller geht.
> Hast du die "divisionsfreie" Variante parat?
Wenn du etwa die Gleichungen $3 x + 6 y$ und $4 x + 7 y$ hast, kannst du die zweite Gleichung mit 3 multiplizieren und dann 4-mal die erste davon abziehen. Dann hast du aus der zweiten Gleichung $x$ eliminiert, ohne geteilt zu haben.
LG Felix
|
|
|
|
