Вопросы и ответы

1. Что такое численные методы, их назначение

2. Особенности численных методов

3. Итерационный процесс

4. Понятие о точности и скорости итерационного процесса

5. Сходимость итерационного процесса

6. Когда останавливается итерационный процесс?

7. Понятие оптимизации

8. Математическая задача оптимизации

9. Примеры критериев оптимальности и ограничений в задачах

оптимизации

10. Сущность методов поиска оптимума

11. Особенность симплексного метода поиска

Вопросы 4-6 см. на слайдах в конце презентации

#3 уравнения сходимость

12-17

… продолжение

12. Что такое аппроксимация?

2 значения слова «интерполяция»?

13. Суть Метода Наименьших Квадратов (МНК)?

14. Что такое задача Коши? Назовите 2 метода ее решения.

15. Какой метод точнее, Эйлера или Рунге-Кута?

​

16. Какую систему называют системой без резервирования?

С резервированием?

17. Как определить надежность и вероятность отказа

* системы последовательных элементов?

* системы параллельных элементов?

1. Назначение ЧМ, их сущность

и основные понятия

Предназначены для решения сложных инженерных задач, которые нельзя решить другими методами (аналитическими, «тыка»)

ЧМ − методы, основанные

на последовательных вычислениях,

на последовательном получении и использовании чисел

В сравнении с аналитическими

1-3

Теоретическая база

Математический анализ

Техническая база

АМ

ЧМ

Вычислительная математика

Можно «бумагу и карандаш»

Компьютеры

(с соответст. Software)

Имеет дело

с функциями

с ЧИСЛАМИ

Особенность A

Что за числа?

Осуществляется замена функции дискретным набором чисел − дискретизация задачи

a

b

В частности, используется «сеточное» представление функции – набор значений функции в равноотстоящих

(как правило) узлах «сетки»:

f(x) → {x_i, f(x_i)}, i = 0, 1, …, n

S

Квадратурные формулы

Такая замена «целого» «частью» − всей функции отдельными значениями (а также бесконечных процессов конечными, последовательностями отдельных значений) приводит к следующей особенности ЧМ →

В результате всегда приближенное решение

B

Обозначим:

X − точное (неизвестное) решение задачи

В частности: вектор (x₁, x₂, … x_k) – решение СЛАУ;

корень уравнения; функция – решение

дифференциального уравнения …

​

Всегда нужно оценивать, как далеко оценка результата от истины, поскольку всегда есть ошибка

Δ X − ошибка, погрешность приближенного решения

Она должна быть «разумной»

(строительство туалета и космического корабля)

Поэтому задается норматив точности − достаточно малое число ε

(максимальная допустимая ошибка)

– заданная точность

Δ X должна быть не больше ε, Δ X ≤ ε

Как этого добиваются?

Осуществляется пошаговый – итерационный процесс

Особенность C

Итерация − повторение

Обозначим s номер итерации (шага)

Схема процесса

​

X⁽⁰⁾

s [= 1]

X^(s), Δ X ^(s) ≤ ε ?

Задаваемое начальное приближение

Процесс последовательного

пошагового приближения

к решению задачи с заданной точностью

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

To be continued

Может расходиться

Что это означает?

x ⁽⁰⁾ → x ⁽¹⁾ … → x ^(s) → можем добраться до x при s → ∞

Итерационный процесс называется сходящимся к решению X, если расстояние между оценкой решения на итерации s

и точным решением стремиться к 0 при s→ ∞

• (X^(s), X) = | | X^(s) − X | | → 0 при s → ∞

Если условие не выполняется, процесс расходящийся

​

4-6

Реально s ≠ ∞

Когда остановка ИП?

2 принципа остановки Итерационного Процесса:

1. по заданной точности ε

�2) по заданному ресурсу

( числу итераций N )

ИП останавливают на итерации s, если на этой итерации оказывается Δ^(s) < ε

​

[в программах остановка

после выполнения условия подряд на 5 итерациях]

Если о корне, то остановка где-то в интервале x ± ε

В общем случае говорят:

приближенное решение находится в ε-окрестности (⋅) x,

т.е., в области , в которой

расстояние от любой (⋅) x^(s) до (⋅) x меньше ε

​

​

​

конкретная оценка

ошибки Δ

Тот метод считается более быстрым, который достигает заданной точности (Δ < ε) за меньшее число итераций N _ε

Число итераций N _ε, необходимое для достижения заданной точности − быстродействие (скорость) метода− критерий его эффективности

Другой критерий − точность метода ε _N

Тот метод считают точнее, который обеспечивает меньшую Δ за заданное число итераций N

Методы сравнивают по скорости и точности!!!

Об оптимизации #6

Оптимизация − определение наиболее

целесообразного варианта решения задачи

(с точки зрения поставленной цели)

Любая практическая деятельность имеет какую-либо цель

Существует множество способов достичь цели,

множество вариантов решения задачи,

но приходится выбирать и осуществить один

7-11

Примеры формулировок

разных по содержанию задач

​

1) Определить, как возить сырье на завод, чтобы затраты

на перевозки были наименьшими.

2) Сколько нужно положить цемента и добавки, какую

задать температуру в камере, чтобы получить

максимальную прочность материала?

Ц, Д, t° : R → max

3) Если требуется R ≥ 20 МПа, сколько Д и t°, чтобы

потратить как можно меньше Ц?

Д, t° : Ц → min

R ≥ 20

4) Так подобрать коэффициенты аппроксимирующего

