Организация рекурсии

[Rekky]

Добрый день.
Не могу понять как сделать рекурсию к такой формуле..код не обязательно. мне бы словесно как объяснить.
Формула:
шор.bmp
Как видно из нее, это обратная матрица.
Смысл таков. матрица A, для которой находим обратную матрицу делится на подматрицы(соответственно на 4 части)
B-1 - это обратная матрица к B, которая находится по формуле сложения и умножения подматриц матрицы A.
понятно что B-1 получается также по такой формуле обратной матрицы, и А-1 тоже.
Когда размер матриц дойдет до 2на2 то есть поделить их на подматрицы уже нельзя, то тогда находим обратную матрицу по обычной формуле через детерминант и союзную матрицу
Понимаю, что написала филькину грамоту) надеюсь вы мне поможете объяснить лучше вопросами

[Kukurudza]

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

[f.hump]

а что делать если А11 вырожденная?
у метода имя есть?

все оказалось еще печальней чем я думал. метод работает только для симметричных положительно определенных матриц.
http://www.mgopu.ru/PVU/2.1/Recurs/Matrix/matr_ref.htm

[Rekky]

Товарищи давайте не будем гнать на метод
Мне надо решить им.
Дошла до размерности 128 на 128
на 256 глохнет
я делаю со степенями двойки, тк так проще делить на кубики. можно и по другому сделать. хватит и такого решения.
То есть изначально условия такие
квадратная матрица. степень двойки. Надо чтобы срабатывало на 1024*1024.на определитель не проверяю.
Я бы и призадумалась сделать больше, если бы было время больше, но дел насущных было много, да и лень матушка
Ну тык вот щас прога ругается на память..не могу понять в чем дело.
Уважаемый f.hump вы мне говорили о памяти и тп, для меня это очень сложно пока(надеюсь), я написала как смогла, без перегрузок и тп..я буду ну очень признательна. если поможете исправить мой вариант, с минимумом вложений или тут очень все плохо?

#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <time.h>
#include<iostream>
#define n 256
#pragma comment(linker, "/STACK:1000000000")
using namespace std;
class Matrix 
{
public:
	int size;
	double **Matr;
	Matrix(const int isize)
	{
		size = isize;
	    Matr = new double*[isize];
		for (int i=0; i< size; i++) Matr[i] = new double[isize];
	}
	void Add(int i, int  j, int value, int k)
	{
		if (k==0) {Matr[i][j] = value;}
		else
		{
			srand(time(0)); 
			for (int m = 0; m<size; m++)
			for (int l = 0; l<size; l++)
				Matr[m][l] = 1+rand()%20;
		}
	}

	// вывод матрицы
	void Out()
	{
		for (int i = 0; i<size; i++)
		{
			for (int j = 0; j<size; j++)
			{
				cout<<Matr[i][j]<<' '; 
			}
			cout<<endl;
		}		
	}
	// получение подматриц
	void SubMatrix(Matrix A, int sub)
	{
		switch(sub)
		{
		case 1: 
			for (int i = 0; i<size/2; i++)
				for (int j = 0; j<size/2; j++)
					A.Matr[i][j]=Matr[i][j]; 	
			break;
		case 2:
			for (int i = 0; i<size/2; i++)
				for (int j = 0; j<size/2; j++)
					A.Matr[i][j]=Matr[i][j+size/2];
			break;
		case 3:
			for (int i = 0; i<size/2; i++)
				for (int j = 0; j<size/2; j++)
					A.Matr[i][j]=Matr[i+size/2][j];
			break;
		case 4: 
			for (int i = 0; i<size/2; i++)
				for (int j = 0; j<size/2; j++)
					A.Matr[i][j]=Matr[i+size/2][j+size/2];
			break;
		}
	}
	//~Matrix()
	//{
	////	/*for (int i=0; i<size; i++)
	////		delete Matr [i]; 
	////	delete [] Matr;*/
	//}
};
// сложение матриц
Matrix Plus (Matrix A, Matrix B)
	{
		Matrix C(A.size);
		for (int i=0;i<A.size;i++)
		{
			for (int j=0;j<A.size;j++)
			{
				C.Matr[i][j] = B.Matr[i][j]+A.Matr[i][j];
			}
		}
		return C;
	}
// вычитание матриц
Matrix Minus (Matrix A, Matrix B)
	{ 
		Matrix C(A.size);
		for (int i=0;i<A.size;i++)
		{
			for (int j=0;j<A.size;j++)
			{
				C.Matr[i][j] = A.Matr[i][j]-B.Matr[i][j];
			}
		};
		return C;
	}
