toe_1o
tvmsscho2011 (Power method...)
toe_1n
Arrow matrices
Lower Hessenberg Toeplitz
Several exercises with Euler-Maclaurin summation formula
Computation of Bernoulli numbers...B_{2k}(0)B_{2k}(1/2)<0..
..B_{2k}(0)B_{2k-2}(o)<0 ?...Computation of Bernoulli numbers...
toe_1m
tvmsscho2010, et al
toe_1l
How Chebycev polynomial arise (more details, seminar CAN2 Jacopo De Cesaris)
Deflation (also for vectors)
Power method, an eigenvalue at a time
Exercise on deflation (3x3 stochastic by columns)
Deflation on hermitian, and positive definite matrices, the choice w^* = y_1^*
QR for 2x2 matrices
On matrix algebras, p(X), commutator of X, the algebra C+JC, C circulants,
the best least squares approximation of A in matrix algebras L.
Does it inherites positive definite property from A when L=C+JC?
Clustering property for T.Chan preconditioned Toeplitz systems (briefly):
eignvalues of I-C_T^{-1}T cluster on 1
To Cinzia on Fra algorithm RE preconditioned applied to I-aP, P web matrix
Exercises of the third esonero of AN3 (a differential problem, a stochastic
problem, an equivalent definition of Bernoulli polynomials:
\int_x^{x+1} B_n(y)dy=x^n for all real x )
toe_1k
Conjugate Gradient and GMRES iterations
(in CG: why clustering is good? from CG to GMRES..)
toe_1j
Exercise on matrix norms: can it happen that ||A^3||^{1/3} > ||A^2||^{1/2} ?
Improve Richardson-Eulero (RE)? (to check)
Nonstationary RE methods (to check)
Work with Fra on C, C_P with P web matrix, RE preconditioned with C_P
Matteo Ferrone, Giosi and the columns of the sine transform are orthogonal (a
direct proof)
On the zeros of Bernoulli polynomials in [0,1] (Claudia, Marcello,
Andrea): 0,1/2,1 for odd; x and 1-x for even, x in (0,1/2). Thus the dominant
property of Bernoulli numbers follows from |B_{2k}(1/2)|<|B_{2k}(0)|
Solving the first exam of AN3 (March 17, 2010)
The first 10 Bernoulli polynomials and the relation between
their values in 0 and in 1/2: the conjecture B_j(1/2)=-(1-1/2^{j-1})B_j(0)
A is eig optimally conditioned iff A is normal (mu_2(T)=1 iff T=aU, a scalar,
U unitary)
The transition matrix of AN3 students
Proof of B_j(1/2)=-(1-1/2^{j-1})B_j(0): even Bernoulli polynomials are bounded
(in [0,1]) by their value in 0
toe_1i
On the matrix P=[ ..0 1/mu_i 0..0 1/mu_i 0 ...] of the web,
nu(i) sites ponted by i, |nu(i)|=mu_i; rho(i) sites pointing to i
On its better circulant approximation C_P in Frobenius norm
Updating P and C_P
Upper and lower bounds for \rho(P^*P)
The following inequality holds
( min_{k:nu(k) non empty} |nu(k)| )*|j:nu(j) non empty| is less or equal to
( max_{k} |rho(k)| )*|j:rho(j) non empty|
Computation of the intersection of nu(i) and nu(j), of its cardinality n_{ij}
and of (PP^*)_{ij}=n_{ij}/(mu_i*mu_j)
On the equality rho(H)=lim_n ( ||H^n||^{1/n} ), comments and consequences
There are decreasing subsequences of ||H^n||^{1/n}
toe_1h
How to check if the eigenvalues of a matrix have negative real parts?
-3n is eigenvalue of the (n-1)x(n-1) Abate matrix
A sufficient, and
a necessary condition for a matrix to have R(l(A))<0
A both necessary an sufficient condition for a polynomial to have all
roots with negative real part
Some other remarks on the Abate matrix
Solving the exercise on p.3 (i.e. a differences equation)
Deflation: a (n-2)x(n-2)matrix whose eigenvalues are the remaining eigenvalues of A,
and a factorization of such matrix analogous to the factorization of the Abate matrix
toe_1g
Preconditioned finite elements method: the Poisson problem on the square
Eigenvalues of A (corresponding to the standard basis)
Exploiting the hierarchical basis
Eigenvalues and condition number of tilde A
From the proof that sine transfom is unitary, define a new Cosin transform?
toe_1f
Preconditioned finite elements method
Approximating u by u_h
Example: a differential problem solved by the finite element method
Definition of w solution of the variational version of the problem
Definition of w_h convergent to w
Computation of w_h: standard and hierarchical basis
Yserentant result
toe_1e
CG method
first main result (residuals are orthogonal, directions are conjugate)
second main result (convergence in at most the number of distinct eigenvalues)
Comparison with GMRES
third main result (a bound for the factor reducing the initial error)
preconditioned CG (reproduce a convenient spectrum, to increase rate of convergence
(decreasing the above bound) keeping as low as possible the cost of each step)
Circulant and tau matrices and best approximations to 4x4 symmetric Toeplitz
How Richardson method arise
toe_1d
The sine transform is unitary (proof via Fourier transform), define a cosine transform...
2x2 diagonalizable, but not by unitary transform, has condition number greater than 1
Can a non-unitary matrix T have condition number equal to 1 ? (think to Bauer-Fike)
A first Gershgorin theorem for irreducible matrices with applications (weakly dominant
plus irreducible imply invertibility, convergence of Jacobi method,...)
Proof of the existence of the SVD of A nxn matrix
On SVD: best rank-r approximation of A
On SVD: kernel and image of A
On SVD: exercises (SVD of a normal matrix)
On SVD: how to compute the rank of a matrix, Gram-Schmidt vs SVD
toe_1c
A new matrix algebra? (related to Chebycev)
How Chebycev polynomials arise
Properties of Chebycev polynomials
Chebycev as characteristic polynomials
SVD of A nxn matrix (no proof) and applications, and how to compute the singular
values of A real
Step 1
Step 2
Step 2 for n=2 (convergence)
Step 2 for n=2 (details and example)
Numeric example
toe_1b
An example of preconditioning
Proof that a DFT of order n can be reduced to two DFT of order n/2
The real part of \E(A) > 0 vs \E(A_h) > 0, also for A real
We know that A_h p.d. implies Re(\E(A))>0
...Does Re(\E(A))>0 imply A_h p.d.? If A is normal, yes; otherwise
a stronger hypothesis of kind Re(\E(A))>q>=0 is sufficient to obtain
the p.d. of A_h. The aim is to find a q as small as possible.
A question is "q can be zero for a class of not normal matrices ?"
Eigenstructure of normal matrices
Circulant-type matrix slgebras
Proof of Ax_i=\E_i\Ax_i, A=[t^{|i-j|}], \A=Strang
Let A and B non null matrices. Assume that Ax=\E Bx, Ay=\mu By for non
null x and y, \E\neq\mu. Then x and y are linearly independent
Proof of eigenvalue minmax representation for a hermitian matrix A
(and of the interlace theorem)
Deflation
toe_1a
A che serve il clustering attorno a 1
Dubbio su GStrang
Sui metodi iterativi (H,u_k)
Re(\E(A))>0 vs p.d. of A_h=hermitian part of A
On the rate of convergence of some iterative methods in cases the
coefficient matrix has a p.d. hermitian part
toe_1
A unifying approach to preconditioning, with application to the
Toeplitz case (T.Chan, G.Strang, E.Tyrtyshnikov)
An interesting problem
Proof of TheoremClusterTC (proof of 1, proof of the right inequ in 2,
proof of the left inequ in 2)
Linear Algebra et al
Min-max eigenvalue representation theory
Definition of SVD
FFT: Fz can be computed in O(nlog n) a.o.
Decomposition of A=[t^{|i-j|}]
References