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

learn more… | top users | synonyms

0
votes
1answer
38 views

Estimating rates of convergence

If I have a set of data points obtained from a numerical approximation say 15.3828 15.2458 15.2095 15.2003 how can I estimate the rate of convergence?
0
votes
1answer
56 views

How does LU decomposition work?

I'm interested in the algorithm of LU decomposition in order to solve a LSE like $Ax=b$, where $A$ is a square matrix. My question is: When I compute $PA=LU$ do I also need to interchange rows in $L$ ...
3
votes
1answer
130 views

A Beautiful Determinant!

Find the determinant of the following matrix in the terms of $a_1,a_2,\cdots,a_n$ explicitly, $$ \begin{bmatrix} a_1 & a_2 & a_3 & \cdots & a_n\\ a_2 & a_3 & a_4 & \cdots ...
0
votes
0answers
43 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
1answer
3k views

Gauss Seidel iteration in matlab

I've posted this question before for crout factorization. Now, I need help with Gauss-Seidel iteration. Write a program that takes a value for n and solves for x using the following method: ...
1
vote
0answers
25 views

Simultaneous iteration of Symmetric Matrices

Given a Matrix $A$ we can use Simultaneous iteration(Using power iteration on all columns simultaneously) to compute the d biggest eigenvalues. Now this method will give you the biggest eigenvalues, ...
1
vote
0answers
32 views

Gerschgorin Theorem singularity proof

I know how to prove the Gerschgorin Theorem but how exactly would one show that there are no values of $\mu$ s.t. $\mu<0$ for which $A-\mu B$ is singular where $$ A= \begin{bmatrix} ...
1
vote
0answers
24 views

Gaussian Elimination theoretical question

You know how Gaussian Elimination can be broken up into a sequence of L-U premultiplications right? Suppose that there is a matrix $A=a_{i,j} : j=1,...,n$ is an $n × n$ real matrix such that ...
4
votes
1answer
46 views

QR-Decomposition of matrix valued function

I already posted the following question on MO, but id did not raise much interest there. Maybe the title is too elementary to gain research interest. Suppose I have a matrix valued function $$ ...
0
votes
0answers
45 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 ...
0
votes
1answer
32 views

Using Givens Rotation on a vector

Say we have a vector v=$[3\ 0\ 4]$. Find a 3x3 orthogonal matrix Q such that only the second component of Qv is nonzero and such that this component is also positive. Is Q unique? I tried ...
0
votes
1answer
58 views

Show that the iteration $x_{n+1} = x_n - 2\frac{f(x_n)}{f'(x_n)}$ converges quadratically to $x_*$ provided $x_0$ is sufficiently close to $x_*$

We have the following conditions for the above slightly-modified Newton's method iteration: $f$ is a real function of one real variable $f''$ is Lipschitz continuous $f(x_*) = f'(x_*) = 0$ I also ...
2
votes
1answer
65 views

Non-Orthogonal Eigenvectors and Computation?

Say for a real, rectangular matrix $X$ and a s.p.s.d matrix $Q$ we maximize or minimize $Tr(X^TQX)$ under the constraint $Tr(X^TM) = 1$ for some fixed real matrix $M$. i) Would the columns of the ...
1
vote
0answers
55 views

Least squares of symmetric positive semidefinite matrices

What's the best (in terms of computation time and numerical robustness) way to find the least squares solution of $$Ax = b$$ if $A$ is symmetric and positive semi-definite? If $A$ were symmetric and ...
2
votes
1answer
36 views

Eigenvalue of (1-0) matrix

Assume I have 2 matrices, each of size nxn with only 1 and 0 as entries in both. (n>10) The first matrix (call it A) has each row summing up to 2 (ie: on each row, it has two "1" and n-2 "0"). It is ...
1
vote
2answers
149 views

Cholesky Decomposition for positive semidefinite separation

Cholesky decomposition is a common way to test positive semi definiteness of a symmetric matrix $A$. If the algorithm "goes wrong" trying to take a square root of a negative number, I know the matrix ...
0
votes
1answer
71 views

Householder matrix Uw acts as the identity on the subspace w

How can i show that a Householder matrix $U_w$ acts as the identity on the subspace $w$? and that it acts as a reflection on the one-dimensional subspace spanned by w; i.e., $U_w(x) = x$ if $x$ is ...
3
votes
1answer
87 views

Is there a faster way to calculate a pseudo-inverse of a matrix than using SVD that is as numerically stable as with SVD?

