Нужен алгоритм преобразования матрицы к треугольному виду!

[Tarik]

Люди, выручайте! Мне завтра на информатике надо написать прогу для преобразования матрицы второго порядка к треугольному виду. А алгоритм что-то не получается (я и в обычной-то математике их с трудом преобразовываю )... Так что, поможите, кто чем может... Алгоритм желательно с комментами (хотя и не обязательно)

[Krasavica]

Прости за флуд, а кто у тебя информатику ведет?

[FaKk2]

Ну приведи математический алгоритм,а там обмозгуем

[Leon_]

Второго порядка -- это что, два на два? А треугольный вид -- это когда под главной диагональю все нулевые элементы? Т.е. привести к виду, когда элемент a(2,1)=0?
Какими преобразованиями можно пользоваться? Из какого множества элементы матрицы?

[Amed]

Можно умножать строки на числа и складывать их... Какая проблема?

Скажем, матрица такая:

(5,2)
(4,1)

Надо такую:
(х,х)
(0,х)

Тогда надо умножить 2 строку на 5/4 и вычесть из 2 строки 1...

[Amed]

Умножаешь 2 строку так, чтобы после вычитания из неё 1 в (2,1) оказался 0... Чего проще? =)

[Tarik]

Прости за флуд, а кто у тебя информатику ведет?

Информатику ведёт Надирадзе Ирина Александровна...

Ну приведи математический алгоритм,а там обмозгуем

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

Второго порядка -- это что, два на два?

Наверное, я неправильно выразился... Термины у меня хромают Короче, нужно привести двумерную матрицу произвольного размера (то есть и 10х10 может быть).

А треугольный вид -- это когда под главной диагональю все нулевые элементы?

Точно.

Какими преобразованиями можно пользоваться?

см. выше

Из какого множества элементы матрицы?

В принципе, любое число, но на практике будет от 0 до 100

Умножаешь 2 строку так, чтобы после вычитания из неё 1 в (2,1) оказался 0... Чего проще? =)

Матрица будет произвольного размера, так что это не прокатит

[Leon_]

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

[Leon_]

Это довольно сложно, на практике я так никогда не делал.
А преобразования возможны как строчные, так и столбцовые?

[Amed]

Ясно. Преобразования - только строк.

С 10х10 - уже сложнее.. Надо думать, т.к. задача сложная, вроде...

[Tarik]

С 10х10 - уже сложнее.. Надо думать, т.к. задача сложная, вроде...

Да, хитрая у нас информатичка Мы ведь её просили хотя бы примерно алгоритм показать, а она говорит: "У вас такой хороший преподаватель вышку читает, вы всё должны и без меня знать"

Стоп. Так ведь вроде метод Гаусса как раз позволяет привести матрицу к трегольному виду... Или я не прав?

[Leon_]

Прав-прав. Только нахождение обратимого элемента -- как это реализовать?

[GSerg]

А ведь я это писал
30 октября смогу выложить, потерпит?
Хотя быстрее заново написать

[GSerg]

Надо же, помню ещё что-то

Код: Выделить всё

Option Explicit

'Предполагается, что обе lbound=1
Private Function Triangelize(arr() As Double) As Double()
  Dim r As Long, r2 As Long, c As Long, d As Double, out() As Double
 
  out = arr
 
  For r = 1 To UBound(out, 1)
    For c = UBound(out, 2) To 1 + r - 1 Step -1
      out(r, c) = out(r, c) / out(r, 1 + r - 1)
    Next
     
    For r2 = r + 1 To UBound(out, 1)
      d = out(r2, 1 + r - 1)
      For c = 1 + r - 1 To UBound(out, 2)
        out(r2, c) = out(r2, c) - out(r, c) * d
      Next
    Next
  Next
 
  Triangelize = out
End Function

Private Sub Form_Load()
  Dim arr() As Double, i As Long, j As Long
 
  ReDim arr(1 To 5, 1 To 5)
  For i = 1 To 5
    For j = 1 To 5
      arr(i, j) = Rnd * 100
    Next
  Next
 
  For i = 1 To 5
    For j = 1 To 4
      Debug.Print arr(i, j),
    Next
    Debug.Print arr(i, 5)
  Next
 
  arr = Triangelize(arr)
  Debug.Print
  Debug.Print
 
  For i = 1 To 5
    For j = 1 To 4
      Debug.Print arr(i, j),
    Next
    Debug.Print arr(i, 5)
  Next
End Sub

[Amed]

