99427

Численные методы и оптимизация

Курсовая

Информатика, кибернетика и программирование

Получить линейную и квадратичную аппроксимирующие функции заданной функции yx методом наименьших квадратов для степенного базиса: выполнить расчет параметров линейной аппроксимирующей функции; получить систему нормальных уравнений и выполнить расчет ее параметров для проведения квадратичной аппроксимирующей функции; проверить полученные результаты; вычислить значения аппроксимирующих функций в узлах аппроксимации; построить график заданной функции множество заданных точек и графики функций линейной и квадратичной...

Русский

2016-09-14

178.18 KB

0 чел.

Московский  технический университет
связи и информатики

Курсовая работа по предмету

Информатика

Н.Новгород

2012 год

Задание

  1. Получить линейную  и квадратичную  аппроксимирующие функции заданной функции y(x) методом наименьших квадратов для степенного базиса:
  2. выполнить расчет параметров линейной аппроксимирующей функции;
  3. получить систему нормальных уравнений и выполнить расчет ее параметров для проведения квадратичной аппроксимирующей функции;
  4. проверить полученные результаты;
  5. вычислить значения аппроксимирующих функций в узлах аппроксимации;
  6. построить график заданной функции (множество заданных точек) и графики функций линейной и квадратичной аппроксимации;
  7. оценить качество аппроксимации.
  8. Найти два корня уравнения  с заданной точностью :
  9. отделить корни уравнения;
  10. проверить (аналитически) условия сходимости применяемых методов решения уравнений. В случае необходимости привести уравнение к виду, обеспечивающему сходимость процесса приближения к корню;
  11. выбрать начальные приближения;
  12. записать рекуррентную формулу для уточнения корня и произвести по ней расчеты;
  13. оценить погрешности.
  14. Вычислить  при разбиении отрезка интегрирования на n1=10 и n2=20 интервалов, где x1,  x2 - корни уравнения :
  15. оценить погрешность.
  16. Определить точку экстремума функции  методами одномерной оптимизации (с точностью ):
  17. проверить условие унимодальности функции и выбрать начальный отрезок оптимизации;
  18. провести расчеты по сокращению отрезка оптимизации и проверить условие окончания поиска минимума (максимума) функции.


  1. Нахождение линейной и квадратичной аппроксимирующих функций

Исходная функция  задана таблицей.

i

0

1

2

3

4

5

xi

7

9

11

13

15

17

y(x)

-1.976

-0.19

1.576

3.056

2.926

2.524

Линейная аппроксимирующая функция имеет вид

Найдем параметры линейной аппроксимации:

 

 

Проверим полученные данные средствами MathCad:

или

Искомая линейная аппроксимирующая функция примет вид:

Квадратичная аппроксимирующая функция имеет вид . Для определения параметров многочлена второй степени составим и решим систему нормальных уравнений.

Запишем в следующую таблицу элементы матрицы Грама и столбец свободных членов:

i

x0

x1

x2

x3

x4

y

xy

x2y

0

1

7

49

343

2401

-1.976

-13.832

-96.824

1

1

9

81

729

6561

-0.19

-1.710

-15.390

2

1

11

121

1331

14641

1.576

17.336

190.696

3

1

13

169

2197

28561

3.056

39.728

516.464

4

1

15

225

3375

50625

2.926

43.890

658.350

5

1

17

289

4913

83521

2.524

42.908

729.436

6

72

934

12888

186310

7.916

128.32

1982.732

Система нормальных уравнений примет вид:

Найдем решение этой системы уравнений:

Проверим полученные данные средствами MathCad:

Искомая квадратичная аппроксимирующая функция примет вид:

Значения исходной функции y(x), а также аппроксимирующих функций F1(x) и F2(x) в узлах аппроксимации приведены в таблице 3:

x

7

9

11

13

15

17

y(x)

-1.976

-0.19

1.576

3.056

2.926

2.524

F1(x)

-1.06124

-0.10901

0.84322

1.79545

2.74768

3.6999

F2(x)

-2.16402

0.11124

1.7249

2.67696

2.96742

2.59628

Графики  функций  линейной  и  квадратичной  аппроксимации  показаны  на рисунке

Оценим качество аппроксимации:

Для линейной функции: ρlin=0.85478

Для квадратичной функции: ρsq=0.22319

Получили, что ρ21, из чего можно сделать вывод, что квадратичная аппроксимация более качественная.

  1. Решение уравнения F2(x)=0 с точностью E = 10-3.

Решим уравнение  .

Найдем производные функции F2(x):

Для отделения корней уравнения составим таблицу знаков функции F2(x) и ее производной F2’(x):

x

7

9

19

21

F2(x)

-2.16402

0.11124

1.53654

-0.1308

Sign F2(x)

-

+

+

-

F2’(x)

1.30303

0.97223

-0.68177

-1.01257

Sign F2’(x)

+

+

-

-

