Linear equations

Question 1

What is the general question for linear equations?

Answer 1

How do we solve Ax = b

Question 2

What do we assume about A in this chapter?

Answer 2

A is square, non singular and therefore there is a unique solution.

Question 3

Why is solving linear equations non-trivial?

Answer 3

1. May be unstable to rounding error - pivoting
2. n may be very large - iterative algorithms

Question 4

What are five basic facts for linear algebra you need to know?

Answer 4

Question 5

What are lower triangualr matrices?

Answer 5

All zeros above the diagonal

Question 6

What are upper triangular matrices?

Answer 6

All zeros below diagonal

Question 7

How can you tell if a lower triangular matrix is non-singular?

Answer 7

All diagonal elements are non-zero

Question 8

What type of substitution can any lower triangular system by solved by?

Answer 8

Forward substitution.

Question 9

What is the formula for forward substitution?

Answer 9

Question 10

What is the formula for backward substitution?

Answer 10

Question 11

What is the number of operations required for forward substituion?

Answer 11

n²

Question 12

Prove that the number of operations for forward substitution is n².

Answer 12

Question 13

What is another way to say how many operations something takes?

Answer 13

Computational complexity of the algorithm

Question 14

What process can you use to transform a system to upper triangular?

Answer 14

Gaussian elimination

Question 15

What does Gaussian elimination use to transform a system to upper triangular?

Answer 15

Elementary row operations

Question 16

What is the algorithm for Gaussian elimination?

Answer 16

Question 17

Show what the computational cost of Gaussian elimination is?

Answer 17

Question 18

What equation shows how the sequence of row operations that transform A to U is equivalent to left-multiplying by a matrix F.

Answer 18

Question 19

Prove that the sequence of row operations that transforms A to U is equivalent to left-multiplying by a matrix F such that

Answer 19

Question 20

What is the theorem about LU decompostion?

Answer 20

Question 21

What does unit lower triangular mean?

Answer 21

All 1’s on the diagonal and 0’s above

Question 22

What two systems do we have to solve in LU decomposition?

Answer 22

Question 23

Why is it better to use LU decomposition over Gaussian elimination?

Answer 23

Requires fewer operations

Question 24

When will Gaussian elimination and LU factorisation fail?

Answer 24

When there is a zero on the diagonal

Question 25

What process can you do to stop there being zeros on the diagonal?

Answer 25

Pivotting

Question 26

What is pivoting?

Answer 26

Swapping rows and columns

Question 27

What is partial pivoting?

Answer 27

Interchange a pair of rows at each stgae k of the G.E. to being the largest element a_ik^(k) (for k ≤ i ≤ n) to the diagonal position a_kk^(k).

Question 28

What is the purpose of partial pivoting?

Answer 28

To avoid large multipliers, to dramatically improve the stability of Gaussian elimination

Question 29

How do you attain ultimate accuray in G.E. ?

Answer 29

Question 30

If pivoting is applied, what equation shows the modified factorisation form?

Answer 30

Question 31

What does P stand for in the following?

Answer 31

Permuation matrix - every row and column has exactly one non-zero element, which is 1.

Question 32

What two systems do we solve when we have used a permuation matrix in G.E.?

Answer 32

Question 33

Define a **vector norm.**

Answer 33

Question 34

Define the **l₂-norm.**

Answer 34

Question 35

Define the **l₁ norm**.

Answer 35

Question 36

Define the **l_∞-nrom.**

Answer 36

Question 37

Define the **l_p norm**.

Answer 37

Question 38

What do the unit circles look like for the l₁, l₂ and l_∞ norm?

Answer 38

Question 39

What to do use to measure the size of matrices?

Answer 39

Matrix norms.

Question 40

What do we use to measure the error when the solution is a vector?

Answer 40

A norm

Question 41

Define a **matrix norm.**

Answer 41

Question 42

What is the most important matrix norm?

Answer 42

Induced or operator norms

Question 43

What do induced/operator norms measure?

Answer 43

How much A**x** stretches **x** in some vector norm.

Question 44

Define an induced norm.

Answer 44

Question 45

What is the theorem about the inequality between vector and matrix norm?

Answer 45

Question 46

Prove the following theorem.

Answer 46

Question 47

Finish the following theorm.

Answer 47

Question 48

Prove the following theorem.

Answer 48

Question 49

Finish the following theorem.

Answer 49

Question 50

What is the matrix norm induced by the l₂ norm also known as?

Answer 50

The spectral norm.

Question 51

What is p(A)?

Answer 51

The spectral radius of A - the maximum |λ| over all eigenvalues λ of A.

Question 52

Prove the following theorem.

Answer 52

Question 53

When do you call a solution well-conditioned?

Answer 53

When the solution is within rounding error of the true solution.

Question 54

When do a call a solution ill-conditioned?

Answer 54

When a system is very sensitive to errors in **b**

Question 55

When measuring the conditioning of a linear system, what inquality can you produce to measure the relative error in **x** compared to **b**.

Answer 55

Question 56

Define the **condition number.**

Answer 56

Question 57

What does a large value of κ_٭(a) mean?

Answer 57

* The solution will be sensitive to errors in **b** * The matrix is close to being non-invertible

Question 58

When is a matrix A called symmetric positive definite (or SPD)?

Answer 58

Question 59

What value do the eigenvalues of a matrix A have to take so that the matrix is positive definite?

Answer 59

Positive

Question 60

What is the minimizing function we look at to solve A**x** = **b**?

Answer 60

Question 61

What is the main type of optimsiation we look at?

Answer 61

Line search methods

Question 62

What is the general equation for a line search method?

Answer 62

Question 63

What does **d**_k and α_k stand for in the following?

Answer 63

* **d**_k is the search direction * α_k is the step size

Question 64

How is α_k chosen in line search methods?

Answer 64

Question 65

What is the residual vector **r**_k?

Answer 65

Question 66

What is the formula for step size, α_k?

Answer 66

Question 67

What are the two methods for the search direction?

Answer 67

1. Method of steepest descent 2. Conjugate gradient method

Question 68

What is the formula for the search direction, **d**_k, in the method of steeoest descent?

Answer 68

Question 69

Which search direciton method is slower to converge?

Answer 69

The method of steepest descent

Question 70

What is **d**₀ in the conjugate gradient method?

Answer 70

-**r**₀

Question 71

What is the formula for the search direction using the conjugate gradient method?

Answer 71

Question 72

What is the equation for β_k in the following formula for the search direction in the conjugate gradient method?

Answer 72

Question 73

What is the algorithm for the conjugate gradient method?

Answer 73

Question 74

How many iterations does the conjuaget gradient method need to give the exact answer? And why?

Answer 74

n, because

Question 75

What is the theorem about the residuals in the conjugate gradient method.

Answer 75

Question 76

Prove the following theorem.

Answer 76

See problem sheet

Question 77

Give three reasons why conjugate gradients methods are not as good as a direct method in practice.

Answer 77

1. Computationally intensive 2. Rounding erros can destroy orthogonality 3. Meaning you may need more than n iterations

Question 78

When is the conjuagte gradient method mainly used?

Answer 78

For large sparse systems