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

learn more… | top users | synonyms

-1
votes
0answers
10 views

interpolating method

Let the function $f(x)=\ln\left(\frac{1}{|x-1|}\right)$ be approximated by an interpolating polynomial of degree 15 with the nodes equally spaced in the interval [-1, 0]. What bound can be placed on ...
-1
votes
0answers
30 views
+50

Different method for QR decomposition - is it possible

This method could also possibly be applicable to matrices of higher dimension, but for the simplicity of my question i will only ask it for $2$x$2$matrices. Suppose $A=\begin{pmatrix} a_{11} & ...
0
votes
2answers
196 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 ...
0
votes
1answer
54 views

Finding the smallest max eigenvalues for related matrices?

While messing around with a spectral approach to a graph coloring question, I happened upon a type of problem I hadn't seen before. Suppose you have two symmetric $n$ x $n$ matrices in the form ...
0
votes
1answer
27 views

Reentrant constraints in active set algorithm?

Problem definition Supposing you're trying to solve a quadratic program: $$ \min_x f(x) = \frac{1}{2}x^T Q x + c^T x \\ \mbox{s.t} \, \; A x \ge b$$ Where Q is square ($n$x$n$), positive semi ...
2
votes
0answers
23 views

3-sigma Ellipse, why axis length scales with square root of eigenvalues of covariance-matrix

This is my first post on math.stackexchange and i am not a mathematician, but i took some undergrad math courses and some grad mathematical modelling courses, so i come with a basic understanding of ...
1
vote
1answer
9 views

Condition number of a matrix bounded from below and above?

Is condition number of an invertible matrix bounded from below? And is condition number always bounded from above for an invertible matrix?
3
votes
1answer
215 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 ...
0
votes
1answer
19 views

Prove that Frobenius matrix norm is compatible with the vector norm

