Math Question



#2

I am looking at the Jacobi Method which is the simplest (and slowest) iterative method for solving a large system of linear equations. Such systems are too large for traditional methods to work. I am solving:

A x = b

The Jacobi method uses the following matrix form for its iterations:

D x = b – (L + U) x

Where D, L and U are the diagonal, strictly left lower triangular, and strictly right upper triangular matrices, respectively. The algorithm is guaranteed to work, with any initial guess for x, if matrix A has diagonal dominant elements.
In case matrix A is not diagonal dominant, I am trying to find a trick to add a preconditioning matrix P to make A diagonal dominant. P is a diagonal matrix with zeros in non-diagonal elements. Each diagonal value of matrix P is equal to the sum of absolute values in the corresponding row of matrix A. Thus I have:

(A + P) x = b + P x

The iteration formula becomes:

(D + P) x = b + P x – (L + U) x

If I use a guess for x on the right hand side, the iterations do not converge. However, if I solve for x using a traditional method to get a good approximation for x and use that in evaluating the term P x, then the above equation converges to a more accurate solution. In fact, using this approach the expression b + P x can be regarded as equal to b' which is a new constants vector. So basically I am changing the original equation to a more favorable form by updating matrix A and vector b.

The question to is this. Am I cheating in the above method that I described? Can you offer any better solutions?

Namir

PS: whatever approach works with the Jacobi method can also be applied to the Gauss-Seidel method which is a better method. There are algorithms (variants of the conjugate gradient method) that solve large linear systems of equations where matrix A is not diagonal dominant or symmetrical. I am trying to go back to basics and see if the Jacobi and Gauss-Seidel methods can get a face lift.


Edited: 6 Nov 2012, 10:41 a.m.


Possibly Related Threads...
Thread Author Replies Views Last Post
  Need help understanding math.... cyrille de Brébisson 9 492 12-13-2013, 02:23 AM
Last Post: Didier Lachieze
  OT: a math competition site Pier Aiello 0 137 09-16-2013, 06:03 AM
Last Post: Pier Aiello
  Simple Math Question Namir 2 187 08-09-2013, 06:13 PM
Last Post: Eddie W. Shore
  Cool math clock Bruce Bergman 28 1,135 04-10-2013, 03:13 AM
Last Post: Siegfried (Austria)
  Math Challenge I could not solve Meindert Kuipers 22 897 01-05-2013, 04:43 PM
Last Post: Thomas Klemm
  Survey for Special Math Problem Namir 7 374 06-03-2012, 09:46 PM
Last Post: Namir
  math question Don Shepherd 22 796 04-25-2012, 11:38 PM
Last Post: Don Shepherd
  Math Help!! Namir 10 430 04-16-2012, 11:32 PM
Last Post: Allen
  go41cx overlay Math module Alexander Oestert 12 521 02-04-2012, 05:09 AM
Last Post: Alexander Oestert
  A Math Challenge (kind of) Namir 17 572 08-17-2011, 08:58 PM
Last Post: Gilles Carpentier

Forum Jump: