ЛИСП-реализация операций над матрицами
Содержание
Введение 2
1 Постановка задачи 4
2 Математические и алгоритмические основы решения задачи 7
2.1 Сумма матриц 7
2.2 Разность матриц 7
2.3 Умножение матрицы на число λ 8
2.4 Умножение матриц 9
2.5 Транспонирование матрицы 10
3 Функциональные модели и блок-схемы решения задачи 12
4 Программная реализация решения задачи 18
5 Пример выполнения программы 27
Заключение 29
Список использованных источников и литературы 30
Введение
Многие теоретические и практические вопросы приводят не к одному уравнению, а к целой системе уравнений с несколькими неизвестными. Особенно важен случай системы линейных уравнений, т.е. системы m уравнений 1ой степени с n неизвестными:
a
11x1
+ … + a1n xn = b1 ;
a21x1 + … + a2n xn = b2 ;
………………………………
am1x1+ … + amnxn = bm .
Здесь x1, … , xn – неизвестные, а коэффициенты записаны так, что индексы при них указывают на номер уравнения и номер неизвестного. Значение систем 1ой степени определяется не только тем, что они простейшие. На практике часто имеют дело с заведомо малыми величинами, старшими степенями которых можно пренебречь, так что уравнения с такими величинами сводятся в первом приближении к линейным. Не менее важно, что решение систем линейных уравнений составляет существенную часть при численном решении разнообразных прикладных задач. Ещё Г.Лейбниц (1693) обратил внимание на то, что при изучении систем линейных уравнений наиболее существенной является таблица, состоящая из коэффициентов, и показал, как из этих коэффициентов (в случае m = n) строить так называемые определители, при помощи которых исследуются системы линейных уравнений. Впоследствии такие матрицы, или матрицы, стали предметом самостоятельного изучения, так как обнаружилось, что их роль не исчерпывается приложениями к теории систем линейных уравнений. Современная алгебра, понимаемая как учение об операциях над любыми математическими объектами, является одним из разделов математики, формирующих общие понятия и методы для всей математики. Для современной алгебры характерно то, что в центре внимания оказываются свойства операций, а не объектов, над которыми проводятся данные операции. Классическим разделом алгебры является линейная алгебра, т.е. теория векторных пространств и модулей, частью которых являются сформировавшиеся ещё в XIX веке теория линейных уравнений и теория матриц. Идеи и методы линейной алгебры применяются во многих разделах математики. Так, основным предметом изучения функционального анализа являются бесконечномерные векторные пространства.
1 Постановка задачи
Требуется разработать программу, реализующую основные операции алгебры матриц: сложение, вычитание, умножение, транспонирование, а также умножение матрицы на число.
Пример 1. Над матрицами А и В выполнить основные операции:
.
Сумма матриц:
.
Разность матриц:
.
Транспонирование матрицы A и B:
.
Умножение матрицы A на число 3:
.
Умножение
матриц
:
Пример 2. Над матрицами А и В выполнить основные операции:
.
Сумма матриц:
Невозможно вычислить сумму матриц, так как число строк матрицы A не равно числу строк матрицы B.
Разность матриц:
Невозможно вычислить разность матриц, так как число строк матрицы A не равно числу строк матрицы B..
Транспонирование матрицы A и B:
Так как матрица A не квадратная невозможно выполнить ее транспонирование.
.
Умножение матрицы A на число 5:
.
Умножение
матриц
:
.
2 Математические и алгоритмические основы решения задачи
2.1 Сумма матриц
Суммой двух матриц А и В одинаковых размеров называется матрица того же размера, элементы которой равны сумме соответствующих элементов матриц А и В. Таким образом, если
(1)
(2)
.
Операция нахождения суммы матриц называется сложением матриц и распространяется на случай конечного числа матриц одинаковы размеров.
2.2 Разность матриц
Так же, как и сумма, определяется разность двух матриц
Операция нахождения разности двух матриц называется вычитанием матриц. Проверкой можно убедиться, что операция сложения матриц удовлетворяет следующим свойствам:
А + В = В + А; (коммутативность)
А + (В + С) = (А + В) + С; (ассоциативность)
А + О = А.
Здесь А, В, С – произвольные матрицы одинаковых размеров; О – нулевая матрица того же размера.
2.3 Умножение матрицы на число λ
Произведением матрицы А = [аij] на число λ называется матрица, элементы которой получаются из соответствующих элементов матрицы А умножением их на число λ. Произведение обозначим λА. Таким образом от умножения матрицы (1) на число, получим:
,
то
Проверкой можно убедиться, что операция умножения матрицы на число удовлетворяет следующим свойствам:
1) А = А;
2) (λ + μ)А = λА + μΑ;
3) λ(А + В) = λΑ+ λВ;
4) λ( μА) = (λμ)А;
5) А + (-А) = О.
Здесь А, В – произвольные матрицы; μ, λ - произвольные числа; О – нулевая матрица.
2.4 Умножение матриц
Произведение АВ матрицы А на матрицу В определяется только в том случае, когда число столбцов матрицы А равно числу строк матрицы В. Пусть матрицы А и В такие, что число столбцов матрицы А равно числу строк матрицы В:
В этом случае произведением матрицы А на матрицу В, которые заданы в определенном порядке (А – 1ая, В – 2ая), является матрица С, элемент которой сij определяется по следующему правилу:
cij = ai1b1j + ai2b2j + … + ainbnj = ∑ n α = 1 aiαbαj,
где i = 1,2, …, m; j = 1, 2, …, k.
Для получения элемента сij матрицы произведения С = АВ нужно элементы i-й строки матрицы А умножить на соответствующие элементы j-го столбца матрицы В и полученные произведения сложить.
Число строк матрицы С = АВ равно числу строк матрицы А, а число столбцов – числу столбцов матрицы В.
Умножение матриц некоммутативно, т.е.
АВ ≠ ВА.
Проверкой можно показать, что умножение матриц удовлетворяет следующим свойствам:
1) А(ВС) = (АВ)С; (ассоциативность);
2) λ(АВ) = (λА)В = А(λВ);
3) А(В + С) = АВ + АС. (дистрибутивность).
Здесь А, В, С – матрицы соответствующих определению умножения матриц размеров; λ - произвольное число.
Операция умножения двух прямоугольных матриц распространяется на случай, когда число столбцов в 1ом множителе равно числу строк во 2ом, в остальных случаях произведение не определяется. А также, если матрицы А и В – квадратные одного и того же порядка, то умножение матриц всегда выполнимо при любом порядке следования сомножителей.
2.5 Транспонирование матрицы
Транспонированием матрицы называется такое преобразование матрицы, при котором строки и столбцы меняются ролями при сохранении номеров. Транспонированная матрица обозначается АТ.
.
Для квадратной матрицы это преобразование эквивалентно симметричному отображению относительно главной диагонали.
3 Функциональные модели и блок-схемы решения задачи
Функциональные модели и блок-схемы решения задачи представлены на рисунках 1 – 7.
Условные обозначения:
MATRIX1 – первая матрица;
MATRIX2 – вторая матрица;
ROW1, R1 – количество строк в первой матрице;
ROW2, R2 – количество строк во второй матрице;
COL1, C1 – количество столбцов в первой матрице;
COL2, C2 – количество столбцов во второй матрице;
RES_MATRIX – результирующая матрица;
OUTPUT_STREAM – выходной поток;
I, J P – рабочие переменные.
Рисунок 1 – Функциональная модель решения задачи для функции MODUL1
Рисунок 2 – Функциональная модель решения задачи для функции MODUL2
Рисунок 3 – Блок-схема решения задачи для функции SUM_MATRIX
Рисунок 4 – Блок-схема решения задачи для функции sub>TR_MATRIX
Рисунок 5 – Блок-схема решения задачи для функции MULT_NUMBER
Рисунок 6 – Блок-схема решения задачи для функции MULT_MATRIX
Рисунок 7 – Блок-схема решения задачи для функции FLIP
4 Программная реализация решения задачи
;СЧИТЫВАЕМ МАТРИЦУ
(SETF ROW_COL 0)
(SETQ INPUT_STREAM (OPEN " D:\MATRIX.TXT" :DIRECTION :INPUT))
;ПОЛУЧАЕМ РАЗМЕРНОСТЬ ПЕРВОЙ МАТРИЦЫ
(SETQ ROW_COL1 (READ INPUT_STREAM))
;ПОЛУЧАЕМ МАТРИЦУ
(SETF MATRIX1 (READ INPUT_STREAM))
;ПОЛУЧАЕМ СПИСОК ЧИСЕЛ, НА КОТОРЫЕ БУДЕМ УМНОЖАТЬ МАТРИЦУ
(SETQ LIST_NUM1 (READ INPUT_STREAM))
;ПОЛУЧАЕМ РАЗМЕРНОСТЬ ВТОРОЙ МАТРИЦЫ
(SETQ ROW_COL2 (READ INPUT_STREAM))
;ПОЛУЧАЕМ МАТРИЦУ
(SETF MATRIX2 (READ INPUT_STREAM))
;ПОЛУЧАЕМ СПИСОК ЧИСЕЛ, НА КОТОРЫЕ БУДЕМ УМНОЖАТЬ МАТРИЦУ
(SETQ LIST_NUM2 (READ INPUT_STREAM))
(CLOSE INPUT_STREAM)
;ЗАПИСЫВАЕМ ЧИСЛО СТРОК И СТОЛБЦОВ МАТРИЦЫ 1
(SETQ ROW1 (CAR ROW_COL1))
(SETQ COL1 (CADR ROW_COL1))
;ЗАПИСЫВАЕМ ЧИСЛО СТРОК И СТОЛБЦОВ МАТРИЦЫ 2
(SETQ ROW2 (CAR ROW_COL2))
(SETQ COL2 (CADR ROW_COL2))
;СЛОЖЕНИЕ МАТРИЦ
(DEFUN SUM_MATRIX (MATR1 MATR2 R1 R2 C1 C2)
;МАССИВ СУММЫ ДВУХ МАТРИЦ
(DECLARE (SPECIAL RES_MATRIX))
;ЕСЛИ ЧИСЛО СТРОК МАТРИЦЫ 1 НЕ РАВНО ЧИСЛУ СТРОК И СТОЛБЦОВ МАТРИЦЕ 2, ТО СЛОЖЕНИЕ МАТРИЦ НЕВОЗМОЖНО
(IF (OR (/= R1 R2) (/= C1 C2)) '"It is not possible to calculate the sum of matrices"
(PROGN
(SETQ RES_MATRIX (MAKE-ARRAY (LIST R1 C1) :ELEMENT-TYPE 'INTEGER :INITIAL-ELEMENT 0))
(DO
((I 0))
((>= I R1))
(DO
((J 0))
((>= J C1))
(SETF (AREF RES_MATRIX I J) (+ (AREF MATR1 I J) (AREF MATR2 I J)))
(SETQ J (+ J 1))
)
(SETQ I (+ I 1))
)
RES_MATRIX
)
)
)
;ВЫЧИТАНИЕ МАТРИЦ
(DEFUN sub>TR_MATRIX (MATR1 MATR2 R1 R2 C1 C2)
;МАССИВ РАЗНОСТИ ДВУХ МАТРИЦ
(DECLARE (SPECIAL RES_MATRIX))
;ЕСЛИ ЧИСЛО СТРОК МАТРИЦЫ 1 НЕ РАВНО ЧИСЛУ СТРОК И СТОЛБЦОВ МАТРИЦЕ 2, ТО ВЫЧИТАНИЕ МАТРИЦ НЕВОЗМОЖНО
(IF (OR (/= R1 R2) (/= C1 C2)) '"It is not possible to calculate the difference matrix"
(PROGN
(SETQ RES_MATRIX (MAKE-ARRAY (LIST R1 C1) :ELEMENT-TYPE 'INTEGER :INITIAL-ELEMENT 0))
(DO
((I 0))
((>= I R1))
(DO
((J 0))
((>= J C1))
(SETF (AREF RES_MATRIX I J) (- (AREF MATR1 I J) (AREF MATR2 I J)))
(SETQ J (+ J 1))
)
(SETQ I (+ I 1))
)
RES_MATRIX
)
)
)
;ПРОИЗВЕДЕНИЕ МАТРИЦЫ НА ЧИСЛО L
(DEFUN MULT_NUMBER (MATR ROW COL L)
(DECLARE (SPECIAL RES_MATRIX))
;ОБНУЛЯЕМ МАТРИЦУ РЕЗУЛЬТАТ
(SETQ RES_MATRIX (MAKE-ARRAY (LIST ROW COL) :ELEMENT-TYPE 'INTEGER :INITIAL-ELEMENT 0))
(DO
((I 0))
((>= I ROW))
(DO
((J 0))
((>= J COL))
(SETF (AREF RES_MATRIX I J) (* L (AREF MATR I J)))
(SETQ J (+ J 1))
)
(SETQ I (+ I 1))
)
RES_MATRIX
)
;ПРОИЗВЕДЕНИЕ МАТРИЦ
(DEFUN MULT_MATRIX (MATR1 MATR2 R1 R2 C1 C2)
(DECLARE (SPECIAL TEMP))
(DECLARE (SPECIAL RES_MATRIX))
(SETQ TEMP 0)
(IF (/= C1 R2) '"It is not possible to calculate products of matrices"
(PROGN
;ОБНУЛЯЕМ МАТРИЦУ РЕЗУЛЬТАТ
(SETQ RES_MATRIX (MAKE-ARRAY (LIST R1 C2) :ELEMENT-TYPE 'INTEGER :INITIAL-ELEMENT 0))
(DO
((I 0))
((>= I R1))
(DO
((J 0))
((>= J C2))
(SETQ TEMP 0)
(DO
((P 0))
((>= P C1))
(SETQ TEMP (+ TEMP (* (AREF MATR1 I P) (AREF MATR2 P J))))
(SETQ P (+ P 1))
)
(SETF (AREF RES_MATRIX I J) TEMP)
(SETQ J (+ J 1))
)
(SETQ I (+ I 1))
)
RES_MATRIX
)
)
)
;ТРАНСПОНИРОВАНИЕ МАТРИЦЫ
(DEFUN FLIP (MATR ROW COL)
(DECLARE (SPECIAL RES_MATRIX))
;ЕСЛИ КОЛИЧЕСТВО СТРОК И СТОЛБЦОВ НЕ РАВНО МАТРИЦУ НЕЛЬЗЯ ТРАНСПОНИРОВАТЬ
(IF (/= ROW COL) '"It is not possible to flip matrice"
(PROGN
;ОБНУЛЯЕМ МАТРИЦУ РЕЗУЛЬТАТ
(SETQ RES_MATRIX (MAKE-ARRAY (LIST COL ROW) :ELEMENT-TYPE 'INTEGER :INITIAL-ELEMENT 0))
(DO
((I 0))
((>= I ROW))
(DO
((J 0))
((>= J COL))
(SETF (AREF RES_MATRIX I J) (AREF MATR J I))
(SETQ J (+ J 1))
)
(SETQ I (+ I 1))
)
RES_MATRIX
)
)
)
;ПРИМЕНЕНИЕ "УМНОЖЕНИЯ МАТРИЦЫ НА ЧИСЛО" ДЛЯ СПИСКА
(DEFUN MULT1 (NUM)
(PRINT (MULT_NUMBER MATRIX1 ROW1 COL1 NUM) OUTPUT_STREAM)
)
;ПРИМЕНЕНИЕ "УМНОЖЕНИЯ МАТРИЦЫ НА ЧИСЛО" ДЛЯ СПИСКА
(DEFUN MULT2 (NUM)
(PRINT (MULT_NUMBER MATRIX2 ROW2 COL2 NUM) OUTPUT_STREAM)
)
;ЗАПИСЫВАЕМ РЕЗУЛЬТАТ
(SETQ OUTPUT_STREAM (OPEN " D:\RESULT.TXT" :DIRECTION :OUTPUT))
;МАТРИЦА 1
(PRINT (LIST 'MATRIX_1 MATRIX1) OUTPUT_STREAM)
;МАТРИЦА 2
(PRINT (LIST 'MATRIX_2 MATRIX2) OUTPUT_STREAM)
(PRINT '---------------------------- OUTPUT_STREAM)
;СЛОЖЕНИЕ МАТРИЦ
(PRINT (LIST 'SUM_MATRIX (SUM_MATRIX MATRIX1 MATRIX2 ROW1 ROW2 COL1 COL2)) OUTPUT_STREAM)
;РАЗНОСТЬ МАТРИЦ
(PRINT (LIST 'DIFFERENCE_MATRIX (sub>TR_MATRIX MATRIX1 MATRIX2 ROW1 ROW2 COL1 COL2)) OUTPUT_STREAM)
;УМНОЖЕНИЕ МАТРИЦ
(PRINT (LIST 'MULTIPLICATION_MATRIX (MULT_MATRIX MATRIX1 MATRIX2 ROW1 ROW2 COL1 COL2)) OUTPUT_STREAM)
(PRINT '---------------------------- OUTPUT_STREAM)
;ТРАНСПОНИРОВАНИЕ МАТРИЦЫ1
(PRINT (LIST 'FLIP_MATRIX1 (FLIP MATRIX1 ROW1 COL1)) OUTPUT_STREAM)
;ТРАНСПОНИРОВАНИЕ МАТРИЦЫ2
(PRINT (LIST 'FLIP_MATRIX2 (FLIP MATRIX2 ROW2 COL2)) OUTPUT_STREAM)
(PRINT '---------------------------- OUTPUT_STREAM)
;УМНОЖЕНИЕ МАТРИЦЫ1 НА ЧИСЛО
(PRINT 'MULTIPLICATION_MATRIX_ON_NUMBER OUTPUT_STREAM)
(PRINT (LIST 'NUMBERS LIST_NUM1) OUTPUT_STREAM)
(PRINT 'MATRIX1 OUTPUT_STREAM)
(MAPCAR 'MULT1 LIST_NUM1)
(PRINT '---------------------------- OUTPUT_STREAM)
;УМНОЖЕНИЕ МАТРИЦЫ2 НА ЧИСЛО
(PRINT (LIST 'NUMBERS LIST_NUM2) OUTPUT_STREAM)
(PRINT 'MATRIX2 OUTPUT_STREAM)
(MAPCAR 'MULT2 LIST_NUM2)
(TERPRI OUTPUT_STREAM)
(CLOSE OUTPUT_STREAM)
5 Пример выполнения программы
Пример 1.
Рисунок 8 – Входные данные
Рисунок 9 – Выходные данные
Пример 2.
Рисунок 10 – Входные данные
Рисунок 11 – Выходные данные
Заключение
Понятие матрицы возникло в связи с исследованием систем линейных уравнений. Однако в последующем это понятие оказалось настолько плодотворным, что стало основой нового раздела математики – матричной алгебры. Матричная алгебра получила широкое распространение при исследовании многих процессов, в том числе и экономических. Основные операции, которые производятся над матрицами: сложение, вычитание, умножение, транспонирование, а также умножение матрицы на число – являются основными операциями алгебры матриц – теории, играющей весьма важную роль в различных разделах математики и естествознания.
Итогом работы можно считать созданную функциональную модель для реализации операций над матрицами. Данная модель применима к матрицам любой размерности. Созданная функциональная модель и ее программная реализация могут служить органической частью решения более сложных задач.
Список использованных источников и литературы
Гантмахер, Ф.Р. Теория матриц (издание третье). [Электронный ресурс] / Ф.Р.Гантмахер. – М.: Наука, 2002, С. 218.
Дадаян, А.А. Алгебра и геометрия. [Текст] / А.А Дадаян, В.А.Дударенко. – М.: Минск, 1999. С. 342.
Калиткин, Н.Н. Численные методы. [Электронный ресурс] / Н.Н.Калиткин. – М.: Питер, 2001. С. 504.
Камалян, Р.З. Высшая математика. [Текст] / Р.З.Камалян. – М.: ИМСИТ, 2004. С.310.
Степанов, П.А. Функциональное программирование на языке Lisp. [Электронный ресурс] / П.А.Степанов, А.В.Бржезовский. – М.: ГУАП, 2003. С. 79.