Численные методы в экономике

вия 1-3.

     Идея метода состоит в следующем:

     Полагаем t 41 0= 7D 0t и решаем систему H(X,t 41 0)=0 при выбранном X 50 0. Полу-

чаем вектор  X 5t1 0.  Далее берем его в качестве начального приближения и

решаем при новом t 42 0=t 41 0+ 7D 0t систему H(X,t 42 0)=0,  получаем X 5t2 0 и так далее

до тех пор, пока не будет достигнута заданная точность. 

                   3. ТЕХНОЛОГИЯ РАЗРЕЖЕННЫХ МАТРИЦ 

                        ОСНОВНЫЕ ИДЕИ МЕТОДА. 

     Основные требования к этим методам можно свести в 3 утверждения:

     1. Хранить в памяти только ненулевые элементы.

     2. В процессе решения принимать меры, уменьшающие возможность по-

явления новых ненулевых элементов.

     3. Вычисления производить только с ненулевыми элементами. 

                     Разреженный строчный формат 

     Это одна  из  широко  используемых  схем для хранения разреженных

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

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

     Значения ненулевых элементов и соответствующие столбцовые индексы

хранятся по  строкам  в двух массивах:  NA и JA.  Для разметки строк в

этих массивах используется массив указателей  IA,  отмечающих  позиции

массивов AN и JA, с которых начинается описание очередной строки. Пос-

ледняя цифра в массиве IA содержит указатель первой свободной  позиции

в JA и AN.  Рассмотрим конкретный пример,  который будет также и далее

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

в качестве  контрольного  примера для программы,  выполняющей основные

операции с разреженными матрицами.

          -           ¬

          ¦ 3 0 0 5 0 ¦      Позиция:  1 2  3 4  5 6  7 8  9 10

          ¦ 0 4 0 0 1 ¦           IA:  1    3    5    7    9    11

      A = ¦ 0 0 8 2 0 ¦           JA:  1 4  2 5  3 4  1 4  2 5

          ¦ 5 0 0 6 0 ¦           AN:  3 5  4 1  8 2  5 6  7 9

          ¦ 0 7 0 0 9 ¦

          L           -

     Данный способ представления называется полным (так как  представ-

лена вся  матрица  А)  и упорядоченным (так как элементы каждой строки

хранятся в соответствии с возрастанием столбцовых индексов). Обознача-

ется RR(c)O - Row-wise representation Complete and Ordered (англ.).

     Массивы IA и JA представляют портрет матрицы А.  Если в алгоритме

разграничены этапы символической и численной обработки,  то массивы IA

и JA заполняются на первом этапе, а массив AN - на втором. 

                 Транспонирование разреженной матрицы 

     Пусть IA,  JA,  AN - некоторое представление разреженной матрицы.

Нужно получить IAT,  JAT, ANT - разреженное представление транспониро-

ванной матрицы. Алгоритм рассмотрим на нашем примере: 

     IA = 1 3 5 7 9 11

     JA = 1 4 2 5 3 4 1 4 2 5

     AN = 3 5 4 1 8 2 5 6 7 9 

     Символический этап.

     1. Заводим 5 целых списков по числу столбцов матрицы А.  пронуме-

руем их от 1 до 6.

     2. Обходим 1 строку и заносим 1 в те списки,  номера которых ука-

заны в JA:

                        1: 1

                        2:

                        3:

                        4: 1

                        5:

     3. Обходим вторую строку, вставляя аналогичным образом 2:

                        1: 1

                        2: 2

                        3:

                        4: 1

                        5: 2

     В итоге получим:

                        1: 1 4

                        2: 2 5

                        3: 3

                        4: 1 3 4

                        5: 2 5

     Массив ANT можно получить,  вставляя численное  значение  каждого

ННЭ, хранимое в AN,  в вещественный список сразу после того, как соот-

ветствующее целое внесено в целый список. В итоге получим:

     IAT = 1 3 5 6 9 11

     JAT = 1 4 2 5 3 1 3 4 2 5

     ANT = 3 5 4 7 8 5 2 6 1 9 

                  Произведение разреженной матрицы и

                     заполненного вектора-столбца 

     Алгоритм рассмотрим на нашем конкретном примере:

     IAT = 1 3 5 7 9 11

     JAT = 1 4 2 5 3 1 3 4 2 5

     ANT = 3 5 4 7 8 5 2 6 1 9

     B = ( -5 4 7 2 6 )

     Обработка 1 строки:

     Просматриваем массив IA и обнаруживаем, что первая строка матрицы

А соответствует  первому  и  второму  элементу  массива  JA:  JA(1)=3,

JA(2)=4, то есть ННЭ являются a 411 0 и a 414 0.

     Просматриваем массив AN и устанавливаем, что a 411 0=3 и a 414 0=5.

     Обращаемся к вектору B,  выбирая из него соответственно  b 41 0=-5  и

