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

learn more… | top users | synonyms

0
votes
0answers
20 views

Jacobi Iteration with Shift

The question is to solve a linear system using Jacobi iterations with a shift of mu = 5. My code converges very quickly, but it does not yield the results that MATLAB gives with the backslash ...
0
votes
0answers
12 views

Convergence of recursive application of finite-difference operator to $C^{\infty}$ functions

Let $f\colon \mathbb{R}\to \mathbb{R}$ be an arbitrary smooth function (whose extension to a complex differentiable function is entire, if it matters). Let $\mathbf{D}_{h}$ be a finite difference ...
0
votes
0answers
9 views

Get stuck with some statements of convergence rate of the iteration method from “Iterative methods for sparse linear systems (2nd edition) ”

Here are the statements I get from the book and the two highlight parts are what I can not understand well. The questions are: Why we can conclude that $\rho=\rho(G)$ from"the above analysis"? ...
0
votes
0answers
21 views

Interpolation question about polinomials?

Let $f(x)=x^n$. show that for each $n$ distinct point $x_0,... x_n$ we have $f[x_0,...x_n]=0$ and $f[x_0,...,x_{n-1}]=\sum_{i=0}^{n-1}x_i$. also show that if $x_{i+1}-x_i$ is fixed for each $i\ge 0$ ...
0
votes
0answers
11 views

Applying perturbed matrix to unperturbed eigenvector

