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

learn more… | top users | synonyms

0
votes
1answer
56 views

Rate of Convergence of Generalized Iterative Method

Consider the generalized iterative method for finding polynomial roots: $z_{k+1}=z_k +d\frac{(1/p)^{(d-1)}(z_k)}{(1/p)^{(d)}(z_k)}$ where d is a positive integer. Note that Newton's Method is a ...
2
votes
3answers
98 views

properties of positive definite matrix

If $A$ is a symmetric positive definite matrix can we conclude $A^{n}$ is positive define too? Why? For example for $n=2$: $x^{T}(AA)x=x^{T}(AA^{T})x=(x^{T}A)^2>0$; for $n>2$?
0
votes
1answer
40 views

function of matrix and eigen values

I want to calculate exp(A), A is matrix, with numann series. is this series depend of matrix's eigen values? for example if it's eigen values are large, is numann series useful for this function?
0
votes
1answer
64 views

Differences between methods for solving linear equation system

I have a huge linear equation system in this form: F=K.Δ as usual form of problems in the finite element method, where the F vector and K are known and Δ vector is unknown. There are several ...
1
vote
1answer
167 views

Need matlab help to construct a numerical example for solving system of linear equation for random matrices

I am reading this paper(page 183). In this paper the iterative methods for computing some solution of the general restricted linear equations \begin{eqnarray} Ax = b, ~~~~ x\in R(A^{k})~~~~ b\in ...
1
vote
1answer
53 views

most efficient way to find distinct complimenting subspaces over a finite field

Let $V$ be a $n$-dimensional vector spaoce over $\mathbb{F}_p$ and let $W$ be a $k$-dimensional subspace. What's the most efficient way to algorithmically write down a basis for each distinct ...
3
votes
1answer
84 views

Understanding higher order SVD

Can someone explain the singular value decomposition of a tensor (maybe a 3 dimensional matrix) with an example? It is intuitively difficult to the get the meaning from just the formulas. On a ...
0
votes
2answers
56 views

A linear programming to obtain “canonical basis of convex cone”

In my research a I need to solve the linear equation (getting its null space) under some constraints. The matrix is given below: The constraints shall be (x1...x[16]>0, x[17]...x[20] arbitary...) ...
1
vote
1answer
55 views

Proof involving Gauss–Seidel method.

I've got a symmetric positive definite matrix $A$ that I decompose into $A=U+R$ where $U$ is the upper triangular portion of $A$ including the diagonal and $R$ is $A-U$. I've shown that $$x^TAx = ...
-1
votes
1answer
35 views

Find the equation to movement with a middle point locked

I have this scenario: One particle has to go from $0$ point to $y$ point in $1$ sec. The particle needs to start moving at time $0$ ($time=0sec$), and to go accelerating until the middle of time ...
1
vote
1answer
71 views

a conjugate gradients result for eigenvalue estimates

Consider the not preconditioned CG-method for a linear system $Ax=b$. Define $\beta_j = \frac{(r_{j+1},r_{j+1})}{(r_j,r_j)}$ and $\alpha_j=\frac{(r_j,r_j)}{(Ap_j,p_j)}$, where $(x,y) = y^Tx$ denotes ...
0
votes
1answer
30 views

Conditioning considerations in least square solutions via the normal equations

I'm a little unsure about how to classify conditioning issues with solving least squares equations via the normal equations approach. I'm hoping to get verification that what I say below is correct, ...
0
votes
0answers
56 views

Cholesky decomposition using Newton-Raphson

Hi I'm trying to do an alternative algorithm for the Cholesky factorization, which factorizes a symmetric pos. def. matrix $A=R^TR$ where $R$ is upper triangular. I'm curious what happens if you solve ...
3
votes
1answer
59 views

Solve Ax = b, but I have a function that implements A

I have an overdetermined linear system $Ax = b$. I need to choose an $x$. $x$ has about 100 elements in it. If I had the matrix $A$, I would set x equal $A^\dagger b$, the pseudoinverse of $A$ ...
1
vote
1answer
232 views

cube root of positive definite matrix

Suppose that $A$ is a real symmetric positive definite $20\times 20$ matrix with condition number $\kappa\le 1000$. I want to solve the system of linear equations $$A^{1/3}x=b$$ with $10$-digit ...
1
vote
0answers
62 views

Solving for A in the system Ax = 0

Consider the system of linear equations $A x = 0$ where $A$ is a $K \times M$ matrix of reals and $x$ is an $M \times 1$ vector of reals. The matrix $A$ is unknown but we can generate $x$s that ...
0
votes
0answers
26 views

only calculate diagonal of cholesky decomposition

I have a massive matrix $A$ that I can't hold entirely in memory, but it is possible to easily calculate individual entries ($A(i,j)$). I'm only interested in calculating the diagonal entries of the ...
0
votes
0answers
51 views

is 'chasing the bulge' in the implicit QR algorithm exactly the same as reducing a general matrix to hessenberg form?

When performing the implicit QR algorithm, there's a part where you 'chase the bulge' down the diagonal. While it may not necessarily be numerically or computation-time equivalent, is that ...
0
votes
0answers
25 views

How to minimize the peak value of this matrix multiplication?

What range or value of $\theta$ will minimize the peak value of $Y $? $$ Y = \begin{bmatrix} 1+j & 2+j & 3+j & 4+j \\ -4-j & -3-j & ...
1
vote
0answers
25 views

The least-squares solution for interval data

I would like to solve the least-squares for $\mathbf{Ax} = \mathbf{y}$ with some values in $\mathbf{A}$ and also in $\mathbf{y}$ are interval-valued numbers. In a more detail, e.g.,: $$ ...
1
vote
4answers
103 views

Proof $\langle Ax,y\rangle = \langle x,A^*y\rangle$ when $A$ Hermitian

I was trying to understand a proof of why a Hermitian $A$ matrix has its eigenvectors orthogonal. As part of the proof they state $$\langle Ax,y\rangle = \langle x,A^*y\rangle$$ From which property ...
1
vote
0answers
135 views

Solving linear system of equations using Successive Over-Relaxation

I was solving a system of linear equations with SOR. I used different values of relaxation factor (w) for the different runs. I found that for all w > w' (1 < w' < 2), the error is the result ...
1
vote
0answers
98 views

Orthogonal Procrustes Problem

The classical orthogonal Procrustes problem concerns finding the matrix $\Omega$ which minimizes $||A\Omega-B||_{F}$ subject to $\Omega'\Omega=I$, with A and B known matrices. Let A be the identity. I ...
0
votes
1answer
106 views

Solving Poisson Equation Finite-difference using maple

How do I solving Poisson Equation Finite-difference using maple consider Poisson equation $$\frac{\partial^2u}{\partial x^2} (x,y)+ \frac{\partial^2u}{\partial y^2} (x,y) = x*e^y$$ $0<x<2$ ...
4
votes
1answer
109 views

QR factorization of a special structured matrix

