Tag Archives: matrix

Successive over-relaxation

Successive over-relaxation

From Wikipedia, the free encyclopedia
In numerical linear algebra, the method of successive over-relaxation (SOR) is a variant of the Gauss–Seidel method for solving alinear system of equations, resulting in faster convergence. A similar method can be used for any slowly converging iterative process. It was devised simultaneously by David M. Young and by H. Frankel in 1950 for the purpose of automatically solving linear systems on digital computers. Over-relaxation methods had been used before the work of Young and Frankel. For instance, the method of Lewis Fry Richardson, and the methods developed by R. V. Southwell. However, these methods were designed for computation by human calculators, and they required some expertise to ensure convergence to the solution which made them inapplicable for programming on digital computers. These aspects are discussed in the thesis of David M. Young.[1]
Advertisements

the Gram–Schmidt process

In mathematics, particularly linear algebra and numerical analysis, the Gram–Schmidt process is a method fororthonormalising a set of vectors in an inner product space, most commonly the Euclidean space Rn. The Gram–Schmidt process takes a finitelinearly independent set S = {v1, …, vk} for k ≤ n and generates an orthogonal setS′ = {u1, …, uk} that spans the same k-dimensional subspace of Rn as S.

The method is named after Jørgen Pedersen Gram and Erhard Schmidt but it appeared earlier in the work of Laplaceand Cauchy. In the theory of Lie group decompositions it is generalized by the Iwasawa decomposition.[1]

The application of the Gram–Schmidt process to the column vectors of a full column rank matrix yields the QR decomposition (it is decomposed into an orthogonal and a triangular matrix).

In linear algebra, a QR decomposition (also called a QR factorization) of a matrix is a decomposition of a matrix A into a product A = QR of an orthogonal matrix Q and anupper triangular matrix R. QR decomposition is often used to solve the linear least squares problem, and is the basis for a particular eigenvalue algorithm, the QR algorithm.

If A has n linearly independent columns, then the first n columns of Q form an orthonormal basis for the column space of A. More specifically, the first k columns of Q form an orthonormal basis for the span of the first k columns of A for any 1 ≤ k ≤ n.[1] The fact that any column k of A only depends on the first k columns of Q is responsible for the triangular form of R

 

Complexity of Matrix Inversion

 

What is the computational complexity of inverting an nxn matrix? (In 
general, not special cases such as a triangular matrix.)

Gaussian Elimination leads to O(n^3) complexity. The usual way to 
count operations is to count one for each "division" (by a pivot) and 
one for each "multiply-subtract" when you eliminate an entry.

