Questions on the various algorithms used in linear algebra computations (matrix computations).

learn more… | top users | synonyms

1
vote
1answer
72 views

Singular Value Decomposition using Jacobi Method

First time user of the site, so I apologize if my question isn't worded properly. I'm trying to implement the SVD of a square matrix using Algorithm 6 found on this website: ...
1
vote
1answer
40 views

$LDL^T$ decompositon of a symmetric matrix and a matrix determinant expression for the lower triangular entries

Let $n$ be a positive integer, and let $M$ be an integral, symmetric, nonsingular matrix. As $M$ is nonsingular, there exists an $LDL^T$ decomposition such that $D = (d_j)$ is diagonal and ...
4
votes
1answer
70 views

Prove $\min_{i}|\lambda_i| \leq |r_{jj}| \leq \max_{i}|\lambda_i|$

Let A be a normal $n \times n$ matrix with the eigenvalues $\lambda_1,...,\lambda_n$ |A| = |QR|, $|Q^HQ| = I$, $|R| = [r_{ik}]$ upper triangular matrix. Prove: $$\min_{i}|\lambda_i| \leq |r_{jj}| \leq ...
0
votes
0answers
42 views

How to fit a stochastic matrix to given data.?

Given a data sequence of noisy observations of a 3-state Markov chain $X$ -- $y_1$,$y_2$,...$y_n$, with two transition matrices $A_1$ and $A_2$ corresponding to different regions (**) in the (unit) ...
0
votes
2answers
84 views

Prove that $q_{ki} = \lambda_1[1+ \mathcal{O}((\frac{\lambda_1}{\lambda_2})^k)] \; \text{for all } i \; \text{with} \; (x_1)_i \neq 0$

Let A be a real symmetric $n x n$ matrix having the eigenvalues $\lambda_i$ with $$|\lambda_1|>|\lambda_2| \geq ... \geq |\lambda_n|$$ and the corresponding eigenvectors $x_1...x_n$ with $x_1^Tx_k ...
0
votes
1answer
25 views

Reformulate this system of equations

I have the following systems of equations: $$ A\cdot g = \mathbb 0\\ G\cdot \mathbb 1 = w$$ $A$ is a $J\cdot I \times J\cdot I$ matrix. $g$ is a $J\cdot I \times 1$ column vector $\mathbb 0$ and ...
3
votes
1answer
66 views

Relationship between the solution to $Ax=b$ and $(A+I)x=b$

I have have a symmetric, tridiagonal, Toeplitz matrix $A$, where $A_{11} = -\frac{1}{2}$ and $A_{21} = 1$, and I need to solve the system $$ (A+I)x=b, $$ numerically where $b$ does not necessarily ...
1
vote
1answer
27 views

Trying to show convergence of a Forward Euler method based on step size restriction

I have shown that for the given ODE system, that when we apply the forward Euler method to something like \begin{align} \mathbf{y'} &= A\mathbf{y} \\ \mathbf{y}(t_{0}) &= y_{0} \\ t &\in ...
3
votes
1answer
103 views

Value of an integral involving the fractional part function

I have difficulties in evaluating the double integral defined in the following. Let $$\left\{ t \right\} = t - \lfloor t \rfloor, $$ $ t> 0$ be the fractional part function, where the ...
0
votes
0answers
12 views

Powers of matrices via the generalised Lanczos process

At each iterative step of the generalised Lanczos process for the pair of matrices (A,B), we obtain the following factorisation: $$ A Q_k = B Q_{k+1} \widehat{T}_k, $$ where $Q_k^T B Q_k = I_k$ and ...
2
votes
1answer
35 views

Technique to calculate rank of this matrix.

1) How can we calculate the rank of this matrix for $n > 3$ ? \begin{matrix} 1^2 & 2^2 & 3^2 & \cdots & n^2 \\ 2^2& 3^2 & 4^2 &\cdots & (n+1)^2 \\ ...
0
votes
0answers
44 views

Which of the following fixed point iterations will converge?

Which of the following fixed point iterations will converge? Why? Give the rate of convergence. (a) $x_{n+1} = \cos x_n$ (b) $x_{n+1} = \sin x_n$ (c) $x_{n+1} = \tan x_n$ For $10$ bonus ...
1
vote
1answer
36 views

Cholesky decomposition with unit diagonal

Let $A$ be real-valued (strictly) positive definite (P.D.) so that it has a unique Cholesky decomposition of the form $A = LL^T$ where $L$ is lower triangular. What PD matrices $A$ have a Cholesky ...
2
votes
1answer
53 views

Applied/Numerical Linear Algebra-Suggestions for Project

I am looking for suggestions for a research project in applied/numerical linear algebra. As far as requirements, there really aren't any except that the topic has to tie in somehow with numerical ...
6
votes
1answer
48 views

Floating point arithmetic operations when row reducing matrices

