Mathematik: Der Algorithmus Lagrange
Released by matroid on Fr. 21. Mai 2004 12:18:52 [Statistics]
Written by Martin_Infinite - 5615 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)
Titel

Der Algorithmus Lagrange stellt eine Alternative zum erweiterten euklidischen Algorithmus, der z.B. hier vorgestellt wird, dar. Dabei werden in einem euklidischen Ring R für zwei Elemente p,q ein größter gemeinsamer Teiler c von p,q und Elemente r,s mit c = rp + sq gesucht.
 



Dafür müssen neben Addition und Multiplikation jeweils Prozeduren gegeben sein, die den "Rest" und den "ganzzahligen Anteil" bei einer Division berechnen, d.h. Operatoren MOD und DIV, die für b 0 der Gleichung

a = (a DIV b)b + a MOD b

mit a MOD b = 0 oder d(a MOD b) < d(b) genügen, wobei d die "Gradfunktion" des euklidischen Ringes ist. Im euklidischen Polynomring sind diese Operatoren durch die Polynomdivision gegeben, im euklidischen Ring der ganzen Zahlen sogar explizit durch

a DIV b := fdef(floor(a/b),b != 0;0,b=0) , a MOD b := a-(a DIV b)b

Nun zum Algorithmus Lagrange:

1   a := p, b := q, x := 1, v := 1 ,y := 0, u := 0, z := 0 
2 while a Bild 0 and b Bild 0
3 y := zx + y
4 v := zu + v
5 z := a DIV b
6 a := a MOD b
7 if a Bild 0
8 x := zy + x
9 u := zv + u
10 z := b DIV a
11 b := b MOD a
12 end
13 end
14 if a = 0
15 then
16 c := b
17 r := -y
18 s := v
19 else
20 c := a
21 r := x
22 s := -u
23 end


Wir wollen hier diesen Algorithmus verifizieren, d.h. nachweisen, dass der Algorithmus irgendwann abbricht und in jedem Falle einen größten gemeinsamen Teiler c von p,q 0 und Elemente r,s mit c = rp + sq liefert.

Im Folgenden meint "in Zeile j" die Situation nach der Ausführung des Befehls von Zeile j. Zunächst halten wir folgende Gleichungen fest

I p = ub + va
II q = xb + ya
III a = px - qu
IV -b = py - qv

Sie sind offenbar in Zeile 1 und Zeile 4 beim ersten Durchlauf der while-Schleife, die wegen p,q 0 wirklich ausgeführt wird, erfüllt.

Aufgrund der Eigenschaften von MOD und DIV gilt in Zeile 6 b 0 sowie a = 0 oder d(a) < d(b), wobei d wieder die Gradfunktion des gegebenen euklidischen Rings darstellt. Wenn a = 0 ist, wird die while-Schleife schon beendet, ansonsten wird die if-Verankerung ausgeführt und in Zeile 11 gilt analog zu Obigem a 0 sowie b = 0 oder d(b) < d(a). Es ergibt sich also eine streng absteigende Kette von natürlichen d-Werten, sodass die while-Schleife und damit auch der Algorithmus insgesamt nach endlich vielen Schritten beendet wird.

Wir zeigen als nächstes, dass die Gleichungen I bis IV stets in Zeilen 4 und 9 erfüllt sind. Wir wissen ja schon, dass dies in Zeile 4 am Anfang der while-Schleife gilt. Angenommen wir befinden uns in Zeile 4, an einem beliebigen Schritt der while-Schleife. Wir dürfen annehmen, dass danach die if-Verankerung ausgeführt wird, weil die while-Schleife ansonsten sowieso schon beendet ist. Es folgen also die Zuweisungen

z' := a DIV b, a' := a MOD b, x' := zy + x, u' := zv + u


Mit der Voraussetzung, dass z,a,x,u die Gleichungen I bis IV erfüllen, ergibt sich daraus

I u'b+va'=(zv+u)b+v(a MOD b) = v((a DIV b)b+a MOD b)+ub = va+ub = p

