Thread Rating:
• 0 Vote(s) - 0 Average
• 1
• 2
• 3
• 4
• 5
 Matrix Operator Method Gottfried Ultimate Fellow Posts: 766 Threads: 119 Joined: Aug 2007 04/17/2008, 09:21 PM (This post was last modified: 04/18/2008, 11:18 AM by Gottfried.) Hi - although I wanted to be a bit detached for some weeks and look into the basics of the divergent summation thing, I've just made a big step to backup my eigensystem-decomposition by a compeletely elementary iterative method, and I want to share this. The symbolic eigensystem-decomposition is enormous resources-consuming and also not yet well documented and verified in a general manner. Here I propose a completely elementary (while still matrix-based) way to arrive at the same result as by eigensystem-analysis. ---------------------------------------------------- As you might recall from my "continuous iteration" article I've found a matrix representation for the coefficients of the powerseries for the U-tetration $\hspace{24} U_t^{^oh}(x)$, where $U_t(x)= U_t^{^o1}(x) = t^x - 1$. Here I'll extend the notation for the powerseries a bit, compared to the text in the article: $\hspace{24} U_t^{^oh}(x) = a_1(t,h)* b_1/d_1 * x/1! + a_2(t,h)*b_2/d_2 * x^2/2! + ...$ Let me, as earlier, use the notation u=log(t) for this text. Then * the b_k are powers of u (but of no special interest here), * d_k are products of (u^j-1), like $(u-1)*(u^2-1)*...*(u^{k-1}-1)$ and * a_k(t,h) are bivariate polynomials, whose numerical coefficients are the sole mysteries in this powerseries. Since we have two formal variables in each a_k, the coefficients can be arranged in matrices, whose row- and column-multiplieres are the consecutive powers of the parameters. For instance a3(t,h) looks like the following: $\hspace{24} u=log(t) \\ v=u^h \\ \begin{matrix} {rll} a_3(t,h)*b_3/d_3/3! &=& ((u^3 + 2*u^2)/(6*u^3 - 6*u^2 - 6*u + 6))*v^3 \\ & & + u^2/(-2*u^2 + 4*u - 2)*v^2 \\ & & + ((2*u^3 + u^2)/(6*u^3 - 6*u^2 - 6*u + 6))*v \end{matrix}$ The 3! removed from denominator makes this $\hspace{24} \begin{matrix} {rll} a_3(t,h)*b_3/d_3 &=& ((u^3 + 2*u^2)/(u^3 - u^2 - u + 1)) *v^3 \\ && + 3 u^2/(-*u^2 + 2*u - 1) *v^2 \\ && + ((2*u^3 + u^2)/(u^3 - u^2 - u + 1))*v \end{matrix}$ d3 is the common denominator, it is $\hspace{24} d_3 = (u^2-1)*(u-1) =(u^3 - u^2 - u + 1) $ This removed it is $\hspace{24} a_3(t,h)*b_3 =(u^3 + 2*u^2)*v^3 + (-3*u^3 - 3*u^2)*v^2 + (2*u^3 + u^2)*v$ Also b3 = u^2 removed, this is $\hspace{24} a_3(t,h) =(u + 2)*v^3 + (-3*u - 3)*v^2 + (2*u + 1)*v$ Now the numerical coefficients of this polynomial can be arranged in a matrix Code:   A3 =  2  -3  1         1  -2  2where we understand, that the columns are to be multiplied by consecutive powers of v=u^h, beginning at 1 and the rows by consecutive powers of u, beginning at 0: Code:   A3 = [ 2   -3   1 ]*u^0          [ 1   -3   2 ]*u^1        ------------------          *v   *v^2 *v^3The value of this term, given u and h, is then simply the appropriate built rowsums added. Now v is u^h and we have the interesting relation, depending on h that any integer height h provides a columnshift by h rows. So if h=0 we have no shift Code:   A3 = [ 2   -3   1 ]*u^0          [ 1   -3   2 ]*u^1        ------------------          *1    *1  *1and we have simple rowsums of zero (and also all A matrices provide coefficients of zero to the original powerseries the same way). If h=1 we have Code:   A3 = [ 2   -3   1 ]*u^0          [ 1   -3   2 ]*u^1        ------------------          *u   *u^2 *u^3and in effect, this provides a column-shift Code:   A3 = [ 2          ]*u^1          [ 1   -3     ]*u^2        [     -3   1 ]*u^3        [          2 ]*u^4        ------------------ = u(2 - 2u - 2u^2 + 2u^3 ) = 2u(u - 1) *(u^2 - 1 )) = 2u*d3 and we have another sum, where also d3 cancels the denominator. With h=2 we have the most interesting case (concerning a_3) Code:   A3 = [ 2          ]*u^2          [ 1          ]*u^3        [     -3     ]*u^4        [     -3     ]*u^5        [          1 ]*u^6        [          2 ]*u^7   = u^2(2 + u - 3u^2 - 3u^3 + u^4 + 2u^5)         = u^2*(u - 1)*(u^2-1)* (2*u^2 + 3*u + 2)   = u^2 * d3 * (2*u^2 + 3*u + 2) where again d3 cancels the denominator. From inspection of the first few A-matrices I concluded, that for each integer h the numerical coefficients of all A-matrices cancel the denominator. This even allows u=1, t=exp(1) and via fixpointshift the tetration-bases b=e^(1/e)) for integer heights, since the zero-denominators cancel. It is interesting concerning fractional heights, for instance if h is half-integer, all these column-shifting has a special consequence. For h=1/2 we have Code:   A3 = [ 2          ]*u^0.5          [     -3     ]*u^1.0        [ 1        1 ]*u^1.5        [     -3     ]*u^2.0        [          2 ]*u^2.5        ------------------ where the cancelling of the denominators cannot occur. This may give a feeling for the mysteries of fractional iteration. ======================================================================== But this is only for recalling some known things. This msg is intended to cover another aspect. The symbolic eigen-decomponsition, which gives us the A-matrices, is extremely costly in time and memory, so I was searching for another method to determine the A-matrices independently. My idea was the striking property, that the coefficients seem to guarantee, that for integer heights the denominator is always a factor of the numerator. So the A-matrices must be expressible in some multiples of the denominators d, let's express their polynomial-coefficients as vector D. If these multiples can be determined apriori then the costly eigenvalue-decomposition is not needed. Yesterday I found the solution (with the help of members of the seqfan-mailing list), and this is an extremely simple routine. We use the same example A_3 here, but since we don't want to use the eigendecomposition, all numerical coefficients in A are unknown. So we have Code:                               RS= // row-sums   A3 = [ a0  -a1  a2]*u^0    [ ?]*u^0        [ b0  -b1  b2]*u^1    [ ?]*u^1        [  0    0   0]*u^2    [ 0]*u^2        [  0    0   0]*u^3    [ 0]*u^3                               //I've extended the rows to get                               // compatibility with the following                               // matrix-operation and the row-sums must equal an integer composition of D3 = column([1,-1,-1,1). We know by 3'rd and 4'th row, that the row-sums RS are zero, so in Code:       RS = D3 * k0 the unknown k0 must be zero. The next condition exploits the properties at h=1 since we have Code:                              RS =   A3 = [a0          ]*u^1    [ ?]*u^1        [b0   -a1    ]*u^2    [ ?]*u^2        [     -b1  a2]*u^3    [ ?]*u^3        [          b2]*u^4    [ ?]*u^4        ------------------ and we have that Code:       RS = D3 * k0 but have no information about k0 here. From Eigenanalysis we know, that k0=1 The next condition, using h=2 is Code:                              RS=   A3 = [ a0         ]*u^2    [ a0]*u^2        [ b0         ]*u^3    [ b0]*u^3        [     -a1    ]*u^4    [-a1]*u^4        [     -b1    ]*u^5    [-b1]*u^5        [          a2]*u^6    [ a2]*u^6        [          b2]*u^7    [ b2]*u^7 and since this must again be an integer composition of the polynomial d3, we may express this by the matrix-multiplication Code:    RS = MD3 * K3 where MD is the matrix built from D3 with column-shift Code:   MD3 = [ 1  .  . ]  K3= [k0]         [-1  1  . ]      [k1]         [-1 -1  1 ]      [k2]         [ 1 -1 -1 ]         [ .  1 -1 ]         [ .  .  1 ] and K3 must be a vector now with integer weigths for each column in MD3 If K3 would be known, the result MD3 * K3 must equal RS, and from RS we can uniquely determine the unknown coefficients a0 to b2. So, if the analoguous K-vectors for all A were known, also all numerical coefficients in the A-matrices were immediately known. This is the concept of my new solution. I collected some K-vectors into a matrix (from the known eigensystem-based solutions) to find a recursive generation rule for this matrix and posted the first nontrivial K-matrix into the mailing list, and a member (Richard Mathar) indeed found a computation-rule for this first K-matrix (there called "H"-matrices) , which I could systematize and generalize to a very simple iteration-process for all K- and then subsequently A-matrices analoguously. Here an excerpt of my concluding mail to seqfan-list (I'm a bit tired of typing, but edited it a bit for this msg...) Code: ========================================================== a) Assume a matrix-function "rowshift(M)" which computes "M1 = rowshift(M)" in the following way: M = [a,b,c,...]     [k,l,m,...]     [r,s,t,...]     [...      ] M1 = [a,b,c, ...   ]      [0,k,l,m, ... ]      [0,0,r,s,t,...]      [ ...         ] b) Assume the lower-trianguler matrix of Stirling-numbers 2'nd kind S = [1  0  0  0 ...]     [1  1  0  0 ...]     [1  3  1  0 ...]     [1  7  6  1 ...]     [ ... ] c)then with H0 = [1]      [1]      [1]      [1]     ... we have the iterative Mathar-products (*1) d) H1 = S * rowshift(H0)     \\ which is then = S * I = S H2 = S * rowshift(H1)   H3 = S * rowshift(H2) ... where H1 =   1   .   .   .  .   1   1   .   .  .   1   3   1   .  .   1   7   6   1  .   1  15  25  10  1 H2=   1   .   .   .   .   .   .   .  .   1   1   1   .   .   .   .   .  .   1   3   4   3   1   .   .   .  .   1   7  13  19  13   6   1   .  .   1  15  40  85  96  75  35  10  1 H3=   1   .   .    .    .    .    .    .    .   .   .   .  .   1   1   1    1    .    .    .    .    .   .   .   .  .   1   3   4    6    4    3    1    .    .   .   .   .  .   1   7  13   26   31   31   25   13    6   1   .   .  .   1  15  40  100  171  220  255  215  156  85  35  10  1 ... and so on (based on the Maple-implementation of R.Mathar) ---------------------------------- In my basic problem-description I also had the vector D, which I also should index now. It contains the coefficients of the polynomials in u: e)   Dk = polcoeffs(prod(j=1,k -1, u^j - 1)) Say D3 = columnvector([1 -1 -1 1]) f) Then define the matrix MD3 as the concatenation of shifted D3 MD3 =    1   -1  1   -1 -1  1    1 -1 -1       1 -1  ...          1         ... up to the required dimension for the following matrix-multiplication to obtain the k'th coefficient in the original powerseries   Ut(x,h) = a1(t,h) b1/d1/1!*x + a2(t,h)*b2/d2/2!*x^2 + ... Then the coefficients for the bivariate polynomial in u=log(t) and v=u^h of the k'th coefficient are in the vector g)   Vk = MDk * transpose(Hj[k,]) where [k,] denotes the k'th row and the index j at Hj indicates the    j=binomial(k-1,2) 'th Mathar-iterate. So we have three essential steps to compute one A-matrix:   1.a) compute the D_k-vector as "polcoeffs(prod(j=1..k-1,u^j - 1))"   1.b) compute the MD_k-matrix by concatenation/shifting of D_k   2)   compute the m'th iterate H_m(), where m=binomial(k-1,2), use the           k'th row of the result as K-vector K_k = H_m[k,]   3.a) compute RS_k = MD_k * transpose(K_k)   3.b) reformat the vector RS_k into a matrix A_k of k columns ------------------------------------ This is an eminent simple recursive scheme to obtain the coefficients for the continuous iteration of x -> t^x-1. However it is again enormous consumptive: the required iterations of the Mathar-products is quadratic (precisely:binomial(index-1,2)) with the index. So for index k=20 I need already 171 iterations with always growing matrices... surely some shortcuts may be implemented. The working load is in the number of columns of the H-matrices: the final number of columns for k=20 is  1/2*k*(k^2-4k+5)=3250, and grows cubically with the index.    However - the fact, that this simple scheme is able to mimic the symbolic eigendecomposition of a matrix-operator is a very astonishing aspect. ======================================================================== (end of mail to seqfan) So, for our members, who did not understand my matrx-method with eigendecomposition (or did not trust it ;-) ) here is a completely elementary approach, simple to implement. However - now two hypotheses are involved, which need proof: a) that indeed the property holds, that A-matrices using integer values of height h contain the denominators d_k as factor b) that the Mathar-process indeed provides the correct H-matrices. I checked that up to h=20 and did not find an error. I append also some A-matrices, computed by the above process. Note, they are transposes compared to my mentioned text about "continuous iteration" Gottfried ======================================================================== Code: D_2= (vector)   -1  1 K_2= (vector)   1 A_2= (matrix)   -1  1 -------------------------- D_3= (vector)   1  -1  -1  1 K_3= (vector)   1  3  1 A_3= (matrix)   1  -3  2   2  -3  1 ------------------------------ D_4=   -1  1  1  0  -1  -1  1 K_4=   1  7  13  26  31  31  25  13  6  1 A_4=   -1   7  -12  6   -6  18  -18  6   -5  18  -18  5   -6  11   -6  1 ------------------------------ D_5=   1  -1  -1  0  0  2  0  0  -1  -1  1 K_5=   1  15  40  100  186  310  490  705  921  1140  1315  1435  1481  1420   1285  1105  886  660  455  285  166  85  35  10  1 A_5=    1   -15   50   -60  24   14   -75  145  -120  36   24  -130  230  -170  46   45  -180  275  -180  40   46  -165  215  -120  24   26  -105  130   -60   9   24   -50   35   -10   1 ------------------------------------------ D_6=   -1  1  1  0  0  -1  -1  -1  1  1  1  0  0  -1  -1  1 K_6=   1  31  121  366  861  1642  2982  4932  7727  11497  16628  23127   31277  40937  52147  64612  78297  92497  107162  121451  135002  146787   156632  163631  167871  168862  166802  161541  153616  142981  130527   116621  102186  87531  73486  60166  48101  37376  28236  20635  14656   10026  6611  4130  2440  1306  636  255  80  15  1 A_6=     -1    31   -180   390   -360  120    -30   270   -870  1290   -900  240    -89   694  -1920  2515  -1590  390   -214  1364  -3345  3905  -2190  480   -374  2025  -4440  4825  -2550  514   -416  2395  -4995  4925  -2325  416   -511  2430  -4530  4110  -1800  301   -461  2006  -3480  2885  -1110  160   -330  1336  -2055  1495   -510   64   -154   675   -960   575   -150   14   -120   274   -225    85    -15    1 ----------------------------------------------------------- D_7=   1  -1  -1  0  0  1  0  2  0  -1  -1  -1  -1  0  2  0  1  0  0  -1  -1  1 K_7=   1  63  364  1316  3857  8540  17522  32676  56763  92722  145565 219590  321413  457324  635782  865844  1158395  1523599  1973805   2519790  3172421  3942099  4837273  5864971  7030269  8336258  9781520   11364262  13075818  14906199  16838921  18855277  20927928  23031974   25132905  27201587  29200578  31099439  32859715  34454231  35847014   37015524  37930670  38578071  38937003  39005785  38775716  38259081   37461558  36406349  35109662  33604207  31912699  30072889  28112666   26071493  23978150  21871710  19778472  17733072  15757701  13878746   12110168  10468493  8959111  7590492  6361384  5272659  4318307  3494092   2790081  2198385  1707203  1306193  983171  727447  527625  374374   258812  173747  112567  69951  41279  22883  11698  5369  2142  686  161   21  1 A_7=      1     -63     602    -2100    3360   -2520   720     62    -903    4501   -10500   12600   -7560  1800    300   -3290   13300   -26740   28700  -15750  3480    889   -8337   29778   -53340   51590  -25830  5250   2177  -16485   52269   -86415   78050  -36624  7028   3368  -25977   78218  -121345  103040  -45360  8056   5188  -36421  102242  -148715  118615  -49161  8252   6980  -44604  117719  -161840  121800  -47481  7426   8007  -48538  120967  -156765  110985  -40635  5979   7867  -46599  110173  -134960   90160  -30849  4208   7188  -40215   89656  -102620   63525  -20076  2542   6111  -30723   63357   -67585   38885  -11340  1295   4270  -20216   39081   -38220   19600   -5019   504   2528  -11193   19355   -16695    7525   -1659   139   1044   -4872    7658    -5425    1890    -315    20    720   -1764    1624     -735     175     -21     1 -------------------------------------------------------------------------- ======================================================================= Gottfried Helms, Kassel « Next Oldest | Next Newest »

 Messages In This Thread Matrix Operator Method - by Gottfried - 08/12/2007, 08:08 PM RE: Matrix Operator Method - by bo198214 - 08/13/2007, 04:15 AM RE: Matrix Operator Method - by jaydfox - 08/13/2007, 05:40 AM RE: Matrix Operator Method - by Gottfried - 08/13/2007, 09:22 AM RE: Matrix Operator Method - by bo198214 - 08/14/2007, 03:43 PM RE: Matrix Operator Method - by Gottfried - 08/14/2007, 04:15 PM RE: Matrix Operator Method - by bo198214 - 08/26/2007, 12:18 AM RE: Matrix Operator Method - by Gottfried - 08/26/2007, 11:24 AM RE: Matrix Operator Method - by bo198214 - 08/26/2007, 11:39 AM RE: Matrix Operator Method - by Gottfried - 08/26/2007, 04:22 PM RE: Matrix Operator Method - by Gottfried - 08/26/2007, 10:54 PM RE: Matrix Operator Method - by bo198214 - 08/27/2007, 08:29 AM RE: Matrix Operator Method - by Gottfried - 08/27/2007, 11:04 AM RE: Matrix Operator Method - by bo198214 - 08/27/2007, 11:35 AM RE: Matrix Operator Method - by Gottfried - 08/27/2007, 11:58 AM RE: Matrix Operator Method - by bo198214 - 08/27/2007, 12:13 PM RE: Matrix Operator Method - by Gottfried - 08/27/2007, 01:19 PM RE: Matrix Operator Method - by Gottfried - 08/27/2007, 02:29 PM RE: Matrix Operator Method - by bo198214 - 08/27/2007, 02:36 PM RE: Matrix Operator Method - by Gottfried - 08/27/2007, 03:09 PM RE: Matrix Operator Method - by bo198214 - 08/27/2007, 07:15 PM RE: Matrix Operator Method - by Gottfried - 08/27/2007, 08:15 PM RE: Matrix Operator Method - by bo198214 - 08/29/2007, 05:28 PM RE: Matrix Operator Method - by Gottfried - 08/27/2007, 12:43 PM RE: Matrix Operator Method - by Gottfried - 10/08/2007, 12:11 PM RE: Matrix Operator Method - by Gottfried - 10/14/2007, 09:32 PM RE: Matrix Operator Method - by Gottfried - 04/04/2008, 09:41 AM RE: Matrix Operator Method - by Gottfried - 04/17/2008, 09:21 PM RE: Matrix Operator Method - by bo198214 - 04/25/2008, 03:39 PM RE: Matrix Operator Method - by Gottfried - 04/26/2008, 06:09 PM RE: Matrix Operator Method - by bo198214 - 04/26/2008, 06:47 PM RE: Matrix Operator Method - by Gottfried - 04/18/2008, 01:55 PM RE: Matrix Operator Method - by Gottfried - 07/08/2008, 06:46 AM Diagonalization for dxp/basic facts/Pari-routine - by Gottfried - 08/08/2008, 01:12 PM Exact entries for T-tetration Bell-matrix - by Gottfried - 09/24/2008, 08:22 PM RE: Exact entries for T-tetration Bell-matrix - by bo198214 - 09/26/2008, 07:30 AM RE: Exact entries for T-tetration Bell-matrix - by Gottfried - 09/26/2008, 09:56 AM

 Possibly Related Threads... Thread Author Replies Views Last Post My interpolation method [2020] tommy1729 1 315 02/20/2020, 08:40 PM Last Post: tommy1729 Kneser method question tommy1729 9 1,419 02/11/2020, 01:26 AM Last Post: sheldonison Half-iterates and periodic stuff , my mod method [2019] tommy1729 0 613 09/09/2019, 10:55 PM Last Post: tommy1729 A fundamental flaw of an operator who's super operator is addition JmsNxn 4 7,526 06/23/2019, 08:19 PM Last Post: Chenjesu Tetration and Sign operator tetration101 0 603 05/15/2019, 07:55 PM Last Post: tetration101 2 fixpoints , 1 period --> method of iteration series tommy1729 0 1,888 12/21/2016, 01:27 PM Last Post: tommy1729 Tommy's matrix method for superlogarithm. tommy1729 0 1,879 05/07/2016, 12:28 PM Last Post: tommy1729 [split] Understanding Kneser Riemann method andydude 7 8,764 01/13/2016, 10:58 PM Last Post: sheldonison [2015] New zeration and matrix log ? tommy1729 1 3,531 03/24/2015, 07:07 AM Last Post: marraco Kouznetsov-Tommy-Cauchy method tommy1729 0 2,214 02/18/2015, 07:05 PM Last Post: tommy1729

Users browsing this thread: 1 Guest(s)