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

learn more… | top users | synonyms

0
votes
0answers
3 views

Error bounds for solution of system of linear equations when coefficients are uncertain

I have a square system $Ax=b$ and would like to know how much the solution $x$ can change when I change the coefficient matrix $A$. I've stumbled upon the condition number, but this seems to apply ...
4
votes
1answer
51 views

What mathematics topics pertain more towards applied mathematics?

I'm entering my second year of undergrad (majoring in mathematics), and I've found that I am really bad at Linear Algebra, but very good at Calculus and Differential Equations. I'm hoping to venture ...
0
votes
1answer
28 views

solve nonlinear system of equation numerically

solve the following system of equations numerically $$2x+2y - e^{xy} = 0$$ $$x^3 + y - xy^3 = 1$$ I'm also asked to solve analytically but I'm pretty sure the closed form solution doesn't exist ...
1
vote
1answer
16 views

Improving the performance of eigs for a large spd Problem

I have two large (think around $100.000\times 100.000$), sparse, real symmetric and positive definite matrices $A$ and $B$ and I want to find the smallest generalized eigenvalue $$Ax = \lambda_{\min} ...
2
votes
0answers
26 views

Number of Arithmetic Operations in Gaussian-elimination/Gauss-Jordan Hybrid Method for Solving Linear Systems

I am stucked at this problem from the book Numerical Analysis 8-th Edition (Burden) (Exercise 6.1.16) : Consider the following Gaussian-elimination/Gauss-Jordan hybrid method for solving linear ...
0
votes
1answer
21 views

Stability of (floating point) computed variance

Homework Question from Accuracy and Stability of Numerical Algorithms, 2nd Edition, by Nicholas J. Higham, page 33: So every time we store an number and do a operation, we introduce an error bounded ...
0
votes
0answers
16 views

What are some possible reasons for a large condition number?

For this question, please assume that I am talking about the condition number with respect to the spectral norm. That is, $\kappa_2(A) = \|A\|_2\|A^{-1}\|_2 = \frac{\sigma_{max}(A)}{\sigma_{min}(A)}$. ...
0
votes
0answers
9 views

Proof of QR Algoirthm Convergence

I am reading Trefthen and Bau and the amount of implicit proof steps are killing me. Can someone explain how the statement of convergence for the "pure" QR Eigenvalue Algorithm (Theorem 28.1) is ...
0
votes
0answers
10 views

how to project optimal parameters on to feasible region

Hi: I'm trying to understand the concept of projection and I created a toy example that might help me to do that. Suppose that I have a non-linear optimization with 3 parameters theta_1, theta_2 and ...
0
votes
0answers
32 views

Parametrization of the $Ax=b, x \geq 0$ domain for Monte-Carlo simulation

I have a linear system, $n=15$, with $6$ constraints. There's no problem finding a single solution or establishing the null space; so I can see the full solution space. But I'm only interested in ...
0
votes
0answers
10 views

Linear Relationship of two equations

if $0.46a = 120b$ and $2.68a = 60b$ The relationship is linear. what does $0b$ equal in terms of $a$? what does $1b$ equal in terms of $a$? A method to work this out would also be nice, I have ...
1
vote
1answer
13 views

Gauss Seidel Iteration for a specific matrix

We seek to solve $Au= f$ via iteration, where $$ A = \left ( \begin{array}{cc} I & S \\ -S^T & I \end{array} \right ) $$ Where $S$ is an arbitrary square matrix in $R^n$ and $I$ is the ...
4
votes
1answer
33 views

LU decomposition for cyclic tridiagonal matrices

It is known that a tridiagonal matrix $$ A = \begin{pmatrix} b_1 & c_1 & 0 & 0 & \dots & 0\\ a_2 & b_2 & c_2 & 0 & \dots & 0\\ 0 & a_3 & b_3 & c_3 ...
1
vote
0answers
35 views

How can I write $\prod\limits_{i = 0}^n {\left( {x - {x_i}} \right)} $ in terms of a polynomial as $\sum\limits_{i = 1}^n {{a_i}{x^n}} $?

How can I write $\prod\limits_{i = 0}^n {\left( {x - {x_i}} \right)} $ in terms of a polynomial as $\sum\limits_{i = 1}^n {{a_i}{x^n}} $? In the other words, is there a way to write $a_i$ in terms of ...
0
votes
0answers
40 views

Most stable algorithm to solve a system of linear equations?

I am doing some image processing involving solving a system of linear equations. I am getting some errors and bits of the image looks corrupted. I would like to know what is the most stable way to ...
1
vote
1answer
40 views

Strange behavior with coordinate transformation of square and quadrilateral

I am trying to map coordinates from a quadrilateral to a square. The coordinates are square: $(500,900)(599,900)(599,999)(500,999)$ quad: $(454,945)(558,951)(598,999)(499,999)$ where the $i^{th}$ ...
0
votes
1answer
21 views

Notation regarding linearization near equilibrium point of dynamical system

