Вычислительные методы и методы оптимизации в экономике

Задание 1

1. Решить СЛАУ методом Гаусса или одной из его модификаций.

Решение:

Метод Гаусса основан на приведении с помощью преобразований, не  меняющих решение исходной СЛАУ с  произвольной матрицей, к СЛАУ с  верхней треугольной матрицей вида:


 

 

 

Этап приведения к системе с  треугольной матрицей называется прямым ходом метода Гаусса. Решение системы с верхней треугольной матрицей находится по формулам, называемым обратным ходом метода Гаусса:

Прямой ход метода Гаусса осуществляется следующим образом: из m-го уравнения (m=2,3,…,n) вычитается первое уравнение, умноженное на , и вместо m-го уравнения подставляется полученное. В результате в матрице системы исключаются все коэффициенты 1-го столбца ниже диагонального. Затем, используя 2-е полученное уравнение, аналогично исключаются элементы второго столбца (m=3,4,…,n) ниже диагонального и т.д. Такое исключение называется циклом метода Гаусса. Проделывая последовательно эту операцию с расположенными ниже k-го уравнениями (k=1,2,…,n-1) приходят к системе с треугольной матрицей. При указанных операциях решение СЛАУ не изменятся. На каждом k-ом шаге преобразований прямого хода элементы матриц изменяются по формулам прямого хода метода Гаусса:

Элементы  называются главными. Если в ходе расчётов по данному алгоритму на главной диагонали окажется нулевой элемент = 0, то произойдёт сбой. Для того, чтобы избежать этого, следует каждый цикл по k начинать с перестановки строк: среди элементов k-го столбца находят номер p главного, т.е. наибольшего по модулю, и меняют местами строки k и p. Такой выбор главного элемента значительно повышает устойчивость алгоритма к ошибкам округления, т.к. в формулах прямого хода метода Гаусса при этом производится умножение на числа меньшие единицы и ошибка, возникавшая ранее, уменьшается.

Решим этим методом нашу систему:

Исключаем коэффициенты 1-го столбца, расположенные ниже 1-ой строки:

Выполним перестановку 2-ой и 3-ей строк:

Исключив второй коэффициент третей строчки системы, получим систему с верхней треугольной матрицей:

Выполнив обратный ход получаем:

Решение данной системы в математическом пакете Maple даёт следующие результаты:

Округлив с заданной точностью, получаем:

2. Решить СЛАУ методом квадратного корня.

Решение:

Блок-схема алгоритма:

 

Матрица S вычислена, теперь можно найти решение.

Теперь вычислим в математическом пакете Maple:

 

Округлив, получим:

=

Ответ: =

 

 

 

 

 

 

 

 

 

 

 

 

Задание 2

1) Постройте интерполяционный многочлен  Лагранжа для функции  с заданными узлами

2) вычислите его значение в  точке  ;

3) сравните с соответствующим  значением  заданной функции, определив относительную погрешность (в %).

Решение:

Интерполяционный многочлен Лагранжа имеет вид:

   (1)

Произведение  выбрано так, что во всех узлах, кроме k-го, оно обращается в нуль, а в k-м узле оно равно единице:

Из выражения  (1) видно, что

1) Построим многочлен Лагранжа  для заданной функции:

В общем  виде он будет такой:

Теперь подставим заданные узлы:

2) Вычислим  значение найденного многочлена  в точке  :

3) Теперь вычислим значение заданной  функции в точке  :

Относительная погрешность аппроксимации  многочленом Лагранжа равна:

или

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

Ответ: , ,

 

 

 

 

 

Задание 3

Методом наименьших квадратов найдите  эмпирическую формулу вида            

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

Решение:

Метод наименьших квадратов является частным случаем среднеквадратичной аппроксимации. При использовании  метода наименьших квадратов аналогично задаче интерполяции в области значений x, представляющей некоторый интервал [a, b], где функции f(x) и j(x) должны быть близки, выбирают систему различных точек (узлов)    x1, ...,xm, число которых больше, чем количество искомых параметров c1, ...,cn , .  Далее, потребовав, чтобы сумма квадратов невязок во всех узлах была минимальна:

 

находят из этого условия параметры c1, ...,cn.

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

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

Решив эту систему, находим искомые  параметры:

Составим расчетную таблицу:

1

1,8

1

1,8

2

1,3

4

2,6

3

3,3

9

9,9

4

4,8

16

19,2

5

3,8

25

19

=15

=15

55

=52,5


Вычислим коэффициенты a и b:

Получаем эмпирическое уравнение линейной регрессии:

Вычисление в maple:

Построим в одной системе  координат график найденной функции  и исходных точек:

 

Ответ:

 

 

 

 

 

 

 

 

 

 

 

Задание 4

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

Решение:

Формула средних получается, если на каждом i-ом отрезке [xi-1, xi] взять один центральный узел  xi-1/2 = xi - h/2, соответствующий середине отрезка. Функция на каждом отрезке аппроксимируется многочленом нулевой степени (константой)  P0(x) = f(xi-1/2). В этом случае получим:

Погрешность формулы средних имеет  второй порядок по h:

.

Составим расчётную таблицу:

0

    

0,1

0,05

2,236

0,2

0,15

2,235

0,3

0,25

2,233

0,4

0,35

2,226

0,5

0,45

2,216

0,6

0,55

2,199

0,7

0,65

2,174

0,8

0,75

2,140

0,9

0,85

2,094

1

0,95

2,035

21,788


И вычислим интеграл:

Формула Симпсона получается при аппроксимации  функции f(x) на каждом отрезке [xi-1, xi] интерполяционным многочленом второго порядка (параболой) c узлами xi-1, xi-1/2 , xi После интегрирования параболы получаем

 

После приведения подобных членов формула  приобретает удобный для программирования вид:

Погрешность формулы Симпсона имеет  четвертый порядок по h:

Для формулы Симпсона также составим расчётную таблицу:

0

    

1,414

0,1

0,05

2,236

1,415

0,2

0,15

2,235

1,417

0,3

0,25

2,233

1,424

0,4

0,35

2,226

1,437

0,5

0,45

2,216

1,458

0,6

0,55

2,199

1,489

0,7

0,65

2,174

1,531

0,8

0,75

2,140

1,585

0,9

0,85

2,094

1,652

1

0,95

2,035

1,732

21,788

21,896


И вычислим интеграл:  

Формула Симпсона даёт лучшее приближение для функции и, соответственно, меньшую  погрешность, чем формула средних прямоугольников.

Вычисление в maple даёт тот же результат, что и формула Симпсона:

Ответ:

 

 

 

 

 

Задание 5

Отделите корни данного уравнения  аналитически и уточните больший  из них методом Ньютона.

Решение:

Метод Ньютона является модификацией метода простой итерации и часто называется методом касательных. Если f(x) имеет непрерывную производную, тогда, выбрав в ψ(x)=-1/f'(x), получаем эквивалентное уравнение x=x–f(x)/f'(x)=φ(x), в котором q≈|φ'(x*)|≈0. Поэтому скорость сходимости рекуррентной последовательности метода Ньютона

вблизи корня очень большая, погрешность очередного приближения  примерно равна квадрату погрешности предыдущего . Очевидно, что этот метод одношаговый (m=1) и для начала вычислений требуется задать одно начальное приближение x0 из области сходимости, определяемой неравенством | f(x)f''(x) |<[f'(x)]2. Метод Ньютона получил также второе название метод касательных благодаря геометрической иллюстрации его сходимости, представленной на рисунке. Этот метод позволяет находить как простые, так и кратные корни. Основной его недостаток – малая область сходимости и необходимость вычисления производной f'(x).

Данное уравнение 3-ей степени, поэтому  у него не более трёх корней.

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

-5

-4

-3

-2

-1

0

1

2

3

4

5

-309

-115

-11

27

23

1

-15

-1

67

213

461


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

Больший из них находится в интервале .

В качестве первого приближения выберем левую границу интервала: .

Вычислим первую производную функции  : , и используя рекуррентную формулу Ньютона находим :

.

Т.к. , то нужно выполнить ещё один шаг:

Значит, можно использовать в качестве приближения большего корня заданного уравнения. Округлив с заданной точностью, получаем:

Вычисление в maple даёт тот же результат:

Ответ:

 

 

Задание 6

Составьте таблицы приближенных значений решения данного дифференциального  уравнения  , удовлетворяющего начальному условию на отрезке [1;2] с шагом h=0,2 с помощью методов Эйлера и Рунге-Кутта,  Сравните полученные результаты с точными, определив относительную погрешность в каждой точке (в %).

Решение:

Изобразим предложенные в условии методы с помощью блок-схем:

Точное решение задачи Коши найдём методом Лагранжа:

Решаем сначала однородное уравнение:

:

Составим искомую таблицу:

Предиктор

1

0,000

0,000

0,000

  

0,100

0,000

0,000

1,2

0,192

0,200

0,044

1,1

0,298

0,191

0,002

1,4

0,397

0,396

0,000

1,3

0,507

0,399

0,006

1,6

0,642

0,618

0,037

1,5

0,750

0,641

0,001

1,8

0,943

0,881

0,066

1,7

1,037

0,930

0,014

2

1,313

1,194

0,091

1,9

1,379

1,273

0,030


Схема Рунге-Кутта имеет большую  степень точности, чем метод Эйлера.

С помощью Maple можно вычислить точное решение задачи Коши:

А вычисление сетки сделаем в Excel:

Ответ:

 

Задание 7

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

Решение:

Выразим из 1-го уравнения системы y и подставим во второе:

Решим второе уравнение методом простой итерации.

Суть метода:

Очень часто в практике вычислений встречается ситуация, когда уравнение  записано в виде разрешенном, относительно x:

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

Метод является одношаговым, и для начала вычислений достаточно знать одно начальное приближение x0=a или x0=b или x0=(a+b)/2.

Для начала проверим сходимость метода для нашего уравнения: сходимость метода выполняется для любого x.

Судя по графику функции

Решение лежит в интервале [-1;0]. Выберем в качестве первого приближения середину этого интервала: . Далее проведём итерации, пока не добьёмся заданной точности:

Теперь выразим 

Maple выдаёт тот же результат, с поправкой на округление:

Ответ:

 

 

 

 

 

Задание 8

1)Решите  задачу линейного программирования  графическим методом.

