Rekursionsgleichung: Substitutionsmethode

18.08.2012, 13:20

HungrigerHugo

Rekursionsgleichung: Substitutionsmethode

Meine Frage:
Hallo, ich hoffe ich bin hier richtig, da ich das ganze gerade nicht in Mathe mache.
Zur Einführung in die Rekursionsgleichungen, hat mein Prof. ein Beispiel gegeben.

$\begin{eqnarray*} T(n)=3\cdot T(n/4)+n \end{eqnarray*}$
$\begin{eqnarray*} T(1)=c \end{eqnarray*}$
Nach einsetzen und vereinfachen folgt:
$\begin{eqnarray*} T(n)=27\cdot T(n/64)+(3/4)^2n+(3/4)^1n+(3/4)^0n \end{eqnarray*}$

Nun kommt es zur Umformung die ich nicht verstehe:
$\begin{eqnarray*} \sum\limits_{i=0}^{log_4n-1} (\frac{3}{4})^in+c\cdot n^{log_4 3} \end{eqnarray*}$

Danke im vorraus!

Meine Ideen:
Da es kein Vorhergegangenes Beispiel gibt und keine "Grundform" gennant wurde, verstehe ich leider gar nix. Meine Suche im Internet war auch nicht wirklich erfolgreich.
$\begin{eqnarray*} (\frac{3}{4})^in \end{eqnarray*}$ ist der einzige Part der Summe den ich nachvollziehen kann. Warum wird der Logarithmus angewandt? Gibt es eine Grundform die diese Lösungen besitzen?

19.08.2012, 22:05

chris95

Auf diesen Beitrag antworten »

Bist du dir sicher, dass dort der $\begin{eqnarray*} \log \end{eqnarray*}$ steht?

Koennte es auch sein, dass dort mod fuer Modolu steht.

19.08.2012, 22:11

HAL 9000

Auf diesen Beitrag antworten »

Für mich stellt sich hier folgende Frage:

$\begin{eqnarray*} T \end{eqnarray*}$ soll ja anscheinend für natürliche Argumente $\begin{eqnarray*} n \end{eqnarray*}$ betrachtet werden? Dann ist aber

Zitat:

Original von HungrigerHugo
$\begin{eqnarray*} T(n)=3\cdot T(n/4)+n \end{eqnarray*}$

nur für durch 4 teilbare $\begin{eqnarray*} n \end{eqnarray*}$ erklärt? Eine ziemlich "löchrig" definierte Rekursion. unglücklich

Sollte es hier nicht eher

$\begin{eqnarray*} T(n) = 3\cdot T\left( \left\lfloor \frac{n}{4} \right\rfloor \right) + n \end{eqnarray*}$

o.ä. heißen? verwirrt

20.08.2012, 09:04

Leopold

Auf diesen Beitrag antworten »

Ich finde den Bezeichner $\begin{eqnarray*} n \end{eqnarray*}$ auch merkwürdig. Ich schreibe einmal dafür lieber $\begin{eqnarray*} x \end{eqnarray*}$ und stelle mir darunter eine beliebige positive reelle Zahl vor.

$\begin{eqnarray*} T(x) = 3 \cdot T \left( \frac{x}{4} \right) + x \end{eqnarray*}$

ist dann die Funktionalgleichung einer Funktion $\begin{eqnarray*} T \end{eqnarray*}$ . Wenn man sie $\begin{eqnarray*} k \end{eqnarray*}$ -mal anwendet, erhält man

$\begin{eqnarray*} T(x) = 3^k \cdot T \left( \frac{x}{4^k} \right) + x \cdot \underbrace{\left( 1 + \frac{3}{4} + \left( \frac{3}{4} \right)^2 + \ldots + \left( \frac{3}{4} \right)^{k-1} \right)}_{\text{geometrische Summe}} \end{eqnarray*}$

also

$\begin{eqnarray*} T(x) = 3^k \cdot T \left( \frac{x}{4^k} \right) + 4x \cdot \left( 1 - \left( \frac{3}{4} \right)^k \right) \end{eqnarray*}$

Diese Gleichung gilt für alle reellen $\begin{eqnarray*} x>0 \end{eqnarray*}$ und alle ganzzahligen $\begin{eqnarray*} k>0 \end{eqnarray*}$ . Speziell darf man $\begin{eqnarray*} x = 4^k \end{eqnarray*}$ , also $\begin{eqnarray*} k = \log_4 x \end{eqnarray*}$ setzen. Dann folgt:

$\begin{eqnarray*} T(x) = 4x + (c-4) \cdot 3^{\log_4 x} = 4x + (c-4) \cdot x^{\log_4 3} \end{eqnarray*}$

Die Formel gilt für alle Viererpotenzen $\begin{eqnarray*} x \end{eqnarray*}$ . Niemand hindert einen natürlich, sie auf alle reellen $\begin{eqnarray*} x>0 \end{eqnarray*}$ fortzusetzen. Man bestätigt, daß dann umgekehrt die obige Funktionalgleichung gilt. Ob es darüber hinaus noch weitere (stetige) Lösungen der Funktionalgleichung gibt, übersehe ich nicht.

21.08.2012, 11:17

HungryHugo

Auf diesen Beitrag antworten »

Hi, hatte leider schon ganz vergessen das ich die Frage hier gestellt habe. Danke für eure Antworten.
Ich habe HIER mal eine Kopie der Aufgabe aus meinem Skript hochgeladen.
Das $\begin{eqnarray*} n \end{eqnarray*}$ steht für die Eingabelänge eines Codes, also ist nach meinem Verständniss $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$ .

@Leopold wie kommst du im letzten Schritt auf $\begin{eqnarray*} (c-4) \end{eqnarray*}$ ? Das c erhälst du durch $\begin{eqnarray*} T(4^k/4^k)=T(1) \end{eqnarray*}$ richtig?

Ich glaube ich muss erstmal das rechnen mit logarithmen üben. Habe da noch nicht so viel erfahrung mit.

23.08.2012, 15:25

Hungriger Hugo

Auf diesen Beitrag antworten »

Habe die Aufgabe inzwischen mithilfe eines Rekursionsbaumes gelöst. Unser Skript ist so schlecht aufgebaut, dass die notwendigen Mittel zum lösen der Aufgabe erst später eingeführt wurden.

Neue Frage »

Antworten »

Rekursionsgleichung: Substitutionsmethode

Verwandte Themen