Генерация матриц

Курсовая работа

"Генерация матриц"

Введение

В настоящее время матричное исчисление широко применяется в различных областях математики, механики, теоретической физики, теоретической электротехники и т.д.

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

Данная курсовая работа состоит двух глав, включающих в себя каждая несколько параграфов и подпунктов.

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

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

В заключении говорится о проблемах, с которыми столкнулся при составлении алгоритма и написании на его основе программы, и о путях усовершенствования предложенного алгоритма и программы.

1. Матрицы и определители

1.1 Матрицы. Действия с матрицами

Все определения, теоремы, свойства, следствия и их доказательства, используемые в курсовой работе, взяты из книги В.А. Ильина, Э.Г. Позняка «Линейная алгебра».

Матрицей называется прямоугольная таблица из чисел, содержащая некоторое количество m строк и некоторое количество n столбцов (размера ).

Числа m и n называются порядками матрицы. Если m=n, матрица называется квадратной, а число m=n – её порядком.

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

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

Числа , входящие в состав данной матрицы, называются её элементами. В записи первый индекс означает номер строки, а второй индекс – номер столбца.

В случае квадратной матрицы

(1.1)

вводится понятия главной и побочной диагоналей. Главной диагональю матрицы называется диагональ a11 a 22 … an n, идущая из левого верхнего угла этой матрицы в правый нижний её угол. Побочной диагональю матрицы называется диагональ an1 a(n-1)2 … a1n, идущая из левого нижнего угла в правый верхний угол.

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

Перейдём к определению основных операций над матрицами.

Сложение матриц. Суммой двух матриц и одних и тех же порядков m и n называется матрица тех же порядков m и n, элементы ci j которой равны

(1.2)

Для обозначения суммы двух матриц используется запись C=A+B. Операция составления суммы матриц называется их сложением.

Итак, по определению

=

=

Из определения суммы матриц, а точнее из формулы (1.2) непосредственно вытекает, что и операция сложения матриц обладает теми же свойствами, что и операция сложения вещественных чисел, а именно:

переместительным свойством: A+B=B+A,

сочетательным свойством: (A+B)+C=A+(B+C).

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

Умножение матрицы на число. Произведением матрицы на вещественное число λ называется матрица , элементы ci j которой равны

(1.3)

Для обозначения произведения матрицы на число используется запись C=λA или C=Aλ. Операция составления произведения матрицы на число называется умножением матрицы на это число.

Из формулы (1.3) видно, что умножение матрицы на число обладает следующими свойствами:

сочетательным свойством относительно числового множителя: (λμ) A = λ(μA);

распределительным свойством относительно суммы матриц: λ (A+B) = λA + λB;

распределительным свойством относительно суммы чисел: (λ+μ) A = λA + μA.

Замечание. Разностью двух матриц A и B одинаковых порядков m и n естественно назвать такую матрицу C тех же порядков m и n, которая в сумме с матрицей B даёт матрицу A. Для обозначения разности двух матриц используется естественная запись: C = A – B.

Очень легко убедиться, что разность C двух матриц A и B может быть получена по правилу C = A + (– 1) B.

Перемножение матриц. Произведением матрицы , имеющей порядки, соответственно равные m и n, на матрицу , имеющую порядки, соответственно равные m и p, называется матрица , имеющая порядки, соответственно равные т и р, и элементы ci j, определяемые формулой

. (1.4)

Для обозначения произведения матрицы A на матрицу B используют запись . Операция составления произведения матрицы A на матрицу B называется перемножением этих матриц.

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

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

Формула (1.4) представляет собой правило составления элементов матрицы C, являющейся произведением матрицы A на матрицу B. Это правило можно сформулировать и словесно: элемент cij стоящий на пересечении i й строки и j го столбца матрицы C = , равен сумме попарных произведений соответствующих элементов i й строки матрицы A и j го столбца матрицы B.

В качестве примера применения указанного правила приведем формулу перемножения квадратных матриц второго порядка

.

Из формулы (1.4) вытекают следующие свойства произведения матрицы A на матрицу B:

1) сочетательное свойство: (AB) C = A(BC);

2) распределительное относительно суммы матриц свойство: (A+B) C=AC+BC или A (B+C)=AB+AC.

Распределительное свойство сразу вытекает из формул (1.4) и (1.2), а для доказательства сочетательного свойства достаточно заметить, что если , , , то элемент матрицы (AB) C в силу (1.4) равен , а элемент матрицы A(BC) равен , но тогда равенство = вытекает из возможности изменения порядка суммирования относительно j и k.

Вопрос о перестановочном свойстве произведения матрицы A на матрицу B имеет смысл ставить лишь для квадратных матриц A и B одинакового порядка (ибо, как указывалось выше, только для таких матриц A и B оба произведения AB и BA определены и являются матрицами одинаковых порядков). Элементарные примеры показывают, что произведение двух квадратных матриц одинакового порядка не обладает перестановочным свойством. В самом деле, если положить , , то , а .

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

Среди квадратных матриц выделим класс так называемых диагональных матриц, у каждой из которых элементы, расположенные вне главной диагонали, равны нулю. Каждая диагональная матрица порядка n имеет вид

,

где – какие угодно числа. Если все эти числа равны между собой, т.е. , то для любой квадратной матрицы A порядка n справедливо равенство AD=DA. Проверим это, обозначим символами и элементы, стоящие на пересечении i й строки и j го столбца матриц AD и DA соответственно. Тогда из равенства (1.4) и из вида матрицы D получим, что

, , (1.6)

т.е. = .