На отрезках [7;9] и [19;21] функция F2(x) меняет знак, т.е. существует, по крайней мере, по одному корню, принадлежащему каждому из этих отрезков. Поскольку знак первой (и второй) производной на выбранных отрезках остается постоянным, то можно сказать, что функция на этих отрезках монотонна. Следовательно, выбранные отрезки содержат по одному корню.

  1. Уточним первый корень уравнения F2(x)=0 на отрезке [7;9] методом Ньютона.

Проверим выполнение достаточных условий сходимости метода Ньютона:

F2(x) непрерывна на отрезке [7;9]

F2(7)∙F2(9)<0

F2’(x) и F2”(x) отличны от нуля и сохраняют знаки при .

Выберем начальное приближение x0, удовлетворяющее условию

Возьмем x0=8, поскольку F2”(x)=-0.1654<0 и F2(8)<0.

Рекуррентная формула для уточнения корня уравнения по методу Ньютона:

Уточним корень уравнения на отрезке [7;9].

Условие окончания поиска корня:

Результат запишем в таблицу:

i

xi

F2(xi)

F2’(xi)

xi-1

xi-xi-1

0

8

-0.94369

1.13763

1

8.82952

-0.05691

1.00043

8

0.82952

2

8.88641

-2.67583∙10-4

0.99102

8.82952

0.05688

3

8.88668

-6.02921∙10-9

0.99097

8.88641

2.70008∙10-4

Оценим погрешность вычисления 1-го корня после 3 итераций, используя формулу , где , .

Получим .

Проверим найденный корень уравнения средствами MathCad:

Таким образом, x1=8.88668.

  1. Уточним второй корень уравнения F2(x)=0 на отрезке [19;21] методом итераций.

F2(x) дифференцируема и имеет разные знаки на отрезке [19;21].

Найдем итерирующую функцию. Итерирующая функция  обеспечивает выполнение условия сходимости  для . Выберем параметр λ по правилу:

В нашем случае r=1.01257 и F2’(x)<0, следовательно, . Пусть λ=0.9.

Запишем рекуррентную формулу для вычисления приближений к корню:

Выберем начальное приближение к корню, например, x0=20.

Условие окончания поиска корня:

Результат запишем в таблицу:

i

xi

F2(xi)

xi-1

xi-xi-1

0

20

0.79907

1

20.71916

0.14704

20

0.71916

2

20.8515

0.01774

20.71916

0.13234

3

20.86747

1.95535∙10-3

20.8515

0.01597

4

20.86922

2.10545∙10-4

20.86747

1.74992∙10-3

5

20.86941

2.27685∙10-5

20.86922

1.8949∙10-4

Оценим погрешность вычисления 2-го корня после 4 итераций, используя формулу , где .

Получим .

Проверим найденный корень уравнения средствами MathCad:

Таким образом, x2=20.86941.

  1. Вычисление определенного интеграла  методами Симпсона, трапеций и средних прямоугольников, полагая n1=10 и n2=20.

Вычислим интеграл

Метод средних прямоугольников:

Метод трапеций:

Метод Симпсона:

Результаты занесем в таблицу:

n

Метод средних прямоугольников

Метод трапеций

Метод Симпсона

10

Ip = 22.93436

It = 22.84409

Is = 24.07783

20

Ip = 23.54567

It = 23.55861

Is = 23.83782

Оценка погрешности по правилу Рунге:

Для методов средних прямоугольников и трапеций при k=2

Rср.пр. = 0.20377

Rтрап. = 0.23817

Для метода Симпсона при k=4

RСимп. = 0.016

Вычислим значение  средствами MathCad:

  1. Определение точки экстремума функции F2(x) методами одномерной оптимизации с точностью E=10-2.

Определим функцию

Для нахождения точки экстремума функции f(x) применим методы дихотомии и золотого сечения.

Выясним, унимодальна ли функция y(x), и выберем отрезок неопределенности. Рассмотрим отрезок [14.2;15.2].

Получили, что функция f(x) дважды дифференцируема на рассматриваемом отрезке, ее первая производная f’(x) не убывает на этом отрезке, а вторая производная f’’(x)>0. Таким образом, на отрезке [14.2;15.2] функция f(x) унимодальна, и, следовательно, этот отрезок может быть выбран в качестве начального отрезка неопределенности. Найдем точку экстремума методами дихотомии и золотого сечения.

Условия прекращения поиска:

Метод дихотомии:

i

a

b

x1

x2

f(x1)

f(x2)

b-a

0

14.2

15.2

14.698

14.702

-2.96597

-2.96609

1

1

14.698

15.2

14.947

14.951

-2.96826

-2.96821

0.502

2

14.698

14.951

14.8225

14.8265

-2.96839

-2.96843

0.253

3

14.8225

14.951

14.88475

14.88875

-2.96865

-2.96864

0.1285

4

14.8225

14.88875

14.85362

14.85763

-2.9686

-2.96862

0.06625

5

14.85362

14.88875

14.86919

14.87319

-2.96864

-2.96865

0.03513

6

14.86919

14.88875

14.87697

14.88097

-2.96865

-2.96865

0.01956

7

14.86919

14.88097

14.87308

14.87708

-2.96865

-2.96865

0.01178

8

14.87308

14.88097

14.87502

14.87902

