Testwiki:Reference desk/Archives/Mathematics/2011 June 23

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < June 22 ! width="25%" align="center"|<< May | June | Jul >> ! width="20%" align="right" |Current desk > |}

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 23

FDS for an ODE

Hey guys, I am trying to solve an BVP of the form -(a(x) u'(x))'=f(x) with u(0)=u(1)=0 where $a(x)\ge c>0$ is a bounded differentiable function in [0,1], on an equally spaced grid on [0,1] using finite differences. Since I want $O(h^2)$ approximation, I used central differences for both the first and the second derivative and got the relation:

$(a_{j+1}+4a_j+a_{j-1})u_{j+1}-8a_j{u}_j+(-a_{j+1}+4a_j+a_{j-1})u_{j-1}=-4h^2{f}_j$

with $u_0=u_n=0$ and since the ODE is linear, I can put this in a matrix vector form and get a tridiagonal matrix. I have two questions about this matrix. First of all, using Gerschgorin's theorem, I put a bound on the spectral radius of this matrix as 20M where M is the maximum of |a(x)| on the entire grid (I could use the max on [0,1] too which would be uniform for all grids). Is this correct and is this the best bound one can get? Second, what can I say about the condition number (let's say the 2-norm...using the ratio of the singular values)? How does the condition number depend on h? What happens as h goes to zero? Numerical experiments show that the condition number is blowing up but how would I show it analytically? Thanks!-Looking for Wisdom and Insight! (talk) 01:35, 23 June 2011 (UTC)

Gradient and conjugate gradient

On a completely different topic, how does the conjugate gradient method converge so much faster than plain simple gradient descent? I am not asking for the math behind it. I am just trying to get some intuitive sense and would appreciate it if someone can explain it in words. I thought the gradient points in the direction of maximum increase so negative gradient points in the maximum decrease so if I want to minimize the quadratic function, why not just use the gradient? How can conjugate gradient be faster? Thanks!-Looking for Wisdom and Insight! (talk) 01:45, 23 June 2011 (UTC)

I believe the question relates to our articles Gradient descent and Conjugate gradient method. Dolphin (t) 01:59, 23 June 2011 (UTC)

I have already read both of the articles but I was looking more for some insight in words as to what's wrong with the gradient descent method and how does CG fixes it. - Looking for Wisdom and Insight! (talk) 03:42, 23 June 2011 (UTC)

For intuition, I think a key phrase from our CG article is "Suppose that {pk} is a sequence of n mutually conjugate directions. Then the pk form a basis of Rn, so we can expand the solution x* of Ax = b in this basis" -- Because the pk are orthogonal with respect to A, there is less potential for 'redundancy' in the iterates, and they won't tend to zig-zag as some of the examples given in the gradient decent article. Does that help? SemanticMantis (talk) 03:56, 23 June 2011 (UTC)

Striped triangle question

Is it possible to create a triangle with three horizontal stripes, where each of the stripes has the same number of elements?

For example, it's easy to create such a triangle with two horizontal stripes:

  A
 A A
B B B

This has two stripes, each with three elements. This is (I think) the next smallest example, with two stripes containing 105 elements each:

                   A
                  A A
                 A A A
                A A A A
               A A A A A
              A A A A A A
             A A A A A A A
            A A A A A A A A
           A A A A A A A A A
          A A A A A A A A A A
         A A A A A A A A A A A
        A A A A A A A A A A A A
       A A A A A A A A A A A A A
      A A A A A A A A A A A A A A
     B B B B B B B B B B B B B B B
    B B B B B B B B B B B B B B B B
   B B B B B B B B B B B B B B B B B
  B B B B B B B B B B B B B B B B B B
 B B B B B B B B B B B B B B B B B B B
B B B B B B B B B B B B B B B B B B B B

But is it possible to extend this to three stripes? If so, what's the minimum number of elements in such a triangle? 28bytes (talk) 22:13, 23 June 2011 (UTC)

A quick python script shows that there are none with fewer than 100 million rows. So probably not, but I don't have a proof.--Antendren (talk) 23:20, 23 June 2011 (UTC)

Interesting. Thanks! 28bytes (talk) 23:21, 23 June 2011 (UTC)

The problem is equivalent to finding positive integer solutions of the system $y(y+1)=2x(x+1)$, $z(z+1)=3x(x+1)$. Picking the positive solution to each quadratic equation,

$y=\frac{1}{2}(-1+\sqrt{8x^2+8x+1}),z=\frac{1}{2}(-1+\sqrt{12x^2+12x+1}).$

So it comes down to whether $8x^2+8x+1$ and $12x^2+12x+1$ can both be perfect squares. At this point, I tried reducing modulo some small primes to show that they both can't be quadratic residues mod p for some p, but I wasn't able to find such a prime. Anyway, a slightly different approach might work. Sławomir Biały (talk) 00:45, 24 June 2011 (UTC)

I also couldn't find a three stripe solution. I wrote a Fortran program, and found the following number of elements were solutions to the 2 stripe problem, but none of these had a third stripe:

           3
         105
        3570
      121278
     4119885
   139954815
  4754343828
161507735340

Interestingly, there seems to be an almost exact relationship between each adjacent pair listed above. That is, each is approximately 33.97 times the previous entry. StuRat (talk) 00:43, 24 June 2011 (UTC)

Looks like it converges to around 33.970562748477. Is that an algebraic number, I wonder? 28bytes (talk) 02:42, 24 June 2011 (UTC)

Template:OEIS and Template:OEIS are relevant. Sławomir Biały (talk) 00:47, 24 June 2011 (UTC)

Template:OEIS is the actual sequence given here. A generating function and citation appear. The value near 33.97 is actually the zero of $1-34x+x^2$.McKay (talk) 03:52, 24 June 2011 (UTC)

OK, using that first sequence as the number of lines in the first stripe (ignoring the zero), instead of my previous brute force approach, I was able to come up with an extended list of two stripe solutions, none of which has a third stripe. Here are the numbers of elements in each stripe:

                  3
                105
               3570
             121278
            4119885
          139954815
         4754343828
       161507735340
      5486508657735
    186379786627653
   6331426236682470
 215082112260576330
7306460390622912753

StuRat (talk) 02:28, 24 June 2011 (UTC)

Antendren showed that any solution must have at least 9 digits by directly checking the number of rows below that point to see which fit the two equations. By searching only the solutions of the first equation to see if they solve the second as well, there are no solutions with less than 100,000 digits. This calculation took about 30 seconds in PARI/GP:

isTriangular(n:int)={
	issquare(n<<3+1)
};
test(lim)={
  my(x,y,n,t);
  while(n<=lim,
    t=3*x+2*y+2;
    y=t+x+y+1;
    x=t;
    n=x*(x+1)/2;
    if(isTriangular(3*n),return(n))
  );
  print("No solutions")
};
test(1e100000)

(Actually, the listed code would be somewhat slower; I actually used an optimized and compiled version of the first function.)

CRGreathouse (t | c) 04:30, 24 June 2011 (UTC)

• There are no solutions besides n=0. For details, see my post to SeqFan maillist: http://list.seqfan.eu/pipermail/seqfan/2011-June/015039.html Maxal (talk) 06:38, 24 June 2011 (UTC)