algebra – Zintegra

2011/02/01

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 xy–Cartesian 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 geometry, physics, 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 (x, y, z) 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 reflection, improper 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.

2011/02/01

Spectral theorem

From Wikipedia, the free encyclopedia

In mathematics, particularly linear algebra and functional analysis, the spectral theorem is any of a number of results about linear operators or about matrices. In broad terms the spectral theorem provides conditions under which an operator or a matrix can bediagonalized (that is, represented as a diagonal matrix in some basis). This concept of diagonalization is relatively straightforward for operators on finite-dimensional spaces, but requires some modification for operators on infinite-dimensional spaces. In general, the spectral theorem identifies a class of linear operators that can be modelled by multiplication operators, which are as simple as one can hope to find. In more abstract language, the spectral theorem is a statement about commutative C*-algebras. See also spectral theory for a historical perspective.

Examples of operators to which the spectral theorem applies are self-adjoint operators or more generally normal operators on Hilbert spaces.

The spectral theorem also provides a canonical decomposition, called the spectral decomposition, eigenvalue decomposition, or eigendecomposition, of the underlying vector space on which the operator acts.

In this article we consider mainly the simplest kind of spectral theorem, that for a self-adjoint operator on a Hilbert space. However, as noted above, the spectral theorem also holds for normal operators on a Hilbert space.

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

2011/02/01

Krylov subspace

From Wikipedia, the free encyclopedia

In linear algebra, the order-r Krylov subspace generated by an n-by-n matrix A and a vector b of dimension n is the linear subspace spanned by the images of b under the first r powers of A (starting from A⁰ = I), that is,

$mathcal{K}_r(A,b) = operatorname{span} , { b, Ab, A^2b, ldots, A^{r-1}b }. ,$

It is named after Russian applied mathematician and naval engineer Alexei Krylov, who published a paper on this issue in 1931.^[1]

Modern iterative methods for finding one (or a few) eigenvalues of large sparse matrices or solving large systems of linear equations avoid matrix-matrix operations, but rather multiply vectors by the matrix and work with the resulting vectors. Starting with a vector, b, one computes Ab, then one multiplies that vector by A to find A²b and so on. All algorithms that work this way are referred to as Krylov subspace methods; they are among the most successful methods currently available in numerical linear algebra.

Because the vectors tend very quickly to become almost linearly dependent, methods relying on Krylov subspace frequently involve some orthogonalization scheme, such as Lanczos iteration for Hermitian matrices or Arnoldi iteration for more general matrices.

The best known Krylov subspace methods are the Arnoldi, Lanczos, Conjugate gradient, GMRES (generalized minimum residual),BiCGSTAB (biconjugate gradient stabilized), QMR (quasi minimal residual), TFQMR (transpose-free QMR), and MINRES (minimal residual) methods.

References

Nevanlinna, Olavi (1993). Convergence of iterations for linear equations. Lectures in Mathematics ETH Zürich. Basel: Birkhäuser Verlag. pp. viii+177 pp.. MR 1217705. ISBN 3-7643-2865-7.
Saad, Yousef (2003). Iterative methods for sparse linear systems (2nd ed.). SIAM. ISBN 0898715342. OCLC 51266114.

^ Mike Botchev (2002). “A.N.Krylov, a short biography”.

2009/08/23

La aritmética de Trachtenberg

Así como Viktor Emil Frankl desarrollo la logoterapia para superar los rigores de los campos de concentración Nazi, Jakow Trachtenberg ocupo su mente en desarrollar un sistema de aritmética mental al verse en la misma situación.

El sistema Trachtenberg de rápido cálculo mental, similar a las matemáticas Védicas, consiste en un conjunto de patrones para realizar operaciones aritméticas. Los algoritmos más importantes son multiplicación,división, y adición. El método también incluye algoritmos especializados para realizar multiplicaciones por números entre 5 y 13.

Multiplicación por 11

Abusando de la notación

(11)a = 11Σa_i10ⁱ =

a_n10ⁿ⁺¹ + [Σ_j=0^n-1(a_j+a_j+1)10^j ]+ a₀