Show that, the Frobenius matrix norm $||.||_F$ is compatible or consistent with a vector norm $||.||_2$ , that is, $||Ax||_2 \leq ||A||_F ||x||_2, \forall x \in \mathbb{R}^n$. Where $||A||_F = \sqrt{ ...
-1
votes
1answer
51 views
0
votes
0answers
11 views

How is this a substitution? Linear algebra transformation matrix misunderstanding

I found the following matrix equation in '3D Surveillance System Using Multiple Cameras', (authors: Ajay Kumar Mishra, Bingbing Ni, Stefan Winkler, Ashraf Kassima) (link here): I don't follow the ...
-2
votes
0answers
34 views
0
votes
0answers
10 views

find the mean of a collection of the solutions of given linear systems

Suppose one has a group of $k\times k$ square matrices $A_i, i = 1,2..n$, another $k$-vector $b$ is also given. I want to exam the mean of the group of vectors $x_i$ over $i = 1,2...n$ where $A_i * ...
0
votes
1answer
44 views

Unique least square solutions

There is a theorem in my book that states: If $A$ is $m\times n$, then the equation $Ax = b$ has a unique least square solution for each $b$ in $\mathbb{R}^m$. But can we find a counter-example to ...
4
votes
1answer
27 views

Implementing trig functions for dual numbers

I'm curious, how do common trig functions get implemented for dual numbers? One way would be to use the power series definition, but that seems inefficient
1
vote
0answers
20 views

Setting up Kernel to Numerically Solve Fredholm Equation of Second Kind

I am looking to confirm if what I am doing is the proper procedure. I writing a program to discretely solve a Homogeneous Fredholm Equation of Second Kind that is set up as follows: $ \int ...
5
votes
2answers
276 views

Check whether two subgroup of $GL(n,\mathbb Z)$ are conjugate

Suppose I have two finite subgroups of $GL(n,\mathbb Z)$. Is there an algorithm to find out whether these two belong to the same conjugacy class in $GL(n,\mathbb Z)$? I tried by using the Jordan ...
0
votes
0answers
12 views

Numerical methods for computing exponential, if I have computed an exponential of a perturbated matrix

I need to compute the product $e^{H_1}\,e^{H_2}\,\ldots\,e^{H_n}$ for antihermitian matrices $H_j$ that do not commute and $H_i-H_{i+1}$ is small. Is there a numerically convenient way to compute ...
0
votes
2answers
42 views

Spectral radius and iterative method convergence

I'm trying to show that if the spectral radius of $R$, $\rho(R)\geq 1$, then there exist iterations of the form, given $\mathbf{x}_0$, $\mathbf{x}_{n+1}=R\mathbf{x}_n+\mathbf{c}$ Which do not ...
2
votes
0answers
64 views
0
votes
0answers
13 views

Nearest points / residuals on a total least squares parabola

Consider fitting a parabola $y = a + bx + cx^2$ to 2d data $X_i, Y_i$ with noise in both X and Y, using the the singular value decomposition as in Total_least_squares (TLS): $\qquad X = [ 1\ \ Xdata\ ...
1
vote
1answer
356 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
0answers
11 views

Transformation between Ideal and Warped Surface

I work on manufacturing metal panels with holes drilled in them. Suppose I have an ideal 3D surface from CAD. I want to compare it to the actual part using reference points to compare between the two. ...
3
votes
1answer
215 views

Numerical verification of solution.

I have the non-linear equation \begin{align} &\left( {x}^{2}-1 \right) \left( -\frac{1}{4}\left({\frac { \left( 4\,{x}^{3}+2\, ex \right) ^{2}}{ \left( {x}^{4}+e{x}^{2}+f \right) ...
0
votes
0answers
2 views

How can I apply a median filter directly to a time-varying rotation matrix?

I need MatLab script which would take a series of rotation matrices (referring to an actual physical object's orientation) and apply median filter to it to eliminate speckle noise from it. The way ...
0
votes
0answers
40 views

Fastest Algorithms for Determining the Nullity of a Matrix

How exactly does one go about determining the Nullity of a Matrix quicker than simply running Gaussian Elimination on the matrix itself? To be perfectly honest I can't think of a method that doesn't ...
0
votes
0answers
30 views

Complexity of the power method

I'd like to find out what the complexity of the power method is depending on the size of the matrix $A \in \mathbb{R}^{n\times n}$ given that the algorithm runs until a certain stop criterion. I.e. ...
0
votes
0answers
27 views

resources about sparse global constrainted optimization

Please recommend a good resources (books/articles/software) about sparse global constrained optimization?
1
vote
1answer
253 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 ...
1
vote
0answers
28 views

Numerically stable way to compute $\text{Trace}[\mathbf A\mathbf A_1^{-1}\mathbf B\mathbf B_1^{-1}]$

I have two dense (column-major) PSD matrices $\mathbf A$ and $\mathbf B$, $\mathbf A,\mathbf B\in\mathbb R^{n \times n}$ ($n$ is usually $\sim 1000$) and also $\mathbf A_1=\mathbf A+\eta\mathbf I_n$ ...
0
votes
1answer
44 views

Solving 2x2 diagonally dominant matrix systems (non-symmetric)

I have a linear system of the form $Ax=b$ where $A\in \mathbb{R}^{2\times2}, b\in \mathbb{R}^{2\times1}$. A is diagonally dominant and non-symmetric. This is a "kernel" that I am using to solve a ...
0
votes
1answer
34 views

Application of Conjugate Gradient Method to non-symmetric matrices

I am currently working on a problem in which I am using the Conjugate Gradient method to solve for the steady state solution of a continuous time Markov chain. I am applying the algorithm found in ...
0
votes
1answer
25 views

Finding SVD of a Matrix

If $a_{1},a_{2} \in \mathcal{R}^{2},$ $\ \|a_{1}\|_{2} = \|a_{2}\|_{2} = K$, and the angle $\theta$ between $a_{1}$ and $a_{2}$ is between $0$ and $\pi/2$, we want to compute the SVD of the matrix $A ...
1
vote
0answers
27 views

How to find the rank of a toeplitz matrix?

Is there any trick to compute or estimate the rank of a toeplitz matrix ? Or is this still unknown for a general toeplitz matrix ?
4
votes
2answers
68 views

Rewriting the matrix equation $AX = YB$ as $Y = CX$?

Is it possible in general, if $A,B,C,X,Y$ are square and of the same dimensions? If so, does it generalize to non-square matrices (using a pseudoinverse)? I'm doing some curve fitting in which I have ...
0
votes
1answer
49 views

Proving boundedness of a function (part 1).

Consider the function \begin{eqnarray} f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i}, \end{eqnarray} over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; ...
0
votes
0answers
16 views

estimate an upper bound for the error of an interpolation polynom

The task is to estimate the error of an interpolation polynom $p(x)$ to an function $f(x)$. The sampling points are $x_0 = -1,\ x_1= 0,\ x_2=1,\ x_3=3$ So i already calculated the polynom which does ...
2
votes
1answer
41 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 ...
2
votes
3answers
52 views

How to reverse matrix vector multiplication?

I'm using the simple matrix x vector multiplication below to calculate result. And now I wonder how can I calculate ...
1
vote
0answers
32 views

Iterative methods for solving a linear equation system

There are several methods known for solving a linear equation system Ax = b (like Jacobi or Gauss-Seidel) by iterating $x_{n+1}=Mx_n+c$ with a matrix M, for which some norm is smaller than 1. But ...
2
votes
1answer
33 views

A generalization of GMRES

In oder to solve $Ax=b$, GMRES method finds $x_n$ in the $k$-th Krylov subspace i.e.: $$K_n=span\{b,Ab,...,A^{n-1}\}$$ and we have the condition: minimize $\|r_n\|_2$, which $r_n=b-Ax_n$ Now we ...
2
votes
3answers
284 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
26 views

Solving tridiagonal matrices where the top left element is zero

If I have a matrix like this: $$ \left[\begin{array}{rrrrrrrrr|r} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & ...
2
votes
2answers
59 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
47 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
43 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 ...
1
vote
0answers
40 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
36 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. ...