A Givens rotation is represented by a matrix of the form
where c = cos θ and s = sin θ appear at the intersections ith and jth rows and columns. That is, for fixed i>j, the non-zero elements of Givens matrix are given by:
The product G(i, j, θ)x represents a counterclockwise rotation of the vectorx in the (i, j) plane of θ radians, hence the name Givens rotation.
The main use of Givens rotations in numerical linear algebra is to introduce zeros[clarification needed] in vectors or matrices. This effect can, for example, be employed for computing the QR decomposition of a matrix. One advantage over Householder transformations is that they can easily be parallelised, and another is that often for very sparse matrices they have a lower operation count.
Stable calculation
When a Givens rotation matrix, G(i, j, θ), multiplies another matrix, A, from the left, G A, only rows i and j of A are affected. Thus we restrict attention to the following counterclockwise problem. Given a and b, find c = cos θ and s = sin θ such that
where is the length of the vector . Explicit calculation of θ is rarely necessary or desirable. Instead we directly seek c and s. An obvious solution would be
However, the computation for r may overflow or underflow. An alternative formulation avoiding this problem (Golub & Van Loan 1996, §5.1.8) is implemented as the hypot function in many programming languages.
The following Fortran code is a minimalistic implementation of Givens rotation for real numbers. If the input values 'a' or 'b' are frequently zero, the code may be optimized to handle these cases as presented here.
Furthermore, as Edward Anderson discovered in improving LAPACK, a previously overlooked numerical consideration is continuity. To achieve this, we require r to be positive.[2] The following MATLAB/GNU Octave code illustrates the algorithm.
function[c, s, r] = givens_rotation(a, b)ifb==0;c=sign(a);if(c==0);c=1.0;% Unlike other languages, MatLab's sign function returns 0 on input 0.end;s=0;r=abs(a);elseifa==0;c=0;s=-sign(b);r=abs(b);elseifabs(a)>abs(b);t=b/a;u=sign(a)*sqrt(1+t*t);c=1/u;s=-c*t;r=a*u;elset=a/b;u=sign(b)*sqrt(1+t*t);s=-1/u;c=t/u;r=b*u;endend
The IEEE 754copysign(x,y) function, provides a safe and cheap way to copy the sign of y to x. If that is not available, |x|⋅sgn(y), using the abs and sgn functions, is an alternative as done above.
Triangularization
Given the following 3×3 Matrix:
two iterations of the Givens rotation (note that the Givens rotation algorithm used here differs slightly from above) yield an upper triangular matrix in order to compute the QR decomposition.
In order to form the desired matrix, zeroing elements (2,1) and (3,2) is required; element (2,1) is zeroed first, using a rotation matrix of:
The following matrix multiplication results:
where
Using these values for c and s and performing the matrix multiplication above yields A2:
Zeroing element (3,2) finishes off the process. Using the same idea as before, the rotation matrix is:
Afterwards, the following matrix multiplication is:
where
Using these values for c and s and performing the multiplications results in A3:
This new matrix A3 is the upper triangular matrix needed to perform an iteration of the QR decomposition. Q is now formed using the transpose of the rotation matrices in the following manner:
Performing this matrix multiplication yields:
This completes two iterations of the Givens Rotation and calculating the QR decomposition can now be done.
Complex matrices
Another method can extend Givens rotations to complex matrices. A diagonal matrix whose diagonal elements have unit magnitudes but arbitrary phases is unitary. Let A be a matrix for which it is desired to make the ji element be zero using the rows and columns i and j>i. Let D be a diagonal matrix whose diagonal elements are one except the ii and jj diagonal elements which also have unit magnitude but have phases which are to be determined. The phases of the ii and jj elements of D can be chosen so as to make the ii and ji elements of the product matrix D A be real. Then a Givens rotation G can be chosen using the i and j>i rows and columns so as to make the ji element of the product matrix G D A be zero. Since a product of unitary matrices is unitary, the product matrix G D is unitary and so is any product of such matrix pair products.
In Clifford algebra
In Clifford algebra and its child structures such as geometric algebra, rotations are represented by bivectors. Givens rotations are represented by the exterior product of the basis vectors. Given any pair of basis vectors Givens rotations bivectors are:
When rotations are performed in the right order, the values of the rotation angles of the final frame will be equal to the Euler angles of the final frame in the corresponding convention. For example, an operator transforms the basis of the space into a frame with angles roll, pitch and yaw in the Tait–Bryan conventionz-x-y (convention in which the line of nodes is perpendicular to z and Y axes, also named Y-X′-Z″).
The meaning of the composition of two Givens rotations g ∘ f is an operator that transforms vectors first by f and then by g, being f and g rotations about one axis of basis of the space. This is similar to the extrinsic rotation equivalence for Euler angles.
Table of composed rotations
The following table shows the three Givens rotations equivalent to the different Euler angles conventions using extrinsic composition (composition of rotations about the basis axes) of active rotations and the right-handed rule for the positive sign of the angles.
The notation has been simplified in such a way that c1 means cos θ1 and s2 means sin θ2). The subindexes of the angles are the order in which they are applied using extrinsic composition (1 for intrinsic rotation, 2 for nutation, 3 for precession)
As rotations are applied just in the opposite order of the Euler angles table of rotations, this table is the same but swapping indexes 1 and 3 in the angles associated with the corresponding entry. An entry like zxy means to apply first the y rotation, then x, and finally z, in the basis axes.
All the compositions assume the right hand convention for the matrices that are multiplied, yielding the following results.
↑ The rotation matrix immediately below is not a Givens rotation. The matrix immediately below respects the right-hand rule and is this usual matrix one sees in Computer Graphics; however, a Givens rotation is simply a matrix as defined in the Matrix representation section above and does not necessarily respect the right-hand rule. The below matrix is actually the Givens rotation through an angle of -.
In mathematics, a spherical coordinate system is a coordinate system for three-dimensional space where the position of a given point in space is specified by three numbers, : the radial distance of the radial liner connecting the point to the fixed point of origin ; the polar angle θ of the radial line r; and the azimuthal angle φ of the radial line r.
Kinematics is a subfield of physics and mathematics, developed in classical mechanics, that describes the motion of points, bodies (objects), and systems of bodies without considering the forces that cause them to move. Kinematics, as a field of study, is often referred to as the "geometry of motion" and is occasionally seen as a branch of both applied and pure mathematics since it can be studied without considering the mass of a body or the forces acting upon it. A kinematics problem begins by describing the geometry of the system and declaring the initial conditions of any known values of position, velocity and/or acceleration of points within the system. Then, using arguments from geometry, the position, velocity and acceleration of any unknown parts of the system can be determined. The study of how forces act on bodies falls within kinetics, not kinematics. For further details, see analytical dynamics.
In linear algebra, an orthogonal matrix, or orthonormal matrix, is a real square matrix whose columns and rows are orthonormal vectors.
In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the second matrix. The resulting matrix, known as the matrix product, has the number of rows of the first and the number of columns of the second matrix. The product of matrices A and B is denoted as AB.
An ellipsoid is a surface that can be obtained from a sphere by deforming it by means of directional scalings, or more generally, of an affine transformation.
In mechanics and geometry, the 3D rotation group, often denoted SO(3), is the group of all rotations about the origin of three-dimensional Euclidean space under the operation of composition.
Unit quaternions, known as versors, provide a convenient mathematical notation for representing spatial orientations and rotations of elements in three dimensional space. Specifically, they encode information about an axis-angle rotation about an arbitrary axis. Rotation and orientation quaternions have applications in computer graphics, computer vision, robotics, navigation, molecular dynamics, flight dynamics, orbital mechanics of satellites, and crystallographic texture analysis.
In vector calculus, the Jacobian matrix of a vector-valued function of several variables is the matrix of all its first-order partial derivatives. When this matrix is square, that is, when the function takes the same number of variables as input as the number of vector components of its output, its determinant is referred to as the Jacobian determinant. Both the matrix and the determinant are often referred to simply as the Jacobian in literature.
In the mathematical field of differential geometry, a metric tensor is an additional structure on a manifold M that allows defining distances and angles, just as the inner product on a Euclidean space allows defining distances and angles there. More precisely, a metric tensor at a point p of M is a bilinear form defined on the tangent space at p, and a metric field on M consists of a metric tensor at each point p of M that varies smoothly with p.
In linear algebra, a QR decomposition, also known as a QR factorization or QU factorization, is a decomposition of a matrix A into a product A = QR of an orthonormal matrix Q and an upper triangular matrix R. QR decomposition is often used to solve the linear least squares (LLS) problem and is the basis for a particular eigenvalue algorithm, the QR algorithm.
An infinitesimal rotation matrix or differential rotation matrix is a matrix representing an infinitely small rotation.
In mathematics, the matrix exponential is a matrix function on square matrices analogous to the ordinary exponential function. It is used to solve systems of linear differential equations. In the theory of Lie groups, the matrix exponential gives the exponential map between a matrix Lie algebra and the corresponding Lie group.
In linear algebra, linear transformations can be represented by matrices. If is a linear transformation mapping to and is a column vector with entries, then
In linear algebra, a rotation matrix is a transformation matrix that is used to perform a rotation in Euclidean space. For example, using the convention below, the matrix
In linear algebra, an orthogonal transformation is a linear transformation T : V → V on a real inner product space V, that preserves the inner product. That is, for each pair u, v of elements of V, we have
In the theory of three-dimensional rotation, Rodrigues' rotation formula, named after Olinde Rodrigues, is an efficient algorithm for rotating a vector in space, given an axis and angle of rotation. By extension, this can be used to transform all three basis vectors to compute a rotation matrix in SO(3), the group of all rotation matrices, from an axis–angle representation. In terms of Lie theory, the Rodrigues' formula provides an algorithm to compute the exponential map from the Lie algebra so(3) to its Lie group SO(3).
A transversely isotropic material is one with physical properties that are symmetric about an axis that is normal to a plane of isotropy. This transverse plane has infinite planes of symmetry and thus, within this plane, the material properties are the same in all directions. Hence, such materials are also known as "polar anisotropic" materials. In geophysics, vertically transverse isotropy (VTI) is also known as radial anisotropy.
Spatial rotations in three dimensions can be parametrized using both Euler angles and unit quaternions. This article explains how to convert between the two representations. Actually this simple use of "quaternions" was first presented by Euler some seventy years earlier than Hamilton to solve the problem of magic squares. For this reason the dynamics community commonly refers to quaternions in this application as "Euler parameters".
In geometry, various formalisms exist to express a rotation in three dimensions as a mathematical transformation. In physics, this concept is applied to classical mechanics where rotational kinematics is the science of quantitative description of a purely rotational motion. The orientation of an object at a given instant is described with the same tools, as it is defined as an imaginary rotation from a reference placement in space, rather than an actually observed rotation from a previous placement in space.
In mathematics, the axis–angle representation parameterizes a rotation in a three-dimensional Euclidean space by two quantities: a unit vector e indicating the direction (geometry) of an axis of rotation, and an angle of rotation θ describing the magnitude and sense of the rotation about the axis. Only two numbers, not three, are needed to define the direction of a unit vector e rooted at the origin because the magnitude of e is constrained. For example, the elevation and azimuth angles of e suffice to locate it in any particular Cartesian coordinate frame.
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 11.3.1. Givens Method", Numerical Recipes: The Art of Scientific Computing (3rded.), New York: Cambridge University Press, ISBN978-0-521-88068-8
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
