Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Numerical - Epiphany > Linear equations > Flashcards

Linear equations Flashcards

1
Q

What is the general question for linear equations?

A

How do we solve Ax = b

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What do we assume about A in this chapter?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Why is solving linear equations non-trivial?

A
  1. May be unstable to rounding error - pivoting
  2. n may be very large - iterative algorithms
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are lower triangualr matrices?

A

All zeros above the diagonal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What are upper triangular matrices?

A

All zeros below diagonal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

All diagonal elements are non-zero

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

Forward substitution.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the formula for forward substitution?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the formula for backward substitution?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the number of operations required for forward substituion?

A

n2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Prove that the number of operations for forward substitution is n2.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

Computational complexity of the algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

Gaussian elimination

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

Elementary row operations

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is the algorithm for Gaussian elimination?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Show what the computational cost of Gaussian elimination is?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is the theorem about LU decompostion?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What does unit lower triangular mean?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

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

A

Requires fewer operations

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

When will Gaussian elimination and LU factorisation fail?

A

When there is a zero on the diagonal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

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

A

Pivotting

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is pivoting?

A

Swapping rows and columns

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is partial pivoting?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

What is the purpose of partial pivoting?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

What does P stand for in the following?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

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

A
33
Q

Define a vector norm.

A
34
Q

Define the l2-norm.

A
35
Q

Define the l1 norm.

A
36
Q

Define the l∞-nrom.

A
37
Q

Define the lp norm.

A
38
Q

What do the unit circles look like for the l1, l2 and l∞ norm?

A
39
Q

What to do use to measure the size of matrices?

A

Matrix norms.

40
Q

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

A

A norm

41
Q

Define a matrix norm.

A
42
Q

What is the most important matrix norm?

A

Induced or operator norms

43
Q

What do induced/operator norms measure?

A

How much Ax stretches x in some vector norm.

44
Q

Define an induced norm.

A
45
Q

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

A
46
Q

Prove the following theorem.

A
47
Q

Finish the following theorm.

A
48
Q

Prove the following theorem.

A
49
Q

Finish the following theorem.

A
50
Q

What is the matrix norm induced by the l2 norm also known as?

A

The spectral norm.

51
Q

What is p(A)?

A

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

52
Q

Prove the following theorem.

A
53
Q

When do you call a solution well-conditioned?

A

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

54
Q

When do a call a solution ill-conditioned?

A

When a system is very sensitive to errors in b

55
Q

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

A
56
Q

Define the condition number.

A
57
Q

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

A
  • The solution will be sensitive to errors in b
  • The matrix is close to being non-invertible
58
Q

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

A
59
Q

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

A

Positive

60
Q

What is the minimizing function we look at to solve Ax = b?

A
61
Q

What is the main type of optimsiation we look at?

A

Line search methods

62
Q

What is the general equation for a line search method?

A
63
Q

What does dk and αk stand for in the following?

A
  • dk is the search direction
  • αk is the step size
64
Q

How is αk chosen in line search methods?

A
65
Q

What is the residual vector rk?

A
66
Q

What is the formula for step size, αk?

A
67
Q

What are the two methods for the search direction?

A
  1. Method of steepest descent
  2. Conjugate gradient method
68
Q

What is the formula for the search direction, dk, in the method of steeoest descent?

A
69
Q

Which search direciton method is slower to converge?

A

The method of steepest descent

70
Q

What is d0 in the conjugate gradient method?

A

-r0

71
Q

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

A
72
Q

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

A
73
Q

What is the algorithm for the conjugate gradient method?

A
74
Q

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

A

n, because

75
Q

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

A
76
Q

Prove the following theorem.

A

See problem sheet

77
Q

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

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

When is the conjuagte gradient method mainly used?

A

For large sparse systems

Numerical - Epiphany (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions