4) Itervative Methods for Solving Linear Systems

Question 1

What is the Reaction-Diffusion Problem

Answer 1

Question 2

How do you implement the Centred Finite Difference approximation

Answer 2

Question 3

Describe the matrix in the Centred Finite Difference Scheme if r(x) and the boudary conditions are 0

Answer 3

Question 4

Describe the eigenvalues of the finite difference approximation matrix using a cos approximation

Answer 4

Question 5

What is Jacobi Iteration

Answer 5

Question 6

What is Gauss-Seidel Iteration

Answer 6

Question 7

What defines the error in Jacobi or Gauss-Seidel iterative methods

Answer 7

Question 8

How many operations are required to perform one iteration of Gauss-Seidel iteration on Ax = b

Answer 8

O(n^2)

Question 9

What is the residual

Answer 9

Question 10

What condition determines a solution in Jacobi or Gauss-Seidel methods

Answer 10

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

Question 11

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

Answer 11

Question 12

How is the error progression formulated in Jacobi and Gauss-Seidel iterations

Answer 12

Question 13

What is a vector norm

Answer 13

Question 14

What are the three most commonly used vector norms

Answer 14

Question 15

What does it mean fora sequence of vectors to converge with respect to a vector norm

Answer 15

Question 16

What is the relationship between the infinity norm and the 2-norm of a vector in Rn

Answer 16

Question 17

Describe the proof of

Answer 17

Question 18

What is the relationship between convergence in the 2-norm and convergence in the infinity norm

Answer 18

Question 19

Describe the proof that convergence in the 2-norm is equivalent to convergence in the infinity norm

Answer 19

Question 20

What is a matrix norm

Answer 20

Question 21

What is the definition of a matrix norm induced by a vector norm

Answer 21

Question 22

Describe the proof that

Answer 22

Question 23

If ∥·∥ is a vector norm, then what do we know about ∥A∥

Answer 23

Question 24

Let ∥A∥ be the induced matrix norm, show that ∥A + B∥ ≤ ∥A∥ + ∥B∥

Answer 24

Question 25

Let ∥A∥ be the induced matrix norm, show that ∥AB∥ ≤ ∥A∥∥B∥

Answer 25

Question 26

What are the norms induced by the vector 1-norms and ∞-norms

Answer 26

Question 27

What is the spectral radius of a matrix

Answer 27

Question 28

How do you find the eigenvalues of a matrix

Answer 28

Question 29

What is the 2-norm of a matrix

Answer 29

Question 30

What is the 2-norm of a symmetric matrix

Answer 30

Question 31

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

Answer 31

Question 32

Describe the proof that

Answer 32

Question 33

Show that for the induced matrix norm ∥A∥, we always have ∥A∥ ≥ ρ(A).

Answer 33

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∥

Question 34

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

Answer 34

Question 35

Describe the proof that

Answer 35

Question 36

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 ∥·∥

Answer 36

• 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

Question 37

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 ∥·∥

Answer 37

Question 38

Describe the proof that x^k iterates converge for all starting points x^0 if and only if p(T) < 1

Answer 38

Question 39

What is Gershgorin’s Circle Theorem

Answer 39

Question 40

Describe the proof of Gershgorin’s Circle Theorem

Answer 40

Question 41

What does it mean to be diagonally dominant

Answer 41

Question 42

If a matrix A is diagonally dominant what does that impy about its convergence

Answer 42

Let A be diagonally dominant. Then the Jacobi method converges to a solution of the system Ax = b for any starting point x^0

Question 43

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

Answer 43

Question 44

What is the condition number of a matrix A

Answer 44

Let ∥·∥ be a matrix norm and let A an invertible matrix.
The condition number of A is defined as cond(A) := ∥A∥· ∥A^−1∥

Question 45

Explain the importance of the condition number of a linear system

Answer 45

• 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

Question 46

What is the relationship between the error, residual, and condition number in iterative methods

Answer 46

Question 47

Describe the proof that cond(A) ≥ 1 for any matrix A

Answer 47