0
$\begingroup$

Jacobi and Gauss-Seidel

1) How does assuming any point as an initial approximation narrow down to the correct solutions?

2) why should the coefficient matrix be diagonally dominant?

3) if I were to think of such a method, what would my path of reasoning be?

Here's a similar question, but I don't quite get the answers. I specifically don't understand what the first two answers, assume to be evident,

which "naturally" defines a fixed-point iteration

$\endgroup$
  • 1
    $\begingroup$ @WlodAA to be honest, I have no idea, how to proceed numerically. I understand solving a system AX=b with the direct methods like using Cramer's rule, Gaussian eliminating etc. $\endgroup$ – Aravindh Vasu Feb 4 at 2:22
  • $\begingroup$ Let me shoot in dark: is there the Banach fixed point theorem involved? Or perhaps, there is a dominating eigenvector? (The two can even cooperate together?). $\endgroup$ – Wlod AA Feb 4 at 2:26
  • 1
    $\begingroup$ @WlodAA I've added an image, that's literally what we were taught. $\endgroup$ – Aravindh Vasu Feb 4 at 2:28
  • $\begingroup$ Can you present the procedures in terms of matrices (so to speak globally, without even mentioning variables)? $\endgroup$ – Wlod AA Feb 4 at 2:35
  • 1
    $\begingroup$ @WlodAA In wiki and in the similat question I've linked there's a procedure, splitting the coefficient matrix, but I couldn't understand it. $\endgroup$ – Aravindh Vasu Feb 4 at 2:46
0
$\begingroup$

You can do this in general for some system $F(X)=0$, $F=(f_1,...,f_n)$, $x=(x_1,...,x_n)$. The idea is to examine each equation and find its dominant variable, if there is one. If one can find a one-to-one dominance relationship of variables and equations, and if the dominance is strong enough, then you can solve each equation for its dominant variable. Assume that $x_i$ is the dominant variable in $f_i$.

Then one can loop through the equations in Jacobi-fashion, that is all-at-once in parallel (conceptually), $$ x_i^{new}=\text{ Solve }( 0=f_i(x^{old}_{1..i-1},u,x^{old}_{i+1..n}) \text{ for } u ) $$ or in Gauss-Seidel fashion, one-equation-at-a-time sequentially, replacing the computed variable value for the next equations $$ x_i^{new}=\text{ Solve }(0=f_i(x^{new}_{1..i-1},u,x^{old}_{i+1..n}) \text{ for } u) $$

This gives a fixed-point method $x^{new}=G(x^{old})$ and all the theorems about them apply, esp. the Banach fixed-point theorem. Thus it is a sensible demand that $G$ be contracting locally around the solution (which poses a problem in practical application as you do not know the solution).

In the non-linear case, there is no easy criterion of convergence, especially if you do not start close to a root (but one might transfer the convergence of the linearization). In the linear situation, contractivity of the method is a global property, so if it is present at all, then you get convergence from any initial point. As is known, one obtains this contractivity from diagonal dominance.

$\endgroup$
  • $\begingroup$ "Then one can loop through the equations in Jacobi-fashion, that is all-at-once in parallel (conceptually)" How does this exactly work? I understood till finding the dominant part and solving for that variable using that specific relation, but I don't get whatever the iteration does, does it repetitively apply any transform? Please bare with me if you've already addressed this. Can you please add a simple 2D example, if possible? $\endgroup$ – Aravindh Vasu Feb 4 at 17:05
  • $\begingroup$ You apply any method you know for the solution of non-linear scalar equations, like the secant method, or any bracketing method. For stability the root closest to the old value of the variable is preferred. The resulting method will converge very slowly in general. $\endgroup$ – Lutz Lehmann Feb 4 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.