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

learn more… | top users | synonyms

2
votes
2answers
56 views

Determinant of an ill conditioned matrix

I have the following ill conditioned matrix. I want to find its determinant. How is it possible to calculate it without much error \begin{equation} \left[\begin{array}{cccccc} ...
0
votes
0answers
15 views

Finite difference method for elliptic pde stability condition

I am trying to implement a finite difference scheme for the elliptic pde $\nabla(a(x_1,x_2)\nabla\phi(x_1,x_2))=0$ where $(x_1,x_2) \in (0,l_1)\times(0,l_2)$ with $l_1 \neq l_2$ necessarily. I know ...
2
votes
1answer
43 views

Positive definite martix

I understand the majority of this solution, it's just I don't understand why I have to use both $\epsilon_1 $ and $\epsilon_2 $ rather than just $\epsilon$. I understand that i'm working with ...
0
votes
2answers
33 views

Least Squares Solution Confusion

Say if I have an overdetermined system $A\vec x=\vec b$, I can use the normal equations $\implies$ $A^TA\vec x=A^T\vec b$. If I solve for $\vec x$ I will get a "solution" with an error. It says in ...
2
votes
1answer
29 views

QR transformation with Householder transformation

It's a task i do to understand minimizing the error including the QR transformation with the help of Householder transformation. I think i really do something wrong but i dont get it running i hope ...
1
vote
0answers
31 views

Numerical rounding errors in intersection code

I hope this question is in the right place, as it is as much about programming as it is about math. I'm trying to find the intersection between a circle and a line. My implementation of the algorithm ...
0
votes
0answers
33 views

Efficient Factorization for Family of Matrix Equations

I am looking for an efficient solution to the following problem $$ A+\lambda I = b \tag{1} $$ where $A\in\mathbf{S}^{n}$ is a symmetric matrix with nonzero eigenvalues, $b\in\mathbf{R}^n$ is fixed, ...
4
votes
1answer
2k views

Linear least squares with inequality constraints

I'm trying to follow this older paper, page 19. The goal is to solve: $\min \|Ax-b\|^2 s.t. Gx \ge h$ given $A, G, b, h$ By combining the equations into a single LCP of the form: $Mz + q = w$ s.t. ...
3
votes
1answer
66 views

I want to study Numerical linear algebra [closed]

Would you like to recommend a book to me? the proof is explicit and easy to understand is preferred.
1
vote
0answers
22 views

Gaussian elimination vs. Jacobi iteration

How can I determine which of the matrix solver is faster for a given set of equations: Gaussian elimination or Jacobi iteration? In case, I have a banded matrix, is it advisable to use LU ...
0
votes
1answer
33 views

Simplying linear equation to get quartic in q using Maple and then using Descarte’s rule of sign

Using the maple I am trying to get quardic in q from this big linear equation. Then use Descarte’s rule of signs to determine the number of positive roots. \begin{equation} ...
1
vote
0answers
25 views

When is the LU decomposition unique?

I want to find out when a matrix decomposition $A = LU $ (L lower and U upper matrix) is unique? Clearly, if $A$ is not invertible, there is no chance that this decomposition is unique. Hence, ...
0
votes
1answer
27 views

Solve for a matrix in a linear equation

This is probably a really basic question, but we are stuck and the usual keyword lead to the normal "Solving linear equations with matrices"/Gaussian-elimination pages ... I have an equation $A X B + ...
1
vote
1answer
340 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 ...
0
votes
0answers
33 views

System of linrar equations and condition number

The relative error of the solution of a system of linear equation $Ax=b$, for any natural norm $\|\cdot\|$ is bounded by $$ \frac{1}{\| A\| \|A^{-1} \|} \frac{\|r\|}{\|b\|} \le \frac{\|e\|}{\|x\|} \le ...
2
votes
2answers
244 views

Methods to solve a system of many Ax=B equations using least-squares

I am working with a force measurement instrument which needs calibration via a calibration matrix. For each of a set of controlled measurements I have a vector $k$ of three known, independent values, ...
0
votes
0answers
28 views

condition number of orthogonal matrix

Let $A\in M_n(\mathbb R)$ be an orthogonal matrix. Then: $cond (A) =1$. I tryed to use facts about the eigenvalues but is did not help. In 2-norm it is easy to prove it since $||A||_2 = \sqrt{\rho ...
0
votes
0answers
10 views

Spectral norm of a Hadamard product

Let $F$ be the $n\times n$ DFT matrix, i.e., $F_{i,j} = \exp\left(-\tfrac{2\pi(i-1)(j-1)}{n}\imath\right)$, for $1\le i,j\le n$ and $\imath =\sqrt{-1}$. Futhermore, let $\Vert \cdot\Vert$ and $\circ$ ...
1
vote
1answer
25 views

linear systems&normalize

suppose $f: \mathbb{R}^n \rightarrow \mathbb{R}^n$ be a linear function which can be represented by a $n \times n$ matrix. Then the jacobian of $f$ is the same as the function for $f$. But I now want ...
0
votes
2answers
20 views

Finding a rotation matrix

I am looking for a rotation matrix such that $$ \operatorname{rot} \cdot \begin{pmatrix} -1 & 0 & 0 \\ 1 & -1 & 0 \\ 0 & 1 & -1 \\ 0 & 0 & 1 \end{pmatrix} = ...
1
vote
1answer
20 views

Efficient Algorithm for Iteratively Reweighted Least Squares Problem

I'm interested in solving a weighted least squares problem of the form $X^T W X \beta = X^T W Y$ where $W$ is a diagonal, positive definite matrix, $X \in R^{m \times n}$, $Y \in R^{m \times 1}$ and ...
3
votes
2answers
50 views

Power iteration

If $A$ is a matrix you can calculate its largest eigenvalue $\lambda_1$. What are the exact conditions under which the power iteration converges? Power iteration Especially, I often see that we ...
1
vote
1answer
26 views

Lipschitz continuity for generalized inverse matrix

Suppose $A$ and $B$ are full-rank and well-conditioned. Is Lipschitz continuity held for generalized inverse? $$\|A^+ - B^+\| \le \omega \|A-B\|,$$ for some $\omega > 0$, where the norm could ...
0
votes
1answer
225 views

approximating diagonal of inverse sum of low rank and diagonal matrices

I was wondering if there is any theorem or algorithm to approximate the diagonal elements of the inverse of sum of low rank symmetric positive semi-definite and non-negative diagonal matrix. Let me ...
0
votes
1answer
14 views

LD$t(L)$ factorization and eigenvalues

A positive definite matrix $A$ can be factored in to $LDt(L)$form. Is the statement the eigenvalues of $A$ are the diagonals of $D$ true? If so , how to prove it?
2
votes
1answer
65 views

Linear equation: $(A^\top A+B^\top B + D)x=c$ where $A,B$ are structured sparse and $D$ is diagonal.

Updated: the goal is to solve $(A^\top A+B^\top B + D)x=c$. Maybe it is not necessary to compute $(A^\top A+B^\top B + D)^{-1}$. Denote $e=(1,1,\ldots,1)^\top\in\mathbb{R}^n$ and ...
3
votes
0answers
47 views

Does anyone know any reference for this matrix?

For $n \geq 4$, $A$ is $(n-1) \times (n-1)$ tridiagonal block matrix $$A = n^2 \begin{bmatrix}B & -I & 0 & \cdots & \\-I & B & -I & 0 & \\ 0 & -I & B & -I ...
2
votes
1answer
28 views

Can an iterative method converge for some initial approximation?

Studying iterative methods for solving(or approximating) linear equation systems, I came accross the following theorem$^1$: Let the following be an iterative method: $$x^{(0)},\qquad known\\ ...
2
votes
2answers
39 views

Solving $a_1x_1 + \cdots +a_nx_n = b$

I'm glad to ask my first question on the maths site! So here we go. I'm trying to set up prices right now and here is my problem : I know that my customer has a certain amount of money available. ...
3
votes
1answer
210 views

How to Store a Banded Matrix by Diagonal

I'm taking a graduate level independent study course this semester in Matrix Computations. I'm not getting much support from the professor, so am turning to the excellent StackExchange community for ...
1
vote
1answer
453 views

Reducing a matrix to upper Hessenberg form using Householder transformations in Matlab

I have the below Matlab code based on what my professor gave me in class. The last line of this code is giving me an incompatible dimensions error. When I checked the size, I got that the matrix ...
1
vote
1answer
39 views

Consistency of the system $AX=b$

In the concept of consistency (compatibility) of a matrix, when $b \in \mathbb R (A)$ we know for sure that the system is consistent or there may exists no solution for it? But when $b \notin \mathbb ...
1
vote
1answer
41 views

Inverse of constant matrix plus diagonal matrix

Is there an efficient way to calculate the inverse of an NxN diagonal matrix plus a constant term? I am looking at N of around 40000. $\left[\begin{array}{cccc} a & b & \cdots & b\\ b ...
0
votes
2answers
25 views

Formatting Linear equation

How do I craft a linear equation so that it is in the form of $ax + bx + c = 0$ where $a^2 + b^2 = 1$ if I have two points? I know how to get it into the form $ax + bx + c = 0$ but I can't figure out ...
1
vote
0answers
18 views

Check feasibility of a system of integer linear equations

I'm currently working on a very large integer linear programme which cannot be solved within any reasonable time. The initial set of linear equations S={Ax<=b) is feasible. I want to add more ...
2
votes
0answers
36 views

Effective computation of matrix commutator

Is there a faster way to compute the commutator of large (at least one of them sparse) matrices $[A,B]$ then to compute $AB$ ,$BA$ and subtract them?
1
vote
0answers
28 views

Influence of preconditioning on degenerate eigenvectors

I'm using a hierarchical decomposition of a sparse matrix $A$ as suggested here. I find that the method essentially finds eigenvectors using the QR algorithm. $A$ has some eigenvalues with ...
1
vote
0answers
56 views

Newton's method for multidimensional functions

Can Newton's method be used to find the root of a function f : $\mathbb{R}^n\to\mathbb{R}^m$. Can anyone provide a proof for this? (I have checked the method of solving system of equations with ...
1
vote
1answer
50 views

Efficient method for determining to the most positive eigenvalue of a matrix

I am trying to implement an algorithm that requires knowing the largest $\textbf{positive}$ eigenvalue of a $\textbf{real symmetric, non-sparse}$ matrix and the corresponding eigenvector. The actual ...
0
votes
0answers
26 views

What is the largest (dense, real, symmetric) random matrix I can diagonalize on a computer?

I have read that 10.000x10.000 is no problem for LAPACK or similar routines. I would like to know if N=20.000 or 40.000 is possible. EDIT: I don't know if it is relevant, but the matrix is positive ...
0
votes
0answers
19 views

Strange Convergence of SOR/Gauss-Seidel

I am having trouble with the convergence of my Gauss-Seidel/SOR method. The matrix $A$ in $Ax=y$ seems to be positive-(semi)definite. Its eigenvalues are: However, the method (SOR) improves the cost ...
0
votes
0answers
23 views

Understanding a preconditioner (Jacobi)

I am having problems to get the point of a Jacobi-Preconditioner. As the Jaco iterative method state, given a system like $Ax=b$, its solution may be obtained by $$x_i^k=\frac{b_i}{a_{ii}}- \sum_{j=1, ...
2
votes
1answer
194 views

equations solved with Newton's method by finding the zeros of functions?

I found this statement in one paper I read recently: This problem can be solved by finding the zero of functions: ...
1
vote
1answer
24 views

How to recover Q from the (tiled) QR decomposition using householder factorisation?

I'm trying to implement the tiled QR decomposition in MATLAB (in an attempt to understand it), and I'm trying to check that my SGEQRF (upper corner tiles) function is working correctly. I have a ...
1
vote
0answers
21 views

If symmetric matrix in a least-square deconvolution problem positive definite?

I want to apply Gauss-Seidel method in a least square deconvolution problem. The convolution of two vectors is written in: $h * x = z$. $$z(n) = \sum_{i=0}^{N-1}h(i)x(n-i)$$ It is a linear transform ...
1
vote
0answers
18 views

Change in Singular Value Decomposition of a matrix on addition of a single row

Given that I know the svd decomposition of a matrix, is there any way to compute the svd decomposition of the matrix obtained by adding a single row to the original matrix? Is there any relation ...
0
votes
0answers
30 views

How to find a transformation matrix T?

(1.) Suppose there is matrix C of dimension "p by n" where p is less then n i.e. p I want to know is there any particular way exist to find transformation matrix T of dimension "n by n" such that ...
0
votes
2answers
36 views

Eigenvalues and eigenvectors of a matrix

We know that if $\lambda (\neq 0)$ is an eigenvalue of a matrix $A$ corresponding to eigenvector $X$, then $\dfrac{1}{\lambda}$ is an eigenvalue of $A^{-1}$. But whether the corresponding eigenvector ...
0
votes
0answers
18 views

Orthogonal polynomials induction proof

I tried writing this all out but cannot seem to get anything sensible. Basically I want to prove that assuming w(x) is the weight function of a Gram Schmidt orthogonalization process and w is an ...
2
votes
1answer
63 views

Matrix Norm Inequalities and Linear Least Squares

I am working through one of my universities old QUALS and came across the following problem: Let $A,E\in \mathbb{C}^{m\times m}$. Suppose that $\sigma_\min>0$ is the smallest singular value of ...