Э, что, уже 30 октября!?

*Зевая и потягиваясь*
Я в шоке

[Tarik]

GSerg, огромное спасибо, выручил! Вот только одно непонятно: почему у тебя везде 1 + r - 1? Разве 1+r-1 не равно r?

[GSerg]

Это осталось от тех тёмных времён, когда я ещё не установил ограничения lbound=1

[Leon_]

Только ведь не каждая квадратная матрица приводима к треугольной. Сначала надо сделать проверку -- вдруг ее определитель равен нулю?

[Ennor]

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

[GSerg]

А определителя у прямоугольной вроде как матрицы нет

Определитель произвольного размера считается рекурсивно, путём последовательного разложения по строке или столбцу, пока не останется матрица 2 или 3 порядка...

[Ennor]

...
Определитель произвольного размера считается рекурсивно, путём последовательного разложения по строке или столбцу, пока не останется матрица 2 или 3 порядка...

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

[Leon_]

Определитель произвольного размера считается рекурсивно, путём последовательного разложения по строке или столбцу, пока не останется матрица 2 или 3 порядка...

Это метод разложения миноров (если я правильно помню), но он применятся для упрощения вычисления определителя вручную. А вообще есть формула вычисления определителя, собственно это и есть определение.. Но ее я не помню. Если дело терпит, то завтра изложу.

[SeRRg]

GSerg, мне кажется, что твой алгоритм - неверный (могу ошибаться).
У тебя на главной диагонали все 1, а так быть не должно.
Мне задали на этой неделе сделать то же самое, и вот что у меня получилось:

Код: Выделить всё

Option Explicit



Private Sub Command1_Click()
  Dim arr() As Double, i As Long, j As Long
 
  ReDim arr(1 To 5, 1 To 5)
  For i = 1 To 5
    For j = 1 To 5
      arr(i, j) = Int(Rnd * 10)
    Next
  Next
 
  For i = 1 To 5
    For j = 1 To 4
      Debug.Print arr(i, j),
    Next
    Debug.Print arr(i, 5)
  Next
 
  arr = Triangelize1(arr)
  Debug.Print
  Debug.Print
 
  For i = 1 To 5
    For j = 1 To 4
      Debug.Print arr(i, j),
    Next
    Debug.Print arr(i, 5)
  Next


End Sub

Private Function Triangelize1(arr() As Double) As Double()
  Dim r As Long, r2 As Long, c As Long, d As Double, out() As Double
  Dim i As Long 'ïî ñòîëáöàì
  Dim j As Long, number As Long 'ïî ñòðîêàì
  Dim k As Long ' ïî ïîðÿäêó
 
  Dim m As Long
  Dim n As Long
 
  Dim koeff As Double

number = 2

For k = 1 To (UBound(arr) - 1)
For j = number To UBound(arr)

If arr(k, k) <> 0 Then koeff = (-1) * arr(j, k) / arr(k, k) Else koeff = 0
For i = number - 1 To UBound(arr)
d = arr(k, i) * koeff

arr(j, i) = arr(j, i) + d
If Abs(arr(j, i)) < 0.00000001 Then arr(j, i) = 0

Next i

Next j
number = number + 1

 
  Next k


Triangelize1 = arr
End Function

[SeRRg]

З.Ы. Если я где-то ошибаюсь, поправьте меня.
(А определитель - произведение членов главной диагонали в треугольной матрице)

[Ennor]

Дело тут вот в чем: для оптимизации расчетов я хочу сначала вычислить определитель, и только потом, если он меня устраивает, заниматься приведением матрицы к треугольному виду. Хотя, впрочем, неизвестно, что в данном случае будет быстрее...

[Faust]

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

[Tarik]

Ого, сколько народу ответило, а я даже мыла не получил
2SeRRg: Код GSerg'a одновременно приводит матрицу и к каноническому виду (почти ). Это мне весьма помогло, когда сказали написать на основе этого алгоритма решение СЛАУ методом Жордана-Гаусса...

[Ennor]

2 Faust: Спасибо за подсказку, пригодится. Я, правда, уже купил себе неск. учебников по линейке и терверу. Все равно по работе требуется...

[GSerg]

Практически во всех кабинетах информатики в наших школах стоит excel, так что есть ещё такой вариант:

Код: Выделить всё

dim arr(1 to 5, 1 to 5) as single, det as single
'заполняем...
with createobject("excel.application")
  det=.worksheetfunction.mdeterm(arr)
  .quit
end with

[SeRRg]