b 44 0=2.

     Вычисляем C 41 0= 3 * (-5) + 5 * 2 = -5.

     Абсолютно аналогично, вычисляя остальные строки, получим:

                         C = (-5 58 56 1 58). 

                 Произведение двух разреженных матриц 

     Рассмотрим метод на конкретном примере.  Предположим, что нам не-

обходимо перемножить две матрицы: 

     IA = 1 3 5 7 9 11

     JA = 1 4 2 5 3 4 1 4 2 5

     AN = 3 5 4 1 8 2 5 6 7 9 

     IAT = 1 3 5 7 9 11

     JAT = 1 4 2 5 3 1 3 4 2 5

     ANT = 3 5 4 7 8 5 2 6 1 9 

     Суть метода состоит в том, что используя метод переменного перек-

лючателя и расширенный вещественный накопитель, изменяется порядок на-

копления сумм для формирования элементов матрицы С.  Мы будем формиро-

вать элементы C 4ij 0 не сразу,  а постепенно накапливая, обращаясь только

к строкам матрицы B. 

     Символический этап. 

     Определяем мерность IX = 5

     IX = 0 0 0 0 0 

     1-я строка матрицы JAT: 1 4

       JA(1) = 1 4      JC(1) = 1 4

       IX = 1 0 0 1 0

       JA(4) = 1 4

       IX(1) = 1 ?  Да. JC(1) - без изменений

       IX(4) = 1 ?  Да. JC(1) - без изменений

     2-я строка матрицы JAT: 2 5

       JA(2) = 2 5      JC(2) = 2 5

       IX = 1 2 0 1 2

       JA(5) = 2 5   -> JC(2) - без изменений

     ....

     4-я строка матрицы JAT: 1 3 4

       JA(1) = 1 4      JC(4) = 1 4

       IX = 4 2 2 4 2

       JA(3) = 3 4

       IX(3) = 4 ? Нет. JC(4) = 1 4 3

       IX(4) = 4 ? Да.  JC(4) - без изменений

     ....

     в итоге получим:

     IC = 1 3 5 7 10 12

     JC = 1 4 2 5 3 4 1 4 3 2 5 

     Численный этап. 

     X = 0 0 0 0 0 

     1-я строка: JC(1) = 1 4

     AN(1) = 3 5,

        AA = 3

           ANT(1) = 3 5

           AA * ANT = 9 15

           X = 9 0 0 15 0

        AA = 5

           ANT(1) = 3 5

           AA * ANT = 15 25

           X = 24 0 0 40 0

     CN(1) = 24 40

     ....

     Аналогично проделывая действия над другими строками получим: 

     IC: 1       3       5      7          10     12

     JC: 1  4    2  5    3  4   1  4  3    2  5

     CN: 24 40   20 35   80 0   55 22 66   16 144 

     Все вышеприведенные операции были получены на  компьютере  и  ре-

зультаты совпали  для нашего контрольного примера.  Описание программы

на языке 2 C 0,  занимающейся этими операциями не приводится, так как дан-

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

ет распечатка этой программы. 

                 2ПРАКТИЧЕСКАЯ ЧАСТЬ. ОПИСАНИЯ ПРОГРАММ. 

     1. ЯВНЫЕ МЕТОДЫ.

     Данная группа представлена 3 программами, реализующими методы Эй-

лера,Рунге-Кутта 2-го и 4-го порядков.  В данной группе все  программы

индентичны, поэтому далее следует описание программы,  реализующем ме-

тод Эйлера,  с указанием различий для методов Рунге-Кутта 2-го и  4-го

порядков.

      1EILER.M

     Головной модуль.

     Входные и выходные данные: отсутствуют.

     Язык реализации: PC MathLab

    Операционная система: MS-DOS 3.30 or higher

     Пояснения к тексту модуля:

     Стандартный головной модуль.  Происходит очистка экрана,  задание

начальных значений по времени и по Y.  Затем происходит вызов подпрог-

раммы EIL.M (RG2.M или RG4.M для методов Рунге-Кутта 2 и 4 порядков) а

после получения результатов строятся графики.

      1EIL.M

     Вычислительный модуль.

     Входные данные:

     FunFcn -  имя  подпрограммы,  написанной  пользователем,  которая

возвращает левые части уравнения для определенного момента времени.

     T0, Tfinal - начальные и конечные моменты времени.

     Y0 - начальные значения.

     Выходные данные:

     Tout - столбец времени

     Yout - столбцы решений по каждой координате

     Язык реализации: PC MathLab

     Операционная система: MS-DOS 3.30 or higher

     Пояснения к тексту модуля:

     Данный модуль  и реализует собственно метод Эйлера (Рунге-Кутта 2

или 4-го порядков). В начале происходит инициализация внутренних пере-

менных, а также вычисление максимального шага, который затем использу-

ется для определения точности.  Далее следует цикл While...End  внутри

которого и выполняются все необходимые действия:  по формуле (для каж-

дого метода своя!) вычисляется значение Y на каждом шаге (при  необхо-

димости вызывается  подфункция  FunFcn)  а  также формируются выходные