Here's one way of arriving at the O(n^3) result:

   At the beginning, when the first row has length n, it takes n 
   operations to zero out any entry in the first column (one division, 
   and n-1 multiply-subtracts to find the new entries along the row 
   containing that entry. To get the first column of zeroes therefore 
   takes n(n-1) operations.

   In the next column, we need (n-1)(n-2) operations to get the second 
   column zeroed out.

   In the third column, we need (n-2)(n-3) operations.

   The sum of all of these operations is:

         n            n         n      n(n+1)(2n+1)   n(n+1)
        SUM i(i-1) = SUM i^2 - SUM i = ------------ - ------
        i=1          i=1       i=1           6           2

   which goes as O(n^3). To finish the operation count for Gaussian 
   Elimination, you'll need to tally up the operations for the process 
   of back-substitution (you can check that this doesn't affect the 
   leading order of n^3).

You might think that the O(n^3) complexity is optimal, but in fact 
there exists a method (Strassen's method) that requires only 
O(n^log_2(7)) = O(n^2.807...) operations for a completely general 
matrix. Of course, there is a constant C in front of the n^2.807. This 
constant is not small (between 4 and 5), and the programming of 
Strassen's algorithm is so awkward, that often Gaussian Elimination is 
still the preferred method.

Even Strassen's method is not optimal. I believe that the current 
record stands at O(n^2.376), thanks to Don Coppersmith and Shmuel 
Winograd. Here is a Web page that discusses these methods:

   Fast Parallel Matrix Multiplication - Strategies for Practical 
   Hybrid Algorithms - Erik Ehrling
   http://www.f.kth.se/~f95-eeh/exjobb/background.html   

These methods exploit the close relation between matrix inversion and 
matrix multiplication (which is also an O(n^3) task at first glance). 

I hope this helps! 

- Doctor Douglas, The Math Forum
  http://mathforum.org/dr.math/

cofactor

In linear algebra, the cofactor (sometimes called adjunct, see below) describes a particular construction that is useful for calculating both the determinant and inverse of square matrices. Specifically the cofactor of the (ij) entry of a matrix, also known as the (ij) cofactor of that matrix, is the signed minor of that entry.


Finding the minors of a matrix A is a multi-step process:
  1. Choose an entry aij from the matrix.
  2. Cross out the entries that lie in the corresponding row i and column j.
  3. Rewrite the matrix without the marked entries.
  4. Obtain the determinant Mij of this new matrix.
Mij is termed the minor for entry aij.
If i + j is an even number, the cofactor Cij of aij coincides with its minor:
C_{ij} = M_{ij}. \,
Otherwise, it is equal to the additive inverse of its minor:
C_{ij} = -M_{ij}. \,
The matrix of cofactors for an n\times n matrix A is the matrix whose (i,j) entry is the cofactor Cij of A. For instance, if A is
 A = \begin{bmatrix}
    a_{11}  & a_{12} & \cdots &   a_{1n}   \\
    a_{21}  & a_{22} & \cdots &   a_{2n}   \\
  \vdots & \vdots & \ddots & \vdots \\ 
    a_{n1}  & a_{n2} & \cdots &  a_{nn}
\end{bmatrix}
the cofactor matrix of A is
 C = \begin{bmatrix}
    C_{11}  & C_{12} & \cdots &   C_{1n}   \\
    C_{21}  & C_{22} & \cdots &   C_{2n}   \\
  \vdots & \vdots & \ddots & \vdots \\ 
    C_{n1}  & C_{n2} & \cdots &  C_{nn}
\end{bmatrix}
where Cij is the cofactor of aij.
In linear algebra, the Laplace expansion, named after Pierre-Simon Laplace, also called cofactor expansion, is an expression for the determinant |B| of an n × n square matrix B that is a weighted sum of the determinants of n sub-matrices of B, each of size (n–1) × (n–1). The Laplace expansion is of theoretical interest as one of several ways to view the determinant, as well as of practical use in determinant computation.
The i,j cofactor of B is the scalar Cij defined by
C_{ij}\ = (-1)^{i+j} |M_{ij}|\,,
where Mij is the i,j minor matrix of B, that is, the (n–1) × (n–1) matrix that results from deleting the i-th row and the j-th column of B.
Then the Laplace expansion is given by the following
Theorem. Suppose B = (bij) is an n × n matrix and i,j ∈ {1, 2, …,n}.
Then its determinant |B| is given by:
\begin{align}|B| & {} = b_{i1} C_{i1} + b_{i2} C_{i2} + \cdots + b_{in} C_{in} \\ & {} = b_{1j} C_{1j} + b_{2j} C_{2j} + \cdots + b_{nj} C_{nj}. \end{align}
Suppose R is a commutative ring and A is an n×n matrix with entries from R. The definition of the adjugate of A is a multi-step process:
  • Define the (i,jminor of A, denoted Mij, as the determinant of the (n − 1)×(n − 1) matrix that results from deleting row i and column j of A.
  • Define the (i,jcofactor of A as
\mathbf{C}_{ij} = (-1)^{i+j} \mathbf{M}_{ij}. \,
  • Define the cofactor matrix of A, as the n×n matrix C whose (i,j) entry is the (i,j) cofactor of A.
The adjugate of A is the transpose of the cofactor matrix of A:
\mathrm{adj}(\mathbf{A}) = \mathbf{C}^T \,.
That is, the adjugate of A is the n×n matrix whose (i,j) entry is the (j,i) cofactor of A:
\mathrm{adj}(\mathbf{A})_{ij} = \mathbf{C}_{ji} \,.

Examples


2 × 2 generic matrix

The adjugate of the 2 × 2 matrix
\mathbf{A} = \begin{pmatrix} {{a}} & {{b}}\\ {{c}}  & {{d}} \end{pmatrix}
is
\operatorname{adj}(\mathbf{A}) = \begin{pmatrix} \,\,\,{{d}} & \!\!{{-b}}\\ {{-c}} & {{a}} \end{pmatrix}.


3 × 3 generic matrix

Consider the 3\times 3 matrix

\mathbf{A} = \begin{pmatrix}
A_{11} & A_{12} & A_{13} \\
A_{21} & A_{22} & A_{23} \\
A_{31} & A_{32} & A_{33}
\end{pmatrix}
= \begin{pmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{pmatrix}.
Its adjugate is the transpose of the cofactor matrix

\mathbf{C} = \begin{pmatrix} 
+\left| \begin{matrix} A_{22} & A_{23} \\ A_{32} & A_{33} \end{matrix} \right| &
-\left| \begin{matrix} A_{21} & A_{23} \\ A_{31} & A_{33}  \end{matrix} \right| &
+\left| \begin{matrix} A_{21} & A_{22} \\ A_{31} & A_{32} \end{matrix} \right| \\
 & & \\
-\left| \begin{matrix} A_{12} & A_{13} \\ A_{32} & A_{33} \end{matrix} \right| &
+\left| \begin{matrix} A_{11} & A_{13} \\ A_{31} & A_{33} \end{matrix} \right| &
-\left| \begin{matrix} A_{11} & A_{12} \\ A_{31} & A_{32} \end{matrix} \right| \\
 & & \\
+\left| \begin{matrix} A_{12} & A_{13} \\ A_{22} & A_{23} \end{matrix} \right| &
-\left| \begin{matrix} A_{11} & A_{13} \\ A_{21} & A_{23} \end{matrix} \right| &
+\left| \begin{matrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix} \right|
\end{pmatrix} = \begin{pmatrix} 
+\left| \begin{matrix} 5 & 6 \\ 8 & 9 \end{matrix} \right| &
-\left| \begin{matrix} 4 & 6 \\ 7 & 9  \end{matrix} \right| &
+\left| \begin{matrix} 4 & 5 \\ 7 & 8 \end{matrix} \right| \\
 & & \\
-\left| \begin{matrix} 2 & 3 \\ 8 & 9 \end{matrix} \right| &
+\left| \begin{matrix} 1 & 3 \\ 7 & 9 \end{matrix} \right| &
-\left| \begin{matrix} 1 & 2 \\ 7 & 8 \end{matrix} \right| \\
 & & \\
+\left| \begin{matrix} 2 & 3 \\ 5 & 6 \end{matrix} \right| &
-\left| \begin{matrix}  1 & 3 \\ 4 & 6 \end{matrix} \right| &
+\left| \begin{matrix} 1 & 2 \\ 4 & 5 \end{matrix} \right|
\end{pmatrix}
So that we have

\operatorname{adj}(\mathbf{A}) = \begin{pmatrix} 
+\left| \begin{matrix} A_{22} & A_{23} \\ A_{32} & A_{33} \end{matrix} \right| &
-\left| \begin{matrix} A_{12} & A_{13} \\ A_{32} & A_{33}  \end{matrix} \right| &
+\left| \begin{matrix} A_{12} & A_{13} \\ A_{22} & A_{23} \end{matrix} \right| \\
 & & \\
-\left| \begin{matrix} A_{21} & A_{23} \\ A_{31} & A_{33} \end{matrix} \right| &
+\left| \begin{matrix} A_{11} & A_{13} \\ A_{31} & A_{33} \end{matrix} \right| &
-\left| \begin{matrix} A_{11} & A_{13} \\ A_{21} & A_{23}  \end{matrix} \right| \\
 & & \\
+\left| \begin{matrix} A_{21} & A_{22} \\ A_{31} & A_{32} \end{matrix} \right| &
-\left| \begin{matrix} A_{11} & A_{12} \\ A_{31} & A_{32} \end{matrix} \right| &
+\left| \begin{matrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix} \right|
\end{pmatrix} = \begin{pmatrix} 
+\left| \begin{matrix} 5 & 6 \\ 8 & 9 \end{matrix} \right| &
-\left| \begin{matrix} 2 & 3 \\ 8 & 9  \end{matrix} \right| &
+\left| \begin{matrix} 2 & 3 \\ 5 & 6 \end{matrix} \right| \\
 & & \\
-\left| \begin{matrix} 4 & 6 \\ 7 & 9 \end{matrix} \right| &
+\left| \begin{matrix} 1 & 3 \\ 7 & 9 \end{matrix} \right| &
-\left| \begin{matrix} 1 & 3 \\ 4 & 6  \end{matrix} \right| \\
 & & \\
+\left| \begin{matrix} 4 & 5 \\ 7 & 8 \end{matrix} \right| &
-\left| \begin{matrix} 1 & 2 \\ 7 & 8 \end{matrix} \right| &
+\left| \begin{matrix} 1 & 2 \\ 4 & 5 \end{matrix} \right|
\end{pmatrix}
where
\left| \begin{matrix} A_{im} & A_{in} \\ \,\,A_{jm} & A_{jn} \end{matrix} \right|=
\det\left(    \begin{matrix} A_{im} & A_{in} \\ \,\,A_{jm} & A_{jn} \end{matrix} \right).
Note that the adjugate is the transpose of the cofactor matrix. Thus, for instance, the (3,2) entry of the adjugate is the (2,3) cofactor of A.
The adjugate matrix is the transpose of the matrix of cofactors and is very useful due to its relation to the inverse of A.
\mathbf{A}^{-1} = \frac{1}{\det \mathbf{A}} \mbox{adj}(\mathbf{A})
The matrix of cofactors
 \begin{bmatrix}
    C_{11}  & C_{12} & \cdots &   C_{1n}   \\
    C_{21}  & C_{22} & \cdots &   C_{2n}   \\
  \vdots & \vdots & \ddots & \vdots \\ 
    C_{n1}  & C_{n2} & \cdots &  C_{nn}
\end{bmatrix}
when transposed becomes
 \mathrm{adj}(A) = \begin{bmatrix}
    C_{11}  & C_{21} & \cdots &   C_{n1}   \\
    C_{12}  & C_{22} & \cdots &   C_{n2}   \\
  \vdots & \vdots & \ddots & \vdots \\ 
    C_{1n}  & C_{2n} & \cdots &  C_{nn}
\end{bmatrix}.

A remark about different notations

In some books, including so the called “a bible of matrix theory”[1] instead of cofactor the term adjunct is used. Moreover, it is denoted as Aij and defined in the same way as cofactor:
\mathbf{A}_{ij} = (-1)^{i+j} \mathbf{M}_{ij}
Using this notation the inverse matrix is written this way:
\mathbf{A}^{-1} = \frac{1}{\det(A)}\begin{bmatrix}
    A_{11}  & A_{21} & \cdots &   A_{n1}   \\
    A_{12}  & A_{22} & \cdots &   A_{n2}   \\
  \vdots & \vdots & \ddots & \vdots \\ 
    A_{1n}  & A_{2n} & \cdots &  A_{nn}
\end{bmatrix}
Keep in mind that adjunct is not adjugate or adjoint.


See also

[edit]References

  1. ^ Felix GantmacherTheory of matrices (1st ed., original language is Russian), Moscow: State Publishing House of technical and theoretical literature, 1953, p.491,
  • Anton, Howard; Rorres, Chris (2005), Elementary Linear Algebra (9th ed.), John Wiley and Sons, ISBN 0-471-66959-8
http://en.wikipedia.org/wiki/Cofactor_(linear_algebra)
http://en.wikipedia.org/wiki/Laplace_expansion
http://en.wikipedia.org/wiki/Adjugate_matrix

Complexity of Matrix Inversion

What is the computational complexity of inverting an nxn matrix? (In 
general, not special cases such as a triangular matrix.)

Gaussian Elimination leads to O(n^3) complexity. The usual way to 
count operations is to count one for each "division" (by a pivot) and
one for each "multiply-subtract" when you eliminate an entry.

Here's one way of arriving at the O(n^3) result:

At the beginning, when the first row has length n, it takes n
operations to zero out any entry in the first column (one division,
and n-1 multiply-subtracts to find the new entries along the row
containing that entry. To get the first column of zeroes therefore
takes n(n-1) operations.

In the next column, we need (n-1)(n-2) operations to get the second
column zeroed out.

In the third column, we need (n-2)(n-3) operations.

The sum of all of these operations is:

n n n n(n+1)(2n+1) n(n+1)
SUM i(i-1) = SUM i^2 - SUM i = ------------ - ------
i=1 i=1 i=1 6 2

which goes as O(n^3). To finish the operation count for Gaussian
Elimination, you'll need to tally up the operations for the process
of back-substitution (you can check that this doesn't affect the
leading order of n^3).

You might think that the O(n^3) complexity is optimal, but in fact
there exists a method (Strassen's method) that requires only
O(n^log_2(7)) = O(n^2.807...) operations for a completely general
matrix. Of course, there is a constant C in front of the n^2.807. This
constant is not small (between 4 and 5), and the programming of
Strassen's algorithm is so awkward, that often Gaussian Elimination is
still the preferred method.

Even Strassen's method is not optimal. I believe that the current
record stands at O(n^2.376), thanks to Don Coppersmith and Shmuel
Winograd. Here is a Web page that discusses these methods:

Fast Parallel Matrix Multiplication - Strategies for Practical
Hybrid Algorithms - Erik Ehrling
http://www.f.kth.se/~f95-eeh/exjobb/background.html

These methods exploit the close relation between matrix inversion and
matrix multiplication (which is also an O(n^3) task at first glance).

I hope this helps!

- Doctor Douglas, The Math Forum
http://mathforum.org/dr.math/

Jacobian matrix and determinant

Jacobian matrix and determinant

From Wikipedia, the free encyclopedia

In vector calculus, the Jacobian matrix is the matrix of all first-order partial derivatives of a vector– or scalar-valued function with respect to another vector. Suppose F :Rn → Rm is a function from Euclidean n-space to Euclidean m-space. Such a function is given by m real-valued component functions, y1(x1,…,xn), …, ym(x1,…,xn). The partial derivatives of all these functions (if they exist) can be organized in an m-by-n matrix, the Jacobian matrix J of F, as follows:

J=\begin{bmatrix} \dfrac{\partial y_1}{\partial x_1} & \cdots & \dfrac{\partial y_1}{\partial x_n} \\ \vdots & \ddots & \vdots \\ \dfrac{\partial y_m}{\partial x_1} & \cdots & \dfrac{\partial y_m}{\partial x_n}  \end{bmatrix}.

This matrix is also denoted by J_F(x_1,\ldots,x_n) and \frac{\partial(y_1,\ldots,y_m)}{\partial(x_1,\ldots,x_n)}. If (x1,…,xn) are the usual orthogonal Cartesian coordinates, the i th row (i = 1, …, m) of this matrix corresponds to the gradient of the ith component function yi\left(\nabla y_i\right). Note that some books define the Jacobian as the transpose of the matrix given above.

The Jacobian determinant (often simply called the Jacobian) is the determinant of the Jacobian matrix.

These concepts are named after the mathematician Carl Gustav Jacob Jacobi. The term “Jacobian” is normally pronounced /dʒəˈkoʊbiən/, but sometimes also /jəˈkoʊbiən/.

http://en.wikipedia.org/wiki/Jacobian_matrix_and_determinant

Rotation matrix

Rotation matrix

From Wikipedia, the free encyclopedia
In linear algebra, a rotation matrix is a matrix that is used to perform a rotation in Euclidean space. For example the matrix
R =  begin{bmatrix} cos theta & -sin theta \ sin theta & cos theta \ end{bmatrix}
rotates points in the xyCartesian plane counterclockwise through an angle θ about the origin of the Cartesian coordinate system. To perform the rotation, the position of each point must be represented by a column vector v, containing the coordinates of the point. A rotated vector is obtained by using the matrix multiplication Rv (see below for details).
In two and three dimensions, rotation matrices are among the simplest algebraic descriptions of rotations, and are used extensively for computations in geometryphysics, and computer graphics. Though most applications involve rotations in two or three dimensions, rotation matrices can be defined for n-dimensional space.
Rotation matrices are always square, with real entries. Algebraically, a rotation matrix in n-dimensions is a n × n special orthogonal matrix, that is an orthogonal matrix whose determinant is 1:
R^{T} = R^{-1}, det R = 1,.
The set of all rotation matrices forms a group, known as the rotation group or the special orthogonal group. It is a subset of the orthogonal group, which includes reflections and consists of all orthogonal matrices with determinant 1 or -1, and of the special linear group, which includes all volume-preserving transformations and consists of matrices with determinant 1.
http://en.wikipedia.org/wiki/Rotation_matrix

As in two dimensions a matrix can be used to rotate a point (xyz) to a point (x′, y′, z′). The matrix used is a 3 × 3 matrix,
mathbf{A} = begin{pmatrix} a & b & c \ d & e & f \ g & h & i  end{pmatrix}
This is multiplied by a vector representing the point to give the result
  mathbf{A}  begin{pmatrix} x \ y \ z end{pmatrix} =  begin{pmatrix} a & b & c \ d & e & f \ g & h & i  end{pmatrix}  begin{pmatrix} x \ y \ z end{pmatrix} =  begin{pmatrix} x' \ y' \ z' end{pmatrix}
The matrix A is a member of the three dimensional special orthogonal group, SO(3), that is it is an orthogonal matrix withdeterminant 1. That it is an orthogonal matrix means that its rows are a set of orthogonal unit vectors (so they are an orthonormal basis) as are its columns, making it easy to spot and check if a matrix is a valid rotation matrix. The determinant must be 1 as if it is -1 (the only other possibility for an orthogonal matrix) then the transformation given by it is a reflectionimproper rotation or inversion in a point, i.e. not a rotation.
Matrices are often used for doing transformations, especially when a large number of points are being transformed, as they are a direct representation of the linear operator. Rotations represented in other ways are often converted to matrices before being used. They can be extended to represent rotations and transformations at the same time using Homogeneous coordinates. Transformations in this space are represented by 4 × 4 matrices, which are not rotation matrices but which have a 3 × 3 rotation matrix in the upper left corner.
The main disadvantage of matrices is that they are more expensive to calculate and do calculations with. Also in calculations wherenumerical instability is a concern matrices can be more prone to it, so calculations to restore orthonormality, which are expensive to do for matrices, need to be done more often.