Найдите максимальное и минимальное  значения целевой функции.

Решение:

Графический метод решения ЗЛП  заключается в следующем: в одной системе координат строим область соответствующую набору ограничений, заданных в условии, и график уравнения . Далее сдвигаем прямую так, чтобы она имела только одну общую точку с областью ограничений. Координаты полученных точек и будут соответствовать оптимальным.

Из рисунка видно, что минимум  функции достигается в точках : ,

а максимум в точках : .

В Maple решение выглядит так:

Ответ: ; .

2) Предприятие выпускает два вида изделий П1 и П2, на изготовление которых идет три вида сырья: S1, S2, S3, запасы которых соответственно равны 200, 110, 120 кг. Расход сырья на 1000 ед. продукции составляет: S1 – 20, 10; S2 – 15, 5; S3 – 10, 10. Оптовая цена за 1000 шт. изделий соответственно равна:  15 и 17 тыс. руб. Себестоимость производства 1000 шт. изделий составляет 12 и  15 тыс. руб. Составить план выпуска продукции, обеспечивающий максимальную прибыль, предполагая, что сбыт неограничен.

Решение:

Для решения данной задачи нужно  составить соответствующую ЗЛП.

Количество выпущенных изделий (в тыс.шт.) П1 обозначим , а изделий П2 - .Естественно и не могут быть отрицательными и дробными.

Производство 1000шт. изделий П1 приносит прибыль: 15000-12000=3000, а производство 1000шт. изделий П2 приносит прибыль: 17000-15000=2000.   Функция, которую необходимо максимизировать будет такой:

.

Поскольку запасы сырья ограничены, то на и накладываются следующие ограничения:

Итак, нам нужно решить следующую  ЗЛП:

Решим данную ЗЛП методом симплексных таблиц:

Приведём систему к каноническому  виду:

Составим симплекс-таблицу и  по правилам преобразования, получим  оптимальное решение:

 

b

  

-3000

-2000

0

0

0

0

  

20

10

1

0

0

200

10

15

5

0

1

0

110

7,333

10

10

0

0

1

120

12


 

 

b

  

0

-1000

0

200

0

22000

  

0

3,333

1

-1,333

0

53,333

16

1

0,333

0

0,0667

0

7,333

22

0

6,667

0

-0,667

1

46,667

7


 

 

b

0

0

0

100

150

29000

0

0

1

-1

-0,5

30

1

0

0

0,1

-0,05

5

0

1

0

-0,1

0,15

7


 

Получено оптимальное решение: .

 

Таким образом, предприятию следует  выпускать 5000 единиц изделия П1 и 7000 единиц изделия П2, при этом оно получит максимальную прибыль:

Вычисление в maple:

Ответ: 5000 единиц изделия П1 и 7000 единиц изделия П2.

 

 

 

 

 

 

Задание 9

  Найдите минимальное значение  функции   и точку ,  в которой оно достигается, методом золотого сечения.

Решение:

Золотое сечение – это такое  деление отрезка [a, b] на две неравные части при котором отношение большего отрезка ко всему интервалу равно отношению меньшего отрезка к большему. При этом имеет место следующее соотношение

О точке, которая расположена на расстоянии длины от одного из концов отрезка, говорят, что она осуществляет золотое сечение данного отрезка. Каждый отрезок имеет две такие точки, расположенные симметрично относительно середины. Алгоритм поиска минимума аналогичен вышеописанному методу деления пополам и отличается тем, что вначале точки x1 и x2 выбираются так, чтобы они осуществляли золотое сечение отрезка, и вычисляются значения функции в этих точках

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

 

Алгоритм метода.

Задаются a, b и погрешность e.

1. Вычисляются две точки золотого  сечения 

.

2. Если то ,

   иначе

3. Если  , то повторить  с п. 2.

4. Вычисляется  .

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

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

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

. С увеличением  значение увеличивается (возрастающая функция на ), также увеличивается значение . Поэтому, на промежутке функция . Соответственно возрастает на этом промежутке.

Исследуем теперь промежуток методом золотого сечения с точностью 0,001.

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

Придя к заданной точности, вычислим минимальные значения:

Вычислим теперь минимальное значение с помощью Maple:

Ответ:

 

 

 

 

 

 

 

 

 


Вычислительные методы и методы оптимизации в экономике 📙 Контрольная → 🆔 20561

Вычислительные методы и методы оптимизации в экономике 📙 Контрольная → 🆔 20561

Вычислительные методы и методы оптимизации в экономике