фортран. сравнение рангов матриц.

[YarЬ]

здравствуйте! помогите пожалуйста вот с чем:
мне надо написать программу на фортране для сравнения рангов нерасширеной и расширеной матрицы.

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

Код:

program 
dimension A(100,100), b(100),
real minor,rang

print*, 'vvedite kolychestvo uravneniy'
read*, n
print*, 'vvedite koeficienty uravnenyy'
  do i=1,n
  read*, (a(i,j), j=1,m)
  end do
  print*, 'vvedite stolbets svobodnyx chlenov'
  read*, (b(i), i=1,n)

if (A(1,1).ne.0) then
 do i=1,n
   do j=1,m
 minor=1
minor=A(i,j)*a(i+1,j+1)-a(i,j+1)*a(i+1,j)
rang=minor
if (minor.eq.0)then 
Rang=minor (i-1,j-1)
end if
   exit
  end do
 end do
end if

end program

[Вад]

Опиши текстом алгоритм нахождения ранга. А то непонятно, в каком месте тебе непонятно

Offtopic:

что-то фортран стал популярен...

Поставлю в угол.

[YarЬ]

я пишу , как сам бы решал.
берется первый элемент, и если он не равен нулю, то ранг матрицы уже 1. дальше смотрим минор 2го порядка  вокруг этого элемента. если он не равен нулю, ищем минор 3 го порядка и т.д.
если мы натыкаемся на минор , равный нулю, и все последующие миноры тоже равны нулю, значит ранг матрицы последний неравный нулю минор.
вот... бред, да?

[Вад]

Минор 2го порядка в коде вижу. А дальше?

[YarЬ]

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

[Вад]

Я думаю, здесь метод вычисления ранга через миноры слишком сложный: нужно считать, в общем случае, миноры до n-ного порядка.
Думаю, тут лучше приводить матрицу к треугольному виду. И по числу ненулевых элементов на главной диагонали определять ранг.

[YarЬ]

а как это можно сделать?

[YarЬ]

и ведь это можно использовать только для квадратных матриц, да?

[Dimka]

Миноры n-го порядка ведь можно посчитать через миноры n-1 порядка. Хотя в целом долго - не отрицаю. Тут как раз хорошо бы динамическое программирование использовать, чтобы повторно не считать то, что уже один раз считалось.

[Sla]

Dimka, динамическое программирование... Хм
 а теперь в терминах фортрана - сможешь?

[Dimka]

Sla, как известно, любую рекурсию можно преобразовать в итерацию, где вместо стека вызовов организуется программный стек (например, на базе массивов). Язык программирования тут большого значения не имеет. Разве что придётся побольше подумать.

[YarЬ]

 а можете рассказать примерный алгоритм?

[Dimka]

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

Код: (Ruby)

class Matrix
 def initialize(n)
  @rows,@n=Array.new,n
  for i in 0..@n
   column=Array.new
   for j in 0..@n
    column.push(0)
   end
   @rows.push(column)
  end
 end
 def [](x,y)
  return @rows[y][x]
 end
 def []=(x,y,value)
  @rows[y][x]=value
 end
 def calculateDeterminant
  if @n==2 then
   a1=self[0,0];a2=self[0,1];b1=self[1,0];b2=self[1,1]
   return a1*b2-a2*b1
  else
   j,determinant=0,0
   for i in 0..@n
    ai=self[i,j]
    if ai!=0 then
     sign=(i+j)%2==0?1:-1
     aai=buildSubmatrix(i,j).calculateDeterminant
     determinant+=sign*ai*aai
    end
   end
   return determinant
  end
 end
 def buildSubmatrix(x,y)
  submatrix=Matrix.new(@n-1)
  k=0
  for i in 0..@n
   if i!=x then
    l=0
    for j in 0..@n
     if j!=y then
      submatrix[k,l]=self[i,j]
      l+=1
     end
    end
    k+=1
   end
  end
  return submatrix
 end
end

Как видно из алгоритма (но нереализовано в нём), сокращение количества вычисляемых миноров обеспечивается поиском строки с наибольшим количеством нулей и пропусканием этих нулей при расчёте. Количество нулей можно увеличивать преобразованиями, но тогда задача сведётся к приведению матрицы к треугольному виду (о чём Вад говорил) и вычислению ранга более простым способом.

[YarЬ]

спасибо.