Uppgift 6

Annika vill lösa ett linjärt ekvationssystem $Ax = b.$ Beräkning av ett element i vektorn b görs med ett komplicerat program och tar 0.04 sekunder. Hon har en naiv version av gausseliminering tillgänglig, och när hon löser ett ekvationssystem med den naiva lösaren för en n × n-matris med $n = 100$ tar beräkningen 1 sekund (exklusive beräkning av b). Hon vill nu balansera beräkningarna, så att beräkningen av b tar ungefär lika lång tid som lösningen av ekvationssystemet. Hur stort n ska hon välja? Gör uppskattningar med flop-count och det förenklande antagandet att O(n^□) kan ersättas med αn^□.