полинома, чтобы сумма квадратов отклонений известных

значений от расчетных была минимальна.

?

МНК

1) транспортные затраты

Примеры:

2) R

3) Ц

4) сумма квадратов отклонений

Решить разные по содержанию задачи оптимизации позволяют общие математические методы

Для этого нужно описать задачу математически

Необходимо

математически описать

2 обязательных компонента

любой по содержанию

задачи оптимизации:

множество вариантов – набор решений, из которых

и надо выбрать лучшее

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

с тем, чтобы количественно оценить

каждый возможный вариант, сравнить варианты по степени близости к цели и выбрать самый близкий !

Для описания вводятся символьные обозначения

− возможное, допустимое решение

​

(Ц, t°, Д, …)

​

Это элемент множества решений

Множество таких элементов

​

​

(возможные t°, диапазоны содержания добавки, …)

​

1-ый обязательный компонент задачи

2-ой обязательный компонент задачи

Нужно определить Ω и f ( x ), чтобы задать математическую задачу

Математическая задача оптимизации:

​

Записывается символически:

​

Оптимальное решение:

​

Разные методы – разная тактика сбора информации и перемещения

Стратегия одна и та же

1. итерационный процесс

из некоторого начального приближения

Поиск это:

2. на каждой итерации (s) определяется

направление движения и делается шаг

в выбранном направлении

3. проверяется выполнение условия остановки;

например, если

x₂

x₁

Симплексный метод

Аппроксимация − замена «истинной» функции f(x) другой, достаточно близкой к ней функцией f_a(x), которую удобно использовать вместо f(x)

f_a(x ) − аппроксимирующая функция

Когда это нужно?

Когда f(x) неизвестна или слишком сложна

Что имеем в обеих ситуациях?

в общем случае

x − вектор

12-13

(1) f(x) неизвестна

Например, для η(τ), R(Ц), …

(2) f(x) известна но «сложна»

Обсчет каждой точки требует много ресурсов

вычисляются значения для ограниченного ряда узлов

y_i = f(x_i) ± Δ_i(в)

​

Для: прогнозирования,

проектирования,

принятия решений

из эксперимента знаем

y_i = f(x_i) ± Δ_i(э)

для ряда x_i, i =0, …, n

− (n + 1) узлов

​

смотрим на графиках

Δ(x)

Δ_i

Δ_a − критерий подбора f_a (x),

который нужно минимизировать

Принцип подбора f_a (x) :

так подобрать аппроксимирующую функцию,

чтобы ошибка аппроксимации

была минимальна, т.е.

f_a (x) : Δ_a → min

Разные методы аппроксимации используют разные конкретные Δ_a

В качестве критерия аппроксимации − меры,

по которой можно судить о близости f_a к f

и подобрать наиболее близкую к ней,

можно использовать:

​

♣ − мажорантную ошибку

Δ_a = max ⎮y_i − f_a(x_i)⎪ → min

^i=0,1,…,n

так заменить f, чтобы максимальное из отклонений d_i известных ее значений y_i от

ее оценок по f_a было минимальным

♣ − квадратичную ошибку

Наиболее часто используется как критерий аппроксимации

В любом случае

d_i

В качестве f_a используют функции простейшего вида

→ полиномы

f_a(x) = F(x) = a₀ + a₁x …+ a_jx^j …+ a_mx^m

Тогда остается так подобрать (M=m+1) ≤ (N=n + 1)

коэффициентов полинома степени m,

чтобы ошибка аппроксимации

Δ_a была минимальной

!

Чаще всего в инженерной практике

задача аппроксимации ставится так

Отсюда название метода аппроксимации

Метод Наименьших Квадратов → МНК

О методе наименьших квадратов

y = f(x) → f_a(x) = F(x) = a + bx

Имеем 2 неизвестных,

но и N = n+1

пар значений (x_i, y_i)

Полагаем в простейшешем случае, что зависимость линейна

Можно провести

«много» прямых, но

как чтобы Δ_a → min?

Выдвигается гипотеза о том, как y зависит от x

→ min

Используем квадратичную норму

и потребуем

замена f

Критерий МНК

a и b можно найти из условия минимума

«Нормальные уравнения»

СЛАУ относительно неизвестных коэффициентов аппроксимирующего полинома

+ статистический анализ,

если по данным эксперимента

Для более сложных F(x) c x_i², x_i³ …

и многофакторных

с x₁, x₂ … СЛАУ

в матричной форме

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

Интерполяция

(во 2-ом смысле)

Интерполяция − частный случай аппроксимации, когда требуется,

​

чтобы значения

приближенной функции

были равны

заданным значениям

исходной функции

​

в некоторых точках − узлах

интерполяции

Задача интерполяции − определение (восстановление) такой f_и(x) → F(x), чтобы F(x_i) = y_i ≈ f(x_i), i = 0, …, n

…

Построить кривую, проходящую

через (n+1) точек (x_i, y_i) − узлов

интерполяции

Используют интерполяционные полиномы − коэффициенты в которых равны известным значениям функции в узлах интерполяции

Интерполяционная

формула Лагранжа

Глобальная и локальная интерполяция

Линейная и квадратичная интерполяция

Задача Коши

− задача отыскания частного решения

обыкновенного дифференциального уравнения n-го порядка

с помощью начальных условий (задача с начальными условиями)

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

14-15

Решается численными методами

Вместо «точного решения» – функции y ( x )

приближенное решение – совокупность чисел,

таблица значений x | y

Двумя методами

To be finished