Remkomplekty.ru

IT Новости из мира ПК
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Определитель матрицы паскаль

Определитель матрицы паскаль

Рекуррентное вычисление определителя

Мы будем здесь решать следующую задачу.

Задача. Написать функцию, вычисляющую определитель квадратной матрицы с целочисленными элементами. В основу вычислительного алгоритма положить формулу разложения по строке

где – элемент матрицы A , стоящий на пересечении i -той строки с j -тым столбцом матрицы, а – его минор, т.е. определитель n–1 -го порядка, составленный из элементов, оставшихся после вычеркивания i -той строки и j -того столбца. Такое решение не самое эффективное по объему вычислений, но может оказаться полезным, если порядок матрицы не очень велик, а значение определителя требуется получить точно и целым.

Приведенная формула сводит вычисление определителя к вычислению нескольких определителей – миноров порядка на 1 меньше. Эти определители, в свою очередь, можно аналогично выразить через миноры еще меньшего порядка. Это наводит на мысль, что функция вычисления минора любого порядка должна работать рекурсивно.

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

Для того, чтобы определить минор матрицы, надо указать ее строки и столбцы, на пересечении которых находятся элементы матрицы, входящие в минор. Равенство rows[i] = TRUE будет означать, что строка матрицы A с номером i участвует в определении минора, и аналогично в массиве cols будем указывать входящие в минор столбцы матрицы. Тогда вычисление определителя будет осуществляться так:

Прежде, чем заняться непосредственно функцией minor , я должен пояснить, что в главной процедуре, демонстрирующей обращение к функции Det :

– ввод элементов матрицы A осуществляется с помощью модуля ReadNum.tpu (см.) из текстового файла num.txt , имеющего следующий вид:

(Возьмите модуль ReadNum.tpu , чтобы иметь возможность проверять на примерах предлагаемые здесь решения.)

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

Займемся, наконец, функцией minor . В первую очередь для вычисления минора надо определить, где находится элемент матрицы, стоящий в левом верхнем углу минора. Именно отсюда будет начинаться вычисление по формуле (*). Для этого этого напишем функцию, дающую номер первого элемента индексного массива, имеющего значение TRUE :

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

Многочисленные комментарии в тексте функции остались от того времени, когда алгоритм планировался сначала в словесной форме. Только после этого он был переписан полностью на Pascal.

Вы можете взять файл det1.pas (и еще num.txt для записи матрицы), чтобы поэкспериментировать с программой. Можно изменять как порядок матрицы (устанавливая в исходном тексте программы значение const NN= ), так и элементы матрицы в файле num.txt (надо только иметь в виду, что расположение элементов по строкам файла не имеет значения, модуль ReadNum в любом случае читает все имеющиеся числа подряд!).

Если вы будете достаточно настойчиво тестировать программу, то обнаружите, что она хорошо справляется с треугольными матрицами, но допускает ошибки для матриц более общего вида. Чтобы понять причину этого явления, попробуйте проследить за изменением переменной sum , выполняя программу пошагово в отладчике.

И вот она, ошибка! Мы забыли, что при разложении определителя по элементам строки произведение надо брать со знаком .

Первое исправленное решение. Чтобы исправить это, напишем функцию, вычисляющую этот «знаковый множитель» (конечно, мы не будем вычислять степень, а просто учтем четность – так эффективнее):

– и введем соответствующую поправку в строку накопления суммы:

Однако, эксперименты показывают, что и это решение дает ошибочные значения. Возьмите файл det2.pas и попробуйте, например, его со следующей матрицей:

Причина в том, что мы неправильно расставляем знаки. Левый верхний элемент минора может оказаться практически в любом месте матрицы, и тем не менее он должен входить в минор всегда со знаком «+», независимо от четности суммы индексов i +j .

Второе исправленное решение. Устроим счетчик элементов jo:INTEGER и будем увеличивать его на 1 только тогда, когда будет найден и обработан очередной элемент первой строки минора. Соответственно измерим функцию step так, чтобы она отмечала четность счетчика jo . Тогда часть функции minor , отвечающая случаю n > 1 , будет выглядеть так:

Эта функция, наконец, работает правильно. Вы можете и ее получить для экспериментов (в файле det3.pas ). Теперь уже можно ее усовершенствовать.

Третье исправленное решение. Во-первых, лучше прослеживать не изменение четности переменной jo , а изменение значения step(jo) , которое просто равно 1 или –1 поочередно. Тогда сама функция step оказывается излишней!

Во-вторых, если элемент A[i,j] равен нулю, то вычисление его минора окажется излишним. Если матрица имеет много нулей, то на этом можно выиграть во времени вычисления.

