4) Itervative Methods for Solving Linear Systems Flashcards
What is the Reaction-Diffusion Problem
How do you implement the Centred Finite Difference approximation
Describe the matrix in the Centred Finite Difference Scheme if r(x) and the boudary conditions are 0
Describe the eigenvalues of the finite difference approximation matrix using a cos approximation
What is Jacobi Iteration
What is Gauss-Seidel Iteration
What defines the error in Jacobi or Gauss-Seidel iterative methods
How many operations are required to perform one iteration of Gauss-Seidel iteration on Ax = b
O(n^2)
What is the residual
What condition determines a solution in Jacobi or Gauss-Seidel methods
In both Jacobi and Gauss-Seidel methods, a vector
x is a solution to the linear system Ax=b if and only if it is a fixed point of the iteration. This means that x satisfies the equation: x=Tx+c
Describe the proof that in both Jacobi and Gauss-Seidel methods, a vector x is a solution to Ax=b if and only if it is a fixed point of the iteration
How is the error progression formulated in Jacobi and Gauss-Seidel iterations
What is a vector norm
What are the three most commonly used vector norms
What does it mean fora sequence of vectors to converge with respect to a vector norm
What is the relationship between the infinity norm and the 2-norm of a vector in Rn
Describe the proof of
What is the relationship between convergence in the 2-norm and convergence in the infinity norm
Describe the proof that convergence in the 2-norm is equivalent to convergence in the infinity norm
What is a matrix norm
What is the definition of a matrix norm induced by a vector norm
Describe the proof that
If ∥·∥ is a vector norm, then what do we know about ∥A∥
Let ∥A∥ be the induced matrix norm, show that ∥A + B∥ ≤ ∥A∥ + ∥B∥
Let ∥A∥ be the induced matrix norm, show that ∥AB∥ ≤ ∥A∥∥B∥
What are the norms induced by the vector 1-norms and ∞-norms
What is the spectral radius of a matrix
How do you find the eigenvalues of a matrix
What is the 2-norm of a matrix
What is the 2-norm of a symmetric matrix
Assume D + L is non-singular and consider the Gauss-Seidel iteration matrix T = −(D + L) −1U.
Show that λ is an eigenvalue of T if and only if det(λ(D + L) + U) = 0
Describe the proof that
Show that for the induced matrix norm ∥A∥, we always have ∥A∥ ≥ ρ(A).
We have Ax = λx
We have ∥Ax∥ = ∥λx∥ = |λ|∥x∥
Then, using a property of the induced matrix norm, we have ∥Ax∥ ≤ ∥A∥ ∥x∥.
Hence |λ|∥x∥≤ ∥A∥ ∥x∥
Since eigenvectors are non-zero, ∥x∥ ̸= 0 and so |λ| ≤ ∥A∥
p(A) is the maximum λ so p(a) ≤ ∥A∥
What is the relationship between the error at the
k-th iteration and the initial error in an iterative method for solving Ax=b using x^k+1 = T x^k +c
Describe the proof that
What are the conditions for the sequence x^k in an iterative method to converge to a fixed point x satisfying x = T x+c, with respect to the chosen norm vector ∥·∥
- Vector Norm Condition: If ∥T ∥ < 1
- Spectral Radius Condition: If and only if p(T) < 1 the x^k iterates converge for all starting points x0
Describe the proof that if ∥T ∥ < 1then the sequence x^k , k ≥ 0, converges to a fixed point x satisfying x = T x+c, with respect to the chosen norm vector ∥·∥
Describe the proof that x^k iterates converge for all starting points x^0 if and only if p(T) < 1
What is Gershgorin’s Circle Theorem
Describe the proof of Gershgorin’s Circle Theorem
What does it mean to be diagonally dominant
If a matrix A is diagonally dominant what does that impy about its convergence
Let A be diagonally dominant. Then the Jacobi method converges to a solution of the system Ax = b for any starting point x^0
Describe the proof that if A is diagonally dominant then the Jacobi method converges to a solution of the system Ax = b for any starting point x0
What is the condition number of a matrix A
Let ∥·∥ be a matrix norm and let A an invertible matrix.
The condition number of A is defined as cond(A) := ∥A∥· ∥A^−1∥
Explain the importance of the condition number of a linear system
- The condition number measures the sensitivity of a linear system to changes in input data. A high condition number indicates potential large changes in the solution for small perturbations
- A high condition number suggests a higher likelihood of significant errors due to rounding and truncation
What is the relationship between the error, residual, and condition number in iterative methods
Describe the proof that cond(A) ≥ 1 for any matrix A
