Questions tagged [numerical-linear-algebra]

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

0
votes
1answer
42 views

Inverting a matrix with the same diagonal entries in a particular form

Hi I'm struggling with this inversion and any help would be greatly appreciated. I want to invert the following $\mathbb R^{m\times m}$ matrix \begin{bmatrix} 1 + m & m & \dots &...
1
vote
1answer
57 views

Simplify this expression with divided differences.

The divided differences are defined as follows $$ f[x_i] := f(x_i), \quad f[x_0, \ldots, x_n] := \frac{f[x_1, \ldots, x_n] - f[x_0, \ldots, x_{n - 1}]}{x_n - x_0} \quad \text{for } n \ge 2 $$ For ...
0
votes
0answers
43 views

Least Squares Normal Equations in Explicit Form

I am struggling with the following least squares problem: Find the minimiser x* $\in \mathbb{R}^{m}$ of $$F(\textbf{x})=||\textbf{b}-A\textbf{x}||_2$$ where $A \in \mathbb{R}^{(m+1) \times m}$, $...
0
votes
0answers
43 views

Computation of $k$ dominant right singular vectors without SVD computation

I have a maxtrix ${\bf A} \in \mathcal{C}^{m \times n}$, where $m < n$. However, the $m$ and $n$ are large numbers (for eg: m = 50, n = 250). I need to find the $k$ dominant right singular vectors ...
1
vote
2answers
66 views

Solve $\mathop{\arg\max}_{{v \in \mathbb{R}^m, \| v \| = 1}} v^T A A^T v$ with SVD

Let $A \in \mathbb{R}^{m \times n}$ be a matrix with full rank and $m \le n$. How can we solve the problem $$ \mathop{\arg\max}\limits_{\substack{v \in \mathbb{R}^m \\ \| v \| = 1}} v^T A A^T v $$ ...
2
votes
2answers
165 views

Different condition numbers of $\begin{pmatrix} a & b \\ b & c \end{pmatrix}$

Let $a,b,c \in \mathbb{R}$ and $A := \begin{pmatrix} a & b \\ b & c \end{pmatrix}$ and $\det(A) \neq 0$. Find the condition number with respect to the 1-, 2- and $\infty$-norm and discuss ...
0
votes
1answer
42 views

Why does non constrained MPC gives double gained input values?

Assume that we have our discrete state space model: ...
1
vote
1answer
63 views

How can I find partial pivoting matrix $P$ from $PA=LU$ decomposition if we know $A,L,U$?

Assume that we have this equation $$PA=LU$$ Where $A \in \Re^{mxn}$, $L \in \Re^{mxn}$ is a lower triangular matrix and $U \in \Re^{nxn}$ is an upper triangular matrix. $P \in \Re^{mxm}$ is the ...
-1
votes
3answers
52 views

Proof properties of vector norm

How can I proof that for all vector norm on $ \mathbb{R} $ that $\left | \left \| x \right \|-\left \| y \right \| \right |\leq \left \| x-y \right \|$
1
vote
1answer
39 views

Approximate $f''(x)$ given $f(x),f(x+h),f(x+3h),f(x-5h)$

Given $f(x),f(x+h),f(x+3h),f(x-5h)$, approximate $f''(x)$. Book's solution: From Taylor' series, $$ \\ f(x+h)=f(x)+f'(x)h+0.5f''(x)h^2+{1\over6}f'''(x)h^3+O(h^4) \\ f(x+3h)=f(x)+3f'(x)h+4.5f''(x)h^2+...
3
votes
1answer
170 views

Linear Least-Squares Problem with Inequality Constraints on Residual

I have an over-determined linear least-squares problem $$\min_{\vec{x}}\Vert\mathbf{A}\vec{x}-\vec{b}\Vert_2^2,$$ where $\mathbf{A}\in\mathbb{R}^{n\times m}$, $\vec{x}\in\mathbb{R}^m$, $\vec{b}\in\...
0
votes
1answer
37 views

Proving that product of general matrices has small spectral radius

