WisFaq!

Operaties

Beste, hoe kan men bewijzen dat het aantal benodigde vermenigvuldigingen en delingen bij (algemeen) een n*n- matrix voor het berekenen van de inverse ongeveer gelijk is aan n^3.

Of, gelijkaardige vraag, hoe kan men bewijzen dat de hoeveelheid bewerkingen (bij Gauss-eliminatie) ongeveer n^3/3 is.

Ik denk dat dit in het algemeen een probleem is van numerieke wiskunde, kunt u even kort ingaan hoe men in het algemeen de hoe-grootheid van het aantal bewekingen van algoritmes kan berekenen ;

bij voorbaat dank ;

Tom
7-11-2008

Antwoord

Gewoon: tellen.

• Eén rijoperatie kost n vermenigvuldigingen en optellingen.
  
• Eén kolom schoonvegen kost n-1 rijoperaties
  
• Er zijn n kolommen.
  

Bij Gauss-eliminatie is het aantal vermenigvuldigingen als je in de k-de kolom bezig bent gelijk aan n-k+1; dat geeft de factor 1/3.

kphart
12-11-2008