Результат улучшений будет выглядеть так:

Эту версию вы тоже можете получить (в файле det4.pas ). Но и она не свободна от существенных недостатков!

Четвертое исправленное решение. Заметим, что 3 массива в списке аргументов функции minor передаются по значению, а не по ссылке. Для того, чтобы обеспечить неизменяемость массива со стороны вызывающей процедуры, Turbo Pascal создает в программном стеке копию массива и через тот же стек передает вызываемой функции адрес этой копии. И это присутствует в стеке в стольких экземплярах, какова глубина рекурсии. Так расходовать стек непозволительно! Понятно, что надо использовать передачу массивов по ссылке, когда функции передается лишь адрес массива.

Читать еще:  Виды сортировки паскаль

Далее, использование в качестве вспомогательных массивов rows и cols глобальных переменных является тактической ошибкой. Не следует обременять пользователя заботой о выделении вспомогательных массивов и навязывать ему их имена. Во избежание возможных коллизий следует эти массивы размещать в динамической памяти («куче») и освобождать эту память, как только потребность во вспомогательных массивах прекратится. Но это мы сможем сделать только после изучения темы «Указатели».

А пока займемся передачей массивов по ссылке. Перепишем заголовки функций:

(сделайте это сами в файле det4.pas ). После этого вдруг обнаруживается, что программа снова дает неправильные ответы! В чем тут дело?

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

Смотрите: при вычислении минора к элементу A[1,1] мы нашли входящую в него вторую строку: ( i := 2 ) и вычеркнули ее: rows[i] := FALSE . Это изменение было сделано в глобальном массиве rows , а не в его копии, персональной для данного вызова функции minor . После этого при вычислении минора к элементу A[1,2] мы ищем первую входящую в него строку и не находим второй строки, так как пользуемся тем же глобальным массивом rows .

Хорошим тоном в программировании является соблюдение

Поэтому в функции minor перед выходом из нее вычеркнутую i -тую строку надо восстановить:

Вот, наконец, решение (файл det5.pas ), которое нас удовлетворяет.

Замечание. Есть еще один способ экономии программного стека. Надо объявить функцию minor внутри функции det . Тогда массивы, доступные в det , будут доступны и всем экземплярам функции minor , без объявления их в списке параметров. Этот вариант решения проблемы, естественно, также требует восстановления состояния массива rows . Вы можете получить и его (файл det6.pas ). Но тогда функция minor становится не видна извне функции det , и мы теряем возможность вычисления минора для решения самостоятельной задачи, независимой от вычисления определителя.

Критика последнего решения. Есть еще одно замечание, более существенное с точки зрения использования разработанной функции. Она вычисляет определители матриц только одного порядка, зафиксированного в определении типа TYPE Matrix = ARRAY[1..NN,1..NN] OF INTEGER . При компиляции функции minor Turbo Pascal должен знать, чему равна константа NN , задействованная в определении типа матрицы. Если нам понадобится определитель матрицы другого порядка, можно перекомпилировать программу, задав другое значение NN . А как быть, если нам в рамках решения одной задачи надо вычислять определители матриц разных порядков? Эту задачу написанная так функция det , вкупе с minor , не решает.

Вывод: требуются дальнейшие усовершенствования. Нашу разработку надо переписать так, чтобы она не зависела от размерности массивов, с которыми работает. Это будет сделано далее, в разделе «Переход от индексов к указателям».

Определитель матрицы

Народ помогите,не пойму почему прога не работает:

Определитель матрицы
Привет ребят, решите задачу плиз каму не сложно. Задача. Вычислить определитель матрицы ( рекурсия.

Определитель матрицы
Написать программу вычисления определителя матрицы к-го порядка. k

Найти определитель матрицы
Напишыте плиз прогу (или кусок) которая находить детерминант матрицы NxN, где N вводят с.

Вычислить определитель матрицы
Как вычислить определитель для матрицы a, где i изменяется от 0 до n-1, j от 0 до N-1?

Трансер, ты код оформи нормально, тогда скажу

Добавлено через 31 секунду
надо чтобы не все в одну линию было

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

Добавлено через 1 час 51 минуту 41 секунду

Трансер, ты код оформи нормально, тогда скажу

Добавлено через 31 секунду
надо чтобы не все в одну линию было

Решение

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

Добавлено через 1 минуту
А может быть(извиняюсь конечно) вообще здесь

Возможно здесь неправильно ввожу.

Добавлено через 4 минуты

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

Добавлено через 1 минуту
А может быть(извиняюсь конечно) вообще здесь

Вот это условие не выполнили и вообще не ввели матрицу?

И введите числа, какие хотите.

Добавлено через 1 минуту
Можно и так

здесь вводите по 3 числа в строку, жмете Enter

Добавлено через 3 минуты
Можно матрицу задать константой.

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

Читать еще:  Система обеспечения региональной безопасности

а за код спасибо, сэкономил немного времени)

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Определитель матрицы Вандермонда
Задача состоит в следущем: Вводим размер массива,создаем матрицу вандермонда, и вищитиваем.

