Week 4

Question 1

How to solve linear equation using back substitution?

Answer 1

If we have a diagonal matrix, then we can easily solve the first one. Then we can fill the value in in the row above, and continue from there.

I.e.

1. Prepare space for the solution x = (x1, …, xn)
2. Solve starting at i = n
3. Calculate the remaining sum: s.i = sum j >I a.ij * xj, where the sum is defined as s.i = 0 if I = n
4. Compute solution xi = (bi-si)/aii
5. Decrease I, repeat from 3 while i > 0

Question 2

How does Gaussian elimination work?

Answer 2

1. Set i =1
2. Wipe column I below pivot a.ii by:
3. 1. Set j = i + 1
4. 2 Calculate multiplicity f = a.ji/a.ii
5. 3 Subtract f times row I from row j: a’.jk = a jk - f a/ik, k ≥ I
6. 4 Increase j, if j ≤ n goto 2
7. Increase I, if i ≤ n - 1 goto step 2

Question 3

What is a trivial pivot?

Answer 3

When you swap rows when needed

Question 4

What is a partial pivot?

Answer 4

When you swap rows to get larger (absolute) pivot in this column

Question 5

What is complete pivoting?

Answer 5

When you swap rows and columns to get the largest absolute pivot from the remaining submatrix. (This is not recommended, the gain is small, but it requires much more work.)

Question 6

What’s scaled partial pivoting?

Answer 6

Swapping rows to get the largest absolute relative pivot in this column.

Question 7

How to partial pivot?

Answer 7

1. Jet j* = i
2. For j in i + 1,.., n
   - If |a.ji| > |a.jI| then j = j
   - Use j* for optimal row

Question 8

Why scale partial pivot?

Answer 8

If factor f leads to a large subtraction factor, large rounding errors may accumulate.

Question 9

How to Scaled Partial Pivot?

Answer 9

1. Find s.j = max 1≤k≤n |a.jk.^(0)|, j = 1, …, n^1.
2. Choose pivot a.ki^(i -1) with k = argmax i≤j≤n (a.ji^(i-1))/(s.j)
3. Use a.ki^(i-1) as the pivot for eliminating th ei-th column