Реферат: "Комплект" заданий по численным методам - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

"Комплект" заданий по численным методам

Банк рефератов / Математика

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 30 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

2ВВЕДЕНИЕ В экономике очень часто используется модель , назыв аемая "черный ящик ", то есть система у которой и звестны входы и выходы , а то , что происходит внутри - неизвестно . Законы по которым происходят изменения выходных сигналов в зависимости от в ходных могут быть различными , в том числе это могут быть и д ифференциальные законы . Тогда встает проб- лема решения систем дифференциальных урав нений , которые в зависимости от своей структуры могут быть решены различными методами . Точное реше- ние получить очень часто не удается , поэтому мы рассмотрим численные методы решения таких систем . Далее мы представим две группы методов : явные и неявные . Для решения систем ОДУ неявными методами придется ре- шать системы нелинейных уравнений , поэтом у придется ввести в рассмот- рение группу методов решения систем нелин ейных уравнений , которые в свою очередь будут представлены двумя методами . Далее следуют теорети- ческие аспекты описанных методов , а з атем будут представлены описания программ . Сами программы , а также их графики приведены в приложении. Также стоит отметить , что в п ринципе все численные методы так или иначе сводятся к матрично й алгебре , а в экономических задачах очен ь часто матрицы имеют слабую заполненность и большие размеры и поэтому неэффективно работать с полными матрицами . Одна из технолог ий , позво- ляющая разрешить данную проблему - технол огия разреженных матриц. В связи с этим , мы рассмотрим данн ую технологию и операции умножения и транспонирования над такими матрицами. Таким образом мы рассмотрим весь спектр лабораторных работ. Опи- сания всех программ приводятся после теоретической части . Все тексты программ и распечатки графиков приведены в приложении. 2ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 1. ОПИСАНИЕ МЕТОДОВ ИНТЕГРИРОВАНИЯ СИСТЕМ ОДУ И ИХ ХАРАКТЕРИСТИК ЯВНЫЙ МЕТОД ЭЙЛЕРА И ЕГО ХАРАК ТЕРИСТИКИ Алгоритм этого метода определяется ф ормулой : x 5m+1 0 = x 5m 0 + h 4m 0*F(x 5m 0, t 4m 0) 4, 0 (1) которая получает ся путём аппроксим ации ряда Тейлора до членов перво- го порядка производной x'(t 4m 0),т.к . порядок точности равен 1 (s=1). Для аналитического исследования свойств метода Эйлера линеари- зуется исходная система ОДУ x' = F(x, t) в точке (x 5m 0,t 4m 0): x' = A*x, (2) где матрица А зависит от точки линеаризации (x 5m 0,t 4m 0). Входной сигнал при линеаризации явля ется неизвестной функцией времени и при фиксированном t 4m 0 на шаге h 4m 0 может считаться констан- той . Ввиду того ,что для линейной системы свойство устойчивости за- висит лишь от А , то входной сиг нал в системе (2) не показан . Элемен- ты матрицы А меняются с изменением точки линеаризации,т.е . с измене- нием m. Характеристики метода : 1. _Численная устойчивость .. Приведя матрицу А к диагональной форме : А = Р * 7l 0*Р 5-1 0 и перейдя к новым переменным y = P 5-1 0*x , система (2) приме т вид : y' = 7l 0 *y (3) Тогда метод Эйлера для уравнения (3) будет иметь вид : y 5m+1 0 = y 5m 0 + h* 7l 0 * y 5m 0, (4) где величина h* 7l 0 изменяется от шага к шагу. В этом случ ае характеристическое уравнение для дискретной сис- темы (4) будет иметь вид : 1 + h* 7l 0 - r = 0. А корень характеристического уравнения равен : r = 1+ h* 7l 0, где 7l 0 = 7 a 0 _+ . 7 b 0 . _Случай 1 .. Исходная система (3) являе тся асимптотически устой- чивой , т.е . нулевое состояние равновесия системы асимптотически ус- тойчиво и 7 a 0 < 0. Областью абсолютной устойчивости метода интегрирования системы (4) будет круг радиусо м , равным 1 , и с центром в точке (0, -1). Таким образом , шаг h должен на каждо м интервале интегрирования под- бираться таким образом , чтобы при э том не покидать область А . Но в таком случае должно выполняться требование : h < 2* 7t 0, (5) где 7t 0=1/ 72a2 0 - постоянная времени системы (3) . Она определяет ско- рость затухания переходных процессов в ней . А время переходного про- цесса T 4пп 0 = 3* 7t 0 , где 7t 0 = 72a2 5-1 0. Если иметь ввиду , что система (3) n-го порядка , то T 4пп 0 > 3* 7t 4max 0, где 7t 4max 0 = 72a 4min 72 5-1 7 0; 7a 4min 0= min 7a 4i 0 . Из всех 7a 4i 0 (i=[1;n]) выби рает- ся максимальное з начение : max 72a 4i 72 0= 7a 4max 0 и тогда можно вычислить : 7t 4min 0= 1/ 7a 4max 0, а шаг должен выбираться следующим образом : h < 2/ 7a 4max 0 или h < 2* 7t 4min 0. _Случай 2 .. Нулевое сос тояние равно весия системы (2) неустойчи- во , т.е . 7a 0 > 0 . Т.е . система тоже неустой чива , т.е . 72 0r 72 0>1. Поэтому областью относительной устойчивости явног о метода Эйлера является вся правая полуплоскость . Выполняется требование : 72 0 1+h* 7l 0 72 0< 7 2 0e 5hl 7 2 0 (6) 2. _Точность метода .. Так как формула интегрирования (1) аппр оксимирует ряд Тейлора для функции x(t 4m 0+1) до линейного по h чл ена включительно . Су ществует такое значение t в интервале [t 4m 0 , t 4m+1 0], при котором Е 4i 5am 0 =1/2! * h 4m 52 0*x 4i 0''(t), где i=[1;n]. 3. _Выбор шага интегрирования .. Должны соблюдаться условия абсолютной (5) или отно сительной (6) устойчивости в зависимости от характе ра интегрируемой системы. Для уравнения первого порядка шаг должен быть : h < 2* 7t 0 . Для уравнений n-ого порядка : h 4i 0 <= 2* 7t 4i 0. А окончательно шаг выбирают по усл овиям устойчивости : h < 2* 7t 4min 0 , 7t 4min 0 = min 7t 4i Вначале задаётся допустимая ошибка апп роксимации , а в процессе ин- тегрирования шаг подбирается следующим образ ом : 1) по формуле (1) определяется очередное з начение x 5m+1 0; 2) определяется dx 4i 5m 0 = x 4i 5m+1 0 - x 4i 5m 0 ; 3) условие соблюдения точности имеет ви д : h 4i 5m 0 <= E 4i 5aдоп 7/ 0[ 72 0f 4i 0(x 5m 0,t 4m 0) 72 0 + E 4i 5aдоп 7/ 0h 4max 0] (7) 4) окончательно на m-м интервале времени выбирается в виде : h 4m 0 = min h 4i 5m 0. ЯВНЫЕ МЕТОДЫ РУНГЕ-КУТТА Метод Эйлера является ме тодом Рунге-Кутта 1-го порядка . Методы Рунге-Кутта 2-го и 4-го порядк а являются одношаговыми , согласуются с рядом Тейлора до пор ядка точности s , который равен порядку метода . Эти методы не тре буют вычисления производных функ ций , а только самой функции в нескольких точках на шаге h 4m 0. Алгоритм метода Рунге-Кутта 2-го порядк а состоит в следующем : x 5m+1 0 = x 5m 0 + h 4m 0/2 (k 41 0+k 42 0), где k 41 0=f(x 5m 0,t 4m 0) ; k 42 0=f(x 5m 0+h 4m 0*k 4 1 0,t 4m 0+h 4m 0). Ошибка аппроксимации Е 5a 0 = k*h 4m 53 0 . Алгоритм метода Рунге-Кутта 4-го порядк а x 5m+1 0=x 5m 0+h 4m 0/6(k 41 0+2k 42 0+2k 43 0+k 44 0), где k 41 0=f(x 5m 0,t 4m 0); k 42 0=f(x 5m 0+h 4m 0/2*k 41 0,t 4m 0+h 4m 0/2); k 43 0=f(x 5m 0+h 4m 0/2*k 42 0,t 4m 0+h 4m 0/2); k 44 0=f(x 5m 0+h 4m 0*k 43 0,t 4m 0+h 4m 0). Ошибка аппроксимации Е 5a 0 = k*h 4m 55 0. НЕЯВНЫЙ МЕТОД ЭЙЛЕРА И ЕГО ХАРА КТЕРИСТИКИ Неявный метод Эйлера используетс я для интегрирования " жест- ких " систем . "Жесткие " системы это та кие системы , в которых 7 0 ( 7l 4max 0) и ( 7l 4min 0) сильно отключаются друг от д руга , то в решениях системы x' = A*x (1) будут присутствовать экспоненты , сильно отличаются друг от друга по скорости затухания . Шаг интегрирования для таких систем должен вы- бираться по условиям устойчивости из неравенства h <= 2 * 7t 4min , 0 (2) где 7t 0=1/ 72a2 0 - постоянная времени системы y' = 7l 0*y . Она определяет скорость затухания переходных процессов в ней . Неравенство (2) должно выполняться на всем участке решения , что соответс твенно тре- бует значительных затрат машинного вре мени. Алгоритм этого метода определяется ф ормулой : x 5m+1 0 = x 5m 0 + h 4m 0*F(x 5m+1 0, t 4m+1 0) 4 0(3) Если h 4m 0 мал , то x 5m 0 и х 5m+1 0 близ ки друг к другу . В качестве на- чального приближения берется точка x 5m 0 , а следовательно , между x 5m 0 и x 5m+1 0 будет существовать итерационный процесс. Для аналитического исследования свойств метода Эйлера линеа- ризуется исходная с истема ОДУ x' = F(x, t) в точке (x 5m 0,t 4m 0): x' = A*x, где матрица А зависит от точки линеаризации (x 5m 0,t 4m 0). Входной сигнал при линеаризации явля ется неизвестной функцией времени и при фиксированном t 4m 0 на шаге h 4m 0 может считаться констан- той . Ввиду того ,что для линейной системы свойство устойчивости за- висит лишь от А , то входной сиг нал в системе (1) не показан . Элемен- ты матрицы А меняются с изменением точки линеаризации,т.е . с измене- нием m. Характеристики метода : 1. _Численная устойчивость .. Приведя матрицу А к диагональной форме : А = Р * 7l 0*Р 5-1 0 и перейдя к новым переменным y = P 5-1 0*x , система (3) приме т вид : y' = 7l 0*y (4) Тогда метод Эйлера для уравнения (4) будет иметь вид : y 5m+1 0 = y 5m 0 + h* 7l 0 * y 5m+1 0, (5) где величина h* 7l 0 изменяется от шага к шагу. В этом сл учае характеристическое уравнение для дискретной сис- темы (5) будет иметь вид : 1 - h* 7l 0*r - 1 = 0. А корень характеристического уравнения равен : r = 1/(1-h* 7l 0) , где 7l 0 = 7 a 0 _+ . 7 b 0 . _Случай 1 .. Исходная система (4) является асимптотически устой- чивой , т.е . нулевое состояние равновесия системы асимптотически ус- тойчиво и 7 a 0 < 0. Областью абсолютной устойчивости метода интегрирования системы (5) будет вся левая полуплоскость . Т аким образом , шаг h должен на каждом интервале интегрирования подбиратьс я таким образом , чтобы при этом не покидать эту область . Но в таком случае должно выполняться требование : h < 2* 7t 0, (6) где 7t 0=1/ 72a2 0 - постоянная времени системы (4) . Она определяет ско- рость затухания переходных процессов в ней . А время переходного про- цесса T 4пп 0 = 3* 7t 0 , где 7t 0 = 72a2 5-1 0. Если иметь ввиду , что система (4) n-го порядка , то T 4пп 0 > 3* 7t 4max 0, где 7t 4max 0 = 72a 4min 72 5-1 7 0; 7a 4min 0= min 7a 4i 0 . Из всех 7a 4i 0 (i=[1;n]) выби рает- ся максимальное значение : max 72a 4i 72 0= 7a 4max 0 и тогда можно вычислить : 7t 4min 0= 1/ 7a 4max 0, а шаг должен выбираться следующим образом : h < 2/ 7a 4max 0 или h < 2* 7t 4min 0. _Случай 2 .. Нулевое состояние равновесия системы (4) неустойчи- во , т.е . 7a 0 > 0 . Т.е . система тоже неусто йчива , т.е . 72 0r 72 0>1, а следовательно : 72 0 1/(1-h* 7l 0) 72 0 > 1. С учетом ограничения на скорость изменения приближенного ре- шения относительно точн ого : 72 0 1/(1-h* 7l 0) 72 0 > 7 2 0e 5hl 7 2 0. (7) Из этого соотношения следует , что при 72 0h* 7l2 0 -> 1 левая часть стремится к бесконечности . Это означае т , что в правой полуплоскос- ти есть некоторый круг радиусом , равным 1 , и с центром в точке (0, 1), где неравенство (7) не выполняется. 2. _Точность метода .. Ошибка аппроксимации по величине рав на ошибке аппроксимации явного метода Эйлера , но она против ополо жна по знаку : Е 4i 5am 0 =-1/2! * h 4m 52 0*x 4i 0''(t), где t 4m 0 <= t <= t 4m+1 0, i=[1;n]. 3. _Выбор шага интегрирования .. Должны соблюдаться условия абсолютной (6) или относительной (7) устойчиво сти в зависимости от характера интегрируемой системы. Для уравнения первого порядка шаг должен быть : h < 2* 7t 0 . Для уравнений n-ого порядка : h 4i 0 <= 2* 7t 4i 0. О днако область абсолютной устойч ивости - вся левая полуплос- кость . Поэтому шаг с этой точки зрения может быть любым. Условия относительной устойчивости жестч е , так как есть об- ласть , где они могут быть нарушены . Эти условия будут выполня ться , если в процессе решения задачи кон тролировать ошибку аппроксимации , а шаг корректировать . Таким образом , шаг можно выбирать из условий точности , при этом условия устойчивости будут соблюдены автоматичес- ки . Сначала задается допустимая по грешность аппроксимации : E 4i 5aдоп 0 <= 0,001 72 0x 4i 72 4max 0, где i=[1;n]. Шаг выбирается в процессе интегриров ания следующим образом : 1. Решая систему (3) относительно x 5m+1 0 с шаг ом h 4m 0, получаем о чередную точку решения системы x = F(x,t) ; 2. Оцениваем величину ошибки аппроксимации по формуле : Е 4i 5am 0 = 72 0h 4m 7/ 0(h 4m 0+h 4m-1 0)*[(x 4i 5m+1 0 - x 4i 5m 0) - h 4m 7/ 0h 4m-1 0*(x 4i 5m 0 -x 4i 5m-1 0)] 72 3. Действи тельное значение аппроксимац ии сравнивается с до- пустимым . Если Е 4i 5am 0 < E 4i 5aдоп 0, то выпо лняется следующий пункт , в про- тивном случае шаг уменьшается в дв а раза , и вычисления повторяются с п .1. 4. Рассчитываем следующий шаг : h 4i 5m+1 0 = SQR(E 4i 5aдоп 7/2 0Е 4i 5am 72 0) * h 4m 0. 5. Шаг выбирается одинаковым для всех элементов вектора X : h 4m+1 0 = min h 4i 5m+1 0. 6. Вычисляется новый момент времени и алгорит м повторяется . НЕЯВНЫЕ МЕТОДЫ РУНГЕ-КУТТА Метод Эйлера является методом Рунге- Кутта 1-го порядка . Методы Рунге-Кутта 2-го и 4-го порядк а являются одношаговыми , согласуются с рядом Тейлора до пор ядка точ ности s , который равен порядку метода . Эти методы не тре буют вычисления производных функций , а только самой функции в нескольких точках на шаге h 4m 0. Алгоритм метода Рунге-Кутта 2-го поряд ка состоит в следующем : x 5m+1 0 = x 5m 0 + h 4m 0/2 (k 41 5m+1 0+k 42 5m+1 0), где k 41 5m+1 0=f(x 5m+1 0,t 4m+1 0); k 42 5m+1 0=f(x 5m+1 0-h 4m 0*k 41 5m+1 0,t 4m+1 0). Ошибка аппроксимации Е 4m 5a 0 = k*h 4m 53 0 . Алгоритм метода Рунге-Кутта 4-го поря дка x 5m+1 0 = x 5m 0 + h 4m 0/6 (k 41 5m+1 0+2k 42 5m+1 0+2k 43 5m+1 0+k 44 5m+1 0), где k 41 0=f(x 5m+1 0,t 4m+1 0); k 42 0=f(x 5m+1 0-h 4m 0/2*k 41 5m+1 0,t 4m+1 0-h 4m 0/2); k 43 0=f(x 5m+1 0-h 4m 0/2*k 42 5m+1 0,t 4m +1 0-h 4m 0/2); k 44 0=f(x 5m+1 0-h 4m 0*k 43 5m+1 0,t 4m 0). Ошибка аппроксимации Е 5a 0 = k*h 4m 55 0. 2. МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ САУ МЕТОД НЬЮТОНА Итерационная формула метода Ньютона имеет вид X 5m+1 0=X 5m 0- 5 0J 5-1 0* 5 0(X 5m 0) 5 0* 5 0F(X 5m 0), где J(X)=F 4x 5| 0/ 4x=xm Характеристики метода : 1. Сходимость . Покажем , что в точке P(G 4x 5| 0(X 5* 0))=0 Здесь G(x)=X - J 5-1 0(x) * F (x) - изображение итерационно го процес- са . Условие сходимости метода : P(G 4x 5| 0(X)) < 1 должн о выполняться для всех значений X 5m 0. Это условие осуществляе тся при достаточно жестких требованиях к F(x): функция должна быть н епрерывна и дифференц ируема по X, а также выпукла или вогнута в близи X 5* 0. При этом выполняется лишь условие локальной сходимости . Причем можн о показать , что чем ближе к X 5* 0, тем быстрее сходится метод. 2. Выбор начального приближения X 50 0 - выбирает ся достаточно близко к точному решению . Как именно близко - зависит от скорости изменения функции F(x) вблизи X 5* 0: чем выше скорость , тем меньше область , где соблюдается условие сходимости и следова тельно необходимо ближе выби- рать X 50 0 к X 5* 0. 3. С корость сходимости определяется соотношением ¦ E 5m+1 0¦ = C 4m 0 * ¦ E 5m 0¦ 51+p 0, 0 < P < 1. При X -> X 5* 0 величина P -> 1. Это значит , что вблизи точного реше- ния скорость сходимости близка к квад ратичной . Известно , что мет ода Ньютона сходится на 6-7 итерации. 4. Критерий окончания итераций - здесь мо гут использоваться кри- терии точности , то есть максимальная и з норм изменений X и F(x). ДИСКРЕТНЫЙ МЕТОД НЬЮТОНА Трудность использования мет ода Нь ютона состоит в 1. Необходимости вычисления на каждом э тапе J=F 4x 5| 0. Возможно несколько путей решения : - аналитический способ . Наиболее эффективен , однако точные форму- лы могут быть слишком большими , а также функции могут быть зад аны таб- лично. - конечно-разностная аппроксимация : dF 4i 0 F 4i 0(x 41 0,...,x 4j 0+dx 4j 0,...,x 4n 0) - F 4i 0(x 41 0,...,x 4j 0-dx 4j 0,...x 4n 0) --- = -------------------------------------------------- dX 4j 0 2*dX 4j В этом случае мы имеем уже дис кретный метод Ньютона , который уже не обладает квадратичной сходимостью . Ско рость сходимости можно увели- чить , уменьшая dX 4j 0 по мере приближения к X 5* 0. 2. Вычисление матрицы J 5-1 0 на каждом шаге требует значительных вы- числительных затрат , поэтому часто решают такую систему : dX 5 0= 5 0J 5-1 0(X 5m 0) 5 0* 5 0F(X 5m 0) или умножая правую и левую часть на J, получим : J(X 5m 0) 5 0* 5 0dX 5m 0= 5 0F(X 5m 0) На каждом M-ом шаге матрицы J и F известны . Необходимо найти dX 5m 0, как решение вышеприведенной системы линей ных АУ , тогда X 5m+1 0=X 5m 0+dX 5m Основной недостаток метода Ньютон а - его локальная сходимость, поэтому рассмотрим еще один метод. МЕТОД ПРОДОЛЖЕНИЯ РЕШЕНИЯ ПО ПАРАМ ЕТРУ Пусть t - параметр , меняющийся от 0 до 1. Введем в рассмотрение некоторую систему H(X,t)=0, такую , что : 1. при t=0 система имеет решение X 50 2. при t=1 система имеет решение X 5* 3. вектор-функция H(X,t) непрерывна по t. Вектор функция может быть выбрана несколькими способами , например H(X,t) = F( X) + (t-1) или H(X,t) = t * F(X) Нетрудно проверить , что для этих в ектор-функций выполняются усло- вия 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 Math Lab Операционная система : MS-DOS 3.30 or higher Пояснения к тексту модуля : Данный модуль и реализует собственно метод Эйлера (Рунге-Кутта 2 или 4-го порядков ). В начале происходит инициализация внутренних пере- менных , а также вычисление ма ксима льного шага , который затем использу- ется для определения точности . Далее следует цикл While...End внутри которого и выполняются все необходимые действия : по формуле (для каж- дого метода своя !) вычисляется значение Y на каждом шаге (при необхо- д имости вызывается подфункция FunFcn) а также формируются выходные значения Tout и Yout. Далее метод сам коррект ирует свой шаг , по форму- ле описанной выше (в теоретическом раз деле ). Этот цикл выполняется до тех пор , пока значение Tfinal не будет дости гнуто . Все выходные значе- ния формируются внутри данного цикла и поэтому никаких дополнительных действий не требуется . В связи с э тим с окончанием цикла заканчивается и подпрограмма EIL.M. Методы Рунге-Кутта реали зованы аналогично , с учетом отличий в формулах вычислени й (более сложные по сравнению с ме- тодом Эйлера ). 2. НЕЯВНЫЕ МЕТОДЫ. Представлены группой из двух похожих между собой программ , реали- зующих соответственно неявные методы Эйле ра и Рунге-Кутта 2 порядка. Также как и в вышеп риведенном случае , будет описан метод Эйлера , а от- личия метода Рунге-Кутта будут отмечены в скобках. 1NME.M Головной модуль. Входные и выходные данные отсутствуют. Язык реализации : PC MathLab Операционная система : MS-DOS 3.30 or higher Пояснения к тексту модуля : Выполняет стандартные действия : очистка экрана , инициализация и ввод начальных значений , вызов подпрограм м обработки и вычислений , а также построение графиков. 1NMEF.M, NRG2.M Вычислительные модул и. Входные данные : T0, Tfinal - начальные и конечные моменты време ни X0 - вектор-столбец начальных значений. H - начальный шаг A - матрица , на диагонали которой стоят собственные числа линеа- ризованной системы ОДУ. Выходные данные : T - столбец времени X - столбец решений 7D 0X - столбец ошибки Пояснения к тексту модуля : Стандартные действия : инициализация начал ьных значений , цикл While T < Tfinal, вычисление по формулам , вывод пром ежуточных рез уль- татов , формирование выходных значений мас сивов. 3. МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ САУ Представлены группой из 4-х методов : метод последовательных приб- лижений , метод Ньютона , метод Ньютона дискретный , метод продолжения решения по параметру. Метод последовательных приближений. 1MMPP.M Головной модуль. Входные и выходные данные отсутствуют. Язык реализации : PC MathLab Операционная система : MS-DOS 3.30 or higher Пояснения к тексту модуля : Очи стка экрана , инициализация нача льных значений , вызов вычисли- тельного модуля MPP.M, вывод результатов в виде графиков. 1MPP.M Вычислительный модуль. Входные данные : X0 - начальное приближение в виде вектора- строки Fun1 - функция , возвращающая вычисленные левые части Fun2 - функция , возвращающая матрицу Якоби в определенной точке. E - допустимая ошибка. Выходные данные : Mout - номера итераций Xout - приближения на каждой итерации DXout - ошибка на каж дой итерации Язык реализации : PC MathLab Операционная система : MS-DOS 3.30 or higher Пояснения к тексту модуля : Аналогичен вышеприведенным вычислительным модулям - инициализация начальных значений , вычисления по формула м , вывод проме жуточных ре- зультатов , формирование выходных значений . По мере необходимости вызы- вает подпрограммы Fun1 и Fun2. Методы Ньютона и Ньютона дискретны й 1MNEWT.M Головной модуль. Входные и выходные данные отсутствуют. Я зык реализации : PC MathLab Операционная система : MS-DOS 3.30 or higher Пояснения к тексту модуля : Стандартный головной модуль - выполняет действия , аналогичные предыдущим головным модулям . Вызывает из себя NEWT.M и NEWTD.M - моду- ли реа лизующие методы Ньютона и Ньютона дискретный , а также строит их графики на одной координатной сетке. 1NEWT.M, NEWTD.M Вычислительные модули. Входные данные : X0 - начальное приближение в виде вектора- строки Fun1 - функция , возвра щающая левые част и Fun2 - функция , вычисляющая матрицу Якоби (т олько для метода Ньютона !) E - допустимая ошибка Выходные данные : Mout - номера итераций Xout - приближени я на каждой итерации DXout - ошибка на каждой итерации Язык реализации : PC MathLab Операционная система : MS-DOS 3.30 or higher Пояснения к тексту модулей : Стандартные вычислительные модули , произв одящие соответствующие им действи я . Отличие их в том , что в первом случае для вычисления м ат- рицы Якоби вызывается подпрограмма , а во втором случае матрица Якоби вычисляется внутри модуля. Метод продолжения решения по парам етру 1MMPRPP.M Головной модуль. Входные и выходные данные отс утствуют. Язык реализации : PC MathLab Операционная система : MS-DOS 3.30 or higher Пояснения к тексту модуля : Стандартный головной модуль со всеми вытекающими отсюда последс- твиями. 1MPRPP.M Вы числительный модуль. Входные данные : Fun1 - имя подпрограммы , вычисляющей правые части Fun2 - имя подпрограммы , вычисляющем матрицу Якоби X0 - начальное приближение dT - начальный шаг Edop - допустимая ошибка Trace - выво д на экран Язык реализации : PC MathLab Операционная система : MS-DOS 3.30 or higher Пояснения к тексту модуля : Стандартный вычислительный модуль - инициа лизация , вычисление, вывод , формирование результата . Стоит отме тить , что поско льку метод имеет глобальную сходимость , то объем вычислений тут значительный , а это значит , что при выполнении вычисле ний требуется значительное коли- чество свободной оперативной памяти. 2ВЫВОДЫ При выполнении дан ных лабораторны х работ были изучены основные численные методы для решения ОДУ , САУ , а также технология разреженных матриц . Заодно были получены основные навыки в программировании мате- матической системы PC MathLab. Каждый из представ ленных методо в по своему хорош и применяется для систем определенного вида. 2Теоретическая часть. В данной расчетно-графической работе (д алее РГР ) требует- ся составить программу для решения си стемы нелинейных уравне- ний методом после довательной итерации обратной матрицы Якоби. Суть метода в следующем : Пусть требуется решить систему нелине йных алгебраических или трансцендентных уравнений : F 41 0(X 41 0,X 42 0,...,X 4n 0)=0; i=1,2,...,n, с начальным приближением к решен ию : X 50 0=(x 41 50 0,x 42 50 0,...x 4n 50 0). Вычислительная схема реализованного метод а состоит в сле- дующем : В начале итерационного процесса матри ца H полагается рав- ной единичной : H 50 0=E. Зате м для k=0,1,... 1. Вычисляется P 5k 0= 5 0- 5 0H 5k 0* 5 0F(X 5k 0); 2. Находятся X 5k+1 0= 5 0X 5k 0+ 5 0t 5k 0*P 5k 0. Первоначально t 5k 0=1. Затем путем последовател ьного деления t 5k 0 на 2 находим такое t 5k 0, чтобы выполнялос ь неравенство : ¦ F(X 5k+1 0) ¦ < ¦ F(X 5k 0) ¦ Итерационный процесс заканчивается при выполнении усло- вия : ¦ F(X 5k+1 0) ¦ < E, где E - заданная точность. 3. Определяется Y 5k 0= F(X 5k+1 0) - F(X 5k 0) 4. Находится новое приближение матрицы : H 5k+1 0= 5 0H 5k 0- 5 0(H 5k 0*Y 5k 0- 5 0P 5k 0*t 5k 0) 5 0* 5 0(P 5k 0) 5T 0* 5 0(H 5k 0) 5T 0/ 5 0((P 5k 0) 5T 0* 5 0H 5k 0*Y 5k 0) и снова повторяется вычислительный пр оцесс с пункта 1. 2Порядок работы с программой Данная РГР представлена в виде 3 и сполняемых модулей : 1OBRJ.M, OBRF.M и FUN1.M. 0 Решением поставленной задачи з анима- ется модуль 1 OBRF.M 0, а два остальных являю тся вспомогательными : 1OBRJ.M - 0 головной модуль , в котором вводятся входные данные и выводятся результаты вычислений , а 1 FUN1.M - 0 мо дуль , который пишет сам пользователь и который возв ращает выч исленные левые части для требуемого уравнения. В головной программе задаются начальн ые приближения , в - 3 - виде вектора X0 а также запрашивается д опустимая ошибка . Затем вызывается модуль 1 OBRJ.M, 0 который и реа лизует решение данной системы уравнений методом последовательной итерации обратной матрицы Якоби . Внутри себя данный моду ль по мере необходимости вызывает функцию 1 FUN1.M 0, которую пишет сам пользователь. 2Описание работы п рограмм В связи с тем , что данная РГР состоит из 3 частей , то опишем их по одиночке (распечатки дан ных модулей приведены в приложении ): 1. 1 OBRJ.M Головной модуль Входные данные : отсутствуют. Выходные данные : отсутствуют. Язык реализации : PC MathLab. Операционная система : MS-DOS 3.30 or Higher. Пояснения к тексту модуля : "Стандартный " головной модуль . В данном модуле задаются начальные значения в виде вектора , нап ример : X 40 0=[0 .4 0.9] Также в данном модуле запрашивается допустимая ошибка, очищается экран , а также производятся другие подготовительные действия. Затем происходит вызов модуля 1 OBRF.M 0 с полученными вход- ными данными . Формат вызова данного м одуля описан далее (в описании самого модуля ). После вычислений в головную программу возвращаются ре- зультаты вычислений на основе которых строятся графики а также выводятся оценки по затратам машинного времени и быстродейс- твия. 2. 1 OBRF. M Вычислительный модуль Входные данные : FunFcn - имя функции , написанной пользователем , которая вычисляет левые части для требуемой системы в определенной точке. X0 - вектор-строка , определяющий начальные зна чения (на- чальное п риближение ). E - допустимая ошибка. Выходные данные : Tout - Столбец итераций ("Время ") Xout - Столбцы значений вычисленных на каж дом этапе для каждой итерации DXout - Столбцы погрешностей по каждой комп оненте , вычис- ленные на определенном этапе Язык реализации : PC MathLab Операционная система : MS-DOS 3.30 or Higher Пояснения к тексту модуля : Данный "вычислительный " модуль реализует метод последова- - 5 - тельной итерации о братной матрицы Якоби . Общая структура вызо- ва данного модуля : [T 4out 0,X 4out 0,DX 4out 0]=OBRF(FunFcn,X 40 0,E); Значения каждого из параметров были описаны выше. На начальном этапе в данном модул е инициализируются внут- ренние пере менные (например , задается единичная матрица H, в соответствии с размерностью X0), формируются (на основе на- чальных значений ) первичные элементы матр иц Tout,Xout,DXout. Затем данная функция , как и многие другие в численных методах, имеет вид : While ОШИБКА > ДОПУСТИМОЙ ОШИБКИ Оператор 1 Оператор 2 ......... ......... Оператор N End Внутри данного цикла происходят вычис ления внутренней пе- ременной P 5k 0 на каждом шаге K и , вычисляе тся начальное прибли- ж ение X 5k+1 0. Первоначально t=1 (Не номер итерации , а внутренний параметр !). Затем , в очередном цикле While...End в случае , ес- ли ¦ F(X 5k+1 0)¦ < ¦ F(X 5k 0)¦ t=t/2 и снова выч исляется X 5k+1 0. Когда очередное X 5k+1 0 найдено , вычисляется Y 5k 0, а з атем и новое приб- лижение матрицы H. Итерационный процесс за канчивается , если ¦ F(X 5k+1 0)¦ < E. Если данное условие не вы полняется - итерацион- ный процесс продолжается заново. Формирование выходных значений-матриц про исходит внутри данного ц икла и поэтому никаких дополнительных действий не требуется , то есть с окончанием данног о цикла заканчивается и сама функция. 3. 1 FUN1.M Модуль , вычисляющий левые части Входные данные : X - вектор-строка , задающий точки для выч ис лений по каж- дой компоненте. Выходные данные : FF - вектор-строка , возвращающий значения кажд ой компо- ненты в определенной точке Язык реализации : PC MathLab Операционная система : MS-DOS 3.30 or Higher Пояснения к тексту модуля : В принципе , текст данного модуля н е требует пояснений . В нем пользователь реализует систему уравне ний , которая подлежит решению . То есть на входные значения X данная функция возвра- щает левые части по каждому уравнению . Единственное требование к да нному модулю - соблюдение форм ата , то есть входные и вы- ходные данные должны быть представлены в виде вектор-строк. 2Сравнительный анализ и 2оценка быстродействия. - 7 - Сравнительный анализ показал , что данн ый метод обладает неплохой сходимостью , так как попробованн ый метод простой ите- рации с параметром вообще отказался с ходиться для данной сис- темы . Однако хорошо подходит для срав нения дискретный метод Ньютона , так как данные методы практич ески одинаковы что по точности что по затратам. 1. Метод последовательной итерации обратной матрицы Якоби Число операций : порядка 682 Быстродействие : порядка 0.11 секунды 2. Метод Ньютона дискр етный Число операций : порядка 990 Быстродействие : порядка 0.22 секунды Как видно из вышеприведенных данных , эти два метода очень близки между собой , но метод Ньютона дискретный более сложен в реализации , однако обладает лучшей сходим остью, например при начальных значениях X 50 0=[2.0 2.0]; метод последователь ной ите- рации обратной матрицы Якоби уже не справляется , в то время как дискретный метод Ньютона продолжает неплохо работать . Од- нако метод Ньютона требует больших за трат машин ного времени и поэтому при выборе метода необходимо исходить их конкретных условий задачи и если известно довол ьно точное приближение и требуется быстрота вычислений , то к т аким условиям отлично подходит разработанный метод последовательно й итера ции обрат- ной матрицы Якоби. 2Выводы В данной РГР был разработан и реализован метод последова- тельной итерации обратной матрицы Якоби , предназначенный для решения системы нелинейных уравнений . Про грамма , реализованная на языке PC MathLab хотя и не является оптимальной , однако вы- полняет поставленную задачу и решает системы уравнений . Реали- зованный метод не отличается повышенной сходимостью и требует довольно точного начального приближения , однако довольно быст- ро схо дится к точному решению , то есть его можно порекомендо- вать для вычисления непростых систем нелинейных уравнений при наличии довольно точного начального прибл ижения и наличия вре- менных ограничений. 2Список литературы 1. О.М.Сар ычева . "Численные методы в экономике . Конспект лекций ", Новосибирский государственный технич еский универси- тет , Новосибирск 1995г. 2. Д.Мак-Кракен , У.Дорн . "Численные методы и программиро- вание на Фортране ", Издательство "Мир ", М . 1977г. 3. Н.С.Бахвалов . "Численные методы ", Издат ельство "Нау- ка ", М . 1975г.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
- Все неприятности когда-либо заканчиваются, уж поверьте мне.
- А вы, оптимист, однако.
- Нет, я - сторож на кладбище.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по математике ""Комплект" заданий по численным методам", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru