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

learn more… | top users | synonyms

5
votes
1answer
66 views

proving a theorem of alternative

I've read the following exercise in my book: Let $A\in\mathbb R^{m\times n},b\in\mathbb R^m,c\in\mathbb R^n$. Then exactly one holds: $Ax=0,c^t\cdot x=1$ with $x\geq0$ has a solution $A^ty\geq c$ ...
1
vote
1answer
1k views

Trapezoid Rule to Simpson's Rule Extrapolation

I need to show that one extrapolation of the trapezoid rule leads to Simpson's rule. I've looked through the other posts on ME, specifically the post with the same title, and this for help, but I ...
2
votes
1answer
109 views

(A + D)x = b … efficiently!

let say we have $A$ to be symmetric positive-definite (SPD), moreover block tridiagonal Toeplitz matrix and $D$ is block diagonal SPD (both with full rank). Let say we know everything about $A$ and ...
0
votes
1answer
50 views

Its about Finding the values of (A) for which the system has no solution, infinitely many solutions, and a unique solution in linear Algebra [duplicate]

I really couldn't find the answer no matter how i tried Plz Help when I tried to solve it i got a really big numbers like a^6 ..etc' Okay what I did with this question is solving it by reducing the ...
0
votes
0answers
104 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
2answers
24 views

Is there a formula for finding the series of numbers based on an average.

So I am working on a program that does a scrolling effect. the image is 1200pixels wide, and each time it scrolls, it should move an average of 2.67 pixels. However I am using a function that does not ...
2
votes
1answer
63 views

Vector optimization with set constraint

This is a more generalized form of a previous unanswered question, from which I've removed all the content that wasn't relevant to the actual problem. I have a minimization problem of the form $$ ...
3
votes
1answer
55 views

Linear Algebra quesion

$A^{-1} - \lambda A = B^{-1} - \lambda B - \alpha v v^T$ $A, B \in S^n_+$; $v \in R^n$; $\lambda, \alpha \in R_+$. Can we solve A in term of other variables?
3
votes
1answer
144 views

Necessary and Sufficient conditions for convergence of matrix iterations

I need some help figuring out how to go about the iteration part of the problem...I don't really know where to start. If someone can please help take me through it that would be greatly appreciated. ...
0
votes
1answer
62 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
78 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
243 views

Determinant of circulant matrix

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
1answer
11k 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
39 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
46 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
32 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
72 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
65 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
59 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
88 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
99 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
212 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
57 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
201 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
94 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
395 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
51 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 ...
2
votes
1answer
133 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) ...
1
vote
1answer
249 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
77 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
57 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
348 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
1answer
57 views

Numerical Linear Agebra

how to Prove the backward stability of the inner product ? ...
1
vote
2answers
93 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
38 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.
2
votes
1answer
2k 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
77 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
130 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 ...
1
vote
1answer
27 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
76 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
126 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
121 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 ...
2
votes
1answer
105 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 ...
1
vote
2answers
194 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
261 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 ...
1
vote
1answer
229 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
167 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
36 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 ...
5
votes
4answers
845 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
57 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 ...