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

learn more… | top users | synonyms

0
votes
1answer
10 views

Condition number of preconditioned system

Suppose we are solving an ill-conditioned system $Ax = b$, and we are trying to solve it using preconditioned technique. Given $\kappa (T)\approx \kappa(A)$, where $\kappa(A)$ is condition number of ...
3
votes
2answers
57 views

Efficiently solving many sets of linear equations without inversion or factorization

Suppose I have the normal set of linear equations $Ax = b$. If I can store and manipulate $A$ I have a variety of techniques available to me such as inversion, factorization, or an iterative method. ...
0
votes
1answer
11 views

Reference that Explains Preconditioning

I would like to understand Preconditioning techniques and why they work. Could someone provide a good reference for this type of information?
0
votes
0answers
15 views

Compute the condition number of the matrix and show for what $\Delta x$ it is singular

Given the laplacian $N \times N$ matrix \begin{align*} A=\frac{1}{(\Delta x)^2}\begin{pmatrix} 2&-1& & &\\ -1&2&-1& &\\ &\ddots&\ddots&\ddots&\\ ...
2
votes
1answer
48 views
+100

Detecting singular system during Cholesky resolution

I am solving small linear systems with a symmetric positive matrix by the method of Cholesky, without pivoting. "Bad" matrices are detected when you take the square root of a diagonal element, which ...
0
votes
1answer
19 views

Nearest singular matrix

Let the SVD of $A \in \mathbb R^{{n}*{n}} $ be given as $A=\sum_{i=0}^n \sigma_{i}u_{i}v_{i}^{T}$ where $\sigma_{1}\gt \sigma_{2}>{...}>\sigma_{n-1}=\sigma_{n}>0 $ Compute a matrix $B$ such ...
1
vote
1answer
2k views

Condition number for non-square matrix?

From what I understand the condition number of a non-square matrix A is its largest singular value divided by its smallest nonzero singular value: $\kappa(A) = \sigma_1/\sigma_n $. Where ...
2
votes
2answers
26 views

Reciprocal of a quadratic form

I am working with an expression of the form $$ \frac{x^TAx}{{x^TBx}}$$ and would like to simplify it. I understand that vectors do not have inverses, but viewing the bottom number as a 1 by 1 matrix, ...
6
votes
1answer
3k views

Block inverse of symmetric matrices

Let us assume we have a symmetric $n \times n$ matrix $A$. We know the inverse of $A$. Let us say that we now add one column and one row to $A$, in a way that the resulting matrix ($B$) is an $(n+1) ...
0
votes
1answer
26 views

How to find matrix $A$ from the relation: $A\times (A^TA)^{-1}\times A^T = B$

Kindly help me in the following: I have two Matrices, $A$ of size $(n\times m)$; and $B$ of size $(n\times n)$, where $n>m$. $A$ is unknown, but $B$ is known. $(A^TA)$ is invertible $B$ is ...
0
votes
3answers
39 views

Real problems solved with systems

Can anybody tell me where can I find some REAL problems (i.e. form real life) that can be solved using a 3x3 system of linear equations? Or, can anybody give me an example? A solution could be a ...
0
votes
2answers
22 views

solving an XOR matrix

I'm working on a somewhat-unique linear algebra problem arising from XORing files together in order to encode them, and then figuring out how to subsequently recreate the original files from the ...
2
votes
2answers
42 views

Show that the matrix $AA^T+\alpha I$ is positive definite, where $\alpha >0$ and $A$ is an $m\times n$ real matrix.

Show that the matrix $AA^T+\alpha I$ is positive definite, where $\alpha >0$ and $A$ is an $m\times n$ real matrix. So I need to show that $x^T(AA^T+\alpha I)x>0$ for all vectors $x$. I'm ...
1
vote
0answers
22 views

Numerical stability of computational results

Let z be a function of a finite number of variables i.e. z=f(a,b,c,...). If we have the mathematical formula connecting z and the variables, we can determine how the value of z varies with a change ...
1
vote
1answer
18 views

Normal system of the least square method

I'm trying to show the following. $Pa$ is the approximation system of $y$. I want to show that finding the minimmum for the function $$f(a,y)=||Pa-y||_2^2$$ is equivalent to solve the normal system of ...
1
vote
0answers
73 views

Rayleigh quotient ($|r(q)-\lambda|=O(||q-x||_2^2)$ ?)

how to show $|r(q)-\lambda|=O(\|q-x\|_2^2)$ $r(q)=q^*Aq/(q^*q)$ and $\lambda$ is an eigenvalue, $A$ is a Hermitian matrix. $x$ is the unit eigenvector corresponding to $\lambda$. and $q$ is a unit ...
0
votes
0answers
9 views

Determinants using Row Reduction replacement

