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

learn more… | top users | synonyms

4
votes
0answers
110 views

Solving linear equations with block structure and weak coupling

I have a standard set of linear equations $Ax=b$ where the Hessian matrix $A$ has the special block structure as shown: $A= \begin{pmatrix} T & U\\ U^T & V \end{pmatrix}$, $x= ...
2
votes
0answers
23 views

Why use the logarithm of the relative error?

In my numerical analysis course, we had an assignment to use MATLAB to numerically solve the Poisson Equation $-\nabla\cdot\nabla u = 0$ in one dimension. We computed the numerical solution, plotted ...
0
votes
0answers
26 views

Simplifying matrix expressions with LU decomposition?

If $A, B, C$ are $n \times n$ matrices, with $B$ and $C$ nonsingular, and $b$ is a vector of size $n$, how could one determine $$x = B^{-1}(2A + I)(C^{−1} + A)b?$$ I assume the solution has to do with ...
0
votes
0answers
26 views

Is this a correct equation for numerical differentiation?

I tried to write first derivative of Lagrange's Interpolating Polynomial in a compact way. Is this correct?
0
votes
0answers
20 views

How to derive this formula for numerical differentiation? [duplicate]

I've read from a book that numerical differentiation for a point $x_i$ can be obtained by taking a linear combination of function values of other points $f(x_j)$. I don't have a clue how the ...
-2
votes
1answer
66 views

How was this formula for differentiation derived?

[![enter image description here][1]][1]Please tell me how this formula for numerical differentiation derived. I think it has something to do with Vandermonde Matrices but I am not quite sure how to go ...
1
vote
1answer
37 views

How to derive the Vandermonde Determinant?

I watched this video https://www.youtube.com/watch?v=87iJTcXqTKY explaning the Vandermonde Determinant I understood everything but I was wondering why the guy never mentioned the (-1)^(i+j) term used ...
0
votes
1answer
38 views

Solve matrices both algabraic and numerically

Can someone explain me to what to do here? I don't understand the question, or how to solve the problem. Should I use some theorems, to solve it?
1
vote
3answers
44 views

How to connect the definition of eigenvectors from linear algebra to their definition in Machine Learning

In Linear algebra the eigenvectors of a matrixs are these vectors that don't change their direction after applying this matrix( as a Transformation) to the space. But In machine learning (PCA to be ...
0
votes
1answer
28 views

Solving an equation involving the root of a quartic

Given that $ a = ((k-3)\sqrt{v})/s$ where $k$ and $v$ are known. I have to solve the following equation for $s$: $$q(a,b) = s \sqrt{v},$$ where $b = 1.08148a^2+\epsilon$ and $\epsilon>0$ a very ...
1
vote
0answers
32 views

Is this a correct way to approximate a derivative

I have some function $S(\hat y)$ which I want to approximate its derivative with respect to a vector. It's a tad complicated, I'll try and explain. $S$ is a function of $\hat y$ only, but $\hat y$ is ...
1
vote
1answer
46 views

Matrix equation involving pseudoinverse and trace

Let $P$ be an unknown complex $m \times n$ tall matrix ($m\geq n$, full column-rank), and $D$ a known real $m \times m$ diagonal matrix with positive entries. Is there a solution for $P$ from the ...
1
vote
1answer
36 views

Numerical diagonalization of a random hermitian matrix $H=U\Lambda U^{-1}$: enforce uniqueness and uniformity of $U$

I've stumbled across this seemingly simple question, but I could not find a satisfactory answer. Suppose I have a complex hermitian random matrix $H$. It can be diagonalized by a unitary ...
0
votes
0answers
27 views

Is $ \| \sum_{i \in [k]} \otimes^3 v_i - T \|_F^2 + \theta \| \sum_{i \in [k]} \otimes^3 v_i \|_F^2$ convex?

I am trying to find the minima of the following equation with respect to $v_i$, $i \in [k]$, to solve an optimization problem but I can't manage to make (stochastic or not stochastic, neither of them) ...
0
votes
0answers
46 views

Prove Norm Theorems

I have the following as given: Let $A \in C^{m\times m}$. Then: 1) $$\lVert A\rVert_1 =\sup_{v\in C^m \setminus\{0\} }{\lVert A_v\rVert_1 \over \lVert v\rVert_1} = \max_{j} \sum_i |a_{ij}|$$ How can ...
1
vote
1answer
38 views

Numerically Solving a Poisson Equation with Neumann Boundary Conditions

The Problem Suppose I have an equation of the form $\nabla^2 \phi(x) = f(x)$ on the interval $A \le x \le B$, where $f(x)$ is known and $\phi(x)$ is unknown. I have Neumann-type boundary conditions: ...
1
vote
1answer
13 views

inequality in compressed sensing

Let $h\in R^n$ is a k-sparse vector, then how can i prove this inequality $$||h||_p\leq k^{1/p-1/q}||h||_q\ \ ,\forall p\in[1,q]$$ where $q\geq 1.$ please help.
0
votes
1answer
19 views

