67
Xnumbers Tutorial
130
Macro Integer Relation Finder
The macro Integer Relation Finder, from the menu "Numbers", searches for two type of integer
relations:
Polynomial relation
Input: a real number x, and the n-th degree
n
n
ax
ax
ax ax
a
...
3
3
2
2
1
0
+
+
+
+
General relation
Input: a vector x of n-th dimension
n n
ax
ax a a x x ax
...
3 3
2 2
1 1
+
+
+
Using this macro is very simple: select the cell containing the number x or the range of the
column-vector x and start the macro. The macro assumes a simple layout in order to speed-up
the input operation. The input layout is different for the two type of relation
Polynomial relation input layout
The cell B2 contains the multiprecision number x
of 30 digits and just below, the cell B3 contains
the degree n. Select the cells B2 and start the
macro
Multiple searching for one x and several degree
The cell B2 contains the multiprecision number x
of 30 digits and just the row below, the range
B3:D3 contains the degree n = 5, 6, 7. Select the
cells B2 and start the macro. For the same
number x, the macro will search for integer
polynomial with degree 5, 6 and 7 respectively
Multiple searching for several x and several degree
The range B2:B4 contains the multiprecision
numbers x1, x2 and x3 and just the row
below, the range B5:E5, contains the degree
n = 5, 6, 7 an 8. Select the range B2:B4 and
start the macro. For the each number x, the
macro will search for 4 integer polynomial with
degree 5, 6, 7 and 8, respectively
General relation input layout
The range B2:B6 contains the vector x .
Select the range B2:B6 and start the macro.
The dimension of he relation will be 5, just the same of the
vector dimension
Multiple searching for several vectors is possible. Simple select as many adjacent vectors as
we need. Note that each vector can have different dimension. In this case, select the
rectangular range containing all the vectors.
Metadata in pdf documents - add, remove, update PDF metadata in C#.net, ASP.NET, MVC, Ajax, WinForms, WPFAllow C# Developers to Read, Add, Edit, Update and Delete PDF Metadata
pdf metadata; change pdf metadata Metadata in pdf documents - VB.NET PDF metadata library: add, remove, update PDF metadata in vb.net, ASP.NET, MVC, Ajax, WinForms, WPFEnable VB.NET Users to Read, Write, Edit, Delete and Update PDF Document Metadata
read pdf metadata; view pdf metadata
134
Xnumbers Tutorial
131
Output results
The macro writes the result in the worksheet are beside the input data using a simple standard
layout almost similar for polynomial and general relation.
Let' s see with an example
Example 1. We want to search for a smallest integer polynomial having the approximate root:
x ≅ 2.99197185746375045829465694878... (30 digits)
We restrict our searching to the polynomials from 3 to 8 degree
Insert the input data x and the degree
3, 4, 5, 6 and 7 as in the sheet at the
left. Select the cell B1 and start the
macro
The input fields are correctly filled.
Press "start". In few seconds the
macro finds the polynomials adding
same useful information. Fortunately
it have found 2 "good" polynomials,
in this case
The coefficents of the polynomials are listed in the last section of the report, but just above, the
macro write the information returned by the PSLQ routine
Digits: the precision of the calculus
Degree: degree of the polynomial; degree +1 is the dimension of the relation
RC: return code: 0 =OK, 1 =precision exhausted, 2 = iteration overflow, 3= overflow error
This code states the "goodness" of the relation found
Residue: relative residue of the relation, computed as ε / a , where
∑
=
i i
ax
ε
,
|)
max(|
i i
ax
a=
Bound: this number M states that there can exist no relation vector whose Euclidean norm is
less than M. This is a very important result provided by PSLQ algorithm. Together with RC
helps us to analyze the goodness of the relation found.
Iter: number of iterations needed for reaching the result
Time: elaboration time in seconds
Example 2. We have 3 real numbers x
1
, x
2
, x
3
computed with 15 precision digits.
x
1
= 35.812551166675 , x
2
= 8.554440155849 , x
3
= 4.186428394404
We want to investigate if they could be express by the following simbolic formula
+
+
+
=
e
a
a
ae
a
a
x
5
4
3
2
1
1
π
π
⇔
0
5
4
3
2
1
=
+
+
+
+
−
e
a
a
ae
ax a
π
π
where [a
1
, a
2
, a
3
, a
4
, a
5
] all integer.
For finding this integer relation of dimension n = 5 (that it is compatible with the precision of the
numbers that we have) we compute the following vectors
[
]
1
1
, ,
, ,
−
−
e e
x
π π
changing the x
value with x
1
, x
2
, x
3
respectively
12
Xnumbers Tutorial
132
Arrange the 3 vectors as in the
sheet at the left. Select the range
B2:D6 and start the macro.
The input fields are correctly filled
and the option button "General" is
selected. Press "start".
In very few seconds the macro succesfully finds integer relations for the first two numbers,
while, on the contrary, the third numbers has not a small simple relation. Note how large are
the coefficents of the third column. Note also that its bound M = 3.4E+9 its very high; it assures
that no integer relation exists with norm ||a|| < 3.4E+9
204
Xnumbers Tutorial
133
Linear Algebra Functions
Matrix Addition
xMatAdd(mat1, mat2, [DgtMax])
Performs the addition of two matrices. mat1 and mat2 are (n x m) arrays
+
=
nm
n
n
nm
n
n
nm
n
n
b
b
b
b
a
a
a
a
c
c
c
c
1
1
11
1
1
11
1
1
11
..
..
..
..
..
..
Matrix Subtraction
xMatSub(mat1, mat2, [DgtMax])
Performs the subtraction of two matrices. mat1 and mat2 are (n x m) arrays
−
=
nm
n
n
nm
n
n
nm
n
n
b
b
b
b
a
a
a
a
c
c
c
c
1
1
11
1
1
11
1
1
11
..
..
..
..
..
..
Matrix Multiplication
xMatMult(mat1, mat2, [DgtMax])
Performs the multiplication of two matrices. mat1 (n x p) and mat2 (p x m) are arrays
⋅
=
pm
p
m
m
np
n
n
p
nm
n
n
a
a
a
a
a
a
a
a
a
a
a
a
c
c
c
c
1
2
21
1
11
2
1
1
12
11
1
1
11
..
..
..
..
..
..
..
Matrix Inverse
xMatInv(A, [DgtMax])
Returns the inverse of a (n x n) square matrix
It returns "?" for singular matrix.
This function uses the Gauss-Jordan diagonalization algorithm with partial pivoting method.
Matrix Determinant
xMatDet(A, [DgtMax])
Returns the determinant of a square matrix.
It returns "?" for singular matrix.
80
Xnumbers Tutorial
134
Matrix Modulus
xMatAbs(A, [DgtMax])
Returns the absolute value of a matrix or vector.
It is also known as "modulus" or "norm"
Parameters A may be an (n x m) array or a vector
2
1
1
,
( )
∑∑
=
=
=
n
i
m
j
i j
a
A
Scalar Product
xProdScal( v1, v2, [DgtMax])
Returns the scalar product of two vectors
2i
1
1i
2
1
V V
c V V
n
i
⋅
=
•
=
∑
=
Note: The scalar product is zero if, and only if, the vectors are perpendicular
0
2
1
2
1
V
V
V V
⊥
⇔
=
•
Similarity Transform
= xMatBAB(A, B, [DgtMax])
Returns the matrix product:
C B B AB
−1
=
This operation is also called the "Similarity Transform" of the matrix A by the matrix B. This
operation plays a crucial role in the computation of eigenvalues, because it leaves the
eigenvalues of the matrix A unchanged. For real, symmetrical matrices, B is orthogonal. The
Similarity Transform is also called the "orthogonal transform".
A and B must be square matrices.
Matrix Power
= xMatPow(A, n, [DgtMax])
Returns the integer power of a square matrix.
48
647
time
...
n
n
A A A A A
A
B A
= ⋅ ⋅ ⋅
=
Example
136
Xnumbers Tutorial
135
Matrix LU decomposition
= xMatLU(A, [Pivot], [DgtMax])
Returns the LU decomposition of a square matrix A
It uses Crout's algorithm
⋅
= ⋅ ⋅ =
33
23
22
13
12
11
21
21
21
0
0
0
1
1 0
0 0
1
u
u
u
u
u
u
l
l
l
A LU
Where L is a lower triangular matrix, and U is an upper triangular matrix
The parameter Pivot (default=TRUE) activates the partial pivoting.
Note: if partial pivot is activated, the LU decomposition refers to a permutation of A
If the square matrix has dimensions (n x n), this function returns an (n x 3n) array where the
first n columns are the matrix L, the next n columns are the matrix U, and the last n columns
are the matrix P.
Globally, the output of the Mat_LU function will be:
- Columns (1, n) = Matrix L
- Columns (n+1, 2n) = Matrix U
- Columns (2n+1, 3n) = Matrix P
When pivoting is activated the right decomposition formula is: A = P L U , where P is a
permutation matrix
Note: LU decomposition does not work if the first element of the diagonal of A is zero
Example: find the factorization of the following 3x3 matrix A
Note: if you want to get only the L and U matrices select a range (3 x 6) before entering this
function
Matrix LL
T
decomposition
= xMatLL(A, [DgtMax])
This function returns the LL
T
decomposition of a square matrix A
It uses Cholesky's algorithm
T
T
l
l
l
l
l
l
l
l
l
l
l
l
A L L L
⋅
= ⋅ ⋅ =
33
32
31
22
21
11
33
32
31
22
21
11
0
0
0
0
0
0
Where L is a lower triangular matrix
The function returns an (n x n) array
Note: Cholesky decomposition works only for positive definite matrix
195
Xnumbers Tutorial
136
Example.
The diagonal elements of the L matrix are all positive. So the matrix A is positive definite and
the decomposition is correct. This function simply stops when detects a negative diagonal
element, returning the incomplete decomposition.
See this example
<Attention !>
A diagonal element of the L matrix is
negative. So the matrix is not positive
definite
and the decomposition cannot be
completed
Vector Product
= xProdVect(v1, v2, [DgtMax])
Returns the vector product of two vectors
−
−
−
=
×
=
×
12
21
22
11
32
11
31
12
31
22
32
21
32
22
12
31
21
11
2
1
v v
v v
v v
v v
v v
v v
v
v
v
v
v
v
V V
Note that if V
1
and V
2
are parallels, the vector product is the null vector.
Solve Linear Equation System
xSYSLIN( A, B, [DgtMax])
Solves a linear system in multiprecision.
The input parameter A is an (n x n) array, B may be a vector (n x 1) or an (n x m) array.
It returns a vector (n x 1) or an (n x m) array depending by the argument B
A set of m linear systems in n unknowns looks like this:
, ... [ [ ]
, [ [ ]
[ ]
1
2
1
1
1
m
b
A x
b
A x
b
A x
⋅ =
⋅ =
⋅
⋅ =
It can be rewritten as:
=
⋅
⇒
=
⋅
nm
n
m
nm
n
m
nn
n
n
b
b
b
b
x
x
x
x
a
a
a
a
1
1
11
1
1
11
1
1
11
..
....
..
...
..
....
...
..
..
....
..
...
[ ] ] [ [ ] ] [ [ ]
B
x
A
This function uses the Gauss-Jordan diagonalization algorithm with partial pivoting method.
156
Xnumbers Tutorial
137
Example. Find the solution of the following 7x7 linear system
A
b
462
792
1287
2002
3003
4368
12376
24290
924
1716
3003
5005
8008
12376
31824
62856
1716
3432
6435
11440
19448
31824
75582
149877
3003
6435
12870
24310
43758
75582
167960
333918
5005
11440
24310
48620
92378
167960
352716
702429
8008
19448
43758
92378
184756
352716
705432
1406496
12376
31824
75582
167960
352716
705432
1352078
2697968
The solution is the vector [1, 1, 1, 1, 1, 1, 1]. Solving with standard arithmetic, we have an
average accuracy of about 1E-8, while in multiprecision we have an accuracy better than 1E-28
Square Delta Extrapolation
ExtDelta2(x)
xExtDelta2(x, [DgtMax])
This function returns the Aitken's extrapolation, also known as "Square Delta Extrapolation".
The parameter x is a vector of n value (n ≥ 3), in vertical consecutive cells. (n = 3 for the multi-
precision function xExtDelta2).
This formula can be applied to any generic sequence of values (vector with n>2 ) for
accelerating the convergence.
)
( , , ... , ) ) ( ( , , ...,
2
3
2
1
2
3
2
1
−
∆
→
n
n
v
v v v v
x
x x x x
Note that this algorithm produces a vector with n-2 values. If n = 3, the result is a single value.
Taking the difference
i
i
i
x
x −
∆ =
+1
, the Aitken's extrapolation formula is:
(
)
(
)
2
1
2
1
2
1
2
1
2
−
−
−
−
−
−
+
−
−
= −
∆ −∆
∆
−
=
i
i
i
i
i
i
i
i
i
i
i
x
x
x
x x
x
x
v
This formula can be applied to the second sequence to obtain a new sequence with n-4 values,
and so on. The process stops when the last sequence has less than 3 values.
Example. we want to find the numeric solution of the equation x = cos(x)
We choose the central point method. Starting from x
0
= 0 we build the iterations
x
n+1
= cos(x
n
)
57
Xnumbers Tutorial
138
As we can see in the following table, the convergence is evident but very slow (after 12
iterations the precision is about 3E-5) .
The functions of this worksheet are:
The cell B2 contains the starting value x
0
The cell B3 , C2, D3 contain the formulas
[B3]=C2
[C2]=COS(B2)
[D3]=ASS(B2-C2)
Selecting the range B3:D3 and dragging
down we can easily perform the iterative
process as we like.
We observe that the convergence is
evident but quite slow.
As we can see the last 12
th
value has an
error of about 3.5E-3. But if we perform
the delta extrapolation of the three last
values we get a new value having an
accuracy better than 1E-5.
Now let's repeat the iterative process using systematically the square delta extrapolation
In this process, we have systematically
repeated the ∆
2
extrapolation every 3
iterations.
We have inserted in the cell B5
=ExtDelta2(B2:B4)
In the cell B8
=ExtDelta2(B3:B7)
In the cell B14
=ExtDelta2(B9:B11)
The acceleration is superb!. After only 12 steps, the precision is better than 1E-15.
The graph below shows better than many words the acceleration effect
1E-16
1E-14
1E-12
1E-10
1E-08
1E-06
0.0001
0.01
1
0
2
4
6
8
10
12
Error (extrap)
Error
The Aitken's extrapolation formula works very well with the Gauss-Seidel iterative method, and
for accelerating the convergence of many iterative processes.
68
Xnumbers Tutorial
139
Macro for Multiprecision Matrix Operations
This application collects a set of useful macros performing multiprecision matrix operations
Determinant
)
det(A
Gauss-Jordan algorithm
Addition
A+B
+
Subtraction
A−B
−
Multiplication
A⋅B
⋅
Scalar multiplication
k ⋅A
Inverse
−1
A
Gauss-Jordan algorithm
Similarity transform
B AB
B
−1
Linear System
B
AX =
=
Gauss-Jordan algorithm
Linear System overdetermined.
b
Ax =
rows > columns
LU decomposition
LU
A=
Crout’s algorithm
Cholesky decomposition
T
LL
A=
Cholesky’s algorithm
Norm
A
Scalar product
A B
A
T
⋅
SVD
T
V
U
⋅Σ⋅
Golub-Reinsch algorithm
The use of this macro is quite simple. If the operation requires only one matrix (determinant,
inversion, etc.) select the matrix, start the macro and choose the appropriate operation.
Other operations (addition, multiplication, etc.) require two matrices. In that case you have also
to select the second matrix in the second input-box.
The internal calculus is performed in multiprecision. The result is converted in standard
precision (15 significant digits max) for more readability, but, if you like, you may also leave it in
full multiprecision format.
Example: Solve the following linear system Ax = b.
Select the matrix A and start the macro
Choose the operation “Linear System” and then move into the right field to select the vector b.
Documents you may be interested
Documents you may be interested