I am aware replacement does not affect the value of determinant when doing a row reduction. However, I realised there isn't a good explanation on how to handle different forms of replacement when ...
0
votes
1answer
15 views

Number of iterations for Gauss-Seidel

I am having some difficulty understanding the following solved problem: Question: Shouldn't we have $||T||^k_{\infty} ||e^{0}||_{\infty} \leq 10^{-6}$ instead? Where does the $5$ come from? And ...
1
vote
1answer
837 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 ...
-5
votes
0answers
19 views

SYMMETRIC OVER RELAXATION IN C [closed]

Can anybody give me a c-program for successive over relaxation?
-1
votes
0answers
8 views

Numerical Solution of Matrix with Diagonal Elements of Highly Varying Order

I am trying to solve following set of equations: A(i,i-2)*u(i-2) + A(i,i-1)*u(i-1) + (A(i,i)+β(i) )*u(i) + A(i,i+1)*u(i+1) + A(i,i+2)*u(i+2)= B(i) + β(i) where i=1:1000000 If values of β ...
2
votes
2answers
495 views

Space spanned by matrices

I have a set of $5$ by $5 $matrices, $M_1,M_2,...,M_{19} ,M_{20}$. I want to try to find a basis from this set and also to find relationships between these matrices. This is how I think I should ...
1
vote
2answers
19 views

Turning certain elements of a Matrix to zero through multiplication

Good evening, I apologize for the somewhat dumb question, I have to confess, Linear Algebra is not my strong suit. Secondly, the aim of this question is to apply this process to Excel - using VBA. ...
0
votes
0answers
20 views

Given a triangular matrix $T$, can we find an upper bound for $\| |T^{-1}||T|\|$?

Given a triangular matrix $T$, can we find an upper bound for $\| |T^{-1}||T|\|$, where $|T| =|[T_{ij}]| = [|T_{ij}|]$ ?
1
vote
1answer
26 views

Determining the most appropriate set of eigenmodes for a modal decomposition of an experimental data set

I have a complex vector of the transverse amplitude and phase distribution of a laser beam, derived from experimental data. When modelling these field distributions, ordinarily the eigenmodes of the ...
0
votes
0answers
35 views

What are useful mappings (operators) in image reconstruction

I'd like to ask the technician mates to provide some information regarding mappings and image reconstruction operators. Please, if possible, provide some articles and helpful discussions about useful ...
1
vote
0answers
39 views

Why is it difficult (and not precise) to compute the rank of large matrix numerically?

I have a general question. I have a large square matrix ($n> 1000$) and it is needed to compute the rank of this matrix. I am reading that the computation of the rank for large matrices, can make ...
0
votes
1answer
15 views

Proof with an Artificial Power Method

Suppose $A$ is $m\times m$ and has a complete set of orthonormal eigenvectors, $q_1, \ldots , q_m$, and with corresponding eigenvalues $\lambda_1,\ldots , \lambda_m$. Assume that the ordering is such ...
1
vote
1answer
33 views

Is an orthogonal matrix necessarily a permutation matrix?

Is an orthogonal matrix necessarily a permutation matrix? I believe the answer is no as a permutation matrix is a special case of an orthogonal matrix, but I am having a trouble finding a ...
1
vote
2answers
13 views

Robustly map rotation matrix to axis-angle

The Wikipedia article for rotation matrix gives the following formula for converting from rotation matrix, $Q$, to axis-angle, $u$ and $\theta$: $$ \begin{align} x &= Q_{zy} - Q_{yz} \\ y &= ...
0
votes
0answers
10 views

Error estimate in iterative refinement for solving a linear system

The iterative refinement can be illustrated as follows: given an approximate solution $\hat{x}$ of the system $Ax = b$, at the $n^{th}$ step of the refinement, $r = b- A\hat{x}^{(n)}$, Solve ...
0
votes
0answers
25 views

In practice what is (modified) Gram Schmidt used for?

Modified Gram-Schmidt is known to be numerically less stable than methods like Householder orthogonalization and also not quite as fast at approximately $2mn^2$ flops. So in practice do we ever use ...
1
vote
1answer
60 views

why do we say SVD can handle singular matrx when doing least square? Comparison of SVD and QR decomposition

I don't quite understand why we say that QR decomposition doesn't handle singular matrix, while SVD does when they are used for least square problem? My example in Matlab seems to support the ...
0
votes
1answer
24 views

on a characterization of convergent matrices

Let $A\in \mathbb R^{n\times n}$ a matrix. It's known that the following statements are equivalent: 1) $A$ is convergent, namely $\lim_{k\to\infty}(A^k)_{ij}=0$ 2) $\lim_{k\to\infty}||A^k||=0$ for ...
1
vote
1answer
24 views

eigenvalues lesser than 1 implies affine maps are eventually contractive

