Polynomial Curve Fitting
polyfit finds the coefficients of a polynomial that fits a set of data in a least-squares sense:p = polyfit(x,y,n)
x and y are vectors containing the x and y data to be fitted, and n is the degree of the polynomial to return. For example, consider the x-y test datax = [1 2 3 4 5];
y = [5.5 43.1 128 290.7 498.4];
A third degree polynomial that approximately fits the data isp = polyfit(x,y,3)
p =
-0.1917 31.5821 -60.3262 35.3400
Compute the values of the polyfit estimate over a finer range, and plot the estimate over the real data values for comparison:x2 = 1:.1:5;
y2 = polyval(p,x2);
plot(x,y,'o',x2,y2)
grid on
Gaussian elimination
In linear algebra, Gaussian elimination (also known as row reduction) is an algorithm for solving systems of linear equations. It is usually understood as a sequence of operations performed on the associated matrix of coefficients. This method can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix. The method is named after Carl Friedrich Gauss, although it was known to Chinese mathematicians as early as 179 AD (see History section).
To perform row reduction on a matrix, one uses a sequence of elementary row operations to modify the matrix until the lower left-hand corner of the matrix is filled with zeros, as much as possible. There are three types of elementary row operations: 1) Swapping two rows, 2) Multiplying a row by a non-zero number, 3) Adding a multiple of one row to another row. Using these operations, a matrix can always be transformed into an upper triangular matrix, and in fact one that is in row echelon form. Once all of the leading coefficients (the left-most non-zero entry in each row) are 1, and in every column containing a leading coefficient has zeros elsewhere, the matrix is said to be in reduced row echelon form. This final form is unique; in other words, it is independent of the sequence of row operations used. For example, in the following sequence of row operations (where multiple elementary operations might be done at each step), the third and fourth matrices are the ones in row echelon form, and the final matrix is the unique reduced row echelon form.
Using row operations to convert a matrix into reduced row echelon form is sometimes called Gauss–Jordan elimination. Some authors use the term Gaussian elimination to refer to the process until it has reached its upper triangular, or (non-reduced) row echelon form. For computational reasons, when solving systems of linear equations, it is sometimes preferable to stop row operations before the matrix is completely reduced.
Definitions and example of algorithm
The process of row reduction makes use of elementary row operations, and can be divided into two parts. The first part (sometimes called Forward Elimination) reduces a given system to row echelon form, from which one can tell whether there are no solutions, a unique solution, or infinitely many solutions. The second part (sometimes called back substitution) continues to use row operations until the solution is found; in other words, it puts the matrix into reduced row echelon form.
Another point of view, which turns out to be very useful to analyze the algorithm, is that row reduction produces a matrix decomposition of the original matrix. The elementary row operations may be viewed as the multiplication on the left of the original matrix by elementary matrices. Alternatively, a sequence of elementary operations that reduces a single row may be viewed as multiplication by a Frobenius matrix. Then the first part of the algorithm computes an LU decomposition, while the second part writes the original matrix as the product of a uniquely determined invertible matrix and a uniquely determined reduced row echelon matrix.
Row operations
There are three types of elementary row operations which may be performed on the rows of a matrix:
Type 1: Swap the positions of two rows.
Type 2: Multiply a row by a nonzero scalar.
Type 3: Add to one row a scalar multiple of another.
If the matrix is associated to a system of linear equations, then these operations do not change the solution set. Therefore, if one's goal is to solve a system of linear equations, then using these row operations could make the problem easier.
Echelon form[edit]
Main article: Row echelon form
For each row in a matrix, if the row does not consist of only zeros, then the left-most non-zero entry is called the leading coefficient (or pivot) of that row. So if two leading coefficients are in the same column, then a row operation of type 3 (see above) could be used to make one of those coefficients zero. Then by using the row swapping operation, one can always order the rows so that for every non-zero row, the leading coefficient is to the right of the leading coefficient of the row above. If this is the case, then matrix is said to be in row echelon form. So the lower left part of the matrix contains only zeros, and all of the zero rows are below the non-zero rows. The word "echelon" is used here because one can roughly think of the rows being ranked by their size, with the largest being at the top and the smallest being at the bottom.
For example, the following matrix is in row echelon form, and its leading coefficients are shown in red.
It is in echelon form because the zero row is at the bottom, and the leading coefficient of the second row (in the third column), is to the right of the leading coefficient of the first row (in the second column).
A matrix is said to be in reduced row echelon form if furthermore all of the leading coefficients are equal to 1 (which can be achieved by using the elementary row operation of type 2), and in every column containing a leading coefficient, all of the other entries in that column are zero (which can be achieved by using elementary row operations of type 3).
Example of the algorithm[edit]
Suppose the goal is to find and describe the set of solutions to the following system of linear equations:
The table below is the row reduction process applied simultaneously to the system of equations, and its associated augmented matrix. In practice, one does not usually deal with the systems in terms of equations but instead makes use of the augmented matrix, which is more suitable for computer manipulations. The row reduction procedure may be summarized as follows: eliminate x from all equations below 
, and then eliminate y from all equations below 
. This will put the system into triangular form. Then, using back-substitution, each unknown can be solved for.
System of equations
Row operations
Augmented matrix
The matrix is now in echelon form (also called triangular form)
The second column describes which row operations have just been performed. So for the first step, the x is eliminated from by adding 
to . Next x is eliminated from 
by adding to . These row operations are labelled in the table as
Once y is also eliminated from the third row, the result is a system of linear equations in triangular form, and so the first part of the algorithm is complete. From a computational point of view, it is faster to solve the variables in reverse order, a process known as back-substitution. One sees the solution is z = -1, y = 3, and x = 2. So there is a unique solution to the original system of equations.
Instead of stopping once the matrix is in echelon form, one could continue until the matrix is in reduced row echelon form, as it is done in the table. The process of row reducing until the matrix is reduced is sometimes referred to as Gauss-Jordan elimination, to distinguish it from stopping after reaching echelon form.
History
The method of Gaussian elimination appears in the Chinese mathematical text Chapter Eight Rectangular Arrays of The Nine Chapters on the Mathematical Art. Its use is illustrated in eighteen problems, with two to five equations. The first reference to the book by this title is dated to 179 CE, but parts of it were written as early as approximately 150 BCE.It was commented on by Liu Hui in the 3rd century.
The method in Europe stems from the notes of Isaac Newton.In 1670, he wrote that all the algebra books known to him lacked a lesson for solving simultaneous equations, which Newton then supplied. Cambridge University eventually published the notes as Arithmetica Universalis in 1707 long after Newton left academic life. The notes were widely imitated, which made (what is now called) Gaussian elimination a standard lesson in algebra textbooks by the end of the 18th century. Carl Friedrich Gauss in 1810 devised a notation[which?] for symmetric elimination that was adopted in the 19th century by professional hand computers to solve the normal equations of least-squares problems. The algorithm that is taught in high school was named for Gauss only in the 1950s as a result of confusion over the history of the subject.
Some authors use the term Gaussian elimination to refer only to the procedure until the matrix is in echelon form, and use the term Gauss-Jordan elimination to refer to the procedure which ends in reduced echelon form. The name is used because it is a variation of Gaussian elimination as described by Wilhelm Jordan in 1887. However, the method also appears in an article by Clasen published in the same year. Jordan and Clasen probably discovered Gauss–Jordan elimination independently.
A matrix may be classified by types. It is possible for a matrix to belong to more than one type.
- A row matrix is a matrix with only one row.
E is a row matrix of order 1 × 1
B is a row matrix of order 1 × 3
- A column matrix is a matrix with only one column.
C is a column matrix of order 1 × 1
D is a column matrix of order 2 × 1
A column matrix of order 2 ×1 is also called a vector matrix.
- A zero matrix or a null matrix is a matrix that has all its elements zero.
O is a zero matrix of order 2 × 3
- A square matrix is a matrix with an equal number of rows and columns.
T is a square matrix of order 2 × 2
V is a square matrix of order 3 × 3
- A diagonal matrix is a square matrix that has all its elements zero except for those in the diagonal from top left to bottom right; which is known as the leading diagonal of the matrix.
B is a diagonal matrix
- A unit matrix is a diagonal matrix whose elements in the diagonal are all ones.
P is a unit matrix.
In linear algebra, a matrix is in echelon form if it has the shape resulting of a Gaussian elimination. Row echelon form means that Gaussian elimination has operated on the rows and column echelon form means that Gaussian elimination has operated on the columns. In other words, a matrix is in column echelon form if its transpose is in row echelon form. Therefore only row echelon forms are considered in the remainder of this article. The similar properties of column echelon form are easily deduced by transposing all the matrices.
Specifically, a matrix is in row echelon form if
All nonzero rows (rows with at least one nonzero element) are above any rows of all zeroes (all zero rows, if any, belong at the bottom of the matrix).
The leading coefficient (the first nonzero number from the left, also called the pivot) of a nonzero row is always strictly to the right of the leading coefficient of the row above it (some texts add the condition that the leading coefficient must be 1.)
All entries in a column below a leading entry are zeroes (implied by the first two criteria).
This is an example of a 3×5 matrix in row echelon form:
Reduced row echelon form
A matrix is in reduced row echelon form (also called row canonical form) if it satisfies the following conditions:
It is in row echelon form.
Every leading coefficient is 1 and is the only nonzero entry in its column.
The reduced row echelon form of a matrix may be computed by Gauss–Jordan elimination. Unlike the row echelon form, the reduced row echelon form of a matrix is unique and does not depend on the algorithm used to compute it.
This is an example of a matrix in reduced row echelon form:
Note that this does not always mean that the left of the matrix will be an identity matrix, as this example shows.
For matrices with integer coefficients, the Hermite normal form is a row echelon form that may be computed using Euclidean division and without introducing any rational number nor denominator. On the other hand, the reduced echelon form of a matrix with integer coefficients generally contains non-integer entries.
Transformation to row echelon form
By means of a finite sequence of elementary row operations, called Gaussian elimination, any matrix can be transformed to row echelon form. Since elementary row operations preserve the row space of the matrix, the row space of the row echelon form is the same as that of the original matrix.
The resulting echelon form is not unique; for example, any multiple by a scalar of a matrix in echelon form is also an echelon form of the same matrix. However, every matrix has a unique reduced row echelon form. This means that the nonzero rows of the reduced row echelon form are the unique reduced row echelon generating set for the row space of the original matrix.
Systems of linear equations
A system of linear equations is said to be in row echelon form if its augmented matrix is in row echelon form. Similarly, a system of equations is said to be in reduced row echelon form or canonical form if its augmented matrix is in reduced row echelon form.
The canonical form may be viewed as an explicit solution of the linear system. In fact, the system is inconsistent, if and only if one of the equations of the canonical form is reduced to 1 = 0. Otherwise, regrouping in the right hand side all the terms of the equations, but the leading ones expresses the variables corresponding to the pivots as constants or linear functions of the other variables, if any.
Matrix (mathematics)
Each element of a matrix is often denoted by a variable with two subscripts. For instance, a2,1 represents the element at the second row and first column of a matrixA.
- A matrix (plural matrices) is a rectangular array of numbers, symbols, or expressions, arranged in rows and columns.The individual items in a matrix are called its elements or entries. An example of a matrix with 2 rows and 3 columns is -->
- Matrices of the same size can be added or subtracted element by element. But the rule for matrix multiplication is that two matrices can be multiplied only when the number of columns in the first equals the number of rows in the second. A major application of matrices is to represent linear transformations, that is, generalizations of linear functions such as f(x) = 4x. For example, the rotation of vectors in three dimensional space is a linear transformation which can be represented by a rotation matrix R. If v is a column vector (a matrix with only one column) describing the position of a point in space, the product Rv is a column vector describing the position of that point after a rotation. The product of two matrices is a matrix that represents the composition of two linear transformations. Another application of matrices is in the solution of a system of linear equations. If the matrix is square, it is possible to deduce some of its properties by computing its determinant. For example, a square matrix has an inverse if and only if its determinant is not zero. Eigenvalues and eigenvectors provide insight into the geometry of linear transformations.
Applications of matrices are found in most scientific fields. In every branch of physics, including classical mechanics, optics, electromagnetism, quantum mechanics, and quantum electrodynamics, they are used to study physical phenomena, such as the motion of rigid bodies. In computer graphics, they are used to project a 3-dimensional image onto a 2-dimensional screen. In probability theory and statistics, stochastic matrices are used to describe sets of probabilities; for instance, they are used within the PageRank algorithm that ranks the pages in a Google search.[4] Matrix calculus generalizes classical analytical notions such as derivatives and exponentials to higher dimensions.
A major branch of numerical analysis is devoted to the development of efficient algorithms for matrix computations, a subject that is centuries old and is today an expanding area of research. Matrix decomposition methods simplify computations, both theoretically and practically. Algorithms that are tailored to particular matrix structures, such as sparse matrices and near-diagonal matrices, expedite computations in finite element method and other computations. Infinite matrices occur in planetary theory and in atomic theory. A simple example of an infinite matrix is the matrix representing the derivative operator, which acts on the Taylor series of a function.
Linear algebra is the branch of mathematics concerning vector spaces and linear mappings between such spaces. It is the study of lines, planes, and subspaces and their intersections using algebra. Linear algebra assigns vectors as the coordinates of points in a space, so that operations on the vectors define operations on the points in the space.
The set of points with coordinates that satisfy a linear equation form a hyperplane in an n-dimensional space. The conditions under which a set of n hyperplanes intersect in a single point is an important focus of study in Linear algebra. Such an investigation is initially motivated by a system of linear equations containing several unknowns. Such equations are naturally represented using the formalism of matrices and vectors.
Linear algebra is central to both pure and applied mathematics. For instance, abstract algebra arises by relaxing the axioms of a vector space, leading to a number of generalizations.Functional analysis studies the infinite-dimensional version of the theory of vector spaces. Combined with calculus, linear algebra facilitates the solution of linear systems of differential equations. Techniques from linear algebra are also used in analytic geometry, engineering, physics, natural sciences, computer science, computer animation, and the social sciences(particularly in economics). Because linear algebra is such a well-developed theory, nonlinear mathematical models are sometimes approximated by linear ones.
