Competition - post a photo you've taken of nature >>

Diagonally dominant matrix

Hello everyone,

I have been dealing with this problem for a couple of days now and can't figure it out how to solve it. Specifically, I need to prove the last sentence (see below), which is showing that the system of equations given by (10) is diagonally dominant.

In equation (10), we have a, b, c, d and L, which are all constants. In addition, a_iand a_j are the unknowns and p(x) is a function but this part should not play a role if I am supposed to find the coefficient matrix? I have tried unsuccessfully to solve it symbolically, so I decided to do it numerically:

Am I wrong?

Thanks in advance!

Reply 1

Gregorius

Original post by turk89

<a huge system of equations omitted for brevity>

Thanks in advance!

OK, so when faced with a mess like this and after getting over the initial panic, it's good to get back to first principles. One is solving a system of equations that basically boils down to a matrix equation:

\displaystyle A x = b

The system is diagonally dominant if each leading diagonal element is larger than the sum of the other elements on the same matrix row.

Let's look at what you've got and see if we can get it into this form. It looks to me that the vector

b

is given by the integrals over on the rhs of the equations. The vector

x

is the vector of unknowns

\alpha_j

. We have to extract the matrix

A

out of the rest.

So for

A

, notice that much of the lhs of your equations simply has the index j - so lies on the leading diagonal of

A

. The only off-diagonal elements correspond to the summation (for the j odd elements). Can you now write down what the matrix

A

looks like? The proof of diagonal dominance should now be straightforward.

Reply 2

turk89

I get something like this:

With my constants: L = 1385, a = 1,023E11, b = -5.155E8, c = 0 and d = 10,873, then my coefficient matrix [A] is not diagonal dominant. Can you confirm that?

Reply 3

turk89

I have been trying with i = j = {1,3,5} now and it seems that element (1,1) in the coefficient matrix, which is the first element in the diagonal, always doesn't satisfy the diagonal dominant requirement. Rest of the elements in the diagonal do. What is my coefficient matrix then called?

Reply 4

Gregorius

Original post by turk89

This is just a mess to latex, so let's simplify by taking the case n=3 as an example. Larger n follows the same pattern.

The first row first: the sum in equation 10 for j=1 boils down to

\displaystyle 4d \alpha_{1} (L/\pi)^2 + 4d \frac{\alpha_{3}}{3} (L/\pi)^2

The left hand term in this goes on the leading diagonal with the rest of the stuff on the lhs of equation 10 (i.e. into A[1,1]). The right hand term goes into the matrix position A[1,3].

The second row has no off-diagonal elements.

The third row: the sum in equation 10 for j=3 boils down to

\displaystyle 4d \frac{\alpha_{1}}{3} (L/\pi)^2 + 4d \frac{\alpha_{3}}{9} (L/\pi)^2

Here the right hand term goes on the leading diagonal along with the rest of the stuff on lhs (i.e. into A[3,3]). The right hand term goes into A[3,1]

So when we check the condition for diagonal dominance, the second row trivially satisfies it. The first row depends on comparing the magnitude of

\displaystyle 4d \frac{\alpha_{3}}{3} (L/\pi)^2

with the rest of the stuff out of the lhs of equation 10. Similarly for the third row. To my eyes at this time in the morning this would appear to depend upon the values of the many and various constants in this system!

Reply 5

Dr Pesto

I really thought the title said something about a dominatrix.

Reply 6

Gregorius

Original post by Dr Pesto

I really thought the title said something about a dominatrix.

Calm down at the back there! We'll be onto dominated convergence next....

Reply 7

Gregorius

Original post by Gregorius

To my eyes at this time in the morning this would appear to depend upon the values of the many and various constants in this system!

In fact, if we take a=b=c=0, d=1, L=Pi and n=3 then we get the matrix A as

Unparseable latex formula:

\displatstyle A = \begin{pmatrix} 1 & 0 & 1/3 \\0 & 0 & 0 \\1/3 & 0 & 1/9 \end{pmatrix}

Which is clearly not diagonally dominant. So, where are the constants chosen?

Reply 8

turk89

The constants a, b, c and d are constants based on the geometry and mechanical properties of a system, while L is the length of the system.

My conclusion is the same as yours in #5. Only element (1,1) does not satisfy the diagonal dominant requirement.

So... what can I say about convergence?

Reply 9

Gregorius

Original post by turk89

So... what can I say about convergence?

Diagonal dominance is often a sufficient but not necessary condition for convergence of an iterative schema. This is now getting me out of my depth, but which particular iterative method is being suggested in this problem? And by the way, from where has this problem arisen?

Reply 10

Gregorius

Original post by turk89

I get something like this:

With my constants: L = 1385, a = 1,023E11, b = -5.155E8, c = 0 and d = 10,873, then my coefficient matrix [A] is not diagonal dominant. Can you confirm that?

When I plug these numbers into Mathematica, I get approximately

\displaystyle \begin{pmatrix} 8.45 & 2.82 \\ 2.82 & 0.92 \end{pmatrix} \times 10^9

Can I just check that value of a - do you mean a = 1,023E11 or a = 1.023E11 - I've assumed the latter.

So this is OK for the first row but not for the second. At least it looks like it is non-singular!

Reply 11

ghostwalker

Original post by Gregorius

...

In case some context is useful:

See here

- downloads a pdf.

Reply 12

Gregorius

Original post by ghostwalker

In case some context is useful:

See here

- downloads a pdf.

Ah thanks, that's useful (and reminds me why I never went into applied mathematics...)

From a quick scan of the paper I can't see how their claim of diagonal dominance can be true in general. However, in the following section it looks like they may be trying to prove that the spectral radius of the iteration matrix is less than 1 - which is the real criteria for the Gauss Jacobi method to converge. Not sure about this - I've only scanned it...and it's time for Dr. Who now.

Reply 13

ghostwalker

Original post by Gregorius

...and it's time for Dr. Who now.

I have to wait for it to come onto the iPlayer :sad:

Reply 14

Gregorius

Original post by turk89

I get something like this:

With my constants: L = 1385, a = 1,023E11, b = -5.155E8, c = 0 and d = 10,873, then my coefficient matrix [A] is not diagonal dominant. Can you confirm that?

I've just noticed that in the paper linked by @ghostwalker that just after equation (6) on page 68, it says "For the suspended bridge model (2), b = -1 and c=0". If we take these values and plug them into the above, for the second row of your matrix we get

\displaystyle \frac{8}{9} < \frac{L}{2} \left (\frac{3 \pi}{L} \right)^4 \left( a \left( \frac{3 \pi}{L}\right)^2 - 1 \right)

as the condition for dominance, which if

L < 3 \pi

is not too hard to satisfy. Note also the values that the authors choose to demonstrate the methods in section 5 of the paper on numerical simulations. I suspect that they have these magnitudes of coefficients in mind in the theoretical parts of the paper but have omitted to mention it...

Reply 15

turk89

Thanks for your responses guys. I think that #Gregorius is right. They might be using the following coefficients: a = d = L = 1, b = -1 and c = 0, which makes no sense. The coeffcients are totally meaningless from a physical point of view.

With those coefficients I've given earlier, we can't satisfy the requirement from the paper, where lambda < 1 should be true for all rows.

However, diagonal dominance is not necessary condition for convergence of an iterative schema, as pointed out earlier by #Gregorious.