Beweise < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 20:15 Mi 10.05.2006 | | Autor: | Lee1601 |
| Aufgabe 1 | (2) Eine Matrix A = (aij)1<=i;j<=n 2 heißt (Spalten-)stochastisch, falls:
(i) aij >= 0, 1 <= i; j <= n,
(ii) [mm] \summe_{i=1}^{n}aij [/mm] = 1, 1 <= j <= n.
Zeigen Sie: Eine stochastische Matrix hat einen Eigenvektor zum Eigenwert
1
(als Hinweis geg: [mm] \lambda [/mm] eigenwert von A genau dann wenn /lambda eigenwert von A transponiert)
|
| Aufgabe 2 | (3) Wie funktioniert Google? Im Folgenden geben wir eine sehr grobe Beschreibung, wie eine Suchmaschine wie Google Webseiten bewertet.
Wir betrachten die Menge W = (w1,...,wn) von Websites. Die Frage ist
nun, welche dieser Websites die "Wichtigste" ist? Sei li die Anzahl der
Links auf der Website wi zu Websites wj für i [mm] \not= [/mm] j. Dann bauen wir eine
Matrix A = (aij)1<=i;j<=n aus [mm] R^n [/mm] mit Einträgen aij = 1/lj , falls ein Link
von Website wj zu Website wi deutet, und aij = 0 sonst. Aus gewissen
Gründen, die mit Störungen zu tun haben, die von Websites erzeugt werden, die keinen einzigen Link enthalten, perturbiert man die Matrix A nun noch:
Sei N = (nij)1<=i;j<=n die Matrix mit Einträgen nij := 1/n. Für ein 0 < p < 1
betrachtet man die Matrix Bp = pA + (1-p)N
(i) Zeigen Sie: Bp ist eine stochastische Matrix. (Bed. siehe vorherige Aufgabe)
Aus (i) und Aufgabe 2 folgt, dass Bp die 1 als Eigenwert besitzt. Man kann
zeigen, dass für eine (irreduzible) stochastische Matrix C gilt
dim Eig1(C) = 1:
Dabei heißt eine quadratische Matrix C irreduzibel, wenn ein l > 0 existiert,
so dass jeder Eintrag von [mm] C^l [/mm] echt größer 0 ist.
(ii) Zeigen Sie: Bp ist irreduzibel.
|
Sodale, hier bin ich mal wieder (leider)!
Bei den angegebenen Aufgaben komme ich nicht so ganz weiter.
zu Aufgabe 2: ich habe mir die eigenschaften von eigenvektoren aufgeschrieben und auch die matrix und den gesuchten eigenvektor in allgemeiner form hingeschrieben also A*v=v. dann hab ich angefangen, die gleichungen, die man bei der multiplikation lösen muss aufzuschreiben, aber das bringt mich auch nicht weiter. und wie soll man den hinweis verarbeiten??
zu Aufgabe 3:
(i) die bedingung, dass alle einträge >= 0 sein müssen habe ich schon gezeigt, aber wie zeige ich, dass die summe der einträge 1 ergibt (die einträge sind ja nicht grade "unkompliziert")? habe das ganze schon in ne gleichung geschrieben, die 1 ergeben soll, aber man hat ja so viele unbekannte, wie mach ich das?
(ii) hier weiß ich nicht, wie ich zeige, dass die einträge alle echt > als 0 sein sollen. dass sie >= 0 sind, ist klar, aber das andere...
Ich hoffe mal wieder, dass mir jemand die entscheidenden dinge für die lösung erklären kann!
Vielen lieben Dank!
lg
Linda
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:29 Mi 10.05.2006 | | Autor: | Lee1601 |
Lasst euch von der Aufgabenstellung (bitte) nicht abschrecken - ich weiß, die ist sehr sehr lang, aber die Fragen an sich sind kurz und knapp!
DANKE!
|
|
|
| |
|
> (2) Eine Matrix A = (aij)1<=i;j<=n 2 heißt
> (Spalten-)stochastisch, falls:
> (i) aij >= 0, 1 <= i; j <= n,
>
> (ii) [mm]\summe_{i=1}^{n}aij[/mm] = 1, 1 <= j <= n.
>
> Zeigen Sie: Eine stochastische Matrix hat einen Eigenvektor
> zum Eigenwert
> 1
> (als Hinweis geg: [mm]\lambda[/mm] eigenwert von A genau dann wenn
> /lambda eigenwert von A transponiert)
>
>
> (3) Wie funktioniert Google? Im Folgenden geben wir eine
> sehr grobe Beschreibung, wie eine Suchmaschine wie Google
> Webseiten bewertet.
> Wir betrachten die Menge W = (w1,...,wn) von Websites. Die
> Frage ist
> nun, welche dieser Websites die "Wichtigste" ist? Sei li
> die Anzahl der
> Links auf der Website wi zu Websites wj für i [mm]\not=[/mm] j.
> Dann bauen wir eine
> Matrix A = (aij)1<=i;j<=n aus [mm]R^n[/mm] mit Einträgen aij = 1/lj
> , falls ein Link
> von Website wj zu Website wi deutet, und aij = 0 sonst.
> Aus gewissen
> Gründen, die mit Störungen zu tun haben, die von Websites
> erzeugt werden, die keinen einzigen Link enthalten,
> perturbiert man die Matrix A nun noch:
> Sei N = (nij)1<=i;j<=n die Matrix mit Einträgen nij :=
> 1/n. Für ein 0 < p < 1
> betrachtet man die Matrix Bp = pA + (1-p)N
>
> (i) Zeigen Sie: Bp ist eine stochastische Matrix. (Bed.
> siehe vorherige Aufgabe)
>
> Aus (i) und Aufgabe 2 folgt, dass Bp die 1 als Eigenwert
> besitzt. Man kann
> zeigen, dass für eine (irreduzible) stochastische Matrix C
> gilt
> dim Eig1(C) = 1:
> Dabei heißt eine quadratische Matrix C irreduzibel, wenn
> ein l > 0 existiert,
> so dass jeder Eintrag von [mm]C^l[/mm] echt größer 0 ist.
>
> (ii) Zeigen Sie: Bp ist irreduzibel.
>
>
> Sodale, hier bin ich mal wieder (leider)!
>
> Bei den angegebenen Aufgaben komme ich nicht so ganz
> weiter.
>
>
> zu Aufgabe 2: ich habe mir die eigenschaften von
> eigenvektoren aufgeschrieben und auch die matrix und den
> gesuchten eigenvektor in allgemeiner form hingeschrieben
> also A*v=v. dann hab ich angefangen, die gleichungen, die
> man bei der multiplikation lösen muss aufzuschreiben, aber
> das bringt mich auch nicht weiter. und wie soll man den
> hinweis verarbeiten??
>
Naja, was gilt bei einer stochastischen Matrix? Summiert man in einer Spalte alle Einträge so erhält man 1. Und das gilt für jede Spalte. Das heißt für [mm] A^T [/mm] gilt das analoge für Zeilen. Mit welchem Vektor musst du [mm] A^T [/mm] multiplizieren, so dass im Vektor A^Tv jeweils die Summe der Zeileneinträge steht. Hoffe, das hilft dir.
Aufgabe 3 ist mir ehrlich zu lang 
> zu Aufgabe 3:
> (i) die bedingung, dass alle einträge >= 0 sein müssen habe
> ich schon gezeigt, aber wie zeige ich, dass die summe der
> einträge 1 ergibt (die einträge sind ja nicht grade
> "unkompliziert")? habe das ganze schon in ne gleichung
> geschrieben, die 1 ergeben soll, aber man hat ja so viele
> unbekannte, wie mach ich das?
>
> (ii) hier weiß ich nicht, wie ich zeige, dass die einträge
> alle echt > als 0 sein sollen. dass sie >= 0 sind, ist
> klar, aber das andere...
>
> Ich hoffe mal wieder, dass mir jemand die entscheidenden
> dinge für die lösung erklären kann!
>
> Vielen lieben Dank!
>
> lg
>
> Linda
>
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:20 Fr 12.05.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
