Montante's method

Montante's method

Montante's Method is a linear algebra method to calculate solutions to systems of linear equations, and finding matrix inverses, adjoints and determinants. It is named after its discoverer René Mario Montante.

Its main feature is working exclusively using integer arithmetic for integer matrices, which allows for exact results in computer implementations.

History

The method was developed in 1973 by René Mario Montante Pardo, from the Department of Mechanical and Electric Engineering of the Universidad Autónoma de Nuevo León, in Monterrey,México.

Method

The method is pivot-based, working through the matrix main diagonal and rewriting the matrix iteratively by using 2x2 determinants based on elements and pivot rows and columns. If the original matrix is integer, the method works using integers until the final step, yielding at worst rational results.

This is a pseudo-code implementation of a linear system solver for Ax=B using Montante's method:

Input: An "n"x"n+1" matrix "M" holding left(A|B ight). Output: An "n"x"n+1" matrix holding left(dI_n|x^prime ight) where I_n is the identity matrix of order n d is a scalar and frac{x^prime}{d} is the solution p0 ← 1 foreach t in 1 .. n pt ← mtt foreach i in 1 .. n except t foreach j in t+1 .. n mij ← ( pt * mij - mit * mtj ) / pt-1 mkt ← 0 forall k ≠ t mkk ← p forall k ≤ t return "M"

And an implementation in Ruby

def montante_solve( a ) nr = a.size nc = nr+1 # a must be n x n+1 m = Array.new # work on a copy (0 ... nr).each do |k| m [k] = Array.new(a [k] ) end p_pre = 1 # The previous pivot for t in ( 0 ... nr ) do p = m [t] [t] # The current pivot (0 .. t).each do |k| m [k] [k] = p end for i in 0 ... nr do for j in (t+1) ... nc do m [i] [j] = ( p * m [i] [j] - m [i] [t] * m [t] [j] ) / p_pre if i!=t end end p_pre = p (0 ... nr).each do |k| m [k] [t] = 0 end end return m end a = [ [2,-1,-3, 1, 3] , [1, 1,-2,-2, 2] , [3,-2, 1,-1,-2] , [1,-1, 1, 3, 1] ] p montante_solve( a )

Walkthrough

Given the following linear equation system with integer coefficients
:2x - y - 3z + w = 3 ,:x + y - 2z - 2w= 2 ,:3x - 2y + z - w= -2 qquad qquad (1):x - y + z + 3w= 1 ,
The augmented matrix (including the results column) is:

: A_0 = egin{pmatrix}2 & -1 & -3 & 1 & 3 \ 1 & 1 & -2 & -2 & 2 \3 & -2 & 1 & -1 &-2 \ 1 & -1 & 1 & 3 & 1end{pmatrix}

First iteration: keep the first row (pivot row) as-is and zero-out all but the first elements in the pivot column;

: A_1 = egin{pmatrix}2 & -1 & -3 & 1 & 3 \ 0 & cdots & cdots & cdots & cdots \0 & cdots & cdots & cdots & cdots\ 0 & cdots & cdots & cdots & cdotsend{pmatrix}

The current pivot p_1 = 2 at a_{11} (the upper-leftmost cell), and the "previous" pivot p_0 is 1.

Each of the elements in the rest of the matrix (except the pivot row and pivot column) are obtained by the formula

: a^1_{ij} leftarrow frac{ a_{ij} p_1 - a_{1j} a_{j1} }{p_0}

Thus

: A_1 = egin{pmatrix}2 & -1 & -3 & 1 & 3 \ 0 & 3 & -1 & -5 & 1 \0 & -1 & 11 & -5 &-13 \ 0 & -1 & 5 & 5 & -1end{pmatrix}

Second iteration: the new pivot is p_2 = 3 at a^1_{22}

Keep the second (pivot) row as-is, zero-out the second column except the diagonal element, replace all previous pivot elements with p_2. Then apply the determinant formula to the remaining elements, which form a submatrix holding columns 3 to 5 and lines 1, 3 and 4.

: a^2_{ij} leftarrow frac{ a^1_{ij} p_2 - a^1_{2j} a^1_{j2} }{p_1} qquad forall (i,j) in left{ 1,3,4 ight} imes left{ 3,4,5 ight}

: A_2 = egin{pmatrix}3 & 0 & -5 & -1 & 5 \ 0 & 3 & -1 & -5 & 1 \0 & 0 & 16 & -10 &-19 \ 0 & 0 & 7 & 5 & -1end{pmatrix}

Third iteration: as before, with pivot p_3 = 16 at a^2_{33}.

: A_3 = egin{pmatrix}16 & 0 & 0 & -22 & -5 \ 0 & 16 & 0 & -30 & -1 \0 & 0 & 16 & -10 & -19 \ 0 & 0 & 0 & 50 & 39 \end{pmatrix}

Fourth iteration:

: A_4 = egin{pmatrix}50 & 0 & 0 & 0 & 38\ 0 & 50 & 0 & 0 & 70\0 & 0 & 50 & 0 & -35\ 0 & 0 & 0 & 50 & 39 \end{pmatrix}

The solution to system (1) is then:

:x = frac {38}{50} qquad y = frac {70}{50} qquad z = frac {-35}{50} qquadw = frac {39}{50}


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia

  • Matrix (mathematics) — Specific elements of a matrix are often denoted by a variable with two subscripts. For instance, a2,1 represents the element at the second row and first column of a matrix A. In mathematics, a matrix (plural matrices, or less commonly matrixes)… …   Wikipedia

  • Moteur Crower à six temps — Le moteur Crower six temps est une variante à haut rendement d un moteur à combustion interne en phase de développement par Bruce Crower. Deux temps sont ajoutés aux quatre temps d un moteur classique à cycle de Beau de Rochas, ce qui en fait un… …   Wikipédia en Français

  • Venetian style shoe/References — See main article Venetian style shoe A bibliography of books, articles, websites, and photos about Venetian style shoes (VSS). All entries here should be substantially about VSS or its applications, or make significant points specifically about… …   Wikipedia

  • Junior dos Santos — Fiche d identité Nom complet Junior dos Santos Almeida Surnom Cigano JDS Nationalité …   Wikipédia en Français

  • DMX (rappeur) —  Pour l’article homonyme, voir DMX (éclairage).  DMX …   Wikipédia en Français

  • Dwayne Johnson — Pour les articles homonymes, voir Johnson et The Rock. Dwayne Johnson …   Wikipédia en Français

  • Dynastie Song/Traduction à faire — Modèle:Otheruses Sommaire 1 0 2 Histoire de la dynastie Song 2.1 Les Song du Nord 2.2 Les Song du Sud …   Wikipédia en Français

  • Sarah Trimmer — par Henry Howard Nom de naissance Kirby Naissance …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”