Linear equations Flashcards
What is the general question for linear equations?
How do we solve Ax = b
What do we assume about A in this chapter?
A is square, non singular and therefore there is a unique solution.
Why is solving linear equations non-trivial?
- May be unstable to rounding error - pivoting
- n may be very large - iterative algorithms
What are five basic facts for linear algebra you need to know?
What are lower triangualr matrices?
All zeros above the diagonal
What are upper triangular matrices?
All zeros below diagonal
How can you tell if a lower triangular matrix is non-singular?
All diagonal elements are non-zero
What type of substitution can any lower triangular system by solved by?
Forward substitution.
What is the formula for forward substitution?
What is the formula for backward substitution?
What is the number of operations required for forward substituion?
n2
Prove that the number of operations for forward substitution is n2.
What is another way to say how many operations something takes?
Computational complexity of the algorithm
What process can you use to transform a system to upper triangular?
Gaussian elimination
What does Gaussian elimination use to transform a system to upper triangular?
Elementary row operations
What is the algorithm for Gaussian elimination?
Show what the computational cost of Gaussian elimination is?
What equation shows how the sequence of row operations that transform A to U is equivalent to left-multiplying by a matrix F.
Prove that the sequence of row operations that transforms A to U is equivalent to left-multiplying by a matrix F such that
What is the theorem about LU decompostion?
What does unit lower triangular mean?
All 1’s on the diagonal and 0’s above
What two systems do we have to solve in LU decomposition?
Why is it better to use LU decomposition over Gaussian elimination?
Requires fewer operations
When will Gaussian elimination and LU factorisation fail?
When there is a zero on the diagonal
What process can you do to stop there being zeros on the diagonal?
Pivotting
What is pivoting?
Swapping rows and columns
What is partial pivoting?
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).
What is the purpose of partial pivoting?
To avoid large multipliers, to dramatically improve the stability of Gaussian elimination
How do you attain ultimate accuray in G.E. ?
If pivoting is applied, what equation shows the modified factorisation form?
What does P stand for in the following?
Permuation matrix - every row and column has exactly one non-zero element, which is 1.
What two systems do we solve when we have used a permuation matrix in G.E.?
Define a vector norm.
Define the l2-norm.
Define the l1 norm.
Define the l∞-nrom.
Define the lp norm.
What do the unit circles look like for the l1, l2 and l∞ norm?
What to do use to measure the size of matrices?
Matrix norms.
What do we use to measure the error when the solution is a vector?
A norm
Define a matrix norm.
What is the most important matrix norm?
Induced or operator norms
What do induced/operator norms measure?
How much Ax stretches x in some vector norm.
Define an induced norm.
What is the theorem about the inequality between vector and matrix norm?
Prove the following theorem.
Finish the following theorm.
Prove the following theorem.
Finish the following theorem.
What is the matrix norm induced by the l2 norm also known as?
The spectral norm.
What is p(A)?
The spectral radius of A - the maximum |λ| over all eigenvalues λ of A.
Prove the following theorem.
When do you call a solution well-conditioned?
When the solution is within rounding error of the true solution.
When do a call a solution ill-conditioned?
When a system is very sensitive to errors in b
When measuring the conditioning of a linear system, what inquality can you produce to measure the relative error in x compared to b.
Define the condition number.
What does a large value of κ٭(a) mean?
- The solution will be sensitive to errors in b
- The matrix is close to being non-invertible
When is a matrix A called symmetric positive definite (or SPD)?
What value do the eigenvalues of a matrix A have to take so that the matrix is positive definite?
Positive
What is the minimizing function we look at to solve Ax = b?
What is the main type of optimsiation we look at?
Line search methods
What is the general equation for a line search method?
What does dk and αk stand for in the following?
- dk is the search direction
- αk is the step size
How is αk chosen in line search methods?
What is the residual vector rk?
What is the formula for step size, αk?
What are the two methods for the search direction?
- Method of steepest descent
- Conjugate gradient method
What is the formula for the search direction, dk, in the method of steeoest descent?
Which search direciton method is slower to converge?
The method of steepest descent
What is d0 in the conjugate gradient method?
-r0
What is the formula for the search direction using the conjugate gradient method?
What is the equation for βk in the following formula for the search direction in the conjugate gradient method?
What is the algorithm for the conjugate gradient method?
How many iterations does the conjuaget gradient method need to give the exact answer? And why?
n, because
What is the theorem about the residuals in the conjugate gradient method.
Prove the following theorem.
See problem sheet
Give three reasons why conjugate gradients methods are not as good as a direct method in practice.
- Computationally intensive
- Rounding erros can destroy orthogonality
- Meaning you may need more than n iterations
When is the conjuagte gradient method mainly used?
For large sparse systems