Multiplicación por 12

(12)a = 12Σa_i10ⁱ =

a_n10ⁿ⁺¹ + [Σ_j=0^n-1(a_j+2a_j+1)10^j ]+ 2a₀

Multiplicación por 6

Definiendo

b_j = a_j/2, donde / denota división entera

c_j = a_j mod 2

tenemos

a_j = 2b_j + c_j

(6)a = (10/2)Σa_i10ⁱ + Σa_i10ⁱ =

Σb_i10ⁱ⁺¹ + Σ(a_i + 5c_i)10ⁱ

b_n10ⁿ⁺¹ + [Σ_j=1ⁿ(a_j+ 5c_j + b_j-1)10^j ]+ (a₀ + 5c₀)

Expresando el algoritmo en python:

def x6(number):
	previous = 0
	result = 0
	power_of_10 = 1
	while (number):
		digit = number%10
		odd_term = 5 if digit%2 else 0
		result = 
                (digit + odd_term + previous ) * 
		power_of_10 + result
		previous = digit//2
		power_of_10 *= 10
		number = number // 10
	result = previous * power_of_10 + result
	return result

Multiplicación por 7

De manera similar al caso anterior:

a_j = 2b_j + c_j

(7)a = (10/2)Σa_i10ⁱ + Σ2a_i10ⁱ =

Σb_i10ⁱ⁺¹ + Σ(2a_i + 5c_i)10ⁱ

b_n10ⁿ⁺¹ + [Σ_j=1ⁿ(2a_j+ 5c_j + b_j-1)10^j ]+ (a₀ + 5c₀)

Expresando el algoritmo en python:

def x7(number):
	previous = 0
	result = 0
	power_of_10 = 1
	while (number):
		digit = number%10
		odd_term = 5 if digit%2 else 0
		result = 
                (2*digit + odd_term + previous ) * 
		power_of_10 + result
		previous = digit//2
		power_of_10 *= 10
		number = number // 10
	result = previous * power_of_10 + result
	return result

Multiplicación por 5

De manera similar al caso anterior:

a_j = 2b_j + c_j

(5)a = (10/2)Σa_i10ⁱ =

Σb_i10ⁱ⁺¹ + Σ(5c_i)10ⁱ

b_n 10ⁿ⁺¹ + [Σ_j=1ⁿ(5c_j + b_j-1)10^j ]+ (5c₀)

Expresando el algoritmo en python:

def x5(number):
	previous = 0
	result = 0
	power_of_10 = 1
	while (number):
		digit = number%10
		odd_term = 5 if digit%2 else 0
		result = 
                (odd_term + previous ) * 
		power_of_10 + result
		previous = digit//2
		power_of_10 *= 10
		number = number // 10
	result = previous * power_of_10 + result
	return result

Multiplicación por 9

Definiendo

b = 10ⁿ⁺¹ – Σ_j=0ⁿa_j, o sea el complemento a 10 de a

tenemos

(9)a = 10a –a =

10a –a + b – b =

10a + b – 10ⁿ⁺¹ =

(a_n – 1)10ⁿ⁺¹ + [Σ_j=1ⁿ(b_j+ a_j-1)10^j ]+ (b₀ )

Expresando el algoritmo en python:

def x9(number):
	previous = number%10
	result = 10 - previous
	power_of_10 = 10
	number = number // 10
	while (number):
		digit = number%10
		result = 
                (9 - digit + previous ) * 
                power_of_10 + result
		previous = digit
		power_of_10 *= 10
		number = number // 10
	result = 
        (previous-1) * power_of_10 + 
        result
	return result

Multiplicación por 8

Definiendo

b = 10ⁿ⁺¹ – Σ_j=0ⁿa_j, o sea el complemento a 10 de a

tenemos

(8)a = 10a –2a =

10a –2a +2 b – 2b =

10a + 2b – (2)10ⁿ⁺¹ =

(a_n – 2)10ⁿ⁺¹ + [Σ_j=1ⁿ(2b_j+ a_j-1)10^j ]+ (2b₀ )

