Questions on the various algorithms used in linear algebra computations (matrix computations).
1
vote
1answer
20 views
What is the fastest algorithm to solve the eigenvector of a transition matrix of a Markov Chain?
Given a transition matrix of a Markov chain, $P$, I want to solve the left eigenvector of $P$, namely a row vector $\alpha$ such that
$$
\alpha P = \alpha
$$
I know the algorithm to solve a linear ...
1
vote
1answer
47 views
How to find the unknown values in this Numerical Integration type?
Given the following type of numerical integration:
$$I(f)=\int_0^1 f(x) \, dx \approx \frac 12 f(x_{0}) +c_1 f(x_1) $$
a) Find the values of: the coefficient $c_1$ and points $x_0$ and $x_1$ so ...
0
votes
0answers
55 views
A minimax problem
Let $\omega$ be a non zero real number, $(\lambda_i)_{i = 1}^n$ be a sequence of $n$ real numbers and
$$u_{i}:=1-(1-\lambda_{i})\,\omega.$$
Show that if we pick
...
0
votes
1answer
18 views
Existence criteria for the LU decomposition of a tridiagonal matrix
In this link, the following result is presented without proof:
Let $a, b, c$ be the lower off diagonal, diagonal, and upper off diagonal elements of a tridiagonal matrix. A pivotless LU ...
1
vote
1answer
16 views
Non-monotonic decrease of residuals in Conjugate Gradients:
In some of my numerical programming using conjugate gradient solvers, I noticed an alarming problem: The residuals were not monotonically decreasing to zero, but were sometimes increasing. In this ...
1
vote
0answers
28 views
About the Generalized singular value decomposition (GSVD).
I have studied about Singular value decomposition (SVD) and had solved few numerical examples to understand SVD. Now I am studying Generalized singular value decomposition (GSVD). I followed this ...
0
votes
0answers
16 views
Can I detect repeated eigenvalue by inverse iteration?
Suppose all eigenvalues of $A$ are nonnegative. By using inverse iteration $A-\mu I$ for many values of $\mu\ge 0$, I can find eigenvalues of $A$. If $A$ is a $n\times n$ matrix and have different $n$ ...
1
vote
2answers
94 views
+100
On integral of a function over a simplex
Help w/the following general calculation and references would be appreciated.
Let $ABC$ be a triangle in the plane.
Then for any linear function of two variables $u$.
$$
\int_{\triangle}|\nabla ...
-4
votes
0answers
43 views
Linear algebra vector space [duplicate]
Let $W$ be the set of all solutions $(a, n, b, m)$ of $a + 3b + 4m = 0$, i.e.
$$W=\{(a,n,b,m)\in\mathbb{R}^4: a+3b+4m=0; a,n,b,m\in\mathbb{R}\}$$
Show that W is a vector space. Is vector $(6,8,6,4)\in ...
0
votes
0answers
14 views
Shifted inverse power method in Octave.
EDIT: Ok, I've managed it. It was very stupid bug... I must write $p=L\(P*z0)$ etc....
I'm trying to write a function which returning vector $a$ (vector of eigenvalues of matrix $A=A^T \in ...
0
votes
0answers
8 views
Error bound on matrix vector multiplication
I am multiplying a matrix $A$ with vector $p$. However, the matrix $A$ isn't accurate.
Some (a very small fraction) of the element's value is changed from $a_{i,j}$ to {0,$-a_{i,j}$, $2a_{i,j}$}. ...
2
votes
0answers
19 views
Solver for sparse linearly-constrained non-linear least-squares
Reposted from stackoverflow on the advice of Nick Rosencrantz:
Are there any algorithms or solvers for solving non-linear least-squares problems where the jacobian is known to always be sparse, and ...
1
vote
0answers
22 views
Algorithm to compute similarity computation
I have a similarity transformation of matrices from the type $B = P^{-1}AP$. It is known that $A$ and $P$ are invertible matrices, but not orthogonal.
Given that I have the matrices $P$ and $A$ I ...
2
votes
1answer
28 views
Block matrix notation
Given that $A$ is a real, rectangular matrix of dimension $m \times n$ and
$\begin{align}
A = \left[\begin{array}{c} I \\ e^{\intercal} \\ -e^{\intercal}\end{array}\right]
\end{align}$ is represented ...
1
vote
2answers
25 views
solving linear recurrence - general solution confusion
I've been trying to get my head around this for days. I understand what is going on with the calculation of a linear recurrence and I also understand how the characteristic is obtained.
What is ...
1
vote
0answers
40 views
Approximation of (FEM) by (FDM)
[Ciarlet 3.4-6] Consider the functional
$$J_h : v = (v_i)\in\mathbb{R}^N\longrightarrow J_h(v)\ :=\ \frac{h}{2}\sum_{i=1}^N\left(\left[\frac{v_{i+1}-v_i}{h}\right]^2 + c_iv_i^2\right) - ...
3
votes
1answer
55 views
About iterative refinement to the solution of the linear equations
I want to know what is iterative refinement for improving the solution to the linear equations? How they improve solutions and what are the various techniques for the iterative refinements?
Any ...
1
vote
0answers
20 views
Multigrid Interpolation and Restriction operators
I have a question about the restriction and the interpolation operators of a Multigrid algorithm.
Let those be given:
The full weighting restriction stencil (in 2D): $\frac{1}{16} \left[ ...
0
votes
1answer
51 views
error for Conjugate gradient method
Suppose A is a real symmetric 805*805 matrix with eigenvalues 1.00, 1.01, 1.02, ... , 8.89,8.99, 9.00 and also 10, 12, 16, 36 . At least how many steps of conjugate gradient iterations must you take ...
3
votes
1answer
147 views
Sum of eigenvalues and singular values
How one can prove that for a matrix $A\in \mathbb{C}^{n\times n}$ with eigenvalues $\lambda_i$ and singular values $\sigma_i$, $i=1,\ldots,n$, the following inequality holds:
$$ \sum_{i=1}^n ...
0
votes
1answer
37 views
$\lambda_{min}\left (\frac{A+A^*}{2} \right )\leq \sigma_{min}(A)$
For $A \in \mathbb{C}^{n \times n}$, how to show that
$\displaystyle \lambda_{min}\left (\frac{A+A^*}{2} \right )\leq \sigma_{min}(A)$?
2
votes
2answers
62 views
Minimum eigenvalue and singular value of a square matrix
How to show that the relationship $\left | \lambda_{min} \right | \geq \sigma_{min}$ holds between the minimum eigenvalue and singular value of a square matrix $A \in \mathbb{C}^{n \times n}$?
1
vote
1answer
20 views
Preconditioning and effects on precision of solution of LSE
In my courses on numerical analysis I have been tought that the main and principle motivation for preconditioning linear systems of equations is to increase the convergence rate of iterative solvers ...
0
votes
1answer
62 views
Largest and smallest eigenvalues of a hermitian matrix
How to show that the largest and smallest eigenvalues of a hermitian matrix $A \in \mathbb{C}^{n \times n} $ can be found as:
$\displaystyle \lambda_{max} = ...
0
votes
0answers
24 views
What is the error in Newton's Method for Matrix Inversion?
I need it to invert a matrix. Wikipedia explains that there is a generalization of the Newton Method for matrices. However, there is nothing mentioned about the error bounds.
Suppose we have, as ...
0
votes
1answer
25 views
Underdetermined linear systems least squares
I have an underdetermined linear system, with 3 equations and four unknows. I also know an initial guess for these 4 unknows. The article I am reading says: We can solve the system using the least ...
0
votes
1answer
46 views
Condition number for non-square matrix?
From what I understand the condition number of a non-square matrix A is its largest singular value divided by its smallest nonzero singular value:
$\kappa(A) = \sigma_1/\sigma_n $.
Where ...
2
votes
1answer
29 views
Problems where SPD linear system arises
I know some of the places where SPD linar systems arises such as elliptic PDEs and normal equations. Can I have a more comprehensive list of scientific applications which require solving SPD linear ...
3
votes
1answer
36 views
Polynomial Condition Number
I have a question, from "Applied Numerical Linear Algebra"(James W. Demmel), that I don't know how to do.
Consider $\mathbb{R^{d+1}}$ as the set of polynomials of degree $\leq d$ and $S_a$ the set of ...
3
votes
2answers
44 views
Matrix Calculus in Least-Square method
In the proof of matrix solution of Least Square Method, I see some matrix calculus, which I have no clue. Can anyone explain to me or recommend me a good link to study this sort of matrix calculus?
...
0
votes
0answers
37 views
Singular Value Decomposition uniqueness
I assume $\mathbf{A}$ is an $m\times n$ non-negative real valued matrix such that $m>n$ and $\operatorname{rank}(\mathbf{A})=n$. I have already calculated the overdetermined system for a least ...
4
votes
1answer
50 views
Help in Proving a theorem
For the last few days I am trying to prove Result 2 which I have written below that uses the concepts of matrix decompostions to write matrix $A$ in the block form. I need help to prove this ...
1
vote
1answer
55 views
Why SVD on $X$ is preferred to eigendecomposition of $XX^\top$ in PCA
In this post J.M. has mentioned that ...
In fact, using the SVD to perform PCA makes much better sense numerically than forming the covariance matrix to begin with, since the formation of ...
1
vote
0answers
23 views
Boltz method for solving normal equations
Recently I came across an interesting comment in a geodetic paper which follows as:
"Initially, the
normal equations were solved using the Gaussian method
of successive elimination. This method, ...
0
votes
1answer
75 views
Solve: This System of equations for $X$ (does a real solution, exist?)
How can I solve $AX + diag(X)[I-c]=0$ for $X$?
All matrices have real entries, $diag(X)$ is a diagonal matrix with the diagonal entries being the diagonal entries of $X$, and $c$ is a constant, real ...
1
vote
1answer
49 views
How to find the Householder transformation?
Assume $x=(1,0,4,6,3,4)^T$. Find a Householder transformation and a positive number $\alpha$ such that $Hx=(1,\alpha,4,6,0,0)^T$.
I'm sorry that I don't know how to start with this problem. A ...
1
vote
2answers
54 views
A question about unitary matrix
We know that a complex square matrix V is unitary if
\begin{eqnarray}
VV^{*} = V^{*} V = I
\end{eqnarray}
I want to write matrix V into block matrix form, say $V = [V_1, V_2]$. My question is ...
1
vote
1answer
37 views
A basic question about convergence of matrix
I am confused with this very basic question.
We know that for a square matrix A the following two properties are equivalent to A being a convergent matrix:
1: $lim_k\rightarrow \infty \|A^{k}\| = ...
0
votes
1answer
17 views
Conjuagate Gradient on Periodic BCs
I'm currently writing a CG solver. It works perfectly fine for Dirichlet boundary conditions, however, I also want it to work with periodic BCs.
The problem I'm solving is a 3D Poisson equation.
I ...
2
votes
0answers
32 views
Determinant error bound is better than norm bound for matrix product
In by textbook on numerical algebra, it states that for a numerical matrix product the error bound:
$|A B - \hat{A} \hat{B}| \le c|A| |B|$
is a stronger expression than
$\|A B - \hat{A} ...
0
votes
1answer
35 views
what we can say about block inverse besides schur complement
Suppose I have a matrix $M$, which has a block structure $%
\begin{bmatrix}
A & B \\
B^{T} & C%
\end{bmatrix}%
$, where A has the inverse. How can I better numerically calculate $A^{-1}B$ ? ...
0
votes
1answer
30 views
How do I get a matrix from a coordinate system?
What is the matrix of the reflection at the line $y = x-2$?
How do I get the matrix at homogeneous coordinates? I don't get this question at all. I have really no idea of what I am supposed to do ...
2
votes
1answer
93 views
Relation between positive definite Hermitian matrices with their inverses
Let $A$ and $B$ be two positive definite Hermitian matrices. Show that the Hermitian matrix $$C\ =\ A^{-1} + B^{-1} - 4(A + B)^{-1}$$ is also positive definite.
Thanks in advance.
0
votes
1answer
127 views
Column space of a matrix?
Recently I started learning about matrices and know for example that the pivot columns of a matrix form a basis for the column space of this matrix. I just can't seem to find out when two matrices ...
1
vote
2answers
43 views
Align basis of vector space with that of subspace
Suppose I have two real vector spaces $V,S\subset\mathbb{R}^n$ and $S\subset V$. Say the dimension of $V$ is $l$ and that of $S$ equals $m<l$. They are given in terms of their basis vectors $v_i, ...
1
vote
0answers
36 views
Eigenvalues of discretized linear integral operator
Suppose I have the following kernel operator:
$Af(x) = \int_{-1}^1 K(x-y)f(y)dy$
which is also positive and compact. Hence, it has a countable set of positive eigenvalues. Suppose those eigenvalues ...
7
votes
1answer
96 views
Sum of idempotent matrices is Identity
[Ciarlet, Problem $1.1-10$] Let $A_k$, $1 \leq k\leq m$, be matrices of order $n$ satisfaying
$$\sum_{k=1}^mA_k\ =\ I.$$
Show that the following conditions are equivalent.
$A_k = ...
0
votes
1answer
155 views
QR Algorithm information
How can we perform 2 iterations of the QR Algorithm to the following matrix?
$$A =\pmatrix{2 & -1 & 0 \\
-1 & -1 & -2 \\
0 & -2 &3
...
1
vote
0answers
43 views
Criterion for detecting rank-deficiency via QR decomposition?
I apologize in advance if this is an ill-posed question -- I'd appreciate advice on what pieces are missing as much as an answer.
I'm solving a system like $P \approx X Y^T$, where P is a large ...
3
votes
2answers
84 views
When do two matrices have the same column space?
Recently I started learning about matrices and know for example that the pivot columns of a matrix form a basis for the column space of this matrix.
I just can't seem to find out when two matrices ...