In a Jacobi type of iteration for finding solution to a linear system $Ax=b$, one writes $$x_i^{(k+1)} = Gx_i^{(k)}+c,$$ where $x_i$ is the $i$-th component of vector $x$ and $G=D^{-1}N$, $c = D^{-1}...
1
vote
1answer
104 views

Discretization matrix for 3D Poisson equation

It is known that the 2D Poisson equation defined on a domain $\Omega$ (let's say $\Omega := (0,1)^2$) with Dirichlet boundary conditions $u(x,y)_{|\partial \Omega}=g(x,y)$, $$u_{xx} + u_{yy}=f$$ can ...
1
vote
1answer
55 views

Coupled differential equations into system of first-order equations implicitly

I am looking to solve the following equations numerically: $a x=\frac{d}{dt}\left(f(x,y,t)\frac{dy}{dt}\right),\quad b y=\frac{d}{dt}\left(g(x,y,t)\frac{dx}{dt}\right)$ For arbitrary functions $f$ ...
1
vote
1answer
46 views

What's the reason to use Singular Value Decomposition instead io $(A^TA)^{-1}A^T$ for pseudo inverse?

I wonder what's the reason to use this formula from Singular Value Decomposition $$ A = U\Sigma V $$ $$ A^{\dagger} = V\Sigma^{-1}U^T $$ Instead of $$ A^{\dagger} = (A^TA)^{-1}A^T $$ Both give ...
0
votes
0answers
48 views

What is the relationship between $||.||_{max}$ and energy of a matrix?

I was interested to find a relationship between $||.||_{max}$, i.e. max-norm of a matrix with that of its energy. $||.||_{max}$ of a matrix is defined by the maximum entry in the matrix. Generally, ...
0
votes
1answer
23 views

Perturbation bound on approximate linear system

Suppose that $A, \hat A$ are invertible real matrices such that $Ax = y$ and $\hat A\hat x = \hat y$, where $\|A - \hat A\| \leq \epsilon_1$ and $\|\hat y - y\| \leq \epsilon_2 \|y\|$. I'm trying to ...
0
votes
1answer
32 views

Ill-conditioned matrices and their singular values

For ill-conditioned matrices, must it be that the smallest singular value is arbitrarily close to $0$? I know that $K_2(A) = \frac{\sigma_{max}}{\sigma_{min}}$ where $\sigma$ is a singular value of A. ...
0
votes
1answer
37 views

Solving a Linear System using Cholesky method Confusion

Hello I am trying to solve the following system using the cholesky method in Matlab ...
1
vote
0answers
40 views

Discrete Poisson Equation , how to include non-zero boundary conditions

I have question about the discretization of the poisson equation $$\triangle u =f$$ on a two-dimensional grid as described in https://en.wikipedia.org/wiki/Discrete_Poisson_equation. In this example, ...
0
votes
1answer
42 views

$ \sum_{i = 1}^{m}\lambda_i v_i v_i^T$ for $v_1,v_2, \ldots,v_m \in \mathbb{R}^n$ linearly independent has rank $m$ $(\lambda_i \neq 0)$

I often see this formula used in the rank 1 or rank 2 cases for Quasi-Newton methods, but I am wondering how this can be proven in the general rank $m$ case. As a linear algebra problem, I would like ...
0
votes
1answer
56 views

The inverse of a submatrix of an inverse matrix; how to numerically approach this?

Suppose that $A$ is a positive-definite symmetric matrix. I want to solve $$\widetilde{(A^{-1})_k}x = b$$ where $\widetilde{(B)}_k$ is the matrix $B$ but with the $k^{th}$ row and $k^{th}$ column ...
1
vote
0answers
55 views

circulant matrix inversion using fast fourier transform

I am Huda. May I know, if I have a circulant matrix, can I calculate its inversion using fast fourier transform? If yes, I really need an explanation. Thank you.
0
votes
1answer
32 views

Real and Complex part of Hermitian and positive definite forming another Symmetric positive definite

Suppose that H = A + iB is Hermitian and positive definite with A and B being Real n by n matrices. This means that $x^HHx > 0$ whenever $x\neq0$. (a) Show that C = $\left(\begin{array}{cc} A &...
0
votes
1answer
52 views

Machine learning: What method should I use for classification?

I post this on Math Stack Exchange instead of Data Science Stack Exchange because I want to have the theory, not Pyton import. Assume that we have a vector who contains decimal values, sorted. $$V =...
0
votes
1answer
31 views

LU decomposition of banded matrix without pivot

Say I have a Matrix $M$ that is a banded matrix where an LU decomposition exists (so without pivot). Are the $L$ and $U$ of the $LU$ decomposition also banded? Is the band the same (ignoring the upper/...
0
votes
0answers
27 views

Computing a matrix modulo a group?

Say I have a matrix A that is a representation of an element of the product of groups $G_b$ and $G_c$, and would like to find $B$ from group $G_b$ and $C$ from group $G_c$ so that $A = BC$. In my ...
-1
votes
1answer
19 views

Multiplicity of eigenvalues of preconditioned matrix

I have a symmetric positive definite (SPD) matrix $A\in\mathbb{R}^{n\times n}$ and a full-rank matrix $B\in\mathbb{R}^{m\times n}$. I know that the pre-conditioned matrix $\begin{bmatrix} A ...
1
vote
1answer
44 views

How can I find the pivot matrix from LU-factorization?

I trying to solve LU-factrization with pivoting: $$PA=LU$$ By using the subroutine sgeft2 from Lapack. It's a Fortran 90 library for numerical linear algebra. I have found the $L$ and $U$ matrix, ...
0
votes
2answers
91 views

How to solve $Q$ matrix from Householder QR-factorization? - Lapack

I'm using the subroutine sgeqr2 from Lapack. This subroutine solves the QR-factorization $$A = QR$$ It's easy to find the $R$ matrix, because the in-out argument $A$ of subroutine sgeqr2 will return ...
0
votes
0answers
38 views

How to numerically solve for system of implicit algebraic equations?

I have a system of ODE's with a steady state solution $x^* \in \mathbb{R}^N$ given by the following $N$ implicit equations: $$x^*_i = \frac{ \sum_{j=1}^N c_{ij} x^*_j}{a_i + \sum_{j=1}^N c_{ij} x^*_j}...
0
votes
1answer
31 views

Results about unitary matrices?

If $U$ is the unitary matrix of order (n by n) matrix, then we have $U^{*}U=UU^{*}=I_{n}$. Can we write this relation $U^{T}\overline { U }=\overline { U }U ^ { T }=I_{n}$, where $T$ denotes transpose ...
2
votes
0answers
44 views

Algorithm to find eigenvector given eigenvalues

This may sound like a strange question, but I've actually been having some difficulty finding a general algorithm to create eigenvectors from a given eigenvalue + the associated matrix A. Trying to ...
0
votes
0answers
21 views

Iterative method for a system of linear equations

I need to solve this problem: Let $A\in \mathcal M_n(\mathbb R)$ a positive definite matrix, $B \in \mathbb R^n $, and $AX=B$ a system of linear equations. We use an iterative method which ...
-3
votes
1answer
39 views

Rank of a matrix constructed using the codewords of a linear block code.

Suppose that $[n, k,d]_2$ represents a linear block code. Then we have $2^k$ different codewords. Suppose that $c_1, c_2,....,c_{2^k}$ represents different code vectors. Define a matrix $A$ as, $$A=[...
0
votes
0answers
66 views

Behavior of 2-norm of k-th power of matrix

I got this problem from Greenbaum's book of iterative methods. In page 14 he mentions that the 2-norm of matrix $A^k$ is asymptotically behaves like $v \left( \begin{array} { c } { k } \\ { j - 1 } \...
0
votes
2answers
29 views

Well-conditioned problem and a stable algorithm?

I am trying to figure out the difference between Well-conditioned problem and a Stable algorithm: A well-conditioned problem is one in which rounding errors play very little role. A stable algorithm ...
1
vote
0answers
52 views

preconditioned matrix with golden ratio, golden ratio conjugate, and 1 as eigenvalues

I have a symmetric positive definite (SPD) matrix $A\in\mathbb{R}^{n\times n}$ and a full-rank matrix $B\in\mathbb{R}^{m\times n}$. I need to show that the pre-conditioned matrix $\begin{bmatrix} ...
0
votes
0answers
47 views

Schur complement condition number

How can I most simply show, without referring to advanced theorems, that the Schur complement is better-conditioned than the original SPD matrix itself?
2
votes
1answer
87 views

Why is the norm $1$ of matrix $A$ is equal to the maximum sum of column

first, I know that there exists a similar question to mine which is in here, and it is actually very well explained. However, there is just one part that I do not understand. That is the conclusion. ...
0
votes
2answers
82 views

LU decomposition implies Gaussian Elimination without pivoting

If Gaussian elimination can be carried out without pivoting for A, then A has an LU decomposition. Is the converse true: if A has an LU decomposition, then Gaussian elimination can be carried out (in ...
0
votes
0answers
43 views

What is the easiest way to solve SVD numerically?

I want to solve Singular Valude Decomposition(SVD) $$A = USV^T$$ I have been using the QR-method before, but it takes lot of time and is very slow. Is there any easier method to use? Is it easy to ...
5
votes
1answer
48 views

Showing $\min\limits_{j=1,\dots,n}|\lambda-\lambda_j|\le ||C||_p||C^{-1}||_p||B||_p$

Let $A$ be a diagonalizable $n\times n$ matrix with eigenvalues $\lambda_1,\dots, \lambda_n$, $B$ an $n\times n$ matrix, and $\lambda$ an eigenvalue of $A+B$. Show that $$\min\limits_{j=1,\dots,n}|\...
-1
votes
1answer
37 views

Solving a matrix least squares problem with a fixed Frobenius norm constraint

I am trying to solve for X an equation of the form : Min ||AXB-CXD|| s.t. ||X||_F=1, where , A, C are m-by-m matrices, and B, D are n-by-b matrices. Is there any effective algorithms? Any hint is ...
1
vote
1answer
187 views

Underflow while evaluating softmax, despite using exp-normalize

I have a very simple linear classifier that uses softmax (with exp-normalize trick) for the output: ...
2
votes
1answer
24 views

Transpositions wrt the energy and usual norm

Let $^\dagger$ denote transposition w.r.t. the usual norm $(\cdot,\cdot)$ and $^*$ denote transposition w.r.t. the energy norm $(\cdot,\cdot)_A$ defined for symmetric $A$: $(u,v)_A=(Au,v)=(u,Av)$. ...
6
votes
1answer
369 views

Upper bound CP tensor rank

I have a question about CP tensor ranks. In the following, $\mathcal X \in \mathbb R^{n_1 \times n_2 \times n_3}$ is a third-order tensor of CP rank $R$, i.e., there exist vectors $a_i$, $b_i$ and $...
0
votes
0answers
38 views

why the name “relaxation” in the SOR Gauss-Seidel iterative method?

The question is that simple. It is in the subject. Why the name "relaxation" in the SOR Gauss-Seidel iterative method? I have googled for it without luck. Moreover, when $\omega$ is used in Gauss-...
0
votes
0answers
23 views

How to transform a square orthogonal matrix into a norm-preserving non-square matrix?

Assume we have an arbitrary $n \times n$ orthogonal matrix of real values. How can you transfer such a matrix into an $m \times n$ non-square matrix (where $m < n$) which also preserves the norm of ...
0
votes
0answers
27 views

Are there algorithms for solving a sequence of sparse linear systems of the form $(x_iI+B)y_i = b$?

I am struggling to solve a sequence of linear systems of the form $$(x_i I + B ) y_i = b, \quad i = 1,2,\dotsc,$$ where $I$ is identity, $x_i$ is a real number and $B$ is sparse. Both the matrix $B$...