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

learn more… | top users | synonyms

3
votes
2answers
155 views

How to efficiently solve a series of similar matrix equations using the LU decomposition

This is the problem I'm dealing with: Let $\sigma_1,\dots,\sigma_n \in \mathbb{R}$ and $b_1,\dots,b_n$ be column vectors of length $n$. Consider the system $$ (A - \sigma_jI)x_j = b_j, \quad ...
0
votes
1answer
26 views

Function from one Null space to Another

Suppose a single vector space over $R$ of degree $n$, and two matrices $A, B$ of arbitrary row size, but col size $n$, s.t. their individual null spaces are linear subspaces of this vector space. Is ...
0
votes
0answers
39 views

Are there any sure-fire methods for correctly arranging matricies for Gaussian Elimination?

I am attempting to make a Gaussian Elimination solver for systems of linear equations that contain less than 100 equations. I have roughed out a method for creating and filling in the diagonal of a ...
0
votes
4answers
233 views

Shortest Distance between a Point and a Numerical 2D Curve

I have a 2D Curve. I have all the numerical values for the line within a certain range. I do not have an equation for this line. At several points in this 2D space I want to calculate the shortest ...
0
votes
0answers
35 views

Stuck on condition number derivation of the perturbed equation $(A + \Delta)\tilde{x} = b + \delta_b$

I've almost got what I want. We start with $Ax = b $ and $(A + \Delta)\tilde{x} = b + \delta_b$. What I have then is \begin{align*} \tilde{x} - x &= -A^{-1}\Delta\tilde{x} + A^{-1}\delta_b \\ ...
2
votes
1answer
99 views

compute the bisecting normal hyperplane between two $n$-dimensional points.

I have two points $\mathbf{x_1}$ and $\mathbf{x_2}$, where $\mathbf{x_i}=\{x^i_1, x^i_2, \ldots, x^i_n\}$. I need to find a normal hyperplane $P$ that goes through the midpoint of $\mathbf{x_1}$ and ...
1
vote
1answer
330 views

Jacobi vs. Gauss-Seidel: convergence

I know that for tridiagonal matrices the two iterative methods for linear system solving, the Gauss-Seidel method and the Jacobi one, either both converge or neither converges, and the Gauss-Seidel ...
0
votes
1answer
171 views

Tridiagonalize matrices with Householder transformation

I know that it is possible to tridiagonalize symmetric matrices by using a Householder trafo. I also found that we can get any matrix to Hessenberg form by using Householder trafos, but I still don't ...
0
votes
0answers
56 views

Integration of ODE equation in Matlab / Octave

I have a system of 8 ODE's where the initial conditions are in matrix form. $\frac{dT}{dS} = H T$ where T at the initial state is the identity matrix. $T(a) = I$ H is a constant 8x8 matrix T is ...
0
votes
0answers
80 views

Is the Hessenberg form of a matrix unique?

I have to calculate the Hessenberg form of an matrix using householder reflectors. For real Matrices I get the same result as the 'hess()' function in Matlab, but for Complex Matrices I keep getting ...
0
votes
0answers
97 views

Alternative to the Gram-Schmidt Procedure for Orthogonalization

I was wondering if there is an alternative to the Gram-Schmidt procedure, which instead of being a successive orthogonalization scheme, would be non-successive (simultaneous)? In other words, is there ...
1
vote
1answer
36 views

Matrices admit a QR decomposition

I just wanted to ask which matrices admit a QR decomposition. I think that all matrices $A \in \mathbb{R}^{m \times n}$ with $m \ge n$ admit a QR decomp. Are these the only ones that have a QR decomp, ...
5
votes
1answer
209 views

Generate arbitrary numerically invertable matrix

I'm designing a unit-test for a matrix inversion function. Currently I make a random matrix as a test case by generating its elements with random numbers uniformly distributed in $[0,1)$. If I ...
1
vote
0answers
126 views

stability of FTCS scheme for parabolic equation

Can you suggest any method for stability analysis of FTCS scheme for the the following parabolic equation ? D.E: $u_{t}=a(x,t)u_{xx}+f(x,t,u)$, $0<x<1$, $0<t<T$, $T>0$ BCs: ...
0
votes
0answers
105 views

Proof of theorem about iterative methods

How do I prove that if $A$ is a tridiagonal (or block tridiagonal) matrix then the corresponding $P_J$ and $P_G$ iteration matrices for the Jacobi and Gauss-Seidel methods satisfy that if $\lambda$ is ...
4
votes
1answer
475 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
29 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?
0
votes
1answer
258 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{ ...
0
votes
1answer
45 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 ...
0
votes
2answers
109 views

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
1answer
82 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
113 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
2answers
74 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
55 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 ...
1
vote
0answers
30 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 ...
1
vote
0answers
28 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. ...
2
votes
0answers
70 views

Numerically approximate the maximum of an element of a vector after a series of matrix multiplications.

Where S is a sigmoidal function, A_i is a matrix, and x is an input vector, and ...
0
votes
0answers
48 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
1answer
95 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 ...
1
vote
0answers
51 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
306 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
43 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
47 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
116 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
2answers
120 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 ...
0
votes
1answer
84 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,\; ...
2
votes
3answers
561 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
50 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
42 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 ...
1
vote
0answers
42 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
1answer
50 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
60 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
131 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
56 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
40 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, ...
3
votes
1answer
102 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
103 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 ...
1
vote
0answers
67 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
53 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} ...
0
votes
1answer
52 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 + ...