A numerical note in my linear algebra text states the following: "In general, the forward phase of row reduction takes much longer than the backward phase. An algorithm for solving a system is usually ...
1
vote
2answers
60 views

Explaining roundoff error when row reducing matrices

In my linear algebra textbook (in the context of row reducing and obtaining a matrix in echelon or reduced echelon form), there is a numerical note that reads as follows: "A computer program usually ...
1
vote
0answers
43 views

Least-squares solution to a transformation between coordinate frames

Suppose I have four coordinate frames in 3D space: A, B, X and ...
0
votes
0answers
20 views

Mixed Lognormal Model Calibration

Any ideas as to how to calibrate a mixed lognormal volatility model (Brigo and Mercurio 2002) for arbitrary N < 10? The paper seems vague with respect to implementation.
0
votes
0answers
15 views

LU Decopmostions with block

So both $A_{11}$ and $\hat{A_{22}}$ have $LU$ decompositions say $A_{11}=L_{1}U_{1}$ and $\hat{A_{22}}=L_{2}U_{2}$. Show that $ \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} ...
1
vote
1answer
77 views

How to obtain a convergent solution iteratively for a linear system of equations?

I am working on a problem that requires an iterative procedure to solve a linear system of equations, the system of equations in matrix form is: $$\underbrace{\begin{bmatrix} r_{11} & r_{12} ...
2
votes
1answer
27 views

How to prove Kahan's example on componentwise pertubation theory?

In Matrix Computations (4th edition) by Gene H. Golub and Charles F. Van Loan, Problem 3.5.3 asks the following problem (and citing Kahan, William. "Numerical linear algebra." Canadian Math. Bulletin ...
2
votes
0answers
19 views

Dense Rank Deficient Linear System

What are some of the best methods for solving a Dense Rank Deficient Linear System $Ax = b$, where $A$ is Dense, Symmetric but possibly Rank Deficient. I know SVD can solve it pretty nicely while ...
1
vote
1answer
32 views

Perspective transformation matrix application

I need to transform an angled photographed pice of paper to a "flat" image. I found this question & solution here on Mathematics and tried it out for the image given in the solution: The values ...
0
votes
0answers
75 views

Generalized SVD and weighted SVD

I've the following question: How should I select the $A$,$B$ matrices in the generalized singular value decomposition (GSVD) such that it solves the weighted version of the generalized singular value ...
5
votes
1answer
138 views

Convergence of Conjugate Gradient Method for Positive Semi-Definite Matrix

Let $A\in\mathbb{R}^{N\times N}$ be a positive semi-definite matrix, given $b\in\mbox{Col}\left(A\right)$ we want to solve the equation system $Ax=b$ . To add some notation, we define ...
1
vote
1answer
39 views

Any good books to practice on Endomorphisms as related to Diagonalization, Cayley-Hamilton, etc.?

Well, I am looking for books (graduate level) that covers linear maps (endomorphisms, to be specific) with emphasis on topics related to numerical linear algebra, like: diagonilzation, ...
-1
votes
1answer
41 views

Is matrix multiplication commutative for square matrices representing linear transforms?

On several occasions, I have heard that matrix multiplication is commutative for square matrices $A$ and $B$ when they represent linear transformations. Is this true? I know that in general $AB$ is ...
2
votes
0answers
48 views

Numerically stable method for angle between 3D vectors

I'm looking for a numerically stable method for computing the angle between two 3D vectors. Which of the following methods ought to be preferred? Method 1: $$ u\times v = ||u|| ||v|| \sin(\theta) ...
1
vote
1answer
96 views

Best approach for numerically computing the pseudo-inverse of a covariance matrix

What are the reasons to prefer eigenvalue decomposition over singular value decomposition for numerically computing the pseudo-inverse of a symmetric real matrix? In the case when you want to form the ...
0
votes
0answers
44 views

Finding the closest low rank correlation matrix?

I am looking to find the rank 3 correlation matrix approximation of a rank $n-1$ correlation matrix. This best approximation can be more clearly defined as the closest correlation matrix with rank 3 ...
3
votes
3answers
81 views

How to find all orthogonal matrices which commute with a given symmetric matrix?

Suppose we have a symmetric matrix $H$. I'd like to find all the orthogonal matrices $S_i$, which commute with it. Particularly I'm interested in the set of $S_i$, which are linearly independent from ...
-1
votes
1answer
21 views

QR Decomposition Inverse?

For QR Decomposition (of an n by n matrix) since A = QR, where A is a matrix, Q is an orthogonal matrix and R is the upper triangular matrix, does this mean that A$R^{-1}$ = Q? And if the above ...
0
votes
1answer
32 views

Find orthogonal operator to satisfy the transformation

everyone, here I have a question as shown in the figure. firstly ,I assume the standard matrix for the operator to be $A=[a_1, a_2, a_3]$ ,and I know the property that transpose of A=inverse of A ...
0
votes
0answers
26 views

Linear System with non zeros count constraint

I trying to solve a simple linear system: $Ax=b$ But with constraints like: $\sum{x_i}=S$, Usually S = 1. $L \le x \le U$, Lower & Upper bounds (usually $0 \le x \le 1$) And "Maximum count of ...
0
votes
1answer
25 views

Simplify the following in index notation

Simplify the following in index notation $I_{s,t}\delta_{s,n}\delta_{n,t}$ Since both $\delta$ 's contain an $n$ index does it simplify to $I_{s,t}\delta_{s,t}$ Then can you simplify further since ...
3
votes
2answers
50 views

Convergence for Conjuguate gradient method

I am trying to probe this corollary in a numerical PDE book: If $A\in \mathbb{R^{n\times n}}$ is symmetric and positive definite, then the conjugate gradient method reaches the exact solution in at ...
0
votes
1answer
40 views

An Optimal Value of a Diagonal Matrix $\Xi$ in $ H = U \Xi$

We have access to very accurate estimates of matrices $H$ and $U$ (both are $n \times k$, $n > k$) such that the following relationship holds $$ H = U \Xi$$ where $\Xi$ is a $k \times k$ diagonal ...
2
votes
1answer
60 views

Why are ill-conditioned systems of equations hard to solve iteratively?

Is there some intuition as to why ill conditioned system of equations hard to solve iteratively ( i.e. the convergence is slow) ? I've read convergence proofs of several methods, but still don't have ...
0
votes
1answer
48 views

Inversing badly-conditioned square matrix: methodology

I have a badly-conditioned square matrix. I need to inverse it. For inversing, currently I'm doing the following steps: I take the badly-conditioned matrix with size of $n$ by $n$ By reduced row ...
1
vote
1answer
41 views

Recover the inverse after interative solution of a linear system

I have solved the linear system $\mathbf{A} \mathbf{x} = \mathbf{b}$ with an iterative solver. The problem is well-posed ($\mathbf{A}$ is invertible, $\mathbf{b} \ne \mathbf{0}$, blah blah blah). ...
0
votes
1answer
37 views

integration and convolution

Please can some one help me on the following integration. $$ G(\nu)=\frac{1}{\Delta t}\int_{t_a - \frac{\Delta t}{2}}^{t_a + \frac{\Delta t}{2}} f(t_a -t)e^{-2\pi\nu it}dt $$ where ...
3
votes
2answers
74 views

The purpose of LU Decomposition

I was curious if anyone could help me understand why an LU decomposition is useful from a theoretical or computational standpoint. It seems to me that it is just a way to teach students the basics of ...
0
votes
1answer
31 views

Eigen value system? solution

I have the following system. $AW = \lambda B W$ Where $A,B,W$ are matrices and $\lambda$ is a scalar. The values of $A,B$ and $\lambda$ are known. $B$ is invertible. This is a solution to an ...
0
votes
0answers
18 views

Does the Conjugate Gradient Method provide an eigenvalue estimate?

Suppose that we apply a Krylov subspace method to the linear system $A x = b$. For example, if $A$ is symmetric positive-definite, then the Conjugate Gradient method may be used. I remember that the ...
1
vote
1answer
35 views

Is LU decomposition of matrices efficient for today's standards?

This is in the spirit of a previous question of mine about the efficiency of the QR algorithm. The reason for asking is that I want to motivate some students, and I'm also curious. I do understand ...
0
votes
1answer
83 views

Norm of Outer Product

Let $x \in \mathbb{R}^N$ and $ y\in \mathbb{R}^M$. Show that $\|xy^T\|_{\infty}=\|x\|_{\infty}\>\|y\|_1$ I've been able to show the following: $\|xy^T\|_{\infty}= \|xIy^T\|_{\infty} \le ...
1
vote
0answers
27 views

LU-factorisation of a square matrix

I need to show that the following matrix cannot be factor into the product LU. \begin{equation} A=\begin{bmatrix}1&2&-1\\2&4&0\\ 0&1&-1\end{bmatrix} \end{equation} I did the ...
0
votes
0answers
36 views

Search Direction in Conjugate Gradient

Could you help me with a Conjugate Gradient question? In using CG to solve $Ax = b$, why is the search direction $p_{k+1}$ in CG chosen as a linear combination of the residual $r_k$ and previous ...
2
votes
0answers
36 views

Solving a structured partitioned linear system

I am trying to solve the following partitioned linear system, where each letter represents a block $\begin{pmatrix}-H & A^T & I_n \\ A & 0_1 & 0_2 \\ z_D & 0_2^T & ...
0
votes
1answer
45 views

Heat equation in 1D with collocation method

I want to use the collocation method to solve $u_t=u_{xx}$. I impose the PDE pointwise and expand the solution in Fourier Series: $$ \partial_{t}\sum_{k=-K}^{K}\hat{u}_{k}(t)\ ...