summaryrefslogtreecommitdiffstats
path: root/src/math
diff options
context:
space:
mode:
authorKore Nordmann <github@kore-nordmann.de>2006-08-17 11:49:04 +0000
committerKore Nordmann <github@kore-nordmann.de>2006-08-17 11:49:04 +0000
commit24758cba490f1670961042c6470ad7579af1f8c1 (patch)
treef36c9879c84cf7d35fc34d914a35508d7066e021 /src/math
parent441e0054ad7b4f38d4596cf3ceda08ec00cc2127 (diff)
downloadzetacomponents-graph-24758cba490f1670961042c6470ad7579af1f8c1.zip
zetacomponents-graph-24758cba490f1670961042c6470ad7579af1f8c1.tar.gz
- Fixed matrices to use parameter order <row>, <column>
- Added dataset which builds polygon of defined order for set of points # Using least squares algorithm - Added method to solve a subset of nonlinear equatations to matrix class # Using Gauss-Newton algorithm
Diffstat (limited to 'src/math')
-rw-r--r--src/math/matrix.php254
-rw-r--r--src/math/polynom.php19
2 files changed, 222 insertions, 51 deletions
diff --git a/src/math/matrix.php b/src/math/matrix.php
index f64d7e4..eed5c5b 100644
--- a/src/math/matrix.php
+++ b/src/math/matrix.php
@@ -15,10 +15,10 @@
class ezcGraphMatrix
{
- protected $columns;
-
protected $rows;
+ protected $columns;
+
protected $matrix;
/**
@@ -28,15 +28,15 @@ class ezcGraphMatrix
* define the initial matrix values. If no array is given an identity
* matrix is created.
*
- * @param int $columns Number of columns
* @param int $rows Number of rows
+ * @param int $columns Number of columns
* @param array $values Array with values
* @return void
*/
- public function __construct( $columns = 3, $rows = 3, array $values = null )
+ public function __construct( $rows = 3, $columns = 3, array $values = null )
{
- $this->columns = max( 2, (int) $columns );
- $this->rows = max( 2, (int) $rows );
+ $this->rows = max( 1, (int) $rows );
+ $this->columns = max( 1, (int) $columns );
if ( $values !== null )
{
@@ -58,9 +58,9 @@ class ezcGraphMatrix
*/
public function fromArray( array $values )
{
- for ( $i = 0; $i < $this->columns; ++$i )
+ for ( $i = 0; $i < $this->rows; ++$i )
{
- for ( $j = 0; $j < $this->rows; ++$j )
+ for ( $j = 0; $j < $this->columns; ++$j )
{
$this->matrix[$i][$j] =
( isset( $values[$i][$j] )
@@ -81,9 +81,9 @@ class ezcGraphMatrix
*/
public function init()
{
- for ( $i = 0; $i < $this->columns; ++$i )
+ for ( $i = 0; $i < $this->rows; ++$i )
{
- for ( $j = 0; $j < $this->rows; ++$j )
+ for ( $j = 0; $j < $this->columns; ++$j )
{
$this->matrix[$i][$j] = ( $i === $j ? 1 : 0 );
}
@@ -93,23 +93,23 @@ class ezcGraphMatrix
}
/**
- * Returns number of columns
+ * Returns number of rows
*
- * @return int Number of columns
+ * @return int Number of rows
*/
- public function columns()
+ public function rows()
{
- return $this->columns;
+ return $this->rows;
}
/**
- * Returns number of rows
+ * Returns number of columns
*
- * @return int Number of rows
+ * @return int Number of columns
*/
- public function rows()
+ public function columns()
{
- return $this->rows;
+ return $this->columns;
}
/**
@@ -117,18 +117,21 @@ class ezcGraphMatrix
*
* Returns the value of the matrix at the given position
*
- * @param int $i Row
- * @param int $j Column
+ * @param int $i Column
+ * @param int $j Row
* @return float Matrix value
*/
public function get( $i, $j )
{
- if ( !isset( $this->matrix[$i][$j] ) )
+ if ( ( $i < 0 ) ||
+ ( $i >= $this->rows ) ||
+ ( $j < 0 ) ||
+ ( $j >= $this->columns ) )
{
- throw new ezcGraphMatrixOutOfBoundingsException( $this->columns, $this->rows, $i, $j );
+ throw new ezcGraphMatrixOutOfBoundingsException( $this->rows, $this->columns, $i, $j );
}
- return $this->matrix[$i][$j];
+ return ( !isset( $this->matrix[$i][$j] ) ? .0 : $this->matrix[$i][$j] );
}
/**
@@ -136,16 +139,19 @@ class ezcGraphMatrix
*
* Sets the value of the matrix at the given position
*
- * @param int $i Row
- * @param int $j Column
+ * @param int $i Column
+ * @param int $j Row
* @param float $value Value
* @return ezcGraphMatrix Updated matrix
*/
public function set( $i, $j, $value )
{
- if ( !isset( $this->matrix[$i][$j] ) )
+ if ( ( $i < 0 ) ||
+ ( $i >= $this->rows ) ||
+ ( $j < 0 ) ||
+ ( $j >= $this->columns ) )
{
- throw new ezcGraphMatrixOutOfBoundingsException( $this->columns, $this->rows, $i, $j );
+ throw new ezcGraphMatrixOutOfBoundingsException( $this->rows, $this->columns, $i, $j );
}
$this->matrix[$i][$j] = $value;
@@ -163,15 +169,15 @@ class ezcGraphMatrix
*/
public function add( ezcGraphMatrix $matrix )
{
- if ( ( $this->columns !== $matrix->columns() ) ||
- ( $this->rows !== $matrix->rows() ) )
+ if ( ( $this->rows !== $matrix->rows() ) ||
+ ( $this->columns !== $matrix->columns() ) )
{
- throw new ezcGraphMatrixInvalidDimensionsException( $this->columns, $this->rows, $matrix->columns(), $matrix->rows() );
+ throw new ezcGraphMatrixInvalidDimensionsException( $this->rows, $this->columns, $matrix->rows(), $matrix->columns() );
}
- for ( $i = 0; $i < $this->columns; ++$i )
+ for ( $i = 0; $i < $this->rows; ++$i )
{
- for ( $j = 0; $j < $this->rows; ++$j )
+ for ( $j = 0; $j < $this->columns; ++$j )
{
$this->matrix[$i][$j] += $matrix->get( $i, $j );
}
@@ -190,15 +196,15 @@ class ezcGraphMatrix
*/
public function diff( ezcGraphMatrix $matrix )
{
- if ( ( $this->columns !== $matrix->columns() ) ||
- ( $this->rows !== $matrix->rows() ) )
+ if ( ( $this->rows !== $matrix->rows() ) ||
+ ( $this->columns !== $matrix->columns() ) )
{
- throw new ezcGraphMatrixInvalidDimensionsException( $this->columns, $this->rows, $matrix->columns(), $matrix->rows() );
+ throw new ezcGraphMatrixInvalidDimensionsException( $this->rows, $this->columns, $matrix->rows(), $matrix->columns() );
}
- for ( $i = 0; $i < $this->columns; ++$i )
+ for ( $i = 0; $i < $this->rows; ++$i )
{
- for ( $j = 0; $j < $this->rows; ++$j )
+ for ( $j = 0; $j < $this->columns; ++$j )
{
$this->matrix[$i][$j] -= $matrix->get( $i, $j );
}
@@ -219,9 +225,9 @@ class ezcGraphMatrix
{
$scalar = (float) $scalar;
- for ( $i = 0; $i < $this->columns; ++$i )
+ for ( $i = 0; $i < $this->rows; ++$i )
{
- for ( $j = 0; $j < $this->rows; ++$j )
+ for ( $j = 0; $j < $this->columns; ++$j )
{
$this->matrix[$i][$j] *= $scalar;
}
@@ -242,9 +248,9 @@ class ezcGraphMatrix
$this->matrix = array();
- for ( $i = 0; $i < $this->columns; ++$i )
+ for ( $i = 0; $i < $this->rows; ++$i )
{
- for ( $j = 0; $j < $this->rows; ++$j )
+ for ( $j = 0; $j < $this->columns; ++$j )
{
$this->matrix[$i][$j] = $matrix->get( $j, $i );
}
@@ -270,14 +276,14 @@ class ezcGraphMatrix
throw new ezcGraphMatrixInvalidDimensionsException( $this->columns, $this->rows, $mColumns, $mRows );
}
- $result = new ezcGraphMatrix( $mRows, $mRows );
+ $result = new ezcGraphMatrix( $this->rows, $mColumns );
- for ( $i = 0; $i < $this->columns; ++$i )
+ for ( $i = 0; $i < $this->rows; ++$i )
{
- for ( $j = 0; $j < $mRows; ++$j )
+ for ( $j = 0; $j < $mColumns; ++$j )
{
$sum = 0;
- for ( $k = 0; $k < $mColumns; ++$k ) {
+ for ( $k = 0; $k < $mRows; ++$k ) {
$sum += $this->matrix[$i][$k] * $matrix->get( $k, $j );
}
@@ -287,5 +293,163 @@ class ezcGraphMatrix
return $result;
}
+
+ /**
+ * Solve nonlinear equatation
+ *
+ * Tries to solve equatation given by two matrices, with assumption, that:
+ * A * x = B
+ * where $this is A, and the paramenter B. x is cosnidered as a vector
+ * x = ( x^n, x^(n-1), ..., x^2, x, 1 )
+ *
+ * Will return a polynomial solution for x.
+ *
+ * See: http://en.wikipedia.org/wiki/Gauss-Newton_algorithm
+ *
+ * @param ezcGraphMatrix $matrix B
+ * @return ezcGraphPolygon Solution of equatation
+ */
+ public function solveNonlinearEquatation( ezcGraphMatrix $matrix )
+ {
+ // Build complete equatation
+ $equatation = new ezcGraphMatrix( $this->rows, $columns = ( $this->columns + 1 ) );
+ for ( $i = 0; $i < $this->rows; ++$i )
+ {
+ for ( $j = 0; $j < $this->columns; ++$j )
+ {
+ $equatation->set( $i, $j, $this->matrix[$i][$j] );
+ }
+ $equatation->set( $i, $this->columns, $matrix->get( $i, 0 ) );
+ }
+
+ // Compute upper triangular matrix on left side of equatation
+ for ( $i = 0; $i < ( $this->rows - 1 ); ++$i )
+ {
+ for ( $j = $i + 1; $j < $this->rows; ++$j )
+ {
+ if ( $equatation->get( $j, $i ) !== 0 )
+ {
+ if ( $equatation->get( $j, $i ) == 0 )
+ {
+ $factor = 0;
+ }
+ else
+ {
+ $factor = -( $equatation->get( $i, $i ) / $equatation->get( $j, $i ) );
+ }
+
+ for ( $k = $i; $k < $columns; ++$k )
+ {
+ $equatation->set( $j, $k, $equatation->get( $i, $k ) + $factor * $equatation->get( $j, $k ) );
+ }
+ }
+ }
+ }
+
+ // Normalize values on left side matrix diagonale
+ for ( $i = 0; $i < $this->rows; ++$i )
+ {
+ if ( ( ( $value = $equatation->get( $i, $i ) ) != 1 ) &&
+ ( $value != 0 ) )
+ {
+ $factor = 1 / $value;
+ for ( $k = $i; $k < $columns; ++$k )
+ {
+ $equatation->set( $i, $k, $equatation->get( $i, $k ) * $factor );
+ }
+ }
+ }
+
+ // Build up solving polynom
+ $polynom = new ezcGraphPolynom();
+ for ( $i = ( $this->rows - 1 ); $i >= 0; --$i )
+ {
+ for ( $j = $i + 1; $j < $this->columns; ++$j )
+ {
+ $equatation->set(
+ $i,
+ $this->columns,
+ $equatation->get( $i, $this->columns ) + ( -$equatation->get( $i, $j ) * $polynom->get( $j ) )
+ );
+ $equatation->set( $i, $j, 0 );
+ }
+ $polynom->set( $i, $equatation->get( $i, $this->columns ) );
+ }
+
+ return $polynom;
+ }
+
+ public function __toString()
+ {
+ $string = sprintf( "%d x %d matrix:\n", $this->rows, $this->columns );
+
+ for ( $i = 0; $i < $this->rows; ++$i )
+ {
+ $string .= '| ';
+ for ( $j = 0; $j < $this->columns; ++$j )
+ {
+ $string .= sprintf( '%04.2f ', $this->get( $i, $j ) );
+ }
+ $string .= "|\n";
+ }
+
+ return $string;
+ }
+
+ public function LRdecomposition()
+ {
+ /**
+ * Use Cholesky-Crout algorithm to get LR decomposition
+ *
+ * Input: Matrix A ($this)
+ *
+ * For i = 1 To n
+ * For j = i To n
+ * R(i,j)=A(i,j)
+ * For k = 1 TO i-1
+ * R(i,j)-=L(i,k)*R(k,j)
+ * end
+ * end
+ * For j=i+1 To n
+ * L(j,i)= A(j,i)
+ * For k = 1 TO i-1
+ * L(j,i)-=L(j,k)*R(k,i)
+ * end
+ * L(j,i)/=R(i,i)
+ * end
+ * end
+ *
+ * Output: matrices L,R
+ */
+ $l = new ezcGraphMatrix( $this->columns, $this->rows );
+ $r = new ezcGraphMatrix( $this->columns, $this->rows );
+
+ for ( $i = 0; $i < $this->columns; ++$i )
+ {
+ for ( $j = $i; $j < $this->rows; ++$j )
+ {
+ $r->set( $i, $j, $this->matrix[$i][$j] );
+ for ( $k = 0; $k <= ( $i - 1 ); ++$k )
+ {
+ $r->set( $i, $j, $r->get( $i, $j ) - $l->get( $i, $k ) * $r->get( $k, $j ) );
+ }
+ }
+
+ for ( $j = $i + 1; $j < $this->rows; ++$j )
+ {
+ $l->set( $j, $i, $this->matrix[$j][$i] );
+ for ( $k = 0; $k <= ( $i - 1 ); ++$k )
+ {
+ $l->set( $j, $i, $l->get( $j, $i ) - $l->get( $j, $k ) * $r->get( $k, $i ) );
+ }
+ $l->set( $j, $i, $l->get( $j, $i ) / $r->get( $i, $i ) );
+ }
+ }
+
+ return array(
+ 'l' => $l,
+ 'r' => $r,
+ );
+ }
}
?>
diff --git a/src/math/polynom.php b/src/math/polynom.php
index 779c4f1..6939252 100644
--- a/src/math/polynom.php
+++ b/src/math/polynom.php
@@ -147,18 +147,25 @@ class ezcGraphPolynom
*
* @return string String representation of polynom
*/
- public function __to_string()
+ public function __toString()
{
krsort( $this->values );
$string = '';
foreach ( $this->values as $exponent => $factor )
{
- $string .=
- ( $factor != 1 ? sprintf( '%.2f * ', $factor ) : '' ) .
- ( $exponent > 1 ? sprintf( 'x^%d + ', $exponent ) :
- ( $exponent === 1 ? 'x + ' : '' )
- );
+ if ( $factor == 0 )
+ {
+ continue;
+ }
+ elseif ( $factor != 1 )
+ {
+ $string .= sprintf( '%.2f * ', $factor );
+ }
+
+ $string .= ( $exponent > 1 ? sprintf( 'x^%d + ', $exponent ) :
+ ( $exponent === 1 ? 'x + ' : '' )
+ );
}
return substr( $string, 0, -3 );
OpenPOWER on IntegriCloud