Gauß Rücksubstitution: Anzahl Additionen beziehungsweise Subtraktionen bei Schleife bestimmen

Question

in meinem Skript steht das:

für i = n, ..., 1:

    \(x_i = (b_i  - \sum\limits_{j=i+1}^{n}{a_{i,j}x_j})/a_{i,i} \)

Betrachten wir nun auch die Kosten für die Rücksubstitution.

Davon haben wir in Schleifendurchlauf i gerade n−i Additionen/Subtraktionen, genau so viele Multiplikationen und eine Division.

Aber ich habe doch n-(i+1) Multiplikationen durch die Summe. Woher kommen die n-i Additionen beziehungsweise Subtraktionen?

Danke im Voraus:)

Answer 1

Aber ich habe doch n-(i+1) Multiplikationen durch die Summe.

Sagen wir, j läuft von 5 bis 10. Wie viele Summanden sind das?

Antwort: 6 Summanden  (und bei jedem Summand eine Multiplikation). die 6 Summanden zählst du nacheinander oder gleichzeitig von bi ab. Daher auch 6 Additionen oder Subtraktionen.

[spoiler]

6 = 10 - 5 +1 Summanden

Nun stattdessen: j läuft von 5 = i+1 bis 10 =n.

Somit n - (i+1) + 1 = n-i Summanden.