Reduced row echelon form: Difference between revisions

Content added Content deleted
(→‎{{header|Wren}}: Added a sentance)
Line 2,553: Line 2,553:
rref(a);
rref(a);
matrix([1,0,0,0,1/2],[0,1,0,0,-1],[0,0,1,0,-1/2],[0,0,0,1,1],[0,0,0,0,0])</lang>
matrix([1,0,0,0,1/2],[0,1,0,0,-1],[0,0,1,0,-1/2],[0,0,0,1,1],[0,0,0,0,0])</lang>

=={{header|Nim}}==
===Using rationals===
To avoid rounding issues, we can use rationals and convert to floats only at the end.
<lang Nim>import rationals, strutils

type Fraction = Rational[int]

const Zero: Fraction = 0 // 1

type Matrix[M, N: static Positive] = array[M, array[N, Fraction]]


func toMatrix[M, N: static Positive](a: array[M, array[N, int]]): Matrix[M, N] =
## Convert a matrix of integers to a matrix of integer fractions.

for i in 0..a.high:
for j in 0..a[0].high:
result[i][j] = a[i][j] // 1


func transformToRref(mat: var Matrix) =
## Transform the given matrix to reduced row echelon form.

var lead = 0

for r in 0..<mat.M:

if lead >= mat.N: return

var i = r
while mat[i][lead] == Zero:
inc i
if i == mat.M:
i = r
inc lead
if lead == mat.N: return
swap mat[i], mat[r]

if (let d = mat[r][lead]; d) != Zero:
for item in mat[r].mitems:
item /= d

for i in 0..<mat.M:
if i != r:
let m = mat[i][lead]
for c in 0..<mat.N:
mat[i][c] -= mat[r][c] * m

inc lead


proc `$`(mat: Matrix): string =
## Display a matrix.

for row in mat:
var line = ""
for val in row:
line.addSep(" ", 0)
line.add val.toFloat.formatFloat(ffDecimal, 2).align(7)
echo line


#———————————————————————————————————————————————————————————————————————————————————————————————————

template runTest(mat: Matrix) =
## Run a test using matrix "mat".

echo "Original matrix:"
echo mat
echo "Reduced row echelon form:"
mat.transformToRref()
echo mat
echo ""


var m1 = [[ 1, 2, -1, -4],
[ 2, 3, -1, -11],
[-2, 0, -3, 22]].toMatrix()

var m2 = [[2, 0, -1, 0, 0],
[1, 0, 0, -1, 0],
[3, 0, 0, -2, -1],
[0, 1, 0, 0, -2],
[0, 1, -1, 0, 0]].toMatrix()

var m3 = [[1, 2, 3, 4, 3, 1],
[2, 4, 6, 2, 6, 2],
[3, 6, 18, 9, 9, -6],
[4, 8, 12, 10, 12, 4],
[5, 10, 24, 11, 15, -4]].toMatrix()

var m4 = [[0, 1],
[1, 2],
[0, 5]].toMatrix()

runTest(m1)
runTest(m2)
runTest(m3)
runTest(m4)</lang>

{{out}}
<pre>Original matrix:
1.00 2.00 -1.00 -4.00
2.00 3.00 -1.00 -11.00
-2.00 0.00 -3.00 22.00

Reduced row echelon form:
1.00 0.00 0.00 -8.00
0.00 1.00 0.00 1.00
0.00 0.00 1.00 -2.00


Original matrix:
2.00 0.00 -1.00 0.00 0.00
1.00 0.00 0.00 -1.00 0.00
3.00 0.00 0.00 -2.00 -1.00
0.00 1.00 0.00 0.00 -2.00
0.00 1.00 -1.00 0.00 0.00

Reduced row echelon form:
1.00 0.00 0.00 0.00 -1.00
0.00 1.00 0.00 0.00 -2.00
0.00 0.00 1.00 0.00 -2.00
0.00 0.00 0.00 1.00 -1.00
0.00 0.00 0.00 0.00 0.00


Original matrix:
1.00 2.00 3.00 4.00 3.00 1.00
2.00 4.00 6.00 2.00 6.00 2.00
3.00 6.00 18.00 9.00 9.00 -6.00
4.00 8.00 12.00 10.00 12.00 4.00
5.00 10.00 24.00 11.00 15.00 -4.00

Reduced row echelon form:
1.00 2.00 0.00 0.00 3.00 4.00
0.00 0.00 1.00 0.00 0.00 -1.00
0.00 0.00 0.00 1.00 0.00 0.00
0.00 0.00 0.00 0.00 0.00 0.00
0.00 0.00 0.00 0.00 0.00 0.00


Original matrix:
0.00 1.00
1.00 2.00
0.00 5.00

Reduced row echelon form:
1.00 0.00
0.00 1.00
0.00 0.00</pre>

===Using floats===
When using floats, we have to be careful when doing comparisons. The previous program adapted to use floats instead of rationals may give wrong results. This would be the case with the second matrix. To get the right result, we have to do a comparison to an epsilon rather than zero. Here is the program modified to work with floats:
<lang Nim>import strutils

const Eps = 1e-10

type Matrix[M, N: static Positive] = array[M, array[N, float]]


func toMatrix[M, N: static Positive](a: array[M, array[N, int]]): Matrix[M, N] =
## Convert a matrix of integers to a matrix of floats.
for i in 0..a.high:
for j in 0..a[0].high:
result[i][j] = a[i][j].toFloat


func transformToRref(mat: var Matrix) =
## Transform the given matrix to reduced row echelon form.

var lead = 0

for r in 0..<mat.M:

if lead >= mat.N: return

var i = r
while mat[i][lead] == 0:
inc i
if i == mat.M:
i = r
inc lead
if lead == mat.N: return
swap mat[i], mat[r]

let d = mat[r][lead]
if abs(d) > Eps: # Checking "d != 0" will give wrong results in some cases.
for item in mat[r].mitems:
item /= d

for i in 0..<mat.M:
if i != r:
let m = mat[i][lead]
for c in 0..<mat.N:
mat[i][c] -= mat[r][c] * m

inc lead


proc `$`(mat: Matrix): string =
## Display a matrix.

for row in mat:
var line = ""
for val in row:
line.addSep(" ", 0)
line.add val.formatFloat(ffDecimal, 2).align(7)
echo line


#———————————————————————————————————————————————————————————————————————————————————————————————————

template runTest(mat: Matrix) =
## Run a test using matrix "mat".

echo "Original matrix:"
echo mat
echo "Reduced row echelon form:"
mat.transformToRref()
echo mat
echo ""


var m1 = [[ 1, 2, -1, -4],
[ 2, 3, -1, -11],
[-2, 0, -3, 22]].toMatrix()

var m2 = [[2, 0, -1, 0, 0],
[1, 0, 0, -1, 0],
[3, 0, 0, -2, -1],
[0, 1, 0, 0, -2],
[0, 1, -1, 0, 0]].toMatrix()

var m3 = [[1, 2, 3, 4, 3, 1],
[2, 4, 6, 2, 6, 2],
[3, 6, 18, 9, 9, -6],
[4, 8, 12, 10, 12, 4],
[5, 10, 24, 11, 15, -4]].toMatrix()

var m4 = [[0, 1],
[1, 2],
[0, 5]].toMatrix()

runTest(m1)
runTest(m2)
runTest(m3)
runTest(m4)</lang>

{{Out}}
Same result as that of the program working with rationals (at least for the matrices used here).


=={{header|Objeck}}==
=={{header|Objeck}}==
Retrieved from "https://rosettacode.org/wiki/Reduced_row_echelon_form"