П.9. Что делать, если ДУ не может быть разрешено относительно старшей производной?

⇐ ПредыдущаяСтр 6 из 6

Так как ДУ не может быть решено относительно старшей производной, то тогда на каждом шаге решаем нелинейное уравнение относительно y⁽ⁿ⁾(все остальные неизвестные y,y’,y”,…, y⁽^n-1)-к этому моменту уже известны).

Решать уравнение относительно старшей производной любым методом(Хорд, МПД, Ньютона).

Замечание:

Таким образом, если ДУ не разрешается относительно старшей производной, то у нас возникает дополнительный цикл (самый внутренний) при написании программы.

Тема 7: Аппроксимация.

П.1. Постановка задачи аппроксимации.

Пусть некоторая функция у=f(x) задана в точках х₀,х₁,...,х_n. Фиксируем некоторый класс функций G.

Задача аппроксимации: выбрать среди функций g G некоторую функцию g^’, которая лучше всего приближает функцию f в узлах x_i. В отличие от интерполяции при аппроксимации не требуется, чтобы g(x_i)=y_i, а требуется лишь g(x_i) y_i. Обычно аппроксимацию применяют, когда значения функции f были известны не точно, а с некоторой погрешностью.

Конкретизация задачи аппроксимации.

Для оценки близости функции g и fсоставляется вектор невязок (погрешности)

R=(g(x₀)-f(x₀), g(x₁)- f(x₁), ... , g(x_n)- f(x_n)).

Очевидно, что мы будем идти к тому, чтобы норма R была намного меньше, при этом можно работать либо:

1. - минимизируется максимальное отклонение.

2. - минимизируем сумму отклонений.

3. - минимизируем сумму квадратов отклонений.

Легко реализуются вычисления именно для 2ой нормы.

В качестве класса аппроксимирующей функции G, рассмотрим всевозможные линейные комбинации базисных функций g₀,g₁,...,g_n.

базисные функции фиксированы.

П.2. Метод наименьших квадратов.

Фиксирован набор функций: g₀(x),g₁(x),...,g_k(x) даны (x₀,y₀),(x₁,y₁),...,(x_n,y_n).

- линейная комбинация функции g_j_,y_i =f(x_i) 0,…,n;

фиксируем набор:

R=(y₀-g(x₀), ... , y_n-g(x₀))

Для нахождения минимума функции S от (k+1) переменной, нам необходимо все её частные производные приравнять к 0. При этом получаем систему: (k+1) уравнения для (k+1) переменной ( ).

(7.1)

Получили СЛАУ (7.1). Эту систему можно решить методом Гаусса – она всегда имеет единственное решение в случае, если набор базисных функций был линейно независим в узлах , то матрица СЛАУ (7.1) невырожденная, поэтому решение будет существовать и единственное.

Пример аппроксимации полиномами:

базисные функции:

для аппроксимации функциями такого вида, нам необходимо решить СЛАУ 3 на 3:

C₀₀=

C₀₁=

C₁₀=

C₁₁=

C₀₂=

C₁₂=

C₂₀=

C₂₁=

C₂₂=

Тема 8: Нелинейная оптимизация.

Метод градиента (метод наискорейшего спуска).

П.1. Сведение системы линейных уравнений к задаче

нелинейной оптимизации (ЗНО) и наоборот.

Постановка задачи ЗНО:

Найти (8.1) минимум или максимум в некоторой области D.

Как мы помним из мат. анализа, следует приравнять частные производные к нулю.

Таким образом, ЗНО (8.1) свели к СНУ (8.2)

(8.2) n нелинейных уравнений.

Обратное: пусть дана СНУ

(S достигает своего минимума в точке, где все i-ые зануляются)

П.2. Метод градиента.

Наша задача найти минимум функций n переменных без ограничений на X.

Общая идея метода:

Возьмём некоторую стартовую точку Х (желательно, чтобы она была достаточно близка к минимуму функции).

Пусть - гладкая функция, тогда вектор градиента f в точке :

показывает направление наискорейшего роста функции. Соответственно вектор - показывает направление наискорейшего спуска.

Пойдём вдоль этого вектора, рассмотрим функцию

уравнение луча, исходящего из в направлении –grad

Идём вдоль этого луча до тех пор, пока не начнёт возрастать, т.е. не достигнет своего минимума. В этот момент (в точке ) мы остановимся и повторим такую же процедуру (т.е. пойдём из точки в направлении –grad, т.е. рассмотрим и т.д.)

Данную процедуру повторяем до тех пор, пока не достигнем заданной точности (применяем универсальный критерий прерывания )

Иллюстрация:

Итак, с помощью метода градиента нам удаётся многомерную ЗНО свести к одномерной ЗНО, т.е. нам необходимо научиться находить минимум функций одной переменной (на первом шаге минимум , на втором шаге и т.д.)

П.3. Решение одномерной ЗНО.

Нам необходимо найти минимум некоторой функции f (одной переменной) на интервале [a,b]. Будем считать, что f на данном интервале имеет ровно один минимум.

Простейший метод нахождения точки минимума – метод сечений:

Разобьем участок [a,b] на n интервалов и

рассмотрим . Предположим

минимум достигается при , тогда

новый участок поиска будет [ ]

его снова разбиваем на новые участки

(критерий как в МПД, т.е. ).

Рассмотрим вариант n=3 (ежу понятно,

что делить меньше чем на 3 интервала

бессмысленно).

( ) (*)

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

Пропорции деления (они сохраняются) были подобраны таким образом, что при переходе к новому интервалу нам необходимо вычислять значения f не в 2х новых точках, а в 1-ой, хотя при этом интервал поиска сокращается не в два раза (как было на предложенной схеме (*)), а чуть меньше, следовательно, этот вариант оказывается выгоднее, т.к. для достижения заданной точности нам придётся меньше раз вычислять значение f. 4 точки на первом шаге и по 1-ой новой точке на каждом последующем шаге, а не в 2х.

Найдём пропорции золотого сечения:

Итак, в алгебре метода золотого сечения заложены пропорции: 0,382 ; 0,236 ; 0,382.

Тема 9: Метод Монте-Карло.

Дата добавления: 2018-04-05; просмотров: 250; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 2 3 4 56

Мы поможем в написании ваших работ!