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

learn more… | top users | synonyms

3
votes
1answer
122 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
37 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
45 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
39 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
64 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
54 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
64 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
45 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
23 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
81 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
40 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
149 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
141 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
43 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
42 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
61 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
123 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
46 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
112 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
22 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
32 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
52 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
76 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
51 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
42 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
38 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
84 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
32 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
22 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
39 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
106 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
29 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
37 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
43 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
47 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)\ ...
0
votes
1answer
14 views

Linear independence of three simple functions (2.9-22)

Why is the following set of three functions linearly independent on an interval $I$ with $x>0$ if $k_2$ can take on any value besides zero and still hold true for a zero sum or that $k_1=k_3$ which ...
1
vote
1answer
38 views

A problem about lub and glb of matrix

For any matrix $A\in \mathbb{C}^{n\times n}$, define $$lub_K(A):= \inf\{\alpha\geq 0: AK\subset \alpha K\},$$ and $$glb_K(A):= \sup\{\alpha\geq 0: \alpha K\subset AK\},$$ where $K$ is a equilibrated ...
0
votes
1answer
146 views

subtraction between sum of all elements of two symmetric matrices

Let assume that I have an $n\times n$ symmetric matrix $A$ and I know $A^{-1}$. Now, I have a new matrix $$M = \begin{pmatrix} A & b \\ b^T & c \end{pmatrix},$$ where $b$ is a vector and ...
1
vote
1answer
32 views

How to prove or disprove the matrices formula

Could some one give me some hints about the following prove of disprove: (a) If $PXX^TP^T=QXX^TQ^T$, then $PX=QX$; (b) If $PXX^T=QXX^T$, then $PX=QX$. In the above formulas, $P$, $Q$ and $X$ are ...
2
votes
1answer
62 views

Eigenvectors of transition matrices in PageRank algorithm

In my probability course, we were discussing applications of Markov Chains to computer science -- in particular, how the PageRank algorithm goes about finding stationary distributions, and thus, ranks ...
0
votes
2answers
303 views

How to solve $Ax=b$ via backward and forward substitution on Matlab

How can I solve $Ax=b$ in Matlab code via LU factorization. I know that the command [L,U]=LU(A) stores the ...
2
votes
0answers
43 views

Wiedemann for solving sparse linear equation

I am new member. I am researching in Wiedemann algorithm to find solution $x$ of $$Ax=b$$ Firstly, I will show a Wiedemann's deterministic algorithm (Algorithm 2 in paper Compute $A^ib$ for ...
0
votes
1answer
50 views

help to find SOR optimal parameter $w$

Please let following linear system as $Ax=b$: $$\begin{array}{l} 6a{x_1} + {x_2} + {x_3} = 1\\ {x_1} - 3a{x_2} + 4{x_3} = 2\\ {x_1} + {x_2} - 2a{x_3} = 3 \end{array}$$ Help me to prove that the ...