principle component analysis - manual calculation - problem finding axis and eigenvectors on approximated covariance matrix

For the sake of a future tutorial video, I'm trying to manually perform the calculation of the principle axis and associated variances. Of course i'm trying to compute the eigenvectors and ...
2
votes
0answers
54 views

Faster Cholesky factorization of $diag(\mathbf{x}_{i}) \otimes \mathbf{A} + \mathbf{B}$ for $i=1,\ldots,n$?

I have many positive integer vectors $\mathbf{x}_{i} \in \mathcal{N}^{d_1}$, $i=1,\ldots,n$, a p.s.d. matrix $\mathbf{A} \in \Re^{d_2\times d_2}$ and a p.s.d. matrix $\mathbf{B} \in \Re^{d_1d_2\times ...
2
votes
1answer
63 views

show that $\lambda_{max}(B^{-1}A) \leq 1$ (eigenvalues, matrices, preconditioning)

I'm trying to get more familiar with eigenvalues and matrices but struggle to see the following: $\lambda_{max}(B^{-1}A) \leq 1$ $A \in \mathbb{R}^{n \times n}$ is symmetric, positive definite ...
1
vote
1answer
30 views

Backward Euler method and the trapezoidal method are zero-stable

Show that backward Euler method and the trapezoidal method are zero- stable. I have no clue to prove the claim. Can anyone give me some hints? Thank you in advance. For someone who don't know ...
9
votes
3answers
1k views

I get a wrong determinant - why?

I'm trying to calculate the following determinant: $$\begin{vmatrix} a_0 & a_1 & a_2 & \dots & a_n \\ a_0 & x & a_2 & \dots & a_n \\ a_0 & a_1 & x & \dots ...
1
vote
1answer
32 views

Calculating the determinant by upper triangular reduction - can you check if it's correct?

Exercise: Calculate $$\begin{vmatrix} a_0 & a_1 & a_2 & \dots & a_n \\ -x & x & 0 & \dots & 0 \\ 0 & -x & x & \dots & 0 \\ \dots & \dots & ...
0
votes
0answers
15 views

Minimising two interdependent equations with least squares regression.

Originally, I had a set of points in three dimensional space that I was fitting using linear regression. So my model is $$Y = \alpha A+ \beta B$$ where $Y = \{y_i\}$ is the dependent variable, and ...
2
votes
1answer
46 views

Doubts on inverse power method

I found written that if matrix A is real and you use the Power method to find eigenvalues then "If the matrix and starting vector are real then the power method can never give a result with an ...
0
votes
0answers
17 views

condition number of a matrix with diagonal ones and constant else. [duplicate]

Consider the matrix $$A=\left(\begin{array}{ccccc} 1 & c & \cdots & c\\ c & 1 & \ddots & \vdots \\ \vdots & \ddots & \ddots & c\\ c & \cdots & c & 1\\ ...
0
votes
1answer
62 views

Fastest way to solve linear system with block symmetric banded/Toeplitz matrix

I have a matrix of the following form: The size of the matrix may grow to be large, but the general pattern of being blockwise symmetric and banded (with 5 bands) will always hold. What is the ...
1
vote
1answer
43 views

Finding the Coefficient Matrix of a Spring-Mass System

So as part of a class in numerical linear algebra, we're exploring the topic of banded matrix system. I've come across a problem that involves Hooke's Law, but I'm having a little difficulty ...
0
votes
1answer
28 views

SVD for Seam Carving

Could SVD be used for Seam Carving ? I am making a small program for a uni course and I'm looking for different ways to calculate pixel energy; which made me come across SVD. Among others, I have ...
1
vote
0answers
14 views

How to determine if an algorithm converges for solving Ax = b in practice?

Suppose I am using iterative refinement. I am updating the solution $$x^{(k+1)} = x^{(k)} +p$$ where $Ap = b - Ax^{(k)}$. If $A$ is ill-conditioned, then we can not simply use residual norm or the ...
0
votes
1answer
30 views

How to find a number greater than the largest (smaller than the smallest) eigen value of a matrix efficiently?

I have a symmetric matrix $A$, I want to find a number say $\lambda_1$ which is greater than $\lambda$,i.e. the largest eigen value of the matrix $A$. It doesn't need to be equal to $\lambda$. But ...
0
votes
2answers
29 views

$LU$ Factorization, improving upon stability

I was wondering when we add partial pivoting to an $LU$ factorization to a matrix $A$ it supposedly changes the data structure but improves the overall algorithm since we get better numerical ...
2
votes
0answers
25 views

Iterative methods: What happens when the spectral radius of a matrix is exactly 1?

I know that an iterative method (I'm using Jacobi and Gauss-Seidel in this case) will converge iff the spectral radius (max absolute value of eigenvalues) of its iterative matrix is strictly less than ...
1
vote
0answers
31 views

What is the function of the pivot index vector in Gauss Jordan Elimination with full pivoting?

In numerical recipes, on page 39 (page 4 of the pdf) the following algorithm has been suggested for finding a pivot: ...
2
votes
1answer
41 views

Determining symmetricity of a matrix by multiplying with random vectors?

Stemming from an approach in a hint/answer to this question here. The idea is presented to determining wether a matrix is symmetric or not by measuring the following: $$e = \|({\bf Av})^T - ({\bf ...
1
vote
2answers
31 views

Is there an iterative way to evaluate least squares estimation?

Suppose to have a set of data $\{y_i, u_i\}_{i=1}^m$, where $y_i \in \mathbb{R}$ and $u_i \in \mathbb{R}^n$. The claim is that $$y_i = u_i^\top \theta + \varepsilon$$ where $\theta \in ...
0
votes
1answer
38 views

Prove there exist such that $A = [T]_\beta$ and $B = [T]_\gamma$ [closed]

Let $A$ and $B$ be similar $n \times n$ matrices. Prove that there exists an $n$-dimensional vector space $V$, a linear operator $T$ on $V$, and ordered bases $\beta$ and $\gamma$ for $V$ such that $A ...
1
vote
3answers
42 views

upper bound of a function $n^{1/\log(n)}$

I have the following expression $n^{1/\log(n)}, \quad where \quad n \in [1, 10,000]$. When I solve this numericall, I get the resultant value 2.718282 for all $n \in [2, 10,000]$. On this basis, I can ...
3
votes
1answer
45 views

An exercise with linear maps

I'm solving the following exercise: $\newcommand{\RR}{\mathbb{R}}$ Let $f: \RR^3 \rightarrow \RR^4: (a,b,c) \mapsto (a+2b+c, b+c, a + 2b + 3c, a + b + 2c)$ Find the basis of $f^{-1}(E)$ ...
1
vote
1answer
33 views

Choosing value of ω for SOR

I am learning about successive overrelaxation, and I'm wondering if there is an intuitive reason as to why ω must be between 0 and 2. I know that the method will not converge is ω is not on this ...
1
vote
0answers
48 views

Dynamically equivalent of numerical solution of $y' = f(y)$.

Consider an autonomous system $y' = f(y)$ and a fixed step size $h$. a) Show that the trapezoidal method applied $N$ times is equivalent to applying first half a step of forward Euler, (i.e ...
0
votes
0answers
12 views

matrix optimization problem techniques

I'm looking for some resources on learning techniques commonly used in matrix optimization. For example, minimization of the Frobenius/nuclear/weighted norm of a function of a matrix subject to ...
2
votes
1answer
33 views

Unitary diagonalization of matrices

Can someone tell me whether every square matrix $A\in \mathbb{R}$ unitarily diagonizable? If yes what is a necessary and sufficient condition for a square matrix $A\in \mathbb{R}^{n\times n}$ to be ...
0
votes
0answers
44 views

Beginner Linear Algebra 1 equation with 3 variables

I do not understand what to put into the remaining values. I tried to solve for the y and z like I did for the x, but the system is telling me that is incorrect. Some help would be appreciated
0
votes
1answer
31 views

Is there any Eigen value decomposition, which can be warm-started?

I have a Matrix, $A$ which is positive semidefinite. No consider, $B=A+\Delta$. I have Eigen decomposition of $A$ and $\Delta_{ij}<= \epsilon_1$, $\Vert \Delta \Vert_F <= \epsilon_2$. Is there ...
3
votes
1answer
38 views

$LU$ Factorization

Suppose the $A\in\mathbb{R}^{n\times n}$ is nonsingular and that $A = LU$ is its $LU$ factorization. Give an algorithm that can compute, $e_i^TA^{-1}e_j$,i.e., the $(i,j)$ element of $A^{-1}$ in ...
0
votes
1answer
26 views

Is it true that solving a triangular system using forward or backward substitution numerically stable?

The system is $TX = B$, where $T$ is a triangular matrix, $X$ is a unknown matrix, and $B$ is the RHS matrix. I know the system $Tx = b$ is backward stable where $b$ is a RHS vector. Detail check ...
1
vote
1answer
82 views

Best algorithm to compute the first eigenvector of symmetric matrix

Assume that we have a real symmetric matrix $\mathbf{A}\in\mathbb{R}^{n\times n}$ obtained as following : $$\mathbf{A}=\mathbf{N}-\mathbf{P},$$ with $\mathbf{N}\in\mathbb{R}^{n\times n}$ and ...
1
vote
0answers
30 views

Galerkin formulation of 1D linear Schrodinger equation

I am interested in the weak (Galerkin) formulation of the 1D Schrodinger equation: $i u_t−\beta u_{xx}=0$ and $u(x,0)=u_0(x)$. As usual, we do integration by parts which yields: $i (u_t,v)+\beta ...
0
votes
0answers
25 views

Computing a new inverse given information from an earlier inverse:

Suppose I have linearly independent set of vectors $v_1 ... v_k \in \mathbb{R}^{k}$. I can let $B = [v_1 ... v_k]$ and by applying Gaussian elimination on the matrix $$ [ B \ I_k] $$ I end up ...