Среди всех диагональных матриц (1.5) с совпадающими элементами особо важную роль играют две матрицы. Первая из этих матриц получается при d=l, называется единичной матрицей n го порядка и обозначается символом E. Вторая матрица получается при d=0, называется нулевой матрицей n го порядка и обозначается символом O. Таким образом,

, .

В силу доказанного выше AE = EA и AO = OA. Более того, из формул (1.6) видно, что

AE = EA = A, AO = OA = O. (1.7)

Первая из формул (1.7) характеризует особую роль единичной матрицы E, аналогичную той роли, которую играет число 1 при перемножении вещественных чисел. Что же касается особой роли нулевой матрицы O, то ее выявляет не только вторая из формул (1.7), но и элементарно проверяемое равенство

A + O = O + A = A.

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

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

Например, матрицу

можно рассматривать как блочную матрицу

,

элементами которой служат следующие блоки:

, ,

, .

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

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

Столь же элементарно проверяется, что если матрицы A и B имеют одинаковые порядки и одинаковым образом разбиты на блоки, то сумме матриц A и B отвечает блочная матрица с элементами =+ (здесь и – блочные элементы матриц A и B).

Пусть A и B – две блочные матрицы такие, что число столбцов каждого блока равно числу строк блока (так что при любых α, β и γ определено произведение матриц ). Тогда произведение C = AB представляет собой матрицу с элементами , определяемыми формулой

.

Для доказательства этой формулы достаточно расписать левую и правую ее части в терминах обычных (числовых) элементов матриц A и B.

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

1.2 Определители

Целью этого параграфа является построение теории определителей любого порядка п.

Рассмотрим произвольную квадратную матрицу любого порядка n:

. (1.8)

С каждой такой матрицей связана определенная численная характеристика, называемая определителем, соответствующим этой матрице.

Если порядок n матрицы (1.8) равен единице, то эта матрица состоит из одного элемента a11 и определителем первого порядка соответствующим такой матрице, называется величиной этого элемента.

Если далее порядок n матрицы (1.8) равен двум, т.е. если эта матрица имеет вид

, (1.9)

то определителем второго порядка, соответствующим такой матрице, есть число, равное a11a22 – a12 a21 и обозначаемое одним из символов

.

Итак, по определению

. (1.10)

Формула (1.10) представляет собой правило составления определителя второго порядка по элементам соответствующей ему матрицы. Словесная формулировка этого правила такова: определитель второго порядка, соответствующий матрице (1.9), равен разности произведения элементов, стоящих на главной диагонали этой матрицы, и произведения элементов, стоящих на побочной ее диагонали.

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

Договоримся называть минором любого элемента матрицы n го порядка (1.8) определитель порядка n 1, соответствующий той матрице, которая получается из матрицы (1.8) в результате вычеркивания i й строки и j го столбца (той строки и того столбца, на пересечении которых стоит элемент ). Минор элемента будем обозначать символом . В этом обозначении верхний индекс обозначает номер строки, нижний – номер столбца, а черта над M означает, что указанные строка и столбец вычеркиваются.

Определителем порядка n, соответствующим матрице (1.8), назовем число, равное и обозначаемое символом

. (1.11)

Итак, по определению

. (1.12)

Формула (1.12) представляет собой правило составления определителя порядка n по элементам первой строки соответствующей ему матрицы и по минорам элементов первой строки, являющимся определителями порядка n 1.

Если n=2, то правило (1.12) в точности совпадает с правилом (1.10), ибо в этом случае миноры элементов первой строки имеют вид: , .

Естественно возникает вопрос, нельзя ли использовать для получения величины определителя (1.11) элементы и отвечающие им миноры не первой, а произвольной i й строки матрицы (1.8). Ответ на этот вопрос дает следующая основная теорема.

Теорема 1.1. Каков бы ни был номер строки i (i=1,2… n), для определителя n го порядка (1.11) справедлива формула

, (1.13)

называемая разложением этого определителя по i й строке.

В этой формуле показатель степени, в которую возводится число (–1), равен сумме номеров строки и столбца, на пересечении которых стоит элемент ai j.

Доказательство теоремы 1.1. Формулу (1.13) нужно доказать лишь для номеров i = 2, 3,…, n. При n = 2 (т.е. для определителя второго порядка) эту формулу нужно доказать лишь для номера i = 2, т.е. при n = 2 нужно доказать лишь формулу

Справедливость этой последней формулы сразу вытекает из выражений для миноров матрицы (1.9) в силу которых правая часть этой формулы совпадает с правой частью (1.10). Итак, при n = 2 теорема доказана.

Доказательство формулы (1.13) для произвольного n > 2 производится по индукции, т.е. для определителя порядка n – 1 справедлива формула вида (1.13) разложения по любой строке, и, опираясь на это, можно убедиться в справедливости формулы (1.13) для определителя порядка n.

При доказательстве понадобится понятие миноров матрицы (1.8) порядка n – 2. Определитель порядка n 2, соответствующий той матрице, которая получается из матрицы (1.8) в результате вычеркивания двух строк с номерами и двух столбцов с номерами , называется минором (n 2) – го порядка и обозначается символом .

Определитель n го порядка ∆ вводится формулой (1.12), причем в этой формуле каждый минор является определителем порядка n 1, для которого по предположению справедлива формула вида (1.13) разложения по любой строке.

Фиксировав любой номер i (i=2,3… n), разложим в формуле (1.12) каждый минор по i – й строке основного определителя (1.11) (в самом миноре эта строка будет (i 1) – й).

В результате весь определитель ∆ окажется представленным в виде некоторой линейной комбинации миноров (n 2) – го порядка с несовпадающими номерами j и k, т.е. в виде

(1.14)

Для вычисления множителей