Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [numerical-linear-algebra]

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

0
votes
1answer
37 views

Find the linear dependence using the rotation matrix

My attempt: The only thing that I know is rotating $[c_1 , c_2 ]^T$ by an angle $\theta$ in the counter-clockwise direction is the same as multiplying the rotation matrix by $[c_1 , c_2 ]^T$. How to ...
2
votes
0answers
13 views

Efficient approach for solving matrix plus diagonal matrix system that varies in time [migrated]

When solving a system of ODEs, as part of a preconditioner, I get the system $(A + D(t))x = b(t)$ where $A$ is a sparse matrix and $D(t)$ is diagonal. I'm currently solving this by taking the LU-...
0
votes
0answers
12 views

scalar triple product for continuous functions

How is the scalar triple product for continuous functions, rather than vectors? Can it also be written using the integral of the product of three continuous functions?
0
votes
1answer
31 views

Big-o notation confused

In error analysis we say the error is of order $\epsilon$ if the error is less than or equal constant multiple of $\epsilon$. The question is: what is the benefit we have if we can multiply by any ...
1
vote
0answers
41 views
+50

Implicit Euler method yields incorrect output - in depth and simple

We are given the system of PDEs $\begin{pmatrix}f_t \\ g_t\end{pmatrix} = i\begin{pmatrix}0 & 1 \\ 1 & 0\end{pmatrix}\begin{pmatrix}f_{xx}\\ g_{xx}\end{pmatrix}+i\begin{pmatrix}3 & -1 \\ -...
0
votes
1answer
21 views

Rewriting product of special rank one updates as a low rank update

I'm trying to improve the speed of the following iteration to calculate $s_k$: $$B_k^{-1} = \Bigg( I + \frac{s_{k}s_{k-1}^T}{||s_{k-1}||^2}\Bigg)...\Bigg(I+ \frac{s_1s_0^T}{||s_0||^2}\Bigg) B_0^{-1}\\...
2
votes
2answers
74 views

How to compute the smallest eigenvalue efficiently? [on hold]

$A$ is a $m \times m$ symmetric PSD matrix whose top $n$ eigenvalues are equal to $1$ and whose remaining $(m-n)$ eigenvalues are zero. Here, $n \ll m$. Let $D$ be a diagonal matrix with all diagonal ...
0
votes
2answers
39 views

Spectral Radius $\leq$ min(1-norm, infinity norm)

How do I prove that the spectral radius of a matrix is less than or equal to the minimum of 1-norm and infinity norm of the matrix? i.e. $$\rho(A) \leq min(||A||_1, ||A||_{\infty})$$ I know the ...
-2
votes
0answers
19 views

Influencer/Impact formula needed [closed]

I am looking for a formula and an explanation of the result that I can deliver to the management, that would show the impact of the result per category on the overall result. Here, the overall target ...
0
votes
1answer
31 views

Condition number of dot product of vectors

I was wondering if anybody knows what is the relative condition number of dot product of vectors and how to compute it. I'm just reading about this stuff, but don't really understand how to compute it....
0
votes
0answers
41 views

complexity of QR decomposition .

Could anyone help me to find the complexity of QR decomposition of matrix $A \in C^{N \times P}$, where $P \leq N$. I am also willing to know the complexity of adding a matrix $A \in C^{N \times N}$ ...
0
votes
1answer
57 views
+100

Is there a fast way to compute the lowest eigenvalue of this symmetric PD matrix in this specific scenario?

Consider $$C = A^H D A + M$$ where $A$ is a $m \times m$ unitary matrix. $D$ is a $m \times m$ diagonal matrix with entries either $0$ or $1$. The number of $1$'s is $n \ll m$. $M$ is a $m \times ...
0
votes
1answer
58 views

Proving an inequality based on condition number.

I was trying to prove this inequality, by taking $K(A) = ||A|| ||A^{-1}||$ and also the error $A(x -\hat{x}) =e$, I am thinking how to get those terms, estimates? any help in ideas to proceed.
0
votes
0answers
33 views

condition number and the norm of inverse

