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
21 views

Are the divided differences $f[a, b, c]$ and $f[a, c, b]$ equal to eqchother?

I was wondering whether the divided differences $f[a, b, c]$ and $f[a, c, b]$ were equal. I tried proving this by writing out the definition and got that those two are equal iff $-cf(b) + cf(a) + af(b)...
1
vote
0answers
18 views

Understanding/Proving a theorem in Numerical Optimization by Nocedal

I was reading this book specially theorem 8.4 on page 210. Suppose that a method in the Broyden class is applied to a strongly convex quadratic function $f : R^n \rightarrow R$, where $x_0$ is the ...
0
votes
1answer
28 views

Understanding the rate of convergence of a numerical method (Euler's method)

I have recently implemented a function for Euler's method and I am trying to find some information about the rate of convergence for it, though I am failing to understand it. So far I have a set of ...
1
vote
0answers
30 views

Dodging to do conjugate gradient on the normal equations.

Let us consider the linear equation system $$\bf Ax = b$$ We can formulate it's normal equations: $${\bf A}^T{\bf Ax=A}^T{\bf b}$$ but these are often harder to solve, because ${\bf A}^T{\bf A}$ ...
3
votes
0answers
44 views

Best method to calculate the characteristic polynomial

Is there a "gold" standard for computing the characteristic polynomial of a given $n \times n$ matrix in finite precision arithmetic on a computer? There are fast methods running in $O(n^3)$ or even $...
0
votes
1answer
41 views

If $M=v_1v_i^TD_i$, compute $v_i$ and $D_i$

A known real-valued $n\times n$ matrix $M$ can be written as $$ M = v_1v_i^TD_i, $$ (no summation on repeated indices) where the $v_i$ are orthonormal column vectors, $D_i$ are diagonal matrices and ...
0
votes
0answers
22 views

Boundary for eigenvectors of perturbed tridiagonal matrix

Let $A = \left[\begin{array}{cccc} 2 & -1 & 0 & 0 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ 0 & 0 & -1 & 2 \end{array}\right] \; \; $ and $H $ a ...
1
vote
2answers
22 views

QR - Factorization: If A has full rank then R has non-zeros in the diagonal

$Q$ is an orthogonal matrix. $R$ is an upper triangular matrix. $A \in \mathbb{R}^{m\times n}$ with $m > n$ and its QR-Factorizations is $A = QR$. Show that if $A$ has full rank, then the diagonal ...
0
votes
0answers
16 views

QR-algorithm complexity on a symmetric tridiagonal matrix

Why does the QR algorithm (for calculating eigenvalues) only require O(m) calculations per step when performed on a symmetric tridiagonal matrix?
0
votes
3answers
54 views

algebra odd numbers

A question states, using algebra, prove that when the square of any odd number is divided by four, the remainder is $1$ I managed to go up to $4(n^{2}+n)+1$, from $(2n+1)^{2}$ but I dont know how to ...
0
votes
1answer
26 views

Point intersecting line, and finding implicit equation for line given parametrisation. [closed]

Consider a point $A= (1,3,9)$ in $\mathbb{R}^3$, and a line $L$ defined by the parametric equations $$x=2+2t, y=2, \textrm{and } z=10+5t.$$ (a) Determine if $A$ lies on $L$. (b) Write a general, or ...
-3
votes
1answer
28 views

Counterexample of closure of subset under vector addition and scalar multiplication. [closed]

Determine if the following set is a vector space over real numbers. Prove your answer. You need to check only the closure of the set under the operations. If a property is false, provide specific ...
4
votes
1answer
48 views

QR decomposition with lower triangular matrix using Householder reflection

Problem Find householder matrices $H_1,H_2,\cdots,H_n$ such that $$ H_n\cdots H_1 A = L $$ where $A$ : $n \times n$ matrix and $L$ : $n \times n$ lower triangular matrix. Try By defining $...
0
votes
1answer
22 views

Basis complement of image of sparse matrix

I have a map of vector space $R:T\to M$, and I'm interested in the quotient $E=M/R(T)$. In particular I want to construct a section $s:E\to M$. Theoretically this is not very difficult to solve, but I ...
0
votes
0answers
7 views

Linear system with non-constant matrix containg entries form unknown vector

Consider a system of PDEs $$ \begin{cases} u_t = \nabla \cdot (D(u)\nabla u) + \frac{c}{K_U+c}u-ku\\ c_t = d_c\Delta c -\frac{\nu_U c}{K_U + c}u \end{cases} $$ with some boundary conditions. Here, $D(...
0
votes
0answers
29 views

How to solve a matrix dominated by zeros?

I am trying to solve a matrix of this form: Is there a known algorithm or a method to solve this kind of matrices more efficiently than a normal Gauß elimination method? I input the diagonals as ...
1
vote
0answers
16 views

Derive Hessian inverse update using Sherman-Morrison in Quasi Newton Method

From Nocedal's Numerical Optimization book, the Hessian approximation equation is given using Symmetric Rank 1 (SR1) formula as follows: $$B_{k+1} = B_k + \frac{(y_k - B_ks_k)(y_k - B_ks_k)}{(y_k - ...
0
votes
1answer
21 views

negative semidefinite matrix

I got a positive definite matrix $B$, that is, $V(x)=x^TBx>0$ for any vector $x≠0$. I am clear with the statement that $λ_\min∥x∥_2^2≤V(x)≤λ_\max∥x∥_2^2$ for any $x≠0$, where $λ_\min$ and $λ_\max$ ...
0
votes
0answers
17 views

$\ell_1$ norm of multivector in exterior algebra

Suppose you have a set of $n$ linearly independent vectors $v_1, v_2, ..., v_n$. Then we can call their wedge product $W = v_1 \wedge v_2 \wedge ... \wedge v_n$. The $\ell_2$ norm $\|W\|_2$ is equal ...
0
votes
1answer
35 views

Lagrange interpolation formula

Give the formula of the $1$st degree Lagrange polynomial $L(x)$ interpolating a function $f$ at the points $0$ and $1$. Give the formula for the error $L - f$. Finally, show that $$\sup_{x \in ...
0
votes
0answers
44 views

Efficiently solve a system of equations for only certain degrees of freedom given a known structure

I have an algorithm such that at some point I must solve the following system for $X_5$: $$ \left( \begin{array}{cccccccccc} A_1& B_1& & C_1& & & & & \\ B_7& A_2&...
0
votes
0answers
45 views

Angle between vectors from vector coordinates.

I want to compute the angle between vectors by means of the formula given here, $$ \theta = 2\arctan2 \left( \left|\left| \frac{\textbf{y}}{\|\textbf{y}\|} - \frac{\textbf{x}}{\|\textbf{x}\|} \right|\...
1
vote
0answers
24 views

Treatment of Floating Point Rounding in Trefethen & Bau

Something I noticed in the Trefethen & Bau Numerical Linear Algebra book is that, after introducing elementary floating point arithmetic, they do not pay too much care to the initial rounding of ...
0
votes
0answers
28 views

Difficulty in understanding the program for Gaussian elimination using full pivoting

I am a second year open university BS mathematics student taking a course on numerical methods. I thought it would be good idea to implement some of these algorithms in C++ - to learn how numerical ...
0
votes
1answer
41 views

How can I prove that an algorithm is numerically stable?

I come from Computer Science and I designed an algorithm belongs to Numerical Linear Algebra field. The analysis of algorithms in Computer Science usually involves the correctness, time and space ...
1
vote
0answers
13 views

Constructing a degree-1 Lagrange interpolation polynomial

Construct the Lagrange polynomial $p_1$ of degree $1$ for a continuous function $f$ on $[-1, 1]$ using the points $x_0 = -1$ and $x_1 = 1$. My attempt (note: I am using the notation that is used on ...
0
votes
1answer
35 views

Construct a Real Matrix for given Complex Eigenvalues

I need to construct real-valued matrices with specific complex eigenvalues. I have seen the companion matrix, which sort of does my job, but there are some other desirable properties as well, so I'm ...
0
votes
0answers
17 views

Equivalent to a condition number inequality but for singular matrices

When we have a linear system ($AX=b$) ($A$ an invertible matrix of size $n\times n$ and $X,b$ vectors of size $n$) and there's a disturbance in $b$ (say $b+\delta b$) we get $A(X+\Delta X)=(b+\delta b)...
2
votes
0answers
38 views

Showing $\vert \mathrm{det}(A) \vert \le \prod_{j=1}^n \Vert a_j \Vert_2$ [duplicate]

Problem Show $\vert \mathrm{det}(A) \vert \le \prod_{j=1}^n \Vert a_j \Vert_2$, where $a_j$ denotes the $j$th column of $A$, which is $n \times n$ matrix. Try When $A$ is singular, the result is ...
0
votes
1answer
73 views

What do these matrices converge to?

Sorry this is quite a specific question, happy to reword the title however you think is more appropriate, but for a given $m$ x $n$ matrix A, and an initial, random $n$ x $k$ matrix $v$, I have this ...
1
vote
1answer
31 views

convergence of unshifted $QR$ algorithm proof

I'm currently getting most of my info from Burden's Numerical Analysis book . In the book it mentions that the $QR$ algorithm converges to a diagonal matrix with no proof provided. The method in the ...
1
vote
1answer
53 views

Computational cost of finding only the eigenvalues

I have read that the computational cost of full eigendecomposition (finding both eigenvalues and eigenvectors) is $O(n^3)$. But what is the cost if we want to find only eigenvalues? How does MATLAB ...
0
votes
0answers
19 views

Double precision (using 16-digits) in mathematica

How can i control the precisions of the numeric results in mathematica? For example; for the residual error i want to working with 16-digits for each step, especially of matrix norms.
1
vote
1answer
29 views

Condition number growth with “column add” operation

This problem concerns how when you add a column to a matrix, its two-norm condition number grows. I ran across this as Problem 5.3.2 in Golub and van Loan, stated in the line below. Let $A \in \...
3
votes
1answer
38 views

Solving for $L$, where $P_n \cdots P_1 = I - XLX^T$, with $\Vert x_i \Vert_2=1$, $P_i := I - 2x_i x_i^T$, $X=[x_1 \cdots x_n]$

Problem Solve for $L$, where $P_n \cdots P_1 = I - XLX^T$ where $\Vert x_i \Vert_2=1$, $P_i := I - 2x_i x_i^T$, and $X_{m \times n} = [x_1 |\cdots | x_n]$. Try Note that $L$ is a lower ...
0
votes
0answers
25 views

Fitting parabola to data set using inner products

I need to find $P(x) = ax^2 +bx + c$ that fits the following data set: $$P(1) = 2\\P(2) = 3\\P(3) = 4$$ using the least squares method. That is, we need to minimize $$\min \sum_{i=0}^2 (y_i -(ax_i^...
4
votes
0answers
54 views

Gram-Schmidt: how close are resulting vectors to $0$?

Let $\{u_1,u_2,\ldots,u_n\}$ be the orthogonal (i.e., before the normalization) basis obtained from linearly independent vectors $\{v_1,v_2,\ldots,v_n\}$ by the Gram-Schmidt process, starting from $...
0
votes
0answers
22 views

Estimating rate of decay of residual norms in gradient descent

I am using gradient descent to solve the linear system $Ax=b$, where matrix $A$ is symmetric and positive definite. More precisely, I am attempting to solve the following quadratic program $$\text{...
0
votes
0answers
20 views

Hessenberg reduction via Householder reflector

I'm trying to understand $QR$ algorithm, and one oefficient way of using the QR algorithm is to first transform the matrix to Hessenberg form using Householder reflectors. We use the Householder ...
0
votes
1answer
39 views

Prove that $\lim_{k\rightarrow > \infty} \frac{\|A^{k+2}x\|}{\|A^{k}x\|}=\lambda^2$

Assume that $A \in \mathbb R^{n×n}$ has $n$ linearly independent eigenvectors $u_1, u_2, . . ., u_n ∈ \mathbb C^n$ with associated eigenvalues $λ_1, λ_2, . . ., λ_n$ with $λ_1 = λ, λ_2 = −λ$, for ...
0
votes
0answers
14 views

the reference for block tridiagonal matrix of finite element discretization of 2D convection diffusion equation.

I need to know a block tri-diagonal matrix with Kronecker product structure arising from finite element discretization of 2-D convection-diffusion equation on square domain to test some codes. But I ...
4
votes
1answer
79 views

Show convergence of an algorithm within $m$ steps

I am trying to show that the following algorithm outputs the solution to the problem $Ax=b$. Assumptions $A$ is symmetric positive definite of size $n \times n$ with $m$ distinct eigenvalues. The ...
0
votes
1answer
21 views

Showing $\sup_{\Vert w \Vert_\infty} |v^\ast w| = \Vert v \Vert_1$ for $v \neq 0$

Problem Show, for $v \neq 0 \in \mathbb{C}^n$ $$ \sup_{\Vert w \Vert_\infty=1} |v^\ast w| = \Vert v \Vert_1 $$ And find the similar equality for $\sup_{\Vert w \Vert_1=1} |v^\ast w|$ Try ...
0
votes
1answer
30 views

Finding the solution $\xi$ of $(M + \xi)x = y$ with the smallest 2-norm.

Problem Show $\xi = \frac{(y - Mx)x^\ast}{x^\ast x}$ is the solution of the following $$ (M + \xi)x = y $$ with the minimum $\Vert \xi\Vert_2$, where $M \in \mathbb{C}^{m \times n}, x \...
0
votes
0answers
28 views

Solving a system of Trignometric equations

I came across this system of trigonometric equations inbetween a problem in Numerical Linear Algebra. I was required to find $p^2$ and $\cos(\theta)$ in terms of $q^{(k-1)},q^{(k)},q^{(k+1)},q^{(k+2)}$...
0
votes
1answer
58 views

Explain every steps of the Modified Gram–Schmidt algorithm

Can someone explain in details what every step in the modified gram Schmidt algorithm is doing? MGS algorithm Excerpts: Gram-Schmidt Algorithm Modified Gram-Schmidt Algorithm This is what I ...
0
votes
1answer
48 views

Show $\Vert A\Vert_2 = \sup_{x \neq 0} \frac{x^T A x}{x^T x}$ where $A$ is symmetric and positive-definite

Problem Show: $$\Vert A\Vert_2 = \sup_{0 \neq x \in \mathbb{R}} \frac{x^T A x}{x^T x}$$ where $A$ is symmetric and positive definite. Try Since \begin{align} \Vert A\Vert_2 &= \sup_{0 \...
0
votes
0answers
23 views

Solve dynamic system using Euler method

Problem Statement Consider the following dynamic system, Where, K=4 and m=4. Find out the value of x(t) at the given value of t=2, with initial condition $x(0)$ and $\dot x(0)$, using the Euler ...
1
vote
1answer
96 views

Showing $Q_n = \frac{T_n(x)}{2^{n-1}}$ is the monic polynomial of least norm

The Chebyschev polynomials are denoted by $T_n(x) = \cos (n\arccos x)$ and are orthogonal in relation to $\langle f,g\rangle = \int_{-1}^1\frac{f(x)g(x)}{\sqrt{1-x^2}}$ Show that $T_n(x) = \...
1
vote
0answers
55 views

Book about interpolation of functions by polynomials using linear algebra/projection

I've been asking a lot of questions about interpolation of functions using polynomials: Approximate $f(t) = 1-|2t-5|$ in $[2,3]$ by $p\in P_2$ by using the least squares method Approximate $f(x) = x^...