Scribd
Upload
24 views17 pages

Solving Linear Systems

The document discusses iterative methods for solving linear systems, focusing on the Jacobi and Gauss-Seidel methods. It highlights the convergence criteria for both methods, noting that Jacobi converges with diagonally dominant matrices while Gauss-Seidel converges with symmetric positive definite matrices. Additionally, it compares the efficiency of both methods, indicating that Gauss-Seidel generally requires fewer iterations than Jacobi.

Uploaded by

syahrul aulia
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
24 views17 pages

Solving Linear Systems

The document discusses iterative methods for solving linear systems, focusing on the Jacobi and Gauss-Seidel methods. It highlights the convergence criteria for both methods, noting that Jacobi converges with diagonally dominant matrices while Gauss-Seidel converges with symmetric positive definite matrices. Additionally, it compares the efficiency of both methods, indicating that Gauss-Seidel generally requires fewer iterations than Jacobi.

Uploaded by

syahrul aulia
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 17

Solving Linear Systems

Iterative approach
Alternative Approach
• We are going to pursue iterative methods
which will satisfy the equation
in an approximate way without an
excessive amount of extra storage.
• There are a number of different classes of
iterative methods, today we will discuss an
example from the class of stationary
methods.

http://www.netlib.org/linalg/html_templates/node9.html
Jacobi Iteration
• Example system:

• Initial guess:
• Algorithm:

• i.e. for the I’th equation compute the I’th degree


of freedom using the values computed from the
previous iteration.
Cleaning The Scheme Up
Couple of Iterations

1st iteration:

2nd iteration:
Pseudo-Code For Jacobi Method
1) Build A, b
2) Build modified A with diagonal zero Q
3) Set initial guess x=0
4) do{
a) compute:

b) compute error:

c) update x:
}while err>tol
Convergence History

Stopping
criterion..
Increasing System Size

Notice how the number of iterations required grew with N


Ok – so I kind of broke the rules

• We set up the Jacobi iteration but did not ask the


question “when will the Jacobi iteration converge and
how fast?”

Definition:
A matrix A is diagonally dominant if

Theorem:
If the matrix A is diagonally dominant then Ax=b has a
unique solution x and the Jacobi iteration produces a
sequence which converges to x for any initial
guess
Convergence history for diagonally dominant system – notice dramatic
reduction in iteration count
Gauss-Seidel
• Example system:

• Initial guess:
• Algorithm:

• i.e. for the I’th equation compute the I’th degree of


freedom using the values computed from the
previous iteration and the new values just computed
Cleaning The Scheme Up
First Iteration

1st iteration:

As soon as the 1 level values are computed, we use them


in the next equations..
Theorem First This Time!.
• So we should first ask the questions
1) When will the Gauss-Seidel iteration converge?
2) How fast will it converge?

Definition:
A matrix is said to be positive definite if

Theorem:
If A is symmetric and positive definite, then
the Gauss-Seidel iteration converges for any
initial guess for x
Unoficially:
Gauss-Seidel will converge twice as fast in some
cases as Jacobi.
Gauss-Seidel Algorithm
• We iterate:
Comparing Jacobi and Gauss-Seidel

Same problem – Gauss-Seidel takes almost half the work


The Catch
• Ok – so it looks like one would always use
Gauss-Seidel rather than Jacobi iteration.

You might also like