I need to prove that the condition number of the following matrix $A$ with respect to the infinity norm is greater than 20. $$A= \begin{bmatrix} 1 \ \frac{1}{2} \ \ \frac{1}{3} \ \ \frac{1}{4} \ \ \...
0
votes
1answer
32 views

Generating correlated normal vectors with observations

Assume we are given two normally distributed random variables, $X_1$ and $X_2$, with $X_i \sim \mathcal N (0, \sigma_{x_i}^2)$, with correlation coefficient $\rho_x$. Assume further that we need to ...
0
votes
0answers
32 views

Convergence of GMRES

I have a question about the convergence of this upper triangular matrix A in GMRES. $ { \text { let } } \\ { A = \left( \begin{array} { c c } { I } & { Y } \\ { 0 } & { I } \end{array} \...
0
votes
1answer
49 views

Series where every element contains a mean of near elements

I wonder if already exists a solution to this problem: I must calculate the value of every element of a time series (a finite series of numbers) where every element equals the mean of an easily ...
0
votes
0answers
43 views

Difference between R and Q in numbers

I am an ICSE student and I have some problem in mathematics regarding linear inequations. In some examples I have found x $\in$ R and I have also found x $\in$ Q . I know that 'R' means rational ...
0
votes
1answer
18 views

Algorithm to solve systems of first order “triangular” linear difference equations

I have a system of first order linear difference equations, which look like this: \begin{align*} \vec{x_n} = A \vec{x_{n-1}} + \vec{b} \end{align*} Where $A$ is an upper triangular matrix. What ...
2
votes
0answers
42 views

Conditions for solving generalized Sylvester matrix equation XA + BX + CXD = E

In relation with an observation problem I have the matrix equation (1) $XA + BX + CXD = E$ where all the matrices $A$, $B$, $C$, $D$, $E$ can be assumed real, square and known, whereas $X$ is the ...
1
vote
0answers
10 views

How to show Schulz's method converges $Q$-quadratically?

Let $A \in \mathbb{R}^{n \times n}$ be an invertible matrix. Consider the Schulz's method for fast computation of the inverse of $A$ given by: $$ X_{k+1} = X_k + X_k (I -AX_k) $$ where each $X_k \in ...
0
votes
0answers
31 views

Find the norm of the matrix in Gauss-Seidel method

Let's consider the system $$ \begin{cases} 3x_{1}-x_{2}+x_{3} & =5,\\ 2x_{1}+5x_{2}-2x_{3} & =1,\\ 2x_{1}-x_{2}+6x_{3} & =7. \end{cases} $$ The Gauss-Seidel method is an iterative process: ...
0
votes
0answers
24 views

Ratio of the relative error $x$ to the relative error of $b$ and relative error of $A$ ($Ax=b$)

In my HW assignment I was asked to generate random matrix $A$ and $b$ to solve the system $Ax=b$, then I needed to perturb vector $b$ by 1% (call it $\tilde{b})$ first to see how $x$ changes (let it ...
0
votes
0answers
18 views

How to go from left eigenvectors to right eigenvectors?

Somehow I got stuck on this seemingly simple problem. Here it is: Let L be a non-degenerate (no eigenvalue is zero/invertible) implicit linear operator whose k largest real eigenvalues are known, ...
1
vote
1answer
88 views

Simplify this expression for the relative condition number of $f(x,y) := [ x^y, x + y ]^T$

Find the relative condition number of the function $$ f: D := (0, 2] \times \mathbb{R} \to \mathbb{R}, \ (x,y) \mapsto \begin{bmatrix} x^y \\ x + y \end{bmatrix} $$ and use the euclidean norm for ...
0
votes
1answer
51 views

Incremental solution for matrix inverse using Shermann-Morrison in $O(n^2)$

I have been reading a presentation on Value Function Approximation by David Silver (Introduction to Reinforcement Learning Course). On page 43 he finds a solution for linear least squares for an ...
0
votes
0answers
45 views

Find the relative condition number of $f(x,y) := y e^{4x^2}$ with respect to the 1-norm.

Let $f: \mathbb{R} \to \mathbb{R}$ (I guess it's supposed to be $\mathbb{R}^2 \to \mathbb{R}$) be defined by $f(x,y) := y e^{4x^2}$ Find the relative condition number of with respect to the 1-norm. ...
1
vote
1answer
50 views

Factoring a matrix as the product of block triangular and diagonal matrices.

How can I check that the matrix $$K = \left[\begin{array}{c|cc} 1 & 0^{\mathrm T}_m & m \mathbf u^{\mathrm T} \\ \hline 0_m & I_m & I_m \\ m \mathbf u & I_m & O_m \end{array}...
1
vote
0answers
24 views

Lagrange interpolation well-conditioned?

Let $m$ be an integer, let $x_j = \frac{j−1}{m},1 \leq j \leq m.$ Let $y_1, y_2 , . . . , y_m$ be real numbers, and let $p$ denote the polynomial of degree $\leq m − 1$ with $p(x_j ) = y_j$ for $1 \...
1
vote
0answers
17 views

Computational Complexity of A=PLU versus other methods

I am currently trying to understand how to wrap my head around the following problem - Consider solving $AX=B$ for $X$, where $A$ is $n\times n$, and $X$ and $B$ are $n\times m$. There are two ...
0
votes
1answer
51 views

Writing a matrix in an alternative form with a Kronecker product.

I need to express the matrix \begin{equation} \begin{bmatrix} I & A \\ A^T & O \\ \end{bmatrix} \end{equation} where $$A = \begin{bmatrix} m\textbf{u}^T\\ I_m\\ \...
0
votes
1answer
39 views

Inverting a matrix with the same diagonal entries in a particular form

Hi I'm struggling with this inversion and any help would be greatly appreciated. I want to invert the following $\mathbb R^{m\times m}$ matrix \begin{bmatrix} 1 + m & m & \dots &...
1
vote
1answer
46 views

Simplify this expression with divided differences.

The divided differences are defined as follows $$ f[x_i] := f(x_i), \quad f[x_0, \ldots, x_n] := \frac{f[x_1, \ldots, x_n] - f[x_0, \ldots, x_{n - 1}]}{x_n - x_0} \quad \text{for } n \ge 2 $$ For ...
0
votes
0answers
34 views

Least Squares Normal Equations in Explicit Form

I am struggling with the following least squares problem: Find the minimiser x* $\in \mathbb{R}^{m}$ of $$F(\textbf{x})=||\textbf{b}-A\textbf{x}||_2$$ where $A \in \mathbb{R}^{(m+1) \times m}$, $...
-1
votes
0answers
28 views

Accuracy order for linear system which approximate $f''(x) + f(x) = \psi(x)$ using difference equation is $cond(A)\cdot h^2$

I want to show that when approximating $f(x_i)$ , $i\in \{0,1,...,n\}$ when $x_0 = a , x_n=b$ and $x_{i+1} -x_i = h = (b-a)/n$, given the boundary conditions, $f(x_0), f(x_n)$ the second order ...
0
votes
0answers
24 views

Computation of $k$ dominant right singular vectors without SVD computation

I have a maxtrix ${\bf A} \in \mathcal{C}^{m \times n}$, where $m < n$. However, the $m$ and $n$ are large numbers (for eg: m = 50, n = 250). I need to find the $k$ dominant right singular vectors ...
1
vote
2answers
55 views

Solve $\mathop{\arg\max}_{{v \in \mathbb{R}^m, \| v \| = 1}} v^T A A^T v$ with SVD

Let $A \in \mathbb{R}^{m \times n}$ be a matrix with full rank and $m \le n$. How can we solve the problem $$ \mathop{\arg\max}\limits_{\substack{v \in \mathbb{R}^m \\ \| v \| = 1}} v^T A A^T v $$ ...
2
votes
2answers
158 views

Different condition numbers of $\begin{pmatrix} a & b \\ b & c \end{pmatrix}$

Let $a,b,c \in \mathbb{R}$ and $A := \begin{pmatrix} a & b \\ b & c \end{pmatrix}$ and $\det(A) \neq 0$. Find the condition number with respect to the 1-, 2- and $\infty$-norm and discuss ...
0
votes
1answer
33 views
1
vote
1answer
58 views

How can I find partial pivoting matrix $P$ from $PA=LU$ decomposition if we know $A,L,U$?

Assume that we have this equation $$PA=LU$$ Where $A \in \Re^{mxn}$, $L \in \Re^{mxn}$ is a lower triangular matrix and $U \in \Re^{nxn}$ is an upper triangular matrix. $P \in \Re^{mxm}$ is the ...
-1
votes
3answers
30 views

Proof properties of vector norm

How can I proof that for all vector norm on $ \mathbb{R} $ that $\left | \left \| x \right \|-\left \| y \right \| \right |\leq \left \| x-y \right \|$
1
vote
1answer
38 views

Approximate $f''(x)$ given $f(x),f(x+h),f(x+3h),f(x-5h)$

Given $f(x),f(x+h),f(x+3h),f(x-5h)$, approximate $f''(x)$. Book's solution: From Taylor' series, $$ \\ f(x+h)=f(x)+f'(x)h+0.5f''(x)h^2+{1\over6}f'''(x)h^3+O(h^4) \\ f(x+3h)=f(x)+3f'(x)h+4.5f''(x)h^2+...
3
votes
1answer
101 views

Linear Least-Squares Problem with Inequality Constraints on Residual

I have an over-determined linear least-squares problem $$\min_{\vec{x}}\Vert\mathbf{A}\vec{x}-\vec{b}\Vert_2^2,$$ where $\mathbf{A}\in\mathbb{R}^{n\times m}$, $\vec{x}\in\mathbb{R}^m$, $\vec{b}\in\...
0
votes
1answer
32 views

Proving that product of general matrices has small spectral radius

In a Jacobi type of iteration for finding solution to a linear system $Ax=b$, one writes $$x_i^{(k+1)} = Gx_i^{(k)}+c,$$ where $x_i$ is the $i$-th component of vector $x$ and $G=D^{-1}N$, $c = D^{-1}...
0
votes
1answer
43 views

Discretization matrix for 3D Poisson equation

It is known that the 2D Poisson equation defined on a domain $\Omega$ (let's say $\Omega := (0,1)^2$) with Dirichlet boundary conditions $u(x,y)_{|\partial \Omega}=g(x,y)$, $$u_{xx} + u_{yy}=f$$ can ...
1
vote
1answer
47 views

Coupled differential equations into system of first-order equations implicitly

I am looking to solve the following equations numerically: $a x=\frac{d}{dt}\left(f(x,y,t)\frac{dy}{dt}\right),\quad b y=\frac{d}{dt}\left(g(x,y,t)\frac{dx}{dt}\right)$ For arbitrary functions $f$ ...
1
vote
1answer
40 views

What's the reason to use Singular Value Decomposition instead io $(A^TA)^{-1}A^T$ for pseudo inverse?

I wonder what's the reason to use this formula from Singular Value Decomposition $$ A = U\Sigma V $$ $$ A^{\dagger} = V\Sigma^{-1}U^T $$ Instead of $$ A^{\dagger} = (A^TA)^{-1}A^T $$ Both give ...
0
votes
0answers
43 views

What is the relationship between $||.||_{max}$ and energy of a matrix?

I was interested to find a relationship between $||.||_{max}$, i.e. max-norm of a matrix with that of its energy. $||.||_{max}$ of a matrix is defined by the maximum entry in the matrix. Generally, ...
0
votes
1answer
22 views

Perturbation bound on approximate linear system

Suppose that $A, \hat A$ are invertible real matrices such that $Ax = y$ and $\hat A\hat x = \hat y$, where $\|A - \hat A\| \leq \epsilon_1$ and $\|\hat y - y\| \leq \epsilon_2 \|y\|$. I'm trying to ...
0
votes
1answer
26 views

Ill-conditioned matrices and their singular values

For ill-conditioned matrices, must it be that the smallest singular value is arbitrarily close to $0$? I know that $K_2(A) = \frac{\sigma_{max}}{\sigma_{min}}$ where $\sigma$ is a singular value of A. ...