Suppose we've got a matrix $P$ and a perturbed version $\hat{P}=P+E.$ Given that $v$ is an eigenvector of $P$ with $Pv=0,$ I'd like to get as sharp a bound as possible on $\hat{P}v$ (in terms of ...
0
votes
0answers
54 views

Matlab project - Jacobi method for tridiagonal matrices…

I have to do a project in Matlab to my University and I don't quite understand what I should do. I was given script that solves systems of equations with Jacobi's method with given tolerance and ...
0
votes
0answers
18 views

$Tn(x) =\frac{(x-\sqrt{x^2-1})^n+(x+\sqrt{x^2-1})^n}{2}$, show that $|Tn(x)| \le 1,\forall x \in [-1,1]$

$Tn(x) =\frac{(x-\sqrt{x^2-1})^n+(x+\sqrt{x^2-1})^n}{2}$, show that $|Tn(x)| \le 1,\forall x \in [-1,1]$
0
votes
0answers
12 views

Consistently obtaining the negative of the correct eigenvalue in hand calculations

The question is "find the eigenvector of A corresponding to the given eigenvalue" A = | 1 0 2 | |-1 1 1 | | 2 0 1 | Eigenvalue = -1 Add -1 * I to A Row reduced to | 1 0 1 | | 0 1 1 ...
0
votes
0answers
35 views

QR Algorithm without Shifts (Trefethen and Bau)

A real symmetric matrix $A$ has eigenvalue 1 of multiplicity 8, while all the rest of the eigenvalues are $\leq 0.1$ in absolute value. Describe an algorithm for finding an orthonormal basis of the ...
0
votes
0answers
27 views

Strictly diagonally dominant matrix -LU factorization

Let $A\in\mathbb{C^{n\times n}}$ be strictly diagonally dominant. I want to show that the LU factorizations with and without partial pivoting are the same for these matrices. For start, I created ...
0
votes
0answers
19 views

Pairing Two Point Clouds

So I have two point clouds $X$ and $Y$ each with $N$ points in the familiar $\mathbb{R}^3$ euclidian 3D space. I then have an inter-point distance $d(\vec x_i,\vec y_j)$ which is zero if $\vec x_i$ is ...
0
votes
0answers
16 views

Relative Error with Respect to Frobenius Norm

I'm look at this tiny book called "Deblurring Images: Matrices, Spectra, and Filtering" by Hansen, Nagy, O'Leary. This is a self study, but I believe my question is broad enough so that it can be of ...
0
votes
0answers
11 views

Dimensionality Reduction

Let $X\in\mathbb{R}^{100\times 100}$ matrix and let its eigenvector and eigenvalues be $X_{vec}$ and $X_{val}$ respectively. If the rank of $X$ is $5$, then is it possible to approximate $X$ with ...
0
votes
0answers
23 views

Condition number perturbation

I have a matrix of the form $\tilde{H} = H + i A A^\dagger$. It is known that $H$ is hermitian and that $\tilde{H}$ is invertible and $A A^\dagger$ has a kernel of dimension $\geq 1$. I want to study ...
0
votes
0answers
25 views

Householder reflector sign error

I am studying Householder reflectors from Trefethen and Bau but am having trouble creating a simple example for it. I am given the equation for the vector v that the Householder reflector H is based ...
0
votes
0answers
21 views

Computing a few eigenvalues of large sparse nonsymmetric matrix without LU factorisation

I'm trying to find a few targeted eigenvalues of a large sparse (N=1e6,nnz=4e6) non-symmetric matrix. Currently I'm using MATLAB's 'eigs' function with the 'sigma' option and this uses the Shifted ...
0
votes
0answers
17 views

SOR and Conjugate Gradient Method

Let $H_n=[H_{ij}]\in\mathbb{R}^{n\times n}$ be Hilbert Matrix, define $h_{ij}=\frac{1}{i+j-1}$ and $x=\left(1\quad 1\quad\cdots\quad 1\right)\in\mathbb{R}^{n\times n}$ such that $b_n=H_nx$. Use SOR ...
0
votes
0answers
24 views

Recasting Ax=b to use SOR method

Just need some guidance as to how to recast the matrix equation equation $Ax = b$ so that I can produce an iterative matrix to perform Succesive Over Relaxation on. These matrices are $n x n$ I ...
0
votes
0answers
15 views

Properties of specific case of the gradient descent method

Consider the gradient descent method for the system $Ax=b$ where, $A=\begin{pmatrix}1 & 0 \\0 & a\end{pmatrix}, b=\begin{pmatrix}0 \\ 0\end{pmatrix}$ and the initial vector ...
0
votes
0answers
36 views

Optimized way to compute L1 distance matrix

I'm computing distances between two groups of multi-dimensional points giving a matrix of distances pairwise between points. For the L2 (euclidean) distance I can use optimized matrix multiplication ...
0
votes
0answers
42 views

Saddle point problem (KKT) with block-diagonal matrix

Consider the following saddle point problem originating from an interior-point method algorithm: $$ \begin{bmatrix}\mathbf{H} & \mathbf{A}^{T}\\ \mathbf{A} & \mathbf{0} ...
0
votes
0answers
35 views

matrix diagonalization without eigen decomposition, what other ways available?

I have a matrix, $A$ (it may be symmetric or asymmetric). I need to have a diagonal matrix without eigenvalue decomposition, please suggest what others ways are possible? Any new idea would be much ...
0
votes
0answers
24 views

computing leftmost eigenpair of positive-definite matrix

Let $A$ be an $n\times n$ real symmetric positive-definite matrix. Assume that $n$ is large and that $A$ is dense (i.e. it is not sparse). Question: What is the state-of-the-art algorithmically for ...
0
votes
0answers
42 views

Test for powers method

I have been told that for a normal matrix $A$, the powers method (i.e. computing the succession of Rayleigh quotients for a succession of vectors $z_k=A\cdot z_{k-1}$) can use the following stop ...
0
votes
0answers
34 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
0answers
22 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 \\ ...
0
votes
0answers
42 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
33 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
70 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 ...
0
votes
0answers
69 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 ...
0
votes
0answers
24 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 ...
0
votes
0answers
30 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\ ...
0
votes
0answers
21 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
42 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
57 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
29 views

resources about sparse global constrainted optimization

Please recommend a good resources (books/articles/software) about sparse global constrained optimization?
0
votes
0answers
57 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 ...
0
votes
0answers
29 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 ...
0
votes
0answers
38 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, ...
0
votes
0answers
44 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 ...
0
votes
0answers
34 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
46 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
46 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
0answers
28 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 ...
0
votes
0answers
19 views

Maximal angle between kernel of rows of a matrix

Consider a matrix with 2 columns $$ \begin{pmatrix} a_1 & b_1 \\ a_2 & b_2 \\ a_3 & b_3 \\ \vdots & \vdots \end{pmatrix} . $$ To each row $(a_i \;\;\; b_i)$, one draws the kernel ...
0
votes
0answers
28 views

Not enough memory for GMRES

After realizing that Gauss-Seidel is extremely slow for my simulation, i wanted to try GMRES and luckily found the C++ code here without diving into the theory. The size of the matrix in my case is ...
0
votes
0answers
59 views

Francis Algorithm (Implicit QR Algorithm)

In Numerical Analysis, we are touching upon QR and Francis Algorithm. I understand that for Francis's Algorithm, we reduce the matrix to its upper Hessenberg form using Householder transform. What I ...
0
votes
0answers
58 views

Upper Hessenberg Form

I am given a matrix. I would like to reduce it to its upper Hessenberg Form. We are discussing eigenvalue computations in Numerical Analysis and the textbook just gives the algorithm for it without an ...
0
votes
0answers
44 views

Minimizing a vector constrained to a set

Sorry if this is wordy or over-complicated, I'm not sure how to isolate the problem any more than I have below without losing important context: I'm trying to implement a coordinate block descent ...
0
votes
0answers
48 views

QR Algorithm with Shifts Question

Why must QR Algorithm with Shifts make no progress when applied to this n x n matrix? (attached as image). Also, if a matrix A is orthogonal in a QR factorization, will R be tridiagonal? How would ...