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

learn more… | top users | synonyms

0
votes
4answers
53 views

Is it possible to generate $A$ from a linear system of the form $Ax=b$ given $x$ and $b$?

Take a linear system of the form $Ax=b$. Usually, for obvious reasons, we want to find $x$ given $A$ and $b$. As you all know, the solutions may not be unique, or exist, and many algorithms have been ...
0
votes
0answers
34 views

Practical examples/implementation details for Gauss-Seidel method

I'm having a presentation on Gauss-Seidel iterative method, and although it isn't mandatory , I would like to have some practical examples for this method (a system of linear equations with n>=1000, ...
1
vote
1answer
49 views

How to find Housholder reflection

For example, let say I have a matrix$$ \left(\begin{array}{rrr} 3 & 3 & 0 \\ 0 & 0 & 0 \\ 4 & 1 & 3 \end{array}\right) $$ and the Householder has the form $H = I -2uu^T$, and ...
0
votes
0answers
16 views

Iterated Schur complement for block matrices

Suppose you have got a symmetric block matrix $A = \begin{pmatrix} A_{1,1} & \dots & A_{1,n} \\ \vdots & & \vdots \\ A_{n,1} & \dots & A_{n,n} \end{pmatrix}$ Suppose that ...
1
vote
1answer
35 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
34 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
66 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
37 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
73 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
23 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
63 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
22 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
94 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
11 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
34 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
42 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
33 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
45 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
42 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
47 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
40 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
18 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
13 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
75 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
26 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
16 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
20 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
36 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
121 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
37 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
35 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
36 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
54 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
40 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
64 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
20 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
23 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
22 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
24 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 ...
2
votes
2answers
47 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
51 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
41 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
40 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
34 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
59 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
30 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
15 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
29 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
64 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 ...