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

Задание 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) должны быть близки, выбирают систему различных точек (узлов)    x₁, ...,x_m, число которых больше, чем количество искомых параметров c₁, ...,c_n , .  Далее, потребовав, чтобы сумма квадратов невязок во всех узлах была минимальна:

 

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

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

Выполнив  элементарные преобразования, получим  систему двух линейных уравнений относительно 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-ом отрезке [x_i-1, x_i] взять один центральный узел  x_i-1/2 = x_i - h/2, соответствующий середине отрезка. Функция на каждом отрезке аппроксимируется многочленом нулевой степени (константой)  P₀(x) = f(x_i-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) на каждом отрезке [x_i-1, x_i] интерполяционным многочленом второго порядка (параболой) c узлами x_i-1, x_i-1/2 , x_i После интегрирования параболы получаем

 

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

Погрешность формулы Симпсона имеет  четвертый порядок по 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) и для начала вычислений требуется задать одно начальное приближение x₀ из области сходимости, определяемой неравенством | f(x)f''(x) |<[f'(x)]². Метод Ньютона получил также второе название метод касательных благодаря геометрической иллюстрации его сходимости, представленной на рисунке. Этот метод позволяет находить как простые, так и кратные корни. Основной его недостаток – малая область сходимости и необходимость вычисления производной 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

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

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