II x'b+ya'=((a DIV b)y+x)b+y(a MOD b)=y((a DIV b)b+a MOD b)+xb=ya+xb=q

III px' - qu' = p((a DIV b)y + x) - q((a DIV b)v + u)
= (a DIV b)(py - qv) + px - qu = -(a DIV b)b + a = a MOD b = a'

IV -b = py - qv

Also sind die Gleichungen I bis IV mit den zwischen Zeile 4 und 9 neu definierten Variablen auch in Zeile 9 erfüllt. Und genauso leicht kann man nachrechnen, dass jene Gleichungen in Zeile 4 erfüllt sind, wenn sie nur in Zeile 9 gelten.

Nun wenden wir uns dem zweiten Teil des Algorithmus zu. Angenommen in Zeile 13 ist a = 0. Dann kann im letzten Schritt der while-Schleife nicht die if-Verankerung ausgeführt worden sein, sodass die letzten beiden Zuweisungen 5 und 6 waren. Wir ersetzen sie durch

z' := a DIV b und a' := a MOD b

und haben damit Variablen a,b,u etc., die die Gleichungen I bis IV erfüllen. Ferner gilt a' = 0 und a 0. Mit den Zuweisungen 16 - 18 gilt dann

rp + sq = -py + qv = b = c

sowie

