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

learn more… | top users | synonyms

1
vote
1answer
29 views

Gauss Seidel Iteration for a specific matrix

We seek to solve $Au= f$ via iteration, where $$ A = \left ( \begin{array}{cc} I & S \\ -S^T & I \end{array} \right ) $$ Where $S$ is an arbitrary square matrix in $R^n$ and $I$ is the ...
4
votes
1answer
67 views

LU decomposition for cyclic tridiagonal matrices

It is known that a tridiagonal matrix $$ A = \begin{pmatrix} b_1 & c_1 & 0 & 0 & \dots & 0\\ a_2 & b_2 & c_2 & 0 & \dots & 0\\ 0 & a_3 & b_3 & c_3 &...
1
vote
0answers
42 views

How can I write $\prod\limits_{i = 0}^n {\left( {x - {x_i}} \right)} $ in terms of a polynomial as $\sum\limits_{i = 1}^n {{a_i}{x^n}} $?

How can I write $\prod\limits_{i = 0}^n {\left( {x - {x_i}} \right)} $ in terms of a polynomial as $\sum\limits_{i = 1}^n {{a_i}{x^n}} $? In the other words, is there a way to write $a_i$ in terms of $...
0
votes
0answers
82 views

Most stable algorithm to solve a system of linear equations?

I am doing some image processing involving solving a system of linear equations. I am getting some errors and bits of the image looks corrupted. I would like to know what is the most stable way to ...
1
vote
1answer
50 views

Strange behavior with coordinate transformation of square and quadrilateral

I am trying to map coordinates from a quadrilateral to a square. The coordinates are square: $(500,900)(599,900)(599,999)(500,999)$ quad: $(454,945)(558,951)(598,999)(499,999)$ where the $i^{th}$ ...
0
votes
1answer
32 views

Notation regarding linearization near equilibrium point of dynamical system

Suppose we have $\frac{dx}{dt} = \dot{x} = f(x)$ with equilibrium point $x_e$ such that $f(x_e) = 0$. Then for the linearized approximation of the differential equation near $x_e$ we hope to use the ...
1
vote
1answer
63 views

How to determine positive or negative definite of a bordered Hessian ?

