Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Java: Общие вопросы > Нахождение определителя матрицы

Автор: gmart 26.4.2004, 17:19

не могли бы отправить прогу(JAVA)

"нахождение определителя матрицы"

Автор: Sid 28.4.2004, 20:06

Могу дать код написанный на C++ если хошь.
Думаю переписать на Java его будет легко

Автор: Kurt 29.4.2004, 01:18

Я написал тебе такую программку. Конечно, ее можно оптимизировать или вообще использовать другой алгоритм (тады обращайся в "Алгоритмы" - я не спец.

), но этой полностью работающий код.
Вроде бы.

Для вычисления определителя я использовал разложение на миноры.
Если не знаком, немного теории:
Определитель любой квадратной матрицы можно разложить так:
|A11..A1n|
|........| = ((-1)^(k+1))*Ak1*Mk1+((-1)^(k+2))*Ak2*Mk2+..+((-1)^(k+n))*Akn*Mkn.
|An1..Ann|

Где 1<=k<=n (по какой строке раскладываем),
Aij - соотв. элемент определителя
Mij - минор определителя, получающийся вычеркиванием i-й строки и j-го столбца. (соответственно, он более низкого порядка).
Раскладывать можно по любой строке - это не имеет значения.

Вот код(написан в Sun ONE Studio):

Код


/*
 * MatrixCalculation.java
 *
 * Created on 29 Апрель 2004 г., 0:25
 */


/**
 *
 * @author  Ocheredko
 */
public class MatrixCalculation {
    
    /** Creates a new instance of MatrixCalculation */
    public MatrixCalculation() { //конструктор класса - я его не использовал, но можно тут сделать заполнение матрицы и т.п..
    }
    

    //рекурсивная функция - вычисляет значение определителя. Если на входе определитель 2х2 - просто вычисляем (крест-на-крест), иначе раскладываем на миноры. Для каждого минора вычисляем ЕГО определитель, рекурсивно вызывая ту же функцию..
    public double CalculateMatrix(double[][] matrix){
        double calcResult=0.0;
        if (matrix.length==2){
            calcResult=matrix[0][0]*matrix[1][1]-matrix[1][0]*matrix[0][1];
        }
        else{
            int koeff=1;
            for(int i=0; i<matrix.length; i++){
                if(i%2==1){  //я решил не возводить в степень, а просто поставить условие - это быстрее. Т.к. я раскладываю всегда по первой (читай - "нулевой") строке, то фактически я проверяю на четность значение i+0.
                    koeff=-1;
                }
                else{
                    koeff=1;
                };
      //собственно разложение:                
                calcResult += koeff*matrix[0][i]*this.CalculateMatrix(this.GetMinor(matrix,0,i)); 
            }
        }
        

	//возвращаем ответ
        return calcResult;
    }
    


    //функция, к-я возвращает нужный нам минор. На входе - определитель, из к-го надо достать минор и номера строк-столбцов, к-е надо вычеркнуть.
    private double[][] GetMinor(double[][] matrix, int row, int column){
        int minorLength = matrix.length-1;
        double[][] minor = new double[minorLength][minorLength];
        int dI=0;//эти переменные для того, чтобы "пропускать" ненужные нам строку и столбец
        int dJ=0;
        for(int i=0; i<=minorLength; i++){
            dJ=0;
            for(int j=0; j<=minorLength; j++){
                if(i==row){
                    dI=1;
                }
                else{
                    if(j==column){
                        dJ=1;
                    }
                    else{
                        minor[i-dI][j-dJ] = matrix[i][j];
                    }
                }
            }
        }
        
        return minor;
        
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) { //просто тест написанного:
        double[][] test = new double[3][3];
        
	//совершенно произвольная матрица - просто для этих чисел я предварительно вычислил результат вручную - чтоб проверить.
        test[0][0]=1;
        test[0][1]=2;
        test[0][2]=3;
        
        test[1][0]=4;
        test[1][1]=5;
        test[1][2]=7;
        
        test[2][0]=8;
        test[2][1]=3;
        test[2][2]=0;
        
        MatrixCalculation mc = new MatrixCalculation();
        double Result = mc.CalculateMatrix(test);
        System.out.println(Result);
        return;
    }
    
}

Все. Как видишь, тут 2 основные ф-ции:
GetMinor(..) - получает минор, "вычеркнув" строку и столбец. (явно можно проще реализовать..withstupid )
CalculateMatrix(..) - рекурсивная ф-ция для вычисления определителя.
Я везде использовал тип double - так "универсальнее".

Хотя тест сделал в целых числах - не охота было возиться с дробями.

Если что не понятно - спрашивай.
Если так не пойдет - скажи как надо (ну или можно попробовать перевести с С++, как предлагал Sid..). :

Автор: Sid 29.4.2004, 16:34

gmart
У меня детерминант находится методом приведения к диагональному виду.
Но думаю у Kurtа реальная реализация

Автор: Kurt 29.4.2004, 18:51

Ну, как я сказал, эт не оптимизированный код. Но работающий.

Однако хотелоь бы услышать мнение самого gmart..

Автор: LSD 30.4.2004, 23:04

CERN создал свою библиотеку математических функций colt (на чистой Java), если надо то могу после праздников кинуть ссылку.

Автор: Kurt 4.5.2004, 01:05

Эхм.. вот бы автора топика услышать..

А то как-то..ну вы понимаете..

Автор: Гость_maxius 5.5.2004, 00:39

Буду благодарен если LSD скинет ссылку на библиотеку мат. функций.

Автор: LSD 6.5.2004, 20:24

http://hoschek.home.cern.ch/hoschek/colt/

Автор: Guest 13.6.2004, 20:34

Профессиональный код Kurt, ты меня просто выручил, наконец я здал все лабы по программированию.

Автор: = niko = 13.6.2004, 20:45

Если можно пришлите код на С++ для расчета определителя на patriot.admin@mail.ru