Consider $(\mathbb R^n,d)$ where $d$ is the Euclidean metric. A map $w:\mathbb R^n\to \mathbb R^n$ is said $\textbf{contractive}$ if there exists $0<s<1$ such that for every $x,y\in \mathbb R^n$ ...
1
vote
0answers
24 views

Eigenvalue equation and the diffusion equation

I am running some finite-element software on Matlab that generates solutions to the diffusion equation over a punctured, rectangular domain. This is the same as the $k \times k$ matrix system ...
0
votes
1answer
27 views

Power Method: Showing convergence to dominant eigenvector

What follows is taken from Numerical Analysis, by R. Burden and D. Faires: Let $A\in \mathbb{R}^{n\times n}$, with eigenvalues $\lambda_1,\dots,\lambda_n$ such that $|\lambda_1|>|\lambda_2|\ge ...
0
votes
0answers
26 views

Finding eigenvectors of the Laplacian operator

I am running some finite-element software on Matlab that generates solutions to the diffusion equation over a punctured, rectangular domain. This is the same as the $k \times k$ matrix system ...
0
votes
1answer
15 views

Diagonalizing a Block Matrix with one non-zero Block column

I am trying to diagonalize $(M+N) \times (M+N)$ matrix $G\Gamma_LG^\dagger\Gamma_R $$ = \left(\begin{array}{cc} 0_{M\times M} & A_{M\times N} \\ 0_{N\times M} & B_{N\times N} ...
12
votes
2answers
82 views

How to get the SVD of $2AA^T-\operatorname{diag}(AA^T)$ given $A$ and its SVD $A=USV^T$?

Given a matrix $A\in R^{n\times d}$ with $n>d$, and we can have some fast ways to (approximately) calculate the SVD (Singular Value Decomposition) of $A$, saying $A=USV^T$ and $V\in R^{d\times d}$. ...
4
votes
1answer
46 views

eigenvalues lesser than $1$ implies contractive map

Consider $(\mathbb R^n,d)$ where $d$ is the Euclidean metric. A map $w:\mathbb R^n\to \mathbb R^n$ is said contractive if there exists $0<s<1$ such that for every $x,y\in \mathbb R^n$ we have ...
4
votes
1answer
111 views

Best way to solve specific block-tridiagonal linear system (10000x10000 and larger)

To provide more context, this system came from energy balance equation on a mesh with (n,m) nodes in each direction. It's a linear system that looks like this (size of system in blocks n = 4, size of ...
0
votes
0answers
11 views

SVD of Cholesky Factor

I am working through the book Fundamentals of Matrix Computations by David Watkins, and I ran into this one and it's stumping me. In my head, I understand the basic premise of it. However, I can't ...
0
votes
0answers
12 views

SVD Transpose Equations

$$Av_i= \begin{cases} \sigma_iu_i & i = 1, \ldots , r \\ 0 & i = r+1, \ldots , m \end{cases}$$ $$A^Tu_i= \begin{cases} \sigma_iv_i & i = 1, \ldots , r \\ 0 & i = r+1, \ldots , m ...
2
votes
2answers
1k views

Gauss-Seidel method convergence algorithm

From Wikipedia: The convergence properties of the Gauss–Seidel method are dependent on the matrix A. Namely, the procedure is known to converge if either: ...
0
votes
0answers
26 views

Simplifying matrix expressions with LU decomposition?

If $A, B, C$ are $n \times n$ matrices, with $B$ and $C$ nonsingular, and $b$ is a vector of size $n$, how could one determine $$x = B^{-1}(2A + I)(C^{−1} + A)b?$$ I assume the solution has to do with ...
1
vote
0answers
23 views

Spectral relaxation of k-means clustering

I am working on a presentation on Spectral relaxation of k-means clustering (http://papers.nips.cc/paper/1992-spectral-relaxation-for-k-means-clustering.pdf) and I am a bit stuck. I understand ...
2
votes
0answers
19 views

Is it possible to design a strongly stable linear multistep method of order 7 which has stiff decay

I'm studying for a test and I'd like to know is it possible to design a strongly stable linear multistep method of order 7 which has stiff decay. I have no clue to verify the claim. Can anyone give me ...
1
vote
0answers
16 views

Is it possible to construct a consistent unstable one step method of order 2? why?

Is it possible to construct a consistent unstable one step method of order 2? why? I think the answer is no but I have no clue to prove it. Can anyone give me some explanations? Thank you in ...
1
vote
1answer
38 views

Proving Equality of the Induced Matrix Norm

I need to prove that the induced matrix norm satisfies $$\|A\| = \max_{\|x\| = 1} \|Ax\|$$ Here's what I've done so far, and I'm not sure how to make the connection. By definition, $$\|A\| = ...