Is there a faster way to calculate a pseudo-inverse of a matrix than using SVD that is as numerically stable as using SVD?
0
votes
2answers
34 views

Minimum of Maximum of Addition of two vectors/arrays

Suppose you have two arrays and you want to compute the maximum of the addition of the two arrays. Now you move the second array one field to the right. Now you can compute the maximum again of the ...
1
vote
1answer
71 views

Homework for Gauss Seidel method

Let A be a strictly diagonally dominant matrix. Suppose we use Gauss Seidel method to solve $Ax=b$, a sequence of vectors {$x_{0},x_{1},...,x_{k},...$} is obtained (where $x_{0}$ is the initial guess) ...
0
votes
1answer
88 views

Linear system of equations and multiple linear regression: Numerical solving

I am currently implementing a test procedure for data, namely a linear form of the Kramers-Kronig relations (paper here: http://jes.ecsdl.org/content/142/6/1885.abstract). This includes solving a ...
0
votes
0answers
37 views

cubic B-spline interpolation function

I read that the B-spline basis functions are the follows: $B_0(x)=(1-x)^3/6$ $B_1(x)=(3x^3-6x^2+4)/6$ $B_2(x)=(-3x^3+3x^2+3x+1)/6$ $B_3(x)=x^3/6$ The cubic b-spline interpolation function it ...
0
votes
0answers
66 views

convergence for symmetric, positive semi-definite operator

Assume $u$ is a vector in the Euclidean space $\mathbb{R}^N$, $||u||=\sqrt{\langle u, u\rangle}$, where $\langle u, v\rangle = \sum_{i=1}^N u_i v_i$. I have that $||u^{k+1}-u||\leq ||I - c ...
0
votes
1answer
42 views

Reference request: nonlinear systems, optimization, ode/pde

Could someone suggest me one or more good books on the following topics: Nonlinear systems: fixed point and Newton's method Optimization: steepest descent and Newton's-quasi newton methods ODE ...
2
votes
0answers
135 views

Standard symmetric tridiagonal matrix Eigenvalue decomposition algorithm?

Hi I am trying to generate an arbitrary Gauss quadrature rule by using the Golub-Welsh algorithm (here). I need to code this on C++ for my personal project. This algorithm involves the eigenvalue ...
0
votes
0answers
63 views

Numerical Linear Algebra- Proof for the Backward stability of inner Product?

I know that inner product is backward stable through various sources but to prove this statement is which I'm not aware of...if someone could help me with that that would be great. ...
0
votes
1answer
50 views

Numerical Linear Agebra

how to Prove the backward stability of the inner product ? ...
1
vote
2answers
71 views

Exponential of a 3x3 lower bidiagonal matrix

I have a 3x3 matrix with non-zero entries ONLY along the main diagonal and the diagonal above. There are exactly two non zero diagonals in the matrix like this \begin{pmatrix} a & 0 & 0 \\ d ...
0
votes
1answer
33 views

How to make a function lie in the interval [0,1]

Is there a way to convert a function g(x) so that the result lies between [0,1]? Thank you in advance.
1
vote
1answer
761 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
33 views

Solving Ax = b where A is composed of diagonal blocks

I would like to solve the equation $Ax=b$ where $x\in\mathbb{R}^n$ and $A$ is of the form: $$A= \begin{bmatrix} D_1 & D_2 &D_3 \\ D_2 & D_4 & D_5 \\ D_3 & D_5 & D_6 ...
1
vote
1answer
39 views

Checksum Invariants for Matrix Inversion via Gaussian Elimination

In general, when solving $Ax=b$, we make the $[A|b]$ matrix and doing row operations to reduce the left hand side to an identity. It's painfully annoying to find mistakes in the process. Assuming we ...
0
votes
0answers
24 views

Iteratively solve linear equations with rank-1 updates on LHS and RHS

What is the best way to iteratively solve updating equations of the form $$ Ax=b $$ $$ (A+c_1v_1^\intercal)x_1=b+ \alpha_1 d_1 $$ $$ (A+c_1v_1^\intercal+c_2v_2^\intercal)x_2=b+\alpha_1d_1+\alpha_2d_2 ...
1
vote
1answer
19 views

Equality of iterates produced by Minres and GMres for practically symmetric matrix

My system is from time-integration of the semi-discretized Stokes equation. The time update of the variables $(v,p)$ is defined via the solution of $$ \begin{bmatrix} A & -\tau B^T \\ B & 0 ...
2
votes
0answers
51 views

Examples of non trivial problems in this structure.

I'm looking for examples of non trivial problems that match with the follow structure. Let the function $$g: U \times V \rightarrow \mathbb{R}$$, where $U$ and $V$ are complex vetorial spaces of ...
0
votes
2answers
70 views

Legendre Polynomial Orthogonality and Size

Show $(P_i,P_j)=\begin{cases} 0& i \neq j \\ \frac{2}{2j+1} & i = j\end{cases}$ for $0 \leq i, j\leq2$ I'm just not sure exactly what I'm supposed to do. Do I plug in values of i and j and ...
0
votes
1answer
54 views

Householder Reflection

I am working on algorithms for SVD by first performing Householder transformation. I got my algorithm to work but I'm trying to gain a better intuition of it. My understanding is that the ...
1
vote
1answer
48 views

Can a tridiagonal matrix be rectangular?

My program works with tridiagonal matrices (calculates its LU decomposition) so before doing anythig, it stores the matrix in 3 vectors: the three diagonals only. So far my conclusion was, a ...
0
votes
0answers
56 views

Rank and solvability of a matrix

I am working with linear complementarity problems (LCPs) which look for a solution $\mathbf{x} \in \mathbb{R}^{n}$ in the form $$ \begin{matrix} \mathbf{x} & \geq & 0 \\ ...
1
vote
2answers
72 views

Square Idempotent matrix: efficient algorithms for finding eigenvectors

Given a square idempotent $N \times N$ matrix $A$ with large $N$, and a priori knowledge of the rank $K$, what is the most efficient way to compute the $K$ eigenvectors corresponding to the $K$ ...
0
votes
1answer
66 views

matrix exponential and Spectral abscissa

Prove that $\lim_{t \rightarrow \infty} \|e^{tA}\| = 0$ if and only if $\alpha(A) < 0 $, where $\alpha$ is the Spectral abscissa, defined as $\max{Re(\lambda_i)}$. I tried to approach this ...
0
votes
1answer
79 views

Can SVD help to solve (inequality) constrained least squares problem?

Consider the following minimization problem: $$ ||Q u - h^{o} ||^{2} \to min \;\;\; s.t. \; u \geq 0 $$ where $Q$ is $m \times n$ matrix and $u$ is $n$-dimensional vector and $h^{0}$ is ...
1
vote
2answers
68 views

non-sequential sequence function

if i remember correctly (i had one workshop on numerics years ago, sorry for my lack of knowledge) there is a way to create some sort of hash function that gives you a non sequential sequence. This ...
2
votes
0answers
33 views

Smallest set of Liner equations, which exactly fit a set of points

I have a set of 2-d points,(it can be of any arbitrary dimension n). I want to find the minimum set of straight lines(linear equations) which exactly passes through the given 2-d points (unlike ...
4
votes
4answers
200 views

Finding nonnegative solutions to an underdetermined linear system

Here's the environment of my problem: I have a linear system of 4 equations in 8 unknowns (i.e. $Ax = b$, where $A$ is $4 \times 8$, $x$ is $8 \times 1$, and $b$ is $4 \times 1$, with $A$ given and ...
0
votes
1answer
52 views

Is there a limit for how “good” a numerical method can be?

Multiplying two matrices $A \cdot B$ of size $n \times n$ in the trivial way requires $n^3$ computations. However, more efficient algorithms such as the Strassen algorithm have a lower complexity of ...
0
votes
3answers
63 views

About matrix products $A^{T}A$ and $ AA^{T} $

I'm investigating the relationship between 2-norms and eigenvalues of $A^{T}A$ and $ AA^{T} $, in order to better understand the SVD decomposition. How can I prove that $A^{T}A$ and $ AA^{T} $ are ...
2
votes
0answers
104 views

Inverse of the sum of a symmetric and diagonal matrices

I have two square matrices, $A$ and $B$. $A$ is a block symmetric matrix with 1's along the diagonal (and therefore 1's in whole blocks along the diagonal). $B$ is a block diagonal, with the same ...
0
votes
0answers
19 views

need to determine weights so that quadrature formula holds

Let $l$ be an interval on the real axis, $t_1,...,t_n$ be distinct $n$ points, then there exists n numbers $m_1,...,m_n$ such that the quadrature formula, $\int_l p(t)dt = m_1p(t_1) + ... + ...
0
votes
1answer
25 views

Complexity of sparse back substitution

What is the complexity of sparse backsubstitution $Rx = b$, given $n$, the dimensions of dense $x$ and $b$ as well as of the sparse $R$ and $nnz$, the number of nonzero entries in $R$?