Erweiterter euklidischer Algorithmus

07.06.2013, 21:29

henriii

Erweiterter euklidischer Algorithmus

Jetzt sitze ich schon tagelang an einem Verständnisproblem. Ich versuche gerade, autodidaktisch den erweiterten Euklidischen Algorithmus zu verstehen anhand folgender Überlegungen:

Der Text sagt, ax + by = ggT(a,b)

zunächst soll ganz normal der ggT berechnet werden, zusätzlich in jedem Schritt aber noch die Zahlen

$\begin{eqnarray*} <br /> x_{k} = x_{k-2} - q_{k} * x_{k-1} <br /> \end{eqnarray*}$

und

$\begin{eqnarray*} <br /> y_{k} = y_{k-2} - q_{k} * y_{k-1}<br /> \end{eqnarray*}$

mit den Anfangswerten x0 = 1, y0 = 0, x1 = 0, y1 = 1

das soll anscheinend so sein, weil r0 = a und r1 = b, wieso?? welche division gibt als rest den wert a selbst oder b selbst?

wenn $\begin{eqnarray*} r_{k+1} = 0 \end{eqnarray*}$ ist, ist ja der Algorithmus beendet und das y und k löst meine diophantische Gleichung.

Ich verstehe jetzt nicht, wie die Anfangswerte von x und y zustande kommen. Und wieso gibt es überhaupt diese Anfangswerte? Ich meine, die existieren doch noch garnicht in dem Schritt? Kann mir das bitte jemand anschaulich erklären?

07.06.2013, 22:15

HAL 9000

Auf diesen Beitrag antworten »

RE: Erweiterter euklidischer Algorithmus
Ob's "anschaulich" genug ist, weiß ich nicht zu sagen. Ich hole mal weit aus, um die Idee des EEA zu verdeutlichen:

Zu jedem (!) Zeitpunkt $\begin{eqnarray*} k \end{eqnarray*}$ des Algorithmus soll für die anfallenden Reste

$\begin{eqnarray*} r_k = x_k a + y_k b \qquad (*) \end{eqnarray*}$

gelten, dabei ist $\begin{eqnarray*} r_0,r_1,r_2,\ldots \end{eqnarray*}$ die Folge der Zahlen, die beim "einfachen" euklidischen Algorithmus anfällt, d.h. mit Start $\begin{eqnarray*} r_0=a,r_1=b \end{eqnarray*}$ .

Nun bestimmt man ja $\begin{eqnarray*} q_k := \left\lfloor \frac{r_{k-2}}{r_{k-1}} \right\rfloor \end{eqnarray*}$ und setzt dann den nächsten Rest gemäß

$\begin{eqnarray*} r_k = r_{k-2} - q_k r_{k-1} \end{eqnarray*}$

fest. Tja, und nun setz mal (*) für die drei Indizes $\begin{eqnarray*} k-2,k-1,k \end{eqnarray*}$ hier in diese Rekursionsgleichung ein, und erhältst

$\begin{eqnarray*} x_k a + y_k b = x_{k-2} a + y_{k-2} b - q_k( x_{k-1} a + y_{k-1} b) \end{eqnarray*}$ .

Koeffizientenvergleich nach $\begin{eqnarray*} a,b \end{eqnarray*}$ ergibt, dass eine Festlegung gemäß

$\begin{eqnarray*} x_k = x_{k-2} - q_k x_{k-1} \end{eqnarray*}$
$\begin{eqnarray*} y_k = y_{k-2} - q_k y_{k-1} \end{eqnarray*}$

die Gleichung (*) für Index $\begin{eqnarray*} k \end{eqnarray*}$ erfüllt, sofern diese bereits für $\begin{eqnarray*} k-2,k-1 \end{eqnarray*}$ erfüllt ist (Schlussweise durch Vollständige Induktion).

Und nun nochmal zur Wahl der Startwerte der x,y-Folgen:

Für $\begin{eqnarray*} k=0 \end{eqnarray*}$ ist $\begin{eqnarray*} r_0=a \end{eqnarray*}$ , und es gilt ja $\begin{eqnarray*} a = {\color{red}1}\cdot a + {\color{red}0}\cdot b \end{eqnarray*}$

Für $\begin{eqnarray*} k=1 \end{eqnarray*}$ ist $\begin{eqnarray*} r_1=b \end{eqnarray*}$ , und da gilt $\begin{eqnarray*} b = {\color{red}0}\cdot a + {\color{red}1}\cdot b \end{eqnarray*}$

10.06.2013, 08:56

Mystic

Auf diesen Beitrag antworten »

RE: Erweiterter euklidischer Algorithmus
Da die Folgen $\begin{eqnarray*} \left( r_k \right), \left( x_k \right) \end{eqnarray*}$ und $\begin{eqnarray*} \left( y_k \right) \end{eqnarray*}$ ersichtlich all der gleichen Rekursion - nur halt mit unterschiedlichen Startwerten - genügen, kann man sie auch sehr schön zu einem Vektor zusammenfassen, wie im nachfolgenden Maple-Programm geschehen... Augenzwinkern

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

EEA:=proc(a::integer,b::integer)
    # option trace;
    local u:=[a,1,0],v:=[b,0,1],w;
    do
       if v[1]=0 then return sign(u[1])*u end if;
       w:=u-floor(u[1]/v[1])*v; u:=v; v:=w
    end do
end:

EEA(17,5);
                           [1, -2, 7]

Neue Frage »

Antworten »

Erweiterter euklidischer Algorithmus

Verwandte Themen