(z'v + u)b = (a DIV b)vb + p - va = ((a DIV b)b - a)v + p = -a'v + p = p

(z'y + x)b = (a DIV b)yb + q - ya = ((a DIV b)b - a)y + q = -a'y + q = q

sodass c in der Tat ein größter gemeinsamer Teiler von p,q mit c = rp + sq ist. Dabei kann man den Fall a 0 mit 20 - 22 völlig analog durchrechnen. Damit ist der Algorithmus Lagrange verifiziert.




Zum Schluss noch ein Beispiel zur Anwendung des Algorithmus.

Sei f := x² + 1 ein Polynom über dem Körper der rationalen Zahlen Q.
Wir suchen das multiplikative Inverse von (x³ - 2)+(f) im Faktorring Q[x]/(f). Es existiert auf jeden Fall, weil f irreduzibel über Q ist und damit der besagte Faktorring ein Körper ist. Doch wie sieht es nun aus?

Es müsste ein Polynom g in Q[x] mit

((x³ - 2) + (f))*(g + (f)) = 1 + (f), d.h. (x³ - 2)g + (x² + 1)h = 1

für ein Polynom h geben. Mit p = x³ - 2 und q := f = x² + 1 führen wir nun den Algorithmus Lagrange durch:



Wir erhalten damit

(x^3-2)(-x/2+1)+(x^2+1)(1/2 x^2-x-1/2)=-5/2
(x^3-2)(x/5-2/5)+(x^2+1)(-x^2/5+2/5 x+1/5)=1

also für das gesuchte multiplikative Inverse:

((x^3-2)+(f))^(-1)=(x/5-2/5)+(f)

\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Algebra :: Zahlentheorie :: Reine Mathematik :: Mathematik :: Teilbarkeit :
Der Algorithmus Lagrange [von Martin_Infinite]  
stellt eine Alternative zum erweiterten euklidischen Algorithmus, der z.B. hier vorgestellt wird, dar. Dabei werden in einem euklidischen Ring R für zwei Elemente p,q ein größter gemeinsamer Teiler c von p,q und Elemente r,s mit c = rp + sq gesucht.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 5615
 
Aufrufstatistik des Artikels
Insgesamt 375 externe Seitenaufrufe zwischen 2012.01 und 2022.11 [Anzeigen]
DomainAnzahlProz
https://google.com205.3%5.3 %
https://www.startpage.com30.8%0.8 %
http://google.de27773.9%73.9 %
http://google.ru236.1%6.1 %
https://google.de154%4 %
http://google.fr92.4%2.4 %
http://google.pl71.9%1.9 %
https://www.bing.com41.1%1.1 %
http://google.at20.5%0.5 %
http://www.bing.com92.4%2.4 %
http://images.google.de10.3%0.3 %
https://duckduckgo.com10.3%0.3 %
https://www.ecosia.org10.3%0.3 %
http://br.images.search.yahoo.com10.3%0.3 %
http://r.duckduckgo.com10.3%0.3 %
https://de.search.yahoo.com10.3%0.3 %

Häufige Aufrufer in früheren Monaten
Insgesamt 352 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2013-2018 (120x)http://google.de/url?sa=t&rct=j&q=
2012-2014 (42x)http://google.de/url?sa=t&rct=j&q=lagrange algorithmus
201206-07 (24x)http://google.de/url?sa=t&rct=j&q=lagrange mathe
201211-11 (23x)http://google.ru/imgres?q=2 x 2 = 5
201205-05 (19x)http://google.de/url?sa=t&rct=j&q=lagrange matroid
2020-2022 (18x)https://google.com/
201210-10 (15x)http://google.de/url?sa=t&rct=j&q=lagrange-algorithmus
201301-01 (14x)http://google.de/url?sa=t&rct=j&q=matroids matheplanet algorithem eine einfÃ...
2020-2021 (10x)https://google.de/
201202-02 (9x)http://google.de/url?sa=t&rct=j&q=lagrange bewegungsgleichung algorithmus
201212-12 (9x)http://google.de/url?sa=t&rct=j&q=lagrange euler algorithmus
201204-04 (9x)http://google.fr/imgres?q=x³-2
201306-06 (7x)http://google.de/url?sa=t&rct=j&q=lagrange algorithmus programm
201208-08 (7x)http://google.pl/imgres?start=179&um=1&sa=N&biw=1680&bih=888&tbm=isch&tbnid=o...
201209-09 (6x)http://google.de/search?q=lagrange algorithmus
201303-03 (6x)http://google.de/url?sa=t&rct=j&q=multiplikatives inverses mit euklidischem a...
201307-07 (5x)http://google.de/url?sa=t&rct=j&q=lagrange logarithmus
202101-07 (5x)https://google.de
2020-2022 (4x)https://www.bing.com/

[Top of page]

"Mathematik: Der Algorithmus Lagrange" | 4 Comments
The authors of the comments are responsible for the content.

Re: Der Algorithmus Lagrange
von: Martin_Infinite am: Sa. 22. Mai 2004 11:58:57
\(\begingroup\)HIER findet sich neben einer weiteren Beispielrechnung gleich eine Gegenüberstellung zum euklidischen Algorithmus.\(\endgroup\)
 

Re: Der Algorithmus Lagrange
von: matroid am: Sa. 22. Mai 2004 20:23:55
\(\begingroup\)Hi Martin,

kompliziertes Thema, da muß man sich erst mal in Ruhe vertiefen. Jedesmal wenn ich diese Faktoren r und s wieder mal berechnen muß, dann schaue ich in mein Kochrezept. Um so besser, daß Du jetzt ein neues Rezept hinzugefügt hast. Besten Dank.

Aber mal stilistisch: Ist 'Algorithmus Lagrange' eine Anspielung an 'Clockwork Orange'? Und so ist Dein Artikel eine Hommage an den 'Style 2004', in dem 'orange' eine Rolle spielt?

Viele Grüße
Matroid\(\endgroup\)
 

Re: Der Algorithmus Lagrange
von: Martin_Infinite am: Mo. 24. Mai 2004 14:14:11
\(\begingroup\)Hi Matroid

Danke für die Blumen!

Zu deiner Stilfrage: Phonetisch stimmt die Anspielung, inhaltlich aber nicht.

Aber ich habe intuitiv Überschrift und Tabellenrahmen blau gefärbt, um wieder einen Komplementärkontrast, den du ja schon auf der ganzen Seite im neuen Style hergestellt hast, mit dem Orange herzustellen.

Gruß
Martin\(\endgroup\)
 

Re: Der Algorithmus Lagrange
von: Ex_Mitglied_40174 am: Mo. 05. Februar 2007 18:04:29
\(\begingroup\)hi matroid was ist der unterschied (sollte es einen geben) zwischen dem lagrange algorithmus und dem berlekamp algorithmus?\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]