Expresando el algoritmo en python:

def x8(number):
	previous = number%10
	result = 2*(10 - previous)
	power_of_10 = 10
	number = number // 10
	while (number):
		digit = number%10
		result = 
		(2*(9 - digit) + previous ) * 
                power_of_10 + result
		previous = digit
		power_of_10 *= 10
		number = number // 10
	result = 
        (previous-2) * 
        power_of_10 + result
	return result

Multiplicación por 3 y por 4

Los algoritmos para multiplicar por 3 y por 4 combinan las ideas usadas en la multiplicación por 5 y por 9.

Definiendo

b = 10ⁿ⁺¹ – Σ_j=0ⁿa_j, o sea el complemento a 10 de a

a_i = 2c_i + d_i, donde

c_i = a_i/2

d_i = a_i mod 2

tenemos

(4)a = 5a –a =

10c + 5d + b – 10n+1

(3)a = 5a –2a =

10c + + 5d + 2b – (2)10ⁿ⁺¹

Expresando los algoritmos en python:

def x3(number):
	digit = number%10
	result = 2*(10 - digit)
	if digit % 2:
		result += 5
	previous = digit // 2
	power_of_10 = 10
	number = number // 10
	while (number):
		digit = number%10
		odd_term = 5 if digit%2 else 0
		result +=(2*(9 - digit) + odd_term + previous ) * power_of_10
		previous = digit//2
		power_of_10 *= 10
		number = number // 10
	result = (previous-2) * power_of_10 + result
	return result

def x4(number):
	digit = number%10
	result = (10 - digit)
	if digit % 2:
		result += 5
	previous = digit // 2
	power_of_10 = 10
	number = number // 10
	while (number):
		digit = number%10
		odd_term = 5 if digit%2 else 0
		result +=((9 - digit) + odd_term + previous ) * power_of_10
		previous = digit//2
		power_of_10 *= 10
		number = number // 10
	result = (previous-1) * power_of_10 + result
	return result

Referencias

2009/08/07

Aritmética y memoria; 513 Sticker

Es posible mediante el ejercicio de la memoria acelerar cálculos aritméticos. Este es un patrón general que también se aplica a la implementación algorítmica.

Por ejemplo, al multiplicar números de dos dígitos tenemos

a₁a₀ x b₁b₀ = (10a₁+a₀)(10b₁+b_o)=

100a₁b₁+10(a₁b_o+a₀b₁)+a₀b_o

Al multiplicar números de tres dígitos tenemos

a₂a₁a₀ x b₂b₁b₀ = (100a₂+10a₁+a₀)(100b₂+10b₁+b_o)=
10000a₂b₂ + 1000(a₂b₁+a₁b₂) +
100(a₂b₀+a₁b₁+a₀b₂) + 10(a₁b_o+a₀b₁)+a₀b_o

Si recordamos las fórmulas podemos encontrar los dígitos del producto directamente.

Al calcular el cuadrado de un número de 2 dígitos

(a₁a₀ )² = (10a₁+a₀)²=
100a₁²+10(2a₁a₀)+a₀²

Al calcular el cuadrado de un número que termina en 1

(a₁1 )² = (10a₁+1)²=
100a₁²+10(2a₁)+1

Al calcular el cuadrado de un número que termina en 5

(a₁5 )² = (10a₁+5)²=
100(a₁²+a₁) + 25=
100a₁(a₁+1) + 25

Al calcular el cuadrado de un número que empiezan en 5

(5a₀ )² = (50 + a₀)²=
100(25 +a₀) + a₀²

Al calcular el productos de números de tres dígitos que empiezan con 1

(1a₁ a₀)(1b₁b₀) =
(100 + 10a₁ + a₀)(100 + 10 b₁ + b₀) =
10000 + 1000(a₁ + b₁) + 100(a₁b₁ + a₀ + b₀) +
10(a₁b₀+ a₀b₁) + a₀b₀

Multiplicar un número menor que 100 por 99

(a)(99) = 100 (a – 1) + (100 – a)