Analysis
Gaussian elimination to solve a system of n equations for n unknowns requires n(n-1) / 2 divisions, (2n3 + 3n2 − 5n)/6 multiplications, and (2n3 + 3n2 − 5n)/6 subtractions, for a total of approximately 2n3 / 3 operations. Thus it has arithmetic complexity of O(n3). However, the intermediate entries can grow exponentially large, so it has exponential bit complexity.
This algorithm can be used on a computer for systems with thousands of equations and unknowns. However, the cost becomes prohibitive for systems with millions of equations. These large systems are generally solved using iterative methods. Specific methods exist for systems whose coefficients follow a regular pattern (see system of linear equations).
The Gaussian elimination can be performed over any field.
Gaussian elimination is numerically stable for diagonally dominant or positive-definite matrices. For general matrices, Gaussian elimination is usually considered to be stable in practice if you use partial pivoting as described below, even though there are examples for which it is unstable.
Read more about this topic: Gaussian Elimination
Famous quotes containing the word analysis:
“... the big courageous acts of life are those one never hears of and only suspects from having been through like experience. It takes real courage to do battle in the unspectacular task. We always listen for the applause of our co-workers. He is courageous who plods on, unlettered and unknown.... In the last analysis it is this courage, developing between man and his limitations, that brings success.”
—Alice Foote MacDougall (1867–1945)
“Cubism had been an analysis of the object and an attempt to put it before us in its totality; both as analysis and as synthesis, it was a criticism of appearance. Surrealism transmuted the object, and suddenly a canvas became an apparition: a new figuration, a real transfiguration.”
—Octavio Paz (b. 1914)
“Analysis as an instrument of enlightenment and civilization is good, in so far as it shatters absurd convictions, acts as a solvent upon natural prejudices, and undermines authority; good, in other words, in that it sets free, refines, humanizes, makes slaves ripe for freedom. But it is bad, very bad, in so far as it stands in the way of action, cannot shape the vital forces, maims life at its roots. Analysis can be a very unappetizing affair, as much so as death.”
—Thomas Mann (1875–1955)