Vårt problem är att beräkna en approximation till det största eigenvärdet av en n x n stor symmetrisk positiv definitiv matris med relativa fel som mest c. Vi anser endast algoritmer som använder Krylov inforrpation [b, Ab,. .., Akb] bestående av k matris-vektor multiplikationer för vissa enhet vektor b. Om vektorn b väljs deterministiskt kan problemet inte lösas oavsett hur många matris-vektor multiplikationer som utförs och vilken algoritm som används. Om emellertid vektorn b väljs slumpmässigt med avseende på den enhetliga fördelningen över enhetssfären, kan problemet lösas i genomsnitt och probabilistiskt. Mer exakt, för en slumpmässigt vald vektor b studerar vi kraften och Lanczos algoritmer. För kraftalgoritmen (metod) visar vi skarpa gränser på det genomsnittliga relativa felet och på det probabilistiska relativa felet. För Lanczos algoritm presenterar vi endast övre gränser. I synnerhet karakteriserar In(n)Jk det genomsnittliga relativa felet hos effektalgoritmen, medan O(ln(n)jk)l är en övre gräns för det genomsnittliga relativa felet hos Lanczos-algoritmen. I det probabilistiska fallet kännetecknas algoritmen av dess probabilistiska relativa fel som definieras som måttet på den uppsättning vektorer b för vilka algoritmen misslyckas. Vi visar att den probabilistiska släktingen ·Stöds delvis av National Science Foundation under Grant DCR-86-03674. 1 fel går till noll ungefär som vIn(l-c)k för effektalgoritmen och högst som..;n e-(2k-1)y'i för Lanczos algoritm. Dessa gränser är för en värsta fallfördelning av eigenvärden som kan bero på k. vVe också studera beteendet i genomsnitt och probabilistiska fall av de två algoritmerna för en fast matris A som antalet matris-vektor multiplikationer k ökar. Gränserna för kraftalgoritmen beror sedan på förhållandet mellan de två största eigenvärdena och deras mångfald. Gränserna för Lanczos-algoritmen beror på förhållandet mellan skillnaden mellan de två största eigenvärdena och skillnaden mellan de största och de minsta eigenvärdena.
Lanczos metoden kan minska antalet matris-vektor produkter ännu mer REF.
Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
{'venue': 'SIAM J. Matrix Analysis Applications', 'journal': 'SIAM J. Matrix Analysis Applications', 'mag_field_of_study': ['Computer Science', 'Mathematics']}