-2.96865

-2.96865

7.89063∙10-3

После 8 итераций получили xmin=14.87702 и f(xmin)=-2.96865. Учитывая, что мы обозначали f(x)=-F2(x), значение исходной функции в этой точке F2(xmin)=2.96865.

Метод золотого сечения:

i

a

b

x1

x2

f(x1)

f(x2)

b-a

0

14.2

15.2

14.582

14.818

-2.9614

-2.96835

1

1

14.582

15.2

14.818

14.96392

-2.96835

-2.96804

0.618

2

14.582

14.96392

14.72789

14.818

-2.96679

-2.96835

0.38192

3

14.72789

14.96392

14.818

14.87376

-2.96835

-2.96865

0.23603

4

14.818

14.96392

14.87376

14.90818

-2.96865

-2.96857

0.14592

5

14.818

14.90818

14.85245

14.87376

-2.9686

-2.96865

0.09018

6

14.85245

14.90818

14.87376

14.88689

-2.96865

-2.96864

0.05573

7

14.85245

14.88689

14.86561

14.87376

-2.96864

-2.96865

0.03444

8

14.86561

14.88689

14.87376

14.87876

-2.96865

-2.96865

0.02129

9

14.87376

14.88689

14.87876

14.88188

-2.96865

-2.96865

0.01313

10

14.87376

14.88188

14.87686

14.87876

-2.96865

-2.96865

8.11468∙10-3

После 10 итераций получили xmin=14.87782 и f(xmin)=-2.96865. Учитывая, что мы обозначали f(x)=-F2(x), значение исходной функции в этой точке F2(xmin)=2.96865.

Выполним задачу оптимизации средствами MathCad:

Таким образом, функция  имеет максимум в точке x=14.87805.

 


Список литературы:

  1. Лекции по информатике
  2. Методические указания и контрольные задания по дисциплине Информатика. Численные методы и оптимизация. Г.К.Сосновиков, И.Б.Юскова, Н.П.Муравьев. 2008 г.
  3. Практическое решение инженерных и научных задач на ПК с использованием математических пакетов. В.Н.Шакин, Т.И.Семенова, О.М.Кравченко. 2010 г.

 

А также другие работы, которые могут Вас заинтересовать

79718. Механизм государства: понятие и структура. Орган государства: понятие, признаки, классификаци 140 KB
  Обобщая политический опыт развития эксплуататорских государств, можно определить государство как организацию для поддержания одних политических сил, стоящих у власти, над другими. Без механизма государства нет и самого государства
79719. Гражданское общество: основные этапы становления и сфера деятельности 62 KB
  Идея гражданского общества появилась в Новое время, в противовес всевластию государства. Концепцию гражданского общества в наиболее полном виде разработал Г. Гегель, немецкий философ.
79720. Понятие демократии. Предпосылки демократии. Институты прямой демократии 80.5 KB
  Критериями демократического общества в эту эпоху были: Возможность принятия главных решений всему свободными гражданами полиса большинством голосов; Занятие должностей по жребию; Периодические отчеты должностных лиц. Этому способствуют: открытые для прессы заседания коллегиальных государственных органов публикация их стенографических отчетов представление чиновниками деклараций о своих доходах существование свободных от цензуры и независимых от власти неправительственных СМИ; Выборность основных органов власти на основе всеобщего...
79721. Зарождение и развитие идеи правового государства 52 KB
  Признаки правового государства. К концу XX века человечество приблизилось к реальному воплощению выработанной веками идеи правового государства. У ее истоков стояли древние философы Платон и Аристотель но наиболее полное отражение концепция правового государства получили в работах Ш.
79722. Понятие гражданства и подданства. Категории физических лиц по их отношению к гражданству, их правовой статус 79 KB
  Гражданство - устойчивая правовая связь человека с государством, выражающаяся в совокупности их взаимных прав, обязанностей и ответственности, основанная на признании и уважении достоинства, основных прав и свобод человека.
79723. Понятие правового статуса личности и его структура. Основные международные документы о правах человек и их содержание 89.5 KB
  Правовой статус (положение) человека - это совокупность его прав и обязанностей. Права и обязанности закрепляются многочисленными законами и иными нормативно-правовыми актами, но особое значение в определении правового статуса личности имеет конституция государства.
79724. Понятие социальной нормы. Право и мораль. Право и другие социальные нормы 162 KB
  Право и другие социальные нормы. Значение любой нормы состоит в том что она указывает на те границы пределы в которых существует то или иное явление или объект сохраняя при этом свое качество и не утрачивая своей сущности.
79725. Теории происхождения права (основные направления учения о праве) 80 KB
  Некоторые из теорий происхождения права носят аналогичные названия теориям происхождения государств: теологическая, естественно-правовая, теория насилия, марксистская.
79726. Право и государство, их соотношение и взаимодействие. Понятие источников (форм) права 58 KB
  Какое выражение вам кажется более правильным: «Где общество, там и право» или «Где государство, там и право?». Сделаем вывод, что право существует далеко не во всяком обществе, в то время как ни одно государство не может существовать без установленных им правовых норм