Suppose we have $\frac{dx}{dt} = \dot{x} = f(x)$ with equilibrium point $x_e$ such that $f(x_e) = 0$. Then for the linearized approximation of the differential equation near $x_e$ we hope to use the ...
1
vote
1answer
30 views

How to determine positive or negative definite of a bordered Hessian ?

I want to determine the minimization result I get using Lagrange Multiplier method is a local minimum by determining whether the Bordered Hessian is positive definite or negative definite.(Hopefully ...
0
votes
1answer
46 views

Bound on the difference of matrix diagonals

I have two diagonal matrices $\Lambda,\hat{\Lambda}\in\mathbb{R}^{n\times n}$ with non-negative diagonal elements. And I have two matrices $W,\hat{W}\in\mathbb{R}^{m\times n}$, with $m\geq n$, each ...
-8
votes
0answers
34 views

maths and maths oriental doubt [duplicate]

What is 0 power 0 ? And explain verifyly.,
0
votes
0answers
14 views

What is the source of the error in the Sherman-Morrison formula application?

The Sherman-Morrison formula results in small errors in relation to the standard matrix inverse operation after each application, as shown here. From what I understand, the Sherman-Morrison identity ...
3
votes
2answers
90 views

Computing $\operatorname{Tr} \bigl( \bigl( (A+I )^{-1} \bigr)^2\bigr)$

Suppose that $A \in \mathbb{R}^{n \times n}$ is a symmetric positive semi-definite matrix such that $\operatorname{Tr}(A)\le n$. I want a lower bound on the following quantity $$\operatorname{Tr} ...
0
votes
1answer
23 views

Product rule in discrete derivative in finite difference scheme.

Suppose we are on real line and I want to discretize the usual derivative operator. Take a smooth function $u$ and step size $h$. Then I could define $$ \Delta_+u(i) = \frac{u(i+1)-u(i)}{h} $$ as the ...
1
vote
2answers
40 views

Linear combination of basis function in logarithm space. Is it possible?

I have a function $f(x)$. As theory said that it can represent by linear combination of basis functions such as $$f(x)=\sum_{i=1}^{N}\alpha_ig_i(x)$$ where $\alpha$ is coefficient and $g(.)$ is basis ...
1
vote
0answers
15 views

Conditional expectation of a set of Gaussian variables

I was wondering if there is an efficient way to compute the conditional expectation of every element in a Gaussian random vector ? Specifically: For a pair of Gaussian random variables $[x,y]$, the ...
0
votes
1answer
29 views

Gauß-Newton Example with one variable

$$T=f(t):=2 \alpha + \sqrt{\alpha^2+t^2}$$ To estimate $\alpha$ we got the measured values $T_i$ for $t_i$. Formulate the curve fitting problem and show each step in the Gauss-Newton algorithm. My ...
3
votes
3answers
57 views

Is this a circulant matrix?

It's symmetric, but I'm not sure whether it is circulant. In a question that I had asked on MSE a couple of weeks ago, several commenters had said that this is a circulant matrix, and to study the ...
2
votes
1answer
37 views

Choose $\rho$ such that $\rho$-norm minimizes the matrix condition number

I'm solving questions from am exam that I failed miserably, so I would love it if someone can take a look at my proof and make sure I'm not making any gross mistakes. Question Let $A$ a symmetric ...
0
votes
1answer
31 views

Automatic way to have a good initial guess for the iterative methods ( newton method) and for high dimensional nonlinear problems

I am solving a variety class of nonlinear systems where I need to reduce in optimal manner the number of iterations of either the newton or modified newton method. For this end I am trying to figure ...
0
votes
0answers
33 views

How to calculate $det(X^T X)$ efficiently, update one column of X each time

$X_{1} = (A, b)$, where $X_{1}$ is a $n\times p$ matrix, $A$ is a $n\times (p-1)$ and $b$ is $n\times1$. First calculate $\det(X_{1}^T X_{1})$, then update $b$ with $c$, st. $X_{2} = (A, c)$ and ...
1
vote
1answer
57 views

How to numerically solve the Poisson equation given Neumann boundary conditions?

I want to solve the Poisson equation on a 2D domain given Neumann-type boundary conditions: The PDE: \begin{equation} \nabla^2 \; u(r,\theta) \;=\; f(r,\theta) \end{equation} The boundary ...
7
votes
0answers
67 views

How to solve linear system of form $(A \otimes B + C^{T}C)x = b$ when $A \otimes B$ is too large to compute?

For the given linear system: $$(A \otimes B + C^{T}C)x = b$$ where $\otimes$ is the Kronecker product, $A$ and $B$ are dense and symmetric positive-definite, and $C^{T}C$ is a sparse symmetric block ...
0
votes
1answer
24 views

Can adding one column to a matrix increase its rank by more than one

Knowing the answer to this question would help me answer the following question: $A$ is an $m\times n$ matrix with $m>n$, and let $A=\hat{Q}\hat{R}$ be a reduced QR factorization. Suppose ...
0
votes
2answers
31 views

Rewrite matrix equation as a quadratic programming problem

Given real-matrix $X_{n\times p}$ how can the problem of minimizing $Tr(X^TA_{n\times n}X)$ under the constraint $Tr(X^TC)=\phi$ be posed as a standard convex quadratic program given by the form: ...
0
votes
0answers
26 views

Efficient method to compute grand sum of a Vandermonde matrix?

Is there a computationally efficient method to calculate the sum of all elements (grand sum) of a Vandermonde matrix? Each row can be quickly calculated using the formula for a geometric progression. ...
2
votes
0answers
50 views

Fastest way to find linearly independent columns of a matrix

Given a rectangular matrix $X$ of size $n\times m$ with $m>n$, what is the fastest way to find the linearly independent coloums. Robust methods like SVD or RRQR decompostion have complexity of ...
0
votes
0answers
15 views

Evaluating a quadratic form with an inverse of a sparse PD matrix, comparison between using the inverse vs using a Cholseky decomposition

I have the following quadratic form I need to evaluate: $x^T A^{-1} y$, where $A$ is a sparse positive definite matrix, $x, y$ are sparse vectors. Now assume that I am given for free both $A^{-1}$ ...
2
votes
2answers
38 views

Differential equation for finding closest point on surface.

Inspired by this question I got to think about a more general case. Say I have any discretized surface and want to find closest point from each point outside of surface to the surface. Say that I can ...
1
vote
0answers
26 views

How to apply Runge-Kutta to an implicit scheme?

I see there are some differences in the solution as I increase the resolution of my grid. I'm using Operator Splitting to solve Diffusion Reaction equation \begin{equation} \frac{\partial ...
2
votes
3answers
75 views

Symmetry Of Differentiation Matrix

I have a problem computing numerically the eigenvalues of Laplace-Beltrami operator. I use meshfree Radial Basis Functions (RBF) approach to construct differentiation matrix $D$. Testing my code on ...
1
vote
0answers
11 views

Relationship between QR and LU factorization

Both algorithm return very similar results in terms of having a upper/right triangular matrix as one of the factors. What is the relationship between Q and L, and between R and U? What is the ...
0
votes
1answer
48 views

The MU-puzzle from GEB

The MUI system only uses the three letters M,U,and I to make strings. The system has four rules that allow you to make new strings out of existing strings by manipulating them. Rules 1 and 2 lengthen ...
1
vote
2answers
35 views

How to solve the system of equations $\{10^{-4}x_1+x_2=1, x_1+x_2=2\}$ using finite precision arithmetic with three significant figures?

Consider the following two equations: $10^{-4}x_1+x_2=1$ $x_1+x_2=2$ Solve using Gaussian Elimination using finite precision arithmetic with three significant figures. I'm a little ...
1
vote
1answer
34 views

Error bound of midpoint rules with unbounded second derivative

It is well known that error bound of midpoint rule for function $f[a,b]$ is given by $$ E\leq K\frac{(b-a)^3}{24 n^2} $$ where $|f(x)''\leq K|$ and $n$ is the number of time steps. if second ...
0
votes
0answers
17 views

Approximation of Mahalanobis distance

If $A$ is a symmetric positive definite $n\times n$ matrix then the square Mahalanobis norm of a vector $v\in \mathbb{R}^n$ is given by $$\lVert v \rVert_A^2=v^t A^{-1} v.$$ Now I have a situation ...
0
votes
0answers
15 views

Proof that Householder Triangularization for QR is backward stable

How do you prove that QR factorization via Householder Triangularization is backward stable? Theorem 16.1 (From Trefethen and Bau): Let the $QR$ factorization of a matrix $A$ be computed by ...
1
vote
0answers
23 views

How can I solve this specific set of equations?

Here are the equations: $$\sum_{k = 1}^n i_k + Y_n u_n = J \quad \quad (1)$$ $$i_1 + Y(u_1 - u_2) = J \quad \quad (2)$$ $$i_k - Y(u_{k - 1} -2u_{k} + u_{k + 1}) = 0, \quad \quad k = 2, ..., n - 2 ...
0
votes
0answers
22 views

Linear algebra <perhaps an application of Gordan' Theorem>

Question. Let $a_1,...a_n\in\{0,1,-1\}^m$ and $\sum a_i=(1,...,1)$. Is there a permutation $\tau$ of $\{1,...,n\}$ Such that for each $k\in \{1,...,n\}$ the vector $\sum_{i=1}^k a_{\tau (i)}$ has ...
1
vote
0answers
42 views

Numerically stable SVD

In this question regarding SVD, it is explained why eigen decomposition of $ A^tA $ is not numerically stable compared to "direct SVD algorithms". Since the former is the algorithm I'm most familiar ...
2
votes
0answers
17 views

Reference request for finite difference method

I am trying to use finite difference method to solve the minimizing problem $$ J[u]=\min_{u\in BV(Q)}\{\|u-f\|_{L^1(Q)}+|u|_{BV(Q)}\} $$ where $Q=(0,1)\times (0,1)$ is a uint square and ...