Найти определитель квадратной матрицы
Вот программка,которая находит определитель квадратной матрицы,только не понимаю где ошибка,что он.

Определитель матрицы. Метод Гаусса.
Помогите пожалуйста. Админ привет. это vanHalen с вашего бывшего форума. 🙂 Задание: Найдите.

Нужно найти определитель матрицы
ПОМОГИТЕ ПОЖАЛУЙСТА ДОПОЛНИТЬ ПРОГРАММУ, НУЖНО НАЙТИ ОПРЕДЕЛИТЕЛЬ МАТРИЦЫ, ВЕКТОР НЕВЯЗКИ, ОБРАТНУЮ.

[алгоритм] определитель и трeугольник пaскаля

Определитель = 1. Метод Гаусса. Причем тут треугольник Паскаля?

Да, обшибся. Не 1.

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

Сначала из j+1 столбца вычитаешь j-тый, проходя по j от n-1 до 1.
Там вроде останется матрица из одних единиц, у которой определитель равен 0.

Хотя я могу ошибаться, а расписывать влом 🙂

Re: [алгоритм] определитель и трeугольник пaскаля

действительно не 0 🙂

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

Re: [алгоритм] определитель и трeугольник пaскаля

Определитель будет равен n.

Гоняешь несколько(n-1) раз вычитание столбцов по описанному выше методу, в результате получаешь нижнетреугольную матрицу с диагональю [1,1. 1,n], у которой det=n.

Re: [алгоритм] определитель и трeугольник пaскаля

Не обшибся. Таки 1.

Re: [алгоритм] определитель и трeугольник пaскаля

получится матрица с единичной диагональю

Re: [алгоритм] определитель и трeугольник пaскаля

что там у нас в talks про второкурсника проскакивало? тут лучше )

Re: [алгоритм] определитель и трeугольник пaскаля

я понял как решать, когда сдам отпишу решение.

осталось тока формулу записать и доказать.

всё элементарно, хватило методички за 1 курс, 1 семестр по лин. алегбре. )

Re: [алгоритм] определитель и трeугольник пaскаля

> Не обшибся. Таки 1.

Re: [алгоритм] определитель и трeугольник пaскаля

Биномиальный коэффициент — это многочлен от n степени k с главным коэффициентом 1/k!, поэтому определитель данной матрицы — просто определитель Вандермонда для 0,1,2. n-1, умноженный на произведение всех 1/k!. Очевидно получается 1.

Если знать такое утверждение из алгебраической комбинаторики, то тоже очень просто. Пусть a_1, a_2, . a_n, b_1, . b_n — целочисленные точки на плоскости и p_ij — количество путей по решетке (идущих, скажем, только вправо или вниз) из точки a_i в точку b_j. Тогда определитель матрицы (p_ij) — это количество наборов таких попарно непересекающихся путей из a_1 в b_1, из a_2 в b_2, . a_n в b_n. Если выбрать a_i=(0,i-1), b_i=(i-1,0), то матрица (p_ij) как раз данная. С другой стороны, есть только один набор непересекающихся путей: a_i->(i-1,i-1)->b_i. Поэтому определитель 1.

В общем, учите математику. Быдлокодерство поспеет.

Re: [алгоритм] определитель и трeугольник пaскаля

так, решение не отпишу) ибо неправильно)

действительно получается всегда один. надо тока оформить это дело теперича.

а с определителем Вандермонда, не очень то и понял в чем его смысл..

с «утверждением из алгебраической комбинаторики» тоже слегка непонятно)

Re: [алгоритм] определитель и трeугольник пaскаля

матрица Вандермонда — (a_i^)_^n

ее определитель = prod (a_i — a_j)

пусть есть многочлены P_j(x) = c_j x^ + .

тогда определитель матрицы (P_j(a_i))_^n по методу Гаусса равен опредетителю Вандермонда, умноженному на произведение всех c_j

— многочлен степени k от n с главным коэффициентом 1/k!

Re: [алгоритм] определитель и трeугольник пaскаля

Есть способ проще, на уровне 1-го курса.

