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