A friend asked me the following interesting question: Let $$A = \begin{bmatrix} R \\ \xi{\rm I} \end{bmatrix},$$ where $R \in \mathbb{R}^{n \times n}$ is an upper triangular and ${\rm ...
0
votes
0answers
121 views

when fixed Point Iteration does not converge?

I want to solve a nonlinear system with the fixed point iteration method. I have initial condition,and the answer is known. By using this method the answer converges very slowly about 1000 iteration ...
0
votes
1answer
16 views

Are Similar Matrices and Unitary Property related?

Recall that 2 matrices $A, B\in R^{n,n}$ are similar if there exists a matrix $P$ such that $A=P^{-1}BP$. In this case is $P$ always orthogonal?
0
votes
1answer
59 views

Find upper Hessenberg by Householder transformation

I have a matrix that looks like this: $$ \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \epsilon & 0 & 0 & 0 \\ ...
2
votes
1answer
53 views

Show that every operator norm is consistent

Is the following a correct way to show that operator norms are consistent? $$ \|AB\|=\max_{Bx \ne 0}\frac{\|ABx\|_\alpha }{\|x\|_\alpha} =\max_{ Bx\ne 0}\frac{\|ABx\|_\alpha}{\|Bx\|_\alpha} ...
3
votes
1answer
93 views

Computational cost, power method and page rank

When solving the PageRank problem for $n$ web pages, it is necessary to find a solution of the eigenvector equation $$(fM)*p = p,$$ where $$fM = dM + (1 - d)Z$$ $$Z =\frac{1}{n}*ee^T$$ $$e =[1, 1, ...
3
votes
2answers
78 views

Proof that $(\alpha I - A)$ invertible if $\alpha > \rho(A)$

I want to proof that for $A \in \mathbb{R}^{n \times n}$ with $a_{ij}\geq 0, \forall i,j=1,...,n$: \begin{align} (\alpha I - A) \text{ is invertible if } \alpha > \rho(A) \end{align} where ...
2
votes
1answer
72 views

Something about Gram-Schmidt Projections

Recently I'm reading the book Numerical Linear Algebra and I have a problem in Lecture 8, Gram-Schmidt Orthogonalization. The following text is from the book. Let $A\in\mathbb{C}^{m\times n}$, ...
0
votes
0answers
52 views

How to solve a divergent linear system using iterative methods?

I have a matrix A which is symmetric and non-diagonal dominant. I tried to use Jacobi/Gauss-Seidel/SOR to solve it but it diverges. Is there any mechanism to condition the matrix for convergence ...
2
votes
0answers
65 views

Finding generalized eigenvalues with linear constraints

I have a generalized eigenvalue problem $$Mx = \lambda Bx$$ with the additional constraint that $Cx=0$, where $M$ and $B$ are positive-definite and $C$ is a sparse and rectangular. Is there a simple ...
1
vote
0answers
60 views

$F(x)=Ax+b$ is a contraction mapping

I want to proof that $f(x)=Ax+b$ with \begin{align} A = \begin{bmatrix} 0 & -\frac{1}{8} & \frac{1}{4} \\ 0 & \frac{1}{3} & 0 \\ -\frac{1}{2} & -\frac{5}{22} & \frac{3}{4} ...
0
votes
1answer
88 views

Least Square with homogeneous solution!

I've read somewhere that: $x=A^+b+(I-A^+A)Z$ is a solution for $Ax=b$ ,when is doesn't have a particular solution. where $A^+$ indicates the pseudo-inverse and $Z$ is an arbitrary vector!!! I know ...
0
votes
1answer
32 views

Expressing a vector as the best linear combination of “random” vectors

Suppose I have something like: $\vec{v} = \langle 1, 2, 3, 4, 5 \rangle$ and I have a set of vectors (these are all just made up numbers): $\vec{w_1} = \langle 3, 7, -2, -4, 8 \rangle$ $\vec{w_2} ...
3
votes
2answers
97 views

Interesting determinant: Let $A$ be an $n$ by $n$ matrix with entries $a_{i,j}$ given that $a_{i,j}=2$ if $i=j$

Let $A$ be an $n$ by $n$ matrix with entries $a_{i,j}$ given that $a_{i,j}=2$ if $i=j$, $a_{i,j}=1$ if $i-j\equiv\pm2\pmod n$, and $a_{i,j}=0$ otherwise. Find $\det A$. It seems that the ...
1
vote
2answers
43 views

stability function

I have an exercise which asks me to find polynomials $P$ and $Q$ with a degree $2$ that satisfy $$\exp(z)= \dfrac{P(z)}{Q(z)} + O(z^5)\ \text{for} \ z\to 0$$ My question is: Are they actually unique ...
0
votes
0answers
46 views

Find nullspace from one removed column

I have a large, sparse, square matrix $B$ that is full rank, and am going to remove one column from it to get a new matrix $B_{red}$. I also have a matrix $S$ of candidate columns, one of which needs ...
0
votes
1answer
16 views

Question about flipping terms in matrix multiplication in proving that $h(N_n(\mu , K))=\frac{1}{2}\log(2 \pi n)^n |K|$

So in my book, it is written: Let $X_1,X_2,...,X_n$ have a multivariate normal distribution with mean $\mu$ and covariance matrix $K$ and $\textbf{X}=(X_1,X_2,...,X_n)$ The above isn't really ...
1
vote
1answer
34 views

numerical computation without explicitly calculating certain matrices

I have to numerically multiply: $A^{-1} B A$ where B is a diagonal square matrix, and A is symmetric. A is calculated from multiplying two non-square matrices, $A = XX^T$ I know B and X, and A and ...
8
votes
2answers
214 views

Advice in Bachelor Degree

First of all, I´m very sorry for my bad english, especially writing. Ok, for differents problems i´m studing a Bachelor degree in Mathematics. These degree is online. Now, the problem with my school ...
1
vote
1answer
274 views

Jordan Canonical form 2x2 matrix

Compute the Jordan Canonical form of A = $\begin{bmatrix}i & 1\\1 & -1\end{bmatrix}$. My (feeble) attempt: After I compute the characteristic polynomial, which gives me $x^2=0$, the ...
2
votes
0answers
22 views

Nontrivial Matrix-estimate

I try to proof the following estimate: \begin{align} h' W^{-1} H W^{-1} h \geq c h' H h \qquad c>0, \qquad\qquad (1) \end{align} where $h\in\mathbb{R}^{K-1}$ and ...
0
votes
1answer
48 views

Combine 2 sparse QR factorizations

I have sparse matrix $A_1$ which is size $m_1 \times n$ and another sparse matrix $A_2$ which is size $m_2 \times n$, where $m_1 < n$ and $m_2 \leq n$ and plan on stacking them to make a sparse ...
0
votes
1answer
27 views

Set up for matrix solutions

I've haven't touched linear algebra in a while so I'm sorry if this seems simple but I did a google search and I am still confused. I have to find a solution to the following set of equations: ...
1
vote
1answer
45 views

$l_1$ Matrix Norm Inequality

I am independently studying Numerical Analysis and came upon the following question: $l_1$ vector norm $||x_1||$ is defined as $||x_1||=\sum|x_i|$. How can we show that for the natural matrix ...
1
vote
1answer
115 views

Richardson Iteration

Given the Richardson Iteration, $x_{n+1} = x_n + \alpha(b-Ax_n)$ (with $\alpha$ a scalar constant). To which polynomial $p(A)$ at step $n$ does this iteration correspond to? My first idea ...
0
votes
1answer
47 views

Generalized minimal residuals: eigenvalues and sets of functions

Can someone help me on this exercise (2 parts)? Thanks! Suppose that $S \subseteq \mathbb{C}$ is a set whose convex hull contains $0$ in it's interior (so $S$ is contained in no half-plane ...