Re: [алгоритм] определитель и трeугольник пaскаля

Текст программы на языке Pascal

3.2 Текст программы на языке Pascal

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids, Menus, Buttons;

procedure FormCreate(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure BitBtn1Click(Sender: TObject);

procedure StringGrid1KeyPress(Sender: TObject; var Key: Char);

Massiv1 = array[1..Nmax,1..Nmax] of extended;

procedure TForm1.FormCreate(Sender: TObject);

Label3.Caption := ‘ для вычисления определителя матрицы нажмите расчет’;

StringGrid1.Cells [0,0] := ‘Матрица А’;

for r := 1 to N do begin

StringGrid1.Cells [0,r] := ‘ строка ‘ + IntToStr(r);

for c := 1 to N do begin

StringGrid1.Cells [c,0] := ‘ столбец ‘ + IntToStr(c);

procedure TForm1.Button2Click(Sender: TObject);

for r := 1 to N do begin

StringGrid1.Cells [0,r] := ‘ строка ‘ + IntToStr(r);

for c := 1 to N do begin

StringGrid1.Cells [c,0] := ‘ столбец ‘ + IntToStr(c);

procedure TForm1.Button1Click(Sender: TObject);

detA, k, buf: extended;

max, j, z, p, s, zam:integer;

for c := 1 to N do

for r := 1 to N do

for c := 1 to N-1 do begin

for z := c to N-1 do begin

for j := z+1 to N do begin

if abs(A[c,j]) > abs(A[c,max]) then

for p := 1 to N do begin

for r := c+1 to N do begin

for s := 1 to N do begin

if c<>max then begin

for c := 1 to N do

if zam mod 2 <> 0 then

label3.Caption := ‘Детерминант матрицы равен: ‘ + FloatToStrF(detA,fffixed,6,3);

procedure TForm1.BitBtn1Click(Sender: TObject);

MessageDlg(Программа вычисляет детерминант (определитель) матрицы методом Гаусса с выбором главного элемента. Внимание. Матрица должна быть квадратной!’,mtInformation,[mbOK],0);

procedure TForm1.StringGrid1KeyPress(Sender: TObject; var Key: Char);

if Key <> DecimalSeparator then

4. ТЕСТОВАЯ ЗАДАЧА

4.1 Математическое решение задачи

Вычисление определителя данной матрицы вручную целесообразно производить с помощью разложения элементов по 1-й строке по формуле (1). В итоге получится:

(7)

Воспользовавшись правилом Саррюса (правилом треугольников), вычисляются определители третьего порядка входящие в состав выражения (7):

Читать еще:  Заполнение матрицы паскаль

detA = 4(10∙7∙2+(-20) ∙3∙5+5∙7∙10-5∙7∙10-10∙7∙3-5∙(-20) ∙2)-7∙(7,5∙7∙2+(-20) ∙3∙2+7∙3∙10-10∙7∙2-(-20)∙3∙2-7,5∙7∙3)+5∙(7,5∙5∙2+10∙3∙2+3∙5∙10-10∙5∙2-10∙3∙2-3∙5∙7,5)-6∙(7,5∙5∙7+3∙5∙(-20)+10∙7∙2-(-20) ∙5∙2-10∙3∙7-7,5∙7∙5)

Ответ: определитель матрицы равен 280

4.2 Решение, полученное с использованием разработанного программного обеспечения

Введя исходные данные в программу получим следующий результат: «Определитель матрицы равен: 280». Результат, полученный с использованием разработанной программы соответствует результату, вычисленному математически.

Вывод: разработанное программное обеспечение верно вычисляет определитель произвольной матрицы.

5. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ

Для запуска программы необходимо запустить файл Determinant.exe, дважды щелкнув по нему мышью. В появившемся окне при необходимости изменить порядок матрицы, введя значение в поле напротив надписи «Порядок матрицы» и нажав на кнопку «Изменить порядок матрицы». В ячейках таблицы ввести значения элементов матрицы. Вводимые данные должны являться действительными числами, содержать только цифры, знак « — » и разделитель целой и дробной части. После заполнения ВСЕХ элементов матрицы нажать кнопку «Расчет». Ответ будет написан под таблицей в формате: «Детерминант матрицы равен: -280,000»

Выход из программы осуществляется с помощью кнопки .

Внешний вид окна программы представлен на рисунке 5.

Рис. 5. Внешний вид окна программы

В данной работе были изучены численные методы нахождения определителя матрицы и выбран наиболее оптимальный, с точки зрения реализации его на компьютере – метод исключения с выбором главного элемента. Написана программа с использованием массивов. Данная программа позволяет определить детерминант матрицы размером N×N, размер матрицы задается пользователем, вводимые данные – действительные числа. Вычисление определителя матрицы является второй главной задачей линейной алгебры, и применяется при решении сложных систем линейных уравнений с несколькими неизвестными.

Обработка матриц в Паскале

Матрица — это двумерный массив , каждый элемент которого имеет два индекса: номер строки и номер столбца.

Объявить двумерный массив (матрицу) можно так:

имя : array [ индекс1_нач.. индекс1_кон, индекс2_нач.. индекс2_кон ]

  • тип определяет тип элементов массива,
  • имя — имя матрицы,
  • индекс1_нач..индекс1_кон — диапазон изменения номеров строк,
  • индекс2_нач..индекс2_кон — диапазон изменения номеров столбцов матрицы.

var h : array [ 0.. 1 1, 1.. 10 ] of integer;

Описана матрица целых чисел h , состоящая из двенадцати строк и десяти столбцов (строки нумеруются от 0 до 11, столбцы от 1 до 10).

Существует ещё один способ описать матрицы, для этого надо создать новый тип данных :

новый_тип=array [ индекс1_нач.. индекс1_кон ] of тип;

имя : array [ индекс2_нач.. индекс2_кон ] of новый_тип;

новый_тип=array [ список_диапазонов ] of тип;

В данном случае в матрицах a и b есть 10 строк и 30 столбцов, а с — матрица , в которой есть 16 строк и 14 столбцов.

Для обращения к элементу матрицы необходимо указать её имя и в квадратных скобках через запятую номер строки и номер столбца:

имя [ номер_строки, номер_столбца ]

имя [ номер_строки ] [ номер_столбца ]

Например, h[2,4] 1 Или h[2][4]. — элемент матрицы h , находящийся в строке под номером два и столбце под номером четыре.

Для обработки всех элементов матрицы необходимо использовать два цикла . Если матрица обрабатывается построчно, то во внешнем цикле последовательно перебираются строки от первой до последней, затем во внутреннем — все (первый, второй, третий и т. д.) элементы текущей строки. При обработке элементов матрицы по столбцам внешний цикл будет перебирать столбцы, внутренний — строки. На рис. 6.1 представлена блок-схема алгоритма обработки матрицы по строкам, на рис. 6.2 — по столбцам. Здесь i — номер строки, j — номер столбца, N — количество строк, M — количество столбцов матрицы A .

Рассмотрим основные операции , выполняемые над матрицами при решении задач.

6.1 Ввод-вывод матриц

Матрицы, как и массивы, нужно вводить (выводить) поэлементно. Вначале следует ввести размеры матрицы, а затем уже в двойном цикле вводить элементы. Блок-схема ввода элементов матрицы изображена на рис. 6.3.

Вывод можно осуществлять по строкам или по столбцам, но лучше, если элементы располагаются построчно, например,

Алгоритм построчного вывода элементов матрицы приведён на рис. 6.4.

Об описании матриц на языке Паскаль было рассказано в разделе 5.2 главы 5, обращение к элементу матрицы можно осуществить c помощью конструкции или .

Рассмотрим реализацию ввода-вывода матриц в консольных приложениях.

Для организации построчного ввода матрицы в двойном цикле по строкам и столбцам можно использовать оператор read .

В этом случае элементы каждой строки матрицы можно разделять символами пробела или табуляции, и только в конце строки нажимать Enter .

Ниже приведён пример консольного приложения ввода-вывода матрицы.

На рис. 6.5 представлены результаты работы программы.

Ввод матрицы также можно организовать с помощью следующего цикла .

Авторы предлагают читателю самостоятельно разобраться, в чём будет отличие ввода матрицы в этом случае.

Для ввода-вывода матриц можно использовать компонент типа TStringGrid, с которым мы познакомились в главе 5.

В качестве примера рассмотрим следующую задачу.

Блок-схема транспонирования матрицы приведена на рис. 6.6. При транспонировании матрицы получается матрица B.

Рассмотрим частный случай транспонирования матрицы фиксированного размера A(4,3) .

На форме разместим метки Label1 и Label2 со свойствами Caption — Заданная матрица и Транспонированная матрица , два компонента типа TStringGrid , изменив их свойства так, как показано в табл. 6.1, и кнопку Транспонирование матрицы.

Окно формы приложения представлено на рис. 6.7.

Ниже приведён текст подпрограммы с комментариями, которая будет выполняться, если пользователь щёлкнет по кнопке Транспонирование матрицы.

Ссылка на основную публикацию
Adblock
detector