// -A
Matrix Negative(Matrix A)
{
	Matrix B(A.size);
	for (int i = 0; i<A.size; i++)
				for (int j = 0; j<A.size; j++)
					B.Matr[i][j]=-A.Matr[i][j];
	return B;
}
// умножение матриц
Matrix Mul (Matrix A, Matrix B)
	{
		Matrix C(A.size);
		for (int i = 0; i<A.size; i++)
		{
			for (int j = 0; j<A.size; j++)
			{
				C.Matr[i][j] = 0;
				for (int k = 0; k<A.size; k++)
				{
					C.Matr[i][j] = C.Matr[i][j]+ A.Matr[i][k]*B.Matr[k][j];
				}
			}
		}
		return C;
	}
// обратная матрица для 2 на 2
Matrix InversMatrix22 (Matrix A)
	{	
		Matrix A_1(A.size), A_(A.size);
		int D = A.Matr[0][0]*A.Matr[1][1]-A.Matr[1][0]*A.Matr[0][1];
		if (D==0) {cout<< "Нет обратной матрицы"; exit;}
		A_.Matr[0][0] = A.Matr[1][1];
		if (A.Matr[0][1]== 0) {A_.Matr[0][1] = 0;} else {A_.Matr[0][1] = -A.Matr[0][1];}
		if (A.Matr[1][0]== 0) {A_.Matr[1][0] = 0;} else {A_.Matr[1][0] = -A.Matr[1][0];}
		A_.Matr[1][1] = A.Matr[0][0];
		A_1.Matr[0][0] = A_.Matr[0][0]/D;
		A_1.Matr[0][1] = A_.Matr[0][1]/D;
		A_1.Matr[1][0] = A_.Matr[1][0]/D;
		A_1.Matr[1][1] = A_.Matr[1][1]/D;
		return A_1;
	}
// сбор обратной матрицы
Matrix InitialSubInvers(Matrix A11, Matrix A12, Matrix A21, Matrix A22)
{
	Matrix A_1(A11.size*2);
	int m = A11.size;
	for (int i = 0; i<m; i++)
		for (int j = 0; j<m; j++)
		{
			A_1.Matr[i][j] = A11.Matr[i][j];
			A_1.Matr[i][j+m] = A12.Matr[i][j];
			A_1.Matr[i+m][j] = A21.Matr[i][j];
			A_1.Matr[i+m][j+m] = A22.Matr[i][j];
		}
	return A_1;
}
Matrix Shor(Matrix A)
{	
	// основной алгоритм
	if (A.size == 2)
	{   
		return InversMatrix22(A); 
	}
	else {
		Matrix A11(A.size/2), A12(A.size/2), A21(A.size/2), A22(A.size/2); // делим A на подматрицы
		Matrix B(A.size/2);
		// заполнение подматриц
		A.SubMatrix(A11,1);
		A.SubMatrix(A12,2);
		A.SubMatrix(A21,3);
		A.SubMatrix(A22,4);	
		B = Minus(A22 , Mul(Mul(A21,Shor(A11)),A12));
		return InitialSubInvers(			Plus(Shor(A11),Mul(Mul(Mul(Mul(Shor(A11),A12),Shor(B)),A21),Shor(A11))), 
							Mul(Mul(Negative(Shor(A11)),A12),Shor(B)),
							Mul(Mul(Negative(Shor(B)),A21),Shor(A11)),
							Shor(B)
							);
	}
}
int main(void)
{
	// главная матрица
	Matrix matrix(n), invers(n);
	matrix.Add(0,0,0,1);
	int time = clock();
	invers = Shor(matrix);
	//invers.Out();
	cout<< clock()-time;
	getch();
	return 0;
}

[Rekky]

Забыла написать ошибка на 256 размерности: Microsoft C++ exception: std::bad_alloc at memory location
Все что смогла понять, так это то, что некоторые подматрицы не определяются..то есть ссылка не неизвестность у них..
а почему не знаю

[f.hump]

если честно, то мне лень разбираться в этой мурзилке.

поскольку вы не исправили ситуацию с выделением/освобождением памяти под матрицы, то не стоит удивляться проблемам с памятью.

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

далее в "рекурсивных" целях вы делаете разбиение на подматрицы, вместо того, чтобы делать логическое разбиение делаете физическое разбиение создавая охренительное число временных матриц. И это будет быстро считать? - я, мягко говоря, сомневаюсь.

самое забавное, это то, что вы даже обратную матрицу 2х2 неправильно считаете.

[Rekky]

самое забавное, это то, что вы даже обратную матрицу 2х2 неправильно считаете.

Нет самое забавное, что я делала по примеру в книге и ответ сошелся Сейчас смотрю и правда накосячила, интересно, что теперь с ответом будет

И это будет быстро считать?

ну 128 считает за минутку
Я бы исправила, если бы понимала как вы предлагали, но увы