I want to determine the minimization result I get using Lagrange Multiplier method is a local minimum by determining whether the Bordered Hessian is positive definite or negative definite.(Hopefully ...
0
votes
1answer
56 views

Bound on the difference of matrix diagonals

I have two diagonal matrices $\Lambda,\hat{\Lambda}\in\mathbb{R}^{n\times n}$ with non-negative diagonal elements. And I have two matrices $W,\hat{W}\in\mathbb{R}^{m\times n}$, with $m\geq n$, each ...
0
votes
0answers
26 views

What is the source of the error in the Sherman-Morrison formula application?

The Sherman-Morrison formula results in small errors in relation to the standard matrix inverse operation after each application, as shown here. From what I understand, the Sherman-Morrison identity ...
3
votes
2answers
150 views

Computing $\operatorname{Tr} \bigl( \bigl( (A+I )^{-1} \bigr)^2\bigr)$

Suppose that $A \in \mathbb{R}^{n \times n}$ is a symmetric positive semi-definite matrix such that $\operatorname{Tr}(A)\le n$. I want a lower bound on the following quantity $$\operatorname{Tr} \...
0
votes
1answer
257 views

Product rule in discrete derivative in finite difference scheme.

Suppose we are on real line and I want to discretize the usual derivative operator. Take a smooth function $u$ and step size $h$. Then I could define $$ \Delta_+u(i) = \frac{u(i+1)-u(i)}{h} $$ as the ...
1
vote
2answers
55 views

Linear combination of basis function in logarithm space. Is it possible?

I have a function $f(x)$. As theory said that it can represent by linear combination of basis functions such as $$f(x)=\sum_{i=1}^{N}\alpha_ig_i(x)$$ where $\alpha$ is coefficient and $g(.)$ is basis ...
1
vote
0answers
26 views

Conditional expectation of a set of Gaussian variables

I was wondering if there is an efficient way to compute the conditional expectation of every element in a Gaussian random vector ? Specifically: For a pair of Gaussian random variables $[x,y]$, the ...
0
votes
1answer
34 views

Gauß-Newton Example with one variable

$$T=f(t):=2 \alpha + \sqrt{\alpha^2+t^2}$$ To estimate $\alpha$ we got the measured values $T_i$ for $t_i$. Formulate the curve fitting problem and show each step in the Gauss-Newton algorithm. My ...
3
votes
3answers
91 views

Is this a circulant matrix?

It's symmetric, but I'm not sure whether it is circulant. In a question that I had asked on MSE a couple of weeks ago, several commenters had said that this is a circulant matrix, and to study the ...
2
votes
1answer
62 views

Choose $\rho$ such that $\rho$-norm minimizes the matrix condition number

I'm solving questions from am exam that I failed miserably, so I would love it if someone can take a look at my proof and make sure I'm not making any gross mistakes. Question Let $A$ a symmetric ...
0
votes
1answer
87 views

Automatic way to have a good initial guess for the iterative methods ( newton method) and for high dimensional nonlinear problems

I am solving a variety class of nonlinear systems where I need to reduce in optimal manner the number of iterations of either the newton or modified newton method. For this end I am trying to figure ...
1
vote
1answer
306 views

How to numerically solve the Poisson equation given Neumann boundary conditions?

I want to solve the Poisson equation on a 2D domain given Neumann-type boundary conditions: The PDE: \begin{equation} \nabla^2 \; u(r,\theta) \;=\; f(r,\theta) \end{equation} The boundary conditions:...
9
votes
0answers
123 views

How to solve linear system of form $(A \otimes B + C^{T}C)x = b$ when $A \otimes B$ is too large to compute?

For the given linear system: $$(A \otimes B + C^{T}C)x = b$$ where $\otimes$ is the Kronecker product, $A$ and $B$ are dense and symmetric positive-definite, and $C^{T}C$ is a sparse symmetric block ...
0
votes
1answer
64 views

Can adding one column to a matrix increase its rank by more than one

Knowing the answer to this question would help me answer the following question: $A$ is an $m\times n$ matrix with $m>n$, and let $A=\hat{Q}\hat{R}$ be a reduced QR factorization. Suppose $\hat{R}$...
0
votes
2answers
46 views

Rewrite matrix equation as a quadratic programming problem

Given real-matrix $X_{n\times p}$ how can the problem of minimizing $Tr(X^TA_{n\times n}X)$ under the constraint $Tr(X^TC)=\phi$ be posed as a standard convex quadratic program given by the form: ...
2
votes
0answers
82 views

Fastest way to find linearly independent columns of a matrix

Given a rectangular matrix $X$ of size $n\times m$ with $m>n$, what is the fastest way to find the linearly independent coloums. Robust methods like SVD or RRQR decompostion have complexity of ...
0
votes
0answers
36 views

Evaluating a quadratic form with an inverse of a sparse PD matrix, comparison between using the inverse vs using a Cholseky decomposition

I have the following quadratic form I need to evaluate: $x^T A^{-1} y$, where $A$ is a sparse positive definite matrix, $x, y$ are sparse vectors. Now assume that I am given for free both $A^{-1}$ ...
2
votes
2answers
91 views

Differential equation for finding closest point on surface.

Inspired by this question I got to think about a more general case. Say I have any discretized surface and want to find closest point from each point outside of surface to the surface. Say that I can ...
1
vote
0answers
39 views

How to apply Runge-Kutta to an implicit scheme?

I see there are some differences in the solution as I increase the resolution of my grid. I'm using Operator Splitting to solve Diffusion Reaction equation \begin{equation} \frac{\partial u}{\...
4
votes
3answers
132 views

Symmetry Of Differentiation Matrix

I have a problem computing numerically the eigenvalues of Laplace-Beltrami operator. I use meshfree Radial Basis Functions (RBF) approach to construct differentiation matrix $D$. Testing my code on ...
1
vote
0answers
21 views

Relationship between QR and LU factorization

Both algorithm return very similar results in terms of having a upper/right triangular matrix as one of the factors. What is the relationship between Q and L, and between R and U? What is the ...
0
votes
1answer
99 views

The MU-puzzle from GEB

The MUI system only uses the three letters M,U,and I to make strings. The system has four rules that allow you to make new strings out of existing strings by manipulating them. Rules 1 and 2 lengthen ...
1
vote
2answers
40 views

How to solve the system of equations $\{10^{-4}x_1+x_2=1, x_1+x_2=2\}$ using finite precision arithmetic with three significant figures?

Consider the following two equations: $10^{-4}x_1+x_2=1$ $x_1+x_2=2$ Solve using Gaussian Elimination using finite precision arithmetic with three significant figures. I'm a little stuck ...
1
vote
1answer
71 views

Error bound of midpoint rules with unbounded second derivative

It is well known that error bound of midpoint rule for function $f[a,b]$ is given by $$ E\leq K\frac{(b-a)^3}{24 n^2} $$ where $|f(x)''\leq K|$ and $n$ is the number of time steps. if second ...
0
votes
0answers
93 views

Proof that Householder Triangularization for QR is backward stable

How do you prove that QR factorization via Householder Triangularization is backward stable? Theorem 16.1 (From Trefethen and Bau): Let the $QR$ factorization of a matrix $A$ be computed by ...
1
vote
0answers
26 views

How can I solve this specific set of equations?

Here are the equations: $$\sum_{k = 1}^n i_k + Y_n u_n = J \quad \quad (1)$$ $$i_1 + Y(u_1 - u_2) = J \quad \quad (2)$$ $$i_k - Y(u_{k - 1} -2u_{k} + u_{k + 1}) = 0, \quad \quad k = 2, ..., n - 2 \...
1
vote
0answers
26 views

Linear algebra <perhaps an application of Gordan' Theorem>

Question. Let $a_1,...a_n\in\{0,1,-1\}^m$ and $\sum a_i=(1,...,1)$. Is there a permutation $\tau$ of $\{1,...,n\}$ Such that for each $k\in \{1,...,n\}$ the vector $\sum_{i=1}^k a_{\tau (i)}$ has ...
1
vote
0answers
139 views

Numerically stable SVD

In this question regarding SVD, it is explained why eigen decomposition of $ A^tA $ is not numerically stable compared to "direct SVD algorithms". Since the former is the algorithm I'm most familiar ...
2
votes
0answers
33 views

Reference request for finite difference method

I am trying to use finite difference method to solve the minimizing problem $$ J[u]=\min_{u\in BV(Q)}\{\|u-f\|_{L^1(Q)}+|u|_{BV(Q)}\} $$ where $Q=(0,1)\times (0,1)$ is a uint square and $|\cdot|_{BV}...
1
vote
1answer
43 views

What happens if the power method is applied with a starting vector $q=c_2 v_2+…+c_n v_n$ in the presence of roundoff errors?

Supose $\{v_1,...,v_n\}$ is an eigenvector basis and $|\lambda_1|>|\lambda_2|>\ldots >|\lambda_n|>0$, so, my question is, if our starting vector $q \in span\{v_2,\ldots,v_n\}$ and in the ...
1
vote
1answer
72 views

What are some Applications of Hermitian Positive Definite matrices?

I am learning about Hermitian positive definite matrices and the way that they can be decomposed with Cholesky decomposition. I have learned that these matrices deserve special attention for how often ...
0
votes
1answer
83 views

Iterative method to compute only the positive eigenvalue's and corresponding eignevectors of a very large matrix?

I have a very large dense matrix (~10000 X ~10000) which is not full rank . I want to compute only the positive eigenvalues and corresponding eigenvectors instead of computing all of them. I have ...
0
votes
1answer
37 views

How to link the eigenvalues to the components from PCA

I have a difference matrix from daily changes which I use to construct a covariance matrix. On this covariance matrix I use the power method to get the eigenvalues. The power method yields exactly the ...
1
vote
0answers
46 views

Numerically finding eigenvalues of a Volterra operator of first kind

I'm looking for a solution to the following problem - $\int_{-\infty}^{\infty} K(x-y) f(y) = \lambda f(x)$ Consider $K(x-y) = \left\{ \begin{array}{lr} e^{-(x-y)} & : x > y \\ 0 & : x &...
1
vote
0answers
58 views

Ideas for expressing the inverse of matrix quadratic form $CAC^T$

I want to find an expression for the inverse of the matrix system $Z=CAC^T$, where $A \in \mathbb{C}^{n \times n}$ is block diagonal with dense blocks, and $C \in \{-1,0,1\}$ with dimension $m \times ...
2
votes
1answer
46 views

Solving a system of polynomials in $N$ variables

Suppose I am given some non-negative constants $(C_p)_{p=1, ..., l}$ and I would like to find an integer $N$ and vector $v \in R^N$ such that $$ \sum_{i=1}^N (v_i)^p = C_p $$ for $p=1, ..., l$. Can ...
1
vote
0answers
143 views

Eigenvalues after Givens-Rotation

Im just validating my own Code of a Givens-Rotation in Matlab. Therefore i let matlab compute the Eigenvalues after each Givens-Rotation. I am wondering why the Eigenvalues computed by matlab are ...
1
vote
2answers
263 views

Solving a matrix equation using numerical optimization

To my knowledge, if $A \in \mathbf{S}^n_{++}$, then given any $b \in \mathbb{R}^n$, the system of linear equations $Ax = b$ has a unique solution $x^* \in \mathbb{R}^n$. Moreover, the solution $x^* \...
1
vote
0answers
61 views

Simplifying the Generalized Eigenvalue Problem

Let $\Sigma_1$, $\Sigma_2$ be symmetric positive-definite real $n\times n$ matrices. We want to solve the generalized eigenvalue problem $$ \Sigma_1V=\Lambda\Sigma_2V, $$ where $\Lambda$ is the ...
0
votes
1answer
50 views

Use the Forward Difference method to approximate the solution to the following PDE?

Use the Forward Difference method to approximate the solution to the following PDE: $$ u^3\frac{\partial u}{\partial t}-x^2u\frac{\partial^2u}{\partial x^2}=2x^8t^7+6x^6t^5+4x^4t^3 $$ for $0\le x\...
2
votes
4answers
135 views

Inverse Chebyshev Recurrence

The Chebyshev polynomials (of the first kind) are a sequence of polynomials defined recursively by $$ \begin{cases} T_{0}(x) = 1 \\ T_{1}(x) = x \\ T_{n}(x) = 2xT_{n-1}(x) - T_{n-2}(x) \end{cases} $$ ...
1
vote
0answers
77 views

complex rank-one update

I'm trying to find the eigendecomposition of a rank-one update to a complex matrix $D + uv^T$. The matrix $D$ is diagonal, but not the identity. It has unique imaginary entries along the diagonal. $uv^...
1
vote
0answers
57 views

Determining Nullspace Basis such that only one column is deleted or added as row is added or deleted, and remaining columns of basis stay the same

I would like to compute, in MATLAB, the basis Z for the nullspace of an m by n matrix A, such that if one row of A is added (resulting in A_a), the basis for A_a is n-m-1 of the n-m columns of Z, i.e.,...
5
votes
1answer
30 views

Proving a property about Gauss-Seidel

This is a homework problem, so please give hints or tips instead of full answers. The problem is as follows: Let $G$ be the iteration matrix of the Gauss-Seidel method; i